Lei Peng

Posted on Oct 3

MemTable Crash-Safe Recovery

#database #cpp

In our benchmark, recovering a 1.5 GiB MemTable after a process crash took an average of 4.989 ms with CSPP crash-safe recovery versus 5987.152 ms with default SkipList/WAL replay—about 1200× faster.

(1) Background

1.1 Failure models: process crashes and hardware power loss

Process crash: abnormal process termination, including deliberate termination with kill -9 / abort; the operating system continues running, and its file page cache (PageCache) remains intact.
Hardware power loss: the server hardware suddenly loses power, the operating system stops running, and in-memory state (including PageCache) is lost.

The container orchestration system Kubernetes allows a default 30-second grace period for normal termination, then forcibly terminates the process with SIGKILL when that period expires. Bugs in user-space software, operational incidents, or a direct forced kill may bypass normal shutdown.

A data center utility power outage does not necessarily mean that servers suddenly lose power: uninterruptible power supplies (UPS) and backup generators can maintain the supply. For example, the 10–15-minute UPS arrangement in Eaton's handbook lasts far longer than the default grace period above. Combined with alerts and automatic shutdown procedures, it can provide time for an orderly exit.

1.2 File mmap keeps data accessible after a process crash

file mmap is a mechanism that maps a file into a process's address space, allowing the process to access file contents as memory.

With a shared mapping (MAP_SHARED), writes modify file pages managed by the kernel. A process crash only removes that process's mapping; it does not discard the modified file pages. A new process can reopen and map the same file and still access those data. See Linux mmap(2).

What survives is the file data, not the original process's address space. This also does not mean that the data are already durably stored on disk: they remain accessible through the operating system, in PageCache.

(2) From high-performance concurrent reads and writes to crash safety

CSPP (Crash-Safe Parallel Patricia) began with high-performance concurrent reads and writes; its predecessor was Dynamic Patricia Trie. For key reads and writes alone, it is an order of magnitude faster than SkipList. For example, an existing concurrent write test recorded performance more than 30 times that of RocksDB SkipList when value length was excluded from consideration.

Improving concurrent read/write performance requires reducing how much reads and writes wait for one another. Multistep in-place modifications to ordinary data structures may temporarily break consistency. Locks are typically needed to prevent readers from accessing intermediate states, so readers must wait for writers to finish. How can consistency be maintained while reads and writes proceed in parallel? CSPP first completes the replacement structure in a copy, then publishes its new entry point with an atomic operation. Readers therefore see a complete, consistent structure at any moment. This combines Copy-on-Write (COW) with atomic publication. OffsetSkipList (OSL) is another, independent concurrent data structure based on SkipList; it also uses copy-on-write and atomic publication.

A read-side lookup can finish in a finite number of its own steps without depending on a writer's progress. This property is called wait-free reads; see Herlihy's definition of wait-free.

Now consider a process crash: when reading a published structure, a writer stopping permanently midway through an update is indistinguishable from a writer pausing for a long time. The isomorphism between this concurrent read/write mechanism and process crash safety, in terms of structural readability, is explained in The Isomorphism Between Wait-Free Reads and Crash Safety.

For a new process to keep using the structure, its bytes must survive and its addresses must be resolved again. When the new process remaps the same file, the mapping base may change, so absolute addresses from the original process cannot be reused directly. CSPP / OSL use relative offsets inside the structure rather than absolute addresses. Once the new process identifies the structure's entry point in the file, it can access the structure relative to the new mapping base. File mmap preserves the bytes, relative offsets allow address resolution after remapping, and the update and publication mechanism required for wait-free reads preserves the readability of the published structure. Together, these provide crash safety for the underlying data structure.

(3) From LSM to ToplingDB

An LSM (Log-Structured Merge-tree) buffers writes, then generates and merges sorted files in batches. RocksDB is an LSM-based KV storage engine. ToplingDB is a RocksDB fork that retains its basic read/write model while rewriting hot-path code and replacing key components.

