5 ms·

LSM trees have all kinds of tricks to make reads fast too, like Bloom filters to rule out levels that don't have the key. RocksDB, an LSM, powers what is probab

by ot 5y ago

LSM trees have all kinds of tricks to make reads fast too, like Bloom filters to rule out levels that don't have the key. RocksDB, an LSM, powers what is probably the largest MySQL deployment in the world, for OLTP workloads [1] The real killer feature is not write efficiency, but the sequential write pattern, as opposed to the small random writes used by B-trees. On flash, this makes a significant difference for endurance. EDIT: And I forgot to mention that it is a lot easier to do compression on immutable data structures (SSTables) than on mutable ones, so LSMs are generally more space-efficient too. [1] https://vldb.org/pvldb/vol13/p3217-matsunobu.pdf https://vldb.org/pvldb/vol13/p3217-matsunobu.pdf

saurik 5y ago
Every time I look into it though these tricks aren't making reads truly fast, they are just mitigating the impacts of LSM trees to the extent to which is possible, but a B-Tree are still in the end both better for reads and not even that much worse than writes (due to the write amplification from LSM trees; with B-trees this is only an issue if you are making truly random writes, which I believe is the worst case for LSM trees anyway).
- ot 5y ago
  If you're not doing random writes (that is, random keys) an LSM has no write amplification, it essentially becomes a sorted list of SSTables. I can't think of any OLTP application where the writes are not random (in the sense of relative position in the key space). Either your primary keys are, or at least all your indexes are. Write amplification is not an issue if sequential writes are orders of magnitude faster than random writes, which is usually the case, so even with that LSMs come out ahead. Also if your application is read-heavy, you can tune the LSM parameters to have fewer levels (at the cost of more compaction traffic). With B-trees, you have to chase a fixed depth of log_{page size}.
- kragen 5y ago
  What do you mean by "the worst case for LSM trees"? I guess you could merge two index segments (SSTables, in Google-derived implementations) faster if their key ranges don't overlap, because you could just concatenate them without encoding and decoding their entire contents, but does anybody actually do that? LSM trees are a lot faster than B+trees with lots of random writes. In a by-the-book B+tree implementation that doesn't allow MVCC, if your branching factor is 1024, your table is 256 gigabytes, and your records are 128 bytes, most random record writes require updating four tree nodes, the transaction log, and the actual record page, which would be six random seeks without a writeback cache, and probably three random seeks with a writeback cache. I think in practice on modern SSDs this means three 4-KiB blocks added to the FTL's transaction log, but without further write amplification I think that fragments the FTL's storage so that reading a tree node requires multiple random page reads instead of one. If you use a log-structured B-tree approach so MVCC is convenient, you probably want to use a lower branching factor; say you use 128. Now your tree is 5 levels of internal nodes deep, and each node is, say, 2 KiB of data, so you're appending 10 KiB of tree data to the write log for each random write, plus the 128-byte record. By contrast, with an LSM-tree, at the moment of commit, you just append the 128-byte updated record, perhaps after an in-RAM sort: 80 times less data. But if the data survives long enough, it eventually has to get merged up to the root through a series of merges, which involves reading it and writing it an additional logarithmic number of times. Say your merges are 8-way on average; in that case the data has to get read and written 11 more times before the table is a single 256-megabyte segment. That's still 7 times faster than the log-structured B-tree approach. The difference gets bigger with spinning rust. And that's why, on one machine I tested on, LevelDB could insert 300'000 key-value pairs per second while Postgres manages about 3000 and SQLite about 17000.
  - saurik 5y ago
    > What do you mean by "the worst case for LSM trees"? For write amplification. > If you use a log-structured B-tree approach so MVCC is convenient... You just hamstrung your B-tree for conscience to implement a single model, but regardless: I never claimed that B-trees were faster at writes than LSM-trees. I instead claimed that I don't understand where all of these write-dominated use cases are coming from as the world seems to be full of read-dominated services. > And that's why, on one machine I tested on, LevelDB could insert 300'000 key-value pairs per second while Postgres manages about 3000 and SQLite about 17000. I mean, this is clearly an unfair comparison by your own math: you need to keep running this for a long enough time that you can amortize into your calculations the cost of compactions (for LevelDB) and vacuums (PostgreSQL).
    - jeffffff 5y ago
      i don't think that's an unfair comparison, that is in line with similar tests i have performed for random write workloads on lsm trees and b trees that don't fit in ram, including cost of compaction. https://youtu.be/jwq_0mPNnN8?t=3730 https://youtu.be/jwq_0mPNnN8?t=3730 links to a section of a talk i did which explains my benchmarks. it also includes some pretty neat visualizations of the write patterns of the two data structures that may help people understand why there is such a big difference in write throughput. my benchmarks were done on spinning disk, on ssds i'd expect lsm trees to only have around 10x higher write throughput for the same benchmark.
    - kragen 5y ago
      Aha, thanks. I suppose that in theory you could avoid actual merging if you had disjoint key ranges, in which case random writes could conceivably have less write amplification than mostly sequential writes, but does anyone do that in practice? Does it make a difference in practice? What do you mean by "You just hamstrung your B-tree for conscience to implement a single model"? I'm not sure what you mean by either "for conscience" or "to implement a single model". It's probably not an extremely fair comparison, but I'm not sure which databases it's slanted in favor of, and it wouldn't be very surprising if I'd overlooked some easy speedup. Like, maybe by deferring index creation until after ETL you could get a significant boost in Postgres speed, or by changing the Postgres tuning numbers. I do think it was running long enough to incur a significant number of compactions and vacuums, though. Feel free to critique in more detail. The Postgres and SQLite numbers come from http://canonical.org/~kragen/sw/dev3/exampledb.py http://canonical.org/~kragen/sw/dev3/exampledb.py, but for LevelDB I inferred that the Python bindings were the bottleneck, so the 300'000 figure is from http://canonical.org/~kragen/sw/dev3/leveldb-62m.cc http://canonical.org/~kragen/sw/dev3/leveldb-62m.cc.
