Facebook Haystack: photo storage

01 · CONTEXT

Photos: written once, read many times

The Haystack paper reports that Facebook stored more than 260 billion images, which amounts to more than 20 petabytes. Each uploaded photo generates four images of different sizes. Users uploaded one billion new photos per week, and the service delivered more than one million images per second at peak.

The workload is data written once, read often, never modified, and rarely deleted. The team built its own storage system because traditional file systems perform poorly under this workload. Photos are accessed most intensively right after upload.

02 · THE PROBLEM

Why the NFS design was not enough

The NFS design stored each photo in its own file on commercial NAS appliances. Reading a photo required several disk operations: translating the name into an inode, reading the inode, and reading the file.

With thousands of files per directory, it was common to exceed ten disk operations to retrieve one image. With hundreds of images per directory, the system still generally incurred three disk operations per image.

1. The web server builds the URL of each image, pointing the browser to a download location.

2. If the CDN has the image cached, it responds right away; otherwise, it uses the URL to fetch the photo from the site's storage systems.

3. The Photo Store server extracts the volume and file path from the URL, reads over NFS, and returns the result to the CDN.

4. Long-tail requests almost always miss in the CDN and reach storage, where disk operations for metadata limited the read rate.

Caching more did not solve it. The file handle cache in memcache brought only a small improvement, because less popular photos are less likely to be in cache. Storage ends up handling the long tail of less popular photos, which are not in the CDN and are likely to miss in the caches; for this reason, focusing only on caching has limited impact on reducing disk operations.

03 · THE IDEA

Less metadata per photo, everything in memory

Haystack drastically reduces the memory used for file system metadata, which makes it practical to keep all of it in main memory. The core technique is simple: it stores many photos in a single file and, therefore, maintains very large files.

In the NAS approach, each file requires at least one inode, which is hundreds of bytes. The team decided to reduce the per-photo metadata so that having enough memory would be much more economical than buying more NAS appliances.

Haystack seeks high throughput and low latency by requiring at most one disk operation per read. Even so, there are corner cases in which the file system requires more than one disk operation, when the data crosses extents or RAID boundaries.

04 · ARCHITECTURE

Directory, Cache, and Store

The architecture has three core components: Store, Directory, and Cache. The Store holds the photos and is the only component that manages file system metadata. The Directory maintains the mapping from logical to physical volumes and other application metadata. The Cache works as the internal CDN and protects the Store from requests for the most popular photos.

1. When visiting a page, the web server uses the Directory to build the URL of each photo.

2. The Directory decides whether the request goes to the CDN or to the Cache, which makes it possible to tune the dependence on CDNs.

3. If the CDN does not find the photo, it removes its own address from the URL and contacts the Cache.

4. On a Cache miss, it removes its own address from the URL and requests the photo from the indicated Store machine.

5. The Store machine looks up the metadata in its in-memory mappings; if the photo was not deleted, it goes to the right offset in the volume file, reads the entire needle, and verifies the cookie and the data integrity.

6. The design's goal is to require at most one disk operation per read.

The Cache only stores a photo if the request comes directly from the user and not from the CDN, among the conditions described. The reason: experience with the NFS design showed that caching behind a CDN is ineffective.

The cookie eliminates attacks that try to guess valid photo URLs.

05 · THE STORE

Volumes, needles, and the in-memory mapping

A physical volume can be thought of as a very large file. A Store machine represents a physical volume as a superblock followed by a sequence of needles, and each needle represents a photo.

Each Store machine maintains an in-memory structure for each of its volumes. The key point of the design is to obtain a photo's file name, offset, and size without disk operations.

Writes are done by appending. The machine synchronously appends the needle images to the volume files and updates the in-memory mappings. Since Haystack does not allow overwriting needles, a photo is only modified by adding an updated needle with the same key and alternate key, and the most recent version of a needle in a physical volume is the one with the highest offset.

On deletion, the machine sets the deleted flag in the in-memory mapping and, synchronously, in the volume file.

06 · INDEX AND FAILURES

Index, compaction, and recovery

Rebuilding the mapping by reading all the volumes is slow, and index files make it possible to build it quickly, shortening the restart. The needle write is synchronous, but the write to the index file is asynchronous.

This shortcut has consequences. Needles without a corresponding index record are called orphans, and on restart the machine examines each orphan in sequence, creates the corresponding index record, and appends it to the index file. Index records do not reflect deleted photos, so the machine may recover a photo that was already deleted; if the needle is marked as deleted, it updates the in-memory mapping and tells the Cache that the object was not found.

Compaction is an online operation that reclaims the space used by deleted and duplicate needles. It copies needles to a new file, skipping duplicates and deleted ones. Over a year, about 25% of photos are deleted.

1. The user first sends the data to a web server.

2. Next, the web server asks the Directory for a write-enabled logical volume.

3. Finally, the server assigns a unique id to the photo and sends it to each physical volume mapped to the logical volume; each machine appends the needle to its volume.

4. A background task, the pitchfork, periodically checks the health of each Store machine.

5. If a Store machine, here B, consistently fails the checks, the pitchfork marks all of its logical volumes as read-only.

When a photo is stored in a logical volume, it is written to all the corresponding physical volumes, and Haystack replicates each photo in geographically distinct locations. If a machine is lost, another takes its place and the data is copied to maintain redundancy. In heavier cases, bulk sync resets a Store machine's data using the volume files provided by a replica. It happens rarely, but results in hours of mean time to recovery.