Papers
Finding a Needle in Haystack: Facebook's Photo Storage
Doug Beaver, Sanjeev Kumar, Harry C. Li, Jason Sobel, Peter Vajgel · 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2010, 2010
The problem: one file per photo makes the disk spend operations on metadata
Facebook needed to store and serve an enormous number of photos: the paper's research page cites more than 260 billion images (over 20 petabytes), about one billion new uploads per week and peaks above one million images served per second. The previous design kept photos on storage appliances accessed over NFS, essentially one file per photo on a POSIX file system. The problem, according to the authors, is that this model wastes disk operations on metadata. To read a file, the system must first locate its inode and only then read the data, so a single photo read can cost more than one disk access. In addition, the file system maintains metadata such as permissions, which a photo application that writes once and never modifies simply does not use, and each inode takes up hundreds of bytes that do not all fit in memory. The motivation for Haystack is to reduce the per-photo metadata to the point where it fits in main memory, leaving the disk to read the photo's bytes rather than to look for it.
The core idea: packing millions of photos into large files with an in-memory index
Instead of one file per photo, Haystack groups many photos inside a few huge files, called physical volumes. Each storage machine (the Store) manages several of these volumes; one cited example is a 10 TB server divided into 100 volumes of 100 GB. Inside a volume, each photo is a record called a needle, appended to the end of the file, after an initial superblock. For each volume, the machine keeps in memory a map that translates the photo identifier to the offset and size of the needle in the file. So a read consults memory, finds where the photo is and does a single disk read at that spot, 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 xfs_inode_t that the paper itself cites. This change allows at most one disk operation per read, and the paper reports about four times more reads per second than the previous NAS system. Since the data is immutable and only appended, writing is sequential and simple.
Architecture: Directory, Cache and Store, and the read and write paths
The system has three components. The Haystack Store is the persistent layer, with the volumes described above. The Haystack Directory maintains the mapping from logical volumes to physical volumes, spreads writes across the logical volumes and reads across the physical ones, decides whether a request goes to the CDN or to the Cache, and marks volumes as read-only when they fill up or for operational reasons. The Haystack Cache works as a distributed hash table indexed by photo ID: on a miss, it fetches from the Store. A logical volume groups physical volumes from different machines, which are replicas of each other. On a read, the web server queries the Directory and builds a URL that carries the CDN, Cache, machine, and volume information; the request passes through the CDN (which can be skipped), through the Cache and, if necessary, reaches the Store, which checks the cookie (a random number embedded in the URL and written to the needle, which prevents guessing URLs) before returning the data. On a write, the web server asks the Directory for a write-enabled logical volume and sends the photo to all the physical volumes of that logical volume, each appending the needle to its file. According to the paper, the Cache only stores photos requested directly by the user and coming from write-enabled machines, protecting them from reads, since file systems handle simultaneous reads and writes poorly.
Deletion, update, compaction, and fault tolerance
Because volume files are append-only, Haystack handles changes indirectly. A delete just marks the needle as deleted, both in the in-memory map and in the volume file; the space is only reclaimed later by a compaction process, which copies the volume to a new file, discarding deleted and duplicate needles. Needles are never overwritten: a modified photo (for example, rotated) is appended again with the same keys, and the version with the highest offset in the same volume is the most recent. To avoid rebuilding the in-memory map by scanning the whole volume after a restart, each volume has an index file, which is a checkpoint of the map. It is updated asynchronously and can be stale, but the needles not yet indexed are at the end of the file and are easy to locate. Because the hardware is commodity and fails often (disks, RAID controllers, motherboards), a background task called pitchfork periodically checks the health of the Store machines; if one has a problem, all of its logical volumes are marked read-only, and the cause is investigated manually. A bulk sync mechanism restores the data of a failed machine from a replica. Photos are also replicated across geographically distinct datacenters.
Trade-offs, limits, and legacy
Haystack is a clear example of specializing storage for a workload: it gives up the generality of a file system (permissions, overwrites, directory hierarchy) to gain throughput and memory efficiency on data that is written once, read many times, and rarely deleted. This gain has a cost. Common criticisms of the design point out that failure recovery seems largely manual, that the design is tuned very tightly to a specific workload, that deleting requires compaction (so deleted photos take up space for a while), and that the Directory can be a single point of failure if it is not replicated. The idea of packing small objects into large files, with a compact in-memory index and append-only writes, shows up in other object storage systems, but this summary does not confirm a specific list of derived systems, so the reader should treat Haystack mainly as a case study: before scaling with hardware, it is worth reducing the per-object metadata cost.
See the ideas at work
Practice the designs that use this paper in the System Design school.