I'm not bashing MDBM because it's a competitor; it obviously isn't a competitor. Heck the only reason I'm commenting in this thread is because you asked me to elaborate on its design flaws. Now you're hurt that I answered your question. Don't ask if you don't want to know the answer.
... seems like us folks in OpenLDAP weren't the only ones to have bad experiences with it. This guy in this same discussion seems to share the basic sentiment. https://news.ycombinator.com/item?id=8733819
Where did I say your opinions are baseless? Edit. Huh, yeah I did. In the same place where I asked if you had ever used mdbm or are you spouting baseless opinions. So have you used it? All the links you provided talk about various DBM backends, not one of them point to mdbm as a problem. So again, have you used it or are you in fact stating baseless opinions?
I'm sorry the openldap couldn't figure out how to use MDBM in a way that worked for them. Yahoo clearly has. We have. Others have. It works extremely well for what it was designed for and the perf numbers show that it spanks the living crap out of your stuff. But your stuff does more, which is cool. Why don't you focus on that rather than trying to crap all over some useful code? It's clearly not a threat to you. I don't see how the world is well served by your comments. For certain problems MDBM is way the hell better than what you have. It's a narrow niche, doesn't compete with you, so why all the fuss?
As for me asking you to comment, yup, I did, but you were already well on your way of banging on technology you clearly didn't understand. I think I get why it didn't work for you, your comments have made it clear you have no idea how it works. I went and read all the links you provided above, not one mentioned mdbm having corruption bugs. It's entirely possible that the other DBM style dbs had bugs, or it is possible that people were inserting / deleting in a first / next loop, whatever. But pointing a finger at MDBM and claiming corruption bugs, how about you substantiate that claim? Seems somewhat flawed when multiple companies have used it for 10 years or more and it seems to work fine for them.
You were already losing credibility due to your inattention to detail. I never mentioned performance anywhere in this thread. It's stupid to even talk about it since a hash doesn't do ordered lookups. But now that you're raising the topic: https://github.com/hyc/leveldb/tree/benches/doc/bench
"Spanks the living crap" - must be some heretofore unknown definition of "spanks".
Feel free to submit a patch if I got anything wrong in that driver; it was a pretty hasty patch. This is running on tmpfs, so no I/O involved. MDBM is faster on random read, which is what you'd expect since it's a hash and doesn't have to navigate down a tree to locate a record. Aside from that, it's pretty pedestrian.
As to losing credibility, I'm semi retired, I stopped trying to impress people a decade ago. If i were you I'd be more worried about your own image, bad mouthing other people's tech when you demonstrate you don't understand it hasn't made you like good to at least a few people here.
It wouldn't be that hard to say "MDBM is great when used as an index into a DB, it works just fine for that. But you are going to have to rebuild the index after a power failure unless you take care to flush the data. It's somewhat unfair that the OP compared against my database because mine is slower because it handles crashes."
Instead you come out with "MDBM is complete crap". Well, no, it's not. In the domain where it is useful it is actually quite useful, it's 10x faster for lookups than your DB. So the trade off is speed vs surviving reboots. For lots of people, speed is much more important. Machines don't crash every ten minutes. In fact, it's pretty common to see uptimes in 100's of days. Lets say that 100 days is average and lets say that it takes a full day to rebuild the MDBM. So MDBM is delivering 99/100 days of useful work. You deliver 100/100 days. Oh, wait, except that your useful work is running 10x slower if the DB is being used as an index. So you delivered 10/100 days. See why some people may prefer to use MDBM when it is put like that? Performance is a feature.
Nice try. Performance is a side-effect, efficiency is a feature. Nothing you can find will show MDBM to be 10x faster than LMDB. You must be talking about LevelDB.
Look at the results I posted again, and look at the benchmark code. Tell me that I've made a mistake, that's fine. The thing about open source is there's no reason to BS, anyone can build and run it and see for themselves. LMDB is faster and its data is more compact than MDBM, so you can get more work done using less resources, and you don't have to worry about losing your work for unexpected downtime.
Hashes suck for large volumes of data. That's just the reality of it, plain and simple: Low storage efficiency, memory-intensive, and cache-unfriendly. Whether people like or dislike me personally for saying so doesn't change the facts.
As for uptime - sure, and my PCs have uptimes for hundreds of days too. But I'd be a fool to just take that for granted and not take regular backups. The problem with your 99/100 days math is that you can't actually account for the cost of a crash that way. It might only set you back to 0/100; if you're unlucky it will set you back to -100 or more.
You're right, I was talking about LevelDB. But in your benchmark MDBM is 2x faster on the code path it cares about, random reads. Lots of people pay attention to a factor of 2.
Any idea why it is that much better than LMDB?
I actually agree with you in that hashes sort of suck, just look at Git when the repo gets big, a hash is a miserable way to traverse all that data, very cache unfriendly.
But the use cases for MDBM are the same, you have lots of keys and you want to get to any key very quickly. It appears to me that it (still, 20 years later) wins that race.
mdb_stat /tmp/leveldbtest-1000/dbbench_mdb-6/
Status of Main DB
Tree depth: 4
Branch pages: 204
Leaf pages: 31250
Overflow pages: 0
Entries: 1000000
As you said, MDBM can find any record in 2 seeks; for this database the LMDB tree height is 4 so any random access takes 4 seeks. 2x perf difference.
On a larger DB we would expect MDBM's random read perf advantage to get larger as well, until the DB exceeds the size of RAM. I've tried to duplicate my http://symas.com/mdb/ondisk/ tests with MDBM but it makes XFS lose its mind by the time the DB gets to 2x the size of RAM. First I had to increase the MDBM page size from my default of 4KB to 128KB, otherwise I'd see a lot of this in the output:
2014/12/16-13:13:29 ... thread 0: (200000,12200000) ops and (3436.0,8072.2) ops/second in (58.206750,1511.358831) seconds
3:54903002:dc057:00864 mdbm.c:1809 MDBM cannot grow to 33554432 pages, max=16777216
but on this VM with 32GB RAM, every time the DB hit 60GB in size the kernel log would start getting spammed with
Dec 16 22:19:19 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:21 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:23 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
So thus far I've been unable to load the 160GB DB to reproduce the test. But this underscores the basically uncacheable nature of hashes - once the directory gets too big to fit in RAM, your "2 seeks per access" goes out the window because the kernel is thrashing itself trying to keep the whole directory in-memory while finding the requested data pages.
B+tree performance degrades gracefully as data volumes increase. Hash performance falls off a cliff once you cross the in-memory threshold.
So for creating the DB you are correct though you should be able to size the DB such that you aren't splitting and copying all the time if you have an idea of how much data you are going to put in.
The "2 seeks per access" absolutely does NOT go out the window. The whole point was that this works for any size DB. It's a function of the size of the pages, the keys, and the values, for a run with key+val @ 20 bytes and 8K pages, 25 million entries had a directory of 16KB. You hash the key, walk however much of the 16KB you need to find the page, and then you go to that page and only that page.
2 seeks for any lookup for any sized DB. The directory could be better but you walk sequentially (hell, map that and lock it in, then it is 1 seek for any lookup).
The reason you are thrashing XFS so much is we're growing the directory and the number of pages. Each time you split a page you have to copy to the new pages.
For completeness' sake... I've tried a dozen runs at this already, looking for tuning parameters to tweak. It always starts well and then degrades rapidly before finally hanging.
MDBM: version 4.11.1
Date: Tue Dec 16 20:34:36 2014
CPU: 16 * Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz
CPUCache: 20480 KB
Keys: 16 bytes each
Values: 2000 bytes each (1000 bytes after compression)
Entries: 76800000
RawSize: 147656.2 MB (estimated)
FileSize: 74414.1 MB (estimated)
------------------------------------------------
2014/12/16-20:34:38 ... thread 0: (200000,200000) ops and (128923.6,128923.6) ops/second in (1.551306,1.551306) seconds
2014/12/16-20:34:39 ... thread 0: (200000,400000) ops and (110571.0,119044.1) ops/second in (1.808792,3.360098) seconds
2014/12/16-20:34:42 ... thread 0: (200000,600000) ops and (87921.9,106480.3) ops/second in (2.274746,5.634844) seconds
2014/12/16-20:34:44 ... thread 0: (200000,800000) ops and (107459.0,106723.3) ops/second in (1.861175,7.496019) seconds
2014/12/16-20:34:46 ... thread 0: (200000,1000000) ops and (90923.1,103138.7) ops/second in (2.199660,9.695679) seconds
2014/12/16-20:34:50 ... thread 0: (200000,1200000) ops and (51852.2,88542.6) ops/second in (3.857118,13.552797) seconds
2014/12/16-20:34:53 ... thread 0: (200000,1400000) ops and (57516.7,82207.6) ops/second in (3.477253,17.030050) seconds
...
by the end
2014/12/16-21:18:19 ... thread 0: (200000,22400000) ops and (858.0,8541.6) ops/second in (233.094661,2622.447456) seconds
2014/12/16-21:19:19 ... thread 0: (200000,22600000) ops and (3321.7,8424.5) ops/second in (60.210362,2682.657818) seconds
2014/12/16-21:20:28 ... thread 0: (200000,22800000) ops and (2880.3,8284.6) ops/second in (69.437524,2752.095342) seconds
2014/12/16-21:21:31 ... thread 0: (200000,23000000) ops and (3203.6,8171.9) ops/second in (62.429181,2814.524523) seconds
then a stream of these start showing up in dmesg
Dec 16 21:14:09 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 21:14:30 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 21:14:32 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 21:14:34 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 21:14:36 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
and on and on until I kill the job.
Dec 16 22:19:01 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:03 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:05 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:07 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:09 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:11 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:13 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:15 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:17 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:19 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:21 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 16 22:19:23 localhost kernel: XFS: possible memory allocation deadlock in kmem_alloc (mode:0x250)
Dec 17 00:14:16 localhost systemd: Got automount request for /proc/sys/fs/binfmt_misc, triggered by 1372 (vmtoolsd)
LMDB does this load in 8 minutes at an effective data rate of ~283MB/sec. Pretty much as fast as the hardware will stream (peak throughput of 300MB/sec in this VM). I don't see how you can possibly use MDBM as an unreliable data store if it could potentially take hours to reload the data.
Just to be clear - the loading job keeps running when the kernel error messages first start happening at 21:14:09. But after 21:21:31 the loading job makes no more progress. The kernel error messages continued until 22:19:23 when I killed the job, but nothing further got written to the DB in that intervening hour (based on looking at the filesize, which admittedly may not tell the whole story). The job stats were set to output once per 200,000 ops. It's of course possible that it was still making some progress, but dropping from 3203 ops/second to something less than 55/second is pretty drastic, and at that rate it would have taken weeks to complete the load.
As another note, I also tried to use mdbm_pre_split() at the beginning of the job. That churned for 10 minutes at the beginning of the job before adding any records, then started processing at its normal speed, and then quickly degraded into the same state.
I apologize. I reread my comments and they come off as downright incendiary which was not what I intended.
At least back when I was using it, there is a bit of a science to tuning mdbm correctly for your data. In general, it is a tool designed to allow you to tweak with whatever application level knowledge you have of your data's structure, and as a consequence it can be terribly suboptimal out of the box. Depending on circumstances, even if you don't need disk level transactional integrity, LMDB may indeed be a be better choice.
That said, the test case you are describing is definitely for a use case for which mdbm is suboptimal. The results you are getting are if anything surprisingly good under the circumstances, and frankly I'd have never even considered using mdbm for that kind of work load (LMDB would definitely be one of the first choices I'd consider for that kind of work load).
As you've mentioned, a hashtable based key-value store is fairly suboptimal for disk based storage (though depending on circumstnace and how you tweak it, a hash table with mdbm can work surprisingly well with an SSD based store), and the numbers you are presenting seem if anything better than I'd expect.
The reports you are seeing with XFS seem... odd, and almost feel like either a simple issue with a bug in how mdbm is talking to mmap/vfs layer, or more likely within XFS's implementation, but it doesn't seem like they are slowing you down.
In general, mdbm is most useful for storing and accessing compact rows in memory across potentially many processes with a random access pattern, which IMHO is not the problem space that you are testing and tackling with LMDB, LevelDB, or many of the others. One can (rightly) argue that that is a fairly narrow and simple problem space, but as with almost anything in computer science, doing even fairly narrow and simple things efficiently (and mdbm has a number of clever design choices that help it be efficient) and in an error free fashion is enough trouble that having a standard tool for solving that problem is terribly useful.
MDBM isn't really the only tool for solving that problem out there. Pretty much any shared memory hash table based solution may be a good fit for it, and there are alternative data structures that have desirable advantages over hash tables (critbit based structures are one of my favourite pets for such problems). Heck, in C++ I've used the Boost.IPC library's unordered maps for the job with reasonable results.
I bet there are probably some implementations that perform better than mdbm in certain cases (I'd actually be interested in benchmarks comparing that kind of workload with other tools designed for that problem space). Still, the mdbm codebase is battle hardened and really does perform well as long as your data set size & access patterns don't cause thrashing of the page store.
I think the comparison was totally appropriate because the article specifically highlighted mdbm's design limitations. The whole point was that given the compromises mdbm makes, it is possible to yield significant performance gains, so if those design limitations fit your context (and it cited 4 specific examples where Yahoo uses them), you ought to consider it.
My point, and the reason I will still say MDBM is garbage, is that you can get mmap/zero-copy performance without sacrificing reliability. Only a fool would argue for the performance without reliability when they can get both. And with a lower total system cost.
> Only a fool would argue for the performance without reliability when they can get both. And with a lower total system cost.
I think that statement is absolutely true. I just think you have a myopic view about how to achieve performance and reliability. Look at Yahoo's example use cases.
> For lots of people, speed is much more important. Machines don't crash every ten minutes.
Even if they do, it is often faster and more reliable to recover from the RAM of a surviving node than to try to recover from the disk on the crashed system.
> lets say that it takes a full day to rebuild the MDBM
I can't imagine a circumstance where it'd take even an hour to rebuild an MDBM from raw data.
We used MDBM in OpenLDAP for a few years on SGI Irix. I haven't touched it myself in something like 9 or 10 years though. http://www.openldap.org/lists/openldap-devel/199903/msg00094...
http://www.openldap.org/lists/openldap-devel/200501/msg00053...
Using DBM-style DBs was an endless nightmare of corruption bugs. That technology belongs firmly in the distant past, we have better solutions today.
http://www.openldap.org/lists/openldap-software/200607/msg00...
I'm not bashing MDBM because it's a competitor; it obviously isn't a competitor. Heck the only reason I'm commenting in this thread is because you asked me to elaborate on its design flaws. Now you're hurt that I answered your question. Don't ask if you don't want to know the answer.
... seems like us folks in OpenLDAP weren't the only ones to have bad experiences with it. This guy in this same discussion seems to share the basic sentiment. https://news.ycombinator.com/item?id=8733819