14 KiB

Raw Permalink Blame History

created_at

title

url

author

points

story_text

comment_text

num_comments

story_id

story_title

story_url

parent_id

created_at_i

_tags

objectID

year

2017-08-27T22:05:52.000Z

Accountants Don’t Use Erasers (2007)

https://blogs.msdn.microsoft.com/pathelland/2007/06/14/accountants-dont-use-erasers/

tosh

1503871552

story

author_tosh

story_15113079

15113079

2007

Source

Accountants Don’t Use Erasers – PatHelland's WebLog

Search MSDN

Search all blogs

Search this blog

PatHelland's WebLog PatHelland's WebLog

Accountants Don’t Use Erasers

★★★★★

★★★★

★★★

★★

★

Pat HellandJune 14, 20074

Many kinds of computing are "append-only". By that, I mean that observations about the world are recorded in perpetuity. Derived results from those observations may be calculated on demand (or kept as a running tally) but you can't rewrite history.

I spent much of my career working on the transaction plumbing for database systems. In these systems, all changes are made to a transaction log. The log describes both the before and after images of all record changes made by each transaction. The log is appended to at a rapid clip (indeed, some of the fun performance optimizations in achieving the astonishing throughput of SQL Server and other database systems are about optimizing the writes to the tail of the log). You NEVER modify the log other than by appending to the end of it. You archive the log for posterity. In the past, you might delete old log files after many months or years. Nowadays, legislation makes that more problematic.

Well, if EVERYTHING in the history of the database is represented in the log, what is the actual database itself? Well, it is a rollup of a view of the changes represented in the log. The database is a cache of a subset of the log (the subset that represents the latest updates to all the records by the transactions that happened to commit).

So, accountants don't use erasers or they end up in jail. When an entry is made in the accounting records, it will live forever. There may be another entry added to ensure that a mistake is corrected but the mistake will not be erased. The summary of the impact of all of these accounting entries will occasionally be tallied (e.g. your end-of-month balance for your checking account). Now, the June statement may not reflect some outstanding (and uncashed) checks you've written but those are likely to show up in July's statement. Quarterly results issued to corporate stockholders will usually include some small correction to earlier quarterly results because of small transactions that legally occurred in the earlier quarter but whose accounting information wasn't rolled up in time for that quarter. There is uncertainty in the result and that is acknowledge by the mechanism of republishing corrected results.

The Append-Only View of Distributed Single-Master Computing

Distributed work is frequently represented as append-only artifacts on the interoperating systems. When you deposit your neighbor's check in your account, an entry is made into your bank account showing a deposit and some linkage to the check and your neighbor's bank. If your bank is smart, a hold is placed on the funds. When the physical check is shipped to the clearing house to be sent to your neighbor's bank, his bank identifies the account and attempts to debit the account. If the check clears, funds are moved from bank to bank and the hold is released on the funds (admittedly, sometimes these holds are timeout based rather than linked to the clearing of the check). If the check bounces (it is, after all, from your neighbor), a debit is appended to your account (both for the amount of the check and for the fine associated with having an idiot for a neighbor). None of this involved deleting or updating ANYTHING except the interim rollup balance of your checking account which could be calculated on demand. Frequently, a new interim balance is just appended to the bank account.

Lots of today's computing follows this pattern. Inventory balances are maintained by tracking incoming and outgoing changes to the inventory. Sometimes, the inventory balance (in a centralized system) is characterized as "At this time on this date, the inventory for product-X is amount-Y". In this fashion, the information about the balance is true in perpetuity. It just becomes as artifact of history.

Knowledge and Event-Horizons

In a replicated system (say there are N replicas with an opinion of the balance), it becomes more complex. Imagine a world in which independent actions are taken by replicas which are making guesses (see "Memories, Guesses, and Apologies") and the knowledge of these guesses is gradually oozing back-and-forth across the replicas. By all the replicas sharing their knowledge of the changes that they have made over time, you end up with two opinions chasing each other within each replica.

First, there is a point in history prior to which your replica-K has complete knowledge of what ALL the other replicas have done... "Gee, I haven't heard from replica-J since 9AM last Wednesday but prior to that, I know what all N replicas have done." That means YOU have complete knowledge of what happened to the inventory of Product-X up until 9AM last Wednesday (assuming a tight control of the set of N replicas). Since then, you have partial knowledge.

Now if I hear from Replica-K about his changes that have occurred since last Wednesday, I can advance my uncertainty window to Wednesday at 10PM which was the last time I heard from Replica-1. This is an ongoing way to cope with independent decision making and the coping with uncertainty. It is an extension (for multi-master decision making) on the way in which a running balance is managed in a bank account (which processes "the truth as of a point in time" in a centralized fashion).

Now, you say, I am MAD! Stark raving MAD! How can people cope with the chaos and confusion. Well, as I pointed out when discussing my take on the CAP Conjecture, consistency is what people are frequently willing to sacrifice to ensure unfettered availability in the face of partitions.

[As an aside, in my misspent youth, I was chief architect and lead programmer for Tandem's NonStop Transaction Monitoring Facility (TMF) which did the database logging and recovery for Tandem's NonStop SQL. Think of this as the data-protecting and preserving part of the super-duper high-availability system of its day. On the (really pretty rare) times when a system was stuck and needed help to get going, early in my tenure I worked hard to guarantee transactional consistency. I wanted to ensure we did NOT bring the database back online unless we correctly processed all the committed and aborted transactions and recreated a pristine and correct system. As I gained more experience, I noticed a large percentage of the customers (but certainly not all of them) just plain wanted the durn thing up and running... They would figure out the mess later. As I matured (well... at least aged), I learned to ask at the beginning of the crisis whether the priority was availability or the priority was correctness. I was surprising the number of times availability was more important. ]

So, two interweaving themes are being presented:

You don't really ever delete ANYTHING. As a matter of fact, you don't update anything either... You just accrete new knowledge and distill new implications based upon your increasing knowledge.
People (and applications) will act on their partial knowledge and then, when learning new facts, take new actions. Sometimes, you realize you shouldn't have taken the action but, gee, it was a great decision based on what you knew at the time. Since you weren't omniscient, you could have perfect knowledge and could make perfect decisions... Shit happens and you deal with it.

Idempotence and the Lack of Erasers

One final observation... If you never forget anything and never change it, providing idempotent processing takes a completely different twist. You wrote everything down and, if you hear it again, it's just old news to be dropped on the floor. That's cool.

More to be written soon about:

Idempotence, and
Generating output with elevated abstractions to ensure commutativity
Dampening algorithms in redundantly executing multi-master systems...

I've added these to the list of blog entries to write... the list keeps getting longer as I think of things to rant about faster than I am ranting. Sigh.

- Pat

Comments (4)