-
Notifications
You must be signed in to change notification settings - Fork 0
/
a3.html
415 lines (361 loc) · 16.3 KB
/
a3.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html
PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xml:lang="en" lang="en">
<head>
<title>CS-240 Assignment 3: Raft</title>
<link rel="stylesheet" type="text/css" href="style.css" />
<meta http-equiv="Content-Script-Type" content="text/javascript" />
</script>
</head>
<body>
<h1>CS-240 Assignment 3: Raft</h1>
<div id="topnavbar">
<ul class="topnavlist">
<li><a href="index.html">CS-240 Home</a></li>
<li><a href="syllabus.html">Syllabus</a></li>
<li><a href="assignments.html">Assignments</a></li>
<li><a href="announcements.html">Announcements</a></li>
<li><a href="https://piazza.com/kaust.edu.sa/fall2017/cs240/home">Q & A</a></li>
</ul>
</div>
<h2>Introduction</h2>
<p>
This is the first of two assignments in which you'll build a
fault-tolerant key/value storage system. You'll start in this
assignment by implementing Raft, a replicated state machine protocol.
You will start by implementing the leader election features of Raft,
and then you will complete Raft's log consensus agreement features.
You will implement Raft as a Go object with associated methods,
available to be used as a module in a larger service. Once you have
completed Raft, the last course assignment will conclude with such a
service: a key/value service built on top of Raft.
</p>
<h2>Raft Overview</h2>
<p>
The Raft protocol is used to manage replica servers for services
that must continue operation in the face of failure (e.g.,
server crashes, broken or flaky networks). The challenge is that,
in the face of these failures, the replicas won't always hold
identical data. The Raft protocol helps sort out what the correct
data is.
</p>
<p>
Raft's basic approach for this is to implement a replicated state
machine. Raft 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 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 is alive again.
</p>
<p>
You should consult the
<a href="papers/raft.pdf">extended Raft paper</a>
and the Raft lecture notes. You may also find this
<a href="http://thesecretlivesofdata.com/raft/">illustrated Raft guide</a>
useful to get a sense of the high-level workings of Raft. For a
wider perspective, have a look at Paxos, Chubby, Paxos Made
Live, Spanner, Zookeeper, Harp, Viewstamped Replication, and
<a href="http://static.usenix.org/event/nsdi11/tech/full_papers/Bolosky.pdf">Bolosky et al.</a>
</p>
<h2>Software</h2>
<p>
You can download a tarball containing the provided code for assignment 3 <a href="assignments/assignment3.tar.gz">here</a>.
For this assignment, we will focus primarily on the code and tests for the Raft implementation in
<tt>src/raft</tt> and the simple RPC-like system in <tt>src/labrpc</tt>. It is worth your while to
read and digest the code in these packages.
</p>
<p>
Before you have implemented anything, your Raft tests will fail, but this behavior is a sign that you
have everything properly configured and are ready to begin:
<pre>
$ cd cs240 # or wherever you unpacked your tarball
$ export GOPATH="$PWD"
$ cd "$GOPATH/src/raft"
$ go test -run Election
Test: initial election ...
--- FAIL: TestInitialElection (5.00s)
config.go:286: expected one leader, got none
Test: election after network failure ...
--- FAIL: TestReElection (5.00s)
config.go:286: expected one leader, got none
FAIL
exit status 1
FAIL raft 10.053s</pre>
</p>
<p>
You should implement Raft by adding code to
<tt>raft/raft.go</tt> (only). In that file you'll find a bit of
skeleton code, plus some examples of how to send and receive
RPCs, and examples of how to save and restore persistent state.
</p>
<h2>Part I: Leader Election</h2>
<p>
You should start by reading the code to determine which
functions are responsible for conducting Raft leader election, if
you haven't already.
</p>
<p>
The natural first task is to fill in the <tt>RequestVoteArgs</tt> and
<tt>RequestVoteReply</tt> structs, and modify
<tt>Make()</tt> to create a background goroutine that
starts an election (by sending out <tt>RequestVote</tt>
RPCs) when it hasn't heard from another peer for a
while. For election to work, you will also need to
implement the <tt>RequestVote()</tt> RPC handler so
that servers will vote for one another.
</p>
<p>
To implement heartbeats, you will need to define an
<tt>AppendEntries</tt> RPC struct (though you will not need
any real payload yet), and have the leader send
them out periodically. You will also have to write an
<tt>AppendEntries</tt> RPC handler method that resets
the election timeout so that other servers don't step
forward as leaders when one has already been elected.
</p>
<p>
Make sure the timers in different Raft peers are not
synchronized. In particular, make sure the election
timeouts don't always fire at the same time, or else
all peers will vote for themselves and no one will
become leader.
</p>
<p>
Your Raft implementation must support the following interface, which
the tester and (eventually) your key/value server will use.
You'll find more details in comments in <tt>raft.go</tt>.
<pre>
// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)
// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)
// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)
// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg</pre>
<p>
A service calls <tt>Make(peers,me,…)</tt> to create a
Raft peer. The peers argument is an array of established RPC
connections, one to each Raft peer (including this one). The
<tt>me</tt> argument is the index of this peer in the peers
array. <tt>Start(command)</tt> asks Raft to start the processing
to append the command to the replicated log. <tt>Start()</tt>
should return immediately, without waiting for for this process
to complete. The service expects your implementation to send an
<tt>ApplyMsg</tt> for each new committed log entry to the
<tt>applyCh</tt> argument to <tt>Make()</tt>.
<p>
Your Raft peers should exchange RPCs using the labrpc Go
package that we provide to you. It is modeled after Go's
<a href="https://golang.org/pkg/net/rpc/">rpc library</a>, but
internally uses Go channels rather than sockets.
<tt>raft.go</tt> contains some example code that sends an RPC
(<tt>sendRequestVote()</tt>) and that handles an incoming RPC
(<tt>RequestVote()</tt>).
</p>
<p>
Implementing leader election and heartbeats (empty
<tt>AppendEntries</tt> calls) should be sufficient for a
single leader to be elected and -- in the absence of failures -- stay the leader,
as well as redetermine leadership after failures.
Once you have this working, you should be
able to pass the two Election "go test" tests:
<pre>
$ go test -run Election
Test: initial election ...
... Passed
Test: election after network failure ...
... Passed
PASS
ok raft7.008s</pre>
</p>
<h2>Part II: Log Consensus</h2>
<p>
While being able to elect a leader is useful, we want to use
Raft to keep a consistent, replicated log of operations. To do
so, we need to have the servers accept client operations
through <tt>Start()</tt>, and insert them into the log. In
Raft, only the leader is allowed to append to the log, and
should disseminate new entries to other servers by including
them in its outgoing <tt>AppendEntries</tt> RPCs.
</p>
<p>
In this lab you'll implement most of the Raft design
described in the extended paper, including saving
persistent state and reading it after a node fails and
then restarts. You will not implement cluster
membership changes (Section 6) or log compaction /
snapshotting (Section 7).
</p>
<p>
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 <em>index numbers</em>.
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.
</p>
<p>
Your first major task is to implement the leader and follower code
to append new log entries.
This will involve implementing <tt>Start()</tt>, completing the
<tt>AppendEntries</tt> RPC structs, sending them, and fleshing
out the <tt>AppendEntry</tt> RPC handler. Your goal should
first be to pass the <tt>TestBasicAgree()</tt> test (in
<tt>test_test.go</tt>). Once you have that working, you should
try to get all the tests before the "basic persistence" test to
pass before moving on.
</p>
<p class="note">
Only RPC may be used for interaction between different Raft
instances. For example, different instances of your Raft
implementation are not allowed to share Go variables.
Your implementation should not use files at all.
</p>
<h2>Part III: Fault Tolerance</h2>
<p>
The next major task is to handle the fault tolerant aspects of the Raft protocol,
making your implementation robust against various kinds of failures. These failures
could include servers not receiving some RPCs and servers that crash and restart.
</p>
<p>
A Raft-based server must be able to pick up where it left off,
and continue if the computer it is running on reboots. This requires
that Raft keep persistent state that survives a reboot (the
paper's Figure 2 mentions which state should be persistent).
</p>
<p>
A “real” implementation would do this by writing
Raft's persistent state to disk each time it changes, and
reading the latest saved state from
disk when restarting after a reboot. Your implementation won't use
the disk; instead, it will save and restore persistent state
from a <tt>Persister</tt> object (see <tt>persister.go</tt>).
Whoever calls <tt>Make()</tt> supplies a <tt>Persister</tt>
that initially holds Raft's most recently persisted state (if
any). Raft should initialize its state from that
<tt>Persister</tt>, and should use it to save its persistent
state each time the state changes. You can use the
<tt>ReadRaftState()</tt> and <tt>SaveRaftState()</tt> methods
for this respectively.
</p>
<p class="todo">
Implement persistence by first adding code to serialize any
state that needs persisting in <tt>persist()</tt>, and to
unserialize that same state in <tt>readPersist()</tt>. You now
need to determine at what points in the Raft protocol your
servers are required to persist their state, and insert calls
to <tt>persist()</tt> in those places. Once this code is
complete, you should pass the remaining tests. You may want to
first try and pass the "basic persistence" test (<tt>go test
-run 'TestPersist1$'</tt>), and then tackle the remaining ones.
</p>
<p class="note">
You will need to encode the state as an array of bytes in order
to pass it to the <tt>Persister</tt>; <tt>raft.go</tt> contains
some example code for this in <tt>persist()</tt> and
<tt>readPersist()</tt>.
</p>
<p>
In order to pass some of the challenging tests towards the end, such as
those marked "unreliable", you will need to implement the optimization to
allow a follower to back up the leader's nextIndex by more than one entry
at a time. See the description in the
<a href="../papers/raft-extended.pdf">extended Raft paper</a> starting at
the bottom of page 7 and top of page 8 (marked by a gray line).
</p>
<h2>Resources and Advice</h2>
<ul class="hints">
<li>
Start early. Although the amount of code to implement
isn't large, getting it to work correctly will be very
challenging. Both the algorithm and the code is tricky
and there are many corner cases to consider. When one
of the tests fails, it may take a bit of puzzling to
understand in what scenario your solution isn't
correct, and how to fix your solution.
</li>
<li>
Read and understand the
<a href="papers/raft.pdf">extended Raft paper</a>
and the Raft lecture notes before you start. Your
implementation should follow the paper's description
closely, since that's what the tests expect. Figure 2 may
be useful as a pseudocode reference.
</li>
<li>
Add any state you need to keep to the <tt>Raft</tt>
struct in <tt>raft.go</tt>. Figure 2 in the paper may
provide a good guideline.
</li>
<li>
Remember that the field names any structures you will
be sending over RPC (e.g. information about each log entry)
must start with capital letters, as must the field names in
any structure passed inside an RPC.
</li>
<li>
Similarly to how the RPC system only sends structure
field names that begin with upper-case letters, and
silently ignores fields whose names start with
lower-case letters, the GOB encoder you'll use to save
persistent state only saves fields whose names start
with upper case letters. This is a common source of
mysterious bugs, since Go doesn't warn you.
</li>
<li>
While the Raft leader is the only server that causes
entries to be appended to the log, all the servers need
to independently give newly committed entries to their local service
replica (via their own <tt>applyCh</tt>). Because of this, you
should try to keep these two activities as separate as
possible.
</li>
<li>
It is possible to figure out the minimum number of messages Raft should
use when reaching agreement in non-failure cases. You should make your
implementation use that minimum.
</li>
<li>
In order to avoid running out of memory, Raft must periodically
discard old log entries, but you <strong>do not</strong> have
to worry about garbage collecting the log.
</li>
</ul>
<h2>Submission</h2>
<p>
Submit your code via blackboard <a href="https://blackboard.kaust.edu.sa">CS240 Assignment 3</a>. We expect your submission to only contain <tt>raft.go</tt>.
You may submit multiple times, only the one in blackboard at the time of grading will be recorded.
</p>
<p>
Before submitting, please run the full tests given above for each part one final time. <b>You</b> are responsible for making sure your code works.
</p>
<p>
You will receive full credit for Part I, the leader election component, if your software passes
the Election tests (as run by the <tt>go test</tt> commands above) on our servers.
You will receive full credit for Part II if your software passes the tests mentioned for that section on our servers.
You will receive full credit for Part III if your software passes the tests mentioned for that section on our servers.
</p>
<p>
The final portion of your credit is determined by code quality tests, using the standard tools <tt>gofmt</tt> and <tt>go vet</tt>.
You will receive full credit for this portion if all files submitted conform to the style standards set by <tt>gofmt</tt> and the report from <tt>go vet</tt> is clean for your mapreduce package (that is, produces no errors).
If your code does not pass the <tt>gofmt</tt> test, you should reformat your code using the tool. You can also use the <a href="https://github.com/qiniu/checkstyle">Go Checkstyle</a> tool for advice to improve your code's style, if applicable. Additionally, though not part of the graded cheks, it would also be advisable to produce code that complies with <a href="https://github.com/golang/lint">Golint</a> where possible.
</p>
<h2>Acknowledgements</h2>
<p>This assignment is adapted from Princeton's COS-418, and previously from MIT's 6.824 course. Thanks to Mike Freedman, Frans Kaashoek, Robert Morris, and Nickolai Zeldovich for their support.</p>
<hr />
<p class="lastupdated">Last updated: 2017-10-15 15:57:30</p>
</body>
</html>