Hacker News Reader

Comment by packetlost | Hacker News Reader

What's the underlying storage engine? I've been doing some design work on a new hybrid LSM/Extendible Hashing system in Rust and am curious what this is using underneath.

View on HN

Hi packetlost. Currently the underlying storage engines are memory, and distributed TiKV. For the next beta release (coming this week) we also have a local RocksDB implementation and a distributed FoundationDB storage implementation.

In the long run, we want to implement our own key-value store so that we can offer some of the temporal/versioning aspects (which would allow you to view your data in the graph as it appeared at a particular point in time).

For the browser, SurrealDB sits on top of a key-value store which is powered by IndexedDB, so that SurrealDB can run in the browser, using WebAssembly.

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!

I would be really interested to see / find out more about your new hybrid LSM/Extendible Hashing system!

Reply on news.ycombinator.com