Clio: a hardware-software co-designed disaggregated memory system

Clio builds a memory box that plugs straight into the datacenter network, and makes it fast by removing almost all the per-client bookkeeping from the box and pushing that work onto the clients.

Why remote memory is worth the trouble

Start with one application. A graph analytics job wants 3 terabytes of memory. The largest server you can buy holds 1 terabyte. You have three choices. Split the job across three machines and pay the cost of splitting. Buy a much more expensive machine. Or reach memory that lives somewhere else.

The third choice has a second, separate benefit. In a datacenter, each server holds its own memory, and that memory is used unevenly. One machine is full while its neighbour is half empty. If instead the memory sits in a shared pool, any machine can take what it needs. Nothing is stranded.

This arrangement is called memory disaggregation. The machines that run programs are compute nodes. The machines that hold memory are memory nodes. They are connected by an ordinary datacenter network.

The hard part is building the memory node. The paper states four targets that must hold at the same time:

1. Capacity. Hundreds of gigabytes to a few terabytes per memory node, used close to fully.
2. Concurrency. Thousands of client processes, running on tens of compute nodes, sharing one memory node.
3. Speed. 100 gigabits per second of throughput, and a median response time under 2 microseconds.
4. Cost. Cheaper in money and in power than simply buying more servers.

Each target alone is understood. All four together had not been solved.

What people built before, and where each one broke

Approach one: a server with an RDMA network card

Almost all earlier work takes a normal server, fills it with memory, and lets clients reach it with RDMA — Remote Direct Memory Access. RDMA is a network card feature. The card reads and writes the remote machine memory directly, and the remote processor is never interrupted. Latency is low and throughput is high. It is a reasonable starting point.

The trouble is in the bookkeeping. To make memory reachable by RDMA, a process on the memory node must register a block of memory, called a memory region, with the network card. The card then needs two kinds of information for every access: which memory region this is, and how to translate a virtual address into a physical address. That translation lives in a page table, a table in main memory that maps virtual addresses to physical addresses.

The network card cannot hold all of this. It caches page table entries and memory region descriptors in its own small memory. That works while the working set is small. The paper measured what happens when it is not.

• On their local cluster, RDMA latency starts to degrade past about 256 page table entries or memory regions. On CloudLab, with a newer ConnectX-5 network card, past about 4,096.
• RDMA fails completely beyond about 262,144 memory regions.
• Each client needs its own memory region, because that is the unit of protection. So the number of clients is capped by the same limit.

There is a second failure. A page fault is what happens when a program touches memory that has no physical page behind it yet. On a normal computer the operating system quietly allocates a page. Over RDMA the network card must interrupt the host operating system. The paper measured this at 16.8 milliseconds — the same access without a fault is 14,100 times faster. One such event ruins the response time of anything waiting on it.

Because of this, real RDMA systems avoid page faults completely. They allocate one huge block of memory in advance and pin it permanently. That defeats target one: the memory is reserved, not used.

Approach two: raw memory with no processing at all

The opposite design removes the server. The memory node is memory chips and a network port, nothing more. The paper calls this the physical disaggregated memory model. It is cheap, and it burns almost no power.

Everything then falls on the compute nodes.

• Complex operations need many round trips. Following a chain of pointers means one network round trip per pointer, because nothing at the memory node can follow a pointer for you.
• Clients must coordinate. Memory allocation has no owner, so the compute nodes must agree with each other, or ask a separate global server.
• There is no protection. Physical addresses travel over the network. A buggy or hostile client can read memory belonging to someone else.
• Memory must still be pinned, so capacity is again wasted.

The shape of Clio

Clio takes the middle position. Give the memory node some processing power — the right amount, no more. Then design the memory system and the network system together, from scratch, for this one job.

The memory node hardware is a board that the paper calls CBoard. The software that runs on each compute node is a user-space library called CLib.

The board has three paths, and a small table at the entrance decides which one each arriving request takes.

• Fast path. Every read and every write. Built in hardware. This is where all the design effort goes.
• Slow path. Memory allocation and other rare bookkeeping. Runs as ordinary software on a low-power ARM processor on the same board.
• Extend path. Optional application logic that the user offloads onto the board, so that a complex operation does not need many round trips.

The idea: remove state from the memory node

The paper has one organising idea, and it is worth stating plainly.

State is anything the memory node has to remember. Clio removes as much of it as possible, and carefully bounds what is left.

Why does remembering things hurt? Two reasons, and they are both about hardware rather than software.

