4 ms·

Mmaping directly readable data is certainly a way of avoiding the problems PHK is talking about, and can be reasonably efficient. Sendfile can be even better if

Mmaping directly readable data is certainly a way of avoiding the problems PHK is talking about, and can be reasonably efficient. Sendfile can be even better if you can structure things to have a metadata index that's in memory or mmaped, and never need to read the actual sent data. But mmap is no panacea. It's big flaw is that the kernel scheduler often doesn't know as much as your app about what you're doing. So when you touch an out of core page and it page faults, your thread just gets locked up. Worse, the kernel's read ahead logic may make the wrong guess about how many pages you're going to read, or when you want data written back out. You can try to mitigate this using madvise and msync, but in practice it's kinda brittle. Some systems use blocking io with a dedicated thread pool to wait on the block. This way the main threads can move on to other useful work rather than sitting stalled on a page fault. Golang's runtime does something like this for you automatically. Databases for the most part do their own scheduling, and may even use async io. This is because they know far better what they're actually doing than the kernel can guess. Another reason is the database's buffer cache is usually tightly coupled with the consistency control algorithm, so again, you don't want the kernel guessing, you want total control. Databases often use direct io and take on the burden of scheduling everything themselves precisely for this reason. LMDB uses mmap, but should not really be considered a database. It's just an embedded CoW btree, though a fine one. Andy Pavlo's openly published course materials are a great resource for learning about database internels. He used to be emphatically against mmap for databases, but in the last couple years has moderated that position somewhat. io_uring is looking like it will be the best overall solution moving forward, at least for linux only.

nextaccountic 5y ago
Thanks for the explanation. > io_uring is looking like it will be the best overall solution moving forward, at least for linux only. But io_uring means duplicating memory, right? There will be both my in-memory representation and the kernel cache for the file and they will be fighting each other (or at least, consuming more memory than necessary.
- jasonwatkinspdx 5y ago
  You can use io_uring with O_DIRECT, with the usual alignment restrictions. io_uring itself is carefully designed to eliminate copying even request/completion event structures.
  - nextaccountic 5y ago
    Thank you for the pointer, this seems very interesting. do you know of an example of open source code using io_uring and O_DIRECT to bypass the fs cache? What about posix_fadvise? I'm reading here https://unix.stackexchange.com/questions/6467/use-of-o-direct-on-linux https://unix.stackexchange.com/questions/6467/use-of-o-direc... that some people don't think it's a good idea to bypass the fs cache like that. Perhaps mmap could have been salvageable if it had a better error handling API.
    - jasonwatkinspdx 5y ago
      I don't know an example of that sadly. O_DIRECT is definitely doing things the hard way for sure. There's a very real risk you won't be as smart as the kernel, even knowing your app's patterns well. Linus famously has ranted against this for a long time. But like mentioned above, with databases, taking on the complexity is often warranted. I've been tinkering off and on with a database design, and one of the things I want to explore is a hybrid approach where I still have an on heap buffer cache, but misses to that cache get filled out of mmap. The buffer cache is a lock free hash table, greatly simplified by using Copy on Write pages as a fundamental part of the design (don't have to worry about racing updates or duplication races during resizing other than as performance degradations). It's still not finished and totally untested, but the way I imagine it working is the buffer cache is smaller than what you'd typically reserve for a database, and the OS can manage its page cache as a sort of L2 cache.
      - nextaccountic 5y ago
        Thanks for sharing those ideas. This sounds interesting. Is it on github?
