Ayende @ Rahien

It's a girl

Versioned Collections

Last time we talked about collections, I talked about Linked Dictionary and Safe List. The first did some fancy dancing to reduce the cost of allocations, and the second would re-create the list on change.

Those implementations were good enough for us to go to hundreds of thousands of writes per second in the sequential scenario, but we noticed them cracking up under the pressure for the random writes scenario.

So I started looking at more options. As it turns out, there is a very simple immutable and highly efficient design for a list. Just hold to the end of the list, and every append is just creating a new node that points to the old tail of the list. This makes adding to the list an O(1) operation. It is very fast, simple and easy to work with.

This has just one issue, it allows efficient iteration only in reverse order. And there are a few places where we are actually relying on the ordering, so it would be nice not to lose that. Alex suggested using a internally mutable but externally immutable structure, such as this one. The benefit here is that we still get external immutability, but we get the performance of mutable access.

That works, as long as we use a list, which we needed for some pretty important things. However, the key collection, and the one that caused us most performance issues was the cost of getting values from the page table, which is a dictionary. We needed a really good solution there. I started to think that we would need to change all the code that uses this, but then I realized something very important. I don’t actually need this. I don’t need immutability, I just need snapshotting. And another aspect of that is that we have only a single writer thread for all of those items. So while we require that once we gave an instance to a reader, it can never change, that only applies to its externally observable behavior.

I would like to thank Tyler for the suggestion. Basically, we start off with a Concurrent Dictionary (and the only reason we need it is so we can write to the dictionary while we are reading from it, something that isn’t safe to do with standard dictionary). The values in that dictionary is an immutable list of the values with the transaction id. Whenever we modify a value, we can drop all the values older than the oldest existing transaction.

And when we search, we search for a value that is not greater than our own transaction id. That means that we effectively have a frozen snapshot of the page table, at a very little cost. I felt bad calling this as a generic collection name, so we actually named the class PageTable, since it has a very specific role in the code.

After this was done, we could not longer find any major cost associated with collections. So it is onward to the next challenge, reducing the cost of key comparisons…


01/01/2014 05:32 PM by

Ayende, I'm very glad the versioning idea worked out so well. And thanks for the kudos. I'll be following the Voron project with great interest.

Carsten Hansen
01/02/2014 10:41 AM by
Carsten Hansen

Is it the Anders Hejlsberg data structure.

See http://chessprogramming.wikispaces.com/Linked+List http://channel9.msdn.com/Shows/Behind+The+Code/Life-and-Times-of-Anders-Hejlsberg


01/03/2014 05:18 PM by

When I read the title, I was under the impression that this was going to be about versioning of values in Voron, as in e.g. an event store scenario. But I see now it is about page mapping.

Glad to see the code I posted has been useful. It appears you made the trade off decision to minimize time for readers, which makes sense if there are a lot of "in-flight" non-synced transactions in scratch pages buffer.

The two design alternatives I looked at were

(1) a dictionary of pages mapped to versions (in. a transaction ordered "immutable" list), which is what you appear to have chosen. This option requires a bit more work/allocations on updates (i.e. commit and data sync completion) but should (amortized) bring some benefits if there are many readers and a substantial amount of non-synced transactions.

(2) a transaction ordered "immutable" list of committed pages in a dictionary. This allows minimal and atomic work in updates: data sync just records up to where it has advanced, on commit a new list is created that appends a new dictionary with committed pages and sets the head to the transaction where data sync has advanced. Downside is that for each reader you need to flatten the list into a dictionary between last data sync and reader tx id. If there are many entries in the list and many readers, this will be slower.

Ayende Rahien
01/05/2014 10:18 AM by
Ayende Rahien

Alex, That is correct. Our tests scenario is bulk insert, so that is a really costly thing to do if you have to do a lot of work all the time.

Thomas Mueller
01/07/2014 09:37 AM by
Thomas Mueller

This sounds like the multi-version map I'm working on. Beware it is Java:


Comments have been closed on this topic.