Iowow – C11 skiplist-based persistent key/value storage engine
1–10 of 14 posts
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#2Darn, 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.)
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#3It'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.
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#4It'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 writt…
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.
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#5What is the skiplist used for? I.e., what data does it allow to skip over?
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#6What 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...
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#7Skip lists are randomized, right? Whereas B[-whatever] trees have guaranteed fast performance?
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#8Skip 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.
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#9Skip 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.)
Re: Iowow – C11 skiplist-based persistent key/value storage engine
#10unrelated: 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?