Key-Value (KV) Cache Block Transfer Protocol (KBTP) over RDMA: Block Load, Mapped Store, and Unmapped Store

1.1. Background

The KV cache that attention layers keep for processed tokens is reused across decoding steps and, increasingly, across requests. Longer context windows make it larger than accelerator memory can hold, so serving systems store it in several tiers and move it between prefill instances, decode instances, and cache servers [PAGEDATTENTION] [MOONCAKE]. Two organizations are common: a central KV store that inference instances write to and read from, and peer-to-peer transfer in which, for example, a prefill instance writes directly to the decode instance that will use the cache. In both, the data moves in fixed-size blocks (typically holding the cache of 16 to 512 tokens, from kilobytes to megabytes) over RDMA.¶

1.2. Problem Statement

Three RDMA usage patterns are common today:¶

1. One-sided access to statically allocated memory: the target registers a large region in advance (often gigabytes) and the source writes or reads it directly. Access is fast, but the coarse static allocation leaves much memory unused.¶
2. One-sided access to dynamically allocated memory: the source asks the target, with a two-sided remote procedure call, to allocate a fine-grained region (for example 4 KiB to 1 MiB), then accesses it one-sidedly. Memory is used well, but every allocation involves the target CPU, which limits throughput and adds latency.¶
3. Two-sided transfer: the source sends the data in messages and the target CPU allocates memory and copies or registers it. Memory is used well, but every transfer involves the target CPU.¶

No interoperable protocol provides fine-grained allocation and one-round-trip block access without per-operation involvement of the target CPU. Since inference instances and cache servers are built by different implementers, the message formats and the structure of target memory must be specified, not only the RDMA operations.¶

1.3. Overview

A KBTP target manages a pool of equally sized blocks. It keeps a block table that maps block handles to blocks, and a free-block ring that lists unallocated blocks. An initiator sends one request message per operation; the target answers with a completion. The operations are:¶

Block Load:

the target looks up the handle and writes the block into a buffer named by the initiator.¶

Block Mapped Store:

the target looks up the handle and writes data supplied by the initiator into the block.¶

Block Unmapped Store:

the target takes a free block from the ring, binds it to the handle, and writes the data into it.¶

Block Free:

the target unbinds the handle and returns the block to the ring.¶

Each operation needs a fixed, short sequence of RDMA operations at the target whose addresses come from the request, the table, or the ring. The formats in this document are designed so that the target can pre-post these sequences and let its RDMA interface execute them when a request arrives (Section 8). A target that processes requests in software is equally conformant; the initiator cannot tell the difference.¶

Optional direct modes let initiators that the target trusts read blocks and allocate them with one-sided operations only (Section 6.6).¶

1.4. Scope and Relationship to Other Work

KBTP defines an upper-layer protocol in the sense of RDMAP [RFC5040], like the RDMA transport for RPC [RFC8166] and iSER [RFC7145]. It is bound normatively to RDMAP over DDP [RFC5041] and MPA [RFC5044] [RFC6581], with the atomic and immediate data operations of [RFC7306]. A mapping to InfiniBand reliable connections and RoCEv2 [IBTA] is given in Section 9.2. KBTP does not define new RDMA operations. [I-D.talpey-rdma-commit] specifies RDMA extensions for remote persistence and visibility, which KBTP targets can use for persistent tiers. Block keys and cache indexing, which tell an initiator which handle holds a given block, are provided by [I-D.li-kvcache-efficient-storage] or by local means.¶

Typical uses are: storing the KV cache of external knowledge (retrieval-augmented generation documents) once and loading it into any instance; keeping the cache of very long contexts in a shared pool and reusing it across requests; and caches embedded in network devices of computing power networks.¶

3.1. Block Pool

The target allocates F blocks of Block Size octets each within a memory region named by the Pool STag. Each block is identified by its Block Offset. Tables and ring slots store Block Offsets rather than block numbers, so that a value read from them can be used directly as the address of an RDMA operation without arithmetic.¶

3.2. Block Table

The block table has one 16-octet entry per handle that the target serves. The entry for handle h is at Table Offset + 16 * (h - Table Base Handle) within the Table STag.¶

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             Flags             |          Generation           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Data Length                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Block Offset (64 bits)                    |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Flags: 0x0001 VALID (the handle is bound), 0x0002 SEALED. Data Length is the number of valid octets in the block. Generation never takes the value zero. An entry is written only by the target; when it binds an entry, the target writes Data Length and Block Offset before Flags and Generation.¶

3.3. Free-Block Ring

The free-block ring has N slots, where N = 2^n is a power of two not smaller than F, and two 64-bit counters, Head (used to allocate) and Tail (used to free), each aligned to 8 octets. Each slot is 16 octets:¶

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Sequence (Ticket)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           Reserved                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Block Offset (64 bits)                    |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A slot whose Block Offset is all ones is empty (consumed). Each counter holds two fields that advance together: a 32-bit Ticket in bits 63-32 and the Slot Offset, the byte offset of the current slot (16 times the slot number), in the low n+4 bits. Bits 31 to n+4 are zero. Counters are modified only with FetchAdd Section 5.1.1 of [RFC7306] using:¶

   Add Data = 0x0000000100000010
   Add Mask = bit 63 | bit 31 | bit (n+3)

