Failure recovery using consensus replication in a distributed flash memory system

• US 8,856,593 B2
• Filed: 04/12/2011
• Issued: 10/07/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: Eckhardt, Andrew D., Koster, Michael J.
• Primary Examiner(s): Lottich, Joshua P
• Assistant Examiner(s): Arcos, Jeison C
• Application Number:
  US13/085,441
• Publication Number:
  US 20120011398A1
• Time in Patent Office: 1,274 Days
• Field of Search: 714/20, 710/269, 711/708, 709/217
• US Class Current: 714/20
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups

Abstract

Data replication in a distributed node system including one or more nodes. A consensus protocol for failure recovery is implemented. Data items and information relating to consensus protocol roles of participant nodes are stored in at least some of the plurality of nodes. Logical logs stored in at least some of the plurality of nodes are created. The logical logs contain additional consensus protocol information including container metadata and replicated data.

Claims

1. A method for data replication and failure recovery in a distributed node system including a plurality of nodes, wherein each of the plurality of nodes is configurable for participating in performance of the method, the method comprising:

processing requests using a consensus protocol, including;

storing, in at least some of the plurality of nodes;

data items;

consensus protocol information relating to consensus protocol roles of participant nodes; and

logical logs, the logical logs containing additional consensus protocol information including container metadata and replicated data items, wherein the container metadata includes mapping tables to identify one or more nodes in the plurality of nodes containing a most recent replicated data item; and

after failure of a node in the plurality of nodes, using the stored consensus protocol information and the stored additional consensus protocol information to reconstruct an authoritative state of the failed node in the plurality of nodes.

2. The method of claim 1, wherein the consensus protocol roles include a Proposer and an Acceptor role, and wherein the consensus protocol information relating to consensus protocol roles of participant nodes includes a propose and an accept message.

3. The method of claim 1, wherein the consensus protocol includes a Paxos protocol and each node of the plurality of nodes includes flash memory.

4. The method of claim 1, further comprising storing message numbers during a conflict or a crash recovery in at least some of the plurality of nodes.

5. The method of claim 1, further comprising:

creating logical logs of replicated data of write commands from a consensus protocol state machine in at least some of the plurality of nodes; and

using the logical logs of replicated data as their reference points, wherein consensus protocol instance numbers are implied by ordering in the logical logs of replicated data.

6. The method of claim 1, further comprising using the consensus protocol to distinguish valid data from faulty data, when multiple copies of data are stored in the distributed node system.

7. The method of claim 1, further comprising using the consensus protocol to determine:

A) identity of a write command executed across the distributed node system;

B) statuses of stored replicas including an authoritative or partially authoritative statuses; and

C) validity of the stored replicas.

8. The method of claim 1, further comprising replicating a data container by subdividing the data container into segments and replicating the segments by storing replicas or erasure-coded shards of the segments in a selected set of the plurality of nodes, the selected set being tolerant to certain numbers and patterns of failures.

9. The method of claim 8, further comprising allocating the segment replicas across the selected set using schemes including hashing, chained de-clustering, and dynamic load balancing.

10. The method of claim 8, wherein replicating includes operation transfer and state transfer replications.

11. The method of claim 10, wherein the operation transfer includes duplicating individual operations with a replicated state including a cumulative effect of the individual operations, and wherein state transfer includes copying states.

12. The method of claim 10, further comprising applying the consensus protocol to determine a set of data writes to each of the segments.

13. The method of claim 10, further comprising applying the consensus protocol to selected meta data including determining the authoritative status of a replica and using a different protocol for actual replication of the segments.

14. The method of claim 13, wherein mirroring comprises at least one of:

mirroring based on physical addresses;

or mirroring based on node addresses.

15. The method of claim 1, further comprising providing redundancy by mirroring at least some of the data stored in a node to one or more nodes of the plurality of nodes, wherein mirroring is performed by using hardware or software in at least one of the nodes.

