2 // Replicated state machine implementation with a primary and several
3 // backups. The primary receives requests, assigns each a view stamp (a
4 // vid, and a sequence number) in the order of reception, and forwards
5 // them to all backups. A backup executes requests in the order that
6 // the primary stamps them and replies with an OK to the primary. The
7 // primary executes the request after it receives OKs from all backups,
8 // and sends the reply back to the client.
10 // The config module will tell the RSM about a new view. If the
11 // primary in the previous view is a member of the new view, then it
12 // will stay the primary. Otherwise, the smallest numbered node of
13 // the previous view will be the new primary. In either case, the new
14 // primary will be a node from the previous view. The configuration
15 // module constructs the sequence of views for the RSM and the RSM
16 // ensures there will be always one primary, who was a member of the
19 // When a new node starts, the recovery thread is in charge of joining
20 // the RSM. It will collect the internal RSM state from the primary;
21 // the primary asks the config module to add the new node and returns
22 // to the joining the internal RSM state (e.g., paxos log). Since
23 // there is only one primary, all joins happen in well-defined total
26 // The recovery thread also runs during a view change (e.g, when a node
27 // has failed). After a failure some of the backups could have
28 // processed a request that the primary has not, but those results are
29 // not visible to clients (since the primary responds). If the
30 // primary of the previous view is in the current view, then it will
31 // be the primary and its state is authoritive: the backups download
32 // from the primary the current state. A primary waits until all
33 // backups have downloaded the state. Once the RSM is in sync, the
34 // primary accepts requests again from clients. If one of the backups
35 // is the new primary, then its state is authoritative. In either
36 // scenario, the next view uses a node as primary that has the state
37 // resulting from processing all acknowledged client requests.
38 // Therefore, if the nodes sync up before processing the next request,
39 // the next view will have the correct state.
41 // While the RSM in a view change (i.e., a node has failed, a new view
42 // has been formed, but the sync hasn't completed), another failure
43 // could happen, which complicates a view change. During syncing the
44 // primary or backups can timeout, and initiate another Paxos round.
45 // There are 2 variables that RSM uses to keep track in what state it
47 // - inviewchange: a node has failed and the RSM is performing a view change
48 // - insync: this node is syncing its state
50 // If inviewchange is false and a node is the primary, then it can
51 // process client requests. If it is true, clients are told to retry
52 // later again. While inviewchange is true, the RSM may go through several
53 // member list changes, one by one. After a member list
54 // change completes, the nodes tries to sync. If the sync complets,
55 // the view change completes (and inviewchange is set to false). If
56 // the sync fails, the node may start another member list change
57 // (inviewchange = true and insync = false).
59 // The implementation should be used only with servers that run all
60 // requests run to completion; in particular, a request shouldn't
61 // block. If a request blocks, the backup won't respond to the
62 // primary, and the primary won't execute the request. A request may
63 // send an RPC to another host, but the RPC should be a one-way
64 // message to that host; the backup shouldn't do anything based on the
65 // response or execute after the response, because it is not
66 // guaranteed that all backup will receive the same response and
67 // execute in the same order.
69 // The implementation can be viewed as a layered system:
70 // RSM module ---- in charge of replication
71 // config module ---- in charge of view management
72 // Paxos module ---- in charge of running Paxos to agree on a value
74 // Each module has threads and internal locks. Furthermore, a thread
75 // may call down through the layers (e.g., to run Paxos's proposer).
76 // When Paxos's acceptor accepts a new value for an instance, a thread
77 // will invoke an upcall to inform higher layers of the new value.
78 // The rule is that a module releases its internal locks before it
79 // upcalls, but can keep its locks when calling down.
81 #include <sys/types.h>
87 #include "rsm_client.h"
89 rsm::rsm(string _first, string _me) :
90 stf(0), primary(_first), insync (false), inviewchange (true), vid_commit(0),
91 partitioned (false), dopartition(false), break1(false), break2(false)
93 cfg = new config(_first, _me, this);
96 // Commit the first view here. We can not have acceptor::acceptor
97 // do the commit, since at that time this->cfg is not initialized
100 rsmrpc = cfg->get_rpcs();
101 rsmrpc->reg(rsm_client_protocol::invoke, &rsm::client_invoke, this);
102 rsmrpc->reg(rsm_client_protocol::members, &rsm::client_members, this);
103 rsmrpc->reg(rsm_protocol::invoke, &rsm::invoke, this);
104 rsmrpc->reg(rsm_protocol::transferreq, &rsm::transferreq, this);
105 rsmrpc->reg(rsm_protocol::transferdonereq, &rsm::transferdonereq, this);
106 rsmrpc->reg(rsm_protocol::joinreq, &rsm::joinreq, this);
108 // tester must be on different port, otherwise it may partition itself
109 testsvr = new rpcs((in_port_t)stoi(_me) + 1);
110 testsvr->reg(rsm_test_protocol::net_repair, &rsm::test_net_repairreq, this);
111 testsvr->reg(rsm_test_protocol::breakpoint, &rsm::breakpointreq, this);
115 thread(&rsm::recovery, this).detach();
119 void rsm::reg1(int proc, handler *h) {
124 // The recovery thread runs this function
125 void rsm::recovery() [[noreturn]] {
130 while (!cfg->ismember(cfg->myaddr(), vid_commit)) {
131 // XXX iannucci 2013/09/15 -- I don't understand whether accessing
132 // cfg->view_id in this manner involves a race. I suspect not.
133 if (join(primary, ml)) {
134 LOG("recovery: joined");
135 commit_change(cfg->view_id(), ml);
138 this_thread::sleep_for(seconds(30)); // XXX make another node in cfg primary?
142 vid_insync = vid_commit;
143 LOG("recovery: sync vid_insync " << vid_insync);
144 if (primary == cfg->myaddr()) {
145 r = sync_with_backups(ml);
147 r = sync_with_primary(ml);
149 LOG("recovery: sync done");
151 // If there was a commited viewchange during the synchronization, restart
153 if (vid_insync != vid_commit)
157 myvs.vid = vid_commit;
159 inviewchange = false;
161 LOG("recovery: go to sleep " << insync << " " << inviewchange);
162 recovery_cond.wait(ml);
166 bool rsm::sync_with_backups(lock & rsm_mutex_lock) {
167 rsm_mutex_lock.unlock();
169 // Make sure that the state of lock_server is stable during
170 // synchronization; otherwise, the primary's state may be more recent
171 // than replicas after the synchronization.
172 lock invoke_mutex_lock(invoke_mutex);
173 // By acquiring and releasing the invoke_mutex once, we make sure that
174 // the state of lock_server will not be changed until all
175 // replicas are synchronized. The reason is that client_invoke arrives
176 // after this point of time will see inviewchange == true, and returns
179 rsm_mutex_lock.lock();
180 // Start accepting synchronization request (statetransferreq) now!
182 cfg->get_view(vid_insync, backups);
183 backups.erase(find(backups.begin(), backups.end(), cfg->myaddr()));
184 LOG("rsm::sync_with_backups " << backups);
185 sync_cond.wait(rsm_mutex_lock);
191 bool rsm::sync_with_primary(lock & rsm_mutex_lock) {
192 // Remember the primary of vid_insync
194 while (vid_insync == vid_commit) {
195 if (statetransfer(m, rsm_mutex_lock))
198 return statetransferdone(m, rsm_mutex_lock);
203 * Call to transfer state from m to the local node.
204 * Assumes that rsm_mutex is already held.
206 bool rsm::statetransfer(string m, lock & rsm_mutex_lock)
208 rsm_protocol::transferres r;
211 LOG("rsm::statetransfer: contact " << m << " w. my last_myvs(" << last_myvs.vid << "," << last_myvs.seqno << ")");
214 rsm_mutex_lock.unlock();
217 ret = cl->call_timeout(rsm_protocol::transferreq, rpcc::to(1000),
218 r, cfg->myaddr(), last_myvs, vid_insync);
220 rsm_mutex_lock.lock();
222 if (cl == 0 || ret != rsm_protocol::OK) {
223 LOG("rsm::statetransfer: couldn't reach " << m << " " << hex << cl << " " << dec << ret);
226 if (stf && last_myvs != r.last) {
227 stf->unmarshal_state(r.state);
230 LOG("rsm::statetransfer transfer from " << m << " success, vs(" << last_myvs.vid << "," << last_myvs.seqno << ")");
234 bool rsm::statetransferdone(string m, lock & rsm_mutex_lock) {
235 rsm_mutex_lock.unlock();
237 rpcc *cl = h.safebind();
241 auto ret = (rsm_protocol::status)cl->call(rsm_protocol::transferdonereq, r, cfg->myaddr(), vid_insync);
242 done = (ret == rsm_protocol::OK);
244 rsm_mutex_lock.lock();
249 bool rsm::join(string m, lock & rsm_mutex_lock) {
254 LOG("rsm::join: " << m << " mylast (" << last_myvs.vid << "," << last_myvs.seqno << ")");
257 rsm_mutex_lock.unlock();
260 ret = cl->call_timeout(rsm_protocol::joinreq, rpcc::to(120000), log,
261 cfg->myaddr(), last_myvs);
263 rsm_mutex_lock.lock();
266 if (cl == 0 || ret != rsm_protocol::OK) {
267 LOG("rsm::join: couldn't reach " << m << " " << hex << cl << " " << dec << ret);
270 LOG("rsm::join: succeeded " << log);
276 * Config informs rsm whenever it has successfully
277 * completed a view change
279 void rsm::commit_change(unsigned vid) {
281 commit_change(vid, ml);
282 if (cfg->ismember(cfg->myaddr(), vid_commit))
286 void rsm::commit_change(unsigned vid, lock &) {
287 if (vid <= vid_commit)
289 LOG("commit_change: new view (" << vid << ") last vs (" << last_myvs.vid << "," <<
290 last_myvs.seqno << ") " << primary << " insync " << insync);
294 recovery_cond.notify_one();
295 sync_cond.notify_one();
296 if (cfg->ismember(cfg->myaddr(), vid_commit))
301 void rsm::execute(int procno, string req, string &r) {
303 handler *h = procs[procno];
305 unmarshall args(req, false);
308 auto ret = (rsm_protocol::status)(*h)(args, rep);
311 rep1 << rep.content();
316 // Clients call client_invoke to invoke a procedure on the replicated state
317 // machine: the primary receives the request, assigns it a sequence
318 // number, and invokes it on all members of the replicated state
321 rsm_client_protocol::status rsm::client_invoke(string &r, int procno, string req) {
322 LOG("rsm::client_invoke: procno 0x" << hex << procno);
323 lock ml(invoke_mutex);
329 LOG("Checking for inviewchange");
331 return rsm_client_protocol::BUSY;
332 LOG("Checking for primacy");
333 myaddr = cfg->myaddr();
334 if (primary != myaddr)
335 return rsm_client_protocol::NOTPRIMARY;
336 LOG("Assigning a viewstamp");
337 cfg->get_view(vid_commit, m);
338 // assign the RPC the next viewstamp number
343 // send an invoke RPC to all slaves in the current view with a timeout of 1 second
344 LOG("Invoking slaves");
345 for (unsigned i = 0; i < m.size(); i++) {
346 if (m[i] != myaddr) {
347 // if invoke on slave fails, return rsm_client_protocol::BUSY
349 LOG("Sending invoke to " << m[i]);
350 rpcc *cl = h.safebind();
352 return rsm_client_protocol::BUSY;
354 auto ret = (rsm_protocol::status)cl->call_timeout(rsm_protocol::invoke, rpcc::to(1000), ignored_rval, procno, vs, req);
355 LOG("Invoke returned " << ret);
356 if (ret != rsm_protocol::OK)
357 return rsm_client_protocol::BUSY;
359 lock rsm_mutex_lock(rsm_mutex);
360 partition1(rsm_mutex_lock);
363 execute(procno, req, r);
365 return rsm_client_protocol::OK;
369 // The primary calls the internal invoke at each member of the
370 // replicated state machine
372 // the replica must execute requests in order (with no gaps)
373 // according to requests' seqno
375 rsm_protocol::status rsm::invoke(int &, int proc, viewstamp vs, string req) {
376 LOG("rsm::invoke: procno 0x" << hex << proc);
377 lock ml(invoke_mutex);
382 // check if !inviewchange
383 LOG("Checking for view change");
385 return rsm_protocol::ERR;
387 LOG("Checking for slave status");
388 myaddr = cfg->myaddr();
389 if (primary == myaddr)
390 return rsm_protocol::ERR;
391 cfg->get_view(vid_commit, m);
392 if (find(m.begin(), m.end(), myaddr) == m.end())
393 return rsm_protocol::ERR;
394 // check sequence number
395 LOG("Checking sequence number");
397 return rsm_protocol::ERR;
401 execute(proc, req, r);
404 return rsm_protocol::OK;
408 * RPC handler: Send back the local node's state to the caller
410 rsm_protocol::status rsm::transferreq(rsm_protocol::transferres &r, string src,
411 viewstamp last, unsigned vid) {
413 LOG("transferreq from " << src << " (" << last.vid << "," << last.seqno << ") vs (" <<
414 last_myvs.vid << "," << last_myvs.seqno << ")");
415 if (!insync || vid != vid_insync)
416 return rsm_protocol::BUSY;
417 if (stf && last != last_myvs)
418 r.state = stf->marshal_state();
420 return rsm_protocol::OK;
424 * RPC handler: Inform the local node (the primary) that node m has synchronized
427 rsm_protocol::status rsm::transferdonereq(int &, string m, unsigned vid) {
429 if (!insync || vid != vid_insync)
430 return rsm_protocol::BUSY;
431 backups.erase(find(backups.begin(), backups.end(), m));
433 sync_cond.notify_one();
434 return rsm_protocol::OK;
437 // a node that wants to join an RSM as a server sends a
438 // joinreq to the RSM's current primary; this is the
439 // handler for that RPC.
440 rsm_protocol::status rsm::joinreq(string & log, string m, viewstamp last) {
441 auto ret = rsm_protocol::OK;
444 LOG("join request from " << m << "; last=(" << last.vid << "," << last.seqno << "), mylast=(" <<
445 last_myvs.vid << "," << last_myvs.seqno << ")");
446 if (cfg->ismember(m, vid_commit)) {
447 LOG(m << " is still a member -- nothing to do");
449 } else if (cfg->myaddr() != primary) {
450 LOG("but I, " << cfg->myaddr() << ", am not the primary, " << primary << "!");
451 ret = rsm_protocol::BUSY;
453 // We cache vid_commit to avoid adding m to a view which already contains
454 // m due to race condition
455 LOG("calling down to config layer");
456 unsigned vid_cache = vid_commit;
460 succ = cfg->add(m, vid_cache);
463 if (cfg->ismember(m, cfg->view_id())) {
465 LOG("ret " << ret << " log " << log);
467 LOG("failed; proposer couldn't add " << succ);
468 ret = rsm_protocol::BUSY;
475 * RPC handler: Send back all the nodes this local knows about to client
476 * so the client can switch to a different primary
477 * when it existing primary fails
479 rsm_client_protocol::status rsm::client_members(vector<string> &r, int) {
482 cfg->get_view(vid_commit, m);
483 m.push_back(primary);
485 LOG("rsm::client_members return " << m << " m " << primary);
486 return rsm_client_protocol::OK;
489 // if primary is member of new view, that node is primary
490 // otherwise, the lowest number node of the previous view.
491 // caller should hold rsm_mutex
492 void rsm::set_primary(unsigned vid) {
494 cfg->get_view(vid, c);
495 cfg->get_view(vid - 1, p);
496 VERIFY (c.size() > 0);
498 if (isamember(primary,c)) {
499 LOG("set_primary: primary stays " << primary);
503 VERIFY(p.size() > 0);
504 for (unsigned i = 0; i < p.size(); i++) {
505 if (isamember(p[i], c)) {
507 LOG("set_primary: primary is " << primary);
514 bool rsm::amiprimary() {
516 return primary == cfg->myaddr() && !inviewchange;
522 // Simulate partitions
524 // assumes caller holds rsm_mutex
525 void rsm::net_repair(bool heal, lock &) {
527 cfg->get_view(vid_commit, m);
528 for (unsigned i = 0; i < m.size(); i++) {
529 if (m[i] != cfg->myaddr()) {
531 LOG("rsm::net_repair: " << m[i] << " " << heal);
532 if (h.safebind()) h.safebind()->set_reachable(heal);
535 rsmrpc->set_reachable(heal);
538 rsm_test_protocol::status rsm::test_net_repairreq(rsm_test_protocol::status &r, int heal) {
540 LOG("rsm::test_net_repairreq: " << heal << " (dopartition " <<
541 dopartition << ", partitioned " << partitioned << ")");
543 net_repair(heal, ml);
549 r = rsm_test_protocol::OK;
553 // simulate failure at breakpoint 1 and 2
555 void rsm::breakpoint1() {
557 LOG("Dying at breakpoint 1 in rsm!");
562 void rsm::breakpoint2() {
564 LOG("Dying at breakpoint 2 in rsm!");
569 void rsm::partition1(lock & rsm_mutex_lock) {
571 net_repair(false, rsm_mutex_lock);
577 rsm_test_protocol::status rsm::breakpointreq(rsm_test_protocol::status &r, int b) {
578 r = rsm_test_protocol::OK;
580 LOG("rsm::breakpointreq: " << b);
581 if (b == 1) break1 = true;
582 else if (b == 2) break2 = true;
583 else if (b == 3 || b == 4) cfg->breakpoint(b);
584 else r = rsm_test_protocol::ERR;