Storing billions of small files (Haystack)

Why file systems struggle with billions of small photos and how Facebook's Haystack solved it: metadata overhead, packing files into large volumes, in-memory indexes, needle lookups in one disk read, deletes and compaction, warm storage with erasure coding, and lessons for photo and attachment storage.

Reading is half of it. See this used in a real interview: walk through Design Instagram →

Photo-sharing services store hundreds of billions of images, most of them small (tens to hundreds of kilobytes), written once, read often when new and rarely afterwards, and almost never modified. Storing each as a file in a traditional file system turns out to be badly inefficient. Facebook's Haystack paper (2010) described the fix, and its ideas are worth knowing for any "design Instagram" or media storage discussion, even though most teams today use object storage that applies similar techniques internally.

Why one file per photo is slow

In a normal file system, reading a file needs several disk operations: look up the directory entry, read the inode (metadata), then read the data. With billions of files, the metadata does not fit in memory, so each photo read costs extra disk seeks. Facebook found that metadata lookups, not data transfer, dominated photo reads, and that most metadata (permissions, timestamps) was never used.

The Haystack idea

Pack many photos into a few huge files and keep a tiny index in memory:

• A physical volume is a large file (around 100 GB) on a storage machine. Photos ("needles") are appended to it, each with a small header (id, size, flags, checksum).
• An in-memory index maps photo id to (volume, offset, size), using only a few bytes per photo, small enough for all photos on a machine to fit in RAM.
• Reading a photo: look up the offset in memory, then one disk read for the data.

Writes are sequential appends, reads are single seeks, and metadata overhead nearly disappears. Logical volumes are replicated across machines in different racks. See storage engines.

The surrounding system

• A directory service maps logical volumes to physical machines and decides which volumes accept writes (writable versus read-only once full).
• Photo URLs encode the volume and photo id, so the CDN or cache can route requests directly to the right machine.
• A cache layer in front absorbs reads of new, popular photos; storage machines mostly serve the long tail that misses CDN and cache. See CDN and edge.

Deletes and compaction

Deleting sets a flag in the needle header and index; the space is not reclaimed immediately. Periodic compaction copies live needles into a new volume and drops deleted ones, like log compaction in LSM trees. For privacy-driven deletion deadlines, compaction must run often enough, or data must be encrypted per object so destroying keys makes it unreadable. See privacy and data deletion and encryption and key management.

Warm storage: f4

Photos are read heavily in their first days and rarely after. Facebook's follow-up system, f4, moved older "warm" volumes from triple replication to erasure coding (Reed-Solomon within a data centre plus XOR across data centres), cutting the storage overhead from about 3.6 times to about 2.1 times while keeping durability. See distributed file systems and erasure coding.

Lessons for your designs

• Pack small objects into larger containers when building custom storage; per-object metadata overhead dominates at scale.
• Keep the index in memory and make reads a single disk operation.
• Append-only writes with asynchronous compaction suit write-once data.
• Tier by age: hot data replicated for read throughput, cold data erasure coded for cost.
• Serve through caches and CDNs; the storage layer handles the long tail.

Most teams get these properties by using cloud object storage, which packs small objects and tiers internally; you then focus on keys, lifecycle rules and CDN caching. See object storage and files and media uploads and processing.

In the interview

For Design Instagram: "Photos and their resized variants are immutable blobs in object storage (or a Haystack-style store packing them into large append-only volumes with an in-memory index, so each read is one disk seek), served through a CDN; metadata lives in the database; old photos move to erasure-coded warm storage; deletes mark and compaction reclaims space." Mentioning why small files are hard is often enough to impress.

Checklist

• Per-file metadata overhead explained as the bottleneck.
• Large append-only volumes with an in-memory id-to-offset index.
• One disk read per photo; replication across racks.
• Directory for volume placement; URLs that route directly.
• Delete flags plus compaction (or per-object keys for deadlines).
• Hot replicated tier, warm erasure-coded tier, CDN in front.