Refactor the GC of speculative pool

[iGxnon]

Description about the feature

Currently, our speculative pool's garbage collection is conducted at regular intervals, which may potentially result in command execution disorder under certain extreme conditions. (Refer to #159 for details)

Background

In order to limit memory usage and increase the number of fast_path requests, after the command has been synchronized with backups, it is necessary to perform a GC on the follower's speculative pools to remove these commands.

Typical GC path

In our implementation, the leader advances the commitIndex and clean up commands in the speculative pool only after the log has been synchronized with the majority of nodes. Subsequently, an append entries request with the latest commitIndex propagates the update to the state machines in followers. At this stage, followers can clean up commands within their speculative pools.

Challenge

However, there are still some situations in which the command will not be cleared:

• If the client only sends proposals to a follower and then crashes, the command will keep in the follower forever.
• A proposal request is delayed significantly and arrives after the follower finished apply the log.
• A minority of followers have been offline for an extended period, and their logs have already been compacted so that the leader will no longer send append entries requests for these logs.
• ...

During the leadership transfer, the new leader will recover the SP from the cluster. This may recover some unexecuted commands and append them into log and finally going through the typical GC path. For commands that have already been executed, they will not be restored.

Xline/curp/src/server/raw_curp/mod.rs

Lines 939 to 950 in 2a034e9

	// get all possibly executed(fast path) commands
	let existing_log_ids = log.get_cmd_ids();
	let recovered_cmds = cmd_cnt
	.into_values()
	// only cmds whose cnt >= ( f + 1 ) / 2 + 1 can be recovered
	.filter_map(|(cmd, cnt)| (cnt >= self.recover_quorum()).then_some(cmd))
	// dedup in current logs
	.filter(|cmd| {
	// TODO: better dedup mechanism
	!existing_log_ids.contains(cmd.id())
	})
	.collect_vec();

But it seems that it will still recover commands that have already been compacted? (This may result in a particular command being executed twice, and it is unrelated to the SP GC issue discussed here -- It will go the typical GC path.)

Xline/curp/src/server/raw_curp/log.rs

Lines 312 to 316 in 2a034e9

	/// Get existing cmd ids
	pub(super) fn get_cmd_ids(&self) -> HashSet<&ProposeId> {
	self.entries.iter().map(|entry| entry.id()).collect()
	}

Xline/curp/src/server/raw_curp/log.rs

Lines 330 to 339 in 2a034e9

	/// Reset log base by snapshot
	pub(super) fn reset_by_snapshot_meta(&mut self, meta: SnapshotMeta) {
	self.base_index = meta.last_included_index;
	self.base_term = meta.last_included_term;
	self.last_as = meta.last_included_index;
	self.last_exe = meta.last_included_index;
	self.commit_index = meta.last_included_index;
	self.entries.clear();
	}

Solution

1. Solution 1

The CURP paper mentions one potential solution to this issue.

Witnesses detect such uncollected records and ask masters
to retry garbage collection for them. When it rejects a record,
a witness recognizes the existing record as uncollected
garbage if there have been many garbage collections since
the record was written (three is a good number if a master
performs only one gc RPC at a time). Witnesses notify
masters of the requests that are suspected as uncollected
garbage through the response messages of gc RPCs; then the
masters retry the requests (most likely filtered by RIFL), sync
to backups, and thus include them in the next gc requests.

We do not have a structure similar to RIFL, and retrying may result in the execution of a command twice. (Perhaps we can deduplicate during the apply process?)

We can add a suspected commands collection to the response of append_entries RPC, and the leader adds these commands to the log upon receiving them, and then performs the typical GC path.

2. Solution 2

Introducing an additional RPC mechanism to synchronize the SP of followers and the leader. The details and security of this approach require further discussion.

Code of Conduct

• I agree to follow this project's Code of Conduct

[Phoenix500526]

Relevant issue: #159