Recovery and replication of a flash memory-based object store

• US 8,793,531 B2
• Filed: 04/11/2011
• Issued: 07/29/2014
• Est. Priority Date: 04/12/2010
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: George, Johann, O'Krafka, Brian W.
• Primary Examiner(s): BUTLER, SARAI E
• Application Number:
  US13/084,511
• Publication Number:
  US 20110307736A1
• Time in Patent Office: 1,205 Days
• Field of Search: 714/6.3, 714/2, 714/4.1, 714/25, 714/47.1
• US Class Current: 714/6.3
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 11/2071 using a plurality of controllers
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24569 Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

Approaches for recovering nodes and adding new nodes to object stores maintained on one or more solid state devices. At a surviving node, in a cluster of nodes, replicating, to a recovering node in the cluster of nodes, all requests to modify data stored in a first data store thereon that are received by the surviving node. The surviving node performing a bulk copy operation to copy data, stored in the first data store, to a second data store maintained on the recovering node. The surviving node (a) replicates all requests to modify data received by the surviving node and (b) performs a bulk copy operation in parallel.

Claims

1. A method performed at cluster of nodes that includes a first node and a second node, the first node having experienced a failure and the second node including a replica of a state of the first node prior to the failure, the method comprising:

at the second node;

replicating to the first node a plurality of requests to modify data stored in a first data store of the second node; and

performing, in parallel with the replication of the plurality of requests to modify data stored in the first data store, a bulk copy operation to copy data stored in the first data store to a second data store of the first node;

wherein;

the second data store is partitioned into a plurality of logical object containers, each logical object container being configured to store a group of objects, each object in the group of objects being within a corresponding predefined size range; and

said replicating and bulk copy operations both include writing respective objects to respective logical object containers in the plurality of logical object containers in accordance with the size of each respective object.

2. The method of claim 1, wherein, for a respective logical object container of the plurality of logical object containers, each object in the group of objects is larger than a first number of bytes and no greater than a second number of bytes, the second number of bytes being equal to a base value of bytes times a respective power of two, the respective power being unique to the respective logical object container amongst the plurality of logical object containers.

3. The method of claim 1, wherein:

performing the bulk copy operation includes, at the second node, extracting, from the first data store, a plurality of objects using a single read operation, wherein the plurality of objects includes objects to be stored in two or more logical object containers of the plurality of logical object containers; and

the method further includes, at the first node;

receiving the plurality of objects; and

writing in a single write command, to a single respective logical object container of the plurality of logical object containers, data comprising a subset of the plurality of objects, wherein the subset of the plurality of objects is less than a full set of the plurality of objects, and the subset of the plurality of objects includes each object of the plurality of objects to be stored in the single respective logical object container of the plurality of logical object containers.

4. The method of claim 3, wherein writing the data in the single write command includes writing a sufficient amount of data to fill the respective logical object container.

5. The method of claim 4, wherein writing the sufficient amount of data includes writing unrequested data to fill the respective logical object container.

6. The method of claim 1, wherein the failure comprises a partial failure and performing the bulk copy operation includes:

at the second node;

extracting, from the first data store of the second node, a plurality of objects using a single read operation;

copying, to the first node, the plurality of objects;

at the first node;

receiving the plurality of objects;

determining if a respective object of the plurality of objects corresponds to an object already stored on the first node;

in accordance with a determination that the respective object does not corresponds to an object already stored on the first node, writing the respective object to the second data store; and

in accordance with a determination that the respective object corresponds to an object already stored on the first node, forgoing writing the respective object to the second data store.

7. The method of claim 6, wherein determining if a respective object of the plurality of objects corresponds to an object already stored on the first node further includes:

accessing an in-memory hash table storing hash keys for objects stored in the second data store of the first node; and

determining if the respective object corresponds to a hash key stored in the in-memory hash table.

8. The method of claim 6, wherein copying, to the first node, the plurality of objects, includes:

reading first data from the first data store, the first data comprising a first subset of the plurality of objects;

formatting the first data into a plurality of network packets;

transmitting the first data over a network to the first node; and

concurrently with one or more of the formatting and the transmitting operations, reading second data from the first data store, the second data comprising a second subset of the plurality of objects;

wherein the operations of reading, formatting, and transmitting are performed in a pipelined fashion.

9. The method of claim 6, wherein writing the respective object to the second data store includes:

writing the respective object to a cache with a plurality of other objects that do not correspond to an object already stored on the first node; and

