Blob Store

Storage Nodes and Erasure Coding

Design the storage layer under an object store: how nodes lay blobs out on disk, how fresh data is replicated and older data erasure-coded, where each fragment is placed, and how lost disks and racks are repaired.

Overview

An object store has two halves. The metadata half maps a bucket and key to a blob ID and answers LIST; the Object Storage topic covers it, with the API, multipart uploads and consistency. This problem is the other half: the blob store that keeps the bytes. Given a blob ID it must return the bytes quickly, for years, while disks, hosts and whole racks fail every day.

Two published systems make the design concrete. Facebook's f4 (OSDI 2014) stores 'warm' blobs, which are read less often than new ones, with Reed-Solomon coding, cutting the bytes stored per byte of data from 3.6 to 2.8 and then 2.1. Windows Azure Storage (USENIX ATC 2012) writes new data as three copies, then erasure-codes it once an extent is sealed, using its local reconstruction codes (LRC) to make repairs cheaper.

Questions to ask first

How much data, how big are blobs? — 100 PB, about 1 MB on average (photos, documents, video segments)
Are blobs changed after writing? — Never; a blob is written once, read, and eventually deleted
Which failures must we survive? — Disks, hosts and racks within a region routinely; a whole datacenter rarely
How hot is the data? — New blobs are read and deleted much more than old ones
Latency? — A healthy read in one disk seek; a read of a lost block can be slower
Cost target? — Well under 2 bytes of disk per byte of data for older blobs

What you will be able to do

Lay blobs out on a storage node so a read is one disk seek.
Explain why fresh data is replicated and older data erasure-coded, and when to switch.
Compute the storage overhead and the repair cost of replication, Reed-Solomon and LRC.
Place fragments so a rack or datacenter failure costs at most one fragment per stripe.
Design degraded reads, background rebuilds and deletes for immutable, coded data.

Key concepts

Append-only volumes
In-memory blob index
Sealed extents
Reed-Solomon (n, k)
Local reconstruction codes
Effective replication factor
Failure domains
Degraded reads
Rebuild throttling
Crypto-deletion

Functional requirements

Store a blob and return its ID; read it back whole or by byte range
Delete a blob; reclaim its space eventually
Keep every blob readable through disk, host and rack failures, and through the loss of a datacenter
Detect silent corruption and repair it
Move blobs from replicated to erasure-coded storage as they cool

Non-functional requirements

A healthy read costs one disk seek on one node (a target we chose)
Stored bytes under 1.5× the data for sealed volumes within a region (a target we chose)
No stripe ever has two fragments in the same rack
Repairs are throttled so they never starve client reads
A deleted blob is unreadable at once, even before its space is reclaimed

Interview questions

How does a storage node read a blob in one disk seek?
Why not erasure-code everything from the start?
Compare replication, Reed-Solomon and LRC.
How do you place fragments?
What happens when a client reads a blob whose disk just failed?
How are deletes handled in coded storage?
How much repair traffic should you plan for?