E3.6 · LESSON 6 OF 6

Allocation and release

Allocate logical token blocks to physical KV-cache blocks and quantify internal waste and shared-prefix behavior.

THE IDEA

Releasing blocks correctly

When a request finishes, is cancelled or is evicted, its blocks are released: each block's reference count goes down by one, and only a block that reaches zero returns to the free list. A block still referenced by another sequence must stay allocated. Correct bookkeeping (no leaks, no double frees, counts matching the tables) matters as much as the block-size arithmetic.

#0A+B ×2

#1A ×1

#2B ×1

#3free

#4free

#5free

#6free

#7free

#8free

#9free

sequence	tokens	block table (logical → physical)
A	20	[0, 1]
B	21	[0, 2]

free blocks: 7 of 10 in use: 3 (×n = reference count, striped = shared)

state: A [0,1], B [0,2] (block 0 shared)

A block is freed only when its reference count reaches zero. Freeing a block another sequence still uses would corrupt that sequence: correct bookkeeping matters as much as the block-size arithmetic.

Release A or B and see which blocks come back.

Predict first. Should a block still referenced by another sequence be freed?

Chapter context

Contiguous reservation can waste memory when sequence lengths differ or grow unpredictably. Paging separates a sequence's logical block order from the physical blocks storing its cache.

TRY IT YOURSELF

Part 1. Do it hands-on

Release a sequence by hand, then write release, a consistency check and release-all for the block manager.

#0A+B ×2

#1A ×1

#2B ×1

#3free

#4free

#5free

#6free

#7free

#8free

#9free

sequence	tokens	block table (logical → physical)
A	20	[0, 1]
B	21	[0, 2]

free blocks: 7 of 10 in use: 3 (×n = reference count, striped = shared)

state: A [0,1], B [0,2] (block 0 shared)

A block is freed only when its reference count reaches zero. Freeing a block another sequence still uses would corrupt that sequence: correct bookkeeping matters as much as the block-size arithmetic.

blocks freed when A is released reference count of block 0 after that free blocks now

To do: Continue the scenario: A finishes and is released (A held blocks 0 and 1; B holds 0 and 2). How many blocks go back to the free list?
To do: What is the reference count of block 0 after A is released?
To do: How many blocks are free now (of 10)?

Part 2. Do it in code

BlockManager is provided with allocate, fork and append already written (copy-on-write included). Write:
release(name): drop the sequence: decrease each of its blocks' reference counts by 1; a block whose count reaches 0 is removed from ref and returned to the free list (keep the free list sorted). Remove the sequence. Return the sorted list of blocks that were actually freed. KeyError if the sequence does not exist.
check_invariants(): return True only if (a) free blocks and referenced blocks are disjoint and together are exactly the blocks 0..total−1, and (b) each block's reference count equals the number of sequence tables that contain it.
release_all(): release every sequence and return the sorted list of all blocks freed.

import math

class BlockManager:
    def __init__(self, num_blocks, block_size):
        self.block_size = block_size
        self.total = num_blocks
        self.free = list(range(num_blocks))
        self.ref = {}
        self.seqs = {}

    def _take(self):
        if not self.free:
            raise MemoryError("out of blocks")
        b = self.free.pop(0)
        self.ref[b] = 1
        return b

    def allocate(self, name, n_tokens):
        need = math.ceil(n_tokens / self.block_size)
        if need > len(self.free):
            raise MemoryError("not enough free blocks")
        self.seqs[name] = {"blocks": [self._take() for _ in range(need)], "len": n_tokens}

    def fork(self, parent, child):
        p = self.seqs[parent]
        self.seqs[child] = {"blocks": list(p["blocks"]), "len": p["len"]}
        for b in p["blocks"]:
            self.ref[b] += 1

    def append(self, name):
        s = self.seqs[name]
        copied = False
        if s["len"] % self.block_size == 0:
            s["blocks"].append(self._take())
        else:
            last = s["blocks"][-1]
            if self.ref[last] > 1:
                new = self._take()
                self.ref[last] -= 1
                s["blocks"][-1] = new
                copied = True
        s["len"] += 1
        return copied

    def used(self):
        return self.total - len(self.free)

    def release(self, name):
        pass

    def check_invariants(self):
        pass

    def release_all(self):
        pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Should a block still referenced by another sequence be freed?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For length T and block capacity P:

n_{blocks}=\lceil T/P\rceil,\quad slots=P\lceil T/P\rceil,\quad slack=slots-T.

Slack as a fraction of allocated slots is slack/slots. State the denominator when reporting waste percentages.

Worked example

A sequence has 33 tokens and blocks hold 16. It requires ceil(33/16)=3 blocks, allocating 48 token slots. Fifteen slots are unused, so internal slack is 15/48=31.25% of this allocation. It is not 31.25% of all GPU memory, and shared blocks change total ownership accounting.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import ceil,isclose
tokens,capacity=33,16
blocks=ceil(tokens/capacity)
slots=blocks*capacity
assert blocks == 3 and slots == 48
assert slots-tokens == 15
assert isclose((slots-tokens)/slots,.3125)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Paging improves allocation flexibility but does not make memory unlimited. Logical block order differs from physical layout. Internal slack and external fragmentation are different kinds of waste.