Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 41, Arpaci-Dusseau & Arpaci-Dusseau

Locality and The Fast File System

Ken Thompson’s first UNIX FS was simple (superblock, inodes, data, free list) — and eventually delivered only ~2% of disk bandwidth [MJLF84].

Crux: how to organize on-disk data (and policies) so the FS is disk-aware?

The problem​

The old FS treated the disk like RAM:

  • Inodes far from their data → seeks on common open+read paths
  • Free-list fragmentation → logically contiguous files hop around the platter
  • 512 B blocks → positioning overhead dominates transfer

Defragmenters exist because of this class of mess.

FFS: same API, new guts​

Berkeley’s Fast File System kept open/read/write/… compatible and redesigned layout + allocation — the template for modern FS evolution (ext2/3/4 are intellectual descendants).

Cylinder / block groups​

FFS divides the disk into cylinder groups (same-radius tracks across surfaces). Modern drives hide geometry, so Linux uses block groups: consecutive LBA ranges.

Each group holds: replica superblock, inode bitmap, data bitmap, inodes, data. Bitmaps make finding contiguous free space easier than a free list.

ObjectHeuristic
DirectoryGroup with few dirs + many free inodes (balance + room for files)
File inode + dataSame group (no inode↔data seek)
Files in one directorySame group as that directory (namespace locality)

SEER-style traces show lots of opens at distance 0–1 in the tree (same file / same dir) — FFS matches that. Distance-2 patterns (e.g. src/ ↔ obj/) are weaker under FFS.

Large-file exception​

Without a rule, one huge file fills a group and crowds out siblings. FFS places the first directs locally, then each large chunk (historically each indirect tree ≈ 4 MB at 4 KB / 32-bit) in other groups.

Amortization: with ~10 ms position and 40 MB/s, ~410 KB/seek ≈ 50% bandwidth; ~3.7 MB ≈ 90%. Transfer rates improve faster than seeks → chunks grow over time.

Other FFS ideas​

  • Sub-blocks (512 B) for small files; promote to 4 KB (libc write buffering avoids thrashing)
  • Parameterized sector skew for slow host-driven disks (track buffers made this obsolete)
  • Usability: long names, symlinks, atomic rename
Make the system usable

Adoption often rides on small UX wins as much as seek math.

Interactive​

Try: old-FS fragmentation · groups/policies · large-file chunking · extras.

Check your understanding​

Quiz

Fast File System

1 / 6

The old UNIX FS’s main performance sin was…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: ffs.py​

Use the OSTEP file-ffs homework (ffs.py).

Lab

Homework: ffs.py

0/4 started

Loading lab…

Summary​

IdeaTakeaway
Old FSSimple APIs, disk-blind → fragmentation + seeks
GroupsLocality containers with local bitmaps/inodes/data
PoliciesRelated names → nearby blocks
Large filesChunk across groups; amortize seeks
LessonTreat the disk like a disk — still true for HDDs

Previous: File System Implementation

Next: Crash Consistency — fsck, journaling, ordered metadata.

Further Reading​