Skip to content

The Partly Coherent CXL

This post introduces our line of work on the partly coherent CXL 3.0 memory model, which spans two papers: Megalon (OSDI '26, best-paper nominee), which provides a solution for sharing a large amount of data coherently on CXL, and Prism (SOSP '26), which explores the best way to build a shared index.

Start readingSkip to the research
Four hosts, one shared CXL memoryFour outlined host machines sit at the corners. Beams from each converge on a single memory slab labeled CXL memory, terabytes, shared by all four at once.Host 1Host 2Host 3Host 4CXL MEMORY · TBsone device · four address spaces · zero copies

Blog by Kiran Hombal and Jiyu Hu

Megalon: Efficient Data Sharing for Partly Coherent CXL Memory (OSDI 2026, best-paper nominee)
Jiyu Hu, Seokjoo Cho, Landon Johnson, Kiran Hombal, Shreesha G. Bhat, Marcos K. Aguilera, Ramnatthan Alagappan and Aishwarya Ganesan

Disk-Based LSMs: An Unexpectedly Good Index for Partly Coherent CXL Memory (SOSP 2026)
Kiran Hombal, Jiyu Hu, Marcos K. Aguilera, Ramnatthan Alagappan and Aishwarya Ganesan

DASSL Lab, UIUC and NVIDIA

TL;DR

CXL 3.0 enables multiple TBs of memory to be shared between multiple hosts, opening new potential for distributed applications such as databases and KV stores. However, it is reported that only a small portion of the shared CXL memory region (hundreds of MBs) can support cross-host cache coherence due to hardware constraints, leaving the remaining TBs of memory non-cache-coherent across hosts.

Megalon lets us coherently share a large number of data objects in the partly coherent CXL memory by utilizing the software coherence approach. It does so efficiently through split metadata sharing, which uses the precious coherent region smartly by storing only the critical coherence metadata.

Prism explores how to build a shared index on top of partly coherent CXL in a principled manner. It makes a core observation that the LSM, a data structure originally optimized for disk accesses, is an unexpectedly great fit for CXL indexes. The solution lies in the LSM’s small updatable surface area.

1. Intro to CXL

A new memory technology

The memory wall. Server CPUs went from a dozen cores in 2012 to well over a hundred today, yet DRAM capacity per core has been falling for a decade: a CPU cannot simply add memory channels due to hardware constraints.

To solve this problem, Compute Express Link (CXL) was created. It is an open standard built on PCIe. A CXL memory device is a box of DRAM connected over PCIe, and the CPU can issue direct memory loads and stores.

Two ways out of the socket

Sharma et al., CXL survey · PCI-SIG
DDR versus CXL pin budgetsA CPU connects to local DRAM through a wide ribbon of about 200 signal pins carrying about 51 gigabytes per second, and to CXL memory through a narrow ribbon of 64 signal pins carrying about 63 gigabytes per second in each direction at PCIe 5.0 rates.CPULOCAL DRAMhundreds of GBDDR5-6400 · ~200 signal pins · ~51 GB/sCXLCTRLCXL MEMORYterabytesx16 PCIe 5.0 · 64 signal pins · ~63 GB/s per direction
Bandwidth per signal pin is important: close to 1 GB/s per pin for the PCIe link against about 0.25 for DDR5, roughly 4× more, and PCIe 6.0 doubles it again. A CPU can afford far more of these narrow links than DDR channels, which is how CXL adds terabytes where the DDR bus cannot.

A diagram comparing a DDR channel, about 200 signal pins for about 51 gigabytes per second, against a CXL link over PCIe, 64 signal pins for about 63 gigabytes per second in each direction.

But the scalability comes at a cost and that is higher latency. Local DRAM latency is roughly 100 ns, compared to CXL memory latency which is two to three times that. It is about the cost of reaching the other socket of a two-socket server (a NUMA hop), which is an acceptable norm for multi-socket servers. It is still much faster than a remote read over RDMA (microseconds) or an SSD (tens of microseconds).

Where CXL lands in the hierarchy