First, remembered things need chip memory, and on-chip memory is the expensive resource on a chip. If the memory node remembers something per client, then more clients means more chip memory. The design stops scaling.

Second, remembered things make the pipeline stall. A hardware pipeline that must sometimes wait — for a slow table lookup, or for another request to finish first — cannot accept one new unit of data every cycle. Clio wants a pipeline that is smooth (accepts new data every single cycle) and deterministic (takes a known, fixed number of cycles). A deterministic pipeline is what gives a short tail: no request can take surprisingly long, because no path through the hardware is long.

So the memory node is not allowed to remember much. But a memory system must do several things that normally require remembering. Clio deals with each one separately.

Removed: connections

RDMA is connection-oriented. Each client pair holds a queue pair, and the card stores state for every one of them. That state is a scaling limit.

Clio observes an asymmetry. A memory node only ever responds. It never starts a conversation. So there is no need for a general two-way transport protocol. Clio uses request and response pairs with no connection at all. The client library gives each request a unique number. The memory node copies that number onto the response. The response is the acknowledgement — no separate acknowledgement packet exists in either direction.

Everything a transport protocol normally does now lives in the client library on the compute node: retry, ordering, congestion control, and control of incast (many responses arriving at one machine at the same moment). The compute node has spare processor cycles and spare memory. The memory node does not.

Removed: reliability at the packet level

Normal reliable transports resend individual lost packets. That requires remembering which packets are outstanding, which means per-connection buffers and sequence numbers.

Clio lifts reliability up one level. If anything goes wrong — a packet is corrupted, a response never arrives, a negative acknowledgement comes back — the client library simply reissues the whole memory request. Packets inside one request may therefore arrive in any order, and the memory node executes each one as soon as it lands. That is exactly what makes the pipeline smooth.

Moved to software: address allocation

Allocating a range of virtual addresses means searching a tree of free ranges. Trees are painful in hardware: they need large on-chip memory and a lot of logic. But allocation is rare. Applications allocate a few large chunks and then use them for a long time.

So allocation runs as plain software on the board ARM processor, on the slow path, and never blocks a read or a write.

Kept, but redesigned: the page table

Address translation cannot be removed. Every single access needs it. Two properties of the standard design make it wrong here.

Standard page tables are per process and multi-level. Per process means the memory node would have to cache and switch between thousands of page table roots. Multi-level means a translation miss costs several memory reads, not one.

A miss means a miss in the translation cache, a small on-chip table of recently used translations. Its usual name is the translation lookaside buffer. Misses will be frequent here, because a memory node serves many applications at once. Their combined working set is far larger than a single server working set, while the cache on the board is the same size or smaller, for cost reasons.

Clio replaces this with one flat hash table shared by every process.

• The table location in memory is fixed and known to the hardware, so finding the table costs nothing.
• Its size is set by the physical memory of the board, not by the number of clients. With the default 4 megabyte page size, the table takes 0.4% of physical memory. Add a thousand more clients and the table does not grow.
• The hash of the virtual address together with the process identifier picks one bucket. Each bucket holds a fixed number of slots, and the hardware fetches the entire bucket in one memory read.

A hash table has an obvious problem: what if too many entries land in one bucket? Existing hash page tables chain overflowing entries into a second location, which costs a second memory read, or worse, a software rescue.

Clio removes the problem instead of handling it. Overflow is prevented at allocation time. When the slow-path software allocates a virtual address range, it computes where every page in that range would land in the hash table. If any bucket would overflow, it discards the choice and searches for a different address range. It repeats until it finds a range that fits.

This is a deliberate trade. Allocation, which is rare and off the critical path, sometimes retries. Translation, which happens on every access, is then guaranteed to cost at most one memory read, always. Four things keep the retry cost small: huge pages mean fewer entries, the hash function collides rarely, the table has twice as many slots as strictly needed, and each retry is cheap.

Kept, but redesigned: page fault handling

Clio wants memory to run near full, and wants physical memory allocated only when it is actually used. So page faults must happen, and they must be fast.

Recall the RDMA number: 16.8 milliseconds. Clio handles a page fault in hardware, in three clock cycles.

The difficulty is that a page fault needs a free physical page, and finding one means walking allocation structures — a software job. Clio breaks the dependency with an asynchronous buffer. The ARM processor continuously finds free physical pages and drops their numbers into a small buffer. It does this in the background, all the time, faster than the network can deliver requests. When the hardware hits a page fault, it does not ask anyone for a page. It takes one from the buffer, which is always full.

