Btree vs. LSM
github.com
github.com
For more recent and realistic benchmarks you should look at the work of Mark Callaghan.
1. Use SI magnitudes, so that we don't have to count the zeros. (so 100k instead of 100000.)
2. Either use the same chart for LSM vs Btree for each of read and write, or at the very least use the same y axis between the two.
3. It's hard to see the difference on the limited write benchmarks. Can we make it either logarithmic or another graph with these differences highlighted?
[1] https://en.wikipedia.org/wiki/Violin_plot [2] http://stackoverflow.com/questions/23675735/how-to-add-boxpl...
In general, B-Tree index performance has plenty to do with low-level optimizations, beyond things that are published in academic papers. I'm talking about things like micro-optimizing the number of CPU cache misses on internal pages, the use of interpolation search, and so on.
What am I most looking forward to using later this year? ScyllaDB[1] and CockroachDB[2], both in conjunction with LMDB.
It does, yes. The best architecture when using LMDB is to have a single writer thread, and many independent reader threads.
That said, it is nice to be able to run the occasional separate process to do some maintenance task on the database (e.g. to do some writes), and the global lock comes in handy then.
The main reason a single write thread design isn't a problem is you can do a million or more separate, fully transactional and isolated write transactions per second on a single core with LMDB. Writes are simply not the bottleneck.
You can't get anywhere near that kind of write performance with a fully transactional and concurrent write system like CockroachDB, not even with 100x the hardware. However, some of the eventually consistent databases, like ScyllaDB, can scale up to more total writes per second (but of course you give up the transactions, and the consistency).
The actual issue I have with using LMDB in this way is keeping it fed! My code is now written in C++, I'm using Aeron for high-performance messaging and Cap'n Proto for messages (eliminates serialization/deserialization) as well as Cap'n Proto for storing objects inside LMDB. I'm nowhere near LMDB's write thread being the bottleneck, and I'll only get close to it once I'm on a 20Gbit/sec machine.
IMO a properly designed system will always and everywhere be bandwidth constrained, not CPU or "architecture" constrained. (Put another way, everyone has access to supercomputers these days, we just use them poorly most of the time.)
Sure you can. MSR's bw-tree[1] is my favorite example but there are others. I've learned some interesting things from both you and Howard and thank you for it, but the hype around lmdb is a little thick at times. It is possible to build lock free low latency concurrent transactional datastores.
Edit for folks to lazy to scan the whole paper:
They test a real world workload sampled from xbox live services. It's roughly 100 byte keys, 1k values, and around 8:1 read to write ratio. They sustained over 10 million ops a second on a 4 core machine. There are no locks and all transactions can read or write as they like concurrently.
[1]: https://www.microsoft.com/en-us/research/wp-content/uploads/...
Where's the source code for that? (I read the paper when it came out, good stuff!)
In my experience, I don't fully trust research results—especially for databases—until they've been replicated in production. Especially on high-performance systems, small changes (oh, we added error handling, or oh, now we're actually calling fsync) can easily drop actual achieved performance 1 or even 2 orders of magnitude. (I'm not saying this is true for the linked paper, just that I'd want to verify the actual achieved performance on my own workloads before I switched to it. I do believe it's possible FWIW, I just haven't seen it in the real world.)
So if there's an LMDB-style codebase out there I can spin up that uses a Bw-tree internally, I'm definitely interested and would love a link. :-)
Also FWIW, what I like about LMDB isn't just the speed, it's the entire architecture. This fall I'm looking into using ScyllaDB for page storage, and storing the meta pages inside CockroachDB, with a user-per-LMDB-environment model. LMDB's essential design makes that (relatively) easy, whereas with, say, RocksDB, not so much (at least for me).
Closed. It's backing Hekaton in MS SQL and some features of Azure DocumentDB.
While there are many systems in the literature that demonstrate some variation of lock free log and indirection map, they're all either research demonstration codebases or closed source to the best of my knowledge.
The reason I have an axe to grind here is I think the generalizations around LMDB made by you and others are making this situation worse, by convincing people that haven't read the last few years of literature that LMDB's design is all there is. LMDB is great but narrow. It has no answer for many workloads. It's inevitable that better things will be devised. I want those things to be FOSS. Do the over-reaching and over-simplifying comments about LMDB make that more or less likely?
Fair enough. For anyone else following, @jasonwatkinspdx is correct that LMDB is not the right (= best available today) choice for certain workloads. I personally used TrailDB for event traces and if I needed prefix compression on keys (like the CockroachDB team), RocksDB would be an arguably better choice.
What I don't agree with is that LMDB's existence or users are causing open source database research to stagnate. Quite the contrary, I think the benefits of LMDB's architecture have not yet been fully realized and I would love to see more research be done to improve/extend it.
Most of the research action today (at least to me) seems focused on making log-structure merge trees and variations thereof less sucky at the margin instead of identifying what makes LMDB's design actually tick and then improving on it. There's still a lot of low-hanging fruit in the LMDB architecture waiting to be explored.
The Cap'n Proto documentation compares it extensively with Protobuf and most of those comparisons probably apply to Extprot as well.
(Disclosure: I am the author of Cap'n Proto and also Protobuf v2.)
Cap'n Proto has a way better compatibility story, and there's no need to read the entire message just to read a particular part.
SBE is very good for its intended use case: high-frequency trading with tiny, but tons, of small messages. Cap'n Proto is better for use as a stable (but evolvable) message format between systems (e.g. RPCs), or for on-disk storage if you've got a database (like LMDB) that doesn't force you to copy read-only data.
Also reading through their site, I didn't know Google's Spanner required AtomicClocks! Holy deep pockets Batman!
GPS NTP servers start at $1000, but I dunno how much that delivers. The actual GPS signal is probably accurate enough, but the rest of the hardware chain on a $1000 box might not be <1ms. Google might have also wanted a backup in case antennas are disturbed or GPS signal somehow interrupted?
But even then - just because Google chose 7ms doesn't mean everyone else has to. Drop a GPS NTP master at each site and live with that? I wouldn't imagine it'd get much worse than 10-20ms?
I don't really know a whole lot about this though.
I had one in the NTP pool for a while.
Some of the worst production experiences I've had came from exhausting I/O on the database, and then having LevelDB / RocksDB / LSM stores kick off their compaction. B-Tree will give you a very consistent redline in terms of performance generally.
TL;DR: There are trade offs between the two, but this benchmark is not particularly insightful given that it doesn't really test any of the interesting boundary conditions or real world query patterns.
This test uses a 10GB test size which is very small compared to the size of RAM available for the page cache. This will hide the seek penalties that the B-Tree takes on reads. Over a much larger test one would expect the write performance of a well written LSM to flatten out to a constant, indefinitely sustainable, rate. A (COW) B-tree would be expected to gradually degrade over time as it gets more fragmented and takes more seek penalties for writes and range reads.
The seek penalty is relevant for SSDs as there are still only a finite number available: you can expect on the order of 100K/s rather than the 100/s you might expect from a conventional disk. You still want to be mostly operating those things in streaming read mode where possible.
- RDBMS: B-Tree Layout (good for lookups)
- No-SQL (like) DB's: LSM (good for heavy write throughputs)
And then there's ones like Dremel which opt for high-octane full-table scans.
http://highscalability.com/blog/2014/8/6/tokutek-white-paper...
glibc malloc not up to the task?
It's just as tcmalloc or faster (in new versions). Unlike tcmalloc is has very low memory fragmentation and is aggressive by default in returning it to the OS.
Returning memory to the OS is very valuable in DBMS since every extra page not used in userspace is a extra page in page cache which in my testing leads to better query performance under load.