In this model, the WAL records writes, and MemTable buffers new data. Flush turns a MemTable that has stopped accepting writes into an SST, usually entering L0 first and later being merged and organized by compaction. An ordinary Flush traverses the KV pairs and rebuilds an SST: this is BuildTable.

Can this rebuilding step be avoided during a normal Flush?

A MemTable already maintains queryable data and indexes. If that structure is placed in file-mapped memory (file mmap) from the moment it is created, and the database can read it directly as an SST, Flush no longer needs to traverse the KV pairs and reorganize another copy of the data. This requires a MemTable whose file layout can be reused, rather than a faster BuildTable.

ToplingDB uses CSPP / OSL as the underlying mechanisms and implements MemTables that meet this requirement.

For example, in CSPP MemTable's FileMmap mode, data and indexes are maintained directly in the file mapping. During Flush, ConvertToSST turns this existing file into an SST and hands it to the LSM, avoiding rebuilding. However, complete values may still be stored in both the WAL and the MemTable file.

memtable_as_log_index goes further: the MemTable records value offsets in the WAL and directly references the existing values. This eliminates duplicate memory consumption for values in the MemTable and reduces how much data fsync must write back during ConvertToSST. Short values can be stored inline. When combined with ConvertToSST, the resulting SST continues to use these references. See MemTable as Log Index for the complete design.

Figure 1: Two forms of reuse: file structure and values.

If a process crashes at an unexpected point in the code, an ordinary unflushed MemTable disappears with the process. The next Open must replay the WAL and reinsert the KV pairs. The larger the MemTable, the more rebuilding is required. Since a normal Flush can reuse the file, can crash recovery also preserve work already completed? The original proposal for Omit L0 Flush already suggested this direction.

The crucial difference is that a normal Flush handles a complete MemTable that has stopped accepting writes, whereas a file left by a crash may have stopped midway through a write. Whether it is usable cannot be determined merely by its existence.

(4) From individual KV pairs to complete write batches

Is it enough for the data structure to remain readable after a process crash? RocksDB's ordinary write path uses WriteBatch to guarantee atomicity for the entire batch, and sequence numbers to distinguish writes and different versions of the same key. Structural readability alone is therefore insufficient: recovery must not expose half a WriteBatch.

Consider an ordinary write that assigns a sequence number to each KV operation. Suppose earlier writes have completed through sequence number 100, and the next WriteBatch contains two KV pairs with sequence numbers 101 and 102. The batch's WAL has been fully written, but the process crashes after inserting 101 and before finishing 102. The underlying structure may be entirely consistent and 101 readable, yet directly converting this file into an SST would expose half a WriteBatch to the user.

Thus, neither “the last readable KV pair” nor “the maximum sequence number in the file” is the recovery endpoint. With concurrent insertion, a KV pair with a larger sequence number may even finish first; observing it does not prove that earlier writes have completed. A DB may also contain multiple Column Families (CFs). Each CF has its own MemTable and SSTs, but they share the WAL, and a WriteBatch can span CFs. Completion in one CF cannot declare the entire batch successful on behalf of another unfinished CF.

The underlying structure guarantees individual KV pairs; the DB must guarantee the whole WriteBatch. Yet this does not require discarding all data in the file. In the example above, work through 100 has completed. Temporarily hiding 101 and fully replaying the batch containing 101 and 102 from the WAL preserves earlier work while completing the interrupted write.

The question therefore narrows from “Can this file be used?” to “Which part of it can be used directly?” During writes, we must save a safe sequence number that confirms completeness: data up to that boundary can be reused, while data beyond it are recovered from the WAL. This boundary is pubseq.

(5) Where should pubseq be placed?

Batch completeness is not a requirement introduced only by recovery. Normal reads on the ordinary write path must also never see half a WriteBatch, so RocksDB provides a sequence-number boundary for reads. LastPublishedSequence represents this published visibility boundary. It differs from publication of an underlying node or link: that makes a KV pair reachable in the structure, but does not mean the whole write batch is visible. This existing read-visibility boundary is therefore a natural candidate for the recovery boundary pubseq.

