In my last post on the topic, I talked about ImmutableDictionary and why it was too costly for us to use. At the same time, it is basically the data structure that we need for the task at hand. That task is keeping track of the current set of modified pages, with multiple concurrent versions running at the same time.

ImmutableDictionary is perfect for the task, because it gives us the right immutable behavior, but its performance makes it unacceptable. So the solution is to design a data structure that would fit our needs and requirements.

The people who wrote ImmutableDictionary are not stupid. They didn’t set out to make something that would be slow. The issue is that they set out to solve a generic problem. We can benefit from specializing the data structure for our needs (removing a lot of complexity along the way).

Concretely, we need something that:

• Provides O(1) lookup.
• Plays nicely with the GC and allocates rarely.
• Has a simple structure for the GC to work with (not a lot of interior pointers).
• Still supports the snapshot model that made the immutable dictionary so attractive: the ability to discard values while old snapshots remain valid and consistent.

The problem is combining all of those together. It is much easier if we can drop any of those requirements.

I started the design by dropping the very notion that this is a generic data structure. It isn’t an ImmutableDictionary<TKey, TValue>; instead, we have the ScratchPagesTable data structure.

Conceptually, this is similar to a Dictionary<long, ScratchEntry> in terms of how we’ll use it. ScratchPagesTable is essentially an open-addressing hash table, using linear probing and Fibonacci hashing. That is pretty basic, to be honest. That isn’t what makes it interesting.

Here is the actual layout of the data structure:

The entire design for this table is meant to make it easier for the GC to work. Note that the first three arrays here are plain objects. The _keys and _heads are parallel arrays, which we use to find the actual entry in the _entries array.

The _entries array contains the ScratchEntry structs, which you can see on the right side. Each struct contains all the details about the current entry. Note that the entry also does not use any pointers.

The only pointers in the entire ScratchPagesTable are in the _refs array. Each ScratchEntry in the table points to a location in a particular file. Instead of carrying a pointer in each of the (many) entries in the table, we put them all in the _refs array and refer to them by index from the entries.

We may have tens to hundreds of thousands of entries in the table, but we’ll usually have a much smaller number of files (almost always under ten). By centralizing the references in a single small array, we made the job of the GC so much simpler.

When it needs to scan the ScratchPagesTable to see what is used, it can mark each of the top three arrays immediately and not walk their contents (because they have no pointers). And the _refs array is very small, so that isn’t meaningful.

Let’s talk about the concurrency aspect here. We have the ability to take cheap snapshots from this data structure, which gives us a stable view of the data.

We take advantage of the fact that we have a single writer, so there is just a single thread that mutates the table. Then that same thread is the one that is publishing the new snapshots to other threads.

Here is what this looks like:

A snapshot simply captures references to all four arrays, the total count of items in the table, and, most importantly, the sequence number that was stamped on the snapshot when it was created.

If you look at the ScratchEntry layout, you’ll note that we have the OlderIndex field and the Seq field. Together, those represent a linked list that we can scan to find the first entry (value or tombstone) whose sequence number is less than or equal to the current sequence number that we are using.

A reader using a snapshot holds a mutable array, but the use of the sequence number ensures that it can never actually observe changes that happened after the snapshot was taken.

We don’t need to worry about concurrent mutation, since this is meant to be used with a single publisher (already guaranteed by the way RavenDB works).

Of course, if we just keep on using the table in this manner, we’ll have to deal with garbage. How do we get rid of old entries that no snapshot looks at? Don’t we have to replace the GC ourselves?

Let’s go back to the concept of the sequence. RavenDB keeps track of all the active transactions, and each of those holds a snapshot. That means that we have a cheap way of getting the oldest snapshot and its sequence.

Whenever we create a new write transaction, we check what the oldest sequence number is. That means that when we update the scratch table, we can prune the chains when we find entries that no one is able to look at any longer.

Pruning the chain in this manner doesn’t mean that we can immediately use the entries we unlinked. The issue is that a reader may want to read them. Let’s assume we have a deletion, like in the diagram above. When we prune, we cannot just immediately reuse the entries, because the readers may have already started looking at them.

What we do instead is park them, as you can see in the following diagram:

Once we have progressed through enough transactions and all currently opened transactions started after the entries were parked, we can reuse those entries. Of course, if we have enough entries, we may need to allocate brand new arrays (re-hashing). That is safe to do because all the old snapshots contain the old references; we just discard them.

