We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. There are three components to a WAS architecture - the front end, the object layer and the stream replication layer. All of these three components are present within any single storage cluster.  The Erasure coding is implemented within stream replication layer which is responsible for the robustness of data. The object partition is in a separate layer so it can scale out. The main components of a stream layer are the stream managers and extent nodes.  The nodes consist of blocks which is the unit for Crc which implies data is read or appended using blocks. When the extent reaches maximum size, a new extent is  created. When the extent is sealed it becomes immutable. During Erasure coding, the SM creates  fragments on a set of ENs which are responsible for . And then one of the EN is chosen as the coordinator which has the responsibility of making sure the Erasure coding completes.the coordinator EN decides which fragment boundaries for all of the fragments will be in the extent. Then this  is communicated to the target ENs. The Erasure coding can be paused and resumed anytime because it is offline.
#coding exercise
Find duplicate substrings in linear time between two strings. Matching substrings do not overlap on the same string. Their sequences also match.
List <List <char>> getoverlaps ( list<char> a, list <char> b )
{
var ret = new List <List<char>>();
for (int I = 0; I < a.count; i++)
 for ( int j = 0; j < b.count; j++)
{
  If (a [i] == b [j])
    {
      Int m =i;
      Int n = j;
      int k = 0;
      var word = new List <char>();
      while  (a [m] == b [n] && m < a.count  && N < b.count)
       {
          Word.add (a [m]);
           M++;
           N++;
           K++;
        }
        Ret.add (word);
        I = I + k;
        J = j + k;
     
    }
 
}
Return ret;
}

Differences between Additional Edges in a graph and a list of normalized paths

We have traditionally represented nodes and edges in a graph with vertices and adjacency matrix or list. We often use a graph to find shortest path between two vertices. Although we use well known graph algorithms to traverse the graph to find these paths dynamically, we could also capture and save this information with the graph itself. This is ideal when the graph does not have to be manipulated very often such as with addition or deletion of nodes and or edges. Data warehouses represented by graphs could benefit with additional representational aid because they don’t change very much

Some such aid to represent graphs in order to improve performance for traversal or to find paths between vertices include the following:

1)      Add additional edges to represent connectivity by skipping a number of nodes. There could be a set of edges colored differently for skipping say 2, 4, 8 … nodes in the graph.

2)      To have a normalized set of paths among all enumerable paths that could be iterated to construct path between two vertices.

The differences between these approaches are as follows:

The former is used this way: If we have a source and destination vertices, we change the source or destination to something closer between the two between which the destination is guaranteed to be present thus optimizing traversal between visiting each interim node one by one and skipping them. Additionally, we traverse the unknown segment from higher order edges to lower order edges where higher order are skip lists and lowest order is next vertex hop or single hop list.

The latter is used this way: If we have a source and destination vertices, we find all paths that contain source and destination and filter them progressively by replacing source and destination with interim nodes. The idea is that a set of normalized paths will be guaranteed to have interim nodes and also reduce the number of all possible paths that may be scanned otherwise.  By changing source or destination or both with as front most as possible or as end most as possible we can converge to a fully traversable path with fewer iterations. Each iteration skips a few nodes by knowing that there already exists a path to connect them.

The latter technique does not require touching the graph and the normalized list can be stored outside the graph. The former technique requires mode edges to be added to the same graph. Both techniques support algorithms to be modified to offload the shortest path discovery between two vertices with performance improvements.

#code question
Do linear deduplication between two integer arrays to merge them.