Then it does three things at once: write the new page table entry into memory, insert it into the translation cache, and continue the request that faulted. The first two are hidden behind the third.

call:   ralloc(4 MB)
path:   slow path (ARM software)
returns: a virtual address in this process remote address space

Why it works

The causal chain is worth writing out, because every link depends on the one before it.

Because the memory node only responds and never initiates, the transport can be connection-less, and every packet can carry its own full context. → Because every packet carries its own context, the memory node can execute packets in any order, so it never has to hold one packet while waiting for another. → Because nothing waits, the hardware pipeline accepts one unit of data every single cycle, and takes a fixed number of cycles to finish. → Because the page table is one flat hash table sized by physical memory, its size does not grow when more clients arrive, and every translation costs at most one memory read. → Because overflow is prevented when addresses are allocated, “at most one memory read” is a guarantee rather than an average. → Because free physical pages are prepared in advance in a buffer, a page fault never waits for software, and costs three fixed cycles. → Therefore the slowest possible path through the memory node is short and known. That is why the tail latency is short, and why the latency stays flat as clients and memory are added.

Notice what the argument does not rely on. It does not rely on a cache being large enough. It does not rely on a common case being common. Every path through the hardware is bounded, so there is no bad case hiding behind a good average.

What it costs

Every design gives something up. This one gives up five things.

• The application must be rewritten. Clio does not pretend to be local memory. Programs call ralloc, rread, rwrite and explicit locks. This is the opposite of Pond, where the customer virtual machine is not changed at all. The paper argues that explicit calls let applications optimise, and notes that a runtime or an operating system could hide the calls later. That work is left for the future.
• Caches are not kept coherent. Two compute nodes may each cache a copy of the same remote data, and Clio will not reconcile them. The application must choose its own scheme. The authors made this choice deliberately: automatic coherence on every access would be expensive over commodity Ethernet.
• A specific virtual address cannot be guaranteed. Overflow-free allocation works by rejecting address ranges. So a request for one exact address may be refused. Code that requires fixed addresses, such as some libraries, must stay on local memory.
• Allocation gets slower as memory fills. Zero retries below half full, up to 60 retries near full. The cost is real, but it is paid in the right place.
• New hardware. The design targets a custom chip. Making it real means manufacturing a board, not shipping software.

There is also one honest limitation inside the design. Clio tracks conflicting requests at page granularity. Two accesses to different bytes of the same page look like a conflict, so one waits for the other without needing to. The authors chose this to keep the tracking cheap, and leave finer tracking for later work.

What was measured

The prototype uses a Xilinx ZCU106 board, which costs 2,495 US dollars at retail. It carries an FPGA — a Field-Programmable Gate Array, a chip whose logic can be reconfigured after manufacturing — a quad-core ARM Cortex-A53 processor, two 10 gigabit network ports, and 2 gigabytes of on-board memory. The FPGA runs at 250 megahertz. A real product would use an ASIC, an Application-Specific Integrated Circuit, a fixed chip that would run roughly eight times faster.

The test cluster had four compute nodes and four memory nodes on a 40 gigabit switch. Each compute node was a Dell PowerEdge R740 with a Xeon Gold 5128 processor and a 40 gigabit ConnectX-3 network card. Some tests were repeated on CloudLab with newer ConnectX-5 cards.

Two more results are worth stating, because they show the design paying off in whole applications rather than in microbenchmarks.

Image compression. Each client compresses and decompresses 1,000 images of 256 by 256 pixels, with the images stored remotely. As the number of concurrent clients grows from 1 to 800, Clio run time per client stays flat. RDMA run time grows. The reason is exactly the scaling limit above: each client needs its own memory region, and past a point the network card cannot hold them all.

Radix tree search. Clio offloads pointer following onto the board, so one network round trip covers one whole level of the tree. RDMA needs several round trips to walk the same tree, because the client must fetch each node itself and then decide where to look next. The paper also reports that RDMA scales worse than Clio as the tree grows from 10,000 to 1,000,000 entries.

The hardware also stays small. The whole Clio design uses 31% of the FPGA logic and 31% of its on-chip memory. For comparison, two published network stacks alone — StRoM and Tonic — use 39% and 48% of the logic. Inside Clio, the virtual memory system takes only 5.5% of the logic and the network stack 2.3%. Most of the chip stays free for application offloads, which was the point.