Inode Maps and Block Indirection: Finding Data That Never Stays in Place

In a filesystem that overwrites in place, an inode number is an address. The number is divided by the number of inodes per block, multiplied by the block size, and added to the start of the inode table; the result is the byte offset of the inode, and it stays valid for the life of the file. Nothing has to be looked up. In a log-structured filesystem that arithmetic produces an address that becomes wrong the first time the file’s metadata is modified, because the modified inode is written at the head of the log and the old copy is abandoned. If a directory entry stored the inode’s address, every metadata update to the file would require finding and rewriting every entry that names it. That is unacceptable for a file with many hard links, and impossible for an inode that a process holds open by descriptor.

The escape is to stop treating the number as an address and start treating it as a key. A separate structure maps inode numbers to the current location of their inodes, and because that structure is also updated by appending, it needs its own fixed point in the volume from which lookups can start. The log’s append discipline, described in The Log as the Filesystem, is what makes the address unstable in the first place.

What the map has to answer

The map’s contract is a single operation: given an inode number, return the disk address of the inode’s current version. Two properties constrain how it can be built.

It must be cheap to update, because every inode write updates it. If updating the map required rewriting a large region, the map would reintroduce the scattered-write problem the log was built to eliminate.

It must be readable at mount time, because the map is the only path from a name to any data. If the map’s own location were recorded only in memory, a crash would leave the volume unreadable.

Sprite’s original design satisfied both with a fixed-size array of pointers, one per inode number, stored at a known location and shadowed in memory. An inode write updates one entry in the in-memory copy; the dirty entries are written to the log at intervals and the fixed array is rewritten. The array is compact, four or eight bytes per inode, but rewriting it is a large sequential write whose size scales with the number of inodes in the filesystem rather than with the number of files that changed. On a volume with millions of inodes, that is a recurring multi-megabyte write with nothing useful in most of it.

Paging the map, and then indexing the pages

Later designs break the array into fixed-size blocks, conventionally one block per inode-number range, and treat each block as an ordinary log-structured object. Writing an inode dirties the map block that covers its number; that block is appended to the log when it is evicted. The map is now itself a set of movable objects, and a new problem appears: nothing records where map block k now lives.

The answer is a second-level structure, an inode map index, holding the disk address of each map block. It is small enough, one entry per block of map and so one entry per few hundred inodes, that it can be kept entirely in memory and rewritten in full whenever it changes. The same recursion could be carried further, but a single level suffices in practice because the index for a very large volume still fits comfortably in main memory.

/* Two-level lookup: inode number -> map block -> inode address. */
static int inode_locate(struct lfs *fs, uint64_t ino, uint64_t *addr)
{
    uint64_t blk = ino / INODES_PER_BLOCK;      /* which map block holds it */
    uint64_t slot = ino % INODES_PER_BLOCK;

    if (blk >= fs->imap_blocks)                  /* index covers the whole volume */
        return -EINVAL;
    uint64_t mblock = fs->imap_index[blk];       /* in-memory: one u64 per block */
    if (mblock == 0)
        return -ENOENT;                          /* inode never allocated */

    /* addr is stored in the map block; the block itself lives in the log. */
    struct buf *b = cache_read(&fs->cache, mblock);
    *addr = b->imap[slot];
    cache_release(b);
    return *addr ? 0 : -ENOENT;
}

The in-memory index makes the common case cheap: an inode whose map block is cached costs one hash lookup for the buffer and one array index. The expensive case is a miss on the map block, which requires a disk read before the inode’s address is even known, followed by a second read of the inode, followed by a third read of the data block. Three dependent reads to serve one file offset is the structural cost of the design.

The read path, counted

Consider opening a file and reading its first block, with a cold cache. The directory lookup finds the entry and returns an inode number. The inode map index yields the address of the map block. Reading that block yields the address of the inode. Reading the inode yields the address of the first data block. Reading the data block yields the contents. That is four dependent reads, each of which must complete before the next address is known, so the latencies add rather than overlap.

The comparison is with an in-place filesystem, where the inode’s address is arithmetic, so the sequence is: read the directory block, read the inode, read the data block. Three dependent reads. The log-structured design pays exactly one extra round trip per cold open, and nothing at all per subsequent read of the same file.

The warm case is where the difference disappears, and it is the case that matters. The buffer cache holds recently read blocks, and the inode map index is held in memory permanently. A file that is being read repeatedly never touches the map on disk after the first access, and the inode itself is cached as long as it is referenced. The design’s read performance therefore depends almost entirely on whether the working set of inodes fits in memory, which is why the original paper devotes attention to the fraction of inode accesses served from cache rather than to the cost of a miss.

That dependency has an awkward consequence. A workload that touches a very large number of distinct files, each once, has no reuse to exploit, and pays the extra indirection on every one. Directory traversal over a volume with millions of small files is the pathological case, and the extra round trip is paid once per file rather than once per volume. The map does not merely add a read; it adds a read that cannot be prefetched, because the address of the next thing to read is only known after the previous read completes.

Making the map cache behave

Three techniques reduce the cost of the dependency chain without changing its shape.

The first is to keep the map block resident alongside the inode it describes. When a map block is read, the inodes it points to are likely to be accessed together, since they were allocated together and probably belong to files in the same directory. Co-locating them in the cache turns one map miss into many cheap inode hits.

The second is to write map blocks and their inodes into the same segment. Because a map block is dirtied by the same operation that dirties an inode, the two are appended at nearly the same log position, so reading one brings the other into the same disk read or at least into the same sequential prefetch window. This is a specific instance of the general rule that the log’s ordering should mirror the access pattern, and it is the reason the filesystem maintains multiple open segments: map blocks, inodes, directory data, and file data are separated into streams so that each segment contains objects of similar expected lifetime and similar access pattern.

The third is subtler. If the map index is rewritten whenever any map block moves, and map blocks move constantly, the index rewrite becomes a frequent small write of its own. Batching the index update so that it is written only when the map blocks it describes have been evicted amortizes the cost, at the price of holding dirty index state in memory. The failure mode is that a crash loses the index entries for map blocks that were written but not yet indexed, which is exactly the situation the tail recovery machinery in Checkpoint Regions and Tail Recovery exists to repair by scanning forward from the last checkpoint.

Why not a hash table on disk

A natural alternative is to store the map as a hash table keyed by inode number, with overflow blocks appended as needed. Lookups become a single probe in the common case, and updates touch only one bucket. The difficulty is that a hash table’s buckets must be updated in place to be efficient, which is precisely the operation the log forbids, and a log-structured hash table degenerates into a sequence of bucket images whose live fraction drops as the table churns. Cleaning a hash table under these constraints costs more than cleaning a fixed-size array indexed by number, because the array has no collisions to resolve and each map block covers a contiguous, stable range of keys.

The fixed-range array also makes the index trivially small. A hash table large enough to keep probes short must be sized for the maximum inode count anyway, so it saves no space over the array while adding collision handling. The array’s disadvantage is that a volume with a sparse inode number space wastes map blocks on unallocated ranges, which is a real cost but a predictable one.

The map is the one structure in a log-structured filesystem that is allowed to be a large flat object, and it is allowed precisely because it is small relative to the data it indexes and because its access pattern is one lookup per file operation. Everything else in the design moves; the index of where things moved to stays put, and that fixed point is what makes the whole scheme navigable.