EC library interface

Registered by John Dickinson on 2013-07-17

A wrapper for various EC libraries so that different ones can be used

Blueprint information

Status:
Not started
Approver:
None
Priority:
Medium
Drafter:
None
Direction:
Needs approval
Assignee:
None
Definition:
Approved
Series goal:
Accepted for future
Implementation:
Not started
Milestone target:
milestone icon ongoing

Related branches

Sprints

Whiteboard

I figured I would get the discussion going on the EC interfaces and basic mechanics. This is all off the top of my head, so please make suggestions and/or point-out anything that looks wrong or unclear. Feel free to add others to this thread, if you want...

I assume we can use Python abstract base classes to enforce any EC lib used by Swift.

Let's assume that an EC lib must implement encoding a string, decoding a set of fragments into a string, verifying the consistency of a set of fragments, reconstructing a set of missing fragments and returning fragments needed to reconstruct a set of missing fragments.

Here are the basic functions (bastardizing Python syntax for clarity):

def encode(bytes): return List[String]
def decode(fragment_payloads): return String
def reconstruct(available_fragment_payloads, missing_fragment_indexes): return List[String]
def fragments_needed(missing_fragments): return List(List[Int])
def get_metadata(fragment): return String
def verify_stripe_metadata(fragment_metadata_list): return List[Int]

encode() and decode() are pretty self explanatory and will be the main functions used in the data path. We encode a string into a list of strings (fragments). We decode a list of fragments into a string.

fragments_needed() and reconstruct() will be used by the reconstructor to effectively reconstruct corrupted or lost fragments. In the case of Reed-Somolon, fragments_needed() can return a list of choose(n-f, k) fragment lists containing all possible combinations of fragments that can be used to reconstruct the 'f' lost fragments. This function is mostly useful for LRC, Pyramid codes and irregular XOR-based codes, since they will typically require less than 'k' fragments to reconstruct a lost fragment.

For example, suppose we have LRC with 10 data fragments where the first and last 5 data fragments contribute to local parities, P_1 and P_2, respectively. Assume there are two regular Reed-Solomon parities: P_3 and P_4. If the reconstructor detects the loss of fragment 1, then

fragments_needed([1]) -> [ [ 2, 3, 4, 5, P_1], [2, 3, 4, 5, 6, 7, 8, 9, 10, P_3], ...]

The reconstructor can now try to fetch the appropriate fragments (it will try [2, 3, 4, 5, P_1] first) and call reconstruct on their payload: e.g., reconstruct(fragments, [1]) returns a list of strings corresponding to reconstructed fragments. Now the reconstructor can push out the reconstructed fragments.

Stripe-level verifications can be done by having each node send their fragment's metadata to some initiator (via get_metadata()). The metadata is opaque to the auditor, but has meaning in the individual EC instance. The initiator is another storage node auditing a fragment in the particular stripe. The initiator will then use verify_stripe_metadata() to do a stripe-wide verification and returns a list of 'problem' indexes (e.g. detects that fragment 3 is bad).

The metadata can be algebraic signatures, checking other types of checksums, checking fragment indices, etc, or some combination of those things. In other words, anything the underlying library deems useful.

(?)

Work Items

Dependency tree

* Blueprints in grey have been implemented.

This blueprint contains Public information 
Everyone can see this information.