[siculars]

There seems to be three things they are doing to reach their higher performance:

1. Multi-threaded synchronized write ordering. I'm interested in the internal synchronization mechanism...

"LevelDB uses very coarse-grained synchronization which forces all writes to proceed in an ordered, first-come-first-served fashion, effectively reducing throughput to that of a single thread. HyperLevelDB increases concurrency by allowing multiple threads to agree on the order of their respective writes, and then independently apply the writes in a manner consistent with the agreed-upon order."

2. Tuned write delay on compaction. What external instrumentation/markers are they passing into hyperleveldb to tune write delay?

"HyperLevelDB removes this artificial delay, allowing the application (in our case, HyperDex) to independently decide to delay writes, using information available outside the scope of LevelDB."

3. Tuned intra-level re-writes.

"LevelDB's compaction algorithm is not efficient, and in the "fillrand" benchmark will, on average, rewrite 3MB of data in the upper level for every 1MB of data in the lower level. HyperLevelDB avoids this waste by selecting the compaction with the smallest overhead."

[rescrv]

I'm the HyperDex developer who did the work on HyperLevelDB. I'll answer your questions in order as best I can.

1. Our internal synchronization mechanism is a simple change. The stock LevelDB does the following:

    place our current on the back of wait_queue
    wait for (our thread to be head of wait_queue || thread ahead of us to do our work)
    if work done: exit
    possibly build a batch of our writes and 
    append data to the log
    insert data into the memtable
    signal the next writer, and any writer whose work we finished

HyperLevelDB does this a little differently. We made the log and the memtable concurrent datastructures, so that multiple threads can write to each one at a time. We then do a little synchronization to ensure that we don't reveal the writes to readers in the wrong order.

    get a ticket, indicating the order of our writes
    insert the data into the log
    insert the data into the memtable
    wait for writes with a lower token to complete

For the actual implementations, check out the code for LevelDB (Lines 1135-1196 of https://github.com/rescrv/HyperLevelDB/blob/28dad918f2ffb80f...) and HyperLevelDB (Line 1307-1428 of https://github.com/rescrv/HyperLevelDB/blob/master/db/db_imp...).

Effectively, this change moves from a model where there is exactly one writer at a time, to one where the bulk of the work (inserting into log/memtable) is done in parallel by writer threads.

2. LevelDB provides a GetProperty call. We can inspect the number of files in Level-0 and back-off where appropriate. There is no write delay in LevelDB itself. By the end-to-end principle, the storage server is in a better position to decide whether to delay writes, or just keep pushing them into the database.