Methods and systems for replicated state machine transition
View Patent ↗The present disclosure presents methods and architectures that allow non-deterministic concurrent executions that can potentially interleave with other executions and replays in a SMR system. The current disclosure further discloses architectures and methods that executes, validates (replay) then merges transactions without the need to first order the transactions therefore achieves higher throughput. Another aspect of the invention involves organizing SM state as a Multi-Version Concurrency Control (MVCC) database with all concurrent execution/replay generating operation logs on each resource. This disclosure additionally outlines methods for integrating client nodes with State Machine Replication (SMR) systems. This disclosure further provides improved Directed Acyclic Graph (DAG) based consensus protocols.
1 . A computer-implemented method, performed by a distributed network system comprising a plurality of computing nodes, comprising:
Maintaining, by at least one computing node, a state repository that stores at least N previous versions of system states, where N>1, to facilitate recovery from node failure and maintain consistency among the plurality of computing nodes;
Receiving, at a first computing node, a client deployment request;
Generating, by the first computing node-based on the client deployment request, a first replication message;
Transmitting, by the first computing node, the first replication message to one or more other computing nodes of the distributed network system;
Receiving, at the first computing node, a second replication message from a second computing node and executing the second replication message;
periodically selecting, by the first computing node or the second computing node, a list of replication messages according to a predefined consensus protocol;
deterministically selecting, by the first computing node, a subset of transactions from the list of replication messages according to a predefined conflict resolution protocol; and
committing, by the first computing node, the subset of transactions to the state repository.
2 . The method of claim 1 , wherein the state repository is further configured to employ a state expiration policy to discard system state older than the last N versions.
3 . The method of claim 1 , wherein the state repository is implemented as multi-version database.
4 . The method of claim 1 , wherein the predefined consensus protocol is a Byzantine fault-tolerant protocol.
5 . The method of claim 1 wherein the first replication message includes a state transition log that records changes to a system state.
6 . The method of claim 1 , wherein the first replication message includes a snapshot comprising incremental transition information relative to a previous checkpoint.
7 . The method of claim 3 , wherein each state transition is executed in a multi-version concurrency control (MVCC) enabled database with snapshot isolation.
8 . The method of claim 1 , wherein generating the first replication message and replaying the second replication message are performed concurrently by the first computing node.
9 . A computer-implemented method for enabling a client application to interact with a distributed network system, comprising:
receiving, by a client-side computing device, a user transaction request to interact with the distributed network system, the user transaction request comprising user transaction input;
maintaining, by the client-side computing device, a local state repository, the local state repository being synchronized with at least a portion of the distributed network repository maintained by the distributed network system;
processing the user transaction input based on the local state repository;
generating, by the client-side computing device, a replay log that records one or more state transitions resulting from the processed transaction input; and
generating a client deployment request for transmission to the distributed network system, wherein the client deployment request is based at least in part on the replay log.
10 . The method of claim 9 , wherein a user interface is provided for a user to verify the replay log.
11 . The method of claim 9 , wherein the replay log comprises a partial set of operations associated with the user transaction input.