Distributed file systems & erasure coding

A genome sequencing lab produces about 4 TB of read files a day, each file around 30 GB. Fifty analysis machines align those reads and call variants, and every job reads whole files from start to end. One server can't store a year of this, and it couldn't feed fifty machines at once even if it could.

A distributed file system such as HDFS spreads the files across the disks of many ordinary machines and shows them as one tree of directories. Its design starts from three assumptions: hardware failure is the norm, files are large, and they are written once and read many times. The trade-offs it makes follow from those:

That last row is HDFS's motto: moving computation is cheaper than moving data. A batch job is scheduled on the machines that already hold its blocks, so 4 TB a day is read from local disks instead of crossing the network (Batch processing).

HDFS splits every file into blocks, 128 MB by default, so one 30 GB read file becomes 240 blocks spread over different machines. Two kinds of server share the work:

• The NameNode holds the namespace: directories, file names, permissions, and which blocks make up each file and where they live. It keeps all of it in memory.
• DataNodes, one per machine, store blocks as ordinary files on local disks and serve reads and writes.

The NameNode is critical, so its state is made durable like a database's: every change goes to a transaction log (the EditLog), which is periodically folded into a full snapshot of the namespace (the FsImage). For availability, HDFS runs several NameNodes that share the log through a group of journal servers, with one active at a time (Consensus & leader election).

By default each block is stored three times. Where the copies go matters as much as how many there are. Machines sit in racks that share a switch and power, so a rack can fail as a unit (Redundancy & failure domains). HDFS puts the first copy on the writer's machine, and the second and third on two different machines in another rack:

Failures are found by silence. Every DataNode sends the NameNode a heartbeat, plus a periodic report of the blocks it holds. A DataNode that stays quiet for over 10 minutes by default is declared dead. The wait is deliberately long, so that a node flapping on and off doesn't set off a storm of copying (Failure detection & split brain).

Once a node is declared dead, every block that had a copy on it is under-replicated, and the NameNode orders new copies from the survivors. Corruption is caught separately: the client checksums each block when writing it, verifies the checksum on every read, and reads another replica when one doesn't match.

Three copies cost 200% extra: a year of the lab's data, 1.46 PB, takes 4.38 PB of disk. Erasure coding stores computed redundancy instead of copies. The data is cut into k data cells, and m parity cells are computed from them with a Reed-Solomon code. Any k of the k + m cells are enough to rebuild the rest, so any m can be lost.

HDFS's default policy is RS(6,3): six data cells and three parity cells, on nine different DataNodes. Six blocks of data take 9 blocks of disk instead of 18, and any three of the nine can fail. The extra space is m / k:

In Ceph, a 4+2 or 6+3 profile gives about double the usable space of three copies. Past four or so data chunks the savings flatten while the performance cost keeps growing.

With copies, rebuilding a lost block means reading one surviving copy. With RS(6,3) it means reading six blocks from six machines, decoding them, and writing the result. A disk holding millions of blocks multiplies that into a lot of network traffic and CPU. Erasure coding is not a free lunch, especially during recovery.

Reads change too. A missing or slow cell is rebuilt on the fly from other cells, so a read waits on the slowest of several machines. Azure Storage even starts a reconstruction in parallel when a fragment's machine looks slow, and returns whichever answer comes first. HDFS lists further costs:

• Encoding and decoding take CPU on clients and DataNodes.
• Cells are spread across racks, so most reads and writes cross racks.
• RS(6,3) needs at least 9 DataNodes, and at least 3 racks, ideally 9, for rack failures.
• Erasure-coded files don't support append, truncate or flushing a partly written file.

The two schemes suit different stages of a file's life. Replication is cheap to write and repair, and erasure coding is cheap to keep. Azure Storage combines them: data is appended to extents kept as three full copies, and once an extent reaches about 1 GB it is sealed, erasure-coded in the background, and the copies are deleted:

In HDFS the policy is set per directory and applies to new files; changing a file's policy means copying it, not renaming it. The lab keeps /runs/current, where sequencers are still writing, on three copies, and moves finished runs into /archive, which uses RS(6,3) and is read mostly by occasional reanalysis. Google's Colossus does a similar thing with hardware: new data is spread across all drives, then moved to larger drives as it cools (Data lifecycle: tiering, TTL & compression).

Because the NameNode keeps every file and block in memory, the number of files, not the bytes, is what fills it. HDFS aims at tens of millions of files per instance. Each sequencing run also produces thousands of tiny quality-control files, a few kilobytes each. Each one takes a file entry and a block entry in the NameNode's memory, just as a full 128 MB block does, while holding almost nothing. The lab packs them into one archive per run.

Beyond one NameNode there are two routes. HDFS federation runs several independent NameNodes, each owning part of the namespace, over the same DataNodes. Google's Colossus, the successor to GFS, stores file metadata in Bigtable instead of one server's memory, which lets it scale over 100 times past the largest GFS clusters.