Golden SSTables

When you’re testing, it’s common to transform whatever structure you’re dealing with into text and compare that text to a fixed string of expected text. This is convenient because you get a nice visual representation of what you’re expecting the output to be. This approach can cause problems if the text representation doesn’t capture everything about the object you’re testing. If you add a new field to the object and forget to add it to the string representation, then it’s not getting tested and you get false reassurance that you’ve tested everything.

I recently updated my sstable and recordio formats to include include type metadata — whether they contain strings or protos and whether the values are compressed. I was getting annoyed that I had tables lying around with different kinds of data and I’d find myself probing them with the tools until I found the right combination of types. After this change, opening and displaying information in an sstable or recordio file is automatic.

Along with this change, I wanted to make sure I had some golden examples of sstables that I could use for confirming encoding and decoding in different languages. Dumping these structures to a canonical string representation wouldn’t test the binary encoding. I really wanted to have readable binary files that I could use for comparison.

So, I whipped up a simple binary encoding language.

Here’s an example of an SSTable encoding expressed in the simple binary encoding language. Most values are simply one of:

• vint for a variable length integer encoded as LEB128
• uint64 for unsigned 64-bit integers
• utf8 for strings

The only remaining feature is that you can drop a named tag to specify a location and then use tags as values, either as absolute positions in the file or by subtracting them to get the distance between two tags.

This text representation comes with a simple tool for writing out the binary encoding and then we can use the linux cmp command for comparing binary files.

utf8 "SSTABLE\n"
vint 0 // SSTable Version 0
vint 0 // Empty key descriptor means keys are simply encoded as UTF-8 strings
utf8 ""
vint 0 // Empty value descriptor means values are simply encoded as UTF-8 strings
utf8 ""

// Data chunks
tag chunk0
tag skip0 vint (skip1 - elem0) vint 2 vint 1 utf8 "2" // skip to key k02
tag elem0 vint 5 utf8 "apple" // key k00 (from index), value apple
tag elem1 vint 2 vint 1 vint 6 utf8 "1" utf8 "banana" // key k01, value banana

tag skip1 vint (skip2 - elem2) vint 2 vint 1 utf8 "4" // skip to key k04
tag elem2 vint 2 vint 1 vint 6 utf8 "2" utf8 "cherry" // key k02, value cherry
tag elem3 vint 2 vint 1 vint 4 utf8 "3" utf8 "date" // key k03, value date

tag skip2 // no skip pointer since we're at the end of the chunk
tag elem4 vint 2 vint 1 vint 10 utf8 "4" utf8 "elderberry" // key k04, value elderberry

tag chunk1
tag skip3 vint (skip4 - elem5) vint 2 vint 1 utf8 "7" // skip to key k07
tag elem5 vint 3 utf8 "fig" // key k05 (from index), value fig
tag elem6 vint 2 vint 1 vint 5 utf8 "6" utf8 "grape" // key k06, value grape

tag skip4 vint (skip5 - elem7) vint 2 vint 1 utf8 "9" // skip to key k09
tag elem7 vint 2 vint 1 vint 8 utf8 "7" utf8 "honeydew" // key k07, value honeydew
tag elem8 vint 2 vint 1 vint 7 utf8 "8" utf8 "iceberg" // key k08, value iceberg

tag skip5 // no skip pointer since we're at the end of the chunk
tag elem9 vint 2 vint 1 vint 9 utf8 "9" utf8 "jackfruit" // key k09, value jackfruit

tag chunk2
tag elem10 vint 4 utf8 "kiwi" // key k10 (from index), value kiwi
tag elem11 vint 2 vint 1 vint 5 utf8 "1" utf8 "lemon" // key k11, value lemon

// Index Block
tag index_start
vint 3 utf8 "k00" uint64 chunk0
vint 3 utf8 "k05" uint64 chunk1
vint 3 utf8 "k10" uint64 chunk2

// Max Key
vint 3 utf8 "k11"

// Footer
uint64 index_start
uint64 3 // num index entries
uint64 12 // num elements
uint64 5 // chunk size
uint64 2 // skip size