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…