- thesz 5y ago
  If you have an SQL table with a couple of indices, you have B-tree with random inserts/updates. For truly random data such as scale free graphs, B-tree shows quite non-linear performance decline, as if somehow it started to have O(N^2) operation cost instead of O(NlogN). LSM, on the other hand, worked very well there.
bob1029 5y ago
> The real killer feature is not write efficiency, but the sequential write pattern, as opposed to the small random writes used by B-trees. On flash, this makes a significant difference for endurance. Sequential writes with some degree of batching requests can add orders of magnitude to system throughput. I use a ringbuffer abstraction to serialize my writers and handle batches of up to 4096 transactions at a time. Everything in the batch gets compressed and written as 1 chunk to an append-only log. The benefits of processing multiple requests at a time are very hard to overstate. Saturating the write performance of virtually any storage device is trivial with this approach. It also carries back to magnetic storage really well, and even tape if you were so inclined to go down that path.
- ot 5y ago
  The batching comes implicitly in LSMs: for the WAL, the writes are committed only when the WAL is synced, so the amount of batching is user-controlled. When writing SSTables (either from memtables or from compaction) the write sizes are controlled by the write buffer size.
  - bob1029 5y ago
    In these systems you propose, is it possible to store multiple logical transactions per IO operation? My batching approach allows me to say things like "business operations per disk IO" (a positive integer greater than 1 in many cases). To get a better idea - Assume a 4K block size, and 128-byte size for some business type. You can hypothetically store 32 of these per physical write if you have perfect batching going on. Looking at a Samsung 960 which has ~2.1GB/s sequential write speed (which is approximately our use case), you would be able to persist ~16.4 million transactions per second in the most ideal scenario. This is extremely notable, because the maximum stated random write throughput for this device at QD32 w/ 4k block size is only ~440kops/s. Mix in even the most pedestrian of compression algorithms, and this 16m turns into an even more ridiculous figure assuming your transactions look somewhat similar to each other, the system is fully loaded, and the planets are appropriately aligned. These circumstances might sound extreme, but they are fairly common in areas like fintech where you might need to match millions of orders in ~1 second and its non-stop like this for hours. I am not aware of how the LSM+WAL would meet the objectives I have laid out above - Most notably the implication that the disk is being touched multiple times per business transaction. Please correct me if I am mistaken in this regard. My solution ensures that the disk is touched <= 1 time per logical write (where the size of the write is bounded by the block size of the device).

