DS Fall 2023
HomeSchedulePiazzaLabsDev Environment Setup
Lab 1: Raft
Introduction
This is the first in a series of labs in which you’ll build a fault-tolerant key/value storage system. In this lab you’ll implement Raft, a replicated state machine protocol. In the next lab you’ll build a key/value service on top of Raft.
A replicated service achieves fault tolerance by storing complete copies of its state (i.e., data) on multiple replica servers. Replication allows the service to continue operating even if some of its servers experience failures (crashes or a broken or flaky network). The challenge is that failures may cause the replicas to hold differing copies of the data.
Raft manages a service’s state replicas, and in particular, it helps the service sort out what the correct state is after failures. Raft implements a replicated state machine. It organizes client requests into a sequence, called the log, and ensures that all the replicas agree on the contents of the log. Each replica executes the client requests in the log in the order they appear in the log, applying those requests to the replica’s local copy of the service’s state. Since all the live replicas see the same log contents, they all execute the same requests in the same order, and thus continue to have identical service state. If a server fails but later recovers, Raft takes care of bringing its log up to date. Raft will continue to operate as long as at least a majority of the servers are alive and can talk to each other. If there is no such majority, Raft will make no progress, but will pick up where it left off as soon as a majority can communicate again.
In this lab you’ll implement Raft as a C++ class with associated methods, meant to be used as a module in a larger service. A set of Raft instances talk to each other with RPC to maintain replicated logs. Your Raft interface will support an indefinite sequence of numbered commands, also called log entries. The entries are numbered with index numbers. The log entry with a given index will eventually be committed. At that point, your Raft should send the log entry to the larger service for it to execute.
Your Raft instances are only allowed to interact using RPC. For example, different Raft instances are not allowed to share variables. Your code should not use files at all.
Objective
In this lab you’ll implement most of the Raft design described in the extended paper. You will not implement: saving persistent state, cluster membership changes (Section 6), log compaction / snapshotting (Section 7).
Some general tips:
Start early. Although the amount of code isn’t large, getting it to work correctly will be challenging.
Read and understand the Raft paper and the Raft lecture notes before you start. Your implementation should follow the paper’s description closely, particularly Figure 2, since that’s what the tests expect.
Getting Started
Checking out code
Use the following link to get the assignment from GitHub Classroom.
https://classroom.github.com/a/TkjESYSH
Setup
First, make sure you are working on the right branch. Make sure you use lab-raft-solution as the branch name.
$ git checkout -b lab-raft-solution origin/raft-23fa
$ git submodule update --init
$ git push -u origin lab-raft-solution
We supply you with skeleton code and tests in src/deptran/raft.
Before compiling, you need to install all needed software dependencies.
sudo apt-get update
sudo apt-get install -y \
git \
pkg-config \
build-essential \
clang \
libapr1-dev libaprutil1-dev \
libboost-all-dev \
libyaml-cpp-dev \
libjemalloc-dev \
python2 \
python3-dev \
python3-pip \
python3-wheel \
python3-setuptools \
libgoogle-perftools-dev
sudo pip3 install -r requirements.txt
To get up and running, execute the following commands:
$ python3 waf configure build --enable-raft-test # compile
$ build/deptran_server -f config/raft_lab_test.yml # test
TEST 1: Initial election
TEST 1 Failed: waited too long for leader election
TESTS FAILED
ARM Mac users (unsupported by staff):
This lab is tested on x64 version of linux, but you may try ubuntu ARM as well. It looks the Multipass setup on this website installs aarch64 Ubuntu for ARM Mac computers.
For compilation, please use the following command instead.
$ python3 waf configure build --enable-raft-test --boost-libs=/usr/lib/aarch64-linux-gnu
The Code
Most of the Raft implementation will be located in src/deptran/raft/. In this directory, there are 3 .cc files (and respective headers) that you need to modify:
server.cc and server.h
commo.cc and commo.h
service.cc and service.h
Besides these three files, there is also src/deptran/raft/raft_rpc.rpc, where you will find abstract service Raft containing sample prototypes for the RequestVote and AppendEntries RPCs. Here, you can modify the arguments and return values for the RequestVote and AppendEntries RPCs and add any other RPCs as you see fit.
Do not create new files, and do not modify any existing files not mentioned.
RPCs
Class RaftServiceImpl (service.cc) implements receiver-end handlers for the RPCs declared in src/deptran/raft_rpc.rpc. To register a handler for an RPC in RaftServiceImpl, use the RpcHandler macro.
RpcHandler usage: RpcHandler(RPC_NAME, N_PARAMS, PARAMS...) { DEFAULTLOGIC }
RPC_NAME: should match the name of the RPC declared in raft_rpc.rpc
N_PARAMS: number of RPC arguments + number of RPC return values
PARAMS: the RPC arguments and return values in the same order as in raft_rpc.rpc, with comma separations between the type and name.
DEFAULTLOGIC: write code to assign default values to the RPC’s return value in these brackets. This code will get invoked when the server is disconnected from the network to simulate a failed RPC. It is important that your RPC sender code recognizes the default values and ignores them when they happen.
Class RaftCommo (commo.cc) is meant to handle sending RPC requests. See the example sender functions to understand how to send RPCs in RaftCommo.
Server logic
Class RaftServer (server.cc) is your starting point for writing most of the server logic.
Some useful member variables (inherited from a parent class of RaftServer):
loc_id_: id of the server.
commo(): function that returns the server’s RaftCommo instance.
mtx_: a std::recursive_mutex you can use for protecting data from concurrent access.
Required Functionality
There are a few specific functionalities in RaftServer you need to implement in order to pass all tests.
bool Start(shared_ptr &cmd, uint64_t *index, uint64_t *term)
Implement this member function
If server is not the leader, return false
Else, start agreement on cmd in a new log entry, set index and term with the server’s current index and term, and return true
void GetState(bool *is_leader, uint64_t *term)
Implement this member function
Populate is_leader with true if the server thinks it is the leader
Populate term with the server’s current term number
function