Melody (ASPLOS '25); Next Platform
Approximate access latency by tierA log-scale dot plot from L1 cache near one nanosecond to NVMe SSDs near one hundred microseconds. CXL memory sits at roughly 170 to 400 nanoseconds, between local DRAM and an RDMA round trip. Each dot is a representative point inside a range; the table gives the ranges and where each one comes from.L1 cache~1 ns on the core itselfL2 cache~4 ns private per coreL3 cache~15 ns shared on the dieLocal DRAM~111–117 ns over the DDR busCXL memoryabout one NUMA hop away ~170–400 nsRDMA readnetwork round trip ~2–10 µsNVMe SSDflash storage ~10–100 µs
Show the numbers
Where CXL lands in the hierarchy
TierLatencyNoteBasis
L1 cache~1 nson the core itselftextbook order of magnitude
L2 cache~4 nsprivate per coretextbook order of magnitude
L3 cache~15 nsshared on the dietextbook order of magnitude
Local DRAM~111–117 nsover the DDR busmeasured on three Melody platforms
CXL memory~170–400 nsabout one NUMA hop awayMelody measured 214–394 ns; industry quotes 170–250 ns
RDMA read~2–10 µsnetwork round tripcommonly reported range
NVMe SSD~10–100 µsflash storagecommonly reported range

A log-scale ladder of approximate access latencies from L1 cache at about one nanosecond, through local DRAM near 110 nanoseconds, CXL at roughly 170 to 400 nanoseconds, RDMA at microseconds, and NVMe SSDs at tens of microseconds.

CXL 3.0: cross-host sharing

From memory expansion (CXL 1.0) to memory sharing (CXL 3.0+)

CXL 1.1 (2019) does expansion where a single host gets more memory capacity. CXL 2.0 (2020) adds memory pooling, here it is a rack-level pool, broken down into segments where each segment is still owned by one host at a time. CXL 3.0 (2022) and its successors (3.2 in 2024, 4.0 in late 2025) add multi-host shared memory. Several hosts can map the same region into their address spaces and share data efficiently over a unified piece of memory.

Now with CXL 3.0 shared memory, applications like databases, key-value stores, and file systems could keep one copy of their data in CXL, which every host can reach. Accessing this shared data is now a direct memory operation instead of a round trip over the network.

But there is a catch...

Three generations, three relationships to memory

CXL Consortium spec releases
CXL 3.x: SharingFabrics and true multi-host sharing: several machines map the same region, at the same time.Host 1Host 2Host 3Host 4the same bytes, in multiple address spaces at onceSharing: Fabrics and true multi-host sharing: several machines mapthe same region, at the same time.
Toggle the generations.

An interactive diagram showing CXL 1.1 with one host and one expander, CXL 2.0 with a switch assigning pool segments to individual hosts, and CXL 3.0 with four hosts mapping one shared region simultaneously.

2. The catch: partly coherent memory

CXL 3.0 lacks full cross-host cache coherence

Background · Cache coherence · expand if new to CPU caches

Most memory loads/stores never reach DRAM. A memory access costs about 100 ns, so every CPU keeps recently used data in small, fast and local caches and serves most loads/stores from there. But because these caches are local, it creates copies, and copies can go stale: if one CPU changes a value that another has cached, the other’s copy is now wrong.

Inside a single machine this is not visible to the applications, because the hardware does the heavy lifting. Cache coherence keeps every cached copy of a location consistent: before a CPU writes, the hardware finds the other copies and invalidates them, so every CPU always sees one coherent view of memory. Software gets that for free.

Imagine scaling the hardware cache coherence support to what CXL 3.0 needs: several machines with dozens of caches each, sharing terabytes of memory. To behave like memory on a single machine, the hardware would have to run coherence across all the hosts, over PCIe, for every cache line. Vendors like AMD, Micron, and Samsung all say that scaling stops somewhere around a few hundred megabytes.

So the hardware is expected to have a partly coherent model, which is the assumption both of our papers use. The memory is split into two regions. A small coherent region or SCR, is the part that hardware keeps coherent across hosts. A large non-coherent region or LNR, is the rest of the memory, where there is no expectation of coherence across hosts.

The two regions, side by side

Megalon §2.1 · Tigon
SCR versus LNR, not to scaleA bar representing an illustrative four terabytes of CXL memory. The hardware-coherent region, a few hundred megabytes, would be far thinner than a pixel; it is drawn as a widened marker at the left edge and magnified in a callout above.SCR · 100s MBhardware coherentLNR · several TB · no coherence across hosts04 TB

A few hundred MB on a device of several TB.

A long bar representing several terabytes of CXL memory. The hardware-coherent region, a few hundred megabytes, would be far thinner than a pixel; it is drawn as a widened marker at the left edge and shown magnified.

Why do we need cross host cache coherence? What happens if the data stored in LNR is accessed by multiple hosts? Let us look at it with an example.

Suppose Host 1 reads object A and caches it. Host 2 overwrites it with A′. On Host 2's machine that write would invalidate all its other copies. But across other machines, in the LNR, no invalidation is ever sent. So when Host 1 reads the same object again, its cache returns the stale value silently. This is a correctness bug and is very serious.

One could simply use the SCR to share data, but a few hundred megabytes shared among many hosts is insignificant. Therefore, we need a better approach to share data coherently across hosts in CXL.

The stale read, step by step

Host 1 reads A from the LNRThe value drops into host 1’s CPU cache, as every read does.Host 1cacheAHost 2cacheread ALNR · no coherenceA

1 / 4 · Host 1 reads A from the LNR

The value drops into host 1’s CPU cache, as every read does.

Host 2’s write reaches the memory, but no invalidation reaches host 1’s cache, so host 1’s next read is answered by its own cache, which is incorrect.

An animation of two hosts sharing a value in the non-coherent region. Host 1 caches A; host 2 writes A-prime; host 1 reads again and its cache serves the stale A with a warning flag.

3. A software approach, and how it collapses

One way to achieve software coherence is to keep the data in LNR and small metadata in the SCR to track the coherence, where hardware coherence maintains metadata correctness.

More concretely, each shared object gets a coherence record (version counter plus a lock) which is allocated in SCR. A host checks the record before accessing the object. If the version number is updated that means there was a write since the host’s last access. Which means the host might be holding a stale cache. The host will then issue manual cache flush operations and re-reads the data from CXL. The figure on the right illustrates it.

Next to each object’s coherence record, a shared index lets hosts find each object and its record. We refer to the index and the coherence records together as the metadata. In the Megalon paper, we call this software coherence approach, which keeps all of the metadata in the SCR to track coherence for data in the LNR, hardware-coherent metadata-based sharing or HCMeta for short. Tigon (OSDI ’25), a partitioned database for a multi-host CXL pod, uses this method.

Software coherence, step by step

Megalon §2.2
Host 1 reads AHost 1 reads A from the LNR and notes its version from A’s coherence record in the SCR: 0.Host 1cacheA: 0Host 2cacheread Aversion 0SCR · hardware coherentINDEXcoherence record: 0LNR · no coherenceA

1 / 4 · Host 1 reads A

Host 1 reads A from the LNR and notes its version from A’s coherence record in the SCR: 0.

A version record per object in the SCR, which hardware keeps coherent; a reader that finds a newer version drops its copy and re-reads. Simplified: the lock, the fences, and the mid-read retry are left out.

An animation of software coherence. Host 1 caches A at version 0; host 2 writes A-prime to the LNR and bumps A's version in the SCR to 1; host 1 checks the SCR, sees 0 does not match 1, invalidates its cached A, and re-reads A-prime from the LNR.

HCMeta works for Tigon’s workload of occasional cross-partition transactions. But as the shared dataset scales a problem surfaces: the metadata grows with the number of shared objects, but the SCR does not. So the SCR soon fills up after sharing only a limited number of data objects.

Eventually when HCMeta runs out of SCR space, it unshares an old object to make room for a new one. Objects start rotating through the tiny window of shareability, and every rotation is expensive: the host needs to wait for an object to be reshared if it is unshared by the owner. We call the rotation churn. Because of these churns, as the dataset grows, throughput drops sharply (as the figure on the right shows).

Summary. Software coherence lets hosts share data objects in the LNR while keeping them coherent, but HCMeta, which keeps all of its metadata in the SCR, takes a performance hit once the SCR fills up. So our first paper asks: how can hosts share a large number of objects when the metadata itself is too big for the SCR?

Measure HCMeta collapse

Megalon, Figure 1(c)
HCMeta throughput collapses once the dataset outgrows the coherent regionWith unlimited SCR throughput holds near 15 Mops per second across every dataset size. With a realistic 100 MB SCR it falls from 15.2 to 1.0 between 2.4 and 4.8 million objects and keeps sinking. Values were read off the paper's plot.the SCR fills hereunlimited SCR (unrealistic)
  • HCMeta, 100 MB SCR
  • HCMeta, unlimited SCR
A key-value store using HCMeta, read-only, 100 MB SCR. The unlimited-SCR variant, which simulates an unrealistic SCR not limited to a few hundred MB, stays flat; the real one falls from 15.2 to 1.0 Mops/s (million operations per second) between 2.4M and 4.8M objects and keeps sinking. For scale: with 40-byte keys HCMeta spends 52 bytes of SCR per object, so 100 MB caps sharing near 1.9M objects.
Show the numbers
Measure HCMeta collapse
DatasetHCMeta, 100 MB SCRUnlimited SCR
1.2M objects15.5 Mops/s15.5 Mops/s
2.4M objects15.2 Mops/s15.3 Mops/s
4.8M objects1.0 Mops/s15.1 Mops/s
7.2M objects0.9 Mops/s15.0 Mops/s
12M objects0.7 Mops/s14.6 Mops/s
18M objects0.6 Mops/s13.8 Mops/s

A line chart of throughput versus dataset size. With unlimited SCR, throughput holds near 15 million operations per second. With a realistic SCR, throughput collapses from about 15 to about 1 million operations per second once the dataset passes a few million objects.

Paper one · OSDI 2026 · Best-paper nominee

4. Megalon

Share the data. Split the metadata.

Skipped ahead? The setup in brief

CXL lets hosts share terabytes, but reportedly keeps only a small region coherent across hosts (the SCR, a few hundred MB); the large non-coherent region (LNR) can silently serve stale cached data. A natural fix, HCMeta, uses metadata in the SCR to track coherence for data in the LNR through a software approach, but the metadata can grow huge and soon fill up the SCR without even sharing a large number of data objects (~2M). The performance collapses past it. ↑ The partly coherent model · ↑ How HCMeta collapses

Megalon makes one key observation: the metadata is two very different things glued together. The index, which maps each object’s ID to its location. It is big (every object’s key, tens of bytes each) and cold, it changes on inserts and deletes, far less often than data writes. The coherence records are tiny (a lock bit and a counter, 4 bytes) and hot: updated/accessed on every write.

HCMeta allocated both index and coherence record in the SCR. Megalon’s key idea is to split them and share each the way its nature demands. The hot, tiny records stay physically shared in the SCR, where hardware coherence makes coherence checks fast; at 4 bytes, about 13× more of them fit than HCMeta’s 52-byte bundles. The big, cold index is logically shared: every host keeps a full replica in its local DRAM, of which it has hundreds of gigabytes, roughly 1000× the SCR. At 100 MB SCR, HCMeta can share about 2 million objects, but Megalon can share about 25 million, ~12× more.

At first sight, replicating the index recreates the problem: N replicas must now be kept consistent. However, the index is the cold half. It changes rarely, so keeping replicas in sync is cheap, given a mechanism to do it.

Split metadata sharing

Megalon §3.2, Figure 2
Split metadata sharingHosts hold replicated indexes in local DRAM. The CXL memory holds coherence records in the small coherent region and data objects in the large non-coherent region. Occupancy bars compare 52 bytes per object for HCMeta (with 40-byte keys) against 4 bytes for Megalon.Host 1 · local DRAMINDEX REPLICAHost 2 · local DRAMINDEX REPLICAHost N · local DRAMINDEX REPLICACXL MEMORYSCRcoherence records · 4 Bdata objects · 1–4 KB eachLNRSCR SPENT PER SHARED OBJECTHCMeta52 BMegalon4 B · ~13× more objects

The index moved to where memory is plentiful, saving SCR space for frequently accessed tiny coherence records.

The big, cold index is replicated into each host’s DRAM; only the tiny, hot records occupy the SCR. For the paper’s 40-byte-key example, 52 bytes of SCR per object becomes 4.

A diagram of Megalon's split: index replicas in each host's local DRAM point to data objects in the LNR and to small coherence records in the SCR. Occupancy bars compare 52 bytes per object for HCMeta against 4 for Megalon.

That mechanism is a shared log: a linearizable, ordered sequence of entries that many parties can append to at the tail and read. It is the classic basis for state machine replication: replicas that apply the same entries in the same order reach the same state. Megalon keeps the index replicas consistent exactly this way.

Shared logs are usually built on distributed protocols that pass messages, at high cost. Megalon instead follows Node Replication (NR), which uses a shared log to build concurrent data structures across NUMA sockets, but places the log in the LNR, where every host reads and appends to it directly, with no message passing.

Only the log’s head and tail, on which its correctness depends, live in the SCR beside the coherence records, so they get hardware coherence at almost no SCR cost. To change the index, a host claims the next entry with an atomic compare-and-swap on the tail, writes the entry, and flushes it. Before any index read, a host checks the tail and applies any new entries to its replica.

Deeper dive · techniques built on the log

The log supports two further coherence techniques.

Dynamic coherence records. With split metadata sharing, Megalon can share far more objects than HCMeta, but it is still fundamentally limited by the number of coherence records that fit in the SCR. We make another core observation: objects that are only read need no record, since nothing changes under the readers. So Megalon allocates records only for objects that are read and written. Therefore, Megalon can fit an unlimited number of read-only objects, as long as they fit in the LNR. When the SCR fills, Megalon demotes cold objects and reassigns their records, announcing each change through the log. However, churn becomes an appended entry rather than a round trip: about 8× cheaper than HCMeta.

Dual-path coherence. With records coming and going, an object can gain or lose its record while you are reading it, so the record alone cannot prove your cache is fresh. Hosts therefore also check, at the end of a read, whether the log recorded an allocation event for the object; if so, they flush and retry.

Other uses of the log. Since every index change is ordered by the log, Megalon can also keep a host’s private objects in its local DRAM, and cache read copies of hot shared objects there, where access is faster than CXL (paper §3.5).

A shared log in CXL

Megalon §3.3, §4
The CXL shared logA log of ordered entries lives in the non-coherent region; only its head and tail pointers live in the coherent region. Hosts append via compare-and-swap on the tail and replay entries into their index replicas.Host 1INDEX REPLICAHost 2INDEX REPLICAappend · compare-and-swap on the tailreplay → replicaLNR1234567shared log · ordered · entries flushed on write, read past the cacheSCRhead = 1tail = 7

Only the head and tail pointers need hardware coherence. The entries sit in the LNR, written with a flush and read past the cache, and order does the rest.

A shared log laid out in the non-coherent region with its head and tail pointers in the coherent region. Hosts append entries and replay them into local index replicas.

Against HCMeta, Megalon delivers 15× on read-only workloads with large datasets and 10× at 5% writes once metadata outgrows the SCR. The cost is host DRAM for the index replicas, 7.6% more memory in the 24M-object read-only run.

Megalon flat where HCMeta collapses

Megalon Figure 6(a)
Megalon versus HCMeta as the number of shared objects growsGrouped bars, 5 percent writes and a 200 MB coherent region: Megalon holds near 17 Mops per second from 4.8 to 24 million objects while HCMeta falls from 16.6 to 1.7, about 10 times lower at 24 million. Values read off the paper's Figure 6(a).4.8M7.2M12M1.717.424Mshared objects10×
  • HCMeta
  • Megalon
5% writes, Zipfian, 200 MB SCR. From 4.8M to 24M shared objects HCMeta churns and collapses while Megalon holds near 17 Mops/s: 10× at 24M, all thanks to more data being shared through split metadata sharing. Read the paper for more experiments.
Show the numbers
Megalon flat where HCMeta collapses
Shared objectsHCMetaMegalon
4.8M16.6 Mops/s17.7 Mops/s
7.2M5.7 Mops/s17.2 Mops/s
12M2.5 Mops/s17.4 Mops/s
24M1.7 Mops/s17.4 Mops/s

Grouped bars of throughput for 4.8, 7.2, 12 and 24 million shared objects under 5 percent writes. Megalon stays near 17 million operations per second at every size; HCMeta falls from 16.6 to 1.7, a ten times gap at 24 million objects.

5. The index problem

What is the right way to build an index for shared CXL memory?

Shared CXL memory opens the door for a whole range of applications to share data directly: databases, key-value stores, file-system metadata services, analytics engines. Most of them rely on the same building block, an index that supports point queries, range queries, and updates. So our second paper asks a simple question: what is the right way to build an index for shared CXL memory?

The natural starting point is the software coherence approach from section 3: data in the LNR, coherence metadata in the SCR, and a check of the metadata before every access. Can we use it to port existing indexes? We start with two widely used in-memory indexes. The adaptive radix tree (ART) has many small nodes: each node is adaptive, starting as a tiny Node4 and growing only as needed, up to Node256. The B+-tree is the opposite: a few large, fixed-size nodes, each with a high fan-out.

To apply software coherence, we piggyback the coherence records on the version numbers of optimistic lock coupling (OLC). OLC is the concurrency control method already widely used. In OLC every node keeps a version number that changes whenever the node is updated. The port is straightforward. We separate the version numbers from the tree nodes and move them into the SCR, where hardware keeps them coherent. Tree nodes and the key-value pairs stay in the LNR. We call these software-coherent indexes SC-ART and SC-BTree.

Simple enough, right? Not really. It comes with its own problems.

Problem 1: version numbers overflow the SCR. Every node needs a version number in the SCR, and as the tree grows, so does the number of version numbers. With 100M keys, ART has ~40M inner nodes; at 8 bytes per version, a 128 MB SCR holds only about 40% of them. The rest spill into the LNR, and now the metadata we rely on to detect stale data can itself be stale. A host must flush a spilled version number on every access and re-read it, even if nothing has changed causing a huge performance drop.

Problem 1: version numbers overflow the SCR

Prism §3.2, Figure 1
A small tree: every version number fitsEach node of SC-ART keeps its version number in the SCR. With five nodes, five of the eight slots are used, and a host checks a node’s version there before trusting its cached copy.VVVVVVVVVVVVVSC-ART · 5 nodes · 5 version numberstree nodes and data in the LNRSCR · coherent · 8 slotsVVVVV5 of 8 slots usedLNR · no coherence across hostsVVVVVnothing spilled

1 / 4 · A small tree: every version number fits

Each node of SC-ART keeps its version number in the SCR. With five nodes, five of the eight slots are used, and a host checks a node’s version there before trusting its cached copy.

An animation of an ART growing from five nodes to thirteen while its version numbers fill eight slots in the coherent region; the five that spill into the non-coherent region are marked as needing a flush on every access.

Problem 2: bigger nodes cause false invalidations. Larger nodes, as in B-trees, do solve the capacity problem: more keys per node means fewer nodes and fewer version numbers. With a fan-out of 128, SC-BTree’s version numbers fit in the SCR easily. But now a single version number covers many keys, causing significant false invalidations, as the animation on the right shows. We made the metadata fit but introduced unnecessary cache flushes.

Problem 2: false invalidation

Prism §3.3, Figure 2
One version number for the whole nodeA large node holds 128 keys in the LNR and shares a single version number in the SCR. Host 2 has read key 298 before, so the whole node sits in its cache at version 7.Host 1cacheHost 2cachenode · v7read key 298 earlier: node cached at v7SCR · coherentnode version7LNR · one B-tree node, 128 keys, one version number for all of them181194298420498501645… 128host 2 holds a copy of all 128 keys

1 / 4 · One version number for the whole node

A large node holds 128 keys in the LNR and shares a single version number in the SCR. Host 2 has read key 298 before, so the whole node sits in its cache at version 7.

An animation of two hosts and a 128-key B-tree node with one version number in the coherent region. Host 2 has the node cached at version 7; host 1 updates key 194 and the version becomes 8; host 2 reads key 298, sees the mismatch, and must flush and re-read the whole node.

The core problem is what we call the updatable surface area, defined as the portion of the index that can receive in-place modifications. In ART and B-trees, any node from root to leaf can be modified in place, so the updatable surface area spans the entire index, and every node needs a version number. That leaves a trade-off. Small nodes track changes precisely, but need too many version numbers. Large nodes make the metadata fit, but track changes too coarsely and cause false invalidations. Either way, we pay for excessive cache flushes, so just changing the node size does not solve the underlying problem.

Small nodes overflow the SCR; large nodes cause false invalidations

Prism §3, Figures 1–2
Small nodes overflow the SCR; large nodes cause false invalidationsAt small node sizes the version numbers overflow the coherent region; at large node sizes they fit but a single update falsely invalidates every other key in the node. The two ends are measured; the middle is a model.VERSION NUMBERS vs THE SCR (128 MB)spilled into the LNR7.0M version numbers needed · 16M fit · all fit · modeledONE KEY WRITTEN → KEYS FLUSHEDfan-out 23: the write touches 1 key and invalidates 22 unmodified keys

modeled: version numbers fit, false invalidations begin

every version number fits, but one write already invalidates 22 unmodified keys; smaller nodes avoid that and overflow the SCR again

The two ends are the paper’s measurements: SC-ART at ART’s smallest node size and SC-BTree at 128 keys per node.

An interactive slider over index node size. With small nodes, tens of millions of version numbers overflow the coherent region. With large nodes, one update falsely invalidates every other key in a 128-key node. The two ends are measured; the middle is a model.

Paper two · SOSP 2026

6. Prism

A data structure built for disk is an unexpectedly good fit for partly coherent CXL.

That data structure is the log-structured merge tree (LSM), the engine inside RocksDB, LevelDB, Bigtable, and Cassandra. It keeps writes in a small, updatable memtable and the bulk of the data in sorted, immutable files called SSTables.

An LSM confines its updatable surface area to the memtable, a good fit for partly coherent CXL. We place the memtable and the manifest, which records the live SSTables, in the SCR where hardware coherence keeps them coherent. The immutable SSTables live in the LNR. We call this port SC-LSM.

Background · LSM trees · expand if new to LSMs

A conventional LSM sends all writes to an in-memory memtable, where they are updated in place. SSTables sit on disk in levels, and a small manifest records which SSTables are in which level.

When the memtable is full, it is flushed as a new SSTable at level 0 (L0). In the background, compaction merge-sorts SSTables into the next level and discards the old ones. L0 SSTables can overlap in key range because each comes from a separate flush. From L1 onward, SSTables within a level have non-overlapping key ranges.

A read checks the memtable first, then L0 SSTables from newest to oldest, then at most one SSTable per level, stopping at the first hit.

Memory reuse · reading a new SSTable

One thing remains to handle: memory reuse. When compaction discards an SSTable, its memory is recycled for a new one. Each SSTable gets a strictly increasing ID in the manifest, and a host that sees an ID for the first time flushes that SSTable’s region once before reading it.

What a good index for partly coherent CXL looks like

Prism §3.4, §4.1
LSM: updatable surface area, the memtableIn-place updates are confined to the memtable, which fits in the SCR. The SSTables below are immutable for their whole lifetime, so they can live in the LNR with no coherence tracking.any node can be modified in placeevery node needs a version numbermemtableall in-place updatesSSTables · immutableno coherence tracking while aliveINDEXupdatable surface areaSCRhardware coherentmemtableLNRno coherence across hostsSSTablesIn-place updates are confined to the memtable, which fits in the SCR.The SSTables below are immutable for their whole lifetime, so they canlive in the LNR with no coherence tracking.

An interactive diagram of an index drawn as a triangle beside the coherent and non-coherent regions. For an ART or B+-tree the whole triangle is updatable and its version numbers overflow the coherent region. For an LSM only the apex, the memtable, is updatable and sits in the coherent region, with immutable SSTables below.

Even this straightforward port of LSM to SC-LSM performs well. So limiting the updatable surface area helps. But this port inherits an old LSM problem: compaction cannot keep up. At high write rates the memtable fills and flushes quickly, producing L0 SSTables faster than compaction can drain them into the next level. Since L0 is not level-sorted, a point query may end up probing every L0 SSTable. We measured it: at 5% writes SC-LSM probes about 15 SSTables per read, and at 50% writes it jumps all the way up to 49. This is a well-known LSM challenge and not something our port introduced.

Being in memory gives us a way out that disk never had. In-place updates to the upper levels of an LSM are a non-starter on disk, because they need random I/O, which is exactly what LSMs exist to avoid. In memory, they are not that expensive. So the idea is to make the upper level of the LSM updatable in place: when a key is written again, we overwrite it instead of spawning a new SSTable. Fewer SSTables means less compaction pressure, a smaller L0, and fewer probes per read. But wait, doesn’t that bring back the updatable-surface-area problem? Yes it does, so we bound it. We call this layer the bounded updatable layer (BUL). It sits above the SSTables and uses an ART as its index, with its data in the LNR and its version numbers in the SCR, and we limit its size so that all of its version numbers, even tracked per node, fit in the SCR.

Prism’s architecture: where each tier lives

Prism §5, Figure 5
Prism: memtable, BUL, SSTablesThe coherent region holds the manifest, the memtable and the BUL’s version numbers. The non-coherent region holds the BUL’s data and immutable SSTable levels. Keys sort by write frequency: the most frequently written in the memtable, less frequently written in the BUL, the least in SSTables.SCR · 128 MB · hardware coherentMANIFEST2 MBMEMTABLE · 64 MBcache for the most frequently written keysBUL VERSION #s62 MB · one per node── the coherence boundary ──BUL · in-place updatable · less frequently written keysdata here, version numbers above; bounded so they all fit in the SCRL0flush ↓L1Lncompact ↓SSTables · immutable · the least frequently written keys · no coherence tracking
The memtable and the manifest sit in the SCR under hardware coherence. The BUL keeps its data in the LNR and its version numbers in the SCR. The SSTables below are immutable, in the LNR. The memtable and the BUL together form the updatable surface area, sized so that the SCR covers it.

Prism's architecture: a memtable and a manifest inside the coherent region, a bounded updatable layer with data in the non-coherent region and version numbers in the coherent region, and immutable SSTable levels below.

Putting everything together, we get Prism. The memtable (64 MB) and the manifest (2 MB) live in the SCR. The BUL’s index and data live in the LNR, and the remaining 62 MB of the SCR holds the BUL’s version numbers, one per node; that budget is what bounds the BUL’s size. Below the BUL sit the SSTables, all in the LNR. The memtable and the BUL together form the updatable surface area. Everything else is immutable.

The three tiers and what each one holds

Prism §5
Prism’s three tiers and their coherence mechanisms
TierLives inHoldsCoherenceCost
MemtableSCR (64 MB)The most frequently written keysHardware coherenceNo software checks
BULData in LNR; version numbers in SCR (62 MB)Less frequently written keysPer-node version checkFine-grained, bounded
SSTablesLNR (the terabytes)The least frequently written keys, immutableImmutable + rising IDs; one flush on first sightCoarse but safe

A table of Prism's three tiers. The memtable in the SCR holds the most frequently written keys under hardware coherence. The BUL holds less frequently written keys, with data in the LNR and version numbers in the SCR, checked per node. The SSTables in the LNR hold the least frequently written keys, immutable, with rising IDs and one flush on first sight.

The SCR is very limited, so Prism makes the memtable aware of it and changes the memtable from a write buffer into a cache for frequently written keys. A write first checks the memtable. On a hit, the key is updated in place. On a miss, the write goes to the BUL: if the key is absent there, it is added; if it is already present, this is a repeated write, so the key is promoted into the memtable and removed from the BUL. Periodically, and when the BUL is close to full, it flushes cold entries into new SSTables and removes them. So in Prism the most frequently written keys sit in the memtable under hardware coherence, less frequently written keys sit in the BUL with fine-grained software coherence, and the least frequently written keys end up in immutable SSTables. Keys written only once, the one-hit wonders, never take up SCR space.

A read checks the tiers in the same order: memtable, then BUL, then the SSTables, every one in L0 from newest to oldest and at most one per level from L1 on, stopping at the first hit.

How Prism places writes across its three tiers

Prism §5.3, §5.6

Write A = 1

First write: enter the BULStart with an empty memtable and key B already in the BUL after one write. Writing A = 1 misses both the memtable and the BUL, so A is inserted into the BUL. Neither key takes up memtable space. The memtable and BUL version numbers are in the SCR. BUL data is in the LNR and uses fine-grained software coherence. Immutable SSTables are in the LNR.SCR · hardware coherenceMemtable · missemptyBUL versionsfit in SCRLNR belowmiss → insert ABUL · data in LNRfine-grained software coherenceA = 1B = 1Immutable SSTables · LNRL0…empty…

Step 1 / 4 · First write: enter the BUL

Start with an empty memtable and key B already in the BUL after one write. Writing A = 1 misses both the memtable and the BUL, so A is inserted into the BUL. Neither key takes up memtable space.

Repeated writes promote a key from the BUL to the memtable. Cold entries flush from the BUL to immutable SSTables; one-hit wonders never enter the memtable.

A walkthrough of Prism’s write path: a first write misses the memtable and is inserted into the BUL; a repeated write promotes that key to the memtable and removes it from the BUL; a memtable hit updates in place; cold BUL entries flush into immutable SSTables.

Mixed read-write. At 50% writes, Prism reaches up to 6.2× SC-BTree’s peak throughput and 5.6× SC-ART’s. SC-BTree suffers from false invalidations, while SC-ART suffers from version number overflow. Sweeping the write ratio tells the same story: SC-BTree drops off a cliff as the write ratio increases, but Prism declines much more gently.

Throughput against write ratio

Prism Figure 7(c)
Throughput against write ratio for Prism, SC-BTree and SC-ARTThree lines from 10 to 50 percent writes, read off the paper's Figure 7(c). SC-BTree falls from 9.3 to 1.8 million operations per second. SC-ART stays between 3.0 and 2.5. Prism declines from 17.4 to 11.6 and leads at every write ratio.9.31.817.411.6
  • SC-ART
  • SC-BTree
  • Prism
Values read off the paper’s Figure 7(c), one point per write ratio; the 6.2× and 5.6× in the text are peaks from Figure 7(b). SC-BTree falls from 9.3 to 1.8 Mops/s between 10% and 50% writes, because every write falsely invalidates a whole node on every host that cached it. SC-ART stays between 3.0 and 2.5, because its version numbers overflow the SCR. Prism goes from 17.4 to 11.6 and leads at every write ratio.
Show the numbers
Throughput against write ratio
Write ratioSC-ARTSC-BTreePrism
10%3.0 Mops/s9.3 Mops/s17.4 Mops/s
20%2.9 Mops/s4.2 Mops/s16.7 Mops/s
30%2.8 Mops/s2.6 Mops/s14.9 Mops/s
40%2.7 Mops/s2.2 Mops/s13.4 Mops/s
50%2.5 Mops/s1.8 Mops/s11.6 Mops/s

Three lines of throughput against write ratio from 10 to 50 percent. SC-BTree falls from 9.3 to 1.8 million operations per second, SC-ART stays near 3, and Prism declines from 17.4 to 11.6 while staying ahead throughout.

A full KV store under YCSB. Finally, we built a key-value store on top of each index and ran the YCSB suite on it. The takeaway: the heavier the write pressure, the larger Prism’s advantage, up to 7.4× over SC-BTree on YCSB-A and 9.4× on YCSB-F. Even on the read-only YCSB-C, traditionally an LSM’s weakness, Prism still comes out ahead of both.

A full key-value store under YCSB

Prism Figure 9
Prism versus ported in-memory indexes under YCSBGrouped bars read off the paper's Figure 9: Prism reaches 11.8 Mops per second on YCSB-A, 18.5 on B, 21.0 on C, 17.7 on D, 9.8 on E and 14.1 on F; SC-BTree falls to 1.6 and 1.5 on the two write-heavy workloads and wins only on E; SC-ART stays at or below 3.3 throughout.YCSB-A50% writesYCSB-B5% writesYCSB-Cread-onlyYCSB-Dread latestYCSB-Eshort scans1.514.1YCSB-F50% RMW9.4×
  • SC-ART
  • SC-BTree
  • Prism
Values read off the paper’s Figure 9. Prism’s lead is widest under writes, 7.4× over SC-BTree on A and 9.4× on F, because every write falsely invalidates a whole SC-BTree node, while SC-ART is held down everywhere by version number overflow. On the read-only C, Prism is still 1.1× ahead. On E, short range scans at 5% writes, SC-BTree wins. D reads the latest inserted keys; F is 50% read-modify-write (RMW).
Show the numbers
A full key-value store under YCSB
WorkloadSC-ARTSC-BTreePrism
YCSB-A · 50% writes2.2 Mops/s1.6 Mops/s11.8 Mops/s
YCSB-B · 5% writes3.1 Mops/s13.0 Mops/s18.5 Mops/s
YCSB-C · read-only3.3 Mops/s19.5 Mops/s21.0 Mops/s
YCSB-D · read latest2.8 Mops/s12.8 Mops/s17.7 Mops/s
YCSB-E · short scans2.9 Mops/s13.7 Mops/s9.8 Mops/s
YCSB-F · 50% RMW1.9 Mops/s1.5 Mops/s14.1 Mops/s

Grouped bars across YCSB workloads A to F. Prism reaches 11.8, 18.5, 21.0, 17.7, 9.8 and 14.1 million operations per second; SC-BTree collapses to 1.6 and 1.5 on the two write-heavy workloads and wins only on E; SC-ART stays below 3.5 throughout.

Prism’s results

Overall, Prism reaches up to 9.4× the throughput of the ported in-memory indexes and 8.6–15.1× that of Tigon-SWcc, a Tigon-style index whose 100M-key index does not fit in the SCR, so it keeps migrating data in and out of CXL. It also beats Chime-CXL, an RDMA index ported to CXL that pays at least two cache flushes per leaf access, by 3.6–5.7×, and with 128 MB of SCR it matches the throughput SC-ART needs unlimited SCR to reach on YCSB-A. It is not a win everywhere. At 5% writes SC-BTree is faster on range scans, since sorted keys in one large node make a scan cheap; Prism takes the lead from 10% writes. And on read-only workloads Megalon’s index, which sits in each host’s local DRAM, is faster than Prism’s, which sits in CXL; Prism wins once there are writes, by 5.5× on YCSB-A. Read the paper for the rest.

Sources & further reading

Everything this post leans on: our papers first, then every external reference.

Sources of truth

  • Megalon: Efficient Data Sharing for Partly Coherent CXL Memory. OSDI 2026 (best-paper nominee).

    Jiyu Hu, Seokjoo Cho, Landon Johnson, Kiran Hombal, Shreesha G. Bhat, Marcos K. Aguilera, Ramnatthan Alagappan, Aishwarya Ganesan

    paper (PDF) · slides (PDF) · USENIX page · artifact on GitHub

  • Disk-Based LSMs: An Unexpectedly Good Index for Partly Coherent CXL Memory. SOSP 2026.

    Kiran Hombal, Jiyu Hu, Marcos K. Aguilera, Ramnatthan Alagappan, Aishwarya Ganesan

    paper (PDF) · ACM DOI

The numbers in this post come from those two sources. Where a chart’s values were read off a paper figure rather than taken from a table, its caption says so. The background facts below were checked against each linked page; the one whose URL no longer resolves says so in its entry.

CXL and hardware

Tiering and sharing systems

Data structures and protocols

Benchmarks