3 ms·
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 siz
by 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 agoYour 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.