Re:Introduction to LSM Trees: May the Logs Be with You
by zzzcpan on Sunday April 28, 2019 @10:15AM
(#19771231)
You don't actually need to do asynchronous background compaction at all. You can do compaction whenever in small incremental steps not causing any spikes in read or write latencies. Just spreading it across all writes gets you slightly slower, but latency capped writes. It's unfortunate that LevelDB popularized this compaction in a thread idea. It's pretty bad one.
Re:Introduction to LSM Trees: May the Logs Be with You
by lichtenberger on Sunday April 28, 2019 @10:51AM
(#19771377)
Good catch :-) right, but still merging/compaction work has to be done. Maybe too much, if you just need to fetch a value by its key and thus just an equality scan is needed (no range scans or other comparisons). For the latter case I've implemented an AVL-tree, which is also versioned and stored in our record pages and best read fully in-memory (but doesn't have to). For sure there are plenty of optimizations and for instance also spatio-temporal indexes or full-text indexes possible, but I guess first looking into cost-based rewrite rules for the query compiler and replication/partitioning for horizontal scaling. Too many ideas I guess ;-) but the best would be to have a great open source community :-)
Re:Introduction to LSM Trees: May the Logs Be with You
by dominotw on Sunday April 28, 2019 @10:21AM
(#19771256)
would you know why LevelDB choose compaction in thread vs the method you are describing.
Re:Introduction to LSM Trees: May the Logs Be with You
by eeZah7Ux on Sunday April 28, 2019 @10:22AM
(#19771262)
Any though on https://en.wikipedia.org/wiki/NILFS ?
Re:Introduction to LSM Trees: May the Logs Be with You
by lichtenberger on Sunday April 28, 2019 @10:27AM
(#19771277)
Haven't heard of, but the storage system is heavily inspired by ZFS and by putting some of the ideas (plus adding our own obviously ;)) to the sub-file level:
https://kops.uni-konstanz.de/bitstream/handle/123456789/2769...
Re:Introduction to LSM Trees: May the Logs Be with You
by eeZah7Ux on Sunday April 28, 2019 @09:58AM
(#19771174)
I'd like to see a comparison with using mmap and letting the kernel do the paging.
Re:Introduction to LSM Trees: May the Logs Be with You
by lichtenberger on Sunday April 28, 2019 @10:04AM
(#19771191)
Basically, I'd like to provide the I/O layer with memory mapped file regions, such that it's simply a configuration option if you use the RandomAccessFile implementation or maybe one based on memory mapped files. I think for the JVM there's Chronicle. Thanks so much for asking :-) and by the way any contribution would be the best I can hope for
Disclaimer: I'm the author of a recent article about a free open source storage system I'm maintaining, which versions data at it's very core: "Why Copy-on-Write Semantics and Node-Level-Versioning are key to Efficient Snapshots": https://hackernoon.com/sirix-io-why-copy-on-write-semantics-...