by ot 5y ago

saurik 5y ago

Every time I look into it though these tricks aren't making reads truly fast, they are just mitigating the impacts of LSM trees to the extent to which is possible, but a B-Tree are still in the end both better for reads and not even that much worse than writes (due to the write amplification from LSM trees; with B-trees this is only an issue if you are making truly random writes, which I believe is the worst case for LSM trees anyway).

ot 5y ago
If you're not doing random writes (that is, random keys) an LSM has no write amplification, it essentially becomes a sorted list of SSTables. I can't think of any OLTP application where the writes are not random (in the sense of relative position in the key space). Either your primary keys are, or at least all your indexes are. Write amplification is not an issue if sequential writes are orders of magnitude faster than random writes, which is usually the case, so even with that LSMs come out ahead. Also if your application is read-heavy, you can tune the LSM parameters to have fewer levels (at the cost of more compaction traffic). With B-trees, you have to chase a fixed depth of log_{page size}.
kragen 5y ago
What do you mean by "the worst case for LSM trees"? I guess you could merge two index segments (SSTables, in Google-derived implementations) faster if their key ranges don't overlap, because you could just concatenate them without encoding and decoding their entire contents, but does anybody actually do that? LSM trees are a lot faster than B+trees with lots of random writes. In a by-the-book B+tree implementation that doesn't allow MVCC, if your branching factor is 1024, your table is 256 gigabytes, and your records are 128 bytes, most random record writes require updating four tree nodes, the transaction log, and the actual record page, which would be six random seeks without a writeback cache, and probably three random seeks with a writeback cache. I think in practice on modern SSDs this means three 4-KiB blocks added to the FTL's transaction log, but without further write amplification I think that fragments the FTL's storage so that reading a tree node requires multiple random page reads instead of one. If you use a log-structured B-tree approach so MVCC is convenient, you probably want to use a lower branching factor; say you use 128. Now your tree is 5 levels of internal nodes deep, and each node is, say, 2 KiB of data, so you're appending 10 KiB of tree data to the write log for each random write, plus the 128-byte record. By contrast, with an LSM-tree, at the moment of commit, you just append the 128-byte updated record, perhaps after an in-RAM sort: 80 times less data. But if the data survives long enough, it eventually has to get merged up to the root through a series of merges, which involves reading it and writing it an additional logarithmic number of times. Say your merges are 8-way on average; in that case the data has to get read and written 11 more times before the table is a single 256-megabyte segment. That's still 7 times faster than the log-structured B-tree approach. The difference gets bigger with spinning rust. And that's why, on one machine I tested on, LevelDB could insert 300'000 key-value pairs per second while Postgres manages about 3000 and SQLite about 17000.
- saurik 5y ago
  > What do you mean by "the worst case for LSM trees"? For write amplification. > If you use a log-structured B-tree approach so MVCC is convenient... You just hamstrung your B-tree for conscience to implement a single model, but regardless: I never claimed that B-trees were faster at writes than LSM-trees. I instead claimed that I don't understand where all of these write-dominated use cases are coming from as the world seems to be full of read-dominated services. > And that's why, on one machine I tested on, LevelDB could insert 300'000 key-value pairs per second while Postgres manages about 3000 and SQLite about 17000. I mean, this is clearly an unfair comparison by your own math: you need to keep running this for a long enough time that you can amortize into your calculations the cost of compactions (for LevelDB) and vacuums (PostgreSQL).
  - jeffffff 5y ago
    i don't think that's an unfair comparison, that is in line with similar tests i have performed for random write workloads on lsm trees and b trees that don't fit in ram, including cost of compaction. https://youtu.be/jwq_0mPNnN8?t=3730 https://youtu.be/jwq_0mPNnN8?t=3730 links to a section of a talk i did which explains my benchmarks. it also includes some pretty neat visualizations of the write patterns of the two data structures that may help people understand why there is such a big difference in write throughput. my benchmarks were done on spinning disk, on ssds i'd expect lsm trees to only have around 10x higher write throughput for the same benchmark.
  - kragen 5y ago
    Aha, thanks. I suppose that in theory you could avoid actual merging if you had disjoint key ranges, in which case random writes could conceivably have less write amplification than mostly sequential writes, but does anyone do that in practice? Does it make a difference in practice? What do you mean by "You just hamstrung your B-tree for conscience to implement a single model"? I'm not sure what you mean by either "for conscience" or "to implement a single model". It's probably not an extremely fair comparison, but I'm not sure which databases it's slanted in favor of, and it wouldn't be very surprising if I'd overlooked some easy speedup. Like, maybe by deferring index creation until after ETL you could get a significant boost in Postgres speed, or by changing the Postgres tuning numbers. I do think it was running long enough to incur a significant number of compactions and vacuums, though. Feel free to critique in more detail. The Postgres and SQLite numbers come from http://canonical.org/~kragen/sw/dev3/exampledb.py http://canonical.org/~kragen/sw/dev3/exampledb.py, but for LevelDB I inferred that the Python bindings were the bottleneck, so the 300'000 figure is from http://canonical.org/~kragen/sw/dev3/leveldb-62m.cc http://canonical.org/~kragen/sw/dev3/leveldb-62m.cc.
