Disk Space Manager

Storage Block Allocator

Design the part of a file system that hands out fixed-size disk blocks, takes them back, reports fragmentation, and packs files together again.

Overview

A disk is a long row of fixed-size blocks. A file system has to remember which blocks are free, hand some out when a file is written, take them back when it is deleted, and keep track of which blocks belong to which file. This problem asks you to design that allocator: the bitmap that records free and used blocks, the policy that picks blocks for a new file, and a defragmenter that moves files so each one sits in a single run.

The problem is a memory allocator with two differences. Blocks are all the same size, so there is no size field to manage. And position matters: a spinning disk reads a run of adjacent blocks much faster than the same blocks scattered across the platter (on an SSD the gap is smaller but still there), so the allocator cares not just whether space exists but whether it is together. That gap between 'enough free blocks' and 'a long enough free run' is external fragmentation, and it is the idea the interviewer is testing.

A strong answer names the bitmap in the first minute, gives its size (one bit per block), shows two allocation policies behind one interface, and writes a defragmenter that walks the disk once and provably keeps every file's data intact.

Scoping the problem

Fixed block size? — Same-size blocks mean a bitmap is enough; variable sizes need a size-aware allocator — Fixed; the demo uses tiny blocks so the layout fits on one line
Scattered or contiguous allocation, or both? — Contiguous reads faster but can fail when free space is split up — Both, as interchangeable policies
Do we store the data or only the map? — Storing bytes per block lets a test prove defragmentation moved data correctly — Yes, a list of bytes per block
Can a file grow after it is written? — Growing a contiguous file needs free blocks right after it — No; a rewrite frees the old blocks first
Many threads? — Two writers must never get the same block — Yes, one lock around every operation
When to defragment? — Needs a metric — On demand; the metric is the share of files in more than one extent

The bitmap

One bit per block: 0 free, 1 in use. It is small: a disk of 1 GiB in 4 KiB blocks has 262,144 blocks, and 262,144 bits is 32 KiB. Real file systems use the same structure. The ext4 documentation describes a data block bitmap per block group that tracks the usage of that group's data blocks, and the OSTEP file-system chapter builds its example file system on an inode bitmap and a data bitmap, noting that a single 4 KB block of bits can track 32K objects.

Is block i used? — test bit i — O(1)
Free count — a counter kept in step with set and clear — O(1)
First k free blocks (scattered) — scan from block 0 — O(n)
First run of k free blocks (contiguous) — scan, counting the current run — O(n)
Largest free run — one scan — O(n)

The scans are the cost of a bitmap. Real allocators speed them up by remembering where the last search stopped, by keeping a per-group free count so empty groups are skipped, or by keeping a separate tree of free runs. Say this in the interview; the bitmap alone is the right first answer.

Write, delete and the two policies

The trace below is the demo's first disk: 16 blocks, one character per block, a dot for free.

1 — write a (2 blocks) — aa.............. — first fit from block 0
2 — write b (2), write c (1) — aabbc...........
3 — delete b — aa..c........... — a two-block hole opens
4 — write d (3 blocks), scattered — aaddcd.......... — d fills the hole and spills past c: two extents
5 — defragment — aacddd.......... — files packed in name order; d is one extent

With the contiguous policy, step 4 would skip the hole and place d at blocks 5 to 7. With a smaller disk it can fail outright, which is the second demo: four blocks are free but the longest run is two, so a three-block file is refused until a defragment.

Scattered (first fit) — the lowest free blocks, wherever they are — yes — may seek between extents
Contiguous — the first run long enough — no: external fragmentation — one sequential read

Defragmentation in one pass

The defragmenter walks files in a fixed order and assigns the next destination block to each of their blocks in turn. When the destination is free, the block moves there. When the destination is occupied, its occupant has not been placed yet, so the two blocks swap and the occupant's file entry is updated through a reverse map from block to owner. One pass, no temporary disk space, every file ends in one extent.

The metric that decides when to run it is fragmentation(): the share of files with more than one extent. An extent is a run of adjacent blocks written as (start, length), the same idea ext4 uses in place of one pointer per block. The ext4 documentation gives the example that a contiguous run of 1,000 blocks needs an indirect block under the old scheme but a single extent with length 1,000 under the new one.

What you will be able to do

Explain the bitmap: one bit per block, the size math, and which operations are O(1) and which scan.
Show scattered and contiguous allocation behind one interface, and explain external fragmentation with a concrete failed allocation.
Write a defragmenter that packs the disk in one pass and prove with reads that no data moved wrongly.
Define a fragmentation metric in terms of extents and say when to act on it.
Connect the toy to ext4: block bitmaps per group, extents instead of block pointers.

Functional requirements

write(name, data) allocates ceil(len / block_size) blocks under the current policy and stores the data; rewriting a name frees its old blocks first
read(name) returns the bytes in file order, trimmed to the stored size
delete(name) frees the blocks and returns False for an unknown name
Two policies: Scattered takes the lowest free blocks; Contiguous takes the first run long enough or refuses
defragment() packs every file at the front of the disk in one extent each and returns how many blocks changed position
fragmentation() is the share of files stored in more than one extent; stats() reports free blocks and the largest free run
An allocation that cannot be met raises OutOfSpace and leaves the disk unchanged

Non-functional requirements

The bitmap costs one bit per block: 32 KiB for a 1 GiB disk of 4 KiB blocks
Block status and the free count are O(1); allocation scans are O(n) in the number of blocks
Defragmentation walks the disk once and needs no spare blocks
Data integrity: after any sequence of operations every file reads back exactly as written
One lock makes write, read, delete and defragment safe from many threads; no block is ever handed to two files

Interview questions

Why a bitmap rather than a free list?
What is external fragmentation, and how do extents help?
Walk me through the defragmenter. Why does swapping work, and what does it cost?
How would you support directories and file metadata on top of this?
Is one lock enough, and how would you do better?