AnyKey: A Key-Value SSD for All Workload Types

Chanyoung Park, Jungho Lee, Chun-Yi Liu, Kyungtae Kang, Mahmut Taylan Kandemir and Wonil Choi

A key-value SSD is a flash drive that stores data as key-value pairs directly, skipping the layers of host software a normal drive needs, but every existing design quietly assumes the values are much bigger than the keys — and this work from Penn State and collaborators shows that when the keys are instead large, those drives fall apart, because the drive's internal index of keys balloons and overflows its small memory; AnyKey redesigns the drive so its bookkeeping stays the same size no matter how big the keys get, so a single drive performs well across every workload rather than just the one it was tuned for.

The argument in one glance

Problem

Key-value SSDs are tuned for one workload shape

A key-value SSD stores data as key-value pairs directly on the drive, skipping the host-side indexing a normal SSD forces on a key-value store. But existing KV-SSD designs assume the values are much larger than the keys, and are optimized only for that case.
What people did

Keep an internal index over the stored keys

To answer a get, the drive keeps an internal index mapping keys to their physical flash locations in its small on-drive memory. With small keys, this index is tiny, so it fits comfortably and lookups are fast.
Why it fell short

Large keys balloon the metadata past the drive's memory

When keys are large, the per-entry metadata grows with the key size, so the index balloons past the drive's limited memory and spills to flash. The drive then pays extra flash accesses to consult and update it, and performance degrades sharply on these large-key workloads.
This paper's idea

Keep metadata a fixed size regardless of key size (AnyKey)

AnyKey is a KV-SSD design that prevents the metadata size from growing as keys grow, so the internal index stays small and fits the drive's memory whatever the key size. Across a wide range of real-life workloads with varying key and value sizes, AnyKey outperforms the state-of-the-art KV-SSD, working well for all workload types rather than just one.

Why this problem is worth solving

Key-value stores are everywhere in modern systems, and putting the key-value abstraction directly into the drive is an appealing way to make them faster.

A key-value store is one of the most common ways applications keep data: instead of files or tables, the application stores values indexed by keys and asks for a value by its key. Conventionally, a key-value store like RocksDB runs as host software on top of a block SSD, which only understands numbered blocks, so the store must maintain its own elaborate indexing — typically a log-structured merge tree — to translate keys into block locations, and beneath that the SSD runs its own flash translation layer. These stacked layers of translation add software overhead and cause write amplification, where the actual data written to flash is several times the data the application asked to store, wasting bandwidth and wearing the drive out. A key-value SSD (KV-SSD) collapses this by pushing the key-value abstraction into the drive itself: the host simply issues put and get on keys, and the drive internally maps each key to a physical flash location. This removes the host-side indexing layers and much of the redundant translation, promising lower overhead, less write amplification, and simpler software — which is why KV-SSDs are seen as a promising storage solution for large-scale key-value applications.

The difficulty is that this internal mapping has a cost that existing designs assumed away.

For the drive to answer a get, it must remember where each key’s value lives, so it keeps an internal index — metadata — mapping keys to physical flash locations. Like any storage device, a KV-SSD has only a small amount of fast on-drive memory (DRAM) to hold such an index, so keeping the metadata small enough to fit is essential; if it does not fit, the index must be stored in the flash itself, and every lookup or update then costs extra flash accesses, which are far slower. Existing KV-SSD designs handle this by assuming a specific workload shape: that values are much larger than keys. Under that assumption the per-entry metadata — which must capture enough of the key to identify it, plus a pointer — is tiny compared to the value, so the whole index stays small and the design is efficient. But real workloads are not all like that. There is a common and practically important class where keys are relatively large — think long composite keys, identifiers, or hashes. On these, the per-entry metadata grows with the key size, the index balloons past the drive’s limited memory, and the very mechanism that made KV-SSDs efficient turns into their bottleneck. A drive that is meant to serve key-value stores in general should not collapse on an entire category of them.

What people did before, and where it broke

Run a key-value store as host software on a block SSD. Maintain a log-structured merge tree in the host to map keys to blocks, on top of the SSD’s own translation. Where it broke. The stacked indexing layers add software overhead and cause write amplification, wasting bandwidth and wearing the drive.
Push the key-value abstraction into the drive (KV-SSD). Let the drive map keys to flash directly, removing host-side indexing. Where it broke. The drive must keep an internal key index in its small memory, and that metadata cost is what the design must control.
Assume values are much larger than keys. Tune the KV-SSD so its per-entry metadata is negligible relative to the value, keeping the index small. Where it broke. For large-key workloads the metadata grows with the key, so the index overflows the drive’s memory and spills to flash, adding slow accesses.
Ignore the large-key workload class. Optimize only for the small-key, large-value case that the design was built for. Where it broke. Re-evaluated on large-key workloads, existing KV-SSDs degrade sharply, so a single drive cannot serve the full range of real key-value applications.
The gap. No KV-SSD kept its metadata bounded as key sizes varied, so none performed well across all workload types. Providing that is what AnyKey does.

