From a path to an inode

If most of your storage has been S3, you probably picture a file as a key and some bytes. You PUT the whole thing, you GET it back, and the key is its full path. A POSIX file system works differently. It finds a file one name at a time, changes it a few bytes at a time, and renames it without touching its contents. Those differences decide which programs still work when a file system is built on top of a bucket.

In 1974, Dennis Ritchie and Ken Thompson described the Unix file system in a paper that still reads as a description of Linux. One sentence in it is the subject of this page: “The purpose of an open or create system call is to turn the path name given by the user into an i-number by searching the explicitly or implicitly named directories.”Ritchie and Thompson, “The UNIX Time-Sharing System”, Communications of the ACM 17(7), July 1974, section 4. An i-number is what this page calls an inode number. The following sections build that sentence up from a bare disk, one idea at a time, and then hold an object store up against it.

Blocks and inodes§

A disk offers a small interface: read block n, and write block n. The blocks have a fixed size, often 4 KiB, and the disk knows nothing about files, names, or lengths. A file system’s first job is bookkeeping: which blocks belong to which file, how long the file is, and who may read it.

Unix keeps that bookkeeping in an inode, one per file, found by its number. The 1974 paper lists what an inode holds: the file’s owner, its protection bits, the disk addresses of its contents, its size, its time of last modification, its number of links, and whether it’s a directory. Linux’s inode(7) manual page lists the same fields today, with a few more timestamps. When you run stat on a file, you’re reading its inode, and ls -i prints its number.

One thing is missing from that list: the file’s name.

Directories: tables of names§

A directory is a file whose contents are a table. Each entry holds a name and an inode number, and nothing else. The paper says so directly: “a file does not exist within a particular directory; the directory entry for a file consists merely of its name and a pointer to the information actually describing the file.” By convention, every directory also holds two entries of its own: ., which points to the directory itself, and .., which points to its parent.

Two consequences follow, and the rest of this page leans on both. First, a file doesn’t know its path. Inode 87 in the following figure has no record that it’s called app.ts, or that it sits in src/. Second, renaming a file, or giving it a second name, changes only directory tables. The inode and the file’s bytes stay where they are.

Path lookup, one name at a time§

A path is a set of directions, not an address. To resolve /home/agent/repo/src/app.ts, the kernel starts at the process’s root directory and looks up home in its table. It checks that the result is a directory and that the process has search permission on it, then looks up agent there, and so on to the last name. A path without a leading / starts from the process’s working directory instead.The rules in this section are from path_resolution(7).

A symbolic link changes the route partway. Its contents are another path, and the kernel resolves that path starting from the directory that holds the link. Linux follows at most 40 symbolic links while resolving one path, and fails with ELOOP after that.

Each step can fail, and each failure has its own error. A directory without search permission gives EACCES, a missing name gives ENOENT, and a regular file where a directory should be gives ENOTDIR. Step through a few paths in the following explorable, both as the user who owns the files and as one who doesn’t.

A path with five names costs five lookups. Linux remembers recent results in the dentry cache, or dcache, which “caches information about names in each filesystem to make them quickly available for lookup”. For a local file system such as ext3, XFS, or Btrfs, the kernel’s documentation says the dcache is always accurate, though not always complete. A file system shared across a network can’t make that promise, because another machine can change a directory at any time.From the kernel’s Pathname lookup documentation. So an NFS client sends the server a LOOKUP for each name it can’t trust from its cache, and a FUSE file system receives each such lookup as a request to its daemon. Where those requests go, and how long each takes, accounts for much of the speed difference between network file systems. For more information about what each request costs, see Anatomy of a file create over a network.

Descriptors and open file descriptions§

When the walk ends, open() has an inode, but it doesn’t hand the inode back. In the words of the open(2) manual page, “A call to open() creates a new open file description, an entry in the system-wide table of open files. The open file description records the file offset and the file status flags.” The process gets back a file descriptor, a small integer that refers to that description.

So there are three layers. The descriptor belongs to one process. The open file description holds the offset and flags such as O_APPEND. The inode is the file. The middle layer explains two behaviors that surprise people. A child created by fork() inherits its parent’s descriptors, and they refer to the same descriptions, so parent and child share one offset. And every open() makes a new description, so two opens of the same file keep separate offsets.

The descriptor also outlives the name. It “is unaffected if path is subsequently removed or modified to refer to a different file.” From here on, the path no longer matters. Reads and writes name a descriptor, never a path.

Reads and writes at byte offsets§

read(fd, buf, n) reads up to n bytes from the description’s offset and moves the offset forward. pread() and pwrite() take an explicit offset instead. A write in the middle of a file replaces exactly the bytes it covers, and a write past the end makes the file longer. The 1974 paper already said, “There is no distinction between ‘random’ and sequential I/O.”

