Guidelines for Building Indexes on Partially Cache-Coherent CXL Shared Memory
Fangnuo Wu, Mingkai Dong, Wenjun Cai, Jingsheng Yan, Haibo Chen · 2025
Read Guidelines for Building Indexes on Partially Cache-Coherent CXL Shared Memory by Fangnuo Wu, Mingkai Dong, Wenjun Cai, Jingsheng Yan, Haibo Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06460.txt.
Introduction
Fangnuo Wu and colleagues write guidelines for building database indexes on shared memory that is only partly cache-coherent. New interconnect technology lets many cores share memory, but coherence holds only inside core subsets, which breaks assumptions baked into ordinary single-machine software. Indexes, the structures that make lookups fast, must be rebuilt with care for this setting.
One guideline set marks which data must be synchronized and which data stays protected, making existing indexes correct again. A second set attacks the speed bottlenecks that follow, using out-of-place updates, replicated variables, and speculative reads. Two converted indexes gained up to sixteen-fold throughput and beat message-passing and disaggregated rivals.
Catalog record
| CREATOR | Fangnuo Wu, Mingkai Dong, Wenjun Cai, Jingsheng Yan, Haibo Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06460
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Guidelines for Building Indexes on Partially Cache-Coherent CXL Shared Memory Fangnuo Wu, Mingkai Dong, Wenjun Cai, Jingsheng Yan, Haibo Chen Abstract The Partial Cache-Coherence (PCC) model maintains hardware cache coherence only within subsets of cores, enabling large-scale memory sharing with emerging memory interconnect technologies like Compute Express Link (CXL). However, PCC’s relaxation of global cache coherence compromises the correctness of existing single-machine software. This paper focuses on building consistent and efficient indexes on PCC platforms. We present that existing indexes designed for cache-coherent platforms can be made consistent on PCC platforms following SP guidelines, i.e., we identify S ync-data and P rotected-data according to the index’s concurrency control mechanisms, and synchronize them accordingly. However, conversion with SP guidelines introduces performance overhead. To mitigate the overhead, we identify several unique performance bottlenecks on PCC platforms, and propose P 3 guidelines (i.e., using Out-of- P lace update, Re P licated shared variable, S P eculative Reading) to improve the efficiency of converted indexes on PCC platforms. With SP and P 3 guidelines, we convert and optimize two indexes (CLevelHash and BwTree) for PCC platforms. Evaluation shows that converted indexes’ throughput improves up to 16 × \times following P 3 guidelines, and the optimized indexes outperform their message-passing-based and disaggregated-memory-based counterparts by up to 16 × \times and 19 × \times . Introduction Recent advances in highly efficient and byte-addressable memory interconnect technologies, such as Compute Express Link (CXL) [ 8 ] and Unified Bus [ 3 ] , enable memory sharing across multiple hosts. Cross-host memory sharing enables zero-copy data transfer and shared-everything data access, which benefits various application scenarios including key-value stores [ 45 , 41 ] , database systems [ 42 ] and distributed computing frameworks [ 57 , 38 ] . However, it’s impractical to maintain global hardware cache-coherence for memory shared across large-scale hosts. While CXL 3.0 [ 10 ] has announced hardware cache-coherence support, researchers and CXL vendors show that large-scale hardware cache-coherence introduces non-negligible overhead and fails to scale to a larger number of hosts [ 53 , 22 ] . To enable large-scale memory sharing, one practical approach is to relax global cache-coherence with the partial cache-coherence (PCC) models [ 17 , 33 ] . A typical implementation of the PCC model maintains cache coherence among cores within a single host, but not across hosts. To enable synchronization on PCC platforms, global cache-bypass atomic instructions are essential, and atomics are feasible to be implemented without the significant cost and complexity associated with hardware cache coherence [ 58 , 3 ] . This paper focuses on building consistent and efficient indexes on PCC platforms, as indexes are fundamental components of modern software systems [ 45 , 37 , 42 , 38 ] . We begin by converting indexes designed for cache-coherent platforms (CCIndex) to PCC platforms (PCCIndex) with SP guidelines. CCIndexes are selected as they are time-tested and have a variety of implementations. Then, we analyze the performance bottlenecks of PCCIndex and mitigate them accordingly. To convert CCIndexes for correct execution on PCC platforms that lack cache coherence, it is essential to correctly control the update visibility of shared data (with their state cached in CPU cache). To achieve this, we distinguish between two types of shared data that have different visibility requirements. First, sync-data used for concurrency control (e.g., lock flag) requires immediate visibility. Second, protected-data protected by synchronization mechanisms (e.g., data protected by locks) can delay visibility, since the concurrency control mechanisms protect it from being accessed by other cores. We thus propose the SP guidelines to ensure correctness of PCCIndex, which synchronize sync-data using cache-bypass atomics for immediate visibility, and use cacheline flush to make protected-data visible according to index’s concurrency control mechanism. However, conversion with SP guidelines introduces overhead due to excessive software management of cachelines. By breaking down the overhead of the converted indexes, we reveal several common bottlenecks for PCC platforms, and propose P 3 guidelines to mitigate the overhead accordingly. First, we observe that in-place updates of converted PCCIndex introduce more overhead compared with indexes using out-of-place updates . This is because out-of-place updates eliminate the need for invalidating protected-data ’s cacheline before reading, since protected-data ’s cacheline is always fresh as out-of-place updates do not modify them in-place. Besides, out-of-place updated indexes require less cache-bypass operations on sync-data compared to in-place updated ones. With this observation, we start building PCCIndex based on indexes with O ut-of-place updates . Second, we find that current loads, which are commonly considered as scalable on cache-coherent platforms, are actually not scalable on PCC platforms. The underlying reason is that concurrent cache-bypass loads of the same physical address are strictly ordered by the hardware memory controller to preserve memory semantics [ 20 , 51 ] . Thus, PCCIndex’s scalability is bottlenecked by loads of frequently-accessed shared variables (e.g., root node pointer for tree indexes). To mitigate this, we use R eplicated shared variables , which replace cache-bypass loads to a single physical address with loads to multiple distinct addresses. Third, we find that converted PCCIndex fail to fully exploit the high-speed CPU cache and cache coherence within the host. This limitation becomes particularly significant under read-heavy and skewed workloads, which are common in real-world production systems [ 4 , 40 , 56 ] . The primary reason is that converted indexes perform cache-bypass loads even when the data is already cached and unchanged—a common scenario in read-heavy and skewed workloads. To better leverage the CPU cache, we employ sp E culative reading instead of always performing cache-bypass loads. Data can first be speculatively read from the cache; its freshness is then verified, and the operation is retried if necessary to ensure correctness. Following the SP 4 guidelines, we convert and optimize a hash index (CLevel-Hash [ 7 ] ), a B+Tree index (BwTree [ 30 ] ), and a general decentralized garbage collection mechanisms [ 50 , 54 ] for PCC platforms. In the evaluation using YCSB [ 9 ] and real-world traces (i.e., Twitter [ 56 ] ), applying P 3 guidelines can improve the throughput of a converted but not optimized index by up to 2.4 \times (for CLevelHash) and 16 \times (for BwTree). Besides, P 3 -CLevelHash and P 3 -BwTree achieve up to 16 \times and 13 \times throughput improvement over partitioned and message-passing-based indexes, and P 3 -BwTree achieves up to 19 \times improvement over Sherman, an RDMA-based index ported to the CXL platform. Besides, integrating P 3 -BwTree with Ray results in a 49% throughput improvement for an RL algorithm [ 14 ] . In summary, the paper makes the following contributions. • We introduced SP guidelines for converting CCIndex with different synchronization mechanisms to PCCIndex. • We revealed the unique inefficiencies of PCC platforms and proposed the P 3 guideline for unleashing the performance of PCCIndex. • We implemented two indexes and a general GC method using SP guidelines and P 3 guidelines and evaluated their performance using YCSB and real-world traces. Partial Cache-Coherence Shared Memory Memory interconnect technologies Recent memory interconnect technologies, such as Compute Express Link (CXL) [ 8 ] and Unified Bus [ 3 ] , enable multiple physically connected hosts to share