Memory is slow, Disk is fast – Part 3

Big O notation is a lie. Well, okay, it's a simplification that lies by omission.

Can O(√n) scale better than O(log n)? Can a disk-based algorithm outperform an in-RAM data structure? Yes, and yes.

Scaled to 2 billion nodes, the AVL binary tree needs 144 GiB of RAM. DiskArray keeps its data on 8 NVMe drives and uses 264 MiB of RAM, but it's still faster at everything.

Part 1 showed that computers are getting wider, not faster, and that PCIe bandwidth is outpacing DRAM bandwidth.

Part 2 showed that streaming from disk can beat streaming from the page cache.

Part 2.5 showed that with the right hardware and software, streaming from disk can beat a buffer in DRAM. So far I've shown how a sequential read from NVMe is fast, which is a cool trick but not controversial enough.

I'm getting worried people still aren't getting the point.

The point is that our intuitions about computer performance are all wrong.

So this time we're going to show how an on-disk data structure doing random reads and writes to disk is faster than an in-RAM data structure. To make it worse, computer science textbook Big O notation says the on-disk algorithm is going to scale worse than the in-RAM algorithm.

Same old used box as Part 2.5: a 24-core Xeon Platinum 8260 with 35.75 MiB of L3 and 192 GiB of DDR4, and 8 Samsung PM983 NVMe drives over NVMe-oF on four 100 Gb InfiniBand links.

Keep a sorted set of 8-byte keys, and support four transactions on it:

That's the core of a database index, an order book, a leaderboard, a time-series store.

Let's walk through the algorithm selection by first principles and childlike wonder.

The simplest solution is an array of keys, kept in order.

search(key) is a binary search. Look at the middle, throw away the half the key can't be in, and repeat. 16 keys take 3 or 4 hops. A billion takes about 30. O(log n).

at(i) doesn't search at all. The i-th smallest key is just array[i], at a fixed offset from the start. One access. O(1). You can't beat that.

To insert, you have to make room. Everything after the new key moves over one slot to open a gap, then the new key goes in the gap.

Delete is the same in reverse. Take the key out, then everything after it moves over to close the gap.

Either way, on average, half the array moves, every single time. It's a memmove, about the most efficient thing a CPU can do with memory, but it's still O(n). At 4M nodes, every insert moves about 16 MiB. At a billion nodes it would be 4 GiB per insert. The array also has to be one contiguous block, so growing it means allocating a bigger one and copying everything over.

The textbook fix for "insert moves everything" is the linked list.

Each node holds a key and a pointer to the next node. To insert, you change two pointers. Nothing moves.

But to insert 21 you first have to find where 21 goes, and the only way to find anything in a linked list is to start at the head and follow the pointers one at a time. Search is O(n). at(i) is O(n). Insert and delete are O(1) once you're in the right place, and O(n) to get there.

Adding a node is cheap, but finding where to insert it is really expensive. So this doesn't solve our problem.

Use the pointers to branch out instead of to line up, and you get a binary search tree.

Smaller keys go left, bigger keys go right. Search walks down from the top, throwing away half the tree at each step, just like binary search on the sorted array. Insert walks down the same way and hangs the new node off the bottom, just like the linked list. Nothing moves. Keep a count of the nodes under each node and at(i) is a walk down too.

On paper it's the best of both: log n for everything.

In practice a plain binary tree has a problem. Its shape depends on the order you insert things. Insert keys in sorted order and every new node goes to the right of the last one. It would perform like a linked list.

The AVL tree fixes this: after each insert or delete it checks the heights of the two sides and, if they're off by more than one, rotates a few nodes to rebalance. The tree stays about log₂ n deep no matter what.

But this isn't free; there is overhead to implement the tree. Every node is its own allocation with a key, two pointers, a balance factor, and a count. That's a lot of bookkeeping for an 8-byte key: 72 bytes of RAM per key, where the sorted array needs 8. The biggest sorted array I ran, 4M nodes, is 32 MiB of RAM. The same 4M nodes in the AVL tree take 288 MiB. At 2G nodes the AVL tree used 144 GiB of RAM.

Let's look at how things scale and compare that to Big O predictions.

At first glance, it looks like Big O gets the ranking right. The sorted array's performance for insert and delete falls off a cliff while the search and at() performance degrades more slowly. The AVL tree performance degrades slowly as predicted.

The AVL tree solves the insert and delete problem but costs a lot of overhead that shows up in search and at() performance as well as extra RAM. The sorted array has a lot going for it: everything is in order, in one place, with no pointers to chase and no overhead. Its only problem is that an insert has to move half the array. Let's try a more brute-force solution to insert and delete.

If we cut the array into pieces we could contain the areas affected by inserts and deletes. Our DiskArray data structure splits the sorted keys into small extents. A small index says which extent holds which range of keys. To insert, find the extent with the index, then do a sorted-array insert inside that one extent. You only ever move part of the extent, never the whole list.

Then, because we're making a point, we can put the extents on disk too. That way we only need the index in RAM with a small buffer pool to handle the IO for in-flight and active extents.

