Efficiency for erasure encoding

• US 9,116,833 B1
• Filed: 12/18/2014
• Issued: 08/25/2015
• Est. Priority Date: 12/18/2014
• Status: Active Grant

• Current Assignee: Rubrik, Inc.
• Original Assignee: Igneous Systems, Inc. (Rubrik, Inc.)
• Inventors: Rakitzis, Triantaphyllos Byron, Hughes, Jeffrey Douglas
• Primary Examiner(s): Rizk, Sam
• Application Number:
  US14/576,095
• Time in Patent Office: 250 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

Embodiments are directed towards efficient erasure coding for storage systems. A smallest integer in a set may be determined based on a number of storage devices in the storage system such that the determined integer is greater or equal to the number of storage devices. The smallest integer in the set may be determined from the set {2^N−1} where N is an integer based on the number of storage devices. A matrix may be generated based on a number of columns equal to the determined integer and a number of rows equal to the number of columns plus a number of global repair symbol devices and plus a number of virtual repair symbol devices. Each virtual repair symbol device enables an additional of level of protection against failures in the storage system.

Claims

1. A method for erasure coding data using a network computer that performs actions, comprising:

determining a smallest integer in a set based on a number of storage devices in a storage system, wherein the determined integer is greater or equal to the number of storage devices;

determining a number of columns that is equal to a value of the determined integer;

determining a number of rows that is equal to a value of the number of columns plus a number of global repair symbol devices and plus a number of virtual repair symbol devices in the storage system;

generating a generator matrix in two dimensions based on the number of columns and the number of rows, wherein one or more rows of the generator matrix corresponds to one or more virtual repair symbol devices;

generating the contents of the one or more virtual repair symbol devices based on two or more other repair symbol devices;

encoding data that is provided for storage using at least the contents of the one or more virtual repair symbol devices and the generator matrix; and

storing the encoded data in the storage system without the contents of the one or more virtual repair symbol devices.

2. The method of claim 1, wherein determining the smallest integer in the set, further comprises, determining the smallest integer in the set {2^N−

1} where N is an integer based on the number of storage devices.

3. The method of claim 1, wherein generating the generator matrix further comprises, generating a Vandermonde matrix in Galois Field 256 with dimensions based on the number of columns and the number of rows.

4. The method of claim 1, further comprising, determining contents of each virtual repair symbol device based on one or more local repair symbol devices.

5. The method of claim 4, wherein determining contents further comprises, XOR'"'"'ing the content of the one or more local repair symbol devices to compute the contents of each virtual repair device.

6. The method of claim 1, wherein each virtual repair symbol device enables at least one additional of level of protection against physical storage device failures.

7. The method of claim 1, wherein generating the generator matrix further comprises, when the number of columns for the generator matrix exceeds the number of storage devices, including the additional columns in the generator matrix.

8. The method of claim 1, wherein encoding the provided data, further comprises:

when a data word vector is provided for storage, generating an encoded vector using the generator matrix; and

distributing the encoded vector to the storage devices, the local repair symbol devices, and the global repair symbol devices for storage.

9. A system for erasure coding data, comprising:

a network computer comprising;

a transceiver that communicates over a network;

a memory that stores at least instructions; and

a processor device that executes instructions that enable actions, including;

determining a smallest integer in a set based on a number of storage devices in a storage system, wherein the determined integer is greater or equal to the number of storage devices;

determining a number of columns that is equal to a value of the determined integer;

determining a number of rows that is equal to a value of the number of columns plus a number of global repair symbol devices and plus a number of virtual repair symbol devices in the storage system;

generating a generator matrix in two dimensions based on the number of columns and the number of rows, wherein one or more rows of the generator matrix corresponds to one or more virtual repair symbol devices;

generating the contents of the one or more virtual repair symbol devices based on two or more other repair symbol devices;

encoding data that is provided for storage using at least the contents of the one or more virtual repair symbol devices and the generator matrix; and

storing the encoded data in the storage system without the contents of the one or more virtual repair symbol devices; and

a client computer comprising;

a transceiver that communicates over a network;

a memory that stores at least instructions; and

a processor device that executes instructions that enable actions, including;

providing the data to the network computer.

10. The system of claim 9, wherein determining the smallest integer in the set, further comprises, determining the smallest integer in the set {2^N−

1} where N is an integer based on the number of storage devices.

11. The system of claim 9, wherein generating the generator matrix further comprises, generating a Vandermonde matrix in Galois Field 256 with dimensions based on the number of columns and the number of rows.