Writes, however, do not always follow a single serial path. To amortize WAL write costs, the engine can combine multiple WriteBatches into a write group. The WAL and MemTable have their own progression, and multiple threads may insert the same group in parallel. The boundary can advance only after every write it covers has completed. Finishing the WAL write, or having one thread insert a higher sequence number, does not prove that all MemTable data in the group are usable.

The consequences are asymmetric. Advancing the boundary too early treats unfinished data as complete, skips WAL that is still needed, and causes missing data. Letting it lag conservatively only means recovering some already inserted KV pairs again. The former breaks correctness; the latter incurs a small recovery cost. The goal is therefore to keep pubseq as close as possible to LastPublishedSequence, rather than make them equal at any cost.

In the earlier example, even if both 101 and 102 have been inserted, the process may crash before updating the recovery boundary, leaving the saved pubseq at 100. Recovery still uses 100, hides 101 and 102 in the file, and replays the entire batch from the WAL. This does not discard successful writes; it merely does not reuse work that could not be confirmed in time.

Figure 2a: Two different crash points. The boundary may lag conservatively, but must never advance incorrectly. In both examples, [101, 102] has been fully written to the WAL.

Saving only the sequence number is still insufficient. It tells us which KV pairs can be used, but not where to resume in the WAL. If finding that offset still requires scanning the entire log, avoiding KV insertion alone leaves recovery time dependent on total WAL volume. We must therefore save the corresponding WAL file number and offset together, so “how far to reuse” and “where to replay from” are two representations of the same boundary.

These boundaries cannot independently take their latest values. If the WAL offset advances beyond reusable data, a gap appears that is neither fully covered by the file nor recovered from the log. The pair must match: one side preserves confirmed data, and the other restores unconfirmed data. Together they cover the complete write history required for recovery.

The boundary must also align with complete logical log records (WAL Records). A record may contain one WriteBatch or a whole group of combined WriteBatches, also called a WAL group. Anything not directly reused must be replayed as complete records, rather than filling in only the few KV pairs that appear missing. This realigns the underlying individual-KV guarantee with the DB's batch-write guarantee during recovery.

Figure 2b: pubseq and the WAL replay offset are paired. Existing data and complete WAL Records together cover the recovery range.

(6) Saving the boundary can also be interrupted by a crash

We now have three related values: pubseq, the WAL file number, and the WAL offset. They are saved in the recovery metadata file CSPUBSEQ in the DB directory and updated through shared file mmap, so the next Open can read them.

But if the three fields are written individually, the process may exit between writes. For example, a new pubseq paired with an old WAL offset has individually readable fields, but together they do not form a valid recovery boundary. Using it to decide how much WAL to skip can go wrong.

The record containing these three values and padding is 32 bytes. AVX can write it with one aligned 32-byte store instruction. Given the premise that a process crash occurs at an instruction boundary, this avoids leaving a mixture of old and new fields between two store instructions.

Using an AVX intrinsic alone is insufficient. Clang can split a store without volatile into two 16-byte stores. Marking this access volatile uses an explicit Clang/LLVM constraint: the backend must not split or merge volatile loads/stores natively supported by the target. See LLVM Volatile Memory Accesses. The GCC and Clang AVX paths can therefore share this volatile store.

Without AVX, this single-instruction store is unavailable, but incomplete updates can still be identified and rejected. The record carries a generation counter: first mark it odd, then update the fields, and finally publish an even value. If recovery sees an odd value, it knows the update may be incomplete and cannot use the record.

This does not require obtaining the latest boundary after every crash. A complete older boundary, with all required files still available, merely requires replaying more WAL Records. If the record is confirmed incomplete, fast reuse is abandoned. What is unacceptable is combining old and new fields into a seemingly valid boundary that never actually existed.

This resolves publication-record consistency for process crashes, not durability after power loss. WAL and file synchronization settings retain their respective responsibilities.

(7) How to use the files left behind

MemTable files left by the previous process that have not been incorporated into the LSM as normal SSTs are called leftovers. With a reliable boundary, one question remains: these files may actually contain data beyond pubseq. Deciding to replay those data from the WAL does not automatically remove the half-batch from the old file. Exposing the full contents may still let reads encounter versions that must not be accepted.

