3 ms·

Pervasive end-to-end hiding of memory cache misses using coroutines is a standard architectural feature of some database engines. It follows naturally from I/O

Pervasive end-to-end hiding of memory cache misses using coroutines is a standard architectural feature of some database engines. It follows naturally from I/O latency hiding; systems designed like the paper suggests are well over a decade old in industry. However, the devil is in the details of the scheduler design when it comes to making the performance benefits robust in real systems. The scheduler design is non-trivial because it is an inference engine that feeds back into the thing it is making inferences about, and there are temporal locality optimizations well-worth doing aside from hiding cache misses. A naive scheduler, like round-robin, can inadvertently cause the thing it prefetched to be evicted under real workloads. There are many examples of how a cache miss hiding design can suddenly turn into a cache miss creating design when the workload patterns shift modestly. At the same time, the scheduling logic, which is theoretically hard, needs to be simple enough that the cost is worth it. And you also need to manage tail latencies in real designs; robust and highly optimal schedulers in terms of aggregate throughput have a tendency to have high worst-case scheduling latencies. The tradeoff space is very complex and interacts with real design constraints in subtle ways. Even if you address all of that in the scheduler design, the efficacy of these optimizations are sensitive to the physical architecture of the CPU cache, which varies widely. The scheduling algorithms are implicitly making assumptions about the design and specification of the target silicon. tl;dr: This is a mature database technique with real benefits but robust real-world implementations are expensive to design. The code is simple, the cost is in being forced to think through the implications and edge cases so that your execution schedule doesn't get stuck in a pathological equilibrium.

Const-me 6y ago
They are different caches. The database engines you’re talking about do that for pages not found in RAM, which need to be read from disk. This article is about accessing data that’s already present in system memory. The caches they are talking about are on-chip ones, i.e. L1D and L2 caches inside CPU cores, and L3 cache shared across cores but still located on the same CPU die. Some rare CPUs like in my old laptop with Core i3-6157U even have L4 on-chip cache made of DRAM.
- jandrewrogers 6y ago
  These are not different caches. Database engines do this with system memory and CPU cache, in addition to the disk cache. If you are implementing user space I/O and execution scheduling, you are already most of the way there. In fact, some have much more advanced scheduling around the CPU cache hierarchy than what was discussed in the paper. Some database engines don’t just prefetch memory, they also dynamically reorder the execution schedule to minimize CPU cache churn and save some memory bandwidth. A good database can easily retire tens of millions of page operations per second these days, giving them a considerable look ahead window. The technique discussed in the paper has been used in many systems for a long time. This was a standard design idiom for graph databases for at least 15 years, due to their intrinsically poor locality. Most advanced database kernel engineering techniques and architectures are not in the academic literature. That’s just the nature of the domain, they do massive amounts of R&D but rarely publish.

Const-me 6y ago

They are different caches. The database engines you’re talking about do that for pages not found in RAM, which need to be read from disk. This article is about accessing data that’s already present in system memory. The caches they are talking about are on-chip ones, i.e. L1D and L2 caches inside CPU cores, and L3 cache shared across cores but still located on the same CPU die. Some rare CPUs like in my old laptop with Core i3-6157U even have L4 on-chip cache made of DRAM.

jandrewrogers 6y ago
These are not different caches. Database engines do this with system memory and CPU cache, in addition to the disk cache. If you are implementing user space I/O and execution scheduling, you are already most of the way there. In fact, some have much more advanced scheduling around the CPU cache hierarchy than what was discussed in the paper. Some database engines don’t just prefetch memory, they also dynamically reorder the execution schedule to minimize CPU cache churn and save some memory bandwidth. A good database can easily retire tens of millions of page operations per second these days, giving them a considerable look ahead window. The technique discussed in the paper has been used in many systems for a long time. This was a standard design idiom for graph databases for at least 15 years, due to their intrinsically poor locality. Most advanced database kernel engineering techniques and architectures are not in the academic literature. That’s just the nature of the domain, they do massive amounts of R&D but rarely publish.