12. The system of claim 9, wherein the network computer processor device enables actions, further comprising, determining contents of each virtual repair symbol device based on one or more local repair symbol devices.

13. The system of claim 12, wherein determining contents further comprises, XOR'"'"'ing the content of the one or more local repair symbol devices to compute the contents of each virtual repair device.

14. The system of claim 9, wherein each virtual repair symbol device enables at least one additional of level of protection against physical storage device failures.

15. The system of claim 9, wherein generating the generator matrix further comprises, when the number of columns for the generator matrix exceeds the number of storage devices, including the additional columns in the generator matrix.

16. The system of claim 9, wherein encoding the provided data, further comprises:

when a data word vector is provided for storage, generating an encoded vector using the generator matrix; and

distributing the encoded vector to the storage devices, the local repair symbol devices, and the global repair symbol devices for storage.

17. A processor readable non-transitory storage media that includes instructions for erasure coding data, wherein execution of the instructions by a processor device enables actions, comprising:

determining a smallest integer in a set based on a number of storage devices in a storage system, wherein the determined integer is greater or equal to the number of storage devices;

determining a number of columns that is equal to a value of the determined integer;

determining a number of rows that is equal to a value of the number of columns plus a number of global repair symbol devices and plus a number of virtual repair symbol devices in the storage system;

generating a generator matrix in two dimensions based on the number of columns and the number of rows, wherein one or more rows of the generator matrix corresponds to one or more virtual repair symbol devices;

generating the contents of the one or more virtual repair symbol devices based on two or more other repair symbol devices;

encoding data that is provided for storage using at least the contents of the one or more virtual repair symbol devices and the generator matrix; and

storing the encoded data in the storage system without the contents of the one or more virtual repair symbol devices.

18. The media of claim 17, wherein determining the smallest integer in the set, further comprises, determining the smallest integer in the set {2^N−

1} where N is an integer based on the number of storage devices.

19. The media of claim 17, wherein generating the generator matrix further comprises, generating a Vandermonde matrix in Galois Field 256 with dimensions based on the number of columns and the number of rows.

20. The media of claim 17, further comprising, determining contents of each virtual repair symbol device based on one or more local repair symbol devices.

21. The media of claim 20, wherein determining contents further comprises, XOR'"'"'ing the content of the one or more local repair symbol devices to compute the contents of each virtual repair device.

22. The media of claim 17, wherein each virtual repair symbol device enables at least one additional of level of protection against physical storage device failures.

23. The media of claim 17, wherein generating the generator matrix further comprises, when the number of columns for the generator matrix exceeds the number of storage devices, including the additional columns in the generator matrix.

24. A network computer that performs erasure coding data, comprising:

a transceiver that communicates over a network;

a memory that stores at least instructions; and

a processor device that executes instructions that enable actions, including;

determining a smallest integer in a set based on a number of storage devices in a storage system, wherein the determined integer is greater or equal to the number of storage devices;

determining a number of columns that is equal to a value of the determined integer;

determining a number of rows that is equal to a value of the number of columns plus a number of global repair symbol devices and plus a number of virtual repair symbol devices in the storage system;

generating a generator matrix in two dimensions based on the number of columns and the number of rows, wherein one or more rows of the generator matrix corresponds to one or more virtual repair symbol devices;

generating the contents of the one or more virtual repair symbol devices based on two or more other repair symbol devices;

encoding data that is provided for storage using at least the contents of the one or more virtual repair symbol devices and the generator matrix; and

storing the encoded data in the storage system without the contents of the one or more virtual repair symbol devices.

25. The network computer of claim 24, wherein determining the smallest integer in the set, further comprises, determining the smallest integer in the set {2^N−

1} where N is an integer based on the number of storage devices.

26. The network computer of claim 24, wherein generating the generator matrix further comprises, generating a Vandermonde matrix in Galois Field 256 with dimensions based on the number of columns and the number of rows.

27. The network computer of claim 24, wherein the processor device enables actions, further comprising, determining contents of each virtual repair symbol device based on one or more local repair symbol devices.

28. The network computer of claim 27, wherein determining contents further comprises, XOR'"'"'ing the content of the one or more local repair symbol devices to compute the contents of each virtual repair device.

29. The network computer of claim 24, wherein each virtual repair symbol device enables at least one additional of level of protection against physical storage device failures.

30. The network computer of claim 24, wherein generating the generator matrix further comprises, when the number of columns for the generator matrix exceeds the number of storage devices, including the additional columns in the generator matrix.