RECOVERY AND REPLICATION OF A FLASH MEMORY-BASED OBJECT STORE

• US 20110307736A1
• Filed: 04/11/2011
• Published: 12/15/2011
• 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.
• Granted Patent: US 8,793,531 B2
• Time in Patent Office: Days
• US Class Current: 714/6.2
• 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 for adding a new node to a cluster of nodes, comprising:

at a surviving node, in the 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; and

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,

wherein the surviving node (a) replicates all requests to modify data received by the surviving node and (b) performs a bulk copy operation in parallel.

2. The method of claim 1, wherein the surviving node initiates the replication of requests to modify data received by the surviving node prior to initiating the performance of the bulk copy operation.

3. The method of claim 1, wherein the surviving node performing a bulk copy comprises:

upon the surviving node determining if any cached data is being maintained by the surviving node, the surviving node transferring all cached data prior to transferring any non-cached data during the bulk copy operation.

4. The method of claim 1, wherein the surviving node performing a bulk copy comprises:

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

5. The method of claim 1, further comprising:

at the recovering node, determining whether received object data, which was transferred as part of the bulk copy operation, already exists in the second data store;

upon determining that the received object data already exists in the second object store, deleting the received object data without written the received object data to the second object store; and

upon determining that the received object data does not exist in the second object store, writing the received object data to the second object store.

6. The method of claim 1, further comprising:

at the recovering node, writing all objects within a slab in a single write operation, wherein the slab is a logical object container for storing objects of a particular size.

7. The method of claim 1, further comprising:

at the recovering node, writing all objects to the second data store in a single write operation to the head of a first-in-first-out (FIFO) queue.

8. The method of claim 1, wherein replicating all requests to modify data received by the surviving node comprises:

determining if a particular object is in process of being transferred to the recovering node in the bulk copy operation; and

upon determining that the particular object is in process of being transferred to the recovering node in the bulk copy operation, delaying the replication of a deleted operation involving the particular object, received at the surviving node, to the recovering node.

9. The method of claim 1, wherein performing a bulk copy operation further comprises:

the surviving node performing (a) reading data out of the first data store, (b) formatting the data into network packets, and (c) transmitting the data over a network to the recoveror is a pipelined fashion so that reading, formatting, and transmitting are done concurrently by the surviving node.

10. A method for recovering a node in a distributed object store comprising a plurality of nodes, comprising:

dividing a key space into a number of segments, wherein the key space is a range of values returned from a hash function applied to a set of keys that are used to identify objects stored within the distributed object store, wherein each node of the distributed object store is assigned a set of tokens in the key space;

determining a subset of keys, in a particular segment stored on a first node of the distributed object store, that are to be moved to a second node of the distributed object store; and

transferring any object identified by the subject of keys from the first node to the second node.

11. The method of Clam 10, wherein the steps of dividing, determining, and transferring are performed without interrupting service on any of the nodes of the distributed object store.

12. The method of Clam 10, further comprising:

in response to the first node receiving, from a client, a request that references any key in the subset of keys, the first node responding to the client with a error code and a IP address of the second node.

13. The method of Clam 10, further comprising:

prior to transferring, the first node broadcasting a virtual IP address associated with the subset of keys to all clients of the distributed object store; and

upon completion of transferring, the first node reassigning the virtual IP address to identify the second node.

14. The method of Clam 10, wherein transferring any object identified by the subject of keys from the first node to the second node comprises:

in response to the first node receiving, from a client, a request that references any key in the subset of keys, the first node forwarding the request to the second node; and

in response to the first node receiving, from the second node, a response to the request, the first node forwarding the response to the client.

15. A method for recovering a node in a distributed object store comprising a plurality of nodes, comprising:

dividing a key space into a number of equal size segments, wherein the key space is a range of values returned from a hash function applied to a set of keys that are used to identify objects stored within the distributed object store, and wherein the number of segments is greater than the number of nodes in the plurality of nodes;

assigning, to each node of the distributed object store, a set of tokens in the key space; and

storing, in a set of one or more nodes assigned to a next set of N tokens that satisfy a suitability condition, N copies of objects in each key space segment,

wherein the suitability condition limits common failure domains among the plurality of nodes; and

recovering a failed node, in the plurality of nodes, by retrieving, in parallel, copies of the objects previously stored on the failed node from nodes of the plurality of nodes.

16. The method of claim 15, wherein the set of tokens assigned to each node of the distributed object store is assigned in a random or pseudo-random manner.

17. The method of claim 15, wherein the suitability condition is satisfied if the nodes are on different racks or are located in different data centers.

18. A method for performing replication from one solid state device to another solid state device, comprising:

a first node, maintaining, in volatile memory, a set of write operations to be performed on a second node,

wherein each of the first node and the second node persistently store data using one or more solid state devices;

the first node, examining the set of write operations maintained in volatile memory to identify a set of related write operations which write to contiguous data blocks at the second node; and

at the first node, sending a single write operation to the second node to request the performance of the set of related write operations to the contiguous data blocks of the one or more solid state devices used by the second node to persistently store data.

19. A computer readable storage medium for storing one or more sequences of instructions, which when executed by one or more processors, causes:

at a surviving node, in the 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; and

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,

wherein the surviving node (a) replicates all requests to modify data received by the surviving node and (b) performs a bulk copy operation in parallel.

20. A computer readable storage medium of claim 19, wherein performing a bulk copy operation further comprises:

the surviving node performing (a) reading data out of the first data store, (b) formatting the data into network packets, and (c) transmitting the data over a network to the recoveror is a pipelined fashion so that reading, formatting, and transmitting are done concurrently by the surviving node.