It's interesting to have a non-LSM based persistent engine (If I read correctly).
Although BTrees are slower when it comes to writing, they don't have compaction issues and are generally better are reading data from disk.
I also like there is a lower-level API should you wish to build your own database logic on top of the block manager.
It would be interesting to have more information about how data is actually written to disk and I think such approach could benefit from being able to mount a device directly.
Last but not least, 255 GB will seriously limit this database to embedded use cases.
Yes, b+trees are more performant for reading compared to skip-list because of better data locality on memory/disk. But SL better at insertion and sequential reads. 255 GB is a simple trade-off between disk space required per record and the ability to manage large data-sets since SL is a not very space friendly data structure) Although I think 255 GB is good enough in many use cases.
Yes. I suppose that probability to get such bad random distribution which makes SL search to be linear is similar to probability of moving all oxygen atoms to only one side of your room.
If the adversary find a bug in your system, such as not so random "random generator", then it can bring it down. But if the random generator is reasonable, then you can expect it to behave properly on all inputs.
unrelated: I need a key-value storage engine/data structure that is suitable to use on a microcontroller, with sdcard as the storage medium. Performance isn't critical (within reason of course), but must need very little ram (10s-100s of bytes, at the high end), and of course must minimize/optimize sdcard writes and reads. Any suggestions?
ENOTENOUGHINFO: Any of the following changes what data structure should be used: read/write ratio, key size, data size, what is the interface to sdcard.
Gut feeling is that with TENS of bytes you will only get an append-only log.
They take slightly different tradeoffs. I wrote twoskip to work around a handful of issues with skiplist around crash recovery. The big cost still is repack speed, which is why I have a project to build something called zeroskip, which won't be single-file, but will have some very nice never-rewrite behaviour.
13 comments
[ 3.8 ms ] story [ 41.1 ms ] thread(Yes, I know that for some platforms you can mmap memory.)
Although BTrees are slower when it comes to writing, they don't have compaction issues and are generally better are reading data from disk.
I also like there is a lower-level API should you wish to build your own database logic on top of the block manager.
It would be interesting to have more information about how data is actually written to disk and I think such approach could benefit from being able to mount a device directly.
Last but not least, 255 GB will seriously limit this database to embedded use cases.
[1]: https://news.ycombinator.com/item?id=1171468
[2]: https://stackoverflow.com/questions/45115047/why-redis-sorte...
https://github.com/cyrusimap/cyrus-imapd/blob/master/lib/cyr...
https://github.com/cyrusimap/cyrus-imapd/blob/master/lib/cyr...
They take slightly different tradeoffs. I wrote twoskip to work around a handful of issues with skiplist around crash recovery. The big cost still is repack speed, which is why I have a project to build something called zeroskip, which won't be single-file, but will have some very nice never-rewrite behaviour.
http://opera.brong.fastmail.fm/talks/twoskip/twoskip-yapc12.... describes the design of twoskip a bit.