{"id":95,"date":"2026-03-25T16:43:58","date_gmt":"2026-03-25T16:43:58","guid":{"rendered":"https:\/\/byte64.com\/?p=95"},"modified":"2026-03-25T16:43:58","modified_gmt":"2026-03-25T16:43:58","slug":"golden-sstables","status":"publish","type":"post","link":"https:\/\/byte64.com\/?p=95","title":{"rendered":"Golden SSTables"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">When you&#8217;re testing, it&#8217;s common to transform whatever structure you&#8217;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&#8217;re expecting the output to be. This approach can cause problems if the text representation doesn&#8217;t capture everything about the object you&#8217;re testing. If you add a new field to the object and forget to add it to the string representation, then it&#8217;s not getting tested and you get false reassurance that you&#8217;ve tested everything.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I recently updated my sstable and recordio formats to include include type metadata &#8212; 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&#8217;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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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&#8217;t test the binary encoding. I really wanted to have readable binary files that I could use for comparison.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">So, I whipped up a simple binary encoding language. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here&#8217;s an example of an SSTable encoding expressed in the simple binary encoding language. Most values are simply one of:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>vint for a variable length integer encoded as <a href=\"https:\/\/en.wikipedia.org\/wiki\/LEB128\">LEB128<\/a><\/li>\n\n\n\n<li>uint64 for unsigned 64-bit integers<\/li>\n\n\n\n<li>utf8 for strings<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">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.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">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.<\/p>\n\n\n\n<pre class=\"wp-block-code has-small-font-size\"><code>utf8 \"SSTABLE\\n\"\nvint 0 \/\/ SSTable Version 0\nvint 0 \/\/ Empty key descriptor means keys are simply encoded as UTF-8 strings\nutf8 \"\"\nvint 0 \/\/ Empty value descriptor means values are simply encoded as UTF-8 strings\nutf8 \"\"\n\n\/\/ Data chunks\ntag chunk0\ntag skip0 vint (skip1 - elem0) vint 2 vint 1 utf8 \"2\" \/\/ skip to key k02\ntag elem0 vint 5 utf8 \"apple\" \/\/ key k00 (from index), value apple\ntag elem1 vint 2 vint 1 vint 6 utf8 \"1\" utf8 \"banana\" \/\/ key k01, value banana\n\ntag skip1 vint (skip2 - elem2) vint 2 vint 1 utf8 \"4\" \/\/ skip to key k04\ntag elem2 vint 2 vint 1 vint 6 utf8 \"2\" utf8 \"cherry\" \/\/ key k02, value cherry\ntag elem3 vint 2 vint 1 vint 4 utf8 \"3\" utf8 \"date\" \/\/ key k03, value date\n\ntag skip2 \/\/ no skip pointer since we're at the end of the chunk\ntag elem4 vint 2 vint 1 vint 10 utf8 \"4\" utf8 \"elderberry\" \/\/ key k04, value elderberry\n\ntag chunk1\ntag skip3 vint (skip4 - elem5) vint 2 vint 1 utf8 \"7\" \/\/ skip to key k07\ntag elem5 vint 3 utf8 \"fig\" \/\/ key k05 (from index), value fig\ntag elem6 vint 2 vint 1 vint 5 utf8 \"6\" utf8 \"grape\" \/\/ key k06, value grape\n\ntag skip4 vint (skip5 - elem7) vint 2 vint 1 utf8 \"9\" \/\/ skip to key k09\ntag elem7 vint 2 vint 1 vint 8 utf8 \"7\" utf8 \"honeydew\" \/\/ key k07, value honeydew\ntag elem8 vint 2 vint 1 vint 7 utf8 \"8\" utf8 \"iceberg\" \/\/ key k08, value iceberg\n\ntag skip5 \/\/ no skip pointer since we're at the end of the chunk\ntag elem9 vint 2 vint 1 vint 9 utf8 \"9\" utf8 \"jackfruit\" \/\/ key k09, value jackfruit\n\ntag chunk2\ntag elem10 vint 4 utf8 \"kiwi\" \/\/ key k10 (from index), value kiwi\ntag elem11 vint 2 vint 1 vint 5 utf8 \"1\" utf8 \"lemon\" \/\/ key k11, value lemon\n\n\/\/ Index Block\ntag index_start\nvint 3 utf8 \"k00\" uint64 chunk0\nvint 3 utf8 \"k05\" uint64 chunk1\nvint 3 utf8 \"k10\" uint64 chunk2\n\n\/\/ Max Key\nvint 3 utf8 \"k11\"\n\n\/\/ Footer\nuint64 index_start\nuint64 3 \/\/ num index entries\nuint64 12 \/\/ num elements\nuint64 5 \/\/ chunk size\nuint64 2 \/\/ skip size<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>When you&#8217;re testing, it&#8217;s common to transform whatever structure you&#8217;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&#8217;re expecting the output to be. This approach can cause problems if the text representation doesn&#8217;t capture everything [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[8],"class_list":["post-95","post","type-post","status-publish","format-standard","hentry","category-data-structures","tag-sstable"],"_links":{"self":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/95","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=95"}],"version-history":[{"count":1,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/95\/revisions"}],"predecessor-version":[{"id":96,"href":"https:\/\/byte64.com\/index.php?rest_route=\/wp\/v2\/posts\/95\/revisions\/96"}],"wp:attachment":[{"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=95"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=95"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/byte64.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=95"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}