Iowow – C11 skiplist-based persistent key/value storage engine • Hacker News Board

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

#11

Post by hvidgaard » Mon, Apr 09, 2018, 11:53 AM UTC

mehrdadn wrote: post #9

adamansky wrote: post #8

Earlier quoted context omitted.

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.

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

#12

Post by 112233 » Mon, Apr 09, 2018, 12:01 PM UTC

ghoul2 wrote: post #10

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.

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

#13

Post by thr0w__4w4y » Mon, Apr 09, 2018, 2:29 PM UTC

ghoul2 wrote: post #10

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?

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

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

#14

Post by brongondwana » Mon, Apr 09, 2018, 10:27 PM UTC

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.