Erasure coding immutable data

• US 8,473,778 B2
• Filed: 09/08/2010
• Issued: 06/25/2013
• Est. Priority Date: 09/08/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simitci, Huseyin, Xu, Yikang, Wang, Haiyong, Ogus, Aaron William, Calder, Bradley Gene
• Primary Examiner(s): Baker, Stephen M
• Application Number:
  US12/877,175
• Publication Number:
  US 20120060072A1
• Time in Patent Office: 1,021 Days
• Field of Search: 714/6.2
• US Class Current: 714/6.2
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes

Abstract

Embodiments of the present invention relate to systems, methods and computer storage media for erasure coding data in a distributed computing environment. A sealed extent is identified that is comprised of two or more data blocks and two or more index blocks. The sealed extent is optimized for erasure coding by grouping the two or more data blocks within the optimized sealed extent together and grouping the two or more index blocks within the optimized sealed extent together. The optimized extent may also be erasure coded, which includes creating data fragments and coding fragments. The data fragments and the coding fragments may also be stored in the distributed computing environment. Additional embodiments include monitoring statistical information to determine if replication, erasure coding or a hybrid storage plan should be utilized.

Claims

1. A method in a distributed computing environment for erasure coding data, the method comprising:

identifying a data stream stored in the distributed computing environment comprised of at least one sealed read-only extent (sealed extent), wherein the sealed extent is comprised of two or more data blocks and two or more index blocks;

optimizing, with a processor in the distributed computing environment, the sealed extent, wherein optimizing is comprised of;

(1) grouping the two or more data blocks within the optimized sealed extent together and

(2) grouping the two or more index blocks within the optimized sealed extent together;

erasure coding the optimized sealed extent, wherein erasure coding is comprised of;

(1) creating a predefined number of data fragments, wherein the predefined number of data fragments are created by dividing data represented by the two or more data blocks of the optimized sealed extent into the predefined number of data fragments and

(2) creating a predefined number of coding fragments, wherein the coding fragments are created based, at least in part, on the data fragments; and

storing the predefined number of data fragments and the predefined number of coding fragments in the distributed computing environment.

2. The method of claim 1, wherein a Reed-Solomon erasure coding is utilized for the erasure coding.

3. The method of claim 1, wherein the erasure coding is performed as a background operation in the distributed computing environment.

4. The method of claim 1, wherein the last data block of data from the two or more data blocks written to each of the predefined number of data fragments is an entire block of data.

5. The method of claim 1, wherein creating the predefined number of data fragments further comprises inserting the two or more index blocks of the sealed extent to each of the data fragments.

6. The method of claim 1, wherein each of the predefined number of data fragments is stored in a different node within the distributed computing environment.

7. The method of claim 1, wherein the predefined number of data fragments is six (6) and the predefined number of coding fragments is three (3).

8. The method of claim 1, wherein the creating the predefined number of data fragments further comprises padding each of the predefined number of data fragments with zero sectors such that each of the predefined number of data fragments are a common size.

9. The method of claim 8, wherein each of the data fragments is not committed to storage in the distributed computing environment with the zero sectors.

10. One or more computer storage media having computer-executable instructions embodied thereon, that when executed by a distributed computing environment having a processor and memory, cause the distributed computing environment to perform a method, the method comprising:

monitoring a demand for a data stream stored in the distributed computing environment, wherein the data stream is comprised of at least one sealed extent, the sealed extent is comprised of two or more data blocks and two or more index blocks;

determining the demand for the data stream is above or below a predefined demand threshold;

as a result of the demand for the data stream being above or below the predefined demand threshold, erasure coding the sealed extent such that one or more data fragments are created and one or more coding fragments are created; and

storing each of the one or more data fragments and each of the one or more coding fragments in one or more nodes of the distributed computing environment.

11. The method of claim 10, wherein the demand is monitored by identifying at least one of:

(1) a frequency of requests for the data stream;

(2) a duration from a last request for the data stream;

or

(3) a demand on the one or more nodes within the distributed computing environment.

12. The method of claim 10, wherein monitoring a demand for a data stream is comprised of monitoring demand for one or more extents of the data stream.

13. The method of claim 10, wherein determining the demand for the data stream is above or below the predefined threshold is performed by a cluster manager within the distributed computing environment.

14. The method of claim 10, wherein the method further comprises determining a copy of the sealed extent is to be stored in the distributed computing environment in addition to erasure coding the sealed extent.

15. The method of claim 10, wherein the method further comprises determining a copy of at least one of the data fragments is to be stored in the distributed computing environment in addition to erasure coding the sealed extent.

16. The method of claim 10, wherein each of the one or more data fragments and each of the one or more coding fragments are stored in a different node within a different fault domain within the distributed computing environment.

17. The method of claim 10, wherein the one or more nodes are at least nine (9) different nodes in different fault domains of the distributed computing environment.

18. The method of claim 10 further comprising optimizing the sealed extent, wherein optimizing the sealed extent is comprised of defragmenting the sealed extent.

19. The method of claim 18, wherein defragmenting is comprised of:

grouping together two or more index blocks of the sealed extent; and

grouping together two or more data blocks of the sealed extent.

20. A system for erasure coding an immutable sealed extent in a distributed computing environment, the system comprising:

a cluster manager, the cluster manager performs a method, the method comprising;

(1) identifying, based on statistical information interpreted by the cluster manager, a read-only sealed extent to which erasure coding is to be applied, wherein the read-only sealed extent is comprised of two or more data blocks and two or more index blocks;

(2) optimizing the read-only sealed extent to result in an optimized extent, wherein optimizing is comprised of;

a) grouping the two or more data blocks within the optimized extent together and

b) grouping the two or more index blocks within the optimized extent together; and

(3) erasure coding the optimized extent, wherein erasure coding is comprised of;

a) creating a predefined number of data fragments, wherein the predefined number of data fragments are created by apportioning data represented by the two or more data blocks of the optimized extent into the predefined number of data fragments and

b) creating a predefined number of coding fragments, wherein the coding fragments are created based, at least in part, on the data fragments; and

a plurality of storage nodes that are utilized to store the predefined number of data fragments and the predefined number of coding fragments, wherein the number of the plurality of storage nodes is equal to or greater than the predefined number of data fragments.