CodingSets
CodingSets is Hydra's placement scheme that restricts erasure-coded fragments to extended server groups while choosing less-loaded members.
Mechanism: CodingSets partitions servers into k+r+l-node groups. Each codeword uses k+r less-loaded members of one group; l adds placement choices. Hydra reports calculated large-cluster loss probabilities, not incident rates. [1]
Origins: Copysets concerns replication rather than coded fragments. It separates loss frequency from magnitude and supports rack-constrained placement. [2]
Exact example: Six equal-sized 2+1 stripes on six nodes store three fragments per node. Concentrated placement repeats two disjoint triples; spread placement uses six cyclic triples. For all 15 equally likely two-node failures, any-stripe loss occurs in 6/15 versus 12/15 cases. Each layout has 18 stripe-loss occurrences: mean 1.2 stripes per case, but 3 versus 1.5 conditional on any loss. Repeated placements hold distinct data. [3]
Rack control: Instead weight the three rack outages {0,1}, {2,3}, {4,5} equally. Both layouts lose 6 stripes across three cases. A layout repeating {0,2,4} and {1,3,5} loses none. Its mean is still 1.2 under uniform two-node failures. Expected-loss invariance therefore needs a specified failure distribution. [3]
Limits: These static layouts are not a full CodingSets load-balancing simulation. A stripe is unavailable with fewer than two surviving current fragments; this is not proof of permanent data loss. No repair, corruption, write race, fallback or outage duration is modeled. Exact inputs, cases and tests are downloadable. [4] [3] [5]
Probability: The section-5 power expression treats overlapping minimal failure subsets as independent; it is not an exact union probability for fixed-count failures. Exact node-disjoint-group counts use integer coefficients. [6]
Relations
- related
- Hydra remote memory, Failure domain
Limitations
- For two disjoint, fully populated 2+1 groups, all 20 equally likely three-node failure sets make a stripe unavailable: 100%, versus 78.4% from the power expression. This is an exact constructed example, not a fleet measurement. [7]
- For 100 disjoint, fully populated 8+2 groups and ten uniformly chosen failed nodes, the exact probability is 0.834065%, versus 0.862885% from the power expression (rounded). The expression is neither a universal upper nor lower bound. [7]
Citations
- Lee et al. Hydra: Resilient and Highly Available Remote Memory. FAST 2022, sections 5 and 7.2.1.
- Cidon et al. Copysets: Reducing the Frequency of Data Loss in Cloud Storage. ATC 2013, sections 4.1 and 4.3.
- Hesela: exact placement cases, event counts and conditional loss-size results
- Hesela: standalone finite placement model, assumptions and reproduction command
- Hesela: exact arithmetic, exhaustive subset and invalid-input regression tests
- Hesela: exact fixed-count occupancy derivation, assumptions and reproduction instructions
- Hesela: exact integer counts, rational probabilities and formula comparisons
- Hesela: complete offline calculation, tests, independent oracle and source metadata
Sources & caveats
- Primary-source synthesis with an original finite example, not a native Hydra deployment or replication of the papers' performance results.
- Uniform scenario weights are constructed assumptions; no fleet failure rates, confidence intervals or availability SLA are inferred.
- The occupancy audit assumes node-disjoint groups and uniform fixed-count failures. Its 1,000-node examples use l=0, not Figure 15's l=2 baseline; no practical ranking reversal is established. [6]
- With l>0, exceeding a group's parity threshold is only an upper envelope for stripe unavailability unless actual fragment placements cover every dangerous subset. Overlapping groups require a different count. [6]
- The original placement evidence is unchanged. The exact occupancy results and two independently implemented counting methods are included in the reproducible package. [8]