Improved batch key storage

[dw]

[final design: http://pythonsweetness.tumblr.com/post/73248785592/acid-batch-record-format ]

1. "Pure keys" mode: when a collection's key is based entirely on the record value (e.g. log line timestamp) or a common prefix, batches need only store the highest and lowest member keys in their key, since member record keys can be perfectly reconstructed. Lookup would expand varint offset array then bisect+decode until desired member is found.

There are several variants to how this could be implemented.

One way (and possibly the preferred way) would be to contain all the smartness inside the Collection implementation, and make it a default behaviour. Given keys [(a, b, a), (a, b, b), (a, b, c)] collection would notice (a, b) common prefix, and encode that prefix only once during batch record creation.

The second way is relying entirely on the record value, or the record value combined with some context. But since writing the original TODO entry, I'm not sure the former is any better than just storing the exact key, and the latter seems impossible to support without "puncturing" the key function, and maybe turning it into a fully-fledged class.

[dw]

Decided on the 'preferred' approach above: there will be a single batch compression mode, and it will automatically strip any common prefix from the set of records.

Definitely:

• Physical key becomes [hi key, lo key] to continue to allow fast membership tests.
• During batch creation, longest_common_prefix(keys) is used to determine how much of prefix to discard.
• During batch read, longest_common_prefix([hi key, lo key]) is used to determine prefix to restore.

Open questions:

• Should list of suffixes be included in the compressed value? If so, decompression needs to occur to test membership, and record data compressability will be affected by key suffixes.
• How to handle variable-length suffixes. First approach is varint-encoded length prefix on each. Second would be NUL-padded to MAX(len(suffixes)). The first approach works better when variable-length strings are present in the key, but requires a linear scan to locate an entry. The second approach works better when suffixes are all relatively short (e.g. a single integer), and allows bisection search for initial member.

[dw]

Decided:

• List of suffixes are NUL-padded to maximum length of any particular suffix.
• Array of suffixes are included inside the compressed data.

Open questions:

• Support a mode where a bloom filter is used to represent all the compressed suffixes? Initial record value contents would be the filter