Sled: Feature: history

[jjl]

Hi. Sled looks interesting, and some of the crates you've built to enable it look like they could be used to build a rust-native datomic clone.

Before I went off and did something crazy like that, I was just wondering if you'd be amenable to being able to query history within sled itself? One project I will be working on soon requires historical data access for legal reasons and the kludge it's using to make postgres do it is pretty horrible.

Cheers,
James

[spacejam]

@jjl this is something I've been thinking a lot about recently, as we ramp up for MVCC and transaction support.

Possible implementation idea if you want to do this with today's sled:

• create a persistent monotonic ID generator, the simplest (yet not super efficient) way of doing this is to just have a key in sled that represents the highest ID, and writers first use cas to increment its value by 1. This will be implemented in sled shortly, because having a persistent ID generator is pretty valuable for a large number of applications.

Read Technique A:

• append this monotonic ID to any "high-level" key, being careful to zero-pad the beginning to make comparisons simple.
• during reads, add 1 to the last byte of the "high-level" key (or append a 0 byte) and use the pred function from @mitchmindtree's sled-search crate (or a similar approach) to find the preceding key. if present, make sure the result is actually what you're looking for (high-level key is prefix, exact number of ID bytes follows). This is also something that should be built into sled, and may happen when reverse iteration is supported.

Reverse Technique:

• reverse the bits of the ID (let flipped_id = std::u64::MAX - generated_id) and append this flipped representation
• use Tree:scan from the "high-level" key and call next exactly once. Perform the same prefix / id check as above.

Time Tracking

• periodically get an ID from the generator, write it to a key that includes seconds since the unix epoch.
• when you want to know "what happened since ?" you scan to find the last recorded offset among the keys above using a similar reverse-encoding technique, or use pred from sled-search.

Auditing:

• You can scan through different versions of keys and correlate them to the times written in the time tracker above

The Future of sled:
When we implement mvcc / transactions, we'll need to implement some sort of configurable old-version cleaning mechanism anyway. The main question is whether the cleaning will happen at the pagecache or the sled Tree level. Different levels want different historical granularity, and there are different costs to pay for achieving them:

• A transactional KV wants to keep versions around that are at least as old as the oldest currently running transaction. To prevent phantom anomalies while supporting transactional scans, it may be helpful to include the pages which comprise the tree's index nodes which are modified over the course of a transaction due to splits / merges. transaction read timestamps do not need to be persisted across restarts, as long as write timestamps do, so we only need to persist written timestamps.

• A datomic-like database built on top of sled wants to generate ID's, and keep keys and values for human-configurable durations. it is not relevant how the index structure is garbage collected as long as old values for keys remain accessible. Any externally-visible ID's must be assumed to be write timestamps, and internally persisted