storage-array

How it is built

Architecture overview

An erasure-coded storage array keeps data safe across disk, node and rack failures for a fraction of the cost of copies. Each object or block is cut into k data shards, m parity shards are computed from them, and the k + m shards are written to different failure domains (disks, servers, racks). Any k surviving shards rebuild the rest, so a 17 + 3 layout survives three losses at about 1.18× raw space, where triple replication costs 3×. The one idea that makes it work is that every shard is individually verifiable (a checksum per shard) and individually replaceable: a read that finds a bad shard treats it like a lost one, and repair is the same code path as the degraded read. The price is paid on repair, which reads many shards to rebuild one, so most of the design (local parities, declustered layout, throttled rebuild) exists to make repair cheap and to keep it out of the way of foreground traffic. Backblaze Vaults and NetApp arrays are two production forms of this design: Backblaze spreads shards over servers in software, NetApp spreads parity over disks in a RAID group under a copy-on-write filesystem.

Parts:

• Erasure coder — turns k data shards into m parity shards and back — Reed-Solomon codes, erasure-coding (no page yet), finite-field-arithmetic (no page yet), made fast with SIMD programming
• Local repair — extra parities over small groups so a single loss is repaired from a few shards — local-reconstruction-codes (no page yet)
• Layout — which shard lives on which disk; spreads the rebuild load over all disks — declustered-raid (no page yet), Rendezvous hashing, Consistent hashing
• Integrity — a checksum per shard, checked on every read and by the scrubber — CRC32C checksums
• Membership — decides which disks and nodes are dead and starts repair — Phi accrual failure detector, SWIM gossip membership
• Metadata and write path — maps objects to shard sets and makes writes atomic and durable — copy-on-write-b-tree (no page yet), B+ tree, Write-ahead log, fsync, O_DSYNC and O_DIRECT
• Space efficiency — fewer bytes to code and store — content-defined-chunking (no page yet), LZ4, Content-addressed storage
• Repair governor — keeps rebuild traffic from starving clients — Token bucket

 client ─ put/get ─► gateway ──► placement (rendezvous / declustered map) ──► shard set {d1..dk, p1..pm}
                       │                                                         │
                       │ chunk, compress (LZ4), split k                          ▼
                       ▼                                              ┌─ node A: disk ─ [shard+crc]
              erasure coder (GF(2^8), SIMD) ── k data + m parity ───► ├─ node B: disk ─ [shard+crc]
                       ▲                                              └─ node N: disk ─ [shard+crc]
                       │ degraded read / repair                              │ heartbeats
   metadata (CoW B-tree, WAL) ◄── commit after k+m acks     failure detector ◄┘
                       ▲                                              │ dead disk
                       └──── repair queue ◄── scrubber ◄──────────────┘  (token-bucket paced)

How the parts fit together

Erasure coder

Reed-Solomon codes are the default code: a maximum-distance-separable code where any k of k + m shards recover the data, with arithmetic over a Galois field, usually GF(2^8) so one symbol is one byte (finite-field-arithmetic, no page yet). Encoding is a matrix-vector product over that field; decoding with erasures inverts a k × k submatrix, which is cheap because the positions of the missing shards are known (a checksum has already said which). The contract with the layer above: k equal-size data shards in, m equal-size parity shards out, shard size a multiple of the disk block.

The throughput of a coder depends almost entirely on how it multiplies bytes in the field. Plank, Greenan and Miller show that table lookups with byte-shuffle instructions multiply many bytes per instruction, which is why a production coder is a SIMD kernel with runtime dispatch (AVX2 or NEON), not a scalar loop. Backblaze reports 149 MB/s on one core of an Intel Xeon E5-1620 v2 for their 17 + 3 configuration, on a Java library (source: Backblaze, "Reed-Solomon" blog post); a SIMD library such as Intel ISA-L is faster by construction.

Local repair

Plain Reed-Solomon has one weakness: rebuilding one lost shard reads k shards. The Windows Azure Storage paper (Huang et al.) shows the alternative, Local Reconstruction Codes: split the data shards into groups and add one local parity per group on top of a few global parities. A single failure, the common case, is repaired from the group (k/l shards), and the code still tolerates r + 1 arbitrary failures. Their LRC (12, 2, 2) stores 12 data, 2 local and 2 global parities, 16 fragments, at 1.33× overhead, where a Reed-Solomon code of the same repair cost would need 1.5×. local-reconstruction-codes (no page yet) is the block for this; the choice between plain Reed-Solomon and LRC is a trade of storage overhead against repair bandwidth. Ceph exposes the same idea as an LRC plugin in its erasure-code profiles.

Layout

The layout decides which disk gets which shard, and it decides rebuild speed. In a classic RAID group of n disks the rebuild reads from the n − 1 survivors and writes to one spare, so the spare's write bandwidth caps the rebuild. Declustered RAID (declustered-raid, no page yet; origin: Holland and Gibson, ASPLOS 1992) spreads the stripes of many small groups over all disks in a pool, so after a failure every surviving disk reads and writes a small share of the repair. OpenZFS dRAID states this directly: internal raidz groups distributed over all children, with precomputed permutation maps so rebuild I/O spreads evenly, plus distributed hot spares. The trade it documents is a fixed stripe width, which wastes space on small blocks.

At cluster scale the same job is done by a placement function. Rendezvous hashing scores each node with hash(shard-set id, node) and picks the top k + m distinct failure domains: no ring state, exact weights, minimal movement when a node joins or leaves, O(nodes) per lookup. Consistent hashing is the alternative with O(log n) lookup and a ring to maintain. Ceph's CRUSH (Weil et al.) is a third form, a hierarchical, rule-driven pseudo-random placement that knows about racks and rows. Either way, the contract is that any gateway computes the same shard locations from the object id and the cluster map, so the data path needs no central lookup.

