CoroBase: Database engine using C++20 coroutines to hide cache misses
github.com
github.com
To access data (e.g., a tree node) in request t1 which may incur a cache miss, the thread issues a prefetch and switches to another request t2, and repeats this process. While the data needed by t1 is being fetched from memory to CPU cache, the worker thread handles t2, which may further cause the thread to issue prefetch and switch to another request. By the time the worker thread switches back to t1, the hope is that the needed data is (already and still) cache-resident. The thread then picks up at where it left for t1, dereferences the pointer to the prefetched data and continues executing t1 until the next possible cache miss upon which a prefetch will be issued. It is important that the switching mechanism and representation of requests are cheap and lightweight enough to achieve a net gain.
Many things may go wrong, interference from another hardware thread running on the same core, context switches, cache associativity shenanigans, and more.
But still, if you prefetch, switch a co-routine so that other one is spending their 100-500 CPU cycles doing something else, then switch back — I would expect statistically significant performance win, at the cost of code complexity.
With these recent spectre/meltdown/etc, I wouldn’t expect to see an instruction to query cache state for an address, at least in a foreseeable future. An easy implementation probably gonna be a side channel attack vector.
It's not a panacea though; naive usage of prefetch will actually decrease performance [0], because the hardware already does a lot of prefetching on its own and you're messing with that.
From what little research I've done, prefetch mostly improves performance when accessing data in a hot loop, in a non-linear pattern (eg nextAddress isn't just prevAdress + constantValue), 3-4 loop iterations ahead of the execution. Eg
doThings(myArrayOfPointers[i]);
__builtin_prefetch(myArrayOfPointers[i + 4]);
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.
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.
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.
Can someone please explain that this means? I am really curious to know.
Hope this was a clear enough explanation, and someone correct me if I’m wrong.
In this case, prefetch, which to be useful often requires a context switch.
Another, lately, is popcount.
One that only appears in very recent Intel (and AMD?) is an instruction to sleep until a particular cache line gets invalidated, as a way to both save on power and latency, as waking up can be faster than escaping the poorly-branch-predicted spin loop.
There are various appalling tricks to keep your branch predictor from killing your loop escape latency.
From the paper's results, it also looks a lot more effective than most brute force prefetch optimizations usually are.
I once emulated the exotic XMT threading behavior and memory model in software on x86 using coroutines, which had the advantage of not requiring me to shell into the supercomputer to test my code -- developer convenience. It turned out that the XMT idiomatic C++, which is strange looking and normally runs poorly on ordinary CPUs, ran faster on this emulator on x86 than the actual XMT CPU. While the XMT CPUs had unusual architectural features that could not be emulated in software (e.g. the XMT CPU knows precisely which threads are stalled on a per clock cycle basis), x86 silicon was so much more advanced at the time that naively scheduling around stalls by inference had higher performance even after the occasional cache miss. Furthermore, this way of designing code greatly improved performance on x86-based supercomputers compared to more conventional multithreading. It changed the way we designed the software
At the time, there were a few people straddling the supercomputing and database worlds, which was how the "software XMT architecture" discovery bled over into database engine design. It is more difficult to do robustly in software but it worked really well and you can't beat the cost.