Are you sure you want to use MMAP in your DBMS?
symas.com
symas.com
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.
Absolutely brutal read on RavenDB.
https://news.ycombinator.com/item?id=39204622
10 days ago
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.
Would 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.
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.
But at least you thought about the decision. Nice benchmark, by the way. https://mastodon.social/@hyc/111887577620902329
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?"
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).
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.
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...
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 )
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.
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.
> 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]
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.
This is totally unacceptable in most circumstances I am familiar with.
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.