thesz 5y ago
If you have an SQL table with a couple of indices, you have B-tree with random inserts/updates. For truly random data such as scale free graphs, B-tree shows quite non-linear performance decline, as if somehow it started to have O(N^2) operation cost instead of O(NlogN). LSM, on the other hand, worked very well there.

bob1029 5y ago

> The real killer feature is not write efficiency, but the sequential write pattern, as opposed to the small random writes used by B-trees. On flash, this makes a significant difference for endurance. Sequential writes with some degree of batching requests can add orders of magnitude to system throughput. I use a ringbuffer abstraction to serialize my writers and handle batches of up to 4096 transactions at a time. Everything in the batch gets compressed and written as 1 chunk to an append-only log. The benefits of processing multiple requests at a time are very hard to overstate. Saturating the write performance of virtually any storage device is trivial with this approach. It also carries back to magnetic storage really well, and even tape if you were so inclined to go down that path.

ot 5y ago
The batching comes implicitly in LSMs: for the WAL, the writes are committed only when the WAL is synced, so the amount of batching is user-controlled. When writing SSTables (either from memtables or from compaction) the write sizes are controlled by the write buffer size.
- bob1029 5y ago
  In these systems you propose, is it possible to store multiple logical transactions per IO operation? My batching approach allows me to say things like "business operations per disk IO" (a positive integer greater than 1 in many cases). To get a better idea - Assume a 4K block size, and 128-byte size for some business type. You can hypothetically store 32 of these per physical write if you have perfect batching going on. Looking at a Samsung 960 which has ~2.1GB/s sequential write speed (which is approximately our use case), you would be able to persist ~16.4 million transactions per second in the most ideal scenario. This is extremely notable, because the maximum stated random write throughput for this device at QD32 w/ 4k block size is only ~440kops/s. Mix in even the most pedestrian of compression algorithms, and this 16m turns into an even more ridiculous figure assuming your transactions look somewhat similar to each other, the system is fully loaded, and the planets are appropriately aligned. These circumstances might sound extreme, but they are fairly common in areas like fintech where you might need to match millions of orders in ~1 second and its non-stop like this for hours. I am not aware of how the LSM+WAL would meet the objectives I have laid out above - Most notably the implication that the disk is being touched multiple times per business transaction. Please correct me if I am mistaken in this regard. My solution ensures that the disk is touched <= 1 time per logical write (where the size of the write is bounded by the block size of the device).