1 Introduction↩︎

Modern transactional database systems increasingly rely on persistent key-value (KV) stores as their core storage engines [1]–[3]. To support advanced consistency conditions (such as snapshot isolation), these engines have a rich API that offers, in addition to basic put/get operations, high-level operations such as atomic multi-key write batches and consistent snapshot iterators. While several SSD-based stores such as RocksDB [4], PebbleDB [5], and LevelDB [6] offer this functionality, most existing NVM-based KV stores do not, making it harder for transactional databases to benefit from the performance of NVM over SSDs.

One exception to this lack of API support is , a version of RocksDB adapted for NVM. Although inherits RocksDB’s rich API, it attempts to retrofit its concurrency control and persistence mechanisms to an SSD-based design. As a result its performance suffers in comparison to clean slate NVM designs with more restricted APIs [7]–[9]. In particular, relies on a skiplist-based index to balance the need for fast updates with support for efficient range queries [10]. To the best of our knowledge, there does not exist a durable skiplist (or comparable data structure) that both enables RocksDB’s rich API and fully exploits the potential performance gains of NVM.

We propose FlintKV, an NVM-based storage engine that offers high performance and an API suited for use in modern databases. At the heart of FlintKV is a novel persistent skiplist data structure with carefully designed concurrency control and persistence mechanisms that is optimised for performance (see 3.3). To support consistent snapshots while minimising interference between long running scans and update operations, FlintKV relies on multiversioning. To facilitate atomic write batches, FlintKV employs flat-combining [11]–[13], which naturally supports batching while also reducing synchronisation overheads under high contention between update operations.

FlintKV further enhances performance through a novel four phase execution framework for update operations. A key design goal is to minimise synchronisation and persistence delays in the flat-combiner’s critical section. To achieve this, FlintKV performs index traversals for update and read operations, bulk persistence of key-value data, and pointer updates to non-leaf index nodes in a lock-free manner. Only the minimal structural modifications required for crash-consistency are handled within the combiner (e.g. to leaf-index and persistent node pointers and version numbers). The combiner itself is carefully optimised through judicious prefetching, compare-and-swap elision, and a novel persistence optimisation that allows point updates to be committed using only a single asynchronous fence on the critical path.

Our experimental evaluation using RocksDB’s db_bench benchmarking tool shows that FlintKV achieves up to a 73% increase in throughput over , and 75% over ListDB [7], a high-performance store designed specifically for NVM. Moreover, FlintKV is designed in a modular fashion and its durable skiplist can also be readily integrated into existing state-of-the-art stores to boost their performance and enrich their functionality. We demonstrate this via case studies of integrating FlintKV into as well as ListDB. Finally, we rigorously specify and prove the correctness of FlintKV, showing that it satisfies durable linearizability, the key safety guarantee for NVM.

The remainder of this paper is organised as follows: We first survey the APIs of modern SSD stores, analyse the limitations of NVM stores, and introduce our system’s memory model (2). We then present the design of FlintKV, including its interface, data layout, and key features of its concurrency control and persistence mechanisms (3). This is followed by a detailed description of its update and read operations (4). We then describe how FlintKV recovers from crashes (5) and outline our correctness argument (6). The paper finishes with evaluation results (7), related work (8) and conclusions (9).

2 Motivation and Background↩︎

We next discuss how the APIs of modern KV stores have evolved to support database storage engines (2.1), as well as the shortcomings of state-of-the-art KV stores for this important use case (2.2). Finally, we define the memory consistency model and the persistence primitives that our algorithms assume in the rest of the paper (2.3).

2.1 KV Store APIs for Modern Databases↩︎

stores (e.g., RocksDB [4], PebbleDB [5] and LevelDB [6]) are commonly used in standalone deployments but also as database storage engines embedded within database management systems. For example, TiDB explicitly delegates persistence of its storage layer (TiKV) to RocksDB on the grounds that developing a high-performance standalone storage engine requires careful and costly optimization [2], [14]. Similarly, CockroachDB [1] treats its PebbleDB storage engine as a black-box API.

To enable high-level database features such as transactions and their associated concurrency control mechanisms, storage engines typically provide an interface that goes beyond basis point operations such as , and . For example, as shown in Table 1, RocksDB, PebbleDB and LevelDB provide a consistent snapshot iterator () mechanism that allows higher-level database layers to operate over a point-in-time view of the data without blocking concurrent writes [4]–[6]. This can be used as a foundational building block when implementing transaction isolation levels such as snapshot isolation (SI) [15].

In addition, the above storage engines support atomic multi-key write batch operations (), which allow multiple updates to be applied atomically. This capability is also important for database transactions: CockroachDB and TiDB use to coordinate distributed transactions, ensuring that related updates across multiple keys at a server either all commit or all abort atomically [16].

2.2 Hybrid -DRAM KV Stores↩︎

Non-volatile memory () is a byte-addressable persistent storage technology that offers write granularity on the order of hundreds of bytes (e.g., 256 B rather than 4 KB), providing significantly lower latency than SSDs or HDDs. In recent years, a growing body of research [7]–[10], [17]–[32] has explored how to design stores that leverage to achieve high performance. Since is still slower than DRAM, recent research has shifted towards hybrid designs that keep some indexing information in DRAM for performance but can also leverage for both indexing and data.

