Benchmarking Key-Value Stores

Credible storage-systems research depends on credible benchmarks. Yet the community’s standard tools — YCSB, db_bench, and their derivatives — were designed for a simpler era. They cannot distinguish empty from non-empty point queries, force every operation type onto the same key distribution, cannot generate workloads that evolve over time, and cannot model the composite-key structures and near-sorted arrival patterns that dominate real production traces [3][4]. The result is a systematic mismatch between the workloads our systems are evaluated on and the workloads they actually face in deployment — leading to poor benchmarking and, ultimately, suboptimal system optimizations.

Our benchmarking research closes this gap through a sequence of three tools, each extending the reach of the previous one: KVBench [4] expands the operation and distribution vocabulary of key-value workloads; Tectonic [3] adds the temporal, structural, and dynamic properties of production workloads at a fraction of the resource cost; and TexBench [1][2] removes the specification barrier altogether, generating benchmark workloads from natural-language descriptions and comparing multiple key-value stores against them side by side.

If our benchmarks cannot reproduce real workloads, how do we know our systems are actually fast?

The Problem: Standard Benchmarks Miss Real Workload Structure

Four limitations make state-of-the-art workload generators systematically misleading for modern storage research [3][4]:

1. No distinction between empty and non-empty queries. A point lookup on an existing key exercises the full read path — buffer scan, Bloom filter, block I/O — while a lookup on a non-existent key can short-circuit at the Bloom filter or zonemap. These have very different performance implications, yet YCSB cannot generate empty point queries at all, and db_bench emulates them crudely (by lengthening the key), so the two can never be interleaved in one workload [4].

2. Forced identical distributions across operation types. In a social-media workload, updates and searches concentrate on popular hashtags (Zipfian) while searches for non-existent tags are spread uniformly. Every state-of-the-art generator forces inserts, updates, and queries to share one distribution, masking exactly these patterns [4].

3. No dynamic workloads. Production workloads at Meta — UDB, ZippyDB, UP2X — vary over a 7-day window in composition, distribution, access pattern, and entry size; UDB writes peak daily at 17:00 PST, and some column families see up to a 10× jump in query frequency on weekends [3]. The only way to emulate this with existing tools is to generate workload segments separately and stitch them together by hand — which breaks key-sharing across phases and undermines the evaluation’s accuracy.

4. No composite keys or controlled sortedness. Production keys are frequently synthetic composites — cf-EMP:edge:alex — whose prefixes encode origin and domain, and data often arrives nearly sorted on the ingestion attribute. No standard generator can model prefix-structured keys, and none can generate data at a target sortedness while interleaving other operations [3].

Deletes compound all four: 6% of all operations processed by ZippyDB are deletes, yet YCSB does not support deletes on existing keys, and db_bench cannot interleave deletes with queries and updates [4].

KVBench: A Richer Operation and Distribution Surface

KVBench [4] is a C++ workload generator that attacks the first two limitations — and the delete problem — head-on. Its central design decision is to track the live key set during generation (a hash set for membership, a vector for random access), which is what makes the new workload classes possible:

• Empty vs. non-empty query control — the empty-query fraction is a first-class knob (-Z), and empty and non-empty point queries can be freely interleaved in one workload, each with its own distribution
• Independent distributions per operation type — inserts (via key prefixes), updates, and empty and non-empty point queries each choose from uniform, normal, beta, and Zipfian distributions with configurable parameters
• Consistency-preserving deletes — because the live key set is tracked, point and range deletes always target existing keys and can be interleaved with inserts, updates, and queries without breaking workload validity
• Selectivity-aware range operations — both range queries and range deletes take an explicit selectivity parameter, enabling benchmarks that stress secondary-delete and scan paths at controlled result sizes

KVBench ships with five benchmark workloads inspired by real applications and unsupported by prior tools — among them an 80%-empty-query workload (product searches for out-of-stock items), a fully interleaved insert/delete/query/update mix (social-media activity), a multi-distribution update/query workload (Zipfian updates on popular posts, uniform empty searches), an update + range-delete workload (inventory clearance), and an insert-heavy workload with Zipfian key prefixes (IoT timestamps skewed toward daytime) [4].

These new axes immediately expose behavior invisible to YCSB: on RocksDB, average query latency drops by more than 5× as the empty-query fraction sweeps from 0 to 100% — and two workloads with identical composition differ by 1.6× in throughput depending on whether operations are executed sequentially or interleaved [4].

Tectonic: Dynamic, Production-Like Workloads at Scale

Tectonic [3] generalizes the approach into a full benchmarking suite, implemented in Rust, that models the temporal and structural dimensions KVBench leaves open. To the best of our knowledge, Tectonic is the first key-value benchmark that supports benchmarking storage engines under dynamically shifting workloads.

