4 ms·
I 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 sp
by pja 11y ago
I 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.
- hedgehog 11y agoI think we're in violent agreement here, the case you note is exactly why key distribution matters. But even more than that the distribution of value lifetime matters too, if a lot of the values stored are very short lived then not only do they not get rewritten many times but you also get to only ever write them as part of sequential batches (no random seeks). The compressibility of your data also makes a big difference, if intra-key compression is effective on your data that can easily be 1.5x to 3x reduction in the footprint on disk. So, benchmark your workload.