Designing a Database for Non Volatile Memory

Processors have been getting faster for decades. Unfortunately the time to read and write a file has not kept up. A modern non-volatile memory (NVM) drive answers a single 4 KiB random read in tens of microseconds, a thousand times slower than loading the same data from volatile memory.

Databases are asked to hide this gap. We are going to design one that responds to requests quickly (low latency) and handles many requests at once (high throughput) using a simplified model of NVM drives. We discuss why to shard per core, how to choose a storage format, and how to pipeline requests. We finish with a brief discussion of a request's latency distribution.

For the purposes of this article we are going to assume Cassandra's CQL interface. It looks like SQL but is more restrictive, specifically:

CQL is designed this way so requests can be handled by a single shard. Sharding divides a table's rows into groups, and different shards may be stored on distinct drives or machines. Partition keys let us route a request directly to the shard holding the relevant partition. Some requests do need data from several partitions, and potentially several shards. In this case the request is scattered among the shards and then gathered to form a final answer. Cassandra's data modelling guide may be useful for understanding the implications of Cassandra's design.

Constraining our database's interface allows the following analysis to be more specific, although the same factors apply to most databases.

An NVM drive is best utilised when it holds many read or write operations at once. A drive contains many independent flash dies. Software which waits for a response before making another operation leaves most of these dies idle. The drive has a queue of operations submitted but not completed.

Let the average size of the queue be or the queue depth. Let the time to answer one operation be or the unloaded latency. At best we can complete the outstanding operations every seconds. This is the latency bound, . It is dominant when the drive is mostly idle (and exact by definition when only submitting one operation).

The drive also has a ceiling for how well it can parallelize. However many operations we offer, it retires at most per second. This is the saturation bound and does not depend on usage.

Throughput is constrained by

The two bounds cross at a queue depth called the saturation point.

Below the drive is idle part of the time, and adding operations is free throughput. Above the drive is already saturated, so an arriving operation waits behind the others and latency grows in proportion to .

The Micron 7450 PRO is an enterprise NVMe drive. Its 7.68 TB E1.S model answers a 4 KiB random read in at queue depth one, and is rated at 1,000,000 reads per second at queue depth 256. If we approximate our database usage as a 70/30 blend of random reads and writes we are told to expect operations per second. From these numbers we derive from our model that

We expect to be able to issue 33 operations at once before operations start to take longer. The below table illustrates these diminishing returns.

Our model tells us that we should maximize the queue depth enough to reach the point of diminishing returns. The most straightforward way is multithreading. We divide partition ownership among threads and use the partition key to route each query. To avoid contention we have each thread own it's caches and files. If we have enough connections making requests touching different shards we can may be able to saturate the drive using this technique alone.

We can also pin each shard to a core, which tells the operating system not to move the thread to another core. Pinning has the trade-off that a busy shard cannot use an idle core's capacity. This may cause a lower average throughput but allows more consistent latency, we will return to this trade-off when discussing tail latency.

Since I/O operations are much slower than compute we don't want our threads to wait for a response. We could have a thread per request but this requires more work and memory from the OS. We instead make each request's handler into a coroutine: a function that can suspend part-way through, return control to the thread, and resume later from where it stopped. A request suspends it's coroutine when it submits an I/O operation and resumes when the answer arrives. Unfortunately, since we are touching the same shard's shared resources we can't simply overlap the I/O for different request coroutines, this is where pipelining will come in.

The format we store our table's rows deeply effects which I/O operations we make. We will consider two choice, B-Trees or log structured merge (LSM) trees. A B-tree keeps rows in one sorted structure and updates it in place. Its pages form a shallow tree in which each page holds keys and the locations of the pages below it. A log-structured merge tree instead keeps several sorted runs of pages, newest first, and merges them in the background (compaction). The two structures differ in how they utilize I/O.

Under this analysis the LSM tree allows more drive queue depth () per query but requires more total operations. Our goal will be that with Shard-per-core and other tricks we will already be past and so the LSM tree's extra queue depth will not be worth the increased total operations. We therefore choose a B-tree and work on increasing queue depth within a shard.

We break read and write requests into smaller components and map the dependencies between them. This will allows us to overlap and combine operations from different queries. The analysis focuses on I/O, which dominates compute cost. Costs are approximated relative to one uncached drive read ().

Write for the length of the longest chain of dependent I/O operations and for the total number of I/O operations. A request's latency depends on , the request throughput throughput depends on . The diagrams below show example paths for a read and a write request respectively.

The steps have the following relationships:

Two read requests naming different partitions can naturally interleave without coordination. We ensure that a thread does not lock on read and ensure that our clients take advantage by opening multiple connections. Unfortunately we can't pipeline write requests to ensure our tree remains in a consistent state. This means stalling on writes.

We can also trivially pipeline the network calls. The write ahead log can also be pipelined but since we still need to commit before returning to ensure durability. we instead batch with a limit on the number of batched requests.

It was mentioned earlier that sometimes we may trade lower average latency for consistency (low variance).

We reduced variance by:

On the other hand we increased variance by:

There is a trade-off between variance and mean, similar to the trade-off between memory and compute. Our database design allows us to tune this trade-off by, for example, changing the flush batch size.