A workload is a declarative JSON specification structured as Sections — isolated phases with independent keyspaces — each containing Groups of interleaved operations that share a keyspace with the phases before them. Every operation carries its own key distribution, drawn from nine supported families (uniform, normal, beta, Zipfian, exponential, log-normal, Poisson, Weibull, Pareto). On top of this, Tectonic provides:

• Dynamic workload shifts — a write-heavy burst phase followed by a read-heavy serving phase, with either shared or disjoint keyspaces, modeling the diurnal and event-driven patterns of production traces; transitions can be discrete or gradual across phases
• Composite and prefix-structured keys — keys assembled from independently distributed segments, reproducing patterns like product:<vendor_id>:<sku> and order_history:<user_id>:<timestamp>
• Hot key ranges — prefix-defined hot regions with configurable access probability, emulating the flash-sale skew of UDB-class workloads
• Tunable sortedness — ingestion at a user-specified (K, L)-sortedness [5], with string and composite keys, arbitrary distributions, and full interleaving with other operations — none of which the earlier BoDS benchmark supports

Efficiency is not incidental: workload generation is CPU-bound, and a slow generator becomes the bottleneck of the very experiment it drives. Tectonic generates the YCSB workload suite 10× faster than YCSB itself and 12× faster than KVBench, with 84% lower memory footprint than YCSB; at scale (1M–100M operations) it sustains 1.6× and 6.4× higher generation throughput than YCSB and KVBench, respectively [3]. Fidelity is preserved: a 20M-operation workload generated by Tectonic and by YCSB from the same specification produces less than 1% difference in total bytes read and written — and identical cache behavior — when executed on RocksDB [3].

TexBench: Benchmarks from Natural Language

The remaining barrier is the specification itself: composing a faithful multi-phase workload still demands expertise in the generator’s configuration language. TexBench [1][2] removes it. The user describes the workload in plain language (“generate an insert-only workload with 1M entries; add 200K point queries on the ingested keys, Zipfian with α=1; entry sizes uniform between 16B and 128B”), and an LLM-driven pipeline translates the description into a validated Tectonic JSON specification.

The key design choice is that the LLM does not write the JSON directly: it emits commands in a small DSL (e.g., set_operation_fields) that a parser and JSON mutator apply to the specification, with the schema and grammar supplied in the prompt. This bounds the model’s output to valid mutations, making the pipeline robust to hallucination. TexBench also ships preset translations of the YCSB, KVBench, db_bench, and Tectonic workload suites, so a single natural-language interface covers the community’s existing benchmarks and the full expressiveness of Tectonic beneath it [2].

TexBench is also a unified benchmarking front end. Instead of installing and learning several suites and wiring each database up by hand, users pick or describe a workload once, run it against several key-value stores in parallel — RocksDB, Cassandra, ScyllaDB, and Redis today — and compare their performance in one interface [1][2]. Constraining the model pays off measurably: with Llama 3.2, TexBench responds on average 16.7× faster than raw prompting (which took over 150 s for 39 of 50 requests) and captures the user’s intent in 61% of cases versus 4.7%; even with GPT-4o it is more accurate than raw prompting (96.3% vs. 91.3%) while sending far smaller prompts [2].

Key Results

Outlook

The through-line of this project is lowering the cost of asking realistic questions. KVBench made new workload classes expressible; Tectonic made them dynamic and cheap to generate; TexBench makes them accessible to anyone who can describe their application. The next step is closing the loop with real deployments — deriving generator specifications directly from production traces so that any observed workload can be reproduced, perturbed, and stress-tested in the lab. Benchmarking, done right, is not an afterthought of systems research; it is the instrument that keeps the rest of it honest.

Relevant Publications

1. Abhishek Chanda, Shubham Kaushik, Artem Lavrov, Subhadeep Sarkar. TexBench: A Unified Benchmarking Suite for Shifting Workloads. VLDB 2026 (Demo).
2. Shubham Kaushik, Abhishek Chanda, Subhadeep Sarkar. TexBench: Harnessing LLMs for Efficient Key-Value Benchmarking. TPCTC 2026.
3. Alexander H. Ott, Shubham Kaushik, Boao Chen, Subhadeep Sarkar. Tectonic: Bridging Synthetic and Real-World Workloads for Key-Value Benchmarking. TPCTC 2025.
4. Zichen Zhu, Arpita Saha, Manos Athanassoulis, Subhadeep Sarkar. KVBench: A Key-Value Benchmarking Suite. DBTest @ ACM SIGMOD 2024.
5. Aneesh Raman, Konstantinos Karatsenidis, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis. BoDS: A Benchmark on Data Sortedness. TPCTC 2022.