Integrity

Every shard carries a checksum, CRC32C, computed on the way in and verified on every read, and by the background scrubber. CRC32C is the right class of check here: one hardware instruction per 8 bytes on x86 (SSE4.2) and ARMv8, strong against the bit-rot and torn-write patterns of disks, not against adversaries. Backblaze describes the contract: if a shard fails its checksum or cannot be read, it is recomputed from the other shards and rewritten. This is why erasure coding below the filesystem tolerates silent corruption that plain RAID cannot even detect.

Membership

Repair starts when a node or disk is declared dead. A fixed timeout is wrong in both directions (false positives during a load spike trigger a repair storm, slow detection leaves data under-protected). The Phi accrual failure detector outputs a suspicion level from the observed heartbeat distribution, so a threshold means the same on a quiet and a noisy network; SWIM gossip spreads the verdict at constant cost per node. A sensible policy waits before repairing a "suspect" node (reboots are far more common than deaths) and repairs at once only when a stripe is close to k survivors.

Metadata and write path

The data path is simple; the metadata is not. The metadata store maps object ids to shard sets and versions. NetApp's WAFL (Hitz, Lau and Malcolm) is the classic copy-on-write design: new blocks are written to free space and the tree root is updated last, so a snapshot is a retained root and a crash leaves the previous consistent tree. copy-on-write-b-tree (no page yet) is that block; B+ tree is the structure it modifies, and a Write-ahead log is the alternative way to make updates atomic. Shard files themselves are written with fsync, O_DSYNC and O_DIRECT semantics: a shard is acknowledged only after it is durable, and the object is committed when enough shards are acknowledged. On flash, SSD and NVMe internals sets the minimum useful shard size (write amplification, erase-block size).

Space efficiency

Compression before coding (for example LZ4, which decompresses at several GB/s per core) reduces both disk and coder work; compress first, because encrypted or coded data does not compress. Deduplication needs chunk boundaries that survive insertions: content-defined-chunking (no page yet) cuts the stream where a rolling hash matches a pattern, and Content-addressed storage keys the chunks by their hash. A deduplicated chunk is shared by many objects, so protect it at the highest level of any referrer.

Repair governor

Rebuild is a flood of reads and writes at exactly the time the array is weakest. A Token bucket per disk or per node, refilled at a configured repair rate, bounds the bandwidth repair may take; foreground I/O has its own priority. Prioritise stripes by margin: a stripe that has lost m − 1 shards is repaired before a stripe that has lost one.

Data and control flow

Write one object (Vault-style):

1. The gateway compresses and, if enabled, chunks the object; it picks the shard set with the placement function.
2. The coder splits the data into k shards and computes m parity shards (order of hundreds of MB/s per core).
3. Each shard is sent with its CRC32C to its node; the node appends it to a file and makes it durable.
4. The gateway waits for the required number of acknowledgements, then commits the object record in metadata.
5. Slow or failed nodes get the missing shard queued for repair; the client is not told.

Read, degraded or not:

1. Look up the shard set, ask the k data shards (or any k if some node is known slow).
2. Verify each checksum. A bad or missing shard triggers a read of enough extra shards to decode.
3. Return the data; write the recomputed shard back to its node (read repair).

Disk failure:

1. The detector crosses the threshold for a disk; the repair planner lists the affected stripes.
2. Stripes are sorted by remaining margin and fed to workers, paced by the token bucket.
3. Each worker reads k shards (or a local group with LRC), decodes the lost shard, writes it to a new disk chosen by placement, checksums it, and updates metadata.
4. The scrubber then re-reads cold data on a schedule, so a second silent failure never accumulates.

Scaling

1. Coder CPU: the first limit on the write path. Lever: SIMD kernels, one stripe per core, larger shards to amortise setup.
2. Repair bandwidth: reconstructing one shard reads k. Levers in order: declustered layout (spread over all disks), LRC (read k/l not k), throttling so clients win.
3. Metadata: a single metadata B-tree becomes the bottleneck of small objects. Lever: shard the metadata by object id, keep it on flash and replicate it.
4. Small objects: tiny shards waste I/O. Lever: pack small objects into larger extents before coding, or replicate them.

Failure modes

Real implementations

The alternative: n-way replication. It needs no coder and repairs by copying one shard, but costs 3× space for two-failure tolerance; use it for small, hot or latency-critical objects, and erasure coding for the cold bulk.

Sources

• Backblaze, Backblaze Vaults: Zettabyte-Scale Cloud Storage Architecture: blog (17 + 3 shards, 20 pods, ext4, checksums).
• Backblaze, Reed-Solomon erasure coding source code: blog (149 MB/s single core figure, library description).
• C. Huang et al., Erasure Coding in Windows Azure Storage, USENIX ATC 2012: paper (PDF) (LRC (12, 2, 2), 1.33×).
• M. Holland, G. Gibson, Parity declustering for continuous operation in redundant disk arrays, ASPLOS 1992: DOI 10.1145/143365.143383.
• OpenZFS, dRAID Howto: docs.
• J. Plank, K. Greenan, E. Miller, Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions, FAST 2013: USENIX.
• D. Hitz, J. Lau, M. Malcolm, File System Design for an NFS File Server Appliance, USENIX Winter 1994: USENIX.
• S. Weil et al., CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data, SC 2006: PDF.
• P. Corbett et al., Row-Diagonal Parity for Double Disk Failure Correction, FAST 2004: USENIX.
• Ceph documentation, Erasure code: docs.
• N. Hayashibara et al., The φ accrual failure detector, SRDS 2004: DOI 10.1109/RELDIS.2004.1353004.