Timeouts

We need to know how long the entire cycle single-slot recovery cycle takes to set the timeouts large enough to make it unlikely we have an extended leader duel. The complete initial leader election cycle is the time to complete the following steps:

1. The leader creates a prepare message, self-promises and makes their new progress durable.
2. The prepare travels to the follower.
3. The follower receives the prepare message, promises, and makes its new progress durable.
4. The response travels to the leader.
5. The leader creates an accept message, self-accepts it into their journal and makes it durable.
6. The accept travels to the follower.
7. The follower receives the accept message, accepts it into its journal, and makes it durable.
8. The response travels to the leader.
9. The leader receives the response, updates its progress record with the new fixed index number, and makes its new progress durable.
10. The fixed message travels to the follower, who cancels its timeout.

That breaks down as follows:

• 1 network round trip of a small prepare message.
• 1 network round trip of a potentially significant accept message needing multiple packets.
• 0.5 network round trips of the small fixed message.
• 2 small promise durable writes.
• 2 small accept durable writes that potentially flush as multiple blocks.

You must measure these values in your cluster. Remember that your own host application using this library will be doing work. Remember that I am not giving you a journal; you must provide it.

A multiplier of around 3.6 to this value gives a 50% chance of two nodes not timing out within that interval. You then have a double coin toss situation on each attempt to elect a leader:

1. There is a 50% chance that the node with the higher node identifier will time out first. If so, it cannot be interrupted by the other node.
2. If you lose that coin toss, there is a 50% chance that the new leader will not be interrupted.

The probability of a losing streak is 0.5 ^ T, where T is the number of tosses. This goes as 0.25, 0.06, 0.01, and 0.004 each attempt due to the double coin toss per attempt. Those are excellent odds if you let the compound interest do the work to give you the payout.

Therefore, my advice is:

1. Do not assume that you can set a low timeout and expect things to recover faster. On the contrary, if you set it too low, the cluster will never recover.
2. Everyone wants subsecond failover. Very few companies hire a full-time member of staff working as a site reliability engineer, tuning the system to get that sort of uptime that figure implies across the whole site.
3. Most systems have users who will not resign from their jobs or cancel a business contract because their web browser got a connection error that lasted three seconds. This is because users have countless browser connection errors. You can get at least one free pass if you had a server crash and your entire application failed over in a low number digit number of seconds.
4. A one-second timeout would not be a bad guess for many systems. Take the odds above; only 1% of the time would users see a three-second outage.
5. My advice does not apply to your situation. You need to understand the math above and also understand your actual system and application to be able to either use or disregard my advice.

This implementation separates the core algorithm into TrexNode and the timeout logic into TrexEngine. It will allow you to use your own node failure detection or election mechanism.