Could those KV pairs be deleted before conversion? That would require traversing or even rewriting the file, returning recovery to work proportional to MemTable size. Instead, the file contents are retained while the visible data they can contribute are restricted. SSTs converted during recovery are marked with VisFilter:1; their sequence-number upper bound is read from file metadata, and both point lookups and iteration hide KV pairs whose sequence numbers exceed the pubseq boundary.

The leftover 101 in the example is thus no longer “file content that must be repaired,” but “a version this recovered SST must not provide.” Complete writes for 101 and 102 come from WAL replay. Keeping the old bytes physically while accepting only the confirmed prefix logically preserves both the WriteBatch boundary and the speed of direct file reuse.

For a given key, this requires hiding versions beyond the boundary, rather than hiding the entire key. If a key has versions at sequence numbers 90 and 101 and the boundary is 100, version 90 in the file must remain readable. CSPP / OSL MemTable implementations retain versions distinguished by sequence number, allowing a lookup to impose an upper bound and find a confirmed older version without being obscured by an unconfirmed newer one.

Figure 3: Continuing the example where 101 is inserted and 102 is not, two data paths together form the recovery result.

This extra check applies only to SSTs produced by recovery. ConvertToSST during normal Flush does not need it, and ordinary iterators should not incur this cost for crash recovery.

(8) How much WAL work remains?

First consider ordinary writes. Confirmed data can be reused directly, and unconfirmed leftovers have been filtered out. All that remains is the WAL after the recovery boundary. If both recovery metadata and leftovers are usable, a DB on the default write path whose in-flight writes have all completed needs no WAL Record replay after a crash: it skips the covered WAL and seeks directly to the saved offset.

Write organization also affects this tail. two_write_queues separates WAL-only requests from requests that also write to MemTable into two queues. seq_per_batch assigns sequence numbers per batch or sub-batch rather than per KV operation. When the former is enabled without the latter, publishing the boundary after the MemTable side finishes achieves the same result.

unordered_write allows writes to complete out of sequence-number order, while the pipelined_write path overlaps the WAL and MemTable stages. These two paths conservatively keep the saved boundary one WAL group behind, leaving the final group for replay. This is the concrete tradeoff described earlier: reuse slightly less to obtain a safe boundary.

Now consider TransactionDB's two-phase commit (2PC) transactions. If the KV data are already in the file, can the WAL containing them be skipped? Not yet: prepared transactions that have neither committed nor rolled back are still unresolved and must be recovered. KV data alone cannot replace these transaction states.

Thus, under allow_2pc, even when leftovers are reused, the relevant WAL must still be read to rebuild transaction recovery state in recovered_transactions_. KV pairs already covered before the boundary are not inserted again. TransactionDB's WriteCommitted writes transaction data to MemTable at commit time and supports this recovery path, including prepare on the second queue. This does not, however, mean transaction recovery can be promised to need only a seek to the WAL tail.

WritePrepared / WriteUnprepared are two other policies that allow transaction data to enter MemTable before commit and use sequence numbers assigned per batch. When they enable two_write_queues, they fall into the seq_per_batch && two_write_queues combination, for which the current implementation falls back to full WAL replay. The sequence-publication mechanism determines the fallback; the transaction policy's name alone is insufficient.

Another question remains: what if files are missing or the saved boundary is unusable? Fast recovery must prove that skipped WAL is covered by existing data. Missing or invalid required leftovers, relevant CFs lacking the required capability, an unusable publication record, or conversion failure invalidate that assumption and require full WAL replay. The recovery log filter wal_filter requires user logic to actually process the log, while best_efforts_recovery, which tries to recover whatever data remain usable, has its own recovery semantics. These cases likewise do not use fast reuse.

Fast recovery therefore relies on cooperating guarantees: the underlying structure leaves readable KV pairs; the publication boundary confirms complete writes; read filtering excludes unconfirmed leftovers; and the WAL fills in the rest. Without any one of these, “the file still exists” cannot imply “rebuilding can be skipped.” When all conditions hold, recovery shrinks from rebuilding the entire MemTable to reusing files and completing the tail.

