KT-Store: A Key-Order and Write-Order Hybrid Key-Value Store with High Write and Range-Query Performance
Abstract
With the data volume increasing, key-value (KV) store plays an important role in today’s storage systems due to its flexible architecture and good scalability. There are two types of data organization in current KV stores: key-order layout and write-order layout, which organize records according to key order and write sequence, respectively. While the former and the latter layouts deliver high throughput for range-query and write operations respectively, neither of them can perform well for both write and range-query operations. In this paper, we propose a hybrid KV store, KT-Store, which combines the key-order and write-order layout together to improve performance. More specifically, KT-Store stores keys and value metadata into a LSM-tree, and stores values into multiple tables called TrieTables. By inserting the value among multiple TrieTables in a key-order fashion leveraging a trie, and into a specific TrieTable in a write-order fashion, KT-Store can obtain the advantages of existing two layout types and avoid their shortcomings. We implement KT-Store in RocksDB 5.7.2. Extensive evaluations demonstrate that KT-Store can simultaneously obtain encouraging write and range-query performance: compared with key-order based RocksDB, the write performance is improved by $$4.3\times -12.6\times $$ on HDDs; compared with write-order based Wisckey, KT-Store has $$54.2\times -112.6\times $$ range-query performance on HDDs. Besides, KT-Store also has encouraging performance on SSDs.
Domains
Computer Science [cs]Origin | Files produced by the author(s) |
---|
Loading...