The cost of immutability

Over a decade ago I tested immutable data structures inside RavenDB. The verdict at the time was simple: the performance was unacceptable. That was a long time ago, and one of the things I decided to do recently was to revisit all of it. I looked into that, and the situation didn’t change.

The reason this matters is a piece of code inside of RavenDB that is called the Page Translation Table. It is how RavenDB handles MVCC (transactions, isolation, etc.), and to call it critical for performance would be a massive understatement.

The Page Translation Table holds the set of pages that have been modified by a transaction. You may have multiple outstanding transactions running at the same time, and when you want to read a particular value from the system, you have to go over all of the currently outstanding transactions and check whether that value is one of the temporary pages they modified, or if that value is on the disk.

RavenDB’s current PageTable is based on a ConcurrentDictionary holding a versioned view of the pages (with each page version associated with the relevant transaction). If the description sounds complex, you are correct, it is. It was also one of those things that significantly complicated some major re-architecting that we wanted to do.

As part of a major refactor of RavenDB's internals, we moved the data out of the existing page translation table and into something more natural: an immutable dictionary. More specifically, the BCL’s ImmutableDictionary class.

Note that this is the second or third time that we have come back to ImmutableDictionary as the data structure of choice for this particular purpose. In pretty much all respects, that is the perfect data structure for what we want. It lets us capture a snapshot of all the modified pages inside a transaction, hold onto that snapshot cheaply and easily, and stop worrying about concurrency and race conditions entirely.

If another transaction modifies things, that simply does not affect the snapshot I am holding.

That is a great building block for the MVCC infrastructure that we need inside of RavenDB.

The reason we keep not using ImmutableDictionary is pretty simple, however. The performance is just not there for our needs.

As part of the new architecture, we threw away the old page table, implemented the new architecture (and reaped all the benefits thereof) using an ImmutableDictionary and set out to test what this looks like. It was really bad.

When we dug into the details, the problem child was the ImmutableDictionary. So let us talk about how it actually works. While the ImmutableDictionary has the same interface as a normal dictionary, it is actually implemented as a tree internally.

Every time you mutate it, you create a new node in the tree. That is exactly how it manages to be immutable, and that is exactly what makes it such a pleasure to work with under concurrency. Now consider the impact of that in terms of performance.

The first cost: lookups are no longer O(1)

Say I have a dictionary with ten thousand items. What is the expected cost of a lookup? If this is a dictionary, I expect O(1). Every assumption inside RavenDB is built on the premise that getting this value costs O(1). Since this is a tree, the cost of a lookup is O(log N). For 10K items, the cost would be 14 pointer-chasing operations.

Note the emphasis on pointer chasing? That is a huge cost to consider. Especially for something that runs literally billions of times a second.

The second cost: allocations per mutation

Consider Dictionary<long,IntPtr>, which is what the Page Translation Table in RavenDB boils down to. Then consider it as an ImmutableDictionary. Using a standard .NET dictionary, you get essentially no allocations for writing to the dictionary: all the data consists of value types, stored inside arrays with amortized allocations.

In an immutable dictionary, every single one of those entries is an allocated node. What is worse, the more items you have in the dictionary, the bigger the tree, the more allocations you have. Ouch!

To be clear, if you have a dictionary with tens of thousands of items in it, you’ll allocate more than a kilobyte for each mutation. If you have to do 100 updates in a dictionary with 100K items, you’ll allocate more than 100KB for that.

The third cost: the GC has to walk the graph

The internal structure of an ImmutableDictionary is a tree of references. And that is a pretty complex object graph. The GC needs to walk that entire graph (pointer chasing all the way), and the more complex the object graph, the more work the GC has to do. That is enormously wasteful.

Now put that under heavy load, meaning a lot of items going in and out of the dictionary. The structure is producing many allocations and snapshots as it works. With a high churn rate of values, an ImmutableDictionary is incredibly inefficient in terms of GC cost.

So we end up paying for the ImmutableDictionary in three separate ways: the O(log N) lookup, allocations per mutation, and the GC time spent walking the object graph.

Using the same 100K example as before, here is what this looks like. Note the number of pointers that you have and the pointer chasing that this requires from the GC.

This GC cost is nasty, because it does not show up as a single hotspot in the profiler. It shows up as a smear of additional CPU usage spread across the whole system.

Summary

For the third time, we had to discard the option of using ImmutableDictionary because the performance cost was simply unacceptable. We still gained a lot because using it as a model for the re-architecture let us land on a much better design.

We needed a better option. In my next post, I will get into the specifics of how we actually built that solution.