The Add Mask makes each field add independently and discard its carry, so one FetchAdd returns the current Ticket and Slot Offset and advances the Ticket by one and the Slot Offset by one slot, wrapping at the end of the ring. The returned Slot Offset can be used as an address offset without further arithmetic, which allows targets to execute the allocation in their RDMA interface. Counters are in the target's memory byte order, as RFC 7306 specifies for atomic operations; they are never read with RDMA Read.¶

The rules are:¶

• Initialization: for s < F the target writes slot s = {Sequence s, Block Offset of the s-th free block}; for F <= s < N it writes {Sequence s - N (modulo 2^32), all ones}. It sets Head to Ticket 0 and Slot Offset 0, and Tail to Ticket F and Slot Offset 16 * (F mod N).¶
• Allocation: FetchAdd on Head returns ticket t and offset o. The slot at o holds the block for this allocation once its Sequence equals t and its Block Offset is not all ones; until then the allocator re-reads the slot. Having taken the Block Offset, the slot is marked consumed by setting its Block Offset to all ones: by the target itself for target-executed allocations, and by the target when it processes BIND for direct allocations (Section 6.6).¶
• Free: the target first updates the table entry (Section 6.4), then performs FetchAdd on Tail, obtaining ticket u and offset o. If the slot at o is consumed, the target writes the Block Offset and then Sequence u. If it is not yet consumed, because the allocation that owns it has taken its ticket but not yet read it, the target MUST defer the write until the slot is consumed; it MUST NOT overwrite the slot.¶

With these rules no block is ever lost or handed out twice: each slot is written only after its previous content has been consumed, and each allocation reads exactly the slot written for its ticket. Writing the Block Offset before the Sequence ensures that a reader that observes the new Sequence also observes the new Block Offset.¶

3.4. Allocation Quotas

The target assigns each initiator an Allocation Quota at session setup and keeps the sum of quotas not larger than F. An initiator's usage is the number of handles it has bound plus the number of tickets it has taken and not yet bound. An initiator MUST NOT exceed its quota; the target releases one unit of usage when a FREE completes or when an abandoned ticket is reclaimed. When all initiators respect their quotas, the ring always holds a block for every ticket taken, so an allocation waits at most for an in-progress free to finish writing its slot.¶

Target-executed allocations take blocks from a ring shared by all initiators that the target serves this way. For DIRECT_ALLOC (Section 6.6), the target instead gives each initiator its own ring and Head counter over a partition of the pool whose size equals the initiator's quota, so that every ticket on that ring belongs to that initiator and the quota is enforced by the ring itself. A ticket that is not bound by BIND within the Ticket Timeout advertised in HELLO_ACK is abandoned. Before reclaiming its block, the target MUST ensure that no RDMA Write of the initiator can still reach the block, by invalidating the initiator's Partition STag (Section 4), which disables DIRECT_ALLOC for the rest of the session, or by terminating the connection. It then consumes the slot, returns the block to the ring with a new ticket, and rejects a later BIND for that ticket with status TICKET_ABANDONED. If a target observes an allocation by an initiator that exceeds its quota, it completes the request with NO_SPACE and MAY terminate the session.¶

5.1. Common Header

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Version    |    Opcode     |             Flags             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Request ID (64 bits)                      |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Block Handle (64 bits)                     |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          Generation           |            Status             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version is 1. Opcodes are listed in Table 2. Request ID is chosen by the initiator and echoed in the completion. Generation in a request is the generation the initiator expects (zero means "any"); in a completion it is the entry's current generation. Status is zero in requests. Flags are interpreted per opcode; for LOAD, STORE, ALLOC_STORE, and FREE they are:¶

• 0x0001 INLINE: data follows the request.¶
• 0x0002 SEAL: seal the block after the store.¶
• 0x0004 RECORD: complete with a completion record (Section 6.5); a Completion Descriptor is present.¶
• 0x0008 INVALIDATE: the target completes with Send with Invalidate [RFC5040], invalidating the STag of the initiator's Data Descriptor.¶
• 0x0010 ALLOW_UNSEALED: a load may return an unsealed block.¶

5.2. Descriptors

A Data Descriptor is 16 octets: STag (32 bits), Tagged Offset (64 bits), and Length (32 bits), naming a buffer of the initiator. For LOAD it is the destination; for STORE and ALLOC_STORE it is the source that the target reads with RDMA Read, unless INLINE is set, in which case STag and Tagged Offset are zero, Length is the inline data length, and the data follows the message. A Completion Descriptor is 16 octets: STag (32 bits), Tagged Offset (64 bits), and 32 reserved bits, naming a 24-octet completion record slot of the initiator.¶

6.1. Block Load

1. The target reads the table entry of the handle. The entry MUST be VALID, and SEALED unless ALLOW_UNSEALED is set.¶
2. It RDMA-writes Data Length octets of the block to the Data Descriptor. Data Length MUST NOT exceed the descriptor Length.¶
3. It completes the request (Section 6.5) with the Block Offset, Data Length, and Generation of the entry.¶

