STAR: a special-length prefix?
what if: [ len key len val ] -> [ len len key val ]
Rapid-fire pckts coming at you, with increasing frequency! We really gotta settle this early truncation thing. This is, again, about Q3 in Settling the details.
Quick review of the options from last time:
Option 1: accept that STAR doesn't defend against early truncation, apps need to implement something themselves if they need it: rejected. we can do better.
Option 2: signalling bytes: one extra byte before each data pair + one byte to mark the end of the archive. Totally works, very boring, kind of ugly-looking: not preferred. but i'll push for it if folks reject the idea i'm about to pitch.
Option 3: special varint: use signed varint length prefixes so -1 can be the the end-of-archive marker: rejected for varint because signed varints are a mess. we could use bijoux: not preferred (with pain, i really like bijou64): only has a rust implementation.
Option 3 alt: non-minimal LEB128 zero, aka 0x8000. I actually love this option, but everyone else will hate it. The one cool thing we could have with LEB128 is low-cost special (non-canonical) values we could use, but almost no existing decoder will work out of the box.
Option 4: sentinel data: make the empty pair (0x00 0x00) special, make a special encoding for the empty pair with what would be the empty pair as a prefix (like 0x00 0x00 0x00), and then make the end-of-archive signal another special encoding with that prefix (say, 0x00 0x00 0x01). This sort of reminds me of SLIP, and I almost like it but: rejected because it introduces special-case handling for a rare event -- i think many implementations would end up with buggy empty-pair behaviour.
So where does that leave us?
Varint density (..shift the number line?)
I dislike signed varints (option 3) for another reason: they cost double the bits to encode, so they will tend to use more bytes. Every other bit is unused across the entire range, just so that we can encode one special value for the termination marker.
Plus, would we use signed varints for all three length prefixes, or just key-length prefixes? It would be nice to avoid the cost where we can, so I guess we'd have two different varint variants in the format. Boo.
But hey: since we only need to encode one special value, what if we kept unsigned varints but shifted them all up?
0x00 => end of archive.
0xXXXX.. => decode as varint and subtract one => next key length. So, 0x01 is len=0, 0x02 is len=1, etc.
This would pretty much work? We reduce the usable range by exactly one, we keep the varint's bit density (additional bytes just happen one number sooner).
It's a bit weird, and we still have one varint that needs special handling.
Varint density redux: re-wrap the pair!
Right now we have (len | key) followed immediately by (len | val). they are sort of each little atoms, and we hope that serializers and parsers don't lose track of which half of a pair they're parsing.
what if,
# instead of
len(key) | len(val) | len(key) | len(val)
# we did
len(len(key) | val) | len(len(key) | val)I need to work out a better ascii notation, so for clarity:
- the key is wrapped inside an outer pair framing
- the so the outer
lenis the length of(len | key)plus the length ofval.
This is actually CAR-like, where each block's int | CID | data framing makes the int cover the CID and data together.
But something important just happened!!!!! In the previous encoding, and empty pair becomes 0x00 0x00 -- zero-length key prefix, zero-length value prefix. With the wrapped key, an empty pair is: 0x01 0x00 -- the inner key is still 0x00 but the outer wrapping is length=1 because it contains the (empty) key's length prefix.
So: a valid pair block can never begin with 0x00.
That means a block starting with 0x00 cannot be a valid block, and we can use a 0x00 to unambiguously mark the end of the archive.
As a bonus, each pair is now a bit more of an "atomic block" -- harder to get out of sync between keys and values.
0x001