Rédiger un PREreview

The in-memory write buffer of an LSM-tree key-value store is searched on every read and written on every insert, so its cost per operation sets a floor on the whole engine. RocksDB uses a concurrent skip list, which chases pointers across independently allocated nodes and evaluates one data-dependent branch per key comparison. We present Aparajita, a MemTable representation that replaces the skip list with a list of cache-line-sized nodes, each holding fifteen 32-bit order-preserving key surrogates and a sentinel in one line, searched by a branchless SIMD kernel. Three design decisions carry the result. A relational vector compare over a sorted node yields a mask whose population count is the lower bound directly, so ordered search costs one compare, one movemask and one popcount with no branch. Surrogates are taken after the node’s shared prefix rather than from the start of the key, without which an absolute surrogate takes one value across all 200,000 keys in five of eight realistic distributions, including the keyspace this paper’s own evaluation runs on. Nodes are append-only, and the sorted order over their slots is a 64-bit word, so an insert is two stores into a free slot followed by one release store that publishes them. We implement Aparajita as a RocksDB plugin selectable by name without patching RocksDB sources, and evaluate it against the default skip list and VectorRep on a 12-core Emerald Rapids host. Point lookups over a resident MemTable are 22% to 39% faster than the skip list at 1, 4, 16 and 64 threads, non-overlapping across five runs per configuration at every point but one, backed by 55% fewer retired instructions and 40% fewer L1 misses per lookup. Ordered seeks are 15% to 29% faster, but a seek followed by ten iterator steps is 3% to 4% slower, and the representation charges 1.4 times the skip list’s arena per key. The skip list is 48% to 52% slower on insert at the representation level, and Aparajita is 18.8% faster in single-threaded db_bench, but the multi-threaded db_bench write path is bounded by RocksDB’s write group rather than by the MemTable: an insert there retires over 22,000 instructions in both representations. We report that ceiling rather than a write scaling claim the data does not support.