Masstree
Masstree is a concurrent in-memory ordered index that combines trie-like layers of B+ trees to handle variable-length keys.
Structure: Each layer compares an eight-byte key slice; border entries can lead to another tree for a shared prefix. The design avoids repeatedly comparing that prefix. Its shape depends on the key distribution. [1]
Concurrency: Readers validate node versions; writers lock affected nodes. The design is not wholly lock-free. A removed slot's reuse must change the insertion version, or a reader could confuse a replacement key's value with the deleted key's value. [1]
Scan boundary: The original getrange operation returns keys in order but is not atomic relative to concurrent inserts and updates. Ordered traversal is not a snapshot guarantee. [1]
Persistence: The 2012 server replies to put after buffering its log record, before forcing it to storage. Recovery chooses a common cutoff across logs and replays from an eligible checkpoint. Logging enabled therefore does not mean every acknowledged write is durable. [1]
Transaction layer: Silo adds a serializable commit protocol around a Masstree-inspired index. Its range validation tracks overlapping leaf versions, including the leaf for a failed lookup; validating only returned records would miss changes in range membership. [2]
Benchmark scope: The pinned author README distinguishes mttest, which excludes disk and networking, from mtclient against the mtd server. The server has separate log and checkpoint directories and can disable logging. Report the executable and logging mode before comparing rates. [3]
Relations
Citations
- Mao, Kohler and Morris. Cache Craftiness for Fast Multicore Key-Value Storage. EuroSys 2012; sections 3, 4.1, 4.6.5 and 5.
- Tu, Zheng, Kohler, Liskov and Madden. Speedy Transactions in Multicore In-Memory Databases. SOSP 2013; sections 1 and 4.6. DOI 10.1145/2517349.2522713.
- Author Masstree README at 11198427a1170654ca646dd20d96c8f349bca2bd: Testing and Network testing.
Sources & caveats
- Source synthesis, not a native Masstree run, crash experiment or reproduced throughput result.
- Historical server semantics, index algorithms and later integrations are separate scopes; an index name alone does not establish a deployment's durability or isolation contract.