Asymmetric distributed data storage system
Asymmetric distributed replicated data storage systems and methods are described herein. The storage system includes zones that are independent, and autonomous. 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 using erasure coding. The data objects and parity objects are spread across all nodes and zones in the storage system asymmetrically such that a first zone includes all of the data objects and no parity objects while the remaining zones include subsets of the data objects and all of the parity objects. The systems and methods provide for data resiliency while keeping the amount of storage space required relatively low.
1. A data storage 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, the storage request including a data item reference and storage criteria
partitioning the data item into a plurality of data objects according to distribution instructions included in the storage criteria, wherein each data object includes a storage policy identifier and a data portion and the storage policy identifier defines replication of the data object among the storage zones of the data storage system
creating a plurality of parity objects according to the distribution instructions included in the storage criteria
storing all of the data objects in the first storage zone
storing a first subset of the data objects and all of the parity objects in a second storage zone
storing a second subset of the data objects and all of the parity objects in a third storage zone
wherein the second subset of the data objects and the first subset of the data objects have partly different constituent data objects according to the storage criteria
maintaining a latency map that includes a time for each node to reach other nodes in the storage zones.
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 into a plurality of data objects and the creating a plurality of parity objects are achieved using a parity generating erasure coding scheme.
4. The system of claim 3 wherein the parity generating erasure coding scheme is Reed-Solomon encoding.
5. The system of claim 1 wherein the plurality of parity objects is two and the plurality of data objects is five.
6. The system of claim 5 wherein the first subset and second subset of the data objects each include four of the five data objects.
7. The system of claim 1 wherein the first storage zone, the second storage zone and the third storage zone are geographically separate.
8. 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
identifying lowest latency nodes where data objects for the data item are stored by referring to the latency map
attempting to obtain data objects and parity objects to reconstruct the data item from the 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
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 in part from at least one alternative node, wherein alternative nodes are nodes that are not lowest latency, are not impaired and are available
providing the requested data item to a requester.
9. A method comprising:
receiving a storage request to store a data item, the storage request including a data item reference and storage criteria
partitioning the data item into a plurality of data objects and creating a plurality of parity objects using parity generating erasure coding, wherein the plurality of data objects is five and the plurality of parity objects is two and wherein each data object includes a storage policy identifier and a data portion
storing all of the data objects in a first storage zone
storing a first subset of the data objects and all of the parity objects in a second storage zone
storing a second subset of the data objects and all of the parity objects in a third storage zone
wherein the second subset of the data objects and the first subset of the data objects have partly different constituent data objects according to the storage criteria
maintaining a latency map that includes a time to reach other nodes from each node in the storage zones.
10. The method of claim 9 wherein the first storage zone and second storage zone include a plurality of storage devices, the storage devices selected from the group including hard disk drives and solid state storage devices.
11. The method of claim 9 wherein the first storage zone, the second storage zone and the third storage zone are geographically separate.
12. The method of claim 9 wherein the parity generating erasure coding is Reed-Solomon encoding.
13. The method of claim 9 wherein the first subset and second subset of data objects each include four of the five data objects.
14. The method of claim 9 further comprising:
receiving a read request for the data item
identifying lowest latency nodes where data objects and parity objects for the data item are stored in the first storage zone, the second storage zone and the third storage zone by referring to the latency map
attempting to obtain data objects and parity objects to reconstruct the data item from the 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
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 in part from at least one alternative node, wherein alternative nodes are nodes that are not lowest latency, are not impaired and are available
providing the requested data item to a requester.
15. A data storage 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, the storage request including a data item reference and storage criteria
partitioning the data item into a plurality of data objects according to distribution instructions included in the storage criteria and creating a plurality of parity objects according to distribution instructions included in the storage criteria, wherein the plurality of parity objects is two and the plurality of data objects is five, wherein each data object includes a storage policy identifier and a data portion
storing all of the data objects in the first storage zone
storing subsets of four of the five data objects and all of the parity objects in the other storage zones wherein the subsets of the data objects have differing constituent data objects among the storage zones according to the storage policy identifiers in the data objects
maintaining a latency map that includes a time to reach other nodes from each node in the storage zones.
16. The system of claim 15 wherein the storage devices are selected from the group including hard disk drives and solid state storage devices.
17. The system of claim 15 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.
18. The system of claim 15 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 among the storage zones
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
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 in part from at least one alternative node, wherein alternative nodes are nodes that are not lowest latency, are not impaired and are available
providing the requested data item to a requester.
19. A method comprising:
receiving a storage request to store a data item, the storage request including a data item reference and storage criteria
partitioning the data item into a plurality of data objects and creating a plurality of parity objects, wherein each data object includes a storage policy identifier specified in the storage criteria and a data portion and wherein the plurality of parity objects is two and the plurality of data objects is five
storing all of the data objects in the first storage zone of a plurality of storage zones
storing subsets of four of the five data objects and all of the parity objects in at least some the other storage zones, wherein each of the subsets of the data objects have partly differing constituent data objects from other subsets according to the storage criteria
maintaining a latency map that includes a time to reach other nodes from each node in the storage zones.
20. The system of claim 19 wherein the storage zones each include a plurality of storage devices, the storage devices selected from the group including hard disk drives and solid state storage devices.
21. The system of claim 19 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.
22. The method of claim 19 further comprising:
receiving a read request for the data item
identifying lowest latency nodes where data objects and parity objects for the data item are stored by referring to the latency map
attempting to obtain data objects and parity objects to reconstruct the data item from the lowest latency nodes among the storage zones
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
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 in part from at least one alternative node, wherein alternative nodes are nodes that are not lowest latency, are not impaired and are available
providing the requested data item to a requester.