Iowow – C11 skiplist-based persistent key/value storage engine | Hacker News Reader

Iowow – C11 skiplist-based persistent key/value storage engine

iowow.io

48 pointsadamansky13 comments

Will be interesting to test this against Cyrus' two skiplist based databases:

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.

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.

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.

Might be coincidental -- but you also post a similar request very recently on the FreeRTOS forum?

Darn, I hoped for a standalone thread safe structure and there I get a whole database.

(Yes, I know that for some platforms you can mmap memory.)

Skip lists are randomized, right? Whereas B[-whatever] trees have guaranteed fast performance?

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.

Even against an adversary? (Asking because I don't know the data structure too well.)

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.

What is the skiplist used for? I.e., what data does it allow to skip over?

The lastest example I found is Redis, they use Skip List for their Ordered set.

[1]: https://news.ycombinator.com/item?id=1171468

[2]: https://stackoverflow.com/questions/45115047/why-redis-sorte...

Reply on news.ycombinator.com