3 ms·

The 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

The 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 ago
I 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 ago
  Batching 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 ago
    Write 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 ago
      In 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 ago
I 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.

btrask 11y ago

I 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 ago
Batching 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 ago
  Write 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 ago
    In 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 ago

I 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.