4 ms·

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

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

cperciva 3y ago
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?
- kevincox 3y ago
  > 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.
jandrewrogers 3y ago
> 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.
- scrubs 3y ago
  "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?

cperciva 3y ago

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?

kevincox 3y ago
> 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.

jandrewrogers 3y ago

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

scrubs 3y ago
"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?