hyc_symas 5y ago
LMDB is an embedded database engine, the same as Berkeley DB, gdbm, ndbm, etc. (except gdbm/ndbm/etc don't support multithreading, ACID transactions, various other stuff that are essential to DB operation). You use them to build other data management systems. Thus, there was a Berkeley DB backend for MySQL, just as there was a Berkeley DB backend for OpenLDAP. As storage engines go though, LMDB outclasses all the others for compactness, robustness, and efficiency. The eternal debate over app-level caching is always based on the myth that the DB application knows better about the data access patterns than the underlying kernel ever can. This may be true for some data structures, but is irrelevant in the modern computing landscape. The fact is that applications today are running on multi-tenant VMs/containers/etc and only the hypervisor and kernels have a comprehensive view of the resource demands of the entire system. Back in the days when Oracle servers ran on dedicated hardware, it was practical for the DBMS to take all decision making away from the OS, but that is not how computing is done today. Today your apps are sharing resources with countless other unknown apps, and any cache/memory optimizations your app may attempt are futile and instantly nullified by the actions of other unrelated apps in other unrelated VMs/containers. Also, as I mentioned above, the data structures make a difference. LMDB relies solely on OS page caches because only the underlying virtual memory manager really knows what's going on in the system, and also, B+trees are inherently the most cache friendly. Your app-level data access patterns just aren't going to outperform them. The tree structure inherently optimizes for LRU cache mgmt; the tree root is always hit on every access, so it is always most-often-and-recently-used. As accesses navigate down the tree to the leaf nodes, each node is successively less frequently used. The net result is that the root and interior branches naturally stay hot in a cache, and the leaf nodes naturally age out fastest, resulting in optimal cache hit rates for any access pattern. In a modern multi-tenant environment there is no scenario where an app has enough knowledge to make optimal resource mgmt decisions and outsmart the underlying OS.

nextaccountic 5y ago

Thanks for the explanation. > io_uring is looking like it will be the best overall solution moving forward, at least for linux only. But io_uring means duplicating memory, right? There will be both my in-memory representation and the kernel cache for the file and they will be fighting each other (or at least, consuming more memory than necessary.

jasonwatkinspdx 5y ago
You can use io_uring with O_DIRECT, with the usual alignment restrictions. io_uring itself is carefully designed to eliminate copying even request/completion event structures.
- nextaccountic 5y ago
  Thank you for the pointer, this seems very interesting. do you know of an example of open source code using io_uring and O_DIRECT to bypass the fs cache? What about posix_fadvise? I'm reading here https://unix.stackexchange.com/questions/6467/use-of-o-direct-on-linux https://unix.stackexchange.com/questions/6467/use-of-o-direc... that some people don't think it's a good idea to bypass the fs cache like that. Perhaps mmap could have been salvageable if it had a better error handling API.
  - jasonwatkinspdx 5y ago
    I don't know an example of that sadly. O_DIRECT is definitely doing things the hard way for sure. There's a very real risk you won't be as smart as the kernel, even knowing your app's patterns well. Linus famously has ranted against this for a long time. But like mentioned above, with databases, taking on the complexity is often warranted. I've been tinkering off and on with a database design, and one of the things I want to explore is a hybrid approach where I still have an on heap buffer cache, but misses to that cache get filled out of mmap. The buffer cache is a lock free hash table, greatly simplified by using Copy on Write pages as a fundamental part of the design (don't have to worry about racing updates or duplication races during resizing other than as performance degradations). It's still not finished and totally untested, but the way I imagine it working is the buffer cache is smaller than what you'd typically reserve for a database, and the OS can manage its page cache as a sort of L2 cache.
    - nextaccountic 5y ago
      Thanks for sharing those ideas. This sounds interesting. Is it on github?

hyc_symas 5y ago

LMDB is an embedded database engine, the same as Berkeley DB, gdbm, ndbm, etc. (except gdbm/ndbm/etc don't support multithreading, ACID transactions, various other stuff that are essential to DB operation). You use them to build other data management systems. Thus, there was a Berkeley DB backend for MySQL, just as there was a Berkeley DB backend for OpenLDAP. As storage engines go though, LMDB outclasses all the others for compactness, robustness, and efficiency. The eternal debate over app-level caching is always based on the myth that the DB application knows better about the data access patterns than the underlying kernel ever can. This may be true for some data structures, but is irrelevant in the modern computing landscape. The fact is that applications today are running on multi-tenant VMs/containers/etc and only the hypervisor and kernels have a comprehensive view of the resource demands of the entire system. Back in the days when Oracle servers ran on dedicated hardware, it was practical for the DBMS to take all decision making away from the OS, but that is not how computing is done today. Today your apps are sharing resources with countless other unknown apps, and any cache/memory optimizations your app may attempt are futile and instantly nullified by the actions of other unrelated apps in other unrelated VMs/containers. Also, as I mentioned above, the data structures make a difference. LMDB relies solely on OS page caches because only the underlying virtual memory manager really knows what's going on in the system, and also, B+trees are inherently the most cache friendly. Your app-level data access patterns just aren't going to outperform them. The tree structure inherently optimizes for LRU cache mgmt; the tree root is always hit on every access, so it is always most-often-and-recently-used. As accesses navigate down the tree to the leaf nodes, each node is successively less frequently used. The net result is that the root and interior branches naturally stay hot in a cache, and the leaf nodes naturally age out fastest, resulting in optimal cache hit rates for any access pattern. In a modern multi-tenant environment there is no scenario where an app has enough knowledge to make optimal resource mgmt decisions and outsmart the underlying OS.