List<int> dedup( List <int> a, List <int> b)
{
a.sort ();
b.sort();
var ret = new List <int> ();
Int m = 0;
Int n = 0;
For (int I = 0; I < a.count + b.count;  I++)
{
int min = a[m];
If (a [m] == b [n])
{
M++;
n++;
}
If (a [m] < b [n])
{
M++;
}
Else
{
min = b[n];
N++;
}
if (ret.Count == 0 || ret.Last() != min)
     ret.Add(min);
}
Return ret;
} 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.  A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities. We now read the cost and performance trade-offs. Each (k,l,r) set yields one set of values of reliability, reconstruction cost and storage overhead. If we vary the parameters, we can get many set of values. Each fragment has to place on a different domain, the number of domains in a cluster limits the total number of fragments in the code. The authors use 20 as a limit since the storage stamps have upto 20 fault domains.Further they keep those set of parameters that yield equal or higher reliability than 3-replication. Then they plot storage and reconstruction cost of the remaining sets. Each individual point represent one set of coding parameters which in turn represents certain tradeoffs between storage cost and reconstruction performance. The authors found this to vary a lot so they only took the lower bound.

#coding exercise:
given a set of paths in a graph, normalize them to not contain repetitions.
We represent vertices and paths as string
then we apply regular expression between the two
void normalize(List<string>paths)
{
var ret = new List<string>();
for (int i = 0; i < paths.Count; i++)
   for (int j = 0; j < paths.Count; j++)
   {
      // don't compare me to myself
       if (i != j){
       var match = GenerateIntersections(paths[i], paths[j]); //List<string>.Intersect() may give non-contiguous paths
       ret.Add(path);
       }
    }
return ret;
}

The GenerateIntersections does not need to be O(n^2) where n is the length of the paths . It  can be linear because the finite automaton for both strings will have overlaps and those are what we are interested in. There are string matching algorithms that generate such automaton in linear time and it is smaller than the lengths of paths.
With the given automaton, we can find overlaps and use them to find the overlapping paths.
Assuming that we have automaton passed in as character lists as parameters to the function below, we get intersections of the automaton as follows:
List<List<Char>> GenerateIntersections(List<Char> a, List<Char> b)
{
var ret = new List<List<char>>();
for (int i = 0; i < a.Count; i++)
   for (int j = 0; j < b.Count; j++) // we can also make it linear by skipping ahead.
{
     int m  = i;
     int n = j;
     var match = new List<Char>();
     while (a[m] == b[n] && m < a.count && n < b.count)
     {
         match.Add(a[m]);
          m++;
          n++;
      }
     if (match.IsEmpty() == False && ret.Contains(match) == false)
         ret.Add(match);
}
return ret;
}

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. It introduces new codes called the Local Reconstruction Codes.  A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities, one for each local group and r global parities.Any single data fragment can decoded from k/l fragments within its local group. In addition, LRC achieves maximally recoverable property It tolerates upto r+1 arbitrary fragment failures. It also tolerates failures more than r+1 and upto l+r as long as they are information-theoretically decodeable.  Finally LRC provides low storage overhead. It requires the minimum number of parities as compared to other such codes.
The choice of the k,l and r parameters for LRC code is dependent on the reliability outcomes. At a minimum, three-replication is required. This is an industry standard. Higher reliability can be achieved by choosing the parameters with a Markov reliability model.  This model considers both independent and correlated failures. The model is extended by LRC to capture unique state transitions. Those transitions are introduced because the failure mode depends on not only the size of the failures, but also which subset of nodes fails.  Each state in the Markov process represents the number of available fragments (data and parity). Let lambda denote the failure rate of a single fragment. The transition rates from all fragments healthy state N to state N-1  is N times lambda.  Let pd denote the percentage of four decodeable failures. Then the transition state to decodeable failures is N lambda pd and that for non-decodeable failures is N lambda (1-pd) The reverse transition going from a lower state to a higher state is equal to the average repair rate of a single fragment.  Repair rates beyond a single failure are dominated by the time taken to detect failure and trigger repair.
#codingexercise
Normalize two strings with a common pattern into substrings that don't have any overlap.
List<char> normalize(List<char> a, List<char> b)
{
var ret = new List<char>();
// assume one pattern to match
var match = a.Intersect(b);
var fragmenta = a.Except(match);
ret.add(fragmenta);
ret.add(match);
var fragmentb  = b.Except(match);
ret.add(fragmentb);
// repeat the above for more matches based on regex groups or KMP
return ret;
}
In a graph, the branches of a minimum spanning tree are normalized paths 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing how to construct the coding equations. The coding coefficients for each group are assigned elements from a finite field and the elements are represented by four bits. The coding coefficient for one group are chosen with their lower order two bits as zero and that of the other is chosen with their highest order two bits as zero. This way they will never be equal and they satisfy the conditions that they are not individually zero and the groupwise sum of the coding coefficients are not equal.
This way all the three failure patterns can be decoded and about 86% of all the four failures. In short, the LRC achieves the maximally recoverable property.
A (k,l,r) LRC divides k data fragments into l local groups. It encodes l local parities and r global parities. The key properties of a (k,l,r) LRC are as follows: i) single data fragment failure can be decoded from k/l fragments ii) arbitrary failures up to r+1 can be decoded. The paper proves that the number of parities of LRC meets the lower bound exactly, LRC achieves its properties with the minimum number of parities.
#coding exercise
Given  a set of Paths between nodes in a graph as a string of nodes with overlaps, normalize them by splitting. Overlaps have to include one of the ends of the string and cannot be size less than or equal to two.
We compare strings pairwise to detect overlap.  This is an O(N^2) comparisions
However each detection need not cost to the order of the square of the number of elements.
For each pair, we detect the overlap by applying Knuth Morris Pratt which yields O(N) running time. KMP informs the maximum amount of one string matched at the end of other.

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing how to construct the coding equations. The paper says there are four coding equations. The coding coefficients are determined by four different cases - when none of the four parities fails, only one of the px and py fails, and  both px and py fail.  The coefficients of the first set are chosen among the elements whose lower order 2 bits of coefficients and their sum are zero. The coefficients of the second set are chosen among the elements whose higher order 2 bits of coefficients and their sum are always zero.  Hence they will never be equal. The advantage is that this way of constructing coding equations requires a very small finite field and makes implementation practical. This makes LRC decode arbitrary three failures. To check whether a parity is information theoretically decode-able 