(9) Back to Kubernetes: fast Close and fast recovery after a process crash

Since ConvertToSST is so cheap, why not perform it when normally closing the database (Close)? Upstream RocksDB does not Flush ordinary WAL-protected MemTables during Close. The reason is not a lack of benefit, but the expense of BuildTable, which can make Close wait a long time.

ToplingDB MemTables support inexpensive, millisecond-scale ConvertToSST. The cost has changed, so an operation previously unsuitable for Close is now feasible: when all MemTables can be converted, Flush (convert) them during Close. In Kubernetes, an application that responds normally to the stop signal and calls Close no longer waits for expensive BuildTable. In principle, a large MemTable therefore no longer prevents graceful shutdown within the grace period. Successful conversion also avoids rebuilding those MemTables from WAL at the next Open. Fast shutdown and fast restart can be obtained together, rather than deferring the work saved during Close until the next Open. The existing condition that Close Flushes when unpersisted data exist remains in place; here, unpersisted data means data neither written to WAL nor Flushed to SST.

kill -9 terminates a process directly; user-space software bugs and operational incidents can also cause process crashes. The kernel terminating a process because of insufficient memory—an OOM kill—is another source of abnormal exit. Crash-safe recovery does not depend on process cleanup. Instead, it uses the pubseq, visibility filtering, and WAL recovery boundary derived above to reuse the surviving data at the next Open. Flush/Close ConvertToSST and crash-safe recovery thus share underlying capabilities while addressing normal and abnormal exits respectively. The former does not require enabling the latter, and the latter does not require the former to have run.

avoid_flush_during_shutdown: true unconditionally skips Close Flush, including ConvertToSST. This causes data loss only when unpersisted data that were not written to WAL exist; ConvertToSST does not introduce that risk.

(10) Expressing these conditions in configuration

The main switch, DBOptions::memtable_crash_safe_recover, defaults to false and cannot be changed online through SetDBOptions(). Every CF that has not been dropped must use CSPP / OSL with convert_to_sst: kFileMmap, and configure an SST reader matching the conversion output.

10.1 Configuration example

Add memtable_crash_safe_recover: true to DBOptions.default in db_bench_community.yaml to enable it. memtable_as_log_index is not required.

10.2 Configuration constraints and online changes

When enabled, Open automatically sets manual_wal_flush to false, recycle_log_file_num to 0, and wal_compression to kNoCompression. Writes ignore disableWAL and still use the WAL. A read-only Open automatically disables fast recovery and warns that full WAL replay may be slow.

Changing convert_to_sst online requires enabling allow_dangerous_update when creating the factory. It defaults to false and cannot itself be changed online. After a change, inspect the recovery log to confirm whether fast recovery is still used; see Changing Options Online.

Changing memtable_as_log_index at restart changes the WAL format. When the old format is recognized, recovery and Flush first use that format, then the DB opens with the new configuration. If unresolved transactions exist, complete their commit or rollback with the old configuration first.

10.3 Identifying the recovery path actually used

Convert leftover, WAL tail from in the log indicates fast reuse and positioning at the WAL tail. fallback to full WAL RecoverLogFiles indicates fallback to full WAL replay. An enabled switch and a successful Open do not mean that this particular recovery actually used the fast path.

(11) An actual recovery test

If the preceding reasoning holds, the benefit should come from avoiding reconstruction of the entire MemTable, rather than merely replaying WAL a little faster. We can fill similarly sized MemTables with two configurations, terminate the process without calling Close, and compare the next Open on the two recovery paths.

The test on 2026-10-02 filled one MemTable to 75% of 2GiB write_buffer_size (1.5GiB), using 16-byte keys and 128-byte values, then called _exit directly without Close. Each measurement first copied the same directory and timed only DB::Open; checks that read the first and last keys ran after timing.

This compares two configurations of the same ToplingDB build: CSPP crash-safe and the default SkipList / WAL replay. It is not a comparison against a separately built upstream RocksDB.

Data resided on the memory-backed filesystem /dev/shm. Five measurements were taken:

