Yeah the strident and somewhat impolite tone is really hard to tolerate. Esp when directed against respected researchers like Pavlo and Leis who, well, they know what they're talking about.
Everything has compromises and trade-offs. LMDB looks great. But it's also, like a lot of similar systems, built to perform best at single-writer / multiple-reader workloads. That's not the only workload out there.
If they knew what they were talking about they wouldn't have used a raw filesystem benchmarking tool to prove their arguments. They would have used a pair of actual, comparable DBMS implementations.
Single-writer is all you need if each write is fast enough.
BerkeleyDB, which we used before writing LMDB, is multi-writer. It's still slower than LMDB in every workload, because of all of the lock management that comes with being multi-writer.
Feel free to point out specific arguments that you think need further fleshing out. Every aspect of LMDB's design and performance characteristics have been documented already, happy to link you to answers to any of your questions.
Author is right that a read only mmap with writing occurring normally is a better design. It’s a weakness in the paper but in fairness few databases did what LMDB did sanely. Surprising that that’s the case but that is what people chose to do.
Where they’re wrong is about the performance analysis:
> In section 3.2 "I/O stalls" is again a non-issue; no matter how your DBMS handles I/O internally, synchronously or asynchronously, the calling application can't make any progress until the I/O completes, and if the data isn't already in memory then the application must wait.
A TLB shoot down request to pull in a page or evict it can cause pauses not just in your own application but also many others because it’s basically a system wide mutex. There is a trade off obviously where the kernel can evict I/O buffers more efficiently. But to me all that says is that the interface for managing I/O buffers in user space is really immature and needs some better performing API so that we have something in between mmap and buffer management. Also an asynchronous application can switch to doing other work. If your synchronous memory access is blocking your thread, other unrelated work is being blocked.
As for workload optimization, I think OP is overstating how much sharing resources mitigates this - when I’m doing a blind search through all data for some reason (maybe some kind of background GC) or a range lookup I can choose to not cache any of that data. Similarly, if I’m doing a point lookup I can do a pre read. However, mmap has no higher level concept about the workload that’s accessing the memory. This a very real problem the kernel tried to tackle back in the 90s / early 00s when disk indexing was starting out - a disk index would cause the cache for all other apps to be evicted resulting in waking up to a sluggish machine paging everything back in.
The more high level context you can retain, the better your decision making about resource allocation is. When that high level context is lost/discarded you lose efficiency.
> There is a trade off obviously where the kernel can evict I/O buffers more efficiently. But to me all that says is that the interface for managing I/O buffers in user space is really immature and needs some better performing API so that we have something in between mmap and buffer management.
This was essentially the argument against adding the raw device support to Linux, which delayed the Oracle database Linux port for years, with Linus himself being adamant that operating system's own VMM and page cache management was superior to that of the database (except it was not), which was proven to be a fallacy as the transaction and error handling database requires completely different guarantees, and the VMM pursuing different design objectives that most of the time are incompatible with the database expectations.
The raw devices have been used precisely for that reason: «let's bypass the VMM and the page cache for this device, and we will take it from there». That is what the Oracle database did on Solaris – it wanted an entire raw device that it would claim for the table space. Granted, Oracle has had its own VMM and page cache (so to speak) implementation within the DB, an OS mini-kernel if you like.
The argument was eventually settled with adding the O_DIRECT flag to open(2) accomplishing the same outcome, and the raw devices have never made into Linux.
This is commonly avoided by not putting memory pressure on your O_DIRECT application, which is probably an RDBMS on a dedicated single-purpose host.
Not saying more work in the space wouldn't be welcome and interesting, just that it's generally the assumption whenever I've seen O_DIRECT (since the Solaris days and through today) that what's using it is the only thing of substance on the box.
I think that’s a flawed assumption. Databases show up in many spots besides dedicated RDBMS (eg SQLite and RocksDB power all sorts of things and likely coexist with compute nodes because even compute nodes can need some amount of local storage).
I did not imply that O_DIRECT was a full equivalent of raw devices, it was rather a compromise as Linus would not concede with the idea of raw devices making it into Linux.
Besides, O_DIRECT can be used at the file level (and the file system level as well via chattr – if the file system supports it) whereas the raw devices are, well, device level only.
I’m pretty sure you can open disks raw in Linux. But then the disk is owned by the RDBMS. Ceph can do this in its BlueStore engine.
But yeah, I understand you weren’t talking about buffers, I was just highlighting that O_DIRECT and raw devices are totally separate problems from having a user space cache that can be evicted by the kernel memory and reconstructed by the application lazily.
Yes, you can use raw block devices in Linux. LMDB works on raw block devices as well. You get write-through cache behavior; writes are immediate but everything still goes into the page cache.
I've not yet bothered to check how things work with raw devices in Windows. I believe only Admins can even operate on them so it would be kind of limited usefulness.
When I was writing a game engine and doing a multithreaded resource loading system using job queues, I was concerned about TLB shootdowns, but was unable to really experience the issues with them.
I tried both regular IO and mmap and was unable to make regular IO as fast as mmap.
This is on a machine with 32 real cores running 64 job threads, saturating all of them with jobs. The jobs are a mixture of small (metadata) and big (textures and models) files. In theory, this should be a pretty bad situation for the TLB shootdown, and I was concerned about them.
But in reality it seemed to be fine, and a fair amount faster than with regular IO due to being able to have one less extra copy of the data.
You’d be surprised how difficult it can be to create such a scenario and detect when you do, especially using a synthetic benchmark.
In terms of regular io, did you remember to do O_DIRECT? Also yes, I/O paths are slower than mmap for pure throughput in most cases. Databases are a special snowflake though. In some ways you’d want the I/O layer in the kernel like with a filesystem which is why databases typically go the other way and try to bypass the kernel to keep their code in user space
> buffers in user space is really immature and needs some better performing API so that we have something in between mmap and buffer management.
If you don't know about it already, you should look at Viktor Leis' et al's work on this -- kernel module + supporting buffer mgmt code to do the kind of thing you're talking about. The code is not production quality, but the idea is nifty:
Yeah I’m aware work is kind of being done in the space. Not pretending it’s my idea. Just a more formal official API would be supremely interesting and not just for databases - there’s lots of user space caches that should be migrated to that if they’re recomputable.
Relatedly there’s an effort going on in the filesystem space for a long time to add transaction support which would also be useful. Some day.
By “transcations” I mean the ability to do a bunch of “invisible” writes to a file that are only published through an fsync (and also not made visible just because a sibling application invoked sync). Full transactions aren’t necessary and I agree would be overkill. The work is primarily driven by XFS developers if I recall correctly (too lazy to lookup the exact links). But there are clever workarounds in user space although they’re not particularly confidence inducing.
The original paper literally shows the effect of cross tlb shootdowns. I don’t recall LMDB specifically so maybe their performance floor was just naturally much higher anyway. I’ve also seen the impact of cross tlb flushes and synthetic benchmarks are the wrong mechanism because of all the secondary effects. It really is a kind of global mutex for memory operations on the machine where a memory allocation in an entirely different process can take longer as a result. The real world results showing it were inconsistent and impossible to reproduce in synthetic benchmarks and took a lot of smart people a long time to narrow down the cause when I saw this (not a DB application but it was cross tlb shootdowns slowing down the machine).
If this was a significant factor, then it should have a greater impact in high concurrency workloads, getting progressively worse across multi-socket machines.
> The notion that "maybe their performance floor was higher" is laughable, since no other DBMS delivers anywhere near LMDB's read performance.
What I said was that lmdb’s read performance may be so good, that at its worst when you’re seeing cross tlb shootdowns, it’s still better than the other DBs. You seem to contradict me and then restate the exact same thing.
> Benchmarks all show that LMDB performance scales perfectly linearly across arbitrarily many CPUs
As I said, synthetic benchmarks may not reproduce the cross tlb shootdown scenario frequently enough for you to notice it. It’s like frame stuttering - you can’t argue that it’s not happening by saying the average frame rate was 70fps. The data you’re using to support your argument isn’t a relevant measure. You’d have to actually measure how frequently cross tlb shootdowns are happening (via dtrace probably) and ideally compare it against a robust lmdb read path written against iouring to get an accurate measure of the issue.
If there's any effect (like frame stuttering) then it will impact the max and 99th percentile latencies. Given that LMDB's latencies are always the tightest of any DB, it still boils down to "even if the effect is real, it's unmeasurable and therefore negligible." http://www.lmdb.tech/bench/memcache/
And of course, none of this is working in a realtime environment, so a couple nanoseconds here or there just doesn't matter.
Except even your link shows a substantial jump in the log graph from ~500ms->1s going p99 to pmax. And cross tlb shoot down times can vary wildly but nanoseconds is the wrong order of magnitude. They also get significantly worse with the number of cores. That link claims the test is 16 cores but my hunch given that the benchmark is from 2013 is that it’s 8+HT.
I really don’t understand this defensiveness and doubling down on something that’s pretty well studied and documented. Keep in mind that the original paper looked at raw mmap vs raw io api issues regardless of the surrounding DB: https://www.cidrdb.org/cidr2022/papers/p13-crotty.pdf
It’s a really well written and accessible paper and this is not the hill to die on if you’re disagreeing. I agree mmap for the read path only is a weakness in their paper and that idea I agree has some merit. But cross tlb shootdowns are a real performance downside of this approach.
> That link claims the test is 16 cores but my hunch given that the benchmark is from 2013 is that it’s 8+HT.
We tell no lies. Those tests were run on an HP DL585 G5 server with 128GB of RAM and 4 quad core AMD Opteron 8354 CPUs. If cross-TLB shootdowns were actually as big a problem as they claim, there should be massive latency spikes due to cross-socket communication, far worse than for inter-core single socket.
You're definitely misreading the graphs, the Y axis is clearly labeled "msec". You're going to have to pay better attention if you want to discuss this further. Otherwise we're just wasting our time.
> Keep in mind that the original paper looked at raw mmap vs raw io api issues regardless of the surrounding DB
Yes, but that's exactly why the paper is utterly worthless and never should have made it past peer review. Their initial claim is this:
> Unfortunately, mmap has a hidden dark side with many sordid problems that make it undesirable for file I/O in a DBMS. As we describe in this paper, these problems involve both data safety and system performance concerns. We contend that the engineering steps required to overcome them negate the purported simplicity of working with mmap. For these reasons, we believe that mmap adds too much complexity with no commensurate performance benefit and strongly urge DBMS developers to avoid using mmap as a replacement for a traditional buffer pool.
To prove their claims they would have to have demonstrated that a DBMS using mmap was more complex and less reliable than one using a traditional buffer pool. They also had to demonstrate that a DBMS using mmap had no performance benefit vs a DBMS using a traditional buffer pool. They didn't demonstrate any of these things, and LMDB is concrete proof that all of these claims are wrong: at only 7KLOCs it is simpler than every other traditional DBMS, its reliability is literally perfect, and its read performance is always orders of magnitude than all traditional designs.
The reviewers should have known just from reading the abstract that this paper was a dud:
> Such problems make it difficult, if not impossible, to use mmap correctly and efficiently in a modern DBMS.
Their claim required them to prove a negative, which obviously defies the rules of logic. Everything after that was just noise.
It’s funny that the article holds up RavenDB’s rebuttal about MMAP and then discusses correctness, because Aphyr/Jepsen’s latest analysis on RavenDB showed huge correctness issues there: https://jepsen.io/analyses/ravendb-6.0.2
I struggle to use lmdb when using resource isolation (like docker, nomad exec driver). The hidden complexities really become apparent when you build largish systems using shared infrastructure. Anything is easy if you have a dedicated machine or have dataset smaller than your memory allocation.
Mmap is so simple for the application/developer, but the price you pay is giving up clear ownership of memory and clean separation between kernel page cache and application space. The interaction between the mmu, mmap, tlb and the linux kernel IO layer is complicated. You don't want to touch that complexity at all if you care about ultra low latency.
The article rephrases the question into
"do you really want to reimplement everything the OS already does for you?"
but I would rephrase it again into questioning why fairly straight forward concepts like a buffer cache can't be implemented directly in the application?
> You don't want to touch that complexity at all if you care about ultra low latency.
This is less about a given criterion (such as ultra low latency) than about an adequate global performance (multiple requirements: max latency, average latency, perceived interactive latency, throughput...) on a high-yield machine (more often than not the implication being that it simultaneously has many different and changing missions).
Something I ~never see mentioned in mmap discussions is that it completely bypasses the expensive syscall transition for read calls, which has only grown rapidly in cost thanks to all the speculative execution mitigations.
In benchmarking I found an mmap approach to be integral to achieving maximum performance in IO-heavy workloads on modern OSes [0]. (Note that it still is a win even with mitigations disabled.)
Unless I’m completely missing your point, and to be fair I might be because it’s late in Europe and I should have gone to bed hours ago, read speeds due to bypassing expensive syscall overhead is an often cited part of the mmap discussion.
The problem with using mmap-based IO is you generally depend on the kernel's async readahead/readaround to keep things fast while writing blocking-style, obvious procedural style code, but it's totally naive, and sequential relative to the faulted addresses, much like a spinning disk prefers to be read.
That worked well when the storage system was made of spinning disks, and you were incentivized to use data structures laying data out appropriate for that access pattern. It was all complementary and cooperated pretty well.
Then SSDs became commonplace.
Today you want to exploit their fast random access, utilizing whatever data structures make the most sense in a world without seek times. Introducing mmap() into that stack kind of reintroduces spinning disk style performance characteristics, if you're relying on mmap()'s async readahead/readaround magic to keep your accesses from blocking on IO.
I'm not saying mmap() was ever a great choice for a database. But it's really awful for random access patterns until everything's hot in the page cache.
This happens to be a large part of why systemd-journald's journals can be slow to process w/`journalctl -u` or `systemctl status $service` type queries when cold. The access patterns are very random combined with tiny objects being read, while the kernel goes off prefetching heaps of ~unrelated nearby pages in the hopes of preventing blocking subsequent accesses.
With the caveat that I have not looked at this in over a decade, readahead via madvise() is imprecise to the point of near uselessness for high-throughput database workloads. The biggest issue is that, as the name implies, Linux is free to ignore madvise() or do something that is not quite what you requested, and often does. Many types of finely choreographed locality optimizations require more determinism than it offers.
> That worked well when the storage system was made of spinning disks, and you were incentivized to use data structures laying data out appropriate for that access pattern. It was all complementary and cooperated pretty well.
> Then SSDs became commonplace.
You are laughably wrong. Random I/O is random I/O whether you do it using lseek/read or whether you access a page offset in a mmap. And we've got hundreds of hours of benchmarks that show that LMDB outperforms everything else, whether on spinning rust or solid state. http://www.lmdb.tech/bench/
My comment isn't really targeted at LMDB specifically, it's more generally regarding mmap().
If you design the data format to work well on a spinning disk, it should work well with an mmap based access. That's what my comment implies, and it's completely consistent with what you're saying regarding the benchmarks.
> The ones who got it wrong are irrelevant, because correct solutions clearly exist for all the potential problems.
This is a pretty weak argument. Correct solutions exist for doing extremely unsafe things, but that doesn't mean using safer approaches is bad. If a bunch of different projects get something wrong, yes that _is_ a signal that you should think twice before using it yourself.
You need to understand (well) what the kernel is going to do. That's more difficult than if you call read/write yourself (because their semantics are well defined). Otoh the problem is significantly less than it was back in the day because there's really only one kernel now.
Welp, back in college I wrote a virtual memory demand pager for IBM 370 mainframe. I also read the entire 4.3BSD kernel source, as well as the Minix kernel source, and hacked on both of them. Also ported NFS server and client to the mainframe. After college, wrote VMEbus device drivers for Sun4 SPARC/Solaris, and a couple drivers for Linux and Windows as well. I'm pretty familiar with what any given kernel does.
I wrote redb (https://github.com/cberner/redb) using mmap, initially. However, I later removed it and switched to read()/write() with my own user space cache. I'm sure it's not as good as the OS page cache, but the difference was only 1.2-1.5x performance on the benchmarks I cared about, and the cache is less than 500 lines of code.
Also, by removing mmap() I was able to remove all the unsafe code associated with it, so now redb is memory-safe.
500 lines of code is still 500 lines of added complexity. For LMDB that'd be a 7% increase in LOCs, which would also introduce the need for manual cache configuration and tuning (further increasing complexity for the end user) and a 50% performance loss? Doesn't seem like a good tradeoff to me.
In the days of yore, everyone eschewed mmap because it required platform specific tuning. Then everyone switched to one platform and continued to eschew mmap because they didn't want to read the docs.
Sure, you can manifest destiny and write it all yourself, and many do, but if you learn how to make mmap really fly, then you can do that again and again without having to even so much as smell a DBMS.
The Linux kernel defaults are pretty horrendous for anything resembling high performance hardware, let alone disks that act like memory, but it can most comfortably accommodate all of those things handedly if you just configure the damn thing properly.
The authors are very correct in drawing a distinction between read-only mmaps and writable mmaps. Read-only is pretty safe -- the biggest concern is probably sanity-checking data being read from disk, but for some applications on-disk corruption isn't a big concern anyway -- while writable mmaps need very careful use of msync to ensure crash safety and it's very easy to have subtle bugs in that sort of code.
On the other hand, they hand-wave away I/O stalls saying that the application is going to stall regardless of whether disk reads are implicit or explicit; this fails to account for the possible advantages of narrowing down when a stall might occur. A DBMS might be servicing many requests at once; using explicit I/O, blocking reads could be shunted off to a different context (dedicated I/O threads, I/O request rings, etc) allowing unblocked operations to complete without waiting.
The authors also make the odd claim that "[LMDB's] B+tree design is naturally optimal with an LRU cache", which is highly suspect in principle (LRU is a standard not-horribly-bad cache eviction scheme, but it's hard to imagine it being optimal for anything but a trivial workload) but also ignores the fact that a database inherently knows which pages it doesn't need any more. This can be communicated to the kernel with madvise, but that adds more syscalls with inherent overhead.
Finally, there's an issue of paging granularity: If you have a database with a large amount of data in core, you really want to be using superpages in order to reduce your TLB miss costs -- but you can't mmap data with superpages if you want the kernel to be able to evict unused pages.
In short: Using mmap in a database absolutely can work, especially if (like the authors) you're only doing it read-only; but the case for using mmap is nowhere near as strong as the authors make it out to be.
> hand-wave away I/O stalls
> A DBMS might be servicing many requests at once;
Yes, a DBMS may be servicing many requests at once, which is why individual stalls don't matter. Other threads will be making progress.
> a database inherently knows which pages it doesn't need any more.
DBMS engineers always make this BS claim and that's what it is, BS.
You may know exactly what information you need for a single given query. But you don't know what the next query will be. You don't know if the next query will need the same indices or something else entirely. If you throw something away because you're done with it on one query, and it's referenced again on the next, you'll have pessimized your performance for no good reason.
TLB miss costs - this is totally irrelevant. Go check out any benchmark you can find of LMDB against any other DBMS. Whether conducted by us or any 3rd party. Find any system that gets anywhere close to LMDB's read performance and scalability under heavy concurrent load, and prove that TLB misses are costing LMDB efficiency.
Yes, a DBMS may be servicing many requests at once, which is why individual stalls don't matter. Other threads will be making progress.
That works if you have a thread per request. Not all servers are structured this way; thread-per-CPU with non-blocking I/O is increasingly popular.
DBMS engineers always make this BS claim and that's what it is, BS. You may know exactly what information you need for a single given query. But you don't know what the next query will be.
Let me rephrase that: A database doesn't know which data is most likely to be used again, but if does know which pages are guaranteed to not be used again because they're not reachable in the b+tree.
Find any system that gets anywhere close to LMDB's read performance and scalability under heavy concurrent load [...]
I would be interested to see how LMDB compares to Kivaloo. In my benchmarking (40 byte keys, 40 byte values, single core on my laptop, highly parallel workload, in core) I get 10^6 reads per second over the network; if I understand correctly LMDB doesn't serve a network protocol but is at a similar level of performance?
> A database doesn't know which data is most likely to be used again, but if does know which pages are guaranteed to not be used again because they're not reachable in the b+tree.
This is true, but it may not be as helpful as it initially seems. Because it is very likely the the next mutation then writes to this unused page. So the window where that page is wasting cache capacity is quite small.
> You may know exactly what information you need for a single given query. But you don't know what the next query will be. You don't know if the next query will need the same indices or something else entirely.
I think this misrepresents how many modern database engines work. Queries are generatively decomposed into many thousands (or millions) of independent page operations, depending on the amount of data they necessarily touch, before they get to the execution queue. Ops from concurrent queries are all blended together. The I/O and execution scheduler can, in fact, see upwards of a million page operations into the future across all concurrent operations in some systems and adaptively, dynamically reorder the entire schedule to optimize for locality across concurrent operations while preserving invariants. This enables powerful optimizations that circumvent theoretical limits on cache effectiveness and improves locality under high concurrency in ways simple caching cannot. This is not a new idea, it is how silicon is designed to deal with data access patterns that intrinsically have poor cache locality. A modern server can retire tens of millions of these ops per second, so you can get incredible throughput with tight tail latencies because, again, you control what happens and when. This works beautifully even when the working storage is orders of magnitude larger than available memory. It does require exquisitely fine control of I/O and execution scheduling as a matter of architecture.
It is worth acknowledging that the throughput limits are not an mmap() problem. Most non-mmap() database kernels struggle to saturate modern storage hardware too. Classic database architectures are not effective at consistently and inexpensively generating enough concurrency to use the available hardware.
I used to use mmap for database kernel-y stuff. The recurring pain point was that it is impossible to saturate fast storage arrays using it for many real-world workloads when the data won’t mostly fit in memory, and the computational cost of trying to do so was high. And then I did a stint in supercomputing where it turned out everyone knew you could circumvent these limits in highly parallel systems with precise I/O and execution scheduling, and relying much less on caching, but those people don’t work on databases.
"circumvent these limits in highly parallel systems with precise I/O and execution scheduling, and relying much less on caching, but those people don’t work on databases."
Can I bug you for a library, book, algo, gpu i/o card or whatever good stuff you may be referring to there?
Tragically, supercomputing is mostly dead as a hardcore research area AFAICT, and they rarely published in no small part because so much of the research was funded by US intelligence agencies. It was pure serendipity that I ended up in that world; I solved a theoretical CS problem that was particularly interesting to people working in that space and was given free supercomputing time to do further research (which was awesome). I learned a lot about how to think about software at extreme scales from the graybeards in HPC. I was one of the few young people in the space even back then.
To answer your question, almost all of the valuable theory comes from research in silicon architectures designed to hide latency, with graph analysis as the canonical problem case. It is the question of how to get the most throughput out of silicon that is frequently waiting for a cache line to fill or a lock to release. In silicon, this typically refers to barrel processors specifically and the most refined form of that was arguably the Cray XMT. In modern silicon, you don’t have to squint too hard to see that GPUs are a specialized type of barrel processor.
The less obvious aspect is that you can do very effective latency-hiding in software, but how is poorly documented. Nonetheless, if you study how latency-hiding silicon works, it isn’t that hard to figure out how to design a software architecture that has similar properties albeit with fewer guarantees than silicon offers. Latency hiding silicon works by having a huge number of operations in flight at any one time, surveying the landscape, and choosing the operation that is mostly likely to make forward progress. Software has the advantage that it can look much further into the future of operations than silicon can and in many ways is actually more efficient even though you have less control of the fine details.
Before we go any further here, you should all read the original LMDB design paper, to get a grasp of what we traded away first. https://openldap.org/pub/
I love lmdb and mmap, but I wish there was prefix compression for keys. I'm on the fence between rocksdb and lmdb, both using mmap and will likely support both. My database file was so much smaller with rocksdb because it compresses segments, but lmdb is so much more concise and will never do background jobs like rocksdb. One can use different subtables in lmdb, but the amount must be set up front with mdb_env_set_maxdbs and it says that there is a linear search involved.
Prefix compression adds a lot of complexity. If you insert a new record that makes an existing prefix non-unique, you then have to expand and rewrite every key in the page, and that will ripple up to every parent page as well. And the expansion can then cause the records to no longer fit in their current page, so then you need to do a bunch of page splits. It's gross and ugly and easy to get wrong. (The btree.c that LMDB was based on has prefix compression. We ripped it out after finding bugs in it.) If your data values are small enough, you can use DUPSORT records instead, and manage your prefixes manually.
There is a linear search involved to open a DBI handle, yes. But you only do that once, and keep it open for the life of the program. Not a big deal.
If you are a DBMS kernel developer, the most urgent need is how to control memory more precisely to prevent out-of-memory (OOM) situations. Clearly, MMAP cannot achieve this, which is also why most databases still use their own memory pool + direct-IO.
Clearly you have no idea what you're talking about. With a read-only mmap you don't need to do anything, OOM won't happen*. All of the pages of the map are clean; whenever there's memory pressure the OS can just reclaim those pages from the page cache and use them to meet other demands. That page re-use is zero cost; since the pages are clean they don't require a flush or pageout before they can be reused. Using a read-only mmap means the DB will never be the cause of an OOM situation, and will never be the cause of swap usage.
*on Linux you must lower /proc/sys/vm/swappiness from its default of 60, otherwise the kernel won't reclaim FS cache pages.
Imagine you're using a EC2 to run several DBMS instances at the same time, each for a different customer. How do you make sure that each instance only uses a certain amount of memory and doesn't affect the others?
In Linux, you use cgroups to confine a process to a fixed memory limit that won't cause an OOM in adjacent processes. You can create a separate memory cgroup with a different allowance for each customer depending how much memory is allotted to them per the contract, for example.
You can also use ulimit with a hard memory limit, but cgroups are more fine grained and flexible.
Also do note that the point about the read-only mmap still holds – it can't cause an OOM, it is mmap'd pages pointing to dirty pages that have not been written out to the file system yet that can – on the condition their number is growing uncontrollably and/or fast.
P.S. But allowing a database to cause an OOM is never a good idea to start off with whether memory limits have been set or not – the data loss is unacceptable for a database, and databases have been optimised to operate within pre-configured space constraints that do not even require ulimit/cgroup in the first place. Perhaps fixing the database configuration is a better starting point rather than going down the rabbit hole with mmap(2).
We manage memory directly within the DBMS, for instance, by setting MySQL's innodb_buffer_pool_size to 1GB. This precise control method ensures that each cloud-based DBMS instance on our large EC2 instances remains within its memory limit without adversely affecting others.
When the internal memory pool limit of the DBMS is reached, we understand that it will spill dirty pages to disk and utilize the write-ahead log to guarantee ACID properties in the event of a crash. This process is predictable and manageable. In contrast, the effects on the DBMS when cgroup memory limits are reached are less clear, introducing uncertainty into system behavior under memory pressure. This unpredictability strongly supports our preference for managing memory within the DBMS itself.
Our experience over a decade with cloud DBMS products has shown that mmap doesn't suit our needs. We prioritize direct memory management methods within the DBMS to ensure system reliability and optimal performance.
And if you'd read the reliability references linked in the article, you'd see that MariaDB/InnoDB's reliability is the worst of many tested systems. LMDB's is flawless.
The one fault they found for LMDB, caused by fdatasync not updating the DB filesize, was actually a kernel/filesystem bug (fdatasync is documented to update the filesize) that had already been fixed two years before these guys did their research. Not an LMDB flaw.
Please don't misunderstand me; I've also implemented tokudb_buffer_pool_size for TokuDB because their control over memory is excellent, not falling into the black hole of the page cache. This allows my DBMS to be stable enough. This is also my point in this post, and my discussion ends here.
> memcpy() (ie "read()" in this case) is _always_ going to be faster in many
> cases, just because it avoids all the extra complexity. While mmap() is
> going to be faster in other cases.
> - Linus Torvalds [0]
At least a long-running db process can amortize the page table costs across many operations, unlike something ephemeral like journalctl/systemctl where it really hurts.
About 20 years ago, I worked on a server application that used mmap for its database. At startup, it read all the pages into memory, so all data was "hot", ready to go. It also built its in-memory indexes at the same time.
It worked incredibly well, handling 1000's of simultaneous clients. This was the main enterprise application responsible for 100's of millions in revenue for a large organization. It wasn't a general purpose solution, though. The system also fed more standard relational databases for reporting purposes, using a custom change data capture process.
78 comments
[ 3.0 ms ] story [ 158 ms ] threadWould be really interesting to have him discuss with Andy Pavlo :)
Everything has compromises and trade-offs. LMDB looks great. But it's also, like a lot of similar systems, built to perform best at single-writer / multiple-reader workloads. That's not the only workload out there.
Single-writer is all you need if each write is fast enough.
BerkeleyDB, which we used before writing LMDB, is multi-writer. It's still slower than LMDB in every workload, because of all of the lock management that comes with being multi-writer.
https://www.youtube.com/watch?v=tEa5sAh-kVk
Feel free to point out specific arguments that you think need further fleshing out. Every aspect of LMDB's design and performance characteristics have been documented already, happy to link you to answers to any of your questions.
Where they’re wrong is about the performance analysis:
> In section 3.2 "I/O stalls" is again a non-issue; no matter how your DBMS handles I/O internally, synchronously or asynchronously, the calling application can't make any progress until the I/O completes, and if the data isn't already in memory then the application must wait.
A TLB shoot down request to pull in a page or evict it can cause pauses not just in your own application but also many others because it’s basically a system wide mutex. There is a trade off obviously where the kernel can evict I/O buffers more efficiently. But to me all that says is that the interface for managing I/O buffers in user space is really immature and needs some better performing API so that we have something in between mmap and buffer management. Also an asynchronous application can switch to doing other work. If your synchronous memory access is blocking your thread, other unrelated work is being blocked.
As for workload optimization, I think OP is overstating how much sharing resources mitigates this - when I’m doing a blind search through all data for some reason (maybe some kind of background GC) or a range lookup I can choose to not cache any of that data. Similarly, if I’m doing a point lookup I can do a pre read. However, mmap has no higher level concept about the workload that’s accessing the memory. This a very real problem the kernel tried to tackle back in the 90s / early 00s when disk indexing was starting out - a disk index would cause the cache for all other apps to be evicted resulting in waking up to a sluggish machine paging everything back in.
The more high level context you can retain, the better your decision making about resource allocation is. When that high level context is lost/discarded you lose efficiency.
This was essentially the argument against adding the raw device support to Linux, which delayed the Oracle database Linux port for years, with Linus himself being adamant that operating system's own VMM and page cache management was superior to that of the database (except it was not), which was proven to be a fallacy as the transaction and error handling database requires completely different guarantees, and the VMM pursuing different design objectives that most of the time are incompatible with the database expectations.
The raw devices have been used precisely for that reason: «let's bypass the VMM and the page cache for this device, and we will take it from there». That is what the Oracle database did on Solaris – it wanted an entire raw device that it would claim for the table space. Granted, Oracle has had its own VMM and page cache (so to speak) implementation within the DB, an OS mini-kernel if you like.
The argument was eventually settled with adding the O_DIRECT flag to open(2) accomplishing the same outcome, and the raw devices have never made into Linux.
Not saying more work in the space wouldn't be welcome and interesting, just that it's generally the assumption whenever I've seen O_DIRECT (since the Solaris days and through today) that what's using it is the only thing of substance on the box.
Besides, O_DIRECT can be used at the file level (and the file system level as well via chattr – if the file system supports it) whereas the raw devices are, well, device level only.
But yeah, I understand you weren’t talking about buffers, I was just highlighting that O_DIRECT and raw devices are totally separate problems from having a user space cache that can be evicted by the kernel memory and reconstructed by the application lazily.
I've not yet bothered to check how things work with raw devices in Windows. I believe only Admins can even operate on them so it would be kind of limited usefulness.
I tried both regular IO and mmap and was unable to make regular IO as fast as mmap.
This is on a machine with 32 real cores running 64 job threads, saturating all of them with jobs. The jobs are a mixture of small (metadata) and big (textures and models) files. In theory, this should be a pretty bad situation for the TLB shootdown, and I was concerned about them.
But in reality it seemed to be fine, and a fair amount faster than with regular IO due to being able to have one less extra copy of the data.
In terms of regular io, did you remember to do O_DIRECT? Also yes, I/O paths are slower than mmap for pure throughput in most cases. Databases are a special snowflake though. In some ways you’d want the I/O layer in the kernel like with a filesystem which is why databases typically go the other way and try to bypass the kernel to keep their code in user space
If you don't know about it already, you should look at Viktor Leis' et al's work on this -- kernel module + supporting buffer mgmt code to do the kind of thing you're talking about. The code is not production quality, but the idea is nifty:
https://github.com/viktorleis/vmcache
https://github.com/tuhhosg/exmap
https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/_my_direct_up...
I've personally experimented a bit with userfaultfd and this kind of thing, but it's got issues.
Relatedly there’s an effort going on in the filesystem space for a long time to add transaction support which would also be useful. Some day.
https://www.spinics.net/lists/linux-fsdevel/msg70047.html
Trying to implement actual transactions can't work because it requires the FS to maintain unbounded state. https://lore.kernel.org/all/5283E6DC.8000801@symas.com/
Just like those paper's authors can claim using mmap increases complexity when they can find any DBMS with LMDB's features, in fewer lines of code.
Benchmarks all show that LMDB performance scales perfectly linearly across arbitrarily many CPUs. If this effect were an actual issue then the performance scaling should be significantly sub-linear. It's not. See e.g. http://www.lmdb.tech/bench/inmem/scaling.html or even the redb benchmark https://mastodon.social/@hyc/111887593549586249
The notion that "maybe their performance floor was higher" is laughable, since no other DBMS delivers anywhere near LMDB's read performance.
What I said was that lmdb’s read performance may be so good, that at its worst when you’re seeing cross tlb shootdowns, it’s still better than the other DBs. You seem to contradict me and then restate the exact same thing.
> Benchmarks all show that LMDB performance scales perfectly linearly across arbitrarily many CPUs
As I said, synthetic benchmarks may not reproduce the cross tlb shootdown scenario frequently enough for you to notice it. It’s like frame stuttering - you can’t argue that it’s not happening by saying the average frame rate was 70fps. The data you’re using to support your argument isn’t a relevant measure. You’d have to actually measure how frequently cross tlb shootdowns are happening (via dtrace probably) and ideally compare it against a robust lmdb read path written against iouring to get an accurate measure of the issue.
And of course, none of this is working in a realtime environment, so a couple nanoseconds here or there just doesn't matter.
I really don’t understand this defensiveness and doubling down on something that’s pretty well studied and documented. Keep in mind that the original paper looked at raw mmap vs raw io api issues regardless of the surrounding DB: https://www.cidrdb.org/cidr2022/papers/p13-crotty.pdf
It’s a really well written and accessible paper and this is not the hill to die on if you’re disagreeing. I agree mmap for the read path only is a weakness in their paper and that idea I agree has some merit. But cross tlb shootdowns are a real performance downside of this approach.
Him doubling down makes sense, given that LMDB continues to offer the best read performance in any benchmark, regardless of who performed it.
If tlb shoot down times are such a problem, why aren't we seeing it being represented in any DB benchmark?
We tell no lies. Those tests were run on an HP DL585 G5 server with 128GB of RAM and 4 quad core AMD Opteron 8354 CPUs. If cross-TLB shootdowns were actually as big a problem as they claim, there should be massive latency spikes due to cross-socket communication, far worse than for inter-core single socket.
You're definitely misreading the graphs, the Y axis is clearly labeled "msec". You're going to have to pay better attention if you want to discuss this further. Otherwise we're just wasting our time.
> Keep in mind that the original paper looked at raw mmap vs raw io api issues regardless of the surrounding DB
Yes, but that's exactly why the paper is utterly worthless and never should have made it past peer review. Their initial claim is this:
> Unfortunately, mmap has a hidden dark side with many sordid problems that make it undesirable for file I/O in a DBMS. As we describe in this paper, these problems involve both data safety and system performance concerns. We contend that the engineering steps required to overcome them negate the purported simplicity of working with mmap. For these reasons, we believe that mmap adds too much complexity with no commensurate performance benefit and strongly urge DBMS developers to avoid using mmap as a replacement for a traditional buffer pool.
To prove their claims they would have to have demonstrated that a DBMS using mmap was more complex and less reliable than one using a traditional buffer pool. They also had to demonstrate that a DBMS using mmap had no performance benefit vs a DBMS using a traditional buffer pool. They didn't demonstrate any of these things, and LMDB is concrete proof that all of these claims are wrong: at only 7KLOCs it is simpler than every other traditional DBMS, its reliability is literally perfect, and its read performance is always orders of magnitude than all traditional designs.
The reviewers should have known just from reading the abstract that this paper was a dud:
> Such problems make it difficult, if not impossible, to use mmap correctly and efficiently in a modern DBMS.
Their claim required them to prove a negative, which obviously defies the rules of logic. Everything after that was just noise.
Absolutely brutal read on RavenDB.
https://news.ycombinator.com/item?id=39204622
10 days ago
Mmap is so simple for the application/developer, but the price you pay is giving up clear ownership of memory and clean separation between kernel page cache and application space. The interaction between the mmu, mmap, tlb and the linux kernel IO layer is complicated. You don't want to touch that complexity at all if you care about ultra low latency.
The article rephrases the question into
but I would rephrase it again into questioning why fairly straight forward concepts like a buffer cache can't be implemented directly in the application?This is less about a given criterion (such as ultra low latency) than about an adequate global performance (multiple requirements: max latency, average latency, perceived interactive latency, throughput...) on a high-yield machine (more often than not the implication being that it simultaneously has many different and changing missions).
In benchmarking I found an mmap approach to be integral to achieving maximum performance in IO-heavy workloads on modern OSes [0]. (Note that it still is a win even with mitigations disabled.)
[0]: https://neosmart.net/blog/using-simd-acceleration-in-rust-to...
That worked well when the storage system was made of spinning disks, and you were incentivized to use data structures laying data out appropriate for that access pattern. It was all complementary and cooperated pretty well.
Then SSDs became commonplace.
Today you want to exploit their fast random access, utilizing whatever data structures make the most sense in a world without seek times. Introducing mmap() into that stack kind of reintroduces spinning disk style performance characteristics, if you're relying on mmap()'s async readahead/readaround magic to keep your accesses from blocking on IO.
I'm not saying mmap() was ever a great choice for a database. But it's really awful for random access patterns until everything's hot in the page cache.
This happens to be a large part of why systemd-journald's journals can be slow to process w/`journalctl -u` or `systemctl status $service` type queries when cold. The access patterns are very random combined with tiny objects being read, while the kernel goes off prefetching heaps of ~unrelated nearby pages in the hopes of preventing blocking subsequent accesses.
> Then SSDs became commonplace.
You are laughably wrong. Random I/O is random I/O whether you do it using lseek/read or whether you access a page offset in a mmap. And we've got hundreds of hours of benchmarks that show that LMDB outperforms everything else, whether on spinning rust or solid state. http://www.lmdb.tech/bench/
If you design the data format to work well on a spinning disk, it should work well with an mmap based access. That's what my comment implies, and it's completely consistent with what you're saying regarding the benchmarks.
This is a pretty weak argument. Correct solutions exist for doing extremely unsafe things, but that doesn't mean using safer approaches is bad. If a bunch of different projects get something wrong, yes that _is_ a signal that you should think twice before using it yourself.
But at least you thought about the decision. Nice benchmark, by the way. https://mastodon.social/@hyc/111887577620902329
Sure, you can manifest destiny and write it all yourself, and many do, but if you learn how to make mmap really fly, then you can do that again and again without having to even so much as smell a DBMS.
The Linux kernel defaults are pretty horrendous for anything resembling high performance hardware, let alone disks that act like memory, but it can most comfortably accommodate all of those things handedly if you just configure the damn thing properly.
The authors are very correct in drawing a distinction between read-only mmaps and writable mmaps. Read-only is pretty safe -- the biggest concern is probably sanity-checking data being read from disk, but for some applications on-disk corruption isn't a big concern anyway -- while writable mmaps need very careful use of msync to ensure crash safety and it's very easy to have subtle bugs in that sort of code.
On the other hand, they hand-wave away I/O stalls saying that the application is going to stall regardless of whether disk reads are implicit or explicit; this fails to account for the possible advantages of narrowing down when a stall might occur. A DBMS might be servicing many requests at once; using explicit I/O, blocking reads could be shunted off to a different context (dedicated I/O threads, I/O request rings, etc) allowing unblocked operations to complete without waiting.
The authors also make the odd claim that "[LMDB's] B+tree design is naturally optimal with an LRU cache", which is highly suspect in principle (LRU is a standard not-horribly-bad cache eviction scheme, but it's hard to imagine it being optimal for anything but a trivial workload) but also ignores the fact that a database inherently knows which pages it doesn't need any more. This can be communicated to the kernel with madvise, but that adds more syscalls with inherent overhead.
Finally, there's an issue of paging granularity: If you have a database with a large amount of data in core, you really want to be using superpages in order to reduce your TLB miss costs -- but you can't mmap data with superpages if you want the kernel to be able to evict unused pages.
In short: Using mmap in a database absolutely can work, especially if (like the authors) you're only doing it read-only; but the case for using mmap is nowhere near as strong as the authors make it out to be.
Yes, a DBMS may be servicing many requests at once, which is why individual stalls don't matter. Other threads will be making progress.
> a database inherently knows which pages it doesn't need any more.
DBMS engineers always make this BS claim and that's what it is, BS. You may know exactly what information you need for a single given query. But you don't know what the next query will be. You don't know if the next query will need the same indices or something else entirely. If you throw something away because you're done with it on one query, and it's referenced again on the next, you'll have pessimized your performance for no good reason.
TLB miss costs - this is totally irrelevant. Go check out any benchmark you can find of LMDB against any other DBMS. Whether conducted by us or any 3rd party. Find any system that gets anywhere close to LMDB's read performance and scalability under heavy concurrent load, and prove that TLB misses are costing LMDB efficiency.
That works if you have a thread per request. Not all servers are structured this way; thread-per-CPU with non-blocking I/O is increasingly popular.
DBMS engineers always make this BS claim and that's what it is, BS. You may know exactly what information you need for a single given query. But you don't know what the next query will be.
Let me rephrase that: A database doesn't know which data is most likely to be used again, but if does know which pages are guaranteed to not be used again because they're not reachable in the b+tree.
Find any system that gets anywhere close to LMDB's read performance and scalability under heavy concurrent load [...]
I would be interested to see how LMDB compares to Kivaloo. In my benchmarking (40 byte keys, 40 byte values, single core on my laptop, highly parallel workload, in core) I get 10^6 reads per second over the network; if I understand correctly LMDB doesn't serve a network protocol but is at a similar level of performance?
This is true, but it may not be as helpful as it initially seems. Because it is very likely the the next mutation then writes to this unused page. So the window where that page is wasting cache capacity is quite small.
I think this misrepresents how many modern database engines work. Queries are generatively decomposed into many thousands (or millions) of independent page operations, depending on the amount of data they necessarily touch, before they get to the execution queue. Ops from concurrent queries are all blended together. The I/O and execution scheduler can, in fact, see upwards of a million page operations into the future across all concurrent operations in some systems and adaptively, dynamically reorder the entire schedule to optimize for locality across concurrent operations while preserving invariants. This enables powerful optimizations that circumvent theoretical limits on cache effectiveness and improves locality under high concurrency in ways simple caching cannot. This is not a new idea, it is how silicon is designed to deal with data access patterns that intrinsically have poor cache locality. A modern server can retire tens of millions of these ops per second, so you can get incredible throughput with tight tail latencies because, again, you control what happens and when. This works beautifully even when the working storage is orders of magnitude larger than available memory. It does require exquisitely fine control of I/O and execution scheduling as a matter of architecture.
It is worth acknowledging that the throughput limits are not an mmap() problem. Most non-mmap() database kernels struggle to saturate modern storage hardware too. Classic database architectures are not effective at consistently and inexpensively generating enough concurrency to use the available hardware.
I used to use mmap for database kernel-y stuff. The recurring pain point was that it is impossible to saturate fast storage arrays using it for many real-world workloads when the data won’t mostly fit in memory, and the computational cost of trying to do so was high. And then I did a stint in supercomputing where it turned out everyone knew you could circumvent these limits in highly parallel systems with precise I/O and execution scheduling, and relying much less on caching, but those people don’t work on databases.
Can I bug you for a library, book, algo, gpu i/o card or whatever good stuff you may be referring to there?
To answer your question, almost all of the valuable theory comes from research in silicon architectures designed to hide latency, with graph analysis as the canonical problem case. It is the question of how to get the most throughput out of silicon that is frequently waiting for a cache line to fill or a lock to release. In silicon, this typically refers to barrel processors specifically and the most refined form of that was arguably the Cray XMT. In modern silicon, you don’t have to squint too hard to see that GPUs are a specialized type of barrel processor.
The less obvious aspect is that you can do very effective latency-hiding in software, but how is poorly documented. Nonetheless, if you study how latency-hiding silicon works, it isn’t that hard to figure out how to design a software architecture that has similar properties albeit with fewer guarantees than silicon offers. Latency hiding silicon works by having a huge number of operations in flight at any one time, surveying the landscape, and choosing the operation that is mostly likely to make forward progress. Software has the advantage that it can look much further into the future of operations than silicon can and in many ways is actually more efficient even though you have less control of the fine details.
You can also watch the presentation at CMU https://www.youtube.com/watch?v=tEa5sAh-kVk (slides are here http://www.lmdb.tech/SymasDocs/20151008-CMU-LMDB.pdf )
There is a linear search involved to open a DBI handle, yes. But you only do that once, and keep it open for the life of the program. Not a big deal.
If you are a DBMS kernel developer, the most urgent need is how to control memory more precisely to prevent out-of-memory (OOM) situations. Clearly, MMAP cannot achieve this, which is also why most databases still use their own memory pool + direct-IO.
Clearly you have no idea what you're talking about. With a read-only mmap you don't need to do anything, OOM won't happen*. All of the pages of the map are clean; whenever there's memory pressure the OS can just reclaim those pages from the page cache and use them to meet other demands. That page re-use is zero cost; since the pages are clean they don't require a flush or pageout before they can be reused. Using a read-only mmap means the DB will never be the cause of an OOM situation, and will never be the cause of swap usage.
*on Linux you must lower /proc/sys/vm/swappiness from its default of 60, otherwise the kernel won't reclaim FS cache pages.
You can also use ulimit with a hard memory limit, but cgroups are more fine grained and flexible.
Also do note that the point about the read-only mmap still holds – it can't cause an OOM, it is mmap'd pages pointing to dirty pages that have not been written out to the file system yet that can – on the condition their number is growing uncontrollably and/or fast.
P.S. But allowing a database to cause an OOM is never a good idea to start off with whether memory limits have been set or not – the data loss is unacceptable for a database, and databases have been optimised to operate within pre-configured space constraints that do not even require ulimit/cgroup in the first place. Perhaps fixing the database configuration is a better starting point rather than going down the rabbit hole with mmap(2).
We manage memory directly within the DBMS, for instance, by setting MySQL's innodb_buffer_pool_size to 1GB. This precise control method ensures that each cloud-based DBMS instance on our large EC2 instances remains within its memory limit without adversely affecting others.
When the internal memory pool limit of the DBMS is reached, we understand that it will spill dirty pages to disk and utilize the write-ahead log to guarantee ACID properties in the event of a crash. This process is predictable and manageable. In contrast, the effects on the DBMS when cgroup memory limits are reached are less clear, introducing uncertainty into system behavior under memory pressure. This unpredictability strongly supports our preference for managing memory within the DBMS itself.
Our experience over a decade with cloud DBMS products has shown that mmap doesn't suit our needs. We prioritize direct memory management methods within the DBMS to ensure system reliability and optimal performance.
And if you'd read the reliability references linked in the article, you'd see that MariaDB/InnoDB's reliability is the worst of many tested systems. LMDB's is flawless.
https://lists.openldap.org/hyperkitty/list/openldap-devel@op...
The one fault they found for LMDB, caused by fdatasync not updating the DB filesize, was actually a kernel/filesystem bug (fdatasync is documented to update the filesize) that had already been fixed two years before these guys did their research. Not an LMDB flaw.
[0] https://yarchive.net/comp/mmap.html
- https://news.ycombinator.com/item?id=36563187
- https://news.ycombinator.com/item?id=29936104
- https://news.ycombinator.com/item?id=31504052
This is totally unacceptable in most circumstances I am familiar with.
It worked incredibly well, handling 1000's of simultaneous clients. This was the main enterprise application responsible for 100's of millions in revenue for a large organization. It wasn't a general purpose solution, though. The system also fed more standard relational databases for reporting purposes, using a custom change data capture process.