Thursday, April 29, 2010

Persistent store: a new record type

The object map allows us to abstract away the physical addresses where our objects are stored, but only if we can remember where we put it! We need another record type and things will get much more interesting.

A commit-record is a special record that we will write to the durable storage. The commit-record will contain (among other things) the physical address of the root of the object map. We'll require a little more functionality from the durable storage layer. When we first use a previously existing persistent store, we need to ask the durable storage layer to find the most recent valid and complete commit record. It can do this by starting at the newest record and reading backwards through earlier records until it finds one.

Since computers are unreliable, we have to take into account the possibility that the computer could crash in the middle of writing a commit record. When looking for the commit record on restart, we ignore any partially written commit records. When we're writing a commit record to the durable storage, we don't return control until we're sure that the record is durably saved and complete. If the computer crashes at any time before that last byte is written, we will recover using the previous valid commit record, and if it crashes at any time after that last byte is written we'll use this one.

There is an extra burder on the durable store to be able to find the most recent commit record, but we can take a different burden off the store. Instead of insisting that every record be durably written at the time we send it to the store, we can allow most of the records to be buffered until it is more convenient to write. We only insist that the buffers be flushed prior to writing the commit record. This makes a huge difference in the performance of the store.

There is a design decision to be made at this point. When we save durable objects, we can either send the object and the object-map records to the durable store immediattely, or we can defer sending them until we want to write the commit record. The eager strategy is more responsive when we are doing a lot of writes because we can start writing records while we're computing. The lazy strategy will reduce the total amount of traffic (every time we modify the object-map, we need to write new object-map records, if newer entries supersede records that haven't even been written, we can elide the write), but when we eventually do write the commit record, there will be a flurry of activity as we force the pending writes. This will cause a noticable pause at commit time.

There is another interesting design decision. In many cases, it is ok to lose a few seconds of work if the computer crashes. You wouldn't want to lose anything if you were logging financial transactions, but if you were checkpointing a text file, you might consider it ok if two or three of the most recently typed letters didn't get saved. When the computer restarted, you'd re-open the text file and find that what you were typing wasn't completely there, but was mostly there. You can re-enter the last couple of keystrokes. If this is acceptable — and it is for some applications and not for others — then it is not necessary for commit records to be immediately written to durable storage so long as they are written in a reasonably timely manner (within a second or two). The freedom to defer writing commit records like this will also improve performance quite a bit.

Exercise: Add commit records to your durable store and the ability to recover the most recent commit record when opening an existing store.

1 comment:

Faré said...

It's not clear what your leaves are here and how they relate to objects or don't.