...
The second problem is the case of partially accepted (but not yet guaranteed) log entries. It is likely that the new leader will store these entries, in which case they will get fully replicated a by the new leader. However, if an entry has only been accepted by a small number of servers that then it is possible that a new leader can be elected without any of its vote-givers storing the entry. In this case the new leader must make sure that the entry is expunged by all other servers. The way it does this is by initiating a log append for a new entry that indicates leadership change. The id for this entry will be the next one in order on the leader. When this entry arrives at a passive server, the passive server deletes any existing entries with this id or higher before it accepts the entry. This is the only situation where a passive server receives a log entry whose id it has already accepted.
Leader failures also introduce the potential for zombie leaders. A zombie leader is a leader that has been replaced but does not yet know it. ALPO must make sure that zombie leaders cannot continue to modify the log. Each To do this, each request issued by the leader includes the leader's term number. If a passive server receives a request whose term is lower than the server's current term, then it rejects the request. If a leader receives such a request then it knows it has been deposed, and returns to passive state. Before a server gives its vote to a candidate it must increase its term number to that of the new term. This guarantees that
...
that by the time new leader knows that it elected, it is impossible for the previous leader to create enough replicas of a new log entry to guarantee that entry. Furthermore, if a leader receives any election-related requests from candidates with a higher term number, this also indicates that the leader has been deposed, so it returns to passive state.
One final issue related to log management is log cleaning. ALPO allows each server to perform cleaning (or any other form of log truncation) on its log independently of the other servers. However, there is one restriction on log cleaning: a server must not delete a log entry until it has been fully replicated. Otherwise the server could become leader and need that entry to update a lagging passive server. To ensure this property, the leader keeps track of the highest log id that has been fully replicated and includes this value in any requests that make to other servers. The other servers use this information to restrict cleaning; in most cases the fully-replicated-id will be at or near the head of the log, so this will not impose much of a restriction on cleaning.
Clients: at-most-once semantics
ALPO, clients must send any requests that result in log modifications to the leader. If such a request arrives at a passive server (for example, because it used to be leader but has been deposed) the passive server rejects the request; in most cases it will also be able to tell the client who is currently the leader. Clients can send read requests to any server in the cluster. However, passive servers may not be able to return the most recent log entries, for two reasons. First, the server might not have accepted the most recent log entries yet. Second, only guaranteed log entries can be returned to clients, and a passive server may not know whether it's most recent log entries are guaranteed. One way to handle this is for the leader to include the highest guaranteed id in each request to other servers; in most cases, the append for entry N would indicate that entry N-1 is now guaranteed, so the passive server would would lag at most one log entry in comparison to the leader. Thus, if clients can tolerate a small amount of lag they can issue log reads to any server; if they want to be assured of getting all the most recent data, then they must send requests to the leader.
State for each server
- Term number: number of the most recent term seen by this server (updated when notified by a leader or a candidate, or when the server becomes a candidate).
- Vote: the server id of the candidate who has received this server's vote for the current term (if any).
- Server id of this server.
- Log entries that has been accepted by the server.
- Id of the most recent log entry that has been accepted by all servers.
- Time of receipt of the last request from the leader.
- Cluster map: id and location of each server in the cluster, whether dead or alive.
...