Resilient distributed replicated data storage system

• US 9,223,654 B2
• Filed: 09/10/2014
• Issued: 12/29/2015
• Est. Priority Date: 12/14/2012
• Status: Active Grant

• Current Assignee: DataDirect Networks Incorporated
• Original Assignee: DataDirect Networks Incorporated
• Inventors: Molaro, Donald J., Fellinger, David, Fried-Gintis, Adam, Olster, Dan
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/482,441
• Publication Number:
  US 20140380093A1
• Time in Patent Office: 475 Days
• Field of Search: 707/640, 707/652, 707/690, 707/691, 707/821, 707/827
• 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
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0637 Permissions
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A 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 are calculated. Reassembly instructions are created for the data item. The data objects, parity objects and reassembly instructions are spread across nodes and zones in the storage system according to a policy for the data item. When a zone is inaccessible, a virtual zone is created and used until the intended zone is available. When a read request is received, the data item is prepared from the lowest latency nodes according to the reassembly instructions, and a virtual zone is accessed in place of a real zone when the real zone is inaccessible.

Claims

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 stored thereon 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 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 some of the data objects and groups of some of the parity objects and the reassembly instructions among the nodes included in the storage zones according to a predetermined set of criteria, the storing including

evaluating a latency for each storage zone to which the data item is to be stored,

performing the storing in lowest latency order,

evaluating each storage zone to determine whether the storage zone is accessible,

when one of the storage zones is not accessible, creating a virtual zone in the first zone to store the data objects, parity objects and reassembly instructions intended for the inaccessible storage zone;

receiving a read request for the data item;

obtaining data objects and parity objects to reconstruct the data item from lowest latency nodes, including

when one of the storage zones having storage nodes where the data objects and parity objects to reconstruct the data item are stored are inaccessible, using the virtual zone in place of the inaccessible zone to obtain the data objects and parity objects;

providing the requested data item to a requester.

2. The system of claim 1 wherein the storing further comprises:

checking whether the storage zone corresponding to the virtual zone is accessible

when the storage zone corresponding to the virtual zone remains inaccessible, waiting a system defined amount of time

repeating the checking and the waiting until the storage zone corresponding to the virtual zone becomes accessible

when the storage zone corresponding to the virtual zone is accessible, moving the data objects, parity objects and reassembly instructions from the virtual zone to the intended storage zone.

3. The system of claim 1 wherein the storage devices are selected from the group including hard disk drives and solid state storage devices.

4. 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.

5. The system of claim 1 wherein the partitioning the data item partitions the data object into data items that are equally divided among the storage zones.

6. The system of claim 1 wherein the partitioning the data item partitions the data object into data items that are unequally divided among the storage zones.

7. The system of claim 1 wherein the creating the parity objects creates parity objects wherein some of the parity objects are duplicated among the storage zones.

8. The system of claim 1 wherein the creating the parity objects creates parity objects that are equally divided among the storage zones.

9. The system of claim 1 wherein the creating the parity objects creates parity objects that are unequally divided among the storage zones.

10. The system of claim 1 wherein the obtaining data objects and parity objects to reconstruct the data item from lowest latency nodes further includes

checking whether any storage zones having storage nodes where the data objects and parity objects to reconstruct the data item are stored are inaccessible.

11. The system of claim 1 wherein obtaining data objects and parity objects to reconstruct the data item from lowest latency nodes further includes:

when the lowest latency nodes are not impaired and accessible, constructing the data item from the data objects and parity object 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 from the data objects and parity objects obtained from alternative nodes according to the reassembly instructions

using a 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.

12. The system of claim 1 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 a local parity object according to local reassembly instructions included in the reassembly instructions.

13. 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 stored thereon 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) the data item or a data item reference and (b) a storage criteria;

partitioning the data item into a plurality of data objects, each 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 for the data item among the nodes among the storage zones according to the storage criteria and storing the reassembly instructions among the storage nodes among the storage zones, the storing including

evaluating a latency for each storage zone to which the data item is to be stored,

performing the storing in lowest latency order,

evaluating each storage zone to determine whether the storage zone is accessible,

when one of the storage zones is not accessible, creating a virtual zone in the first zone to store the data objects, parity objects and reassembly instructions intended for the inaccessible storage zone;

receiving a read request for the data item;

obtaining data objects and parity objects to reconstruct the data item from lowest latency nodes, including

when one of the storage zones having storage nodes where the data objects and parity objects to reconstruct the data item are stored are inaccessible, using the virtual zone in place of the inaccessible zone to obtain the data objects and parity objects;

providing the requested data item to a requester.

14. The system of claim 13 wherein the storing further comprises:

checking whether the storage zone corresponding to the virtual zone is accessible

when the storage zone corresponding to the virtual zone remains inaccessible, waiting a system defined amount of time

repeating the checking and the waiting until the storage zone corresponding to the virtual zone becomes accessible

when the storage zone corresponding to the virtual zone is accessible, moving the data objects, parity objects and reassembly instructions from the virtual zone to the intended storage zone.

15. The system of claim 13 wherein the storage devices are selected from the group including hard disk drives and solid state storage devices.

16. The system of claim 13 wherein the storage criteria specify whether the data objects and the parity objects should be equally divided among the storage zones, unequally divided among the storage zones, and duplicated among the storage zones.

17. The system of claim 13 wherein the storage criteria specify redundancy, latency, and/or resiliency characteristics.

18. The system of claim 13 wherein the storage criteria include designated placement for the data objects and the parity objects among the storage zones.

19. The system of claim 13 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.

20. The system of claim 13 wherein obtaining data objects and parity objects to reconstruct the data item from lowest latency nodes includes

checking whether any storage zones having storage nodes where the data objects and parity objects to reconstruct the data item are stored are inaccessible.

21. The system of claim 13 wherein the obtaining further comprises:

when the lowest latency nodes are not impaired and accessible, constructing the data item from the data objects and parity object 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 from the data objects and parity objects obtained from alternative nodes according to the reassembly instructions

using a 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.

22. The system of claim 13 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 a local parity object according to local reassembly instructions included in the reassembly instructions.