O_APPEND adds one guarantee. Before each write, the kernel moves the offset to the end of the file, and “The adjustment of the file offset and the write operation are performed as an atomic step.”From write(2), which is also the source of the two quotations that follow. Two processes that append to one log don’t overwrite each other’s lines.

A write lands in the page cache, the kernel’s in-memory copy of the file’s blocks, and reaches the disk later. A successful write() “does not make any guarantee that data has been committed to disk.” Only fsync() asks for that. For more information about what it promises, see Where fsync returns from.

What POSIX does promise readers is narrow: “a read(2) that can be proved to occur after a write() has returned will return the new data.” It promises nothing about a sequence of reads. A program that reads a large file in pieces can see some pieces from before a write and some from after.

This is the gap between a whole-file API and POSIX. GetObject returns one version of an object. A readFile() built on POSIX makes several read() calls, and nothing ties them to one version. Writes have the mirror-image problem: a program that crashes halfway through leaves half its writes behind. The standard way to replace a file all at once is to write a new file and rename it over the old one.

Rename: one entry, one step§

The rename(2) manual page makes the promise that git’s lock files rely on: “If newpath already exists, it will be atomically replaced, so that there is no point at which another process attempting to access newpath will find it missing.” In terms of the earlier figures, a rename removes one entry from a directory table and adds one, and every other process sees the swap as a single step. The page is candid about one detail: there may be a window in which both the old name and the new name refer to the file.

Renaming a directory is the same operation. Renaming build to dist changes one entry in the parent directory and, if the directory moves to a new parent, its own .. entry. The 10,000 files inside don’t move, because none of them records its path.

A rename between two directories is the hardest call on this page to get right. Moving a directory into one of its own descendants would cut a loop out of the tree, so the kernel must check ancestry while nothing else rearranges it. Linux handles this with one lock per file system, s_vfs_rename_mutex, which every cross-directory rename takes. Its documentation notes that “the only operation that could introduce loops is cross-directory rename.”From the kernel’s Directory Locking documentation. On one machine, that lock is a mutex. Across machines, something must play its part, and NFS gives the job to the server: its RENAME is one request, and the protocol says it “must be atomic to the client.”From RFC 1813, the NFS version 3 specification, section 3.3.14.

An object store has no rename at all, so a client that wants one must copy each object to its new key and delete the old one. The following explorable runs mv build dist both ways and lets you choose when a second machine looks.

Links, and the last close§

A hard link is a second directory entry that holds the same inode number. The 1974 paper describes the whole operation: making a link “involves creating a directory entry with the new name, copying the i-number from the original file entry, and incrementing the link-count field of the i-node.” Neither name is the original, and both are equal. A hard link can’t cross file systems, because an inode number means something only within its own file system, and it can’t point to a directory.See link(2) and inode(7).

A symbolic link is a different thing: a small file whose contents are a path. The symlink(7) manual page calls it “a pointer to another name, and not to an underlying object.” A symlink can cross file systems and point to directories. It also breaks when its target name goes away, even if the file lives on under another name.

Removing a file is unlink(). It deletes one name and decrements the inode’s link count, and the data goes when the count reaches zero, with one exception. The unlink(2) manual page puts it this way: “If the name was the last link to a file but any processes still have the file open, the file will remain in existence until the last file descriptor referring to it is closed.”

That exception is hard for a network file system. The NFS version 3 specification says of it, “It is impossible for a stateless server to implement these semantics.” The workaround it suggests is the one NFS clients use: on remove, the client renames the file to a hidden name, and it deletes the file on the last close.From RFC 1813, section 4.2.

Permission bits§

An inode’s mode holds three groups of three bits, for the owner, the group, and everyone else. The kernel uses the first group if you own the file, the second if you belong to its group, and the third otherwise. In each group, the bits grant read, write, and execute.

On a directory, the meanings shift to fit a table of names. Execute means search: permission to look a name up in the directory, which is the check that the path explorable failed as guest. Write permission on a directory is what lets a process add and remove its names, so unlink() fails with EACCES without it, whatever the mode of the file being removed.See chmod(2) and unlink(2). The sticky bit on a world-writable directory such as /tmp narrows that again: a file in it can be renamed or deleted only by its owner, the directory’s owner, or a privileged process.

Git keeps only one of these bits: its index records each regular file as mode 0755 or 0644, and nothing finer.From git’s index format. That one bit is still what decides whether ./build.sh runs.

An object store’s model§

S3 has no inodes, no directories, and no descriptors. AWS’s documentation says that general purpose buckets “have a flat structure instead of a hierarchy like you would see in a file system.” A key is a string that may contain slashes, and an object is a complete set of bytes stored under one key.From Organizing objects in the Amazon S3 console by using folders.

The interface is small:

