Failure resilient distributed replicated data storage system
A failure resilient distributed replicated data storage system is described herein. The storage system includes zones that are independent, and autonomous from each other. The zones include nodes that are independent and autonomous. The nodes include storage devices. When a data item is stored, it is partitioned into a plurality of data objects and a plurality of parity objects calculated. Reassembly instructions are created for the data item. The data objects and parity objects are spread across all nodes and zones in the storage system. Reassembly instructions are also spread across the zones. When a read request is received, the data item is prepared from the lowest latency nodes according to the reassembly instructions. This provides for data resiliency while keeping the amount of storage space required relatively low.
1. A system comprising:
a plurality of storage zones, each storage zone comprising a plurality of nodes wherein each node comprises a plurality of storage devices and a controller, the controller including a processor and memory
a first node of a plurality of nodes included in a first zone of the plurality of zones, the first node having instructions which when executed cause a first processor included in a first controller in the first node to perform actions including:
receiving a storage request from a client of the system to store a data item
partitioning the data item into a plurality of data objects, each data object including a storage policy identifier and a data portion
creating a plurality of parity objects for the data item
creating reassembly instructions for the data item
storing groups of at least three of the data objects and groups of at least two of the parity objects and the reassembly instructions among the nodes included in the storage zones according to a predetermined set of criteria
creating at least one local parity object for a first zone based on the received group of parity objects and the received group of data objects
wherein creating reassembly instructions for the data item includes creating local reassembly instructions, the local reassembly instructions including reference to the local parity object
wherein each of the data objects are included in at least one of the groups of data objects, but each data object is included in less than all the groups of data objects
wherein each of the parity objects are included in at least one of the groups of parity objects, but each parity object is included in less than all the groups of parity objects
wherein some of the parity objects are duplicated among the storage zones
wherein the predefined set of criteria ensures that the data item can be reconstructed by accessing a subset of the plurality of data objects and the plurality of the parity objects.
2. The system of claim 1 wherein the storage devices are selected from the group including hard disk drives and solid state storage devices.
3. The system of claim 1 wherein the partitioning the data item partitions the data item into data objects wherein some of the data objects are duplicated among the storage zones.
4. The system of claim 1 wherein the partitioning the data item partitions the data item into data objects that are equally distributed among the storage zones.
5. The system of claim 1 wherein the partitioning the data item partitions the data item into data objects that are unequally distributed among the storage zones.
6. The system of claim 1 wherein the creating the parity objects creates parity objects that are equally distributed among the storage zones.
7. The system of claim 1 wherein the creating the parity objects creates parity objects that are unequally distributed among the storage zones.
8. The system of claim 1 wherein the partitioning the data item into a plurality of data objects and the creating a plurality of parity objects are achieved using a parity generating erasure coding scheme.
9. The system of claim 8 wherein the parity generating erasure coding scheme is Reed-Solomon encoding.
10. The system of claim 1 wherein the creating a local parity object is achieved using a parity generating erasure coding scheme.
11. The system of claim 10 wherein the parity generating erasure coding scheme is Reed-Solomon encoding.
12. The system of claim 1 wherein the first node has further instructions which when executed cause the first processor to perform further actions including:
receiving a read request for the data item
attempting to obtain data objects and parity objects to reconstruct the data item from lowest latency nodes
when the lowest latency nodes are not impaired and accessible, constructing the data item from the data objects and parity objects at the lowest latency nodes according to the reassembly instructions
when one of the lowest latency nodes is either impaired or not accessible, constructing the data item from the data objects and parity objects obtained from alternative nodes according to the reassembly instructions
using the local parity object to allow for recreation of an inaccessible or corrupted one of the parity objects in the group of parity objects or one of the data objects in the group of data objects
providing the requested data item to a requester.
13. The system of claim 12 wherein when one of the lowest latency nodes is either impaired or not accessible, reconstituting the node that is either impaired or not accessible using the local parity object according to the local reassembly instructions included in the reassembly instructions.
14. A system comprising:
a plurality of storage zones, each storage zone comprising a plurality of storage nodes wherein each storage node comprises a plurality of storage devices and a controller, the controller including a processor and memory
a first node of a plurality of nodes included in a first zone of the plurality of zones, the first node having instructions which when executed cause a first processor included in a first controller in the first node to perform actions including:
receiving a storage request from a client of the system to store a data item, the storage request include (a) the data item or a data item reference and (b) a storage criteria
partitioning the data item into a plurality of data objects, each data object including a storage policy identifier and a data portion according to the storage criteria
creating a plurality of parity objects for the data item according to the storage criteria
creating reassembly instructions for the data item according to the storage criteria
storing the data objects and the parity objects among the nodes among the storage zones according to the storage criteria
storing the reassembly instructions among the storage nodes among the storage zones
creating at least one local parity object for a first zone based on the parity objects and the data objects stored in the first zone
wherein creating reassembly instructions for the data item includes creating local reassembly instructions, the local reassembly instructions including reference to the local parity object
wherein each of the data objects are included in at least one of the plurality of storage zones, but each data object is included in less than all the plurality of storage zones
wherein each of the parity objects are included in at least one of the plurality of storage zones but each parity object is included in less than all the plurality of storage zones
wherein some of the parity objects are duplicated among the storage zones
wherein the reassembly instructions specify how the data item can be reconstructed from a subset of the plurality of data objects and the plurality of parity objects.
15. The system of claim 14 wherein the storage devices are selected from the group including hard disk drives and solid state storage devices.
16. The system of claim 14 wherein the storage criteria specify whether the data objects should be equally distributed among the storage zones, unequally divided among the storage zones, and duplicated among the storage zones.
17. The system of claim 14 wherein the storage criteria specify whether the parity objects should be equally distributed among the storage zones, unequally divided among the storage zones, and duplicated among the storage zones.
18. The system of claim 14 wherein the storage criteria specify redundancy, latency, and/or resiliency characteristics.
19. The system of claim 14 wherein the storage criteria include designated placement for the data objects and the parity objects among the storage zones.
20. The system of claim 14 wherein the storage criteria are designations of redundancy, latency, and/or resiliency characteristics that are processed to determine the distribution of the data objects and the parity objects among the storage zones.
21. The system of claim 14 wherein the creating a local parity object is achieved using a parity generating erasure coding scheme.
22. The system of claim 21 wherein the parity generating erasure coding scheme is Reed-Solomon encoding.
23. The system of claim 14 wherein the first node has further instructions which when executed cause the first processor to perform further actions including:
receiving a read request for the data item
attempting to obtain data objects and parity objects to reconstruct the data item from lowest latency nodes
when the lowest latency nodes are not impaired and accessible, constructing the data item from the data objects and parity objects at the lowest latency nodes according to the reassembly instructions
when one of the lowest latency nodes is either impaired or not accessible, constructing the data item from the data objects and parity objects obtained from alternative nodes according to the reassembly instructions
using the local parity object to allow for recreation of an inaccessible or corrupted one of the parity objects in the parity objects or one of the data objects
providing the requested data item to a requester.
24. The system of claim 23 wherein when one of the lowest latency nodes is either impaired or not accessible, reconstituting the node that is either impaired or not accessible using the local parity object according to the local reassembly instructions included in the reassembly instructions.