Seastar: A Cache-Efficient and Load-Balanced Key-Value Store on Disaggregated Memory
Jingwen Du, Fang Wang, Dan Feng, Dexin Zeng, Sheng Yi · 2024
In modern datacenters, memory disaggregation un-packs monolithic servers to build independent network-connected compute and memory pools, greatly improving resource uti-lization. Existing memory-disaggregated key-value stores adopt ownership sharing or ownership partitioning for request scheduling and they all show poor performance and scalability. The former generates multiple cache misses and multiple network round trips due to poor cache locality, while the latter fails to fully use resources on all Compute Nodes (CNs) due to load imbalance. In this paper, we propose Seastar, a fast and scalable key-value store that achieves high cache locality as well as load balancing. To enable high concurrency and ensure linearizability, Seastar exploits a self-verification version chain to provide out-of-place atomic updates and ensure consistent reads. To improve cache locality, Seastar leverages a pair-based ownership assigning scheme to assign the processing permission of requests corre-sponding to each key to a CN pair through two independent hash functions. To ensure load balancing among CNs, Seastar proposes a decentralized power-of-two-choices routing scheme to route the requests to the less-loaded CNs in CN pairs for handling. Experimental results demonstrate that Seastar improves the throughput by up to 6.7x and significantly reduces the latency compared with state-of-the-art memory-disaggregated key-value stores.