FAILURE RECOVERY USING CONSENSUS REPLICATION IN A DISTRIBUTED FLASH MEMORY SYSTEM

• US 20120011398A1
• Filed: 04/12/2011
• Published: 01/12/2012
• 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.
• Granted Patent: US 8,856,593 B2
• Time in Patent Office: Days
• US Class Current: 714/15
• 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

22-1. 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 nodes are allowed to perform write operations.

23. A system for data replication, the system comprising:

a plurality of nodes;

each node including;

one or more processors; and

memory having instructions encoded therein, the instructions when executed by the one or more processors implementing a consensus protocol for failure recovery by

storing data in the memory of at least some of the nodes of the plurality of nodes;

storing information relating to consensus protocol roles of participant nodes in at least some of the plurality of nodes; and

creating logical logs stored in at least some of the plurality of nodes, the logical logs containing additional consensus protocol information including container metadata and replicated data.

24. The system of claim 23, wherein the consensus protocol includes a Paxos protocol, the consensus protocol roles include a Proposer and an Acceptor role, 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.

25. The system of claim 23, 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.

26. The system of claim 23, 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.

27. The system of claim 23, 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.

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

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

30. The system of claim 29, 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.

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

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

33. The system of claim 32, wherein the processor is further configured to use erasure coding for each row of the rational database.

34. The system of claim 32, 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.