A textbook answer for this kind of structure depends on your assumptions. Extent size is a variable parameter. It could be as bad as O(√n) for insert and delete if we scale the extents with n. However, in practice, given the hardware constraints, I sized the extents to what the disks want and fixed them: 512-key extents because that's one 4 KiB disk block, 4096-entry directory blocks so a split only ever shifts a few tens of KiB. Most of the time an insert is effectively one 4 KiB read, one 4 KiB write, and a log n search of the index in RAM. But occasionally it has to edit a directory block. The extent, directory, and even I/O introduce constants that are significant factors in the math for the realistic scales we'll be working in.

Full Disclosure: if you look at the code you'll notice the top-level index that points to directory blocks is growing with n. I planned to make that split into blocks as well, extents all the way up the tree. But I didn't get around to it. So technically there is a corner case that is O(n). With my current settings a second tier would kick in at around 8G nodes. So in practice the O(n) means that, on average once every couple hundred thousand inserts, a directory block splits and the top level has to memmove() up to about 1.4 MiB and rebuild its count tree. That's noise next to the drive I/O. If I did add a recursive index tree as planned, then I think we're officially just a B-tree variant and are for sure O(log n).

To simplify, I'm just going to say as an algorithm it scales as bad as O(√n) and as good as O(log n). If that's not a reasonable argument, I'm sorry. I majored in Electrical Engineering, not Computer Science, so I don't know the theory as well as I do the reality.

Big O says AVL wins or at least ties. In-RAM vs On-Disk says AVL wins.

I want to compare DiskArray to AVL in DRAM not L3. 512K nodes × 72 B is ~36 MiB which is the L3 size. So we'll compare up to 512K nodes and more than 512K nodes in separate graphs.

AVL wins everything here: about 10x faster on search at 2K nodes, still almost 2x at 512K. Every pointer hop is a cache hit, and cache hits are cheap. DiskArray is flat at around 2M searches/s, because it's paying for machinery it doesn't need yet: queues, workers, a buffer pool. Its data still fits in the 24 MiB buffer pool, so the drives aren't even being read.

Nevertheless, even in cache, AVL performance is scaling down fast. Search goes from 19.6M/s at 2K nodes to 4.0M/s at 512K, about 5x slower.

Now let's compare them as we scale past 512K nodes:

From 16M nodes up, the disk-based structure beats the in-RAM tree at everything, all the way to where AVL ran out of RAM at 2G nodes. DiskArray kept going to 64G.

Let's compare what happens during an insert() at 2G nodes.

This doesn't help at first glance. In fact it makes it look like DiskArray is doing way more work.

It depends what you count, and every way of counting it is interesting.

Two definitions run through all of this. Used is the bytes an algorithm deliberately reads, plus the bytes it deliberately writes. Moved is what the hardware actually transfers: DRAM and the L3/L2 caches move in 64-byte cache lines, so reading 8 bytes moves 64, and the drives move 4 KiB blocks. The drive traffic is measured. The rest is estimated from the data layouts.

Inserts per second, times the data moved and used per insert, gives us the bandwidths. At 2G nodes:

DiskArray moves more data per insert than AVL, and it's faster on both counts. It moves the overhead faster: 5.1 GiB/s of traffic against AVL's 1.8, 2.9x. And it moves the data it actually needs faster: 2.1 GiB/s against 312 MiB/s, 6.9x. More bytes, moved faster, every way you count them.

Every AVL insert waits on about 62 reads, one after another, and uses 1 KiB of the 5.8 KiB those reads drag in. That's 312 MiB/s of useful work. Higher bandwidth DRAM wouldn't help, because DRAM latency hasn't moved in 20 years.

DiskArray is short of bandwidth. Its CPU work is about 0.3 µs per insert. The drives are the limit: from 32M to 1G nodes they hold at ~5.5 GiB/s, ~720K inserts/s. More drives, or faster ones, and it goes faster, until that 0.3 µs of CPU catches up at around 3M inserts/s.

A drive round trip is about 87 µs. If DiskArray did one insert at a time, every insert would wait that long, twice, and it would manage a few thousand inserts/s. It does 670K. Here's how:

DiskArray keeps 2048 transactions in flight, in two halves of 1024. One core does all the algorithm work and queuing; 28 io_uring workers just talk to the drives.

Big O counts steps. It assumes every step costs the same. They don't, not even close.

A billion L1 cache hits take about a second. A billion DRAM misses take a minute and a half, and a billion NVMe reads take a day. Big O counts every one of those as one step. Also, when you parallelize, the timescale comes back down to earth. So Big O notation is very limited in its predictive power in practice. It defines the shape of the performance curve but not it's slope or magnitude.

Let us observe the relative scaling performance these algorithms actually experience from 512K to 2G nodes.

We can see AVL is scales much worse than Diskarrary even though Big O would make us think the opposite is true.

I started at Intel doing flash memory out of college. In the early days of the technology, you could use very simple equations to predict the characteristics of a cell. At some point, the cells shrank to where the number of electrons in a cell was something that had to be quantified and thought about. Now, the equations have to start taking quantum effects into consideration.

Big O in its most reductive form isn't going to tell you how things are going to perform in practical scales. It didn't have to. But as the performance characteristics of various elements of the system continue to diverge and become extreme I don't think the single n term O() is useful anymore. I think it's time to start treating these equations and simulations more seriously and add in more nuanced effects.

Notice the curves aren't smooth log n curves. They have step functions where each step is something outgrowing hardware.

Big O can't see