16. The method of claim 1, wherein the storage device includes a write-once storage device, including flash memory, for maintaining multiple versions of a data item.

17. The method of claim 16, wherein the storage device uses mapping tables to identify a location in the storage device of a most recent replicated data item of the multiple versions.

18. The method of claim 16, further comprising making the multiple versions of the data item visible to an application, such that the application can use the multiple versions to maintain a consensus protocol state.

19. The method of claim 18, wherein the application is a key-value store application and the method further comprises implementing the consensus protocol for a distributed key value store with master-slave replications.

20. The method of claim 1, further comprising applying the consensus protocol on a per-fragment basis at each node.

21. The method of claim 1, further comprising applying the consensus protocol to clustered relational databases, including replicating each row of the clustered relational databases as the row is written and applying the consensus protocol to each row write operation.

22. The method of claim 21, further comprising using erasure coding for each row of the clustered relational databases.

23. The method of claim 1, further comprising applying the consensus protocol to cluster configurations, other than a master-slave configuration, including the plurality of nodes in which more than one node are allowed to perform write operations.

24. A system for data replication and failure recovery in a distributed node system, the distributed node system comprising:

a plurality of nodes;

each node including;

one or more processors; and

memory having instructions for execution by the one or more processors, the instructions for;

processing requests using a consensus protocol, including;

storing, in at least some of the plurality of nodes;

data items;

consensus protocol information relating to consensus protocol roles of participant; and

logical logs, the logical logs containing additional consensus protocol information including container metadata and replicated data items, wherein the container metadata includes mapping tables to identify one or more nodes in the plurality of nodes containing a most recent replicated data item; and

after failure of a node in the plurality of nodes, using the stored consensus protocol information and the stored additional consensus protocol information to reconstruct an authoritative state of the failed node in the plurality of nodes.

25. The system of claim 24, wherein the consensus protocol includes a Paxos protocol, the consensus protocol roles include a Proposer and an Acceptor role, the consensus protocol information relating to consensus protocol roles of participant nodes includes a propose and an accept message, and each node of the plurality of nodes includes flash memory.

26. The system of claim 24, wherein implementing the consensus protocol for failure recovery further comprises storing message numbers during a conflict or a crash recovery in at least some of the plurality of nodes.

27. The system of claim 24, wherein implementing the consensus protocol for failure recovery further comprises:

creating logical logs of replicated data of write commands from a consensus protocol state machine in at least some of the plurality of nodes; and

using the logical logs of replicated data as their reference points, wherein consensus protocol instance numbers are implied by ordering in the logical logs of replicated data.

28. The system of claim 24, wherein implementing the consensus protocol for failure recovery further comprises:

using the consensus protocol to determine;

A) identity of a write command executed across the distributed node system and the;

B) statuses of stored replicas including an authoritative or partially authoritative statuses; and

C) validity of the stored replicas.

29. The system of claim 24, wherein the memory includes a write-once storage device, including flash memory, configured to maintain multiple versions of a data item.

30. The system of claim 29, wherein the write-once storage device is configured to use mapping tables to identify a location in the storage device of a most recent replicated data item of the multiple versions.

31. The system of claim 30, wherein the processor is configured to make the multiple versions of the data item visible to an application, such that the application can use the multiple versions to maintain a consensus protocol state.

32. The system of claim 24, wherein the processor is further configured to apply the consensus protocol on a per-fragment basis at each node.

33. The system of claim 24, wherein the processor is further configured to apply the consensus protocol to clustered relational databases, by replicating each row of the clustered relational databases as the row is written and applying the consensus protocol to each row write operation.

34. The system of claim 33, wherein the processor is further configured to use erasure coding for each row of the clustered relational databases.

35. The system of claim 33, wherein the processor is further configured to apply the consensus protocol to cluster configurations, other than a master-slave configuration, including the plurality of nodes in which more than one node are allowed to perform write operations.