8 ms·
Immutability, MVCC, and garbage collection (2013)
- eloff 12y agoI've been developing high performance databases for the last five years off and on. This article is right on the money. It's tough to beat MVCC for a database that wants isolated concurrent transactions. Append only designs seem attractive, but they don't actually help much with write throughput on SSDs (but avoiding in-place updates does, due to erase blocks.) And they often require writing much more information. E.g. writing 100 bytes in LMDB, which is an append only btree, requires copying all pages from the root to the leaf and writing them all out, typically 64k or more. Writing 100 bytes to a transaction log or WAL costs about 100 bytes. There's a huge write amplification going on.
- reitzensteinm 12y agoI don't doubt that immutability in databases is expensive, but is anyone really arguing against that? The article seems like a straw man to me. From watching Rich's talks on Datomic, the argument seems to be that for many problem domains, we can spend the cost of immutability to get a much nicer development environment. If you're already sharding your DBs in a frantic effort to keep your web startup scaling, obviously switching to an immutable database is a bad idea. But if you can fit every transaction your company has ever done in memory, why wouldn't you go append only? While the latter might be a niche market today, if Moore's Law keeps up for another few decades it'll be the common case. I'm not clicking on more links than I was 15 years ago, but I've got three orders of magnitude more memory.
- taeric 12y agoMany of the arguments in favor of newer databases are about how much simpler these append only data structures make both storing and reasoning about things. The point of this article seems to be that this is neither absolutely true, nor new.
- hyc_symas 12y agoAgreed. None of the ideas are new, and append-only doesn't make life easier.
- jasonwatkinspdx 12y agoIt's important to understand LMDB is an edge case design that wants the fastest reads possible and is willing to significantly burden the write path in that interest. Immutability is still a powerful approach. For a good example read the MSR papers on the hekaton main memory engine's approach: http://research.microsoft.com/apps/pubs/default.aspx?id=178758 http://research.microsoft.com/apps/pubs/default.aspx?id=1787... The original post isn't exactly wrong, it's just something of a straw man. We live in an era of terabyte disks. Cold data storage is cheap.
- hyc_symas 12y agoLMDB 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.
- brandonbloom 12y agoThis article was discussed previously. In short, it's based on numerous false assumptions. For example, Datomic is not based on an append-only B tree. It utilizes persistent data structures instead. Here's Rich's comment: https://news.ycombinator.com/item?id=7011102 https://news.ycombinator.com/item?id=7011102
- taeric 12y agoI'm curious to know what the actual data structure is. Also, it should be noted that "append only b-tree" gives a lot of leeway in how something is actually implemented. That is as easily seen as a family of data structures as it is a specific one. (Not to mention "it uses persistent data structures instead of append-only B tree" is a somewhat silly statement. As append-only B tree is persistent.) And there is something amusing about using git as an example of how there is no technical argument against losing information. Because, losing information is a specific feature that was added to git. (Look up shallow clones.) I can accept that there is no technical reason to have this, actually. But there are pragmatic reasons to have it. Which is basically the point of this article.
- brandonbloom 12y ago> I'm curious to know what the actual data structure is. This tweet from Rich provides the missing puzzle pieces: "The log is not a btree - used for durability, not query. Separate indexes combine memory with batch-updated storage." https://twitter.com/richhickey/status/420910382538948608 https://twitter.com/richhickey/status/420910382538948608 Restating in my own words: The transaction log is essentially just a stream of asserts and retracts with metadata. That's used for durability first and echoed to clients/peers and the indexing engine. The indexing engine asynchronously batch updates indexes (which probably are b-trees, but have no need to be streaming append-only style in this context). The peers query a joined dataset of the latest consistent indexes plus the set of unindexed transactions. > As append-only B tree is persistent. You're right, it can be. However, the popular append-only b-tree systems (such as CouchDB) are actually append-only B+-tree systems. That "+" means the leaves of the tree are intrusively linked together, and so are not persistent. You can not "fork" such trees cheaply. > losing information is a specific feature that was added to git http://blog.datomic.com/2013/05/excision.html http://blog.datomic.com/2013/05/excision.html
- daemonk 12y agoIs this a case of right tools for the right job? Are there special cases where immutability is superior?
- juliangregorian 12y agoOn the RethinkDB thread yesterday there seemed to be a popular misconception that MVCC provides rewindable versioning capabilities -- it does not. Good to see this article getting some traction.
- hyc_symas 12y agoMany MVCC systems can. I personally have never had a reason to want to.
- juliangregorian 12y agoSure, but it's not due to implementing MVCC. And, as the article illustrates, that type of optimistic approach doesn't come for free.