TeksDB:Weaving Data Structures for a High-Performance Key-Value Store

Key-value stores (KVS) are now an integral part of modern dataintensive systems.Thanks to its simplicity, scalability, and efficiency over traditional database systems. Databases such as MySQL employ KVS (in this case, RocksDB as their backend storage instead of conventional database engines because KVS is less affected by data fragmentation. OLAP and big data analytics applications often use KVS as the backend store to make use of the efficient range-query operations of LSM(Log Structured Merge Tree)-based KVS. Furthermore, the increasing use of KVS as backend stores in distributed systems diversifies the workload for each local KVS, making it necessary to design a highly-concurrent data store that simultaneously processes mixed operations. The underlying technology trends also put immense pressure on the design of KVS. Nowadays, many core servers with hundred GBs of memory are common in production environments, and this enhanced density of hardware technologies (both in terms of the number of cores and memory capacity) leads to more data items residing in memory. This phenomenon places greater emphasis on the efficiency of the in-memory data structure in KVS, as more data accesses are serviced from its memory component, which is often called the memtable. The current memtable structure of KVS, however, generally assumes a limited memory capacity that only serves as a temporary write buffer, and the use of single-Threaded writes or unscalable data structures for the memtable fails to fulfill this external demand.