You make some good points. We benchmark LMDB against LevelDB and its derivatives even though none of the LevelDB family offer ACID transactions. (http://symas.com/mdb/ondisk/ ) Despite this fact, people will ask the question and try to make the comparison, so we run those tests. It's silly, but most people seem to pay attention to performance more than to safety/reliability.
From my totally biased perspective, MDBM is utter garbage. They use mmap but make absolutely zero effort to use it safely. This was the biggest obstacle to overcome in developing LMDB; I had a few lengthy conversations with the SleepyCat guys about it as well. It's the reason it took 2 years (from 2009 when we first started talking about it, to 2011 first code release) to get LMDB implemented. If you want to call something a "database" you have to do more than just mmap a file and start shoving data into it - you have to exert some kind of control over how and when the mapped data gets persisted to disk. Otherwise, if you just let the OS randomly flush things, you'll wind up with garbage. As Keith Bostic said to me (private email):
"The most significant problem with building an mmap'd back-end is implementing write-ahead-logging (WAL). (You probably know this, but just in case: the way databases usually guarantee consistency is by ensuring that log records describing each change are written to disk before their transaction commits, and before the database page that was changed. In other words, log record X must hit disk before the database page containing the change described by log record X.)
In Berkeley DB WAL is done by maintaining a relationship between the database pages and the log records. If a database page is being written to disk, there's a look-aside into the logging system to make sure the right log records have already been written. In a memory-mapped system, you would do this by locking modified pages into memory (mlock), and flushing them at specific times (msync), otherwise the VM might just push a database page with modifications to disk before its log record is written, and if you crash at that point it's all over but the screaming."
The harsh realities of working with mmap are what dictated LMDB's copy-on-write design - it's the only way to ensure consistency with an mmap without losing performance (due to multiple mlock/msync syscalls). None of these design considerations are evident in MDBM.
LMDB's mmap is read-only by default, because otherwise it's trivial to permanently corrupt a database by overwriting a record, writing past the end, etc. MDBM's mmap is read-write, and the only "protection" you get is a doc that tells you "be Vewwy vewwy careful!" Ridiculously sloppy.
Leaving reliability aside for a moment, there's also the issue of performance and efficiency. We used to use DBM-style hashes for the indexes in OpenLDAP, up to release 2.1. We abandoned them in favor of B-trees in OpenLDAP 2.2 because extensive benchmarking showed that BDB's B-trees were faster than its hash implementation at very large data sizes. The fundamental problem is that hash data structures are only fast when they are sparsely populated. When the number of data records you need to work with increases to fill the table, you start getting more and more hash collisions that result in lots of linear probes (or whatever other hash recovery strategy you're using). The other problem is that the very sparse/unordered nature of hashes makes them extremely cache unfriendly - you get zero locality-of-reference for groups of related queries. So as your data volumes increase, you get less and less benefit from the amount of RAM you have available. When the data exceeds the size of RAM, the number of disk seeks required for an arbitrary lookup is enormous, and every read is a random access. Using a hash for a large-scale data store is just horrible. (We tested this extensively a decade ago http://www.openldap.org/lists/openldap-devel/200401/msg00077... )
Hey, I've been working on a graph db-like thing as a hobby project for the last six months and I'm using LMDB as backend. I tried many alternatives (LevelDB, Sqlite4's LSM, BDB etc.) before settling on LMDB. The alternatives all had some quirk that stopped me from using them.
Among other things, I like that LMDB has zero-copy reads and that's something I've taken care to preserve all the way through my layers.
Just wanted to say thanks for the great work. LMDB is a joy to work with.
"We abandoned them in favor of B-trees in OpenLDAP 2.2 because extensive benchmarking showed that BDB's B-trees were faster than its hash implementation at very large data sizes."
Didn't bdb's linear hashing scheme extend the size of the hash table enough to keep it at the required loadfactor?
Thanks for the reply. Interesting that linear hashing had such a big effect, seeing as it is meant to be a slowly-occurring process that only happens when the average load factor of all buckets exceeds a threshold. I guess that was back in 2004 though. Wonder if the same performance is still applicable?
Sorry, I haven't kept up with sqlite4 development. I'm still on the sqlite-developers mailing list but I never see any traffic about it in particular.
I'm going to guess that they will not ship an LMDB driver right out of the gate. The one we were working on was not completed (our contractor flaked), and while I know they did some work on their own, I have no idea how complete that was either.
You pretty clearly haven't used MDBM because the MDBM I worked on at SGI (and still use to this day) gets to any key in two page faults (aka 2 disk seeks) at the most. That was the whole point of it.
If you want I'll go shove a few GB into an mdbm, drop caches, and time a lookup.
2 seeks at the most, are you talking about a 32 bit address space? The only way that's possible in 64 bits is to direct map a hash into e.g. 2 32 bit chunks and use the hash as an actual disk block address for the first chunk, and an index into a block list for the 2nd chunk.
2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
LevelDB is based on concepts from Google's BigTable database system. The tablet implementation for the BigTable system was developed starting in about 2004, and is based on a different Google internal code base than the LevelDB code.[1]
They probably release old tech after they have upgraded their own. So when they did their internal LevelDB 3.0 they released 1.0 as opensource. Probably do the same thing with all their releases (map-reduce,bigtable etc).
Comments
You make some good points. We benchmark LMDB against LevelDB and its derivatives even though none of the LevelDB family offer ACID transactions. (http://symas.com/mdb/ondisk/ ) Despite this fact, people will ask the question and try to make the comparison, so we run those tests. It's silly, but most people seem to pay attention to performance more than to safety/reliability.
From my totally biased perspective, MDBM is utter garbage. They use mmap but make absolutely zero effort to use it safely. This was the biggest obstacle to overcome in developing LMDB; I had a few lengthy conversations with the SleepyCat guys about it as well. It's the reason it took 2 years (from 2009 when we first started talking about it, to 2011 first code release) to get LMDB implemented. If you want to call something a "database" you have to do more than just mmap a file and start shoving data into it - you have to exert some kind of control over how and when the mapped data gets persisted to disk. Otherwise, if you just let the OS randomly flush things, you'll wind up with garbage. As Keith Bostic said to me (private email):
"The most significant problem with building an mmap'd back-end is implementing write-ahead-logging (WAL). (You probably know this, but just in case: the way databases usually guarantee consistency is by ensuring that log records describing each change are written to disk before their transaction commits, and before the database page that was changed. In other words, log record X must hit disk before the database page containing the change described by log record X.)
In Berkeley DB WAL is done by maintaining a relationship between the database pages and the log records. If a database page is being written to disk, there's a look-aside into the logging system to make sure the right log records have already been written. In a memory-mapped system, you would do this by locking modified pages into memory (mlock), and flushing them at specific times (msync), otherwise the VM might just push a database page with modifications to disk before its log record is written, and if you crash at that point it's all over but the screaming."
The harsh realities of working with mmap are what dictated LMDB's copy-on-write design - it's the only way to ensure consistency with an mmap without losing performance (due to multiple mlock/msync syscalls). None of these design considerations are evident in MDBM.
LMDB's mmap is read-only by default, because otherwise it's trivial to permanently corrupt a database by overwriting a record, writing past the end, etc. MDBM's mmap is read-write, and the only "protection" you get is a doc that tells you "be Vewwy vewwy careful!" Ridiculously sloppy.
LMDB's design and implementation are proven incorruptible. MDBM (and LevelDB and all its derivatives) are proven to be quite fragile. https://www.usenix.org/conference/osdi14/technical-sessions/...
Leaving reliability aside for a moment, there's also the issue of performance and efficiency. We used to use DBM-style hashes for the indexes in OpenLDAP, up to release 2.1. We abandoned them in favor of B-trees in OpenLDAP 2.2 because extensive benchmarking showed that BDB's B-trees were faster than its hash implementation at very large data sizes. The fundamental problem is that hash data structures are only fast when they are sparsely populated. When the number of data records you need to work with increases to fill the table, you start getting more and more hash collisions that result in lots of linear probes (or whatever other hash recovery strategy you're using). The other problem is that the very sparse/unordered nature of hashes makes them extremely cache unfriendly - you get zero locality-of-reference for groups of related queries. So as your data volumes increase, you get less and less benefit from the amount of RAM you have available. When the data exceeds the size of RAM, the number of disk seeks required for an arbitrary lookup is enormous, and every read is a random access. Using a hash for a large-scale data store is just horrible. (We tested this extensively a decade ago http://www.openldap.org/lists/openldap-devel/200401/msg00077... )
Hey, I've been working on a graph db-like thing as a hobby project for the last six months and I'm using LMDB as backend. I tried many alternatives (LevelDB, Sqlite4's LSM, BDB etc.) before settling on LMDB. The alternatives all had some quirk that stopped me from using them.
Among other things, I like that LMDB has zero-copy reads and that's something I've taken care to preserve all the way through my layers.
Just wanted to say thanks for the great work. LMDB is a joy to work with.
Great to hear that ;)
"We abandoned them in favor of B-trees in OpenLDAP 2.2 because extensive benchmarking showed that BDB's B-trees were faster than its hash implementation at very large data sizes."
Didn't bdb's linear hashing scheme extend the size of the hash table enough to keep it at the required loadfactor?
http://www.openldap.org/lists/openldap-devel/200401/msg00074...
Our experience with it shows that resizing was itself a very expensive operation.
Thanks for the reply. Interesting that linear hashing had such a big effect, seeing as it is meant to be a slowly-occurring process that only happens when the average load factor of all buckets exceeds a threshold. I guess that was back in 2004 though. Wonder if the same performance is still applicable?
Howard, since you're here and taking questions... :-)
Do you have any idea if a sqlite 4 release is imminent? Will lmdb work with it right out of the gate?
Thanks.
Sorry, I haven't kept up with sqlite4 development. I'm still on the sqlite-developers mailing list but I never see any traffic about it in particular.
I'm going to guess that they will not ship an LMDB driver right out of the gate. The one we were working on was not completed (our contractor flaked), and while I know they did some work on their own, I have no idea how complete that was either.
Thanks for your insight and the in-depth benchmarks you provide.
You're welcome ;)
The benchmarks are obviously for our own benefit too - until someone does these comparisons, none of us knows where things truly stand.
You pretty clearly haven't used MDBM because the MDBM I worked on at SGI (and still use to this day) gets to any key in two page faults (aka 2 disk seeks) at the most. That was the whole point of it.
If you want I'll go shove a few GB into an mdbm, drop caches, and time a lookup.
If you've already ported the levelDB benchmark driver, feel free to send it to me: https://github.com/hyc/leveldb/tree/benches/doc/bench
2 seeks at the most, are you talking about a 32 bit address space? The only way that's possible in 64 bits is to direct map a hash into e.g. 2 32 bit chunks and use the hash as an actual disk block address for the first chunk, and an index into a block list for the 2nd chunk.
2 seeks. Address space doesn't matter, you have one seek to read the directory (I'm assuming 100% cold cache), and one seek to get to the page in question.
Not only that, we watched the bus on an SGI Challenge and counted cache misses and TBL misses. 2 TBL misses to get a key.
Saying that it isn't possible on a 64 bit VM system makes no sense to me. If I have a 2TB file and I seek to location A and read it, then seek to location B and read it, you are saying that's not possible? Same thing with mmap, I set a pointer to the mapping, read p, p += <number>, read p. Two seeks, two page faults, whatever you want to call it, it does 2 and only 2 I/O's to get a key/value (unless the pages are bigger than disk blocks but then those are going to be sequential I/O's, no extra seeks).
I was actually thinking of a >2GB DB file on a 32 bit server. But leaving that aside, it sounds like you're assuming a perfect hash function with no collisions. If you have collisions, you have to deal with the possibility of a hash bucket overflowing and requiring an additional seek.
Anyway, I don't doubt that you can operate in 2 seeks in the normal case.
It is 2 seeks, at most, for 100% of lookups.
Care to share any details on the hashing scheme? Is it based on linear hashing, a la Litwin and Larson?
The hash is up to you, several are provided.
Isn't LevelDB a building block of Google's distributed file systems?
LevelDB is based on concepts from Google's BigTable database system. The tablet implementation for the BigTable system was developed starting in about 2004, and is based on a different Google internal code base than the LevelDB code.[1]
[1] http://en.wikipedia.org/wiki/LevelDB#History
They probably release old tech after they have upgraded their own. So when they did their internal LevelDB 3.0 they released 1.0 as opensource. Probably do the same thing with all their releases (map-reduce,bigtable etc).