3 ms·
LMDB is a COW tree but it is emphatically not an append-only tree. Append-only sucks, for all of the reasons already spelled out in the blog post. The write am
by hyc_symas 12y ago
LMDB is a COW tree but it is emphatically not an append-only tree. Append-only sucks, for all of the reasons already spelled out in the blog post.
The write amplification in LMDB is bounded by the height of the tree, so it's O(logN) with N=number of records. The write amplification in all WAL-based designs is O(N) where N=size of the records. With a 4K page size, to get a write amp of 64K in LMDB would require a tree depth of 16. At 100 bytes per record, 40 records per page, that would require 40^16 records, or 42949672960000000000000000 records. IMO your figure of 64K is vastly overestimated.
I've done more detailed investigation of write amplification in various DB engines here http://symas.com/mdb/ondisk/ http://symas.com/mdb/ondisk/ and you can see that the break-even point relative to WAL-based engines is around record size of 2KB. Above that size LMDB has lower write-amp than WAL-based approaches. Coincidentally (hah) LDAP entries tend to be >= 2KB in size.
But most importantly for real-time services - LMDB write latency is tightly bounded, and never suffers from stop-the-world compaction pauses. This was a design requirement from day 1. (See section 3.2 of the 2011 LMDB design paper http://symas.com/mdb/20111010LDAPCon%20MDB.pdf http://symas.com/mdb/20111010LDAPCon%20MDB.pdf ) E.g., see the comparison of write latency in LMDB vs HyperLevelDB here http://symas.com/mdb/hyperdex/#100M http://symas.com/mdb/hyperdex/#100M - we can reliably compute/predict LMDB's I/O latency and our prediction perfectly matches the real world results - 33ms avg latency on a disk with 16ms avg seek time. You cannot do that with any of the other DB engines.
- eloff 12y agoSorry, I got my terminology muddled. IIRC LMDB is similar to append only trees, except it puts obsolete pages into a free list (also a LMDB tree?) and will reuse them when it reaches the end of the file? And my math is way off for 100 byte records, laughably so. Don't get me wrong though, I needed an example of write amplification caused by COW that happens in append only trees, LMDB is a great database, and for the use case it was designed for, large records and read heavy workload, it has no peer.
- hyc_symas 12y ago> and will reuse them when it reaches the end of the file? You were right up till that - it reuses pages as soon as they are safe to reuse, not waiting to get to the end of the file. Anyway, yes, write amplification is a significant factor, in any DB design.
- eloff 12y agoWhile I have your attention, assuming SSD with typical 128k erase blocks, do you do anything special to avoid write amplification at the disk level when reusing pages? My understanding is that those are in-place updates from the filesystem's POV, so writing over 32k of old pages will cause 128-256k actual writes. One could avoid this somewhat with trim support, fallocate + hole punch (not portable) but you have to think carefully about alignments and grouping free pages into contiguous erase block multiples. That never struck me as being very practical. Have you thought about that problem before or tried anything there?
- hyc_symas 12y agoThought about it - yes. Tried anything - no. We have no idea what an SSD's FTL is doing under the covers, and no way to find out thru a SATA/SCSI command interface. Trim and hole punching are no advantage - it's not safe to do them before a page may be safely reused, as soon as a page can be safely reused, we'll probably be writing new data into it.
- databass 12y agoDo you also have stats on the high percentile latencies, besides the average? Sounds like your avoidance of compaction pauses ought to lead to lower latency at the high percentiles.
- hyc_symas 12y agoSee the table of data here http://symas.com/mdb/hyperdex/#100M http://symas.com/mdb/hyperdex/#100M 100M records, 1M ops MinLatency(us) AvgLatency(us) 95th%ile(ms) 99th%ile(ms) MaxLatency(ms) Runtime(sec) Throughput(ops/sec) CPUtime (mm:ss) LMDB update 256 33565 130 209 637 8385 119 4:21.41 LMDB read 215 33493 130 207 817 LevelDB update 241 63660 231 385 20370 15863 63 17:27 LevelDB read 188 63250 230 383 7904 (It's formatted properly if you follow the link) Also look at the latency distribution compared to MySQL's InnoDB http://symas.com/mdb/memcache/ http://symas.com/mdb/memcache/