Saturday, January 29, 2022

Checking Immutable Data

The database implementation in the Go version of Suneido relies a lot on immutable data that is shared between threads without locking.

The problem is that Go has no support for immutability. It doesn’t have const like C++ or even final like Java. (Go has const but only for simple numbers and strings.)

I was seeing some sporadic crashes and corruption. One possible cause was something accidentally modifying the theoretically immutable data. The immutable database state is a large complex set of linked structures processed by a lot of complex code. As with a lot of immutable persistent data structures you don’t copy the entire structure to make a new version, you basically path copy from each spot you want to change up the tree to the root. It's easy to miss copying something and end up mistakenly modifying the original.

I had recently been using checksums (hashes) to verify that the data read from the database file was identical to the data before it was written. (To verify the reading and writing code, not to check for hardware errors.)

I realized I could use the same checksums to detect erroneous changes to the immutable state. I ran a background go routine that looped forever, fetched the state (atomically), computed its checksum, waited a short time (e.g. 100 ms) and then computed the hash again (on the same state). If something had incorrectly mutated the state the checksum would be different.

And I actually found a few bugs that way :-)

Although unfortunately they were not the ones that were causing the crashes :-(