We continue reading the paper "Erasure coding in Windows Azure storage"  by Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin.
Erasure coding is a data protection method where data is broken into fragments, expanded and encoded with redundant data pieces and stored across a different set of locations or media. This paper talks about Erasure coding in windows Azure storage WAS. We were discussing the design decisions such as why Reed-Solomon code was not sufficient and why the paper introduced a new one. We also saw how the Local Reconstruction code introduces group fragment parity and improves reconstruction cost. This is with some storage overhead but provides more options with a new trade-off point. We discussed the coding equations and LRC's maximally recoverable property which is a way of saying LRC can decode any failure pattern which is possible to reconstruct.
The challenge was to find a set of coding equations that achieves the maximally recoverable property
These coding equations were found this way:
LRC can tolerate arbitrary 3 failures by choosing the following two sets of coding coefficients a and b for groups x and y.  For each group, each coefficient is linearly applicable for each of the three failures, or applicable as the squares or none at all.  The same goes for  the other coefficient for the other group.  This gives us six equations.
Then the LRC's coding equation are as follows: the sum of the linear coefficients of each group as p0, the sum of the square coefficients of each group as p1, the no coefficients case for one group as px, and the no coefficients case for the other group as py.
These coefficients can then be found by applying the following scenarios:
None of the four parities fails
Only one of the px and py fails
Both px and py fail
To ensure all the cases are decodable, all the matrices should be non-singular which leads to the following conditions.
None of the coefficients are zero.
None of the coefficients of group 1 are same as that of group 2
the sum of the coefficients of group 1 should not be the same as the sum of the coefficients of group 2.
#codejam problem
Determine sums of list of integers
public static List<int> Sums( this List<List<int>> numbers)
{
var ret = new List<int>();
numbers.ForEach (x => ret.Add(x.Sum()));
return ret;
}
Could we consider implementing extension methods in C++ ?
In C++ we have the ability to wrap classes and structs if we cannot inherit from them. Therefore we can add methods easily as function pointers or methods.