Same durability, less than half the disk: how we pick redundancy per file

Rabata is S3-compatible object storage running on our own hardware in the EU and the US. In this four-part series our engineers explain how the stack works under the hood. Part 1 and Part 2 covered the architecture and the S3 metadata layer. This part is about dstorage, the service that stores the bytes.

Files, recovery sets, chunks

A file is a byte stream with a numeric ID. On write it is split into recovery sets, and each recovery set consists of several chunks. Every chunk in a recovery set is placed on a different server.

A chunk's address is a triple: (file ID, chunk index, disk ID). File metadata (size, redundancy scheme, the map of chunks to disks) lives in a sharded metadata store. Chunk bytes never go there. The metadata store holds only what's needed to find a chunk and to know the state of the hardware.

How many extra bytes

Disks die. Servers reboot. A filesystem sometimes returns something other than what was written. Storage has to survive all of this without losing data, which means storing more bytes than the file itself takes. The only question is how many more.

The simplest answer is several full copies on different servers. Three copies survive the loss of any two disks, but take three times the space of the data.

Erasure codes solve the same problem cheaper. The file is cut into N data chunks, and M more parity chunks are computed from them arithmetically. All N + M go to different servers. The trick is that the original data can be restored from any N chunks of the set: lose two, and the missing ones are recomputed from the rest.

The space overhead drops from (M + 1)× to (N + M) / N, and durability stays the same: the set survives the loss of any M chunks.

Small files pay a per-chunk tax

We pay for the saved space with computation on every write and every chunk repair. On small files we also pay per-chunk overhead. Erasure coding a 3 KiB file gives chunks of a few hundred bytes. For each such chunk, the filesystem write, the metadata record, the network call and the I/O operation outweigh what the chunk protects.

So the redundancy scheme is chosen for each file based on its size. Two schemes are configured today:

Copy costs more space, but a small file is one chunk instead of seven, and nothing has to be computed on read.

Schemes are stored by ID, not by value

File metadata records which configuration the file was written with. New configurations are added rarely.

If we want a new scheme, or new parameters for an existing one (a different number of data or parity chunks, a different chunk size), we don't need a migration. Old files are always read with the scheme they were written with. A new redundancy policy rolls out as a config change and affects new writes only.

Chunk count matters more than byte count

The last group of a file rarely divides evenly. Instead of an incomplete group of tiny chunks, the remainder is appended to the previous group. This keeps chunk sizes in a sane range regardless of file size.

That matters because the number of chunks, not the number of bytes, defines metadata volume, the number of I/O operations and the cost of repairing a chunk.

No per-chunk index

There is no index that maps byte offsets to chunks. The layout is computed. Given a file's size and redundancy scheme, the position of any byte (which recovery set, which chunk, which offset inside the chunk) can be calculated. Reads and repairs of damaged or unavailable chunks use the same code.

Streaming writes with bounded memory

Writes are streamed, but erasure coding needs a full parity group in memory to compute the parity chunks. Chunks of a recovery set are accumulated and flushed once parity is computed and the chunks are uploaded to storage servers.

Memory use is bounded by one parity group (group width × chunk size), whether the file is 1 MiB or 1 TiB. And the parallelism that matters is preserved: the chunks of a group go to different disks on different servers at the same time.

Rabata S3: S3-compatible storage at $0.006/GB/month with no API request fees. Change the endpoint and keys, keep your code.
`