This model of pruning the old versions from the end is great for most scenarios. However, there is a particularly nasty use case where it utterly breaks down. What happens when we have a long-running transaction? We have to keep all the versions alive until the oldest read transaction is done with them.

As it turns out, there is a very common scenario where this can happen. If we run a backup, we may hold a read transaction for a long time. Write transactions while the backup is running will cause the chain to become longer and longer. The design of the scratch table means that we keep things fast for the current transactions and recent ones.

The old transaction has to traverse the entire chain each time, becoming slower the more time goes by. The slower it becomes, the more time it takes, the more write transactions can happen, the slower it becomes… That isn’t a fun scenario.

RavenDB handles this scenario explicitly. When we detect that the chain is too deep, we start pruning the chain. We discard all the intermediate transactional versions that exist between the current committed version and the oldest read transaction.

You can see what this looks like in the following diagram:

Using this mechanism, we can keep the amount of work that old transactions need to do under control.

The end result of all of this work is a high-performance concurrent data structure that takes into account both how it is actually being used and the internal intricacies of the .NET garbage collection. It isn’t your run-of-the-mill data structure, nothing that would be relevant off the shelf.

It is also directly responsible for an improvement of over 20% in the performance of RavenDB when we compare the two versions side by side.

Over a quarter of a century ago, Joel Spolsky wrote about Netscape’s decision to rewrite its browser from scratch, which later led to Firefox. He called it Things You Should Never Do, Part I.

I remember reading that article at the time and fully agreeing with him. As a side note, it is well worth the time to go through the archive of his posts. Even today, a lot of them hold up very well.

Reading it back again, I found the following quote, which is really appropriate today:

Before Borland’s new spreadsheet for Windows shipped, Philippe Kahn, the colorful founder of Borland, was quoted a lot in the press bragging about how Quattro Pro would be much better than Microsoft Excel, because it was written from scratch. All new source code! As if source code rusted.

To be clear, he was writing in (April 2000) about something that happened in 1992, so 34 years ago. That statement is still very much in force today. Another quote from this article that still lives in my head is:

Back to that two page function. Yes, I know, it’s just a simple function to display a window, but it has grown little hairs and stuff on it and nobody knows why. Well, I’ll tell you why: those are bug fixes. One of them fixes that bug that Nancy had when she tried to install the thing on a computer that didn’t have Internet Explorer. Another one fixes that bug that occurs in low memory conditions. Another one fixes that bug that occurred when the file is on a floppy disk and the user yanks out the disk in the middle. That LoadLibrary call is ugly but it makes the code work on old versions of Windows 95.

There is an interesting question here. Do we have the same problem with AI? After all, AI can write a lot of code. Does it matter?

This post was started when I was working on optimizing RavenDB. That is something that I do as a habit, in an ongoing process. Right now I’m looking into optimizing the scenario of how RavenDB starts up after a cold boot, when running on an I/O-constrained system.

The scenario is a 100GB database running on an AWS gp3 disk with 125MB/sec and 3K IOPS. In most cases, you size up your machines so the working set will fit comfortably in memory. But what about when you start up after a cold boot (memory is empty)?

In that case, the access pattern you have for the data is really important. That is also not something that you’ll typically see in “I used AI to generate a storage engine”. That is the sort of “detail work” that is not interesting to teach (no fancy coding here); it isn’t “my benchmark got 15% faster” (it is very specific to a single scenario).

In long-lived software, however, you accumulate such features. Over time, those end up being a very significant advantage.

Another gem from Spolsky is this blog post, where he talks about software bloat, which is the other side. Then he points out that the review for a new word processor pointed out that the software is very fast, but it lacked (for a journalist) an essential word count feature.

Can you get AI to write all those features and behaviors? Of course, but in order to actually run into them (so you know what to do), you need actual in-field experience.

To really hammer that home, you need that support call when they are looking at the downtime clock while the disk is reading in small increments and their business is down. It’s the same as the old story about the chalk mark.

Going back to the original scenario of optimizing RavenDB for I/O-constrained environments, you need to understand how disks work. In general, for a gp3 disk, the cost of reading 8 KB is the same as reading 128 KB. If you are working from a cold boot and try to read an 8 KB page from the disk, it actually makes sense to read more to try to get things into memory faster.

That is where things get interesting, because the previous statement is true only about IOPS; you also have to balance bandwidth limits, as well as what happens when your memory is full and you’ll need to evict data from the cache.

RavenDB is using prefetching; it will analyze patterns in how you access the data and proactively try to read more when it can. That can dramatically improve cold boot performance.