How AnyKey works

From key-size-dependent metadata to fixed-size metadata

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Break the dependence of metadata size on key size. AnyKey’s central design goal, per its abstract, is that the drive’s internal index should not grow just because the keys are large: the metadata per stored pair is held to a fixed size no matter the key’s length, so the whole index stays small enough to live in the drive’s limited fast memory across every workload. This directly attacks the root cause the paper identifies — that existing designs let the metadata scale with the key, which is exactly what overflows the memory and triggers the slow flash accesses. (A standard way to achieve a fixed-size index entry is to store a compact fixed-length fingerprint of each key rather than the key itself, keeping the full key beside its value in flash to resolve rare collisions; the abstract states the fixed-size-metadata property but not the specific mechanism.) Keeping a storage device’s in-memory mapping metadata compact and bounded so it fits the drive’s scarce fast memory, rather than letting it grow with the data and spill to slow flash, is the same discipline the learned flash-translation-layer work covered elsewhere on this site follows, compressing the drive’s mapping table so the index the device must consult on every access stays resident in memory instead of becoming a bottleneck.

Move the indexing into the drive, but do it robustly. AnyKey keeps the fundamental KV-SSD bet — that the drive, not the host, should map keys to flash, eliminating the redundant host-side indexing and write amplification of running a key-value store over a block device — but makes that bet pay off for the full range of workloads rather than a favorable slice of them. The value of a KV-SSD is that the storage device natively understands the application’s data model; AnyKey protects that value by ensuring the in-drive index does not become the new bottleneck. Optimizing a key-value store by co-designing it with the storage device so the device serves the data model directly is the same move the storage-device key-value work covered elsewhere on this site makes, tailoring how keys and values are laid out and looked up to the drive itself so the store runs efficiently on modern storage rather than through generic layers.

Design for the whole workload distribution, not the assumed case. The paper’s framing is that prior KV-SSDs quietly encoded an assumption — values far bigger than keys — and were efficient only where that held; AnyKey’s contribution is partly the discovery that this assumption fails for an entire real class of workloads, and partly a design that removes the assumption so one drive is good for all of them. Recognizing that a system was tuned for one workload profile and breaks on another common one, then re-architecting it to be robust across the full range, is the same lesson the fast-storage I/O-cache work covered elsewhere on this site teaches, showing that design rules calibrated for one regime can invert on a different one and that the fix is to handle the whole spectrum rather than the case the design happened to assume.

Following a request through AnyKey

Serving key-value requests with bounded metadata

A conceptual trace based on the paper's abstract and standard KV-SSD background; specific implementation details were not available.

Step 1 of 5

An application stores a key-value pair

The host issues a put with a key and a value directly to the KV-SSD, with no host-side key-to-block indexing layer in between, whatever the sizes of the key and value.

This is the KV-SSD promise: the drive understands keys natively.

Why it works

Bounded metadata fits the drive’s scarce memory. Because each index entry is a fixed size regardless of key length → the whole index stays small enough to stay resident in the drive’s limited DRAM → so it never spills to flash even under large keys.
In-memory lookups avoid slow flash accesses. Because the index remains in fast memory → gets and puts consult it without extra flash reads or writes → so the metadata path stops being the bottleneck it became for the prior design.
The root cause is the metadata, not the values. Because the paper traces the large-key slowdown specifically to the growing index → fixing the metadata size directly addresses the cause → so performance is restored where prior designs failed.
The KV-SSD benefits are preserved. Because the drive still maps keys to flash natively → the host avoids redundant indexing layers and write amplification → so AnyKey keeps the efficiency that motivated KV-SSDs while fixing their fragility.
One design covers the whole distribution. Because metadata is bounded for any key size → the same drive is efficient for both small-key and large-key workloads → so a deployment need not know its workload shape in advance to get good performance.

What it costs (trade-offs and scope)

This explainer is based on the abstract, not the full paper. The full text was not openly available at the time of writing, so the specific mechanism that keeps metadata fixed-size, the exact index structure, the collision handling, the flash layout, and the detailed measurements are not reflected here beyond what the abstract states, combined with standard background.
Fixed-size key metadata implies some indirection cost. Representing a key by a fixed-size entry rather than the full key generally means storing the full key elsewhere (with the value) and handling the rare case where two keys map to the same fixed-size representation; this is a standard, small cost, but it is a design consideration rather than free, and the abstract does not detail how AnyKey handles it.
It is a device-level design. AnyKey redesigns the KV-SSD itself, so realizing it requires the drive firmware or hardware to implement the new metadata scheme; it is not a host-side tweak that runs on any existing KV-SSD unchanged.
The gains are relative to the state-of-the-art KV-SSD. The abstract reports outperforming the prior best KV-SSD across varied workloads, but the absolute performance and how it compares to a well-tuned host key-value store on a block SSD are part of the full evaluation not available here.
Small-key workloads may see smaller gains. The problem AnyKey solves is acute for large keys; for the small-key, large-value workloads existing designs already handle well, AnyKey should match them but has less headroom to improve, so the benefit is concentrated where prior designs were weak.
KV-SSD adoption itself is a dependency. The whole approach presumes deploying key-value SSDs; organizations committed to conventional block SSDs with host key-value stores would need to adopt KV-SSD hardware to benefit, which is a broader ecosystem question the paper does not resolve.