writing to the second data store, in a single write operation, the respective object together with the plurality of other objects from the cache that do not correspond to an object already stored on the first node.

10. The method of claim 9, wherein the cache is a first-in-first-out (FIFO) cache.

11. The method of claim 1, wherein the plurality of requests includes a request to delete a respective object;

and

the method further includes;

determining whether the respective object is currently being transferred to the second node as part of the bulk copy operation; and

delaying replication of the request to delete the respective object until completion of the transfer of the respective object to the second node.

12. A non-transitory computer readable storage medium storing instructions for recovering a first node of a cluster of nodes that includes the first node and a second node, the first node having experienced a failure and the second node including a replica of a state of the first node prior to the failure, the instructions when executed by one or more processors causing the cluster of nodes to:

at the second node;

replicate to the first node a plurality of requests to modify data stored in a first data store of the second node; and

perform, in parallel with the replication of the plurality of requests to modify data stored in the first data store, a bulk copy operation to copy data stored in the first data store to a second data store of the first node;

wherein;

the second data store is partitioned into a plurality of logical object containers, each logical object container being configured to store a group of objects, each object in the group of objects being within a corresponding predefined size range; and

said replicating and bulk copy operations both include writing respective objects to respective logical object containers in the plurality of logical object containers in accordance with the size of each respective object.

13. The non-transitory computer readable storage medium of claim 12, wherein, for a respective logical object container of the plurality of logical object containers, each object in the group of objects is larger than a first number of bytes and no greater than a second number of bytes, the second number of bytes being equal to a base value of bytes times a respective power of two, the respective power being unique to the respective logical object container amongst the plurality of logical object containers.

14. The non-transitory computer readable storage medium of claim 12, wherein:

performing the bulk copy operation includes, at the second node, extracting, from the first data store, a plurality of objects using a single read operation, wherein the plurality of objects includes objects to be stored in two or more logical object containers of the plurality of logical object containers; and

the instructions further cause the one or more processors to, at the first node;

receiving the plurality of objects; and

writing in a single write command, to a single respective logical object container of the plurality of logical object containers, data comprising a subset of the plurality of objects, wherein the subset of the plurality of objects is less than a full set of the plurality of objects, and the subset of the plurality of objects includes each object of the plurality of objects to be stored in the single respective logical object container of the plurality of logical object containers.

15. The non-transitory computer readable storage medium of claim 14, wherein writing the data in the single write command includes writing a sufficient amount of data to fill the respective logical object container.

16. The non-transitory computer readable storage medium of claim 12, wherein the failure comprises a partial failure and performing the bulk copy operation includes:

at the second node;

extracting, from the first data store of the second node, a plurality of objects using a single read operation;

copying, to the first node, the plurality of objects;

at the first node;

receiving the plurality of objects;

determining if a respective object of the plurality of objects corresponds to an object already stored on the first node;

in accordance with a determination that the respective object does not corresponds to an object already stored on the first node, writing the respective object to the second data store; and

in accordance with a determination that the respective object corresponds to an object already stored on the first node, forgoing writing the respective object to the second data store.

17. The non-transitory computer readable storage medium of claim 16, wherein determining if a respective object of the plurality of objects corresponds to an object already stored on the first node further includes:

accessing an in-memory hash table storing hash keys for objects stored in the second data store of the first node; and

determining if the respective object corresponds to a hash key stored in the in-memory hash table.

18. The non-transitory computer readable storage medium of claim 16, wherein copying, to the first node, the plurality of objects, includes:

reading first data from the first data store, the first data comprising a first subset of the plurality of objects;

formatting the first data into a plurality of network packets;

transmitting the first data over a network to the first node; and

concurrently with one or more of the formatting and the transmitting operations, reading second data from the first data store, the second data comprising a second subset of the plurality of objects;

wherein the operations of reading, formatting, and transmitting are performed in a pipelined fashion.

19. The non-transitory computer readable storage medium of claim 16, wherein writing the respective object to the second data store includes:

writing the respective object to a cache with a plurality of other objects that do not correspond to an object already stored on the first node; and

writing to the second data store, in a single write operation, the respective object together with the plurality of other objects from the cache that do not correspond to an object already stored on the first node.

20. The non-transitory computer readable storage medium of claim 12, wherein the plurality of requests includes a request to delete a respective object;

and

the instructions further include instructions that cause the one or more processors to;

determine whether the respective object is currently being transferred to the second node as part of the bulk copy operation; and

delay replication of the request to delete the respective object until completion of the transfer of the respective object to the second node.