3 ms·

A queue is the correct pattern for a queue. A tree, of any form, offers no advantage. The InfluxDB experience is definitely illuminating. Their problems with L

A queue is the correct pattern for a queue. A tree, of any form, offers no advantage. The InfluxDB experience is definitely illuminating. Their problems with LMDB were mainly due to misuse of the API. https://disqus.com/home/discussion/influxdb/benchmarking_leveldb_vs_rocksdb_vs_hyperleveldb_vs_lmdb_performance_for_influxdb/#comment-1447316291 https://disqus.com/home/discussion/influxdb/benchmarking_lev... For batched sequential writes, there is no other DB anywhere near as fast as LMDB http://symas.com/mdb/microbench/ http://symas.com/mdb/microbench/ (Section E, Batched Writes) But even so - the reason LMDB can do this so quickly is because for batched sequential writes it cheats - it's just performing Appends, there's no complicated tree construction/balancing/splitting of any kind going on. If you know that your workload will only be producer/consumer, with sequentially generated data that is sequentially consumed, it's a stupid waste of time to mess with any other structure than a pure linear queue. (Or a circular queue, when you know the upper bounds of how much data is outstanding.) As for your initial statement - no, an LSM tree is not a correct pattern here. If your consumers are actually running as fast (or faster) than your producer then it should never flush from Level0/memory to Level1/disk. In that case all you've got is an in-memory queue that evaporates on a system crash. If your consumers are running slower, that means data is accumulating in the DB, which means you will have compaction delays. And the compaction delays will only get slower over time, as more and more levels need to be merged. (Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity.) LSM is never a correct pattern.

leif 11y ago
> In that case all you've got is an in-memory queue that evaporates on a system crash. https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf > Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity. No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact. Read more, kids.
- hyc_symas 11y ago
  Ah yes, you're absolutely right. O(N log N) because there are log N chunks to be merged. O(N log N) is still untenable in the long run, nobody has exponentially growing compute resources.
  - databass 11y ago
    May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N). Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.
    - hyc_symas 11y ago
      "Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself. The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes then everything that goes into Level 0 must eventually be pushed out to Level 1. Buffering doesn't make writes free, it only displaces their occurrence in time. So you have a rolling merge every M writes. As far as Big-O goes, that's N log(N) / M == N log(N) because Big-O disregards constant factors! In the context of an implementation like LevelDB, theory and reality diverge even further. Since it's chunking data into 2MB files and deleting them during each merge operation, and also writing a bunch of bookkeeping into Manifest files and other stuff, the number of actual I/Os is much higher. A lot of wasted activity in allocating and deallocating space - filesystem metadata overhead that's also not transactionally safe. In LevelDB a single merge reads 26MB and writes 26MB at a time to push 2MB of data from a level L to level L+1. So now instead of a single merge op costing only N, it actually costs 13*N. Again, if you're only talking about Big-O complexity you sweep this under the rug. But in reality, this is a huge cost.
      - 11y ago

leif 11y ago

> In that case all you've got is an in-memory queue that evaporates on a system crash. https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf > Remember that merge operations are O(N). Then remember that there are N of them to do. O(N^2) is a horrible algorithmic complexity. No. Mountains of actual math refute this. LSM-tree merges are O(N log N). This is an Actual Fact. Read more, kids.

hyc_symas 11y ago
Ah yes, you're absolutely right. O(N log N) because there are log N chunks to be merged. O(N log N) is still untenable in the long run, nobody has exponentially growing compute resources.
- databass 11y ago
  May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N). Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.
  - hyc_symas 11y ago
    "Amortised per write" - now you're getting down into the constant factors, which Big-O disregards. But you can't ignore them in real implementations. First the actual writes have a 2x constant factor, since you're writing to a WAL in addition to the DB itself. The original LSM paper claims that writes to Level 0 are free because that's all in-memory. But that's not really true; if you have a stream of incoming writes then everything that goes into Level 0 must eventually be pushed out to Level 1. Buffering doesn't make writes free, it only displaces their occurrence in time. So you have a rolling merge every M writes. As far as Big-O goes, that's N log(N) / M == N log(N) because Big-O disregards constant factors! In the context of an implementation like LevelDB, theory and reality diverge even further. Since it's chunking data into 2MB files and deleting them during each merge operation, and also writing a bunch of bookkeeping into Manifest files and other stuff, the number of actual I/Os is much higher. A lot of wasted activity in allocating and deallocating space - filesystem metadata overhead that's also not transactionally safe. In LevelDB a single merge reads 26MB and writes 26MB at a time to push 2MB of data from a level L to level L+1. So now instead of a single merge op costing only N, it actually costs 13*N. Again, if you're only talking about Big-O complexity you sweep this under the rug. But in reality, this is a huge cost.
    - 11y ago