6.2. Block Mapped Store

1. The target reads the table entry, which MUST be VALID and not SEALED and MUST belong to the initiator's handle range.¶
2. It obtains the data, from the inline payload or by RDMA Read from the Data Descriptor, and writes it into the block.¶
3. It updates Data Length and, if SEAL is set, sets SEALED.¶
4. It completes the request.¶

6.3. Block Unmapped Store

1. The handle MUST be in the initiator's range and its entry MUST NOT be VALID.¶
2. The target allocates a block from the ring and marks the slot consumed (Section 3.3).¶
3. It obtains the data and writes it into the block.¶
4. It writes the table entry with the Block Offset and Data Length, then with VALID, SEALED if requested, and the next Generation (incremented by one, skipping zero).¶
5. It completes the request with the Block Offset and Generation.¶

The entry is written after the data, so any initiator that observes VALID in the entry also observes the data.¶

6.4. Block Free

1. The handle MUST be in the initiator's range and VALID.¶
2. The target clears VALID and SEALED and increments the Generation (skipping zero) in the table entry.¶
3. It returns the block to the ring from which it was allocated (Section 3.3), after the entry update is visible.¶
4. It completes the request.¶

Initiators that may still be loading the block detect the free by the changed Generation. If the block may next be allocated to an initiator of a different trust domain, the target clears its contents before returning it to the ring.¶

6.5. Completion

By default the target completes a request with a COMPLETION message sent as a Send (or Send with Invalidate when INVALIDATE is set). In the RDMAP binding, the contents of a buffer written by RDMA Write are determinate once a subsequent Send has been delivered (rule 5 of Section 5.5 of [RFC5040]), so receipt of the completion implies that the loaded data is in the initiator's buffer.¶

If the target advertised RECORD_COMPLETION and the request has the RECORD flag, the target instead writes a 24-octet completion record to the Completion Descriptor: Request ID (64 bits), Status (16 bits), Generation (16 bits), Data Length (32 bits), and Block Offset (64 bits). A target MUST use completion records only on bindings in which an RDMA Write cannot become visible before the data of earlier RDMA Writes on the same connection. RDMAP does not guarantee this (rules 3 and 5 of Section 5.5 of [RFC5040]), so a target MUST NOT advertise RECORD_COMPLETION in the RDMAP binding.¶

6.6. Direct Modes

Direct modes expose target structures to the initiator and are OPTIONAL. A target MUST offer them only to initiators it trusts for all blocks reachable through the exposed STags.¶

Direct Load (DIRECT_LOAD): through the read-only Table and Pool STags, the initiator RDMA-reads the table entry, then the block, then the entry again, issuing each read only after the previous one has completed. The data is valid if both entry reads show the same Generation with VALID and SEALED set, because a sealed block does not change until it is freed and a free changes the Generation. This costs two round trips but no target processing.¶

Direct Allocation (DIRECT_ALLOC): the initiator performs FetchAdd on its Head with the Add Data and Add Mask of Section 3.3, RDMA-reads the slot at the returned offset (re-reading until the Sequence equals its ticket and the Block Offset is not all ones, and then once more to confirm both values, since a 16-octet read is not guaranteed to be atomic), RDMA-writes the data into the block, and then sends BIND with the ticket, Data Length, and Block Offset. The target verifies that the ticket has not been abandoned, that the slot of the ticket holds that Block Offset, and that the initiator is within its quota; it then marks the slot consumed, writes the table entry, and completes. The initiator never writes ring slots. Frees always use FREE.¶

9.1. RDMAP Binding

• KBTP runs over an RDMAP Stream [RFC5040] on DDP [RFC5041] and MPA [RFC5044]. Peers SHOULD use the enhanced connection establishment of [RFC6581]. Targets that advertise DIRECT_ALLOC, and targets that execute allocations in their RDMA interface, MUST support the atomic operations of [RFC7306].¶
• Requests, HELLO, HELLO_ACK, and COMPLETION are carried in Send or Send with Solicited Event messages; INVALIDATE uses Send with Invalidate.¶
• Loads use RDMA Write; stores without INLINE use RDMA Read by the target.¶
• Ring counters use FetchAdd with the Add Mask of Section 3.3.¶
• Completions are always COMPLETION messages; RECORD_COMPLETION is not offered (Section 6.5).¶
• The security of the binding is that of [RFC5042]; when the network is not trusted, IPsec MUST be used as specified there.¶

9.2. InfiniBand and RoCEv2

Over an InfiniBand reliable connection or RoCEv2 [IBTA], the same messages are carried with Send, RDMA Write, and RDMA Read. The InfiniBand specification defines an unmasked Fetch and Add; masked variants exist as vendor extensions. With unmasked Fetch and Add, the Head and Tail counters hold the Ticket in their high 32 bits and zero in their low 32 bits (Add Data 0x0000000100000000), and the slot is computed as 16 * (ticket mod N) by the initiator in DIRECT_ALLOC or by the target in software. Completion records on these transports MUST be written with RDMA Write with Immediate, so that the initiator learns of completion from its completion queue rather than by polling memory.¶