from Hacker News

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

by adamansky on 4/8/18, 11:29 AM with 13 comments

• by brongondwana on 4/9/18, 10:27 PM

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

  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.

• by shin_lao on 4/9/18, 9:00 AM

  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.

• by ghoul2 on 4/9/18, 10:49 AM

  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?

• by AstralStorm on 4/9/18, 7:36 AM

  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.)

• by mehrdadn on 4/9/18, 10:02 AM

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

• by amelius on 4/9/18, 9:29 AM

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