Papers
f4: Facebook's Warm BLOB Storage System
Subramanian Muralidhar, Wyatt Lloyd, Sabyasachi Roy, Cory Hill, Ernest Lin, Weiwen Liu, Satadru Pan, Shiva Shankar, Viswanath Sivakumar, Linpeng Tang, Sanjeev Kumar · 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2014, 2014
The problem: data that cools down keeps paying the price of hot data
Facebook stores photos, videos, and other BLOBs (binary large objects, written once and almost never modified). The previous system for this, Haystack, was designed to serve recent, heavily accessed content. It keeps three replicas (two on different racks in the main datacenter and a third in another datacenter), with RAID-6 on each machine. The effective cost is a replication factor of 3.6 (three copies times 1.2 for RAID-6). The authors studied the access patterns and concluded that usage depends strongly on age: new BLOBs are read much more often, and the request rate drops sharply as content ages. The deletion rate also drops with age. The result is that most stored objects are warm: in the medians per calendar window, more than 80% of the objects were warm in all six types analyzed in the oldest window and more than 89% in the most recent one, meaning the warm fraction is growing. This data has few reads per terabyte, yet it still occupies the high number of replicas designed for the hot workload. That wastes disk: the bottleneck of warm data is not throughput, it is capacity. The paper proposes separating the two regimes. Haystack keeps serving hot content, and a new system, f4, takes over the warm BLOBs at a lower storage cost, accepting lower throughput per terabyte. The analysis indicates one month as the safe boundary between hot and warm for most types and three months for Photos; Profile Photos does not migrate to f4. In production at the time, for simplicity, a cutoff of about three months was used for all types.
The central idea: replacing full replicas with erasure coding
The idea behind f4 is to replace full copies with erasure coding while maintaining fault tolerance. Inside a cell (f4's building block, in a single datacenter), data is split into stripes with 10 data blocks and 4 parity blocks, using Reed-Solomon (10,4). Any 4 blocks of a stripe can be lost and the content is still reconstructed. The cost is 1.4 times the size of the data, well below Haystack's 3.6. The blocks used in the encoding are about 1 GB. The cells of the time (2014) used 14 racks of 15 machines, each with 30 disks of 4 TB, and the blocks of a stripe are spread across different racks, so that disk, machine, and rack failures within the datacenter are tolerated. This design stays simple because f4 only stores locked volumes, which accept only reads and deletes: there are no appends or overwrites, so the design does without a journal and compaction, since deletion is done by key. Each BLOB has its own encryption key, and logical deletion consists of destroying that key, instead of rewriting the stripe. The gain comes from exploiting three workload properties at the same time: read-only data, low read rate, and a preference for capacity.
Cell architecture: storage nodes and diskless nodes
Each f4 cell separates storage from compute. The storage nodes keep the blocks on disk and serve reads. Among the cell's components (storage, name, backoff, rebuilder and coordinator nodes), three sit on machines with no storage of their own and plenty of CPU; the name node, in primary-backup, holds the mapping between blocks and nodes. The backoff nodes come in when the data block containing the requested BLOB is unavailable: they reconstruct the requested BLOB on demand, reading pieces of the other blocks in the stripe, instead of rebuilding the whole block. The rebuilder nodes detect failures by probing and rebuild entire blocks in the background, at a limited rate so as not to hurt user requests. The coordinator nodes schedule the rebuilds and run a placement balancer, which fixes cases where blocks of the same stripe end up in the same failure domain, such as the same rack. This split keeps the normal read path simple, and the extra decoding cost only shows up on failure. Rebuilding is a heavy process, which imposes significant I/O and network load on the storage nodes; for that reason rebuilds are limited and carefully scheduled. The paper reports that f4 reads have slightly higher latency than Haystack's (for reads within the same region, the median is 17 ms versus 14 ms), which the authors consider sufficient for a good user experience.
Datacenter fault tolerance: from a factor of 2.8 to 2.1 with XOR
Reed-Solomon (10,4) protects against failures within a datacenter, but not against the loss of the entire datacenter. f4's first solution was to keep a second full copy of the cell in another geographic region, which doubles the cost: 1.4 times 2 results in an effective factor of 2.8. The next step was to use XOR across regions. Each volume, stripe and block is paired with a partner (buddy) in another region, and the XOR of the two is written to a third region. If any one of the three regions is lost, its content can be recovered from the other two: a lost block is obtained by combining its buddy with the XOR. For each pair of volumes there are three encoded cells (the two volumes and their XOR), that is, 3 cells for 2 logical volumes, which gives 1.5 times across regions. Combined with 1.4, the calculation is (1.4·2 + 1.4)/2 = 2.1. The paper's abstract summarizes the result by saying that f4 reduces the factor from 3.6 to 2.8 or 2.1, depending on the scheme, tolerating disk, machine, rack and datacenter failures. The trade-off is in the cost of reading under failure: if the datacenter that holds the BLOB fails, the read combines the XOR block with the buddy from another region, with lower throughput for that datacenter's BLOBs.
Results, limits and design lessons
The paper reports that f4 stored more than 65 PB of logical BLOBs and saved more than 53 PB with the partial deployment of the 2.1 scheme (more than 39 PB at 2.8; more than 87 PB projected with full 2.1). The authors also report a failure episode: a bad batch of disks, combined with high temperatures in one region, raised the annual failure rate from about 1% to more than 60% for a few weeks, with no data loss, because the buddy and XOR blocks were in other cells, which were not affected. In the lessons section, the paper highlights three. First, simplicity favors operational stability: an early version used a deletion journal file like Haystack's, which clashed with the rest of the read-only design, and removing it helped. Second, it is worth measuring the underlying software for your use case, in this case the read path of the distributed file system. Third, hardware heterogeneity reduces the chance of correlated failures, like the one in the episode above; the authors plan to use it. In addition, f4 complements Haystack by handling only what has gone cold, and hardware and software were co-designed, so that the software guarantees that the weekly peak load on each disk stays below the maximum IOPS it delivers. Erasure coding trades lower storage cost for longer reconstruction and recovery times under failure and lower maximum read throughput. The reader can treat f4 as a case study in separating layers by access pattern.
See the ideas at work
Practice the designs that use this paper in the System Design school.