A popular hybrid approach is to use a multi-stage/tier indexing strategy, e.g., based on log-structured merge-trees (LSM trees) [7], [10]. The standard LSM architecture involves two tiers, a staging tier and a . The staging tier consists of an log for fast data persistence and a DRAM resident index (or memtable) that may also hold a copy of the data in the log. The stores recently ingested data efficiently, while the stores the remaining data set in a more compact format, for example as sorted string tables (SSTables) on . Background processes periodically migrate data from the staging tier into the .

However, while many hybrid DRAM-KV stores support basic operations (//), only one (PMemRocksDB [10]) supports both and operations (see 2). This means that (apart from PMemRocksDB) these systems cannot serve as drop-in replacements for the storage engines of databases such as CockroachDB and TiDB [1], [33], [34].

Designing an NVM store that correctly supports both and while maintaining good performance is fundamentally challenging. Both operations demand careful coordination as concurrent readers must never observe a partially executed batch, while snapshot iterators must observe a consistent point-in-time view. adds a further layer of difficulty: crash safety requires that correctness invariants are preserved across failures, which recent research has shown is difficult to get right due to ’s complex low-level interface [35], [36]. Indeed, in our own work on integrating FlintKV into a ListDB-based system we identified two critical correctness bugs in the original ListDB implementation (see 7.2 and Appendix 10).

implements the full RocksDB API by reusing RocksDB’s coordination protocol, including a crash-consistency design that serializes logging and the corresponding DRAM index updates. This design provides correctness and a familiar API, but it limits concurrency in the : operations are grouped into a write group, the group leader persists the group’s data to the log, and each worker then inserts its data into the memtable. The write group leader then waits for every worker in the write group to complete their insertions into the memtable before allowing any of the threads to return, which limits parallelism. In a full deployment, this overhead is largely masked: the is notorious for write stalls under high write contention [37], making it the primary bottleneck. State-of-the-art stores, however, have largely eliminated write stalls in the , which shifts attention to the as the new performance-critical component.

2.3 System Model↩︎

We assume a memory model with a FIFO store buffer (e.g., as in PTSO [38]) that supports instructions ‘CLWB \(x\)’, ‘SFENCE’ and ‘MFENCE’, where

Note that the SFENCE instruction may be stored in the writing thread’s store buffer, and only takes effect when the SFENCE is debuffered (i.e., takes effect in main memory) [39]. In contrast, MFENCE has a stronger semantics that blocks the executing thread until all cached instructions (including writes and CLWBs) executed by the thread have taken effect in memory.

CLWB and SFENCE together are strong enough to support a common message-passing style synchronisation pattern [38] demonstrated by the example in 1. Variables \(x\), \(y\) and \(z\) are initialised to \(0\). The left thread updates \(x\) to \(1\), tags this write using CLWB \(x\) and fences the CLWB operation using SFENCE before updating \(y\) to \(1\).

The right thread reads \(y\), and if it sees the updated value of \(y\) updates \(z\) to \(1\). This means that the program satisfies the persistent invariant PInv, i.e., if the value of \(z\) in is \(1\), then the value of \(x\) in is also \(1\) (but \(y\) in may be \(0\) or \(1\)).

Importantly, visibility of \(y = 1\) by the right thread indicates that the \(y \gets 1\) has been debuffered in the left thread. Since the store buffers are FIFO ordered this means that the previously executed SFENCE must have also been debuffered, which by the memory model semantics means that the write \(x \gets 1\) tagged by CLWB \(x\) must have been persisted. Note that to get the same guarantee when the code in both columns is executed by the same thread, we must replace SFENCE with MFENCE.

None

Finally, for convenience we also define more general operations (ptr, size) and (ptr, size). aligns the address range to cacheline boundaries and flushes all cache lines that cover the interval [ptr, + size] to NVM using the platform’s persistence primitives. On our platform, this is implemented using one or more CLWB instructions. flushes the required range using and then executes an SFENCE instruction to ensure ordering.

3 FlintKV Design↩︎

We present FlintKV, a flexible NVM key-value storage engine that provides a rich API suitable for use in modern databases. To achieve high performance, FlintKV relies on a hybrid NVM-DRAM skiplist index. The core contributions of FlintKV centre on the durable skiplist’s carefully co-designed concurrency control and persistence mechanisms.

We next define FlintKV’s interface and correctness guarantees (3.1), overview its core data structures (3.2), and outline the key design principles underlying its concurrency control mechanisms (3.3).

3.1 Interface Specification↩︎

FlintKV provides an API consisting of the following set of operations:

FlintKV is designed to implement durable linearizability [40], a standard correctness condition for persistent-memory data structures. Durable linearizability strengthens linearizability [41] by additionally requiring crash safety. Durable linearizability assumes that threads executing before a crash are not resumed and requires that any history of operation invocations, responses and system crashes must be linearizable when the crashes are removed from the history. This means that any operation that has linearized must also be persisted. Since operations must linearize before they return, every completed operation must also be persistent.

3.2 Core Data Structures↩︎

At a high-level, FlintKV consists of a concurrent durable skiplist, as illustrated in 2. Its state can be divided into two layers, a volatile layer stored in DRAM containing the skiplist index and a persistent layer stored in NVM containing the user’s key-value data.

The volatile (DRAM) layer stores internal index nodes of the skiplist to avoid costly NVM accesses for index traversals and modifications. Each volatile index node (IndexNode) contains the user’s key, and per-level successor index pointers. Each index node also contains a pointer to a corresponding persistent node in the persistent layer.

The persistent (NVM) layer is responsible for storing inserted or updated key-value pair nodes durably such that they can be recovered after a crash. In isolation it constitutes a persistent linked list. Each persistent node (NVMNode) contains a user key–value pair and a pointer to its successor persistent node.

3.3 Concurrency Control↩︎

FlintKV achieves high performance through careful co-design of its concurrency control and persistence mechanisms. FlintKV’s concurrency control combines multi-versioning with a four-phase execution flow (locate, prepare, attach and promote) for update operations (, and ), as illustrated in 3 and described in detail in the next section (4). We next overview the core design principles underlying these mechanisms.

To ensure durable linearizability while minimizing contention, for example between concurrent write operations and long-running scans, FlintKV’s durable skiplist is multi-versioned, as shown in 2. Each index node includes a version number, which is mirrored in the corresponding persistent node. Version numbers are globally unique, with the exception of atomic operations (see 4.2), and incremented for every update. The volatile global variable visible_version tracks the highest version number used by any update operation. After a crash, FlintKV reconstructs the pre-crash value of visibile_version based on the version numbers of persistent nodes (see 5).

FlintKV executes index traversals in a lock-free manner to minimise synchronisation delays when persisting subsequent index modifications. This includes traversals for update operations and read-only operations ( ). For updates an initial lock-free locate phase searches optimistically for an appropriate insertion point for the updated node. Similarly, a final lock-free promote phase lazily updates non-leaf level index node pointers in parallel after index modifications are persisted.

Given the performance disparity between NVM and DRAM, FlintKV parallelises bulk persistence operations (e.g. of a new NVMNode’s key and value), which are decoupled from persistence of structural modifications (to pointers and version numbers). Workers perform bulk persistence operations after the locate phase as part of a lock-free prepare phase that allocates, initialises and persists new NVMNodes, but defers linking to them from existing nodes in the persistence layer.

FlintKV updates pointers to prepared NVMNodes in the persistent layer and the leaf level of the corresponding IndexNode atomically for crash consistency. To reduce synchronisation overheads under high contention, FlintKV introduces an attach phase that batches these updates using a flat-combining protocol [11]. Workers compete for an exclusive combiner lock to modify the base layers. The successful combiner thread collects and applies updates on behalf of itself and the other workers. Due to multi-versioning and the exclusive lock, no further synchronisation is needed within the combiner (CAS instructions on pointer updates). To boost concurrency, the combiner employs an early release policy where a waiting worker thread returns as soon as its prepared node(s) are attached.

FlintKV introduces several optimisations to reduce persistence delays during the flat-combining critical section. Since bulk persistence is handled during the lock-free prepare phase, the combiner need only persist a minimal amount of critical state (one node pointer and version number for a operation). This minimal state is prefetched into cache at the end of the prepare phase, which avoids incurring the substantial NVM fetch latency on a cache miss during the attach phase. The combiner’s persistence operations are also carefully co-designed with FlintKV’s crash recovery algorithm to require only a single SFENCE for operations (4.1), in contrast to a naive approach requiring separate fences for pointer and version number persistence.

4 Update and Read Operations↩︎

We next describe in detail how the design principles outlined in the previous section are realised in the implementation of FlintKV’s update and read operations. We focus first on the description of the operation (4.1), and then briefly outline how it is adjusted to support atomic  (4.2). operations insert a tombstone version using the algorithm, so we omit a separate description here. Finally, we describe briefly FlintKV’s read-only operations ( and ).

4.1 Operation↩︎

A operation begins by executing locate, which conducts a standard lock-free traversal over the index to collect the predecessor and successor nodes at each level ([algo:add95outer95shell], line [code:search]). This search is guaranteed to terminate because the skiplist uses sentinel head and tail nodes.

The locate phase executes optimistically, since the attach phase may later discover that the cached neighbours are stale (e.g., a concurrent insertion has already placed a node at the target location). Therefore, the worker enters a retry loop that repeatedly executes locate and prepare followed by attach until the operation succeeds (lines 4-[code:retry95loop95exit]).

On entering the prepare phase for the first time, (as indicated by a NULL index node parameter), the worker thread allocates the persistent node and assigns the key and value (line [code:pmem95node95create95and95persist]). It subsequently sets the version number to a temporary initial value of . The final version is assigned later as part our optimised crash recovery algorithm. The worker then flushes the entire memory range occupied by the p_node to persistent memory (line [code:p95node95flush95only]), but does not execute SFENCE at this point. The worker then creates the index node and links it to the p_node (line [code:index95node95create95and95link]). These allocation and persistence steps are performed once per operation and are not repeated on subsequent retries because they do not depend on the target location in the skiplist.

The next part of is executed on each invocation. The worker configures the index node’s successor pointers and the persistent node’s successor pointer to point to the cached neighbours collected during locate (lines [code:index95node95config95start]-[code:pmem95config95start]). The worker then calls , which flushes the cache line containing the persistent node’s successor pointer to persistent memory and executes an SFENCE to ensure correct ordering (line [code:persist95dirty95lines]). To improve performance, it then prefetches the persistent node into the CPU cache to reduce NVM fetch latency for the combiner thread that will execute attach(line [code:prefetch95pmem95node]). Finally, it returns the prepared index node to the caller.

Once the nodes are prepared, the worker gets ready for the attach phase. It first creates a flat-combining advertisement with the information the combiner thread will need (line [code:arg95package]). Advertisements includes the prepared nodes, their neighbours, and a status field set to Ready indicating the request is ready for a combiner thread to process. The worker inserts the advertisement into its own dedicated slot in a global advertisements array, and then enters the attach phase (lines [code:arg95package]-[code:pass95to95flat95combining]). Inside attach, the worker spins in a short wait loop: it either observes that a combiner has processed its advertisement (line [code:combiner95finished95check]), or it succeeds in acquiring the flat-combining lock and becomes the combiner.

The combiner scans the advertisements array and processes each advertisement in the Ready state (lines [code:fc95loop95start]–[code:fc95loop95end]). In rare cases, a thread may acquire the combiner lock before observing that its advertisement has been processed by another combiner. In this case the thread will process any Ready advertisements on behalf of other threads, but will skip processing its own to avoid duplicate execution.

Combiner processing of an advertisement is described in Algorithm [lab:insert95critical]. The combiner first checks if the cached predecessors and successor are still valid (line 5). Performing this check under the exclusive combiner lock avoids any need for compare-and-swap instructions when updating the index later in the attach phase, as would be required in a regular lock-free skiplist implementation. If the cached data is invalid the combiner sets the advertisement’s status to Failed and returns.

If the cached data is valid, the combiner assigns a version number greater than the globally visible version number to the index node and NVM node (Algorithm [lab:insert95critical], lines [code:index95seq95assignment]-[code:pmem95seq95assignment]) and flushes the p_node’s version number (line [code:pmem95flush95seq95id]). The combiner then links the index node to its predecessor and the durable node to its predecessor (lines [code:index95node95insert]-[code:pmem95node95insert]). This makes them visible to threads that are executing locate, but not yet to threads that are executing read-only operations.

The successor pointer of the NVM node’s predecessor is then persisted using (line [code:pmem95flush95pred95next]). At this point the persistent memory node is durably linked to the linked list in persistent memory, and the index node is inserted into the volatile index. Note that in addition to the SFENCE executed within , a naive solution would perform an additional SFENCE after the earlier (line [code:pmem95flush95seq95id]) to ensure the correct node version number is persisted before the node is durably linked. However, our recovery algorithm allows us to ensure correctness using only a single SFENCE (see 5), substantially improving the combiner’s performance.

The globally visible version number is now safely incremented and the new node becomes visible to read-only operations (line [code:increment95seq95id]). Finally, the combiner sets the advertisement’s status to Success and returns. After releasing its lock, the combiner executes an MFENCE to ensure its own operation has been flushed to NVM (Algorithm [algo:add95outer95shell], line [code:mfence]).

While the combiner continues processing any remaining ready entries in the advertisements array, a waiting worker that observes its advertisement’s status is Success immediately proceeds from the attach phase to the promote phase ([algo:add95outer95shell], line [code:promote]) (or conversely returns to the prepare phase if it is Failed).

During promote(not shown), the worker updates higher levels of the volatile index concurrently with other threads using a lock-free skiplist algorithm. The promotion inserts the new index node into levels in ascending order, which preserves the invariant that if the node exists in level i then it also exists in every level below i.

4.2 Operation↩︎

The operation atomically and durably applies a collection of and operations  using the same four-phase execution framework as . We next outline the key differences.

In contrast to , takes a vector of key-value pairs as an argument (Algorithm [lab:insert95batch95outer95shell], line 6). Worker threads therefore execute locate and prepare for each individual pair, collecting the resulting prepared nodes into the set batchAdvs (lines [code:batch95advs95start]-[code:batch95advs95end]). Unlike , the worker thread never retries locate and prepare for operations in a . This avoids having to retry an entire batch for a single failed operation. Instead, the combiner retries failed operations (at most once) during the attach phase.

The worker thread nexts creates a flat-combining advertisement prior to entering the attach phase (line [code:batch95adv]). A minor variation here from is that a advertisement contains a collection batchAdvs of prepared nodes, one for each operation, as well as a status field for the whole batch.

The overall attach phase flat-combining flow is the same as for , except that for advertisements the combiner executes instead of  (Algorithm [algo:add95outer95shell], line [code:call95process95put]).

Within , the key challenge for the combiner is to ensure crash-consistency for the batch as a whole (Algorithm [algo:process95wb]). For this it relies on two persistent variables: to record the version of the most recent completed operation before the start of the batch, and a flag to record whether the combiner was processing a batch when a crash occured. Before processing batch operations, the combiner first updates with the value of and persists it (lines 7-[code:flush95commit95seq95id]). It then sets and persists the flag to switch to batch mode (lines [code:set95use95commit95entry]-[code:flush95use95commit95entry]). If upon recovery the system observes that the flag is set, it will roll back any nodes with a version higher than . Conversely, if the flag is not set, it will recover all commited nodes.

For each prepared node in the batch, the combiner invokes to insert the node into the data structure (lines [code:writrbatch95retry95start]-[code:wb95end95for]). All nodes in the batch are assigned the same version number in because the is not incremented for batch operations (Algorithm [lab:insert95critical], line [code:skip95seq95id95increment]). Similarly to the operation, a retry may be required if the cached neighbours of the prepared node have become stale. However, in the case of the retry is executed within attach to ensure that all operations in the batch have completed. There can be at most one retry per entry, since executes under the exclusive combiner lock.

Once all operations have executed, the combiner switches back to non-batch mode (line [code:commit95batch]). At this point the batch is considered committed and the combiner increments
[1]to make the batch’s nodes visible atomically to readers (line [code:batch95seq95id95assignment]).

Finally, after the worker observes the batch advertisement’s status is Success, it executes the promote phase for each operation in the batch (Algorithm [lab:insert95batch95outer95shell], lines [code:wb95promote95for]-[code:wb95promote95endfor]).

4.3 and Operations↩︎

operations follow a standard lock-free skiplist traversal algorithm, with one addition: they ignore nodes that are not yet visible to the calling thread. This visibility control is achieved by comparing each encountered node’s version against the caller’s active view based on the value of visible_version.

The operation begins by caching the current visible version on (Algorithm [algo:get95operation], line 8). It then traverses from the head node down the levels of the skiplist to locate the target position of (lines [code:get95op95traverse]-[code:end95get95op95traverse]). During this traversal, the inner loop advances along the current level as long as the version-aware key comparator determines that the node’s key is strictly less than the target key given the cached visible version (vv) (lines [code:get95op95compare]-[code:end95get95op95compare]).

When the lock-free traversal finishes, the algorithm evaluates whether the target key was found. First, if the successor node’s key matches the target key (line [code:check95match]), it returns the associated value. Otherwise it returns NULL.

The operation proceeds as follows. The thread first caches the visible_version and then traverses the skip list until it finds the first node whose key is greater than or equal to the snapshot’s start key and whose version is less than or equal to the cached visible_version, or until it reaches the tail, in which case it returns NULL. If the specified range is present in the skip list, the operation returns an iterator object to the caller, which allows traversal of the skip list from that point onward. Each call to the iterator’s next() method returns the node currently pointed to by the iterator and advances the iterator to the next valid node. A node is considered valid if its key is greater than the current node’s key and its version is less than or equal to the cached visible_version. If no such node exists, the iterator will set the return value for the next invocation to NULL.

5 Recovery Procedure↩︎

In the event of a crash, the DRAM index and visible version number are lost, while a durable sorted linked list remains on persistent memory. Two scenarios are possible during recovery:

The list can then be traversed and used to re-initialise the visible version number and to rebuild the in-memory index according to the surrounding system implementation. For example, this may involve reconstructing a memtable in or inserting nodes into the L0 skiplist in the ListDB implementation.

From a performance perspective, the key difference between recovery in FlintKV and other implementations is that the persistent list is already sorted. This property enables faster reconstruction of the skiplist index during recovery, as we demonstrate in our experimental evaluation (7.4).

6 Correctness of FlintKV↩︎

In this section, we give a brief overview of the proof that FlintKV satisfies durable linearizability. A complete proof can be found in Appendix 11.

We represent key/value pairs stored in FlintKV as a collection of read/write variables, and model the update operations (, , and ) as atomic writes of values to one or more keys, and the read operations ( and ) as atomic reads from one or more keys.

Our proof strategy follows the dependency graph approach of [42], which asserts that a history \(\sigma\) of operations is linearizable provided a directed graph induced by the union of four relations – \(\mathsf{wr}\), \(\mathsf{ww}\), \(\mathsf{rw}\), and \(\mathsf{rt}\) – is acyclic (Theorem 2). Informally, \(\mathsf{wr}\) (reads-from) identifies pairs \(r\) and \(w\) of read and write operations such that \(r\) returns the values written by \(w\), \(\mathsf{ww}\) (write-write) establishes a total order over all write operations in \(\sigma\), and \(\mathsf{rt}\) represents the real-time invocation order between pairs of operations in \(\sigma\). The relation \(\mathsf{rw}\) (from-read) is derived from \(\mathsf{wr}\) and \(\mathsf{ww}\) (Definition 1).

To accommodate the operations that may remain incomplete due to crashes, we introduce a visibility predicate [43] such that a read operation \(r\) is visible iff the thread that invoked \(r\) does not crash before \(r\) returns; and a write operation \(w\) is visible iff the thread that invoked \(w\) does not crash before the assignment in line [code:pmem95node95insert] (if \(w =\) ) or line [code:commit95batch] (if \(w =\) ) reaches persistence. We then restrict the four relations above to hold only for visible operations (Definition 1), and revise the linearizability criterion as in [43] to assert durable linearizability (Theorem 2).

In the remainder of the proof, we show how the witnesses for the relations \(\mathsf{wr}\) and \(\mathsf{ww}\) can be constructed for a given history of FlintKV (Definition 2), and prove that the resulting dependency graph is acyclic (3). The durable linearizability of FlintKV then follows from Theorem 2.

7 Evaluation↩︎

In this section, we evaluate FlintKV’s performance to show the benefits of its concurrency control and persistence mechanisms. Our evaluation goals are threefold. First, we investigate the throughput and latency of FlintKV’s durable skiplist index in isolation to understand its behaviour in a standalone deployment (Section 7.2). We then integrate FlintKV with the capacity tiers of existing key-value stores and evaluate its ability to boost their end-to-end performance (Section 7.3). Finally, we evaluate the time taken by FlintKV for crash recovery (Section 7.4).

7.1 Experimental Setup↩︎

We conduct all experiments on a dual-socket server equipped with two Intel Xeon Gold 6326 processors (16 cores per socket, 2 hardware threads per core, 2.90 GHz base/3.50 GHz boost) and 128 GB of DRAM. Persistent memory is provided by a 496 GiB Intel Optane PMEM module mounted in fsdax mode on the first NUMA node. All benchmarks are pinned to a single NUMA node (numactl --cpunodebind=1 --membind=1) to eliminate cross-socket effects. The system runs Ubuntu 22.04 with Linux kernel 6.8.0, and all implementations are compiled with GCC 11.4 at (-O3 -mavx2 -msse4.2 -mclflushopt -mclwb). Our evaluation uses the standard benchmarks provided by the RocksDB db_bench tool. Unless otherwise specified, all experiments are conducted using the fillrandom workload.

7.2 Durable Skiplist Performance↩︎

We begin by evaluating the performance of FlintKV’s durable skiplist in isolation (without a capacity tier). As well as preventing interference from background operations that propagate data to the capacity tier, this allows us to ensure that all evaluated implementations use the same memory allocators, node structures, key comparators, node height generators, fanout factors, and other parameters that affect performance.

To put FlintKV’s performance in perspective, we compare against the staging tiers of two representative state-of-the-art systems: [10] and ListDB [7]. Before presenting our results, we first briefly describe the experimental configuration for each baseline system, and in particular how we address a critical correctness bug that we discovered in ListDB.

Our comparison with ’s staging tier uses the following configuration: we enable the concurrent memtable writes and pipelined write options. These options allow to parallelise WAL and memtable updates across successive write batches, significantly improving its performance. We also configure to use key-value separation, storing payload values in persistent memory in the same manner as the ListDB and FlintKV staging-tier implementations evaluated in this work.

During our initial investigations into ListDB’s staging tier, we discovered two bugs that can cause it to violate the durable linearizability correctness condition. The essence of the first bug is the chain of records in ListDB’s WAL may be persisted out-of-order, such that an entry after an invalid record can become visible to clients but is lost during recovery (see Appendix 10 for details). The second bug arises from a missing flush operation.

To address the first issue, we designed a fix to ListDB’s algorithm that preserves its lock-free properties and ensures that the WAL chain can skip over invalid records, thereby ensuring durable linearizability. For the second issue we add the required flush. We call this fixed version ListDB(sync) and it is the version that we use in our benchmark evaluation.

Figures 9, [fig:bench95throughput952], and [fig:bench95throughput953] show the insertion throughput into the WAL–memtable stack across varied thread counts for , , and operations, respectively, under a fixed payload size of . FlintKV consistently outperforms , which implements the same extended API, by 15%-25% across the entire range of thread counts. Moreover, the performance gap widens as the number of threads increases. Additionally, FlintKV begins to outperform ListDB(sync) at around 10 threads, achieving a throughput improvement of 4% to 68%, with the performance gap continuing to widen as the thread count increases.

In a separate set of experiments, shown in Figures 11 and [fig:bench3952], we vary the payload size while executing operations using 16 and 32 threads. FlintKV significantly outperforms the other systems for small payloads, but the gap narrows as payload size increases. By 2048 bytes, performance largely converges, as persistent-memory bandwidth becomes the dominant limiting factor for all 3 systems. At 32 threads, FlintKV outperforms by 18%–29% and ListDB by 12%–69%, and at 16 threads by 15%–8% and 50%–9% respectively.

Finally, we evaluate the performance of operations for FlintKV and , as shown in Figure [fig:bench95write95batch]. FlintKV consistently outperforms by 10%-15% across the entire range of batch sizes. Similar to single-update operations, FlintKV achieves this performance advantage by parallelising the locate, prepare, and promote phases.

Figures 10 and [fig:bench95295p99] show the median (P50) and 99th-percentile (P99) latencies, respectively, while Figure [fig:bench295tail] shows the tail amplification (P99/P50) for the same experiments. For this set of experiments we run operations with the payload size of , which corresponds to the same configuration as in Figure 9. As with the experiment in Figure 9, FlintKV has lower latency than across the entire range of thread counts, with the performance advantage widening as the number of threads increases. The ListDB(sync) implementation exhibits lower latency than FlintKV at low thread counts, but its latency increases sharply as the number of threads grows, eventually surpassing FlintKV at around 10 threads. This is consistent with the throughput results, where FlintKV begins to outperform ListDB(sync) at similar thread counts.

7.3 End-to-End Performance↩︎

To understand the impact of FlintKV on end-to-end performance and the engineering effort required to integrate its durable skiplist into existing systems, we next evaluate FlintKV in conjunction with the capacity tiers of ListDB and .

In its original form, ListDB only supports and operations. Supporting the full API of FlintKV requires us to address the lack of support for range scans: because ListDB’s data is sharded using a hash-based partitioning scheme, a global range scan would in practice require scanning all shards, which is highly inefficient. However, extending ListDB to support range scans within a single shard is straightforward. We therefore configure ListDB to use a single shard and implement a straightforward range scan API that iterates over both the durable staging tier and capacity tier, returning all keys within the specified bounds.

We use this range-scan-enabled configuration as our baseline ListDB implementation for the integration study. For the integrated FlintKV+ListDB system, we replace ListDB’s original staging tier with FlintKV, while keeping the rest of the shardless ListDB baseline unchanged. As a result, the integrated system supports the extended API, which includes and .

Unlike ListDB, already supports FlintKV’s extended API (including and ), so integrating with it does not require modifying the system’s core codebase. Instead, we simply replace the existing durable staging tier with FlintKV, leaving the remainder of untouched.

Figures [fig:veliris95with95list95db95end95to95end] and 14 show the end-to-end throughput of FlintKV+ListDB and FlintKV+, respectively, in comparison to their original versions. For ListDB, performance exhibits a trend similar to that in 7.2, with FlintKV outperforming ListDB(sync) at higher thread counts by by 8%–75%. We attribute the performance drop when scaling from 6 to 8 threads for both systems to ListDB’s memtable rotation mechanism. This relies on reference counting to determine when the active memtable can be safely made immutable. Combined with the synchronisation overhead for allocating DRAM and NVM space for new memtable entries, this temporarily degrades performance.

With respect to (Figure 14), FlintKV’s end-to-end throughput also demonstrates performance improvment of 49%–73% across the evaluated configurations.

7.4 Recovery Performance↩︎

Finally, we evaluate the recovery time of FlintKV in comparison to and ListDB. The WAL-to-memtable recovery procedures in and ListDB(sync) are largely the same: a recovery thread scans the WAL and reinserts the recovered entries into the skiplist. Because WAL records are appended in arrival order, the log is not sorted by key. This produces mostly sequential accesses to persistent memory during the scan, but forces recovery to perform skiplist insertions in a random order, which is typically more expensive than inserting keys that are already sorted.

FlintKV takes a different approach. Entries are still appended to the WAL in insertion order, but the log additionally maintains links that allow the entries to be traversed in logical key order. This enables recovery to insert entries into the skiplist in (approximately) sorted order, reducing skiplist insertion cost; however, following these links introduces more random accesses to persistent memory.

The goal of this experiment is to determine which trade-off is more efficient in practice. We evaluate two recovery sizes: a small workload of approximately 30 MB and a large workload of approximately 300 MB. For the small dataset, FlintKV recovers nearly 171.5% faster; for the large dataset, the advantage narrows to 20% in favor of FlintKV.

8 Related Work↩︎

ListDB [7] and  [10] are hybrid KV stores that support multi-versioning, and are therefore a good match for integration with FlintKV. In contrast, the previously discussed systems in 2.2—BonsaiKV [8], FluidKV [9], and Viper [21]—do not provide multi-versioning support. Instead, they update entries in place, retaining only the most recent version of each key-value pair in the system.

A large body of work has explored the design of indexes, including B+ trees [17], [22]–[24], [29], [44] and hash-based indexes [31]. In this work, we focus on skip lists because they are the de facto in-memory index for LSM-tree memtables. Memtables are transient data structures that grow from empty to a fixed size before being flushed to persistent storage and discarded. For this workload, skip lists provide efficient ordered access while avoiding the structural maintenance (e.g., rebalancing or node splitting) required by many tree-based indexes, making them a natural choice for write-intensive, short-lived in-memory data structures.

A number of prior works [45]–[48] have explored the design of skip lists. However, these efforts primarily focus on optimizing individual operations and do not support atomic write batches or snapshots. NVTraverse [49] transforms lock-free data structures for persistent memory and introduces the concept of a traversal phase, which inspired the design of FlintKV. However, like the other prior works discussed above, NVTraverse does not support atomic write batches or snapshots.

Recent work on lock-free data structures includes Jiffy [50], which integrates atomic batch updates and snapshot semantics into a lock-free skiplist, and VERLIB [51], which enables snapshot-consistent traversal of concurrent data structures via versioned pointers and per-pointer CAS-based updates. Both systems demonstrate high performance in volatile-memory settings, but neither addresses crash consistency or persistence semantics required for non-volatile memory systems.

A body of work has explored flat-combining data structures for both volatile memory and . These efforts have primarily focused on data structures with little or no traversal, such as stacks, queues, and priority queues [11], [12], [52], [53]. In contrast, the application of flat-combining to traversal-intensive data structures, such as linked lists, skip lists, and trees, remains largely unexplored.

A possible reason is that flat-combining, in its original form, is less well suited to traversal-intensive data structures. In a naive implementation of a linked list or skiplist based on flat-combining, the combiner thread both traverses the data structure and executes all pending operations. As the data structure grows, this centralized traversal becomes an increasingly significant bottleneck, severely limiting throughput and scalability. In contrast, FlintKV adopts a phase-based approach that allows multiple threads to do most of the work associated with traversing and preparing operations concurrently, leaving only the minimal coordination necessary to complete the operations.

9 Conclusions↩︎

In this work, we present FlintKV, an NVM-optimized storage engine designed to bridge the gap between state-of-the-art key-value stores and the API requirements of contemporary database management systems. FlintKV natively supports atomic multi-key writes and consistent snapshot iteration while also guaranteeing durable linearizability. At the heart of FlintKV is a novel concurrent durable skiplist index whose concurrency control and persistence mechanisms are carefully co-designed to maximize performance, allowing FlintKV to outperform prior work by up to 75% in end-to-end throughput.

10 ListDB Crash-Consistency Bug↩︎

In summary, to add an entry to the durable staging tier, ListDB first reserves space in the WAL using a bump-pointer allocation. It then writes the entry and the offset of the next entry in the WAL and persists it. Finally, it marks entry as valid, which means that the entry will be restored during recovery. This, effectively, forms a linked chain. During recovery, the algorithm traverses this chain and checks whether each entry is valid; once it encounters an invalid entry, it stops.

We observe that this behaviour can violate durable linearizability because an acknowledged write operation is not guaranteed to be visible after a crash.

In particular, recovery relies on the following invariants:

The following execution violates these invariants.

After such an execution, the entry written by Thread 2 may not be reachable during recovery, because Thread 1 has not yet created the link that allows the recovery procedure to reach subsequent entries. As a result, operations that returned successfully before the crash can be lost, violating durable linearizability. To address this issue, we designed a fix to their algorithm that preserves its lock-free property and ensures that the WAL chain can skip over invalid records, thereby enforcing the adherence to durable linearizability. We call this fixed version of ListDB ListDB(sync) and it is the verison that we use in our benchmark evaluation.

11 Durable Linearizability Proof↩︎

To each (possibly infinite) execution \(\sigma\) of the algorithm, we associate:

• a set \(V(\sigma)\) consisting of all the operations in \(\sigma\). and are \(\mathsf{read}\)s, and and are \(\mathsf{write}\)s; and

• a relation \(\mathsf{rt}(\sigma) \subseteq V(\sigma)\times V(\sigma)\), defined as follows: for all \(o_1,o_2\in V(\sigma)\), \((o_1,o_2)\in\mathsf{rt}(\sigma)\) if and only if \(o_1\) completes before \(o_2\) is invoked.

We denote the \(\mathsf{read}\) operations in \(\sigma\) by \(\mathsf{Reads}(\sigma)\) and the \(\mathsf{write}\) operations in \(\sigma\) by \(\mathsf{Writes}(\sigma)\). A \(\mathsf{read}\) operation \(r\) is defined as \(\{(k_1, v_1), (k_2, v_2), \ldots\}\) such that \(i \neq j \Rightarrow k_i \neq k_j\), where \(r\) returns values \(\mathsf{values}(r) = \{v_1, v_2, \ldots\}\) for keys \(\mathsf{keys}(r) = \{k_1, k_2, \ldots\}\), respectively. A \(\mathsf{write}\) operation \(w\) is defined as \(\{(k_1, v_1), (k_2, v_2), \ldots\}\) such that \(i \neq j \Rightarrow k_i \neq k_j\), where \(w\) assigns values \(\mathsf{values}(w) = \{v_1, v_2, \ldots\}\), to keys \(\mathsf{keys}(w) = \{k_1, k_2, \ldots\}\) respectively.

The following definition and theorem are inspired by the dependency graph framework introduced by Adya [42] and further refined by Khyzha et al [43]. Our setting differs slightly from Khyzha et al in that we have operations of a data structure that may either be complete (have returned) or incomplete (have not yet returned). In contrast, Khyzha et al’s framework is built to reason about transactions. However, there is a close correlation: we treat complete operations as complete transactions and incomplete operations as commit-pending transactions in this earlier work.

We first formalise the notion of a dependency graph. Note that for simplicity, we interchangeably write \(x \in p\) and \(p(x)\) for a predicate \(p\).

To prove durable linearizability, we rely on the theorem by Khyzha et al. [43] below. This theorem generalises the original dependecy graph framework of [42] to accommodate operations that may not complete.

Recall that a trace \(\sigma\) is durably linearizable iff (i) any thread executing before a crash does not resume after the crash and (ii) the trace \(\sigma\) with crashes removed is linearizable. This close relationship between linearizability and durable linearizability means that 1 can be readily extended to durable linearizability.

Here, the \(\mathsf{vis}\) predicate is used to indicate whether an operation has taken effect; if an operation does not return due to a crash, it is not known to they system whether it was successful.

We now prove that every execution of FlintKV is durably linearizable. Fix one such execution \(\sigma\). Our strategy is to find witnesses for all \(\mathsf{wr}_k\) and \(\mathsf{ww}_k\) that validate the conditions of Theorem 2. To this end, consider the following definition.

We now define the witnesses as follows:

• \(\mathsf{vis}(r)\) holds for \(r\in \mathsf{Reads}(\sigma)\) iff \(r\) completes and returns;

• \(\mathsf{vis}(w)\) holds for \(w\in \mathsf{Writes}(\sigma)\) iff \(w= \text{\Op{Put}}\) and \(w\) persists line [code:pmem95node95insert] in [lab:insert95critical] to persistent memory or \(w= \text{\Op{WriteBatch}}\) and \(w\) persists line [code:commit95batch] in [algo:process95wb] to persistent memory.

• \((w,r)\in\mathsf{wr}_k\) if and only if

  • \(w\in \mathsf{Writes}(\sigma) \cap \mathsf{vis}\)

  • \(r\in \mathsf{Reads}(\sigma)\)

  • \(\tau(w) \le \tau(r)\)

  • \(k\in \mathsf{keys}(w) \cap \mathsf{keys}(r)\) and

  • \(\neg\exists w'.\) \(\mathsf{vis}(w') \wedge k\in \mathsf{keys}(w') \wedge \tau(w) < \tau(w') \le \tau(r)\)

• \((w,{w}')\in\mathsf{ww}_k\) if and only if

  • \(w,w' \in \mathsf{Writes}(\sigma) \cap \mathsf{vis}\)

  • \(\tau(w)<\tau({w}')\) and

  • \(k\in \mathsf{keys}(w) \cap \mathsf{keys}(w')\)

  and

• \(\mathsf{rw}_k\) is derived from \(\mathsf{wr}_k\) and \(\mathsf{ww}_k\) as per the dependency graph definition.

To show that our witnesses satisfy the requirements of the dependency graph, we rely on the following properties. It is easy to see that the algorithms described in [sec:updates] [sec:recovery] satisfy the following lemma:

Our proof also relies on the following auxiliary lemma:

References↩︎