Why does a heartbeat replicate and store a blank LogEntry?

[mfelsche]

While working on our little application using openraft, I noticed that openraft if storing Blank log entries for each heartbeat sent around the cluster. From reading the raft paper, i assumed that the heartbeat was an empty AppendEntriesRequest and thus no changes would be made to the log.

What is the reason for actually storing, replicating and committing such a Blank log entry instead of implementing an empty AppendEntriesRequest with no changes to the log, that only does the heartbeating?

[drmingdrmer]

It's part of the task to get rid of pre-vote: #15

Raft, or other consensus protocol has its own time defined internally.

In paxos it is round_number(AKA ballot number in some paper).
In raft it is (term, voted_for, last_log_index)(because in raft there is only one leader in every term, voted_for can be removed: (term, last_log_index)).

Without heartbeat log(the way standard raft does), when handling a vote request, except vote itself, it has to examine two values to determine if the vote request is valid:

• Whether the last heartbeat has expired by clock time.
• Whether the (last_term, last_log_index) in the request is greater or equal to the local value. This is the pseudo time Raft defines.

With heartbeat log(the way openraft does), when handling a vote request, it only needs to examine one value: the raft time: (last_term, last_log_index). This makes the logic simpler and the test easier to write.

In other words, a consensus protocol does not have to, and should not depend on an external clock.

[schreter]

@drmingdrmer That's a nice idea. However, strictly speaking, this also requires us to persist the blank entry in the log (or at least the incremented index). Doing that every 50ms for 100 consensus domains on one machine will require 2000 IOPS alone for that.

An alternative is not to persist the blank entry at all and just ACK it to the leader (and also don't persist it on the leader). In that case, restarting a node which didn't persist the newest time should not be a problem - the leader should simply re-send the missing log (without unnecessary blank entries). Similarly, restarting the leader will start with older time from before blank entries and most likely be join as a follower, since one of the other followers will have a higher time (as it received previous blank entries from the leader).

The only thing to consider would be the time when snapshots are taken - the blank entries should be irrelevant for snapshots and the leader has to keep the snapshot at least from the last "real" committed entry.

Does that make sense? Or am I missing something?

Thanks.

[drmingdrmer]

It's a good point man.

First, I assume that most consensus domains are busy, and as a domain is busy, it is possible to merge multiple append-entry calls into one call to the storage layer.
Thus if a domain swallows 10 business log entries per 50 ms, it's likely to merge these 10 entries into one or a few IO calls. The IO amplification should be smaller as IOPS gets heavier.

Merging entries into one IO call is already done on followers(because the leader sends entries in a batch).
On the leader, it can be done when the Engine oriented refactoring is ready: (.

Second, if a consensus domain swallows 1 business log entry per 50 ms. It does not need another heartbeat. A normal append-entry can be considered a heartbeat.

So, is this good enough? 🤔

[schreter]

So, is this good enough?

Not really. Some background: Our intention is to have a consensus per tenant. There will be many small tenants (thousands or more) with their respective 3-5 replicas evenly scattered across multiple big machines (tens to potentially hundreds). This gives us extreme availability and scalability of the system. However, the workload on tenants will be very disparate - both from overall throughput POV and from time-of-day POV.

"Regular" voting and timeout handling does not tax the persistency. Doing it with blank entries does.

To offload the network, our intention is to "pool" the connection error detection handling across all connections from A to B for all consensus domains affected by this link from A to B to reduce the number of messages on the network. This would also pool data being sent from A to B by multiple consensus domains, where acceptable. But it doesn't help with persistency.

Persistency is per consensus domain, since each tenant's data is a separate data area (for various practical purposes). Of course we could somehow add "log-over-logs" to somehow handle the unnecessary persistency of blank entries, but I don't think that's practical.

IMHO, the above described recovery when NOT persisting blank entries at all (which I'd definitely prefer) should be sufficient, right?

[drmingdrmer]

IMHO, the above described recovery when NOT persisting blank entries at all (which I'd definitely prefer) should be sufficient, right?

To not persist a blank log will break the consensus: There is one important blank log, that is proposed by the leader when leadership is established, to mark all preceding logs as committed. Committed logs will then be applied to the state machine.

Ti:   Vote in term-i
Li:   Leader established in term-i
Ei-j: Entry in term-i at index-j
Bi-j: Blank log entry in term-i at index-j

R1: T1 L1  B1-1 E1-2                  T3 L3 B3-3
R2: T1                T2              T3    B3-3  T4    B4-3
R3:                   T2 L2 B2-1 E2-2             T4 L4 B4-3
--------------------------------------------------------------> time

1. R1 established leadership and append 2 entries: B1-1, E1-2 but failed to replicate them.
2. R3 established leadership and append 2 entries: B2-1, E2-2 but failed to replicate them.
3. R1 re-established leadership and replicated B3-3 to R2. B1-1,E1-2,B3-3 are all committed and applied.
4. All nodes restart, R3 established leadership and replicate B4-3 to R2, E2-2 then was committed, which conflicts with E1-2.

Hence to complete your solution, the leader-first-blank-log must be treated specially.

Back to your need,

although a consensus should work barely with a pseudo time, the pseudo time does not have to be completely persistent.
Thus just give the pseudo time a non-persistent suffix to extend the precision:

In standard raft, the pseudo time is (last_term, last_log_index).
In openraft, the pseudo time for now is (last_term, node_id, last_log_index).
The next version pseudo time would be: (last_term, node_id, last_log_index, heartbeat_count), where the heartbeat_count:

• heartbeat_count is not persisted, and is reset to 0 when a node restarts;
• heartbeat_count is increased for every heartbeat(append-entries without any entries);
• Add a heartbeat_count field to the append-entries RPC body.

When handling a vote request, a node compares two values to determine whether to grant it:

• the next pseudo time the candidate wants to work in: (term, node_id, nil, nil), which is just the Vote struct, without any change.
• the pseudo time of the data: (last_term, node_id, last_log_index, tick).

This way the pseudo time keeps increasing while there is an active leader. There won't be additional IO introduced.

Make sense? 🤔

[schreter]

There is one important blank log, that is proposed by the leader when leadership is established, to mark all preceding logs as committed.

Right, that's an exception and it must be persisted. I just didn't think it to the end, obviously.

heartbeat_count is not persisted, and is reset to 0 when a node restarts;
heartbeat_count is increased for every heartbeat(append-entries without any entries);
[...]
There won't be additional IO introduced.

The solution with heartbeat_count looks good :-). Thanks.

[drmingdrmer]

The blank log heartbeat can not protect the leadership from being seized by a candidate if it has not yet replicated the latest logs to a quorum.

Fall back to the original heartbeat solution in:

• 97fa158