§41.4–41.6FFS Policies, Locality, and the Large-File Exception

With the group structure in place, FFS needs an allocation policy allocation policy The rules a file system uses to DECIDE where on disk to place inodes and data blocks (as opposed to the data structures that record the result). FFS's mantra: keep related stuff together (a file's data near its inode; files in a directory near each other) and unrelated stuff apart. defined in ch. 41 — open in glossary : rules for where to put inodes and data. The mantra is simple — keep related stuff together (and unrelated stuff apart).

41.4 Policies: Placing Files and Directories

FFS uses a few common-sense heuristics. Directories go in a group with few existing directories (to spread them out) and many free inodes (so its files can be allocated nearby). Files follow two rules: put a file’s data blocks in the same group as its inode (no more inode→data seek), and put files from the same directory in the same group. Watch it against a naive alternative:

41.5 Measuring Locality

Does directory-based grouping actually match how files are used? The namespace locality namespace locality The tendency for files that are close in the directory tree to be accessed close together in time (e.g. compiling all the files in one directory). FFS exploits it by placing files from the same directory in the same group. Distinct from spatial/temporal locality, which are about addresses/time. defined in ch. 41 — open in glossary in real traces (SEER) says yes: measure the directory-tree distance between consecutive file accesses (0 = same file, 1 = same directory, 2 = shared grandparent…), and about 40% of accesses are at distance 0 or 1 — exactly what FFS optimizes:

Notably, a big chunk of accesses are at distance 2 (jumping between sibling directories like src and obj) — locality FFS’s one-level policy does not capture.

41.6 The Large-File Exception

There’s one problem with “keep a file’s blocks in its group”: a large file would fill an entire group, leaving no room for the related small files that also want to live there. So FFS makes the large-file exception large-file exception FFS's rule that overrides 'keep a file's blocks in one group' for big files: after a chunk (e.g. the 12 direct blocks) fills part of a group, later chunks spill into other groups. This stops one large file from filling a group and destroying locality for related small files — at the cost of extra seeks, amortized by using large enough chunks. defined in ch. 41 — open in glossary :

Spreading a file across groups obviously hurts sequential reads — but amortization rescues it: if each chunk is big enough, you spend most of your time transferring and little time seeking between chunks. With a 40 MB/s disk and 10 ms average positioning, the chunk needed for 50% of peak bandwidth is:

Push for higher bandwidth and the chunk grows fast:

FFS itself used a simpler rule tied to the inode: the first 12 (direct) blocks go in the inode’s group, and each indirect block’s worth of data (1024 blocks = 4 MB) goes in a different group.