My hybrid LSM/Ext. Hash system may be of interest actually. It's purpose built for tracking historical data similar to Datomic's data model, but emphasizing constant-time read operations for current data while keeping the read speeds for historical data reasonable. In short: 2 level LSM tree (log file, immutable page files) with a extendible hashing to index into the page files. The identity of each record is the key + tx instant (time of COMMIT, or some other monotonically increasing number that is unique to a transaction set). Optionally you can index over historical data by having a record per-key that just appends a new tx-instant + offset for better longitudinal query performance.

Hi packetlost this is a really interesting topic to me. I wrote my MSc thesis on this exact topic - https://surrealdb.com/static/whitepaper.pdf ! I've learnt a lot since writing this thesis, and would have many different opinions if I wrote it today, but very interested in this area of research!

Same! I'll read through that paper when I have time. What are your thoughts on how you would implement something like that today?

At the time I implemented the versioning using separate trees on top of the Radix tree. Today I would augment the tree with t he versioned nodes, and would use a Concurrent Adaptive Radix Tree for the base tree. This would allow high concurrency. Then at the base of the tree I would store a temporal link to each tree modification, so that you could access the changes in time order!

Very, very interested in chatting further about this!

Same here! I'll reach out on other channels when I've compiled my notes and have a fully functioning prototype :)

Is your work public? I'm also working on a (loosely) datomic inspired database with pluggable backends, so this might be very interesting for me.

Hi the_duke. The base implementation of that key-value store (written in Golang) can be found here: https://github.com/surrealdb/rixxdb

I don't think the implementation of the ideas in the thesis were added to the public project in the end.

We will be working on this in due course in Rust, however, and the implementation will be completely open source!