Redundant fragments recover known erasures under a code model
Calculate k+m storage overhead and reconstruction thresholds while separating known missing fragments from undetected corruption and operational write policy.
On this page
The question for today
What you’ll understand
- Calculate payload expansion for a stated k+m coding layout.
- Explain the assumptions behind reconstruction from k valid matching fragments.
- Distinguish mathematical recoverability from service availability and safe writes.
Replication stores full copies; erasure coding stores a representation with redundant fragments. A suitable Reed-Solomon construction can recover original data from enough valid fragments even when some fragment locations are unavailable. The saving in raw space comes with read, write, placement, and repair tradeoffs. Start with the code's mathematical promise, then add the implementation assumptions needed to use it. Knowing that four symbols suffice algebraically does not prove that the cluster can identify, read, and safely serve the right four fragments.
Count data and redundancy with one unit system
Let k denote data fragments and m denote additional coding fragments for one stripe in a systematic maximum-distance-separable layout. Ignoring padding and metadata, each fragment contains one kth of the logical payload, so all k+m fragments expand storage by a known factor. A 4+2 layout stores six fragments whose combined payload is one and a half times the original. This is a raw encoding calculation, not a prediction of a product's billed capacity or a complete filesystem allocation budget.
The coding arithmetic operates over an appropriate finite field, not by ordinary floating-point interpolation of bytes. The encoder and decoder must agree on field, matrices, fragment indices, lengths, and stripe generation. Fragments from different object versions cannot be combined merely because their sizes match. The RFC 5510 coding model and the explicitly versioned Ceph erasure-code documentation are useful references for the mathematical and implementation layers respectively; neither tells us an undisclosed provider's internal coding profile.
Known erasures differ from unidentified bad data
For the stated MDS code, any k valid distinct fragments from the same stripe generation determine the data. Thus up to m known missing fragments can be tolerated algebraically. If a returned fragment is corrupt but accepted as valid, the decoder's assumptions fail. Checksums can help detect corruption and turn an identified bad fragment into an erasure, but the reference checksum and metadata also need trustworthy handling. General correction of unknown errors has a different budget and decoder requirement; it should not be inferred from the missing-fragment rule.
Operational availability adds constraints beyond the count. Fragment locations can be unreachable, version evidence can be incomplete, and a service can deliberately block writes while redundancy is too low. Ceph has pool and state-dependent policies; the algebraic k-fragment threshold is not a universal safe-write threshold. A reconstruction test should remove known fragments, verify the expected content and generation, and inspect the actual service behavior under its configured policy instead of claiming that every mathematically recoverable state accepts every operation.
A probability model needs an explicit failure unit
A toy independent-fragment calculation can illustrate the reconstruction threshold, but its trial unit must be clear. If p means each fragment is independently valid and readable during one observation, a binomial tail gives the chance of having at least k usable fragments. Shared racks, software bugs, and object-level metadata faults violate that model. The result is not an annual data-loss probability or a product durability estimate. Recovery duration and additional failures during repair require further analysis.
Use the probability lab with Reset, then set both p=0.9 and n=6. Predict which bars represent the at-least-four-fragment event before inspecting and using Play or Step. Add bars four through six to obtain the toy 4+2 reconstruction event. Playback highlights exact outcomes rather than generating disk failures. The instrument performs no finite-field encoding, corruption detection, or version validation, so use its count distribution only after stating the code and independent-valid-fragment assumptions outside the diagram.
Work it through
Budget a 4+2 stripe
Encode an 8 MiB logical stripe using a systematic MDS 4+2 layout. Ignore padding and metadata. Two fragments become known unavailable; all others are valid, distinct, and from the same generation.
Each of the four data fragments represents 8/4 = 2 MiB. There are six stored fragments, so encoded payload is 6 × 2 = 12 MiB, matching expansion factor 1.5.
Two unavailable fragments leave four valid fragments, exactly the reconstruction threshold. The stated MDS decoder can reconstruct the 8 MiB logical stripe from those four under the declared assumptions.
A third known unavailability would leave only three fragments, which is below this general reconstruction threshold. No raw-space saving calculation proves that an implementation can recover from that state or safely accept writes while already degraded.
The stripe uses 12 MiB of encoded payload and tolerates the two specified known erasures algebraically. Metadata, placement, and service policy remain additional requirements.
The living notebook
Explore the model
Interactive lab · probability
Count valid fragments before applying a threshold
Reset, set both independent valid-fragment probability p=0.9 and n=6, predict the total mass of bars four through six, then Play or Step. The binomial model does not encode Reed-Solomon fragments, repair corruption, or estimate annual durability.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forThe k-fragment rule is conditional on valid same-generation fragments and the chosen code; independence is an extra modeling assumption.
Pause & reason
Check your understanding
Your turn
Try it yourself
A 6+3 MDS layout stores a 24 MiB logical stripe, ignoring overhead. Calculate fragment size and encoded payload, then state whether three known missing fragments are algebraically recoverable.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Divide by k for each equal fragment and multiply by k+m for total encoded payload. Count the valid remaining fragments.
Compare with the solution
Each fragment has 24/6 = 4 MiB, and nine fragments total 36 MiB. Three known missing fragments leave six valid distinct same-generation fragments, meeting the stated threshold. This answer assumes the decoder, metadata, and remaining data are correct and reachable; it does not certify operational availability, unknown-error correction, or the policy for accepting further writes.
Keep the idea
Take it with you
- The k+m layout determines a raw coding expansion factor under explicit overhead assumptions.
- Known-erasure reconstruction needs valid correctly indexed same-generation fragments.
- Recoverability, degraded-write policy, and real failure correlation require separate evidence.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.