Recovery path	Five Open times (ms)	Mean (ms)	Relative time
CSPP crash-safe	6.545, 4.692, 3.820, 4.768, 5.120	4.989	1.0
Default SkipList / WAL replay	6124.357, 5849.884, 5984.324, 5943.391, 6033.802	5987.152	1200.1

Both stopped at the same target MemTable memory usage, rather than the same key count: CSPP had 9,664,512 keys, and the default SkipList had 9,090,048. Recovery logs confirmed that the former reused leftovers without fallback, while the latter replayed the full WAL. These results show the practical benefit of avoiding WAL-based reconstruction.

See crash_recover_bench.md in the main repository for the method and raw results. The accompanying YAML was used for this experiment.

Returning to the original rebuilding cost: FileMmap and ConvertToSST let normal Flush avoid rebuilding an existing structure; memtable_as_log_index eliminates duplicate memory consumption for values in MemTable; crash-safe recovery allows existing data and indexes to remain usable after a process crash. The key is not faster WAL replay, but a safe publication boundary that bridges the gap between underlying individual-KV crash safety and DB atomicity, establishing which work need not be repeated.

Once this gap is closed, a large MemTable no longer necessarily entails lengthy crash recovery. Crash-safe mode therefore encourages MemTables much larger than those in typical RocksDB configurations.

(12) Suppressing automatic operating-system writeback

Filling a MemTable performs random memory writes. In CSPP / OSL FileMmap mode, these are random writes to its PageCache. Pages modified but not yet written back to disk are called dirty pages, and the operating system schedules periodic writeback according to how long they have been dirty—their dirty age. Random writes quickly dirty all pages. After pages are written back, continued random writes quickly dirty them again. Different intermediate states of the same page are therefore written to disk repeatedly: repeated writeback.

The random writes are confined to the MemTable. A small MemTable involves fewer pages and less repeated writeback; it may even fill and convert to an SST before repeated writeback occurs, so the effect is limited. As MemTable size increases, random writes involve more pages, the MemTable lives longer, and repeated writeback increases. This overhead therefore deserves more attention for very large MemTables (currently limited to 16G). With memtable_as_log_index enabled, MemTable mainly holds indexes and WAL offsets for values, eliminating duplicate value storage and reducing writeback volume until the issue is essentially negligible. Examining this overhead follows ToplingDB's design philosophy of “eliminating all nonessential overhead”; it does not mean ToplingDB loses its competitive advantage because of it.

Intermediate states continue changing after being written back. Early writeback neither avoids final writeback nor adds any other capability. Existing file writes in the DB have controlled fsync / fdatasync, with the application determining when synchronization is needed. Periodic writeback can therefore be delayed as far as possible while MemTable accepts writes, then synchronization performed according to configuration at ConvertToSST.

Increasing vm.dirty_expire_centisecs delays the point at which dirty-page age triggers periodic writeback; for example, set it to 60000 (600 seconds). This solves the issue for the current workload, but the parameter applies machine-wide and also changes other programs' writeback policies. The application only wants to delay writeback for its own MemTable backing files, yet must change a global policy.

We implemented the deferwriteback kernel module for this purpose. It continuously refreshes the dirty age of a specified file's inode, delaying age-triggered periodic writeback. This avoids changing machine-wide policy, but carries deployment and maintenance costs. What the application actually needs to express is simply: “This file is undergoing continuous random modifications; please delay writeback as far as possible during this phase.” It should not need to repeatedly refresh the kernel's timer.

A further improvement would therefore be an operating-system syscall providing a file-level deferral hint with a lifecycle. The application requests it when filling begins, withdraws it when filling finishes, and then synchronizes according to the existing configuration. Unmapping or process exit should also withdraw the request automatically. This is a proposed public interface: the application provides information about its usage phase, while the kernel retains control of writeback scheduling. The hint applies only to periodic writeback triggered by dirty age; memory pressure, dirty-page limits, and explicit synchronization can still trigger writeback. A feature request has already been submitted to the Linux kernel. If implemented, it would benefit the entire Linux world.

DEV Community