3 ms·

I don't understand his claim that B-tree write amplification is O(1). If I want to write one key to a B-tree, I only have to write O(1) nodes (amortized), but e

by jbapple 11y ago

I don't understand his claim that B-tree write amplification is O(1). If I want to write one key to a B-tree, I only have to write O(1) nodes (amortized), but each node is presumably of size B >> 1, right?

hyc_symas 11y ago
That's irrelevant. The point is that whether your record is 1 byte or 1000 bytes, you still write only 1 node. In an LSM, the write amplification is a large multiple of your record size.
- btrask 11y ago
  In b-trees, there is an inherent tension in choosing a page size (or base). Larger pages are good for reads because of the higher branching factor (which is why we don't use binary trees). Smaller pages are good for random writes because you're rewriting less. This is why Tokutek claims their fractal trees are faster for reads than b-trees, because they can use larger pages without killing write performance.
  - hyc_symas 11y ago
    Tokutek makes a lot of claims but none of their code demonstrates any advantage. Since their algorithm is patented I've avoided reading it in depth. But assuming there's a "there" there, clearly their implementation of it sucks. When your code needs 2x RAM as the actual data volume to operate, you've failed as a database. I'm inclined to believe there's no "there" there.
- jbapple 11y ago
  Assume a very simple LSM with one run per level and an expansion factor of 2. Call the block size B and the key size k. The first two levels have one run of size B, and each level thereafter has one run twice the size of the one from the previous level. For n records, there are nk/B blocks on disk and ceil(lg (nk/B)) + 1 levels, at most, in the database. Every insert writes one of levels 1 or 2. One out of every 2B/k writes also rewrites level 3, at a cost of 2 block writes. This adds an amortized cost of k/B block writes. One out of every 4B/k writes also rewrites level 4, at a cost of 4 block writes. This, again, adds an amortized cost of k/B block writes. This continues until we are out of levels. Since there are ceil(lg (nk/B)) + 1 levels (at most), the amortized cost of an insert is at most 1 + (k/B)(ceil(lg (nk/B)) + 1 - 1) block writes. For a block size of 4096 bytes, a key size of 32 bytes, and n = 2^30, this 1.18 block writes per insert. If k = 256 and n = 2^40, this is 3.25 block writes per insert. Is my math wrong?
  - hyc_symas 11y ago
    Your math is unrealistic. You are tossing around theoretical numbers, which are meaningless for an actual implementation. Assume you have actually implemented this very simple LSM. Is it reliable? i.e., are you using ARIES WAL? If so, then every insert has an additional cost of at least k for the log record. Are you using a raw block device, or are you using a filesystem? If a filesystem, then every insert has additional costs for metadata updates, and these costs are some multiple of the block size, not the key size. If using a filesystem, every "rewrite" of a level includes multiple metadata updates to empty/delete existing files and create/allocate new files. If not using a filesystem, then you must somehow manage metadata about the existence and size of your multiple levels yourself, as well as a space mapping of the raw block device. A B+tree gets most of that for free because it uses a single file, so the amount of filesystem-level metadata updating is minimal.

by jbapple 11y ago

hyc_symas 11y ago

That's irrelevant. The point is that whether your record is 1 byte or 1000 bytes, you still write only 1 node. In an LSM, the write amplification is a large multiple of your record size.

btrask 11y ago
In b-trees, there is an inherent tension in choosing a page size (or base). Larger pages are good for reads because of the higher branching factor (which is why we don't use binary trees). Smaller pages are good for random writes because you're rewriting less. This is why Tokutek claims their fractal trees are faster for reads than b-trees, because they can use larger pages without killing write performance.
- hyc_symas 11y ago
  Tokutek makes a lot of claims but none of their code demonstrates any advantage. Since their algorithm is patented I've avoided reading it in depth. But assuming there's a "there" there, clearly their implementation of it sucks. When your code needs 2x RAM as the actual data volume to operate, you've failed as a database. I'm inclined to believe there's no "there" there.
jbapple 11y ago
Assume a very simple LSM with one run per level and an expansion factor of 2. Call the block size B and the key size k. The first two levels have one run of size B, and each level thereafter has one run twice the size of the one from the previous level. For n records, there are nk/B blocks on disk and ceil(lg (nk/B)) + 1 levels, at most, in the database. Every insert writes one of levels 1 or 2. One out of every 2B/k writes also rewrites level 3, at a cost of 2 block writes. This adds an amortized cost of k/B block writes. One out of every 4B/k writes also rewrites level 4, at a cost of 4 block writes. This, again, adds an amortized cost of k/B block writes. This continues until we are out of levels. Since there are ceil(lg (nk/B)) + 1 levels (at most), the amortized cost of an insert is at most 1 + (k/B)(ceil(lg (nk/B)) + 1 - 1) block writes. For a block size of 4096 bytes, a key size of 32 bytes, and n = 2^30, this 1.18 block writes per insert. If k = 256 and n = 2^40, this is 3.25 block writes per insert. Is my math wrong?
- hyc_symas 11y ago
  Your math is unrealistic. You are tossing around theoretical numbers, which are meaningless for an actual implementation. Assume you have actually implemented this very simple LSM. Is it reliable? i.e., are you using ARIES WAL? If so, then every insert has an additional cost of at least k for the log record. Are you using a raw block device, or are you using a filesystem? If a filesystem, then every insert has additional costs for metadata updates, and these costs are some multiple of the block size, not the key size. If using a filesystem, every "rewrite" of a level includes multiple metadata updates to empty/delete existing files and create/allocate new files. If not using a filesystem, then you must somehow manage metadata about the existence and size of your multiple levels yourself, as well as a space mapping of the raw block device. A B+tree gets most of that for free because it uses a single file, so the amount of filesystem-level metadata updating is minimal.