16 ms·

I'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 t

by eloff 12y ago

I'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 ago
I 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 ago
  Many 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 ago
    Agreed. None of the ideas are new, and append-only doesn't make life easier.
jasonwatkinspdx 12y ago
It'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 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 ago
  Sorry, 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.

by eloff 12y ago

reitzensteinm 12y ago

I 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 ago
Many 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 ago
  Agreed. None of the ideas are new, and append-only doesn't make life easier.

jasonwatkinspdx 12y ago

It'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 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 ago
Sorry, 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.