<!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><div style="font-family:Arial;">I've been thinking about this one for a very long time. It's still not going to be as excellent as zeroskip, but it has the advantage that it's still a single file, and it fixes two of the three defects of twoskip:<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Those three defects are:<br></div><div style="font-family:Arial;">1) poor write locality - updates happen throughout the file<br></div><div style="font-family:Arial;">2) long repack freeze gives unpredictable performance<br></div><div style="font-family:Arial;">3) no MVCC reads - writers block all readers.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Threeskip will fix two of those! Numbers 2 and 3.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">For comparison, here's the twoskip ondisk format:<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* HEADER: 64 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* magic: 20 bytes: "4 bytes same as skiplist" "twoskip file\0\0\0\0"<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* version: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* generation: 8 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* num_records: 8 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* repack_size: 8 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* current_size: 8 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* flags: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">*<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* RECORDS:<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* type 1 byte<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* level: 1 byte<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* keylen: 2 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* vallen: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* <optionally: 64 bit keylen if keylen == UINT16_MAX><br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* <optionally: 64 bit vallen if vallen == UINT32_MAX><br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* ptrs: 8 bytes * (level+1)<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_head: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_tail: 4 bytes<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* key: (keylen bytes)</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* val: (vallen bytes)</span><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;"><br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* padding: enough zeros to round up to an 8 byte multiple</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;"></span><br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Threeskip is almost exactly the same, with three types (and of course with 'threeskip file\0\0\0' in the header)<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">RECORD<br></div><div style="font-family:Arial;">NEWVALUE<br></div><div style="font-family:Arial;">DELETE<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">RECORD:</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* type 1 byte</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* level: 1 byte</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* keylen: 2 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* vallen: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* <optionally: 64 bit keylen if keylen == UINT16_MAX></span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* <optionally: 64 bit vallen if vallen == UINT32_MAX></span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;"><b>* latestptr: 8 bytes (new)</b></span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* ptrs: 8 bytes * (level+1)</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_head: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_tail: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* key: (keylen bytes)</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* val: (vallen bytes)</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* padding: enough zeros to round up to an 8 byte multiple</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;"></span><br></div><div style="font-family:Arial;"><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">NEWVALUE:<br></span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* type: 1 byte<br></span></div></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* padding: 3 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* vallen: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* <optionally: 64 bit vallen if vallen == UINT32_MAX></span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;"><b>* prevptr: 8 bytes</b></span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_head: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_tail: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* val: (vallen bytes)</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* padding: enough zeros to round up to an 8 byte multiple +1</span><br></div><div style="font-family:Arial;"><div style="font-family:Arial;"><br></div></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">DELETE:<br>* type: 1 byte</span></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* ZEROS: 7 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* prevptr: 8 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_head: 4 bytes</span><br></div><div style="font-family:Arial;"><span class="font" style="font-family:menlo, consolas, monospace, sans-serif;">* crc32_tail: 4 bytes (ZERO)</span><br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">This gives us MVCC! When you start a read transaction, the transaction includes the length of the file at the time of transaction start. The reader holds the same filehandle open, meaning it can keep reading even after a repack. If it reads past the transaction length, it just moves on to the next record. If it follows the latestptr past the transaction length, it just follows the prevptr back until it's at the latest value within the transaction.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">(DELETE already had a prevptr, but it was less powerful)<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>DUAL LOCKING<br></b></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">With this comes a second MVCC help. We use two different writelocks, which can be achieved with ranged flock within the header. Lock number 1 is held for the entire transaction and avoids any other writer. Lock number 2 is ONLY held for the duration of writing a single record and updating the related pointers. Readers take a shared lock on number 2 only, which allows them to guarantee clean reads.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>NON-BLOCKING REPACK</b><br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">The repack process can take an MVCC read and stream those records to a new file $DB.new (on which it holds an exclusive lock to avoid racing repacks), and then it can replay the log from there. Even the log replay can be done with read locks if the log length is over a certain amount (though this can lead to starvation, so should be a limited number of times) . The final fsync and rename needs to be done with a writelock on the source file of course.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Reading the log, if we hit a NEWVALUE or DELETE, we follow the prevptrs back to find out the key that it references.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">It might be necessary to have a "repackd" which does the actual repacking, or some other way of a process saying "I don't mind waiting on the repack" because otherwise the repack freeze will still be visible to the current client, even if other readers and writers can continue.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>STORAGE COST COMPARISON</b><b><br></b></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">This adds an extra 8 bytes to the overhead for every CREATE record. The DELETE record is the same size. The NEWVALUE record no longer has the cost of an extract copy of the key in it. So it will use slightly more storage on newly repacked databases.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">(The base-level average overhead of a twoskip record is 40 bytes, this makes it 48)<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>COMPUTATIONAL AND IO COST COMPARISON</b><b><br></b></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Calculating "repack_size" will be a little more costly, but not too bad.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Replacing values will be much cheaper because we don't need to update pointers. In theory we could even "row lock" or "gap lock" if we wanted other concurrency levels.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>CRC ALGORITHM</b><b><br></b></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Since we have a choice with a new format, clearly we'd go with something fast! CRC32c with hardware acceleration all the way.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><b>CRASH SAFETY AND THE OTHER TWOSKIP BENEFITS</b><br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">All still there just as much as ever. Of course, write locality is helped slightly (overwrite and delete only touch the current record) but it's still the issue that will make zeroskip a better DB format.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Bron.<br></div><div style="font-family:Arial;"><br></div><div id="sig56629417"><div>--<br></div><div> Bron Gondwana, CEO, Fastmail Pty Ltd<br></div><div> brong@fastmailteam.com<br></div><div><br></div></div><div style="font-family:Arial;"><br></div></body></html>