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 were discussing Local Reconstruction codes in windows azure storage.  The placement of the fragments was based on two factors: load which favors the less occupied extent nodes and reliability which avoids placing fragments into the same correlated domain.  Correlated domains can be those from a fault such as on a rack that brings down a few nodes together or they can be on an upgrade domain which categorizes a group of nodes that are taken offline. Let us now see how to place a fragment in WAS.  A WAS stamp consists of twenty racks There are sixteen fragments possible for an extent and each is placed on a different rack for maximum reliability. If each fragment were similarly placed on a different upgrade domain, there would be one too many and resulting in slow down.  There are up to 10 upgrade domains used. In order to place the fragments across upgrade domains, the local group property of LRC is exploited and the group fragments belonging to the different local groups are placed into the same upgrade domains. The local data fragments are placed in the same upgrade domain. Similarly the local data parities are placed in the same upgrade domain.  The global parities are placed in separate upgrade domains.
#codingexercise
After detecting the overlaps from two strings, find if a new given string is a concatenation of two or more overlaps

Void Combine (List<List<char>> overlaps, List<List<char>> b, List<char> target,  int start, int level)

{

For (int I = start ; I < overlaps.Length; i++)

{

b[level] = overlap[i];
if (b.toString() == target.toString()) Console.WriteLine('True');

If (I < overlaps.Length)

Combine(overlaps,b, target, start+1,level+1)

B[level] = NULL;

}

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 were discussing the components of the WAS architecture. We discussed the Erasure coding is in the stream layer. We now review LRC in windows Azure storage. The placement of data and parity fragments is based on two factors : load which favors the less occupied and sparse distribution and reliability which favors the separation of faults from correlated domains. There are two such correlated domains one is the rack which can fail altogether and the second is the upgrade which can fail as groups of fragments are taken offline together.
#coding exercise
Determine overlaps in linear time between two sequences
We need offsets and length
If we find a match  we remove it from the original string
We repeat until there are no more left.
Matches have same length and sequence.
We iterate from the end of the last match in one string.

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.