clay-codes 0.3.0

Clay (Coupled-Layer) erasure codes - MSR codes with optimal repair bandwidth
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

# clay-codes

[![Crates.io](https://img.shields.io/crates/v/clay-codes.svg)](https://crates.io/crates/clay-codes)
[![Documentation](https://docs.rs/clay-codes/badge.svg)](https://docs.rs/clay-codes)
[![License](https://img.shields.io/crates/l/clay-codes.svg)](LICENSE)

A Rust implementation of Clay (Coupled-Layer) erasure codes, based on the FAST'18 paper ["Clay Codes: Moulding MDS Codes to Yield an MSR Code"](https://www.usenix.org/conference/fast18/presentation/vajha) ([PDF](https://www.usenix.org/system/files/conference/fast18/fast18-vajha.pdf)). The construction was originally implemented in [Ceph](https://github.com/ceph/ceph/pull/14300/) and is now part of its master codebase.

## Why Clay codes?

In distributed storage, node failures are routine. When a node goes down, the system must repair it by fetching data from surviving nodes. With Reed-Solomon codes, repairing a single node means downloading **k full chunks** across the network -- even though you only need to reconstruct one.

Clay codes are MSR (Minimum Storage Regenerating) codes: they provide the same fault tolerance and storage overhead as Reed-Solomon, but repair a failed node by downloading only a **fraction** of each helper's data. In practice, this reduces repair network traffic by up to **2.9x** and repair time by up to **3x**.

## Quickstart

Add to your `Cargo.toml`:

```toml
[dependencies]
clay-codes = "0.3"
```

### Encode and Decode

```rust
use clay_codes::ClayCode;
use std::collections::HashMap;

// 4 data chunks, 2 parity chunks, 5 helpers for repair
let clay   = ClayCode::new(4, 2, 5).unwrap();
let data   = b"Hello, Clay codes!";
let chunks = clay.encode(data);

// Simulate losing node 0 -- collect the surviving chunks
let mut available: HashMap<usize, Vec<u8>> = HashMap::new();
for (node, chunk) in chunks.iter().enumerate() {
    if node != 0 {
        available.insert(node, chunk.clone());
    }
}

// Recover the original data from the remaining 5 chunks
let recovered = clay.decode(&available, &[0]).unwrap();
assert_eq!(&recovered[..data.len()], &data[..]);
```

### Bandwidth-Optimal Repair

This is the core advantage over Reed-Solomon. Repair downloads a fraction of each helper's chunk, where Reed-Solomon downloads `k` full chunks. `plan_repair` tells you exactly which sub-chunks to fetch from each helper, and `repair` reconstructs the lost node from that partial data.

```rust
use clay_codes::ClayCode;

let clay           = ClayCode::new(4, 2, 5).unwrap();
let data           = b"Hello, Clay codes!";
let chunks         = clay.encode(data);
let chunk_size     = chunks[0].len();
let sub_chunk_size = chunk_size / clay.sub_chunk_no;

// Which sub-chunks do we need from each helper to repair node 0?
let available = vec![1, 2, 3, 4, 5];
let plan      = clay.plan_repair(0, &available).unwrap();

// Fetch only those sub-chunks from each helper node
let mut partial: Vec<Option<Vec<u8>>> = vec![None; clay.n];

for (helper, sub_chunks) in &plan {
    let mut buf = Vec::new();
    for &sc in sub_chunks {
        let start = sc * sub_chunk_size;
        let end   = start + sub_chunk_size;
        buf.extend_from_slice(&chunks[*helper][start..end]);
    }
    partial[*helper] = Some(buf);
}

// Reconstruct node 0 from the partial data
let helpers: Vec<Option<&[u8]>> = partial.iter().map(|buf| buf.as_deref()).collect();
let recovered = clay.repair(0, &plan, &helpers, chunk_size).unwrap();
assert_eq!(recovered, chunks[0]);
```

### Repair With Missing Helpers

`plan_repair` takes the available nodes in your order of preference and plans around the rest. A y-section is a group of `q` nodes whose sub-chunks couple with each other. The plan takes every available node in the lost node's y-section and the first `k` available nodes of the other sections. When a same-section node is missing, the other-section helpers send `β` more sub-chunks each in its place. When fewer than `k` other-section nodes are available, same-section helpers make up the difference. Any `k` available nodes repair the lost one, and the plan errors with fewer.

When `n` isn't a multiple of `q`, `ClayCode::new` adds virtual nodes, and a y-section can hold some. A lost node whose y-section holds `v` virtual nodes needs every real node of its section and `k + v` nodes from the other sections, and the plan errors when any of them is missing.

## Parameters

Clay codes are configured with three values:

| Parameter | Description |
|-----------|-------------|
| `k` | Number of data chunks |
| `m` | Number of parity chunks (tolerates up to `m` simultaneous failures) |
| `d` | Number of helper nodes for repair (`k+1 <= d <= k+m-1`) |

The remaining parameters are derived automatically:

| Derived | Formula | Meaning |
|---------|---------|---------|
| `q` | `d - k + 1` | Coupling factor |
| `alpha` | `q^t` | Sub-chunks per chunk (sub-packetization level) |
| `beta` | `alpha / q` | Sub-chunks downloaded per helper during repair |

### Example Configurations

| Config (k, m, d) | alpha | beta | Repair BW vs RS |
|-------------------|-------|------|-----------------|
| (4, 2, 5)         | 8     | 4    | 37.5% savings   |
| (9, 3, 11)        | 81    | 27   | 59.3% savings   |
| (10, 4, 13)       | 256   | 64   | 67.5% savings   |

Higher `d - k` means more savings, at the cost of larger sub-packetization.

## Documentation

- **API reference**: [docs.rs/clay-codes](https://docs.rs/clay-codes)
- **Implementation guide**: [`docs/clay-practical-implementation.md`](docs/clay-practical-implementation.md) -- storage layouts, repair access patterns, metadata schemas, and performance considerations for integrating Clay codes into a distributed storage system.
- **Paper notes**: [`docs/clay-codes-fast18.md`](docs/clay-codes-fast18.md) -- detailed notes on the FAST'18 paper including construction, algorithms, and experimental results.

## License

Licensed under the Apache License, Version 2.0. See [LICENSE](LICENSE) for details.