DiStore: A Full-Memory-Disaggregation-Friendly Key-Value Store with Improved Tail Latency and Space Efficiency

Memory disaggregation decouples CPUs and memory in monolithic servers to form compute nodes (CNs) and memory nodes (MNs) for elastic and efficient memory scaling. Memory disaggregation benefits in-memory key-value stores (KVSs) that demand large memory capacity. Building a KVS with full functionality, low latency, and high space efficiency under memory disaggregation is critically required by real-world applications. However, we observe that existing disaggregated KVSs fail to achieve all the above demands simultaneously. In this paper, we present DiStore, a full-disaggregation-friendly KVS that accomplishes the above goals. We carefully divide the responsibilities of CNs and MNs when involved in index traversing, concurrency control, and memory management. We first design a two-layer indexing structure, separable adaptive linked array, to reduce network RTTs for index traversing and improve space efficiency. Then, DiStore introduces thread-context-based concurrency control to enable inter-thread collaborating to reduce stall time under multi-thread contention on CNs. Finally, we propose cachable disaggregated memory management to allow CNs to manage remote memory locally with marginal space overhead. We implement DiStore and the evaluation shows that DiStore can reduce P999 tail latency by up to 72.1% and improve space efficiency by up to 33.6%. Meanwhile, DiStore achieves comparable throughput as state-of-the-art disaggregated KVSs.