Hello,
I have read the - very interesting - performance comparison http://symas.com/mdb/microbench/
I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.html
FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log.
Thanks,
Tobias
Tobias Oberstein wrote:
Hello,
I have read the - very interesting - performance comparison http://symas.com/mdb/microbench/
I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.html
FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log.
OK, like LMDB it uses shadow root pages. I think the similarity ends there. It is a relational database with an ASCII query language, while LMDB is strictly a key/value store. That automatically means for simple get/put operations LMDB will be orders of magnitude faster (just as it is so much faster than SQLite3 and SQLite4).
It makes the flawed assumption that many main-memory databases do, that all RAM is the same speed. It uses T-trees as its underlying data structure. LMDB uses B+trees because time and again research shows that B+trees are more efficient, even when all of the data fits into main memory. This is the same mistake the MemSQL guys make, as well as MySQL NDBCluster.
See these papers, for example: http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html http://www.vldb.org/dblp/db/conf/vldb/RaoR99.html
The reality is that computer architectures are hierarchical in nature. A CPU has L1, L2, and possibly L3 cache, each of which is progressively slower than the previous. Then it gets to local RAM, which is slower still. Then in a multiprocessor machine, there is NUMA, memory residing on remote nodes, which is again slower still. B+trees are inherently hierarchical and naturally suited to the reality of system design. All other approaches, including the recently popular LSM trees (as used in e.g. Google LevelDB, SQLite4, and various other recent databases) are all inherently inferior because of this fundamental fact of computer architecture.
FastDB also appears to use locking, while LMDB is MVCC and readers require no locks, so even with all of the other disadvantages out of the way, LMDB will scale better across multiple CPUs.
FastDB is also written in C++ which is another inherent disadvantage compared to LMDB which is pure C.
You could adapt the LevelDB microbenchmarks to test it but ultimately I believe it would be a waste of time.
On Thu, Mar 21, 2013 at 9:58 PM, Howard Chu hyc@symas.com wrote:
Tobias Oberstein wrote:
Hello,
I have read the - very interesting - performance comparison http://symas.com/mdb/**microbench/ http://symas.com/mdb/microbench/
I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.**htmlhttp://www.garret.ru/fastdb.html
FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log.
OK, like LMDB it uses shadow root pages. I think the similarity ends there. It is a relational database with an ASCII query language, while LMDB is strictly a key/value store. That automatically means for simple get/put operations LMDB will be orders of magnitude faster (just as it is so much faster than SQLite3 and SQLite4).
I Not being so young, these considerations remind me of the same arguments that there was about hierarchical DBMS and the relational one. I do not mean that there are not still real, but just to tell that we are talking about topic 20 years old. Isn't it ?
Best Regards
devzero2000 wrote:
On Thu, Mar 21, 2013 at 9:58 PM, Howard Chu <hyc@symas.com mailto:hyc@symas.com> wrote:
Tobias Oberstein wrote: Hello, I have read the - very interesting - performance comparison http://symas.com/mdb/__microbench/ <http://symas.com/mdb/microbench/> I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.__html <http://www.garret.ru/fastdb.html> FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log. OK, like LMDB it uses shadow root pages. I think the similarity ends there. It is a relational database with an ASCII query language, while LMDB is strictly a key/value store. That automatically means for simple get/put operations LMDB will be orders of magnitude faster (just as it is so much faster than SQLite3 and SQLite4).I Not being so young, these considerations remind me of the same arguments that there was about hierarchical DBMS and the relational one. I do not mean that there are not still real, but just to tell that we are talking about topic 20 years old. Isn't it ?
In some ways yes. Because it seems today's crop of NoSQL programmers haven't studied and learned from the lessons of 30+ years ago.
Sure there's a time and a place for a relational database. And LMDB actually supports them - there's an LMDB backend for SQLite3, there will be one for SQLite4 and MariaDB as well.
One of the other important lessons of software design that a lot of the NoSQL folks seem to have missed is having a good abstraction layer between your frontend query handler and your backend storage engine. SQLite4 and MariaDB don't make this mistake. SQLite3 does, and porting LMDB to it was a royal pain. Also the SQLite3 test suite doesn't pass because many of the tests assume they know the actual binary format of the on-disk files. Tightly marrying your data storage engine like this is always a mistake. It's the same mistake MongoDB and CouchBase makes. OpenLDAP slapd has been so flexible precisely because we've always maintained a distinction between the frontend and the backend, which has allowed us to easily experiment with multiple backend technologies over the years.
Another mistake most of these folks make is using high level languages and slow APIs and ASCII query languages. They believe the BS that Intel has been shoveling for the past couple decades, that CPUs are always faster so there's no point in worrying about the CPU cost of an individual function. But reality is that CPU speeds have maxed out, and CPU power is only increasing by virtue of multi-core expansion. Also they assume that network speeds are so fast today that inefficient codings don't matter. Reality is that the fastest growing segment of data consumption today is mobile computing, and most devices are connected to networks delivering 2G speed. Even the deployed 3G and 4G networks seldom deliver their rated speeds, nor can they hope to do so in congested/heavily populated locations.
Efficiency always matters. Bloat is always wrong.
Am 21.03.2013 21:58, schrieb Howard Chu:
Tobias Oberstein wrote:
Hello,
I have read the - very interesting - performance comparison http://symas.com/mdb/microbench/
I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.html
FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log.
OK, like LMDB it uses shadow root pages. I think the similarity ends there.
Ah. Ok.
It is a relational database with an ASCII query language, while LMDB is strictly a key/value store. That automatically means for simple get/put operations LMDB will be orders of magnitude faster (just as it is so much faster than SQLite3 and SQLite4).
Mmh. The overhead of parsing a "SELECT value FROM kv WHERE key = ?" or executing a prepared version of the former versus a direct "kv.get(key)" is there, sure, but _orders_ of magnitude larger?
It makes the flawed assumption that many main-memory databases do, that all RAM is the same speed. It uses T-trees as its underlying data structure. LMDB uses B+trees because time and again research shows that B+trees are more efficient, even when all of the data fits into main memory. This is the same mistake the MemSQL guys make, as well as MySQL NDBCluster.
See these papers, for example: http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html http://www.vldb.org/dblp/db/conf/vldb/RaoR99.html
The reality is that computer architectures are hierarchical in nature. A CPU has L1, L2, and possibly L3 cache, each of which is progressively slower than the previous. Then it gets to local RAM, which is slower still. Then in a multiprocessor machine, there is NUMA, memory residing on remote nodes, which is again slower still. B+trees are inherently hierarchical and naturally suited to the reality of system design. All other approaches, including the recently popular LSM trees (as used in e.g. Google LevelDB, SQLite4, and various other recent databases) are all inherently inferior because of this fundamental fact of computer architecture.
Makes sense .. main-memory access patterns optimized for locality will have an advantage vs patterns that assume O(1) for any (random) pattern.
Btw: could LMDB be used as a backend of sqlite4? I.e. does LMDB support ordered access?
From the sqlite4 docs:
"SQLite4 needs to be able to seek to the nearest key for a given probe key, then step through keys in lexicographical order in either the ascending or the descending direction. "
.. where ordering is:
"Keys sort in lexicographical order (as if sorted using the memcmp() library function). When one key is a prefix of another, the shorter key occurs first."
FastDB also appears to use locking, while LMDB is MVCC and readers require no locks, so even with all of the other disadvantages out of the way, LMDB will scale better across multiple CPUs.
Ah, cool. This is definitely a very good thing: no locks, and writers don't block readers.
FastDB is also written in C++ which is another inherent disadvantage compared to LMDB which is pure C.
Yes, though I'm a C++ fan, I agree with this point. E.g., here is a nice Python wrapper
https://github.com/dw/py-lmdb/
which interfaces using Cython and wouldn't be possible if LMDB would be C++.
You could adapt the LevelDB microbenchmarks to test it but ultimately I believe it would be a waste of time.
Thanks for your detailed answer and sharing information! It seems LMDB deserves much more visibility in the community.
- Tobias
Tobias Oberstein wrote:
Am 21.03.2013 21:58, schrieb Howard Chu:
Tobias Oberstein wrote:
Hello,
I have read the - very interesting - performance comparison http://symas.com/mdb/microbench/
I'd like to ask if someone did benchmark LMDB (and/or the others) against http://www.garret.ru/fastdb.html
FastDB is an in-memory ACID database that works via shadow paging, and without a transaction log.
OK, like LMDB it uses shadow root pages. I think the similarity ends there.
Ah. Ok.
It is a relational database with an ASCII query language, while LMDB is strictly a key/value store. That automatically means for simple get/put operations LMDB will be orders of magnitude faster (just as it is so much faster than SQLite3 and SQLite4).
Mmh. The overhead of parsing a "SELECT value FROM kv WHERE key = ?" or executing a prepared version of the former versus a direct "kv.get(key)" is there, sure, but _orders_ of magnitude larger?
Measure it for yourself and let us know, if you have any doubts.
Btw: could LMDB be used as a backend of sqlite4? I.e. does LMDB support ordered access?
Yes. We have that already under way.
FastDB is also written in C++ which is another inherent disadvantage compared to LMDB which is pure C.
Yes, though I'm a C++ fan, I agree with this point. E.g., here is a nice Python wrapper
https://github.com/dw/py-lmdb/
which interfaces using Cython and wouldn't be possible if LMDB would be C++.
Exactly. If you want to write a tool that's useful, don't choose a language that automatically precludes other uses. People writing libraries in Java, this means you. (e.g. SimpleDBM, which I stumbled on a few years ago while looking into B-link trees. http://code.google.com/p/simpledbm/)
You could adapt the LevelDB microbenchmarks to test it but ultimately I believe it would be a waste of time.
Thanks for your detailed answer and sharing information! It seems LMDB deserves much more visibility in the community.
Totally. I've been hitting every relevant conference that comes my way. http://symas.com/mdb/
but there's only so much time, and travel interferes with development. As is so often the case in OpenLDAP, huge numbers of people/projects use our work but very few publish their success stories.
FastDB also appears to use locking, while LMDB is MVCC and readers
Yeah, MVCC is the right thing ..
require no locks, so even with all of the other disadvantages out of the way, LMDB will scale better across multiple CPUs.
So _one_ LMDB can be concurrently used from multiple threads and multiple processes, with multiple readers and writers?
Writers wont block readers, but writers require exclusive lock?
When used from different process, the single-layer design making use of the filesystem buffer cache will mean there is no "buffer cache" per process, and memory-consumption won't skyrocket?
Tobias
Tobias Oberstein wrote:
FastDB also appears to use locking, while LMDB is MVCC and readers
Yeah, MVCC is the right thing ..
require no locks, so even with all of the other disadvantages out of the way, LMDB will scale better across multiple CPUs.
So _one_ LMDB can be concurrently used from multiple threads and multiple processes, with multiple readers and writers?
Writers wont block readers, but writers require exclusive lock?
When used from different process, the single-layer design making use of the filesystem buffer cache will mean there is no "buffer cache" per process, and memory-consumption won't skyrocket?
Correct. I've already demonstrated this by running SLAMD benchmarks against two slapds operating on the same database. (Due to inefficiencies in slapd's frontend/connection manager/threadpool, you can actually double slapd throughput using 2 slapds on the same database.)
openldap-technical@openldap.org
-
devzero2000 -
Howard Chu -
Tobias Oberstein