• PutObject stores a whole object, replacing any object under that key.
• GetObject reads an object, whole or as a byte range.
• ListObjectsV2 returns keys in lexicographic order, up to 1,000 per request, optionally only those that start with a prefix.
• CopyObject copies an object, atomically for objects up to 5 GB, and DeleteObject removes one.

An object’s user-defined metadata can’t change in place either. The documentation says that “The only way to modify this metadata is to make a copy of the object and set the metadata.”From Working with object metadata and Copying, moving, and renaming objects. What S3 does guarantee is strong consistency. Since December 2020, a read after a successful write returns the new object, and list operations are strongly consistent too.From AWS’s announcement, Amazon S3 now delivers strong read-after-write consistency.

Directories are something a client infers from a listing. Called with the delimiter /, ListObjectsV2 groups keys that share a prefix into CommonPrefixes, which, in the API reference’s words, “act like subdirectories in the directory specified by Prefix.”From the ListObjectsV2 API reference. A FUSE client draws its tree from those prefixes. An empty directory has no keys to imply it, so the S3 console makes one by storing a 0-byte object whose key ends in a slash.

Where the mapping breaks§

The following table maps each POSIX call onto the nearest request that an S3 general purpose bucket offers. Where a client’s workaround is worth knowing, it names Mountpoint for Amazon S3, AWS’s open-source client.Mountpoint’s behavior is from its semantics documentation: it sets one mode and owner for every file at mount time, with --file-mode, --dir-mode, --uid, and --gid, and it supports neither hard nor symbolic links.

Four of those rows need a closer look here. A file system on an object store follows each of them further, with the requests they send and what they cost.

No rename

A client that offers rename over a bucket copies each key and deletes the old one. Each CopyObject is atomic for its own object, so every file arrives whole, but nothing makes the set atomic, which is the race in the rename explorable. AWS’s own console instructions show the same gap from the other side. They warn that when you delete a folder, you should wait for the delete to finish before adding objects to it, or “new objects might be deleted as well.”From Organizing objects in the Amazon S3 console by using folders. S3 Express One Zone, a storage class in directory buckets, can rename single objects atomically, and Mountpoint uses that where it’s available.

Whole-object writes

A write at an offset changes only the bytes it covers. On a bucket, the same change means a new object. Changing 4 KiB of a 1 GiB file writes 1 GiB, which is 262,144 times the change. A client can copy the unchanged ranges on the server side, as s3fs does with multipart copy, but it still produces a whole new object.From the s3fs README: “random writes or appends to files require rewriting the entire object, optimized with multi-part upload copy”. Appending a line to a log has the same cost, because general purpose buckets can’t append.

Listing is a scan

Reading a directory on a file system reads one table. On a bucket, it’s one ListObjectsV2 request per page, and each request needs the continuation token from the one before, so the pages come one at a time. A directory of 100,000 files takes 100 requests in a row, every time a client lists it without a cache.

Directories by implication

A directory on a bucket is an agreement among the keys that share its prefix. It has no object of its own, unless a client stores a marker, so it has nowhere to keep a mode, an owner, or a modification time. It appears when its first key is written and disappears when its last key is deleted, as in the earlier figure.

Who keeps the inodes§

Every design that offers the calls on this page keeps an inode table somewhere, and much of its behavior follows from where:

• A local disk or a network block volume keeps it on the block device, and the file system in your own kernel reads and changes it.
• NFS keeps it on the server. The client sends requests named for the calls in this page, such as LOOKUP, RENAME, LINK, and SYMLINK, and the server’s file system carries them out.The procedures are listed in RFC 1813, section 3.3.
• A metadata-database design, such as JuiceFS, keeps it in a database such as Redis or PostgreSQL, and stores file contents in the bucket as numbered blocks rather than as files at their paths.From JuiceFS’s architecture documentation, which says that “you cannot find the original file directly in the object storage.”
• A FUSE client over a bucket keeps it nowhere. It infers names from keys each time it lists, which is why its rename is a copy, and its links, where it has them, are a convention of its own.

A worked example: Archil§

Archil keeps its inodes and directory tables on its own servers, and a mounted client resolves paths and changes names against them. For a disk synced to your own bucket, the bucket holds a projection of that tree: each file’s contents as an ordinary object at its path.

What the bucket can’t express stays in Archil. Mode bits, ownership, and extended attributes are visible to mounted clients but not to a program that reads the bucket. A symbolic link becomes a small text file that holds its target, and a hard link becomes a full copy. A directory rename is atomic for every mounted client, but a program that reads the bucket directly can see it partly done while the change syncs.See Data sources. Disks that Archil manages store data in our own format instead, and you read them through a mount or the disk’s S3 API.

For what these limits mean for agents that run git and package managers on shared storage, see Storage for agents.