Optimistic State Machine Execution

-

Distributed Consensus algorithms play an essential role in any Distributed System in which a cluster of nodes must agree on a single value - usually an order of user requests. Once user requests are replicated and uniquely ordered on each node (in a replication log), a node can apply the agreed-upon request to its state machine. If each node has the same implementation of a deterministic state machine, the state on all nodes will be the same (up to the given user request). Voila, we have achieved redundancy in our system, and if some of the nodes fail, we still have the state available on other nodes for users to consume. 

State Machine Replication

Idempotency

If a node crashes and restarts, it wouldn't be optimal to have the apply process start applying requests from the beginning of time. Hence, the apply process durably stores its progress in an apply_index variable. This saves us some CPU cycles.
However, a node could crash during the apply process before we have durably stored the apply_index. In this case, the state machine might execute the same request more than once. 
It is crucial that the state machine is idempotent and that re-executing the same request does not hurt its consistency and, after all, its determinism.

A convenient way of achieving state machine idempotency in a Distributed Consensus environment is to deduplicate requests from the replication log. Replication log entries are uniquely identified by their replication_log_index. Along with the request, the apply process gives the replication_log_index to the state machine. The state machine durably stores this value as its deduplication key. It uses it to identify requests it has already processed - "I don't process the request if its deduplication key is smaller or equal to the last one I have seen."

Pessimistic execution

The premise I want to take here is that replicating requests usually does not fail. I said this and stayed alive. In a pessimistic scenario, executing the request would first involve replicating it across the cluster of nodes and invoking the apply process once it has been replicated. The apply process takes the request and gives it to the state machine. The state machine executes it, and the apply_index gets updated. We are now free to move forward with the subsequent request.

Pessimistic Execution

The time necessary for the request to be processed is the sum of the time needed for the replication and the time it takes the state machine to execute the request. We can do better...

Optimistic execution

If the replication is usually successful, why wait for it to complete before we apply the request to the state machine? Well, it is not necessary to wait. We could start executing the request against the state machine while it is being replicated. Once both processes are done, we can update the apply_index.

Optimistic Execution

Now, the time necessary for processing the request is the maximum between the time needed to replicate the request and the time it takes the state machine to execute it.

Of course, this optimization is only possible if the state machine is capable of reverting the execution of requests that failed to replicate. While I'm saying this as a side note and not-a-big-deal thing, it is actually quite crucial for the state machine to have this property if we want to guarantee consistency and determinism.

In the end, a little optimism wouldn't hurt :)

Location: Novi Sad, Serbia

Comments

Post a Comment

Popular posts from this blog

Lock-free Exclusive Processing

-
Image
The problem that I'd like to explore in this article is related to multithreaded processing, and it goes something like this:  Design a component that executes tasks one after the other - there is no overlapping in processing. Tasks could be submitted by different threads. Of course, the most obvious solution would be to synchronize the execution of tasks. Each thread would try to acquire the lock on this object if possible, otherwise, it will block and wait for the lock to be released. While waiting for this lock to be released, the thread cannot do anything else. This approach creates a lot of contention and besides that, acquiring and releasing the lock is quite an expensive operation. So, it is not performant as well. However, we must admire the simplicity of the solution. Is there a more performant solution that does not block the thread which wants to execute the task?  Firstly, let's decouple task submission and task execution - a queue sounds like a perfect fit for the
Read more

Ordering in Event-Sourced Systems

-
Image
In a utopian world, Event Store will write events to the disk in the exact same order in which they have happened in real life. However, computers are not so good at observing things by themselves (yet), we (still) must tell them what to do. Hence, we must provide a way to deterministically order events inside the Event Store.  A naive approach would be to attach a timestamp to each and every event and use it for ordering. The reason for its naiveness lies in the difficulty of synchronizing clocks across different machines in a distributed system. As a consequence, we mustn't rely on timestamps for ordering . Since we also cannot impose ordering of events sent by different Event Store clients among them, the only thing left is to accept the ordering of received events by the Event Store. In other words, the order in which Event Store receives events is going to be the order of events written to the disk. This means that two events could have happened in one order in reality, but t
Read more

Myths about Distributed Business Transactions

-
Image
Nowadays, most systems are distributed in one way or the other - just accessing a database via HTTP makes the system distributed. Not so rarely, there is a message broker in the mix which makes a good soil for Distributed Business Transactions. There is a lot of mystery about them, they get confused with ACID transactions easily. I'm going to address common myths and misunderstandings about Distributed Business Transactions and provide some options on how to handle multiple independent resources. Before we start, let's try to understand what a Distributed Business Transaction is. Distributed Business Transactions Distributed Business Transaction is a business transaction that spans at least two independent  transactional resources.  One example would be a database update and sending a message via a message broker (see Diagram 1 ). Those two resources have their own transaction management and are completely independent. Another example would be updating two different files on a
Read more