The cost of utilization, u/(1-u)

Simulate a modelNeeds Python

Problem

A log-structured store writes new data at the end and reclaims space by cleaning: it picks a block, copies its live pages forward, and frees it. If a block cleaned has a fraction u of live pages, freeing (1 − u) of space costs copying u, so the copying per page of new space is u/(1 − u): one page at 50% full, nine at 90%, nineteen at 95%. A greedy cleaner that picks the emptiest block does better than the average, because random overwrites leave some blocks much emptier than others.

Write a small simulation of a log-structured store: 1,000 blocks of 100 pages, a fixed fraction u of pages live, random overwrites, and a greedy cleaner that picks the block with the fewest live pages. Measure pages copied per page of new space for u = 0.5, 0.7, 0.9, 0.95.

The question. How does the cleaning cost grow with utilization, and how does the greedy cleaner compare with u/(1 − u)?

Predict

At u = 0.9, how many pages does the greedy cleaner copy per page of new space?

Under 11 to 55 to 1212 or more

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

the-cost-of-utilization-u-1.py52 linesDownload

View the code

the-cost-of-utilization-u-1.py

# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""The cost of utilization: u / (1 − u).

A log-structured store of 1,000 blocks of 100 pages with a fraction u of pages
live, random overwrites, and a greedy cleaner that cleans the block with the
fewest live pages. Pages copied per page of new space for u = 0.5 to 0.95,
against u / (1 − u).
"""
import argparse, json, random

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--blocks", type=int, default=1000, help="Blocks.")
p.add_argument("--pages", type=int, default=100, help="Pages per block.")
p.add_argument("--us", default="0.5,0.7,0.9,0.95", help="Utilizations.")
p.add_argument("--writes", type=int, default=1_000_000, help="Overwrites measured (after a warm-up of the same size).")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

def run(u):
    rng = random.Random(args.seed); B, P = args.blocks, args.pages; live_pages = int(u * B * P)
    where = {}; live = [0] * B; content = [[] for _ in range(B)]; free = set(range(B)); cur = free.pop(); full = set()
    stats = {"copied": 0}
    def append(lpn):
        nonlocal cur
        if len(content[cur]) == P: full.add(cur); cur = free.pop()           # a new block; cleaning keeps at least one free
        content[cur].append(lpn); where[lpn] = (cur, len(content[cur]) - 1); live[cur] += 1
    def clean():
        victim = min(full, key=lambda b: live[b])                          # greedy: the full block with the fewest live pages
        survivors = [l for i, l in enumerate(content[victim]) if l is not None]
        full.discard(victim); content[victim] = []; live[victim] = 0; free.add(victim)
        for l in survivors: append(l); stats["copied"] += 1
    def write(l):
        while len(free) < 2: clean()
        append(l)
    for l in range(live_pages): write(l)
    for phase in range(2):                                                  # a warm-up phase, then the measured one
        stats["copied"] = 0
        for _ in range(args.writes):
            l = rng.randrange(live_pages); b, i = where[l]; content[b][i] = None; live[b] -= 1; write(l)
    return stats["copied"] / args.writes
rows = [{"u": u, "copied_per_new_page": run(u), "formula": u / (1 - u)} for u in map(float, args.us.split(","))]
for r in rows: print(f"u = {r['u']:.2f}: greedy cleaner copies {r['copied_per_new_page']:6.2f} pages per new page   (u/(1-u) = {r['formula']:.2f})")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"utilization": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run the-cost-of-utilization-u-1.py
uv run the-cost-of-utilization-u-1.py --help     # every knob
```

Knobs
Knob · default	What it changes
--blocks1000	Blocks.
--pages100	Pages per block.
--us0.5, 0.7, 0.9, 0.95	Utilizations.
--writes1,000,000	Overwrites measured (after a warm-up of the same size).
--seed0	Random seed.

Our run

Cleaning cost against utilizationApple M2 · 8 cores · 8 GB

Greedy cleaneru/(1 − u)

Data table

Cleaning cost against utilization
Live fraction u	Greedy cleaner	u/(1 − u)
0.5	0.247	1
0.7	0.858	2.33
0.9	4.03	9
0.95	8.61	19

macOS 26.6.2 · Python 3.13.3 · run 2026-10-25

Output · uv run the-cost-of-utilization-u-1.py

u = 0.50: greedy cleaner copies   0.25 pages per new page   (u/(1-u) = 1.00)
u = 0.70: greedy cleaner copies   0.86 pages per new page   (u/(1-u) = 2.33)
u = 0.90: greedy cleaner copies   4.03 pages per new page   (u/(1-u) = 9.00)
u = 0.95: greedy cleaner copies   8.61 pages per new page   (u/(1-u) = 19.00)

What we found

The greedy cleaner copied 0.247 pages per new page at u = 0.5, 0.858 at 0.7, 4.03 at 0.9 and 8.61 at 0.95: the same sharp rise as u/(1 − u), at about half its values, because random overwrites leave some blocks much emptier than the average and the greedy cleaner picks those.

Read it

Free space is the cleaner's fuel: the last 10% of utilization costs more than all the rest. Every log-structured system (LSM trees, flash translation layers, log-structured file systems) reserves headroom for this reason, and separating data by lifetime lowers the cost at any utilization.