4 ms·
Yup. That exactly matches my past experience from when we tried levelDB as a possible replacement for our key-value store in a past project. On paper level DB
by pja 11y ago
Yup. That exactly matches my past experience from when we tried levelDB as a possible replacement for our key-value store in a past project.
On paper level DB looks great but the extra write load from the write amplification thanks to the multi-level data structure meant the real world performance was much worse than a plain BTree / B+Tree for continuous random write load.
If you have a different workload, then levelDB might work for you: continuous appends of mostly new data perhaps?
- jorangreef 11y agoDid you try different level multipliers? i.e. Using 4x instead of 10x, to trade write amplification for read amplification (which can be amortised by bloom filters)?
- pja 11y agoI think we tried changing the level multiplier & it not making much difference - although I didn’t write the code, someone else in our team did. The problem space was a seen-set store for a exhaustive prover. (ie, a continuous loop of: have you seen this state yet? If No, add it to the set of known states, rinse and repeat.) Any memory you allocated to another data structure is memory you’ve just taken away from your in-memory cache for the seen set. Total throughput was ultimately disk IO limited, so anything that increased the number of reads/writes just made things slower. I don’t think the bloom filter would have helped, because every access was potentially a write, but I’d have to go away and think about it for a bit to be sure!
- hedgehog 11y agoThat makes some sense, performance is dependent on how writes are distributed in the key space. For logging analytics or telemetry data with keys that are roughly timestamps you get a really nice seekable log and usually good compression ratios and minimal to no compaction. Also for an application that was mostly any kind of writes & deletes I would guess LSMs would do pretty well.
- hyc_symas 11y agoThe InfluxDB experience shows that the answer is more complicated than that - they're storing time-series data, which they thought an LSM would be good for. But in reality, they're storing multiple series simultaneously. That turns the simple sequential workload into a very random one. Each write is a sequence of K/V pairs: A:1, B:1, C:1, D:1, E:1 A:2, B:2, C:2, D:2, E:2 This turns into the worst-case key ordering for LevelDB because every write overlaps with the previous keys. Worst-case turns out to be ridiculously bad. https://news.ycombinator.com/item?id=10437621 https://news.ycombinator.com/item?id=10437621
- btrask 11y agoI think you're backwards. Random writes are LSM trees' forte because they can batch them. Sequential writes would be doable with a b-tree.
- hyc_symas 11y agoBatching doesn't help the write amplification from compaction. Read the doc. http://leveldb.googlecode.com/svn/trunk/doc/impl.html http://leveldb.googlecode.com/svn/trunk/doc/impl.html Do the math.
- btrask 11y agoWrite amplification is not the only thing that matters. For small keys, higher write amplification is a good tradeoff for doing less seeks (which yes, are still a performance problem on SSDs, probably because of the block size). For large keys, I agree with you, you shouldn't use an LSM-tree. There is a threshold between seek time and compaction.
- hyc_symas 11y agoIn the InfluxDB workload, they didn't get the "less seeks" you're talking about. Sure, you can delay paying for the seek by a second, if that. So can the buffer cache on any other DB structure. But when you have an overlapping range of keys and it's continuously growing, you hit the worst-case. Which InfluxDB did.