khonsulabs / bonsaidb

A developer-friendly document database that grows with you, written in Rust
https://bonsaidb.io/
Apache License 2.0
1.01k stars 37 forks source link

Refactor Document Revision to be Sequence based #225

Open ecton opened 2 years ago

ecton commented 2 years ago

Background

Sadly, in pondering #186 as well as #90, it occurred to me that there is no efficient way to retrieve a historical document given the current information. The only way to do so is to scan the history of the single key from the start to the revision being requested.

A few days ago it finally dawned on me what happened. The document design was written back when I planned on doing everything atop Sled, and there was no concept of a "sequence id". Back in those days, my plans for replication and clustering didn't include document history or master-master replication.

Then, I introduced Nebari, and we had a sequence ID. But it just never clicked that I should change from the SHA hash to the sequence id.