3 ms·

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 LM

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.

inkyoto 3y ago
> 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.
- vlovich123 3y ago
  O_DiRECT is insufficient because you have no way to coordinate with the kernel to drop io buffers when there’s memory pressure
  - ericbarrett 3y ago
    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.
    - vlovich123 3y ago
      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).
  - inkyoto 3y ago
    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.
    - vlovich123 3y ago
      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.
Negitivefrags 3y ago
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.
- vlovich123 3y ago
  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
cmrdporcupine 3y ago
> 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: https://github.com/viktorleis/vmcache https://github.com/viktorleis/vmcache https://github.com/tuhhosg/exmap https://github.com/tuhhosg/exmap https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/_my_direct_uploads/vmcache.pdf 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.
- vlovich123 3y ago
  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.
  - hyc_symas 3y ago
    Transactions in the filesystem API is misguided and useless. All you need is to expose command tagging to user level, probably with some fcntl: https://www.spinics.net/lists/linux-fsdevel/msg70047.html 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/ https://lore.kernel.org/all/5283E6DC.8000801@symas.com/
    - vlovich123 3y ago
      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.
hyc_symas 3y ago
You can say the performance analysis is wrong, when you find any benchmarks showing that LMDB performance suffers because of it. 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.
- vlovich123 3y ago
  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).
  - hyc_symas 3y ago
    If this was a significant factor, then it should have a greater impact in high concurrency workloads, getting progressively worse across multi-socket machines. 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 http://www.lmdb.tech/bench/inmem/scaling.html or even the redb benchmark https://mastodon.social/@hyc/111887593549586249 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.
    - vlovich123 3y ago
      > 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.

inkyoto 3y ago

> 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.

vlovich123 3y ago
O_DiRECT is insufficient because you have no way to coordinate with the kernel to drop io buffers when there’s memory pressure
- ericbarrett 3y ago
  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.
  - vlovich123 3y ago
    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).
- inkyoto 3y ago
  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.
  - vlovich123 3y ago
    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.

Negitivefrags 3y ago

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.

vlovich123 3y ago
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

cmrdporcupine 3y ago

> 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: https://github.com/viktorleis/vmcache https://github.com/viktorleis/vmcache https://github.com/tuhhosg/exmap https://github.com/tuhhosg/exmap https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/_my_direct_uploads/vmcache.pdf 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.

vlovich123 3y ago
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.
- hyc_symas 3y ago
  Transactions in the filesystem API is misguided and useless. All you need is to expose command tagging to user level, probably with some fcntl: https://www.spinics.net/lists/linux-fsdevel/msg70047.html 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/ https://lore.kernel.org/all/5283E6DC.8000801@symas.com/
  - vlovich123 3y ago
    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.

hyc_symas 3y ago

You can say the performance analysis is wrong, when you find any benchmarks showing that LMDB performance suffers because of it. 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.

vlovich123 3y ago
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).
- hyc_symas 3y ago
  If this was a significant factor, then it should have a greater impact in high concurrency workloads, getting progressively worse across multi-socket machines. 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 http://www.lmdb.tech/bench/inmem/scaling.html or even the redb benchmark https://mastodon.social/@hyc/111887593549586249 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.
  - vlovich123 3y ago
    > 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.