10 ms·

I don't think it's comparable to benchmark MDBM against LMDB or WiredTiger as keys are not kept in sorted order (no range queries), there is no support for tran

by hendzen 12y ago

I don't think it's comparable to benchmark MDBM against LMDB or WiredTiger as keys are not kept in sorted order (no range queries), there is no support for transactions, and MDBM does not offer durability in the event of power loss. MDBM is pretty much an optimized persistent hash table. LMDB and WiredTiger aim to be full-fledged ACID compliant database storage engines with functionality similar to that of BerkeleyDB or InnoDB.

justin66 12y ago
If you look at the MDBM page you'll notice that they currently benchmark against LevelDB, BerkeleyDB, and Kyoto Cabinet. What I was suggesting involves the same theme but better, newer competition. I agree that it's an apples to oranges comparison in any case.
- deleted 12y ago
  [deleted]
- beagle3 12y ago
  The timings they give there can only make sense on a fast SSD or when the database they benchmark on is completely cached. It's an apples-to-oranges comparison only of MDBM wins significantly against LMDB. If they are comparable in timing, or e.g. MDBM is 20% faster, then it would be an apples-to-apples comparison, MDBM having 20% speed advantage, and LMDB having every other possible advantage (memory safety, ACIDity, ordered retrieval, multiple databases, etc.) LMDB is truly, incredibly, really marvelous. On 64-bit it comes close to being the end-all-be-all local KV-store. If your databases are not more than a few tens of megs each, the same is true for 32-bit processors as well.
  - justin66 12y ago
    Yes, I am quite impressed by it as well.
  - rakoo 12y ago
    > If your databases are not more than a few tens of megs each, the same is true for 32-bit processors as well. Why is that ? Shouldn't 32-bit processors give you enough space in the range of hundreds of MiB ?
    - hyc_symas 12y ago
      Sure. But you only have 2-3GB of usable address space, and if your app has a lot of other variables to work with, there's not much space left over. I should note that in LMDB 1.0 we'll have dynamic unmapping and remapping, to allow 32-bit machines to work with larger DBs. (There's still a significant performance cost for this. It's only being done to allow folks to use the same code on 32 and 64.)
      - jetm9 12y ago
        Off-topic: will you have something like networked KV store aka redis. what do you think of Redis or Cassandra?
        hyc_symas 12y ago
        For redis, there's already ardb, ledisdb, redis-NDS, and a few other redis clones that support LMDB. We also already have memcacheDB on LMDB, as well as HyperDex with LMDB. I haven't looked closely at Cassandra since it's in java, and after I didn't find a simple backend plugin API I didn't look any further.
        jbooth 12y ago
        If you're interested in building a distributed DB on top of LMDB, I took care of part of the problem (replication/consistency) in my flotilla library at https://github.com/jbooth/flotilla https://github.com/jbooth/flotilla Basically I'm just layering the raft consistency algorithm on top of LMDB. Both systems single-thread write transactions for consistency, so there's some mechanical sympathy. Doesn't mandate any specific data model or even a client-server network transport, it's basically a replicated embedded DB. Anyone could build replicated redis on top of it or a Cassandra clone if they want to get into managing shards/rings. Sample app (still WIP) at https://github.com/jbooth/merchdb https://github.com/jbooth/merchdb
hyc_symas 12y ago
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/ 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/presentation/pillai 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.html http://www.openldap.org/lists/openldap-devel/200401/msg00077... )

by hendzen 12y ago

justin66 12y ago

If you look at the MDBM page you'll notice that they currently benchmark against LevelDB, BerkeleyDB, and Kyoto Cabinet. What I was suggesting involves the same theme but better, newer competition. I agree that it's an apples to oranges comparison in any case.

deleted 12y ago
[deleted]
beagle3 12y ago
The timings they give there can only make sense on a fast SSD or when the database they benchmark on is completely cached. It's an apples-to-oranges comparison only of MDBM wins significantly against LMDB. If they are comparable in timing, or e.g. MDBM is 20% faster, then it would be an apples-to-apples comparison, MDBM having 20% speed advantage, and LMDB having every other possible advantage (memory safety, ACIDity, ordered retrieval, multiple databases, etc.) LMDB is truly, incredibly, really marvelous. On 64-bit it comes close to being the end-all-be-all local KV-store. If your databases are not more than a few tens of megs each, the same is true for 32-bit processors as well.
- justin66 12y ago
  Yes, I am quite impressed by it as well.
- rakoo 12y ago
  > If your databases are not more than a few tens of megs each, the same is true for 32-bit processors as well. Why is that ? Shouldn't 32-bit processors give you enough space in the range of hundreds of MiB ?
  - hyc_symas 12y ago
    Sure. But you only have 2-3GB of usable address space, and if your app has a lot of other variables to work with, there's not much space left over. I should note that in LMDB 1.0 we'll have dynamic unmapping and remapping, to allow 32-bit machines to work with larger DBs. (There's still a significant performance cost for this. It's only being done to allow folks to use the same code on 32 and 64.)
    - jetm9 12y ago
      Off-topic: will you have something like networked KV store aka redis. what do you think of Redis or Cassandra?
      - hyc_symas 12y ago
        For redis, there's already ardb, ledisdb, redis-NDS, and a few other redis clones that support LMDB. We also already have memcacheDB on LMDB, as well as HyperDex with LMDB. I haven't looked closely at Cassandra since it's in java, and after I didn't find a simple backend plugin API I didn't look any further.
      - jbooth 12y ago
        If you're interested in building a distributed DB on top of LMDB, I took care of part of the problem (replication/consistency) in my flotilla library at https://github.com/jbooth/flotilla https://github.com/jbooth/flotilla Basically I'm just layering the raft consistency algorithm on top of LMDB. Both systems single-thread write transactions for consistency, so there's some mechanical sympathy. Doesn't mandate any specific data model or even a client-server network transport, it's basically a replicated embedded DB. Anyone could build replicated redis on top of it or a Cassandra clone if they want to get into managing shards/rings. Sample app (still WIP) at https://github.com/jbooth/merchdb https://github.com/jbooth/merchdb

hyc_symas 12y ago

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/ 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/presentation/pillai 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.html http://www.openldap.org/lists/openldap-devel/200401/msg00077... )