CruiseDB: An LSM-Tree Key-Value Store with Both Better Tail Throughput and Tail Latency

Due to excellent performance, LSM-tree key-value stores have been widely used in various applications in recent years. However, LSM-tree's inherent batched data processing approach makes it suffer from poor SLA behaviors, such as a very unstable throughput and high tail latency. Unlike the I/O isolation or prioritization methods that cannot solve the SLA problem thoroughly, we have designed and implemented a new SLA-oriented LSM-tree KV store, i.e., CruiseDB, to solve both the essential and the direct SLA problems of LSM-tree KV stores by introducing an adaptive admission mechanism and improving the LSM-tree structure. According to reliable estimation of the service capacity of the LSM-tree, CruiseDB adaptively admits only an appropriate number of user requests to enter the LSM-tree memory buffer in unit time and removes the internal roadblocks of the request processing, with the advantages of preventing the write stall phenomenon, which leads to SLA declines. CruiseDB can promote the guaranteed throughput by 2.08 times on average compared with the state-of-the-art LSM-tree or B-tree KV stores.