1 Introduction

In this assignment, you will build a distributed replicated  (key-value) map using Raft [1]. Follow the Raft paper to implement and pass all the test cases in the grader. We thank Shimin Wang from Carnegie Mellon University when preparing this assignment.

For the details of Raft please refer to

• The detail of Raft presented by their authors: https://youtu.be/YbZ3zDzDnrw and https://youtu.be/vYp4LYbnnW8

• The Raft extended paper annotated by Shimin Wang, which is included in the assign- ment package.

• The official web site of Raft, http://raft.github.io. It provides a good interactive demo with the Raft consensus protocol.

You do not need to handle all cases in the full Raft paper. Specifically,

• You don’t need to randomize the election timeout.  The election timeout value would be changed by the grader at run-time to simulate different situations.

• You don’t need to implement log compaction and snapshotting.

• We don’t need to handle cluster membership changes.

•  No  disk is considered in this implementation.   Your  key-value map is in  memory. When you commit any log, you should directly apply that operation, committed will be treated equally as applied.  Consequently, the lastApplied operation in the Raft paper is unnecessary to you.

Figure 1: A condensed summary of the Raft consensus algorithm

2 Your Assignment

2.1    Submission:  git classroom

We use Github Classroom https://classroom.github.com for assignment managment. Git is a predominant version control system, created by the inventor of Linux.  Github is an online hosting of Git and it is now hosting thousands of open-source projects.

2.2 Get the assignment package

You are supposed to open a Github account using your CUHK email address (it is fine to use your own Github account if you already have) and follow the steps below to register an account and get the starter code.

1. Use your Github account to come here https://classroom.github.com/a/3qoRTJ1Z to clone the assignment starter package to be under your Github account.

2.  If everything runs smoothly, your Github account will show a new repo named cuhk- raft-[your-Github-account-name], like below:

3. As GitHub shut down password authentication since Aug.  2021, you’re required to setup a ssh key for connection following the GitHub Docs.

4.  Look for the tab “Code” to get the URL of your assignment repo, like below:

5.  Open a terminal, change to a local directory of your desire, type “git  clone  {Your Repo  URL}”  and your username/password to get  a local copy of the repo on your computer.

6.  Finally, we should set the user name and email such that the git system recognizes you. You should do this once only. To begin with, type the followings in the terminal and replace the name and email with your own Git account.

2.3 Get your starter code based on your preferred language

First clone the project from your repository. If you use Java, please execute: git   checkout   java

If you use Go, please execute: git   checkout  go

2.4 Submission

Git is actually a complicated version control system (VCS) that has a lot of features.  Briefly, it installs a local VCS on your computer and you can do any versioning locally (e.g., commit- ting some changes, reverting some changes). If necessary, you can  “push” your local changes from your local repo to an online repo (Github). You may Google the powerful usage of Git online. Here, we focus on how you can commit your finished assignment to your local repo and then push to the online private repo.  We will fetch your assignment from your online private repo for grading. The process is essentially the “assignment submission” process:

Assuming you have done some edits on the source files, the command git  add   .  states your interest of adding everything under the current directory  “.”  to your local Git repo. Next, the command git  commit  tries to commit your changes to your local repo.   The parameter -m  "comments" is your comment about this commit.  Lastly, the command git push  origin tries to synchronize your local repo with your online repo.

For Git beginners, make sure you use a web browser to login your Github online and check if your source codes have been pushed there successfully.

To submit the final version for grading, push the code to the master branch by git  push origin  go:master  -f if you use Go.  Replace the branch name go by java to submit if you use Java.

Warning: DON’T change the file names, otherwise you get 0 marks

2.5 Your job

For Java, write your program in ‘src/main/java/RaftRunner.java ’.  For Go, write your program in ‘main.go ’.

• Follow the  “State” box in Figure 1 to implement RaftNode class (Java) / raftNode struct (Go).  You will need to add a lot more than what Figure 1 tells you such as adding a Map to be the in-memory key-value map, adding a server-state to store whether this node is in “Follower”, “Candidate”, or “Leader” state, etc.

• Function NewRaftNode: After creating an instance of raftNode, its initial state should be a “Follower”, a node shall create a new thread to kick off a new leader election if it has not heard from the leader within a period of electionTimeout.  To kick off the leader election, invoke the others’ RequestVote by RPC concurrently.  If a remote node doesn’t respond to your RequestVote, don’t resend RequestVote, wait for the next election.

• When a node becomes a  “leader”, invoke others’ AppendEntries RPC concurrently based on the heartbeat interval.

Follow Figure 1’s “AppendEntries” box to implement it.  Once again, if a remote node doesn’t respond to your call, don’t resend, wait for the next heartbeat interval.

• RPC Propose:  Our grader will call this  RPC to put or delete to update the dis- tributed replicated map.

Log this operation using LogEntry and append to the local log of the leader.  Propose return only after the the log is committed (i.e., replicated to the majority of other nodes).

We also provide a script to test for a specific test case. For example: bash   . . /scripts/rafttest _single . sh  \ testOneCandidateOneRoundElection

Remember to run rafttest . sh at least once before rafttest single. sh, otherwise the grader is not compiled and can’t be found.

4 Grading

1. The TA will fetch and grade your latest version of master branch in your repository as of the deadline. Remember to commit and push before the deadline!

2.  10 test cases in total.

3.  Passing one test case will earn you 10 marks.

4.  A test case is regarded as PASS if and only if your program always pass it.  If it fails once during the grading, it’s regarded as FAIL.

5.  Part A is leader election part of Raft.  It covers the first six test cases.  Part B is the log replication part, which covers the last four test cases.

6. We’ll try to run the grader as many times as we can.  As far as we know, 10 times is not enough to find all bugs, please run the grader for more times to fully test your program before submission.