Fast Scans on Key-Value Stores

tannal commented 6 months ago

https://vldb.org/pvldb/vol10/p1526-bocksrocker.pdf

tannal commented 3 months ago

An analysis of the design space for building key-value stores that can support both fast point lookups (get/put) and efficient scans. The main tradeoffs are between:

Update strategy (in-place, log-structured, delta-main)
Data layout (row vs column oriented)
Versioning approach
Garbage collection method

tannal commented 3 months ago

Implementation of two main variants of TellStore:

TellStore-Log: Log-structured with chained versioning
TellStore-Column: Delta-main with columnar storage and clustered versions

tannal commented 3 months ago

Experimental evaluation showing TellStore can achieve:

Nearly as good performance as specialized KV stores for get/put workloads
Orders of magnitude better performance for analytical queries compared to existing KV stores
Good performance for mixed OLTP/OLAP workloads

The key insight is that by carefully considering all the design tradeoffs in an integrated way, it's possible to build a KV store that performs well for both transactional and analytical workloads. This enables more flexible "SQL-over-NoSQL" architectures.

The evaluation shows TellStore significantly outperforms existing KV stores like Cassandra, HBase, and RocksDB on scan operations while maintaining competitive get/put performance. This demonstrates the potential for unified OLTP/OLAP storage systems.

tannal / ohmywork

Fast Scans on Key-Value Stores #62