Practical Codes for Storage Systems
Practical Codes for Storage Systems
An Introduction to Entanglement Codes
An Introduction to Entanglement Codes
Entanglement codes generate redundant information to protect content against failures in a storage system. The method increases the reliability and also improves performance because it creates multiple paths to read data using combinations of elements stored in the system.
Simple Entanglement Codes
Simple Entanglement Codes
Simple entanglements create chains of interdependent elements that alternate data represented by a vertex and redundant information represented by an edge.
◼
A visualization of an open entanglement chain. The first and last vertices are virtual elements and do not contain information. The first vertex contains the initial condition of the chain:
In[155]:=
g=Graph[{01,12,23,34,45,56},VertexLabels"Name",VertexSizeMedium,VertexStyle{0Red,6Red}]
Out[155]=
Write data
Write data
Vertices represent data. They can store anything, e.g. a digit, numbers, chars, strings or large chunks of data. The only constraint is that all of them must store the same amount of information.
◼
In this example, the chain will store “Hello”. First, we convert the string to character codes:
In[156]:=
vertexValues=ToCharacterCode["Hello"]
Out[156]=
{72,101,108,108,111}
The encoder uses the function BitXor to compute the bitwise XOR of the last two elements of the chain. The input are the vertex being encoded and its incident edge (whose weight was generated during the encoding of its predecessor vertex and contains redundant information derived from all the predecessor vertices).
◼
If the vertex values is known, the encoding process is equivalent to compute the cumulative bitwise XOR operations of the elements of the vertexValues list:
In[157]:=
encodedData=FoldList[BitXor,0,vertexValues]
Out[157]=
{0,72,45,65,45,66}
The list of vertexValues only contains the values for vertices 1-5. Let’s fix it.
◼
To fill the virtual vertices with some content, we add zeros at the first and last position of the list:
In[158]:=
vertexValues=Insert[vertexValues,0,{{1},{-1}}]
Out[158]=
{0,72,101,108,108,111,0}
Now, we can redefine the graph using the new content.
◼
We could describe vertices with associations. The key is the index/label of the vertex and the value contains one element of the vertexValues list:
In[159]:=
vertex=AssociationThread[VertexList[g],vertexValues]
Out[159]=
00,172,2101,3108,4108,5111,60
◼
We can visualize the entanglement chain using the vertex weight to store plain data and edge weight to store encoded data:
In[160]:=
g=Graph[{01,12,23,34,45,56},VertexSizeMedium,VertexStyle{0Red,6Red},VertexWeightvertexValues,EdgeWeightencodedData,VertexLabels"VertexWeight",EdgeLabels"EdgeWeight"]
Out[160]=
Read data
Read data
Data can be recovered using nodes or edges
◼
Method 1: Reading plain text from vertices (without decoding)
In[161]:=
Row[FromCharacterCode[PropertyValue[{g,#},VertexWeight]]&/@{1,2,3,4,5}]
Out[161]=
Hello
◼
Method 2: Decoding data from edges. We apply BitXor to pair of values obtained by Partition.
In[162]:=
FromCharacterCode[BitXor@@@Partition[encodedData,2,1]]
Out[162]=
Hello
Decoding in detail
Decoding in detail
We can read the content of a node by applying the bitwise XOR to the weight of its two adjacent edges
◼
For example, to read “e” (char code 101) we use the adjacent edges that contain 72 and 45.
In[163]:=
FromCharacterCode[BitXor[encodedData[[2]],encodedData[[3]]]]
Out[163]=
e
◼
Moving from left to right:
In[164]:=
BitXor[encodedData[[2]],vertexValues[[3]]]
Out[164]=
45
◼
Moving from right to left:
In[165]:=
BitXor[encodedData[[4]],vertexValues[[4]]]
Out[165]=
45
Failure Patterns (cmd/alt+4)
Failure Patterns (cmd/alt+4)
Section names, the total number of sections, and section organization will differ based on the topic.
Here are some ideas for sections you might consider:
history/origins
derivation
applications
common misunderstandings
recent developments
unanswered questions
derivation
applications
common misunderstandings
recent developments
unanswered questions
Simple Entanglements behavior
Name of a related topic for exploration
Name of another related topics for exploration (repeat as needed)
Authorship information
Vero Estrada-Galinanes
Date of creation
Author email address (please use the email associated with your Wolfram User ID)
