Concepts
Storing many small objects (Haystack)
Intuition
Imagine a library where every loose sheet has its own card in the catalog: the librarian spends more time searching for cards than reading sheets. If the sheets are gathered into a few bound volumes and the catalog keeps only a short note (in which volume and at what position each sheet is), everything fits on his desk and each sheet is found in one go. The idea is to spend the effort reading the content, not searching for it.
How it works
In Facebook's earlier design, each photo was a file in a POSIX file system accessed over NFS; reading a photo required locating the inode before reading the data, and the metadata (such as permissions, which write-once photos do not use) did not all fit in memory. Haystack packs many photos into a few huge files, the physical volumes, and each photo becomes a record called a needle, appended to the end of the file after a superblock. For each volume, the Store machine keeps in memory a map from the photo identifier to the needle's offset and size, so a read consults memory and does at most one disk operation, without walking directories or inodes. The authors estimate about 10 bytes of in-memory metadata per photo (40 bytes for the four resized versions of the same image), versus the 536 bytes of the xfs_inode_t cited in the paper. Because the volume only receives appends, writes are sequential: a delete just marks the needle as deleted and the space is reclaimed in a later compaction, which copies the volume while discarding deleted and duplicate needles; a modified photo is appended again, and the version with the highest offset wins. An index file, an asynchronous checkpoint of the map, avoids scanning the whole volume to rebuild it after a restart. A logical volume groups physical volumes on different machines that are replicas of each other, and the write is sent to all of them. GFS starts from the same principle of keeping metadata small enough to fit in memory, but from the opposite side, with fixed 64 MB chunks, for huge files, so that the master stores little per chunk and the client performs many sequential operations with a single lookup to it.
In practice
This approach suits workloads of small objects written once, read many times, and rarely deleted, such as Facebook's photos, where you give up permissions, overwriting, and directory hierarchy in exchange for throughput and memory efficiency. The cost is points that the paper itself and critiques of the design highlight: deleting requires compaction (deleted photos take up space for a while), failure recovery appears to be largely manual, and the Directory can be a single point of failure if it isn't replicated. The general lesson is that, before scaling with more hardware, it's worth reducing the per-object metadata cost until it fits in memory.
Use it in a design
Practice the cases that rely on this concept in the System Design school.