Today we start 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 where customers can store unlimited data for any amounts of time. They only pay for what they use. Erasure codes help with the durability of the data and to keep the costs low. This paper introduces a new set of codes for Erasure coding called Local reconstruction codes (LRC). LRC reduces the number of Erasure coding needed to reconstruct the data fragments that are offline. It also reduces the storage overhead involved. LRC reduces the bandwidth and io required for repair reads over prior codes. This together with the low overhead is the main benefit of LRC LRC also demonstrates consistently low read latencies.
WAS uses LRC. WAS stores all of its data in an append only distributed file systemcalled the stream layer. Data is appended on to the end of active extents which are replicated three times by the underlying stream layer. These three copies remain till the extent gets filled. Once the extents are full, they are sealed and are never modified again. A background process lazily generates Erasure codes for the sealed extents and deletes the three copies which are no longer needed.
Erasure codes can reduce the cost of storage by 50% and given the size of cloud storage is in the order of exabyte, this is a significant saving.
#code jam question
Given two ominous find the minimum number of rearrangement needed to transform one omino into another.
Ignore rotations and translations of both oninoes. Oninoes are groups of unit squares joined together on one or more edges.
Solution since the two ominoes are properly oriented and centered for comparision.
We proceed row wise parity from bottom to top. If the number of unit squares in the bottom row are short for being equal, then more is borrowed from the row above or returned otherwise. When the numbers are equal, the sequence has to be the same.
WAS uses LRC. WAS stores all of its data in an append only distributed file systemcalled the stream layer. Data is appended on to the end of active extents which are replicated three times by the underlying stream layer. These three copies remain till the extent gets filled. Once the extents are full, they are sealed and are never modified again. A background process lazily generates Erasure codes for the sealed extents and deletes the three copies which are no longer needed.
Erasure codes can reduce the cost of storage by 50% and given the size of cloud storage is in the order of exabyte, this is a significant saving.
#code jam question
Given two ominous find the minimum number of rearrangement needed to transform one omino into another.
Ignore rotations and translations of both oninoes. Oninoes are groups of unit squares joined together on one or more edges.
Solution since the two ominoes are properly oriented and centered for comparision.
We proceed row wise parity from bottom to top. If the number of unit squares in the bottom row are short for being equal, then more is borrowed from the row above or returned otherwise. When the numbers are equal, the sequence has to be the same.
No comments:
Post a Comment