The evaluation

Serving key-value stores: host software, prior KV-SSD, and AnyKey

Property	KV store on a block SSD	Prior KV-SSD
Where keys are indexed
Metadata size vs key size
Large-key workload performance	Overhead and write amplification
Small-key / large-value performance
Across all workload types	Consistent but with overhead	Only its assumed case

Ways to serve large-scale key-value stores, as framed by the AnyKey abstract (the full paper was not openly available, so this reflects the abstract's claims and standard background rather than the paper's detailed evaluation). Running a key-value store as host software over a block SSD stacks a host-side index (a log-structured merge tree) on the drive's own translation, adding overhead and write amplification. A key-value SSD pushes the key-to-flash mapping into the drive, removing the host indexing layers — but the drive must keep an internal index over the keys in its small memory, and existing KV-SSD designs assume values are much larger than keys, so that index stays tiny. Re-evaluated on the overlooked class of large-key workloads, those designs degrade sharply because the per-entry metadata grows with the key, the index balloons past the drive's memory and spills to flash, and every lookup and update then pays extra slow flash accesses. AnyKey redesigns the KV-SSD so the metadata size does not increase as keys grow, keeping the internal index small and resident in the drive's memory whatever the key size, which avoids the spill and the extra accesses. Across a wide range of real-life workloads with varying key and value sizes, AnyKey outperforms the state-of-the-art KV-SSD, performing well for all workload types rather than only the small-key, large-value case the prior designs were tuned for.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract, because the full text was not openly accessible when it was written, so read it as a faithful account of the abstract’s claims plus standard, well-established background on key-value stores, key-value SSDs, flash translation, and metadata management — not as a report of the paper’s detailed mechanism or measurements. With that caveat, the contribution is clean and well-motivated. Key-value SSDs are attractive because they push the application’s key-value data model into the drive, removing the stacked host-side indexing and write amplification of running a key-value store over a block device. But the paper makes a sharp observation: every existing KV-SSD design quietly assumes values are much larger than keys, and is efficient only in that regime, because the drive keeps an internal index over the keys in its small memory and that index only stays small if keys are small. There is a real, common class of workloads where keys are large, and re-evaluated there, existing KV-SSDs degrade sharply, because the metadata grows with the key, the index overflows the drive’s memory and spills to flash, and every access then pays extra slow flash lookups. AnyKey’s fix is to design the drive so the metadata size does not grow with the key, keeping the index bounded and resident whatever the key size, so a single drive is efficient across the full workload spectrum, outperforming the state-of-the-art KV-SSD on varied real-life workloads. What is not available here is exactly how AnyKey keeps the metadata fixed-size (a natural approach is fixed-length key fingerprints with full keys stored beside values, but the abstract does not specify), how collisions and updates are handled, what the index structure and flash layout are, and how the results break down by workload — the specifics needed to judge and reproduce it. The durable idea, clear even from the abstract, is that a storage device intended to serve a general data model must not bake in an assumption about that data’s shape: a KV-SSD that only works when keys are small is not really a key-value SSD for all workloads, and the way to earn that generality is to make the device’s internal cost independent of the parameter — here, key size — that the workload is free to vary.

Background

Why in-drive metadata keeps deciding storage performance

It helps to see AnyKey within a recurring theme in flash storage: the performance of a smart storage device is often decided not by how it stores the data but by how it manages the metadata that lets it find the data, because that metadata must live in the device’s scarce fast memory. Whether it is a flash translation layer mapping logical to physical blocks, a key-value index mapping keys to locations, or a deduplication table, the same tension appears — the index wants to grow with the data, but the memory to hold it does not, and once it spills to flash the device slows down. The log-structured merging work covered elsewhere on this site reflects the same concern from the key-value-store side, wrestling with how to organize and compact the structures that index a growing store so that lookups and writes stay efficient as the data scales. The common thread is that as storage devices take on more of the application’s data model — becoming key-value drives, computational storage, or deduplicating arrays — the design of their internal indexing metadata becomes the crux of their performance, and a device is only as general as its metadata is disciplined. AnyKey is a pointed instance: by refusing to let the key-value index grow with key size, it turns a drive that worked for one workload shape into one that works for all of them, and as key-value SSDs mature, keeping their internal bookkeeping bounded across the diversity of real workloads is likely to remain central to making them broadly useful.

If you remember only three things

1. A key-value SSD (KV-SSD) stores data as key-value pairs directly on the drive: the host issues put and get on keys, and the drive maps each key to a physical flash location itself. This removes the stacked host-side indexing (a log-structured merge tree in a store like RocksDB) that running a key-value store over a conventional block SSD requires, cutting software overhead and write amplification, which is why KV-SSDs are a promising storage solution. But every existing KV-SSD design is tuned for one workload shape — values much larger than keys — because the drive keeps an internal index over the keys in its small on-drive memory, and that index only stays small if the keys are small. There is a common, practically important class of workloads where the keys are relatively large; re-evaluated on those, existing KV-SSDs degrade sharply. The root cause is metadata: as keys grow, the per-entry metadata grows with them, the index balloons past the drive's limited memory and spills to flash, and every lookup and update then pays extra slow flash accesses.
2. AnyKey, per its abstract, is a KV-SSD design that prevents the size of the metadata from increasing as keys grow. By holding each index entry to a fixed size regardless of key length, the internal index stays small enough to remain resident in the drive's fast memory whatever the key size, so it never spills to flash and gets and puts avoid the extra accesses that crippled the prior design on large keys. This keeps the fundamental KV-SSD benefit — the drive natively maps keys to flash, sparing the host redundant indexing and write amplification — while removing the fragility that limited it to one workload class. (A standard way to achieve fixed-size index entries is to store a compact fingerprint of each key in memory and keep the full key beside its value in flash to resolve rare collisions; the abstract states the fixed-metadata property but not the specific mechanism.) The result is a single drive that performs well for both small-key/large-value and large-key workloads.
3. Across a wide range of real-life workloads with varying key and value sizes, AnyKey outperforms the state-of-the-art KV-SSD, delivering good performance for all workload types rather than only the case prior designs assumed. Important caveat: this explainer is based on the abstract because the full paper was not openly available, so the exact fixed-size-metadata mechanism, index structure, collision and update handling, and detailed per-workload results are not reflected here. The durable idea, clear even from the abstract, is that a storage device meant to serve a general data model must not bake in an assumption about that data's shape: a KV-SSD that only works when keys are small is not truly a key-value SSD for all workloads, and the way to earn that generality is to make the device's internal cost (its metadata) independent of the parameter the workload is free to vary — here, the key size.

Check yourself

Check your understanding

1. What is a key-value SSD (KV-SSD), and why is it attractive?
2. Why do existing KV-SSD designs degrade sharply on workloads with large keys?
3. What is AnyKey's core idea for fixing this?
4. What did AnyKey report, and what should you keep in mind about the evidence?

Sources

The paper is “AnyKey: A Key-Value SSD for All Workload Types” by Chanyoung Park, Jungho Lee, Chun-Yi Liu, Kyungtae Kang, Mahmut Taylan Kandemir, and Wonil Choi, published at ASPLOS 2025, DOI 10.1145/3669940.3707279. The authors are affiliated with institutions including the Pennsylvania State University, Hanyang University, and the Gwangju Institute of Science and Technology.

This explainer is based on the paper’s abstract. The full text was not openly accessible at the time of writing — the ACM Digital Library copy was gated, there was no arXiv or author preprint available (the co-authors’ and institutional publication pages did not expose a downloadable PDF), and the Semantic Scholar, OpenAlex, and Unpaywall records pointed only to the gated version — so this page reflects the abstract’s stated claims (that key-value SSDs are a promising storage solution for large-scale key-value applications; that existing KV-SSD designs are tuned for workloads in which values are much larger than keys; that there is another practically important workload type with relatively large keys, on which existing designs degrade significantly; that the performance problem stems from the increased size of the metadata; that AnyKey is a novel KV-SSD design that prevents the metadata size from increasing under varying key sizes; and that across a wide range of real-life workloads AnyKey outperforms the state-of-the-art KV-SSD under different workload types with varying key and value sizes) together with standard, well-established background on key-value stores, key-value SSDs, log-structured merge trees, flash translation layers, write amplification, and in-drive metadata and indexing, provided to make the abstract’s contribution understandable. The specific mechanism that keeps metadata fixed-size, the index structure and collision handling, the flash layout, and the detailed per-workload measurements are not reflected here beyond what the abstract states; the mention of fixed-length key fingerprints is offered as standard background on how a fixed-size index entry is commonly achieved, not as a description of AnyKey’s specific design, and the flow and step-through sections are conceptual readings of the abstract plus standard background rather than details drawn from the full paper. This page is marked as a draft for that reason and should be confirmed against the full paper when it becomes available.