联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981
CSE 486/586 : Class Project Handout
RAFT (Total Points: 35 + 5 bonus points) Phase 4 : Safe Log Replication with leader election Deadline : 5/6/2022 11:59 PM (FRIDAY) In the previous phase, we worked on leader election and how a new leader would be elected when there is a timeout. To recap, once a follower times out, it increases its own term number, converts to candidate state and sends out RequestVote RPC to all the other nodes. On the receiver side, the node when it receives a RequestVote RPC, it would compare its own term number with the candidate’s term and it’s own log entries with the lastLogIndex and lastLogTerm values (sent out during RequestVote RPC) and decide whether to give a vote or not.
In phase 3, the lastLogIndex and lastLogTerm comparisons were trivial and not considered as the logs entries were always empty as no client requests were being made. However in this phase we will see how these comparisons play an important role in deciding who can and who cannot become the leader.
Note : All references to AppendEntry RPC’s also include heartbeats since both are practically the same thing
Prerequisites of what each server should store
Handling additional requests that will be sent out by controller. STORE & RETRIEVE (5 points)
STORE
The controller from phase 3 has a new purpose in this phase. The controller will be used to send out STORE requests to the RAFT cluster. This is similar to the client making a request to the RAFT cluster where the request gets appended to the log’s of the leader and eventually gets appended to the follower’s logs. You will be using the STORE cmd to make client requests.
RETRIEVE
The controller can send a request to any of the nodes to RETRIEVE all the committed entries at that particular node. However, only the Leader will respond with the committed entries[{entry1},{entry2},{entry3}], any other node responds with Leader Info as depicted in the diagram above. Also, the format of what constitutes an entry is as below –
entry = {
“Term”: Term in which the entry was received(may or may not be current term) “Key”: Key of the message (Could be some dummy value)
“Value”: Actual message (Could be some dummy value)
}
Note 1 : For testing purposes, you will require a listener thread at the Controller end to receive messages from the leader. We will use our controller(hidden test-cases) to evaluate. As long as you follow the naming conventions in the JSON message and you are handling all the specified controller requests on the server-node’s side there will not be any issues in testing.
Safe Log Replication with consistency checks: (15 points)
In phase 2, you would have built a simple mechanism of forwarding the client’s request from the leader node to all the followers and ensuring that the request is executed on all the nodes.
In RAFT, the request first gets appended to the log’s of each node and once the request has been appended to a majority of the node’s logs, the request is said to be committed and will be executed by the leader. This is an extremely simplified explanation of what actually happens. There are certain rules to a client req being appended to the followers logs, whether a follower will accept or reject an AppendEntry RPC and how the logs are replicated. Details in the paper
The leader maintains a nextIndex[] for each follower which is the index of the log entry that the leader will send to that follower in the subsequent AppendEntry RPC. When a leader first comes to power (when a candidate first changes state to a leader) it initializes all nextIndex[] values to the index just after the last one in it’s own log, this will happen every time a leader is elected.
Eg, If the last committed index on the new leader’s own log is 5, then the leader initializes nextIndex[] for each follower node as 6 which means the leader is prepared to send the entry at position 6.
The AppendEntry RPC is used to replicate the log’s on the follower nodes.
1. The client’s request gets appended to the leaders’s log
2. Based on the next index, the leader sends this request to the followers by passing the
entry( or request) in the AppendEntry RPC along with the prevLogIndex, prevLogTerm
and leader’s commitIndex
3. The follower will check to see if needs to accept or reject the the AppendEntry RPC by
performing a log consistency check(read RAFT Paper)
4. If the follower accepts, then it appends the entry to its own log and sends an
APPEND_REPLY with success=True. The Leader on Receiving a True will update the
next index and match index values.
5. If follower rejects (checks rules for rejection in Append Reply section below), follower
sends an APPEND_REPLY with success=False
a. Once the leader receives a reject from the follower, the leader will decrement the
nextIndex[] for that particular follower by 1, and will send the previous log entry at that position back to the follower.
b. The leader will retry the AppendEntry RPC and eventually the we will reach a point where the leader and follower’s log match
c. Eg : If the leader, has nextIndex[] as 6 for a follower, but the follower rejects the leader’s AppendEntryRPC, the leader will decrease nextIndex[] to 5 for the follower that has rejected. This happens until the follower will eventually accept the leader’s AppendEntryRPC (This could be an empty AppendEntryRPC or an heartbeat)
Note 2 : Additionally, you will need to check if a particular entry has been replicated on majority of the followers( utilize matchIndex[] ) and send that in the APPEND RPC to the followers which will apply that to their own logs for a final commit.
Note 3: A STORE req from the controller is not a trigger for the AppendEntryRPC. The AppendEntry RPC is triggered at regular intervals as a heartbeat (which is why it is also functioning as a heartbeat). The STORE req appends an entry to the leader’s log and this new entry gets sent along to the followers in the subsequent heartbeat/AppendEntryRPC.
Fig : How an example message JSON would look like. First five fields are mandatory fields and the remaining fields are dependent on the type of “request”. For instance, the above JSON is an example of an AppendEntryRPC
Append Reply (5 points)
When a follower receives an AppendEntry RPC ( Note: heartbeats are also AppendEntryRPC), the follower can choose to accept or reject.
The follower can:
1. Reply false if term
This ensures SAFETY i.e. once an entry has been committed by a Leader no other node that doesn’t have that entry gets to become the leader thereby preventing overwriting committed entries.
Report and Video Demo ( 5 points)
● A short video demo (Should be less than 8 mins and should be separately recorded for each teammate on their own laptop)
● A report following the structure similar to the previous phases
Note 4: The Report should contain a section discussing the difference between the basic log replication in phase 2 and the log replication you are implementing in this phase
Integrate Client UI from Phase 1 ( Bonus : 5 points )
The client you might have implemented with an UI in phase 1, can be integrated with your RAFT cluster. This can be done by having your client send a STORE request to the leader, where the value of the STORE req can be the actual CRUD command that the client is making.
What to submit ( We will be deducting points if the naming convention for submission, the directory structure is not followed)
The submission must be a zip file with naming convention
The zipped file should contain:
● A folder containing the entire source code
● A short video demo
○ Please do not spend time explaining your code in the video demo
○ To save time, have your docker containers already running and the first leader
already elected before you start recording
○ In your recording go over, you add entries to the logs, stop the leader, let a new
leader be elected, add more entries to the logs, use RETRIEVE to get the logs, restart the old node which you had shutdown earlier and show how the new logs gets appended to the node which was just restart-ed
● A report following the structure similar to the previous phases (5 points for video + report)
Resource:
https://raft.github.io/
https://raft.github.io/raft.pdf http://thesecretlivesofdata.com/raft/ (Highly recommended) https://www.youtube.com/watch v=YbZ3zDzDnrw https://docs.python.org/3/library/socket.html https://docs.python.org/3/library/threading.html
发表评论