00cae81e6ea2627b723b5a7dceb95bda472ace1a
[invirt/third/libt4.git] / rsm.cc
1 //
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.
9 //
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
17 // last view.
18 //
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
24 // order.
25 //
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.
40 //
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
46 // is:
47 //    - inviewchange: a node has failed and the RSM is performing a view change
48 //    - insync: this node is syncing its state
49 //
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).
58 //
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.
68 //
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
73 //
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.
80
81 #include <sys/types.h>
82 #include <unistd.h>
83
84 #include "types.h"
85 #include "handle.h"
86 #include "rsm.h"
87 #include "rsm_client.h"
88
89 rsm::rsm(std::string _first, std::string _me) :
90     stf(0), primary(_first), insync (false), inviewchange (true), vid_commit(0),
91     partitioned (false), dopartition(false), break1(false), break2(false)
92 {
93     last_myvs.vid = 0;
94     last_myvs.seqno = 0;
95     myvs = last_myvs;
96     myvs.seqno = 1;
97
98     cfg = new config(_first, _me, this);
99
100     if (_first == _me) {
101         // Commit the first view here. We can not have acceptor::acceptor
102         // do the commit, since at that time this->cfg is not initialized
103         commit_change(1);
104     }
105     rsmrpc = cfg->get_rpcs();
106     rsmrpc->reg(rsm_client_protocol::invoke, &rsm::client_invoke, this);
107     rsmrpc->reg(rsm_client_protocol::members, &rsm::client_members, this);
108     rsmrpc->reg(rsm_protocol::invoke, &rsm::invoke, this);
109     rsmrpc->reg(rsm_protocol::transferreq, &rsm::transferreq, this);
110     rsmrpc->reg(rsm_protocol::transferdonereq, &rsm::transferdonereq, this);
111     rsmrpc->reg(rsm_protocol::joinreq, &rsm::joinreq, this);
112
113     // tester must be on different port, otherwise it may partition itself
114     testsvr = new rpcs((uint32_t)std::stoi(_me) + 1);
115     testsvr->reg(rsm_test_protocol::net_repair, &rsm::test_net_repairreq, this);
116     testsvr->reg(rsm_test_protocol::breakpoint, &rsm::breakpointreq, this);
117
118     {
119         lock ml(rsm_mutex);
120         std::thread(&rsm::recovery, this).detach();
121     }
122 }
123
124 void rsm::reg1(int proc, handler *h) {
125     lock ml(rsm_mutex);
126     procs[proc] = h;
127 }
128
129 // The recovery thread runs this function
130 void rsm::recovery() [[noreturn]] {
131     bool r = true;
132     lock ml(rsm_mutex);
133
134     while (1) {
135         while (!cfg->ismember(cfg->myaddr(), vid_commit)) {
136             // XXX iannucci 2013/09/15 -- I don't understand whether accessing
137             // cfg->view_id in this manner involves a race.  I suspect not.
138             if (join(primary, ml)) {
139                 LOG("recovery: joined");
140                 commit_change(cfg->view_id(), ml);
141             } else {
142                 ml.unlock();
143                 std::this_thread::sleep_for(std::chrono::seconds(30)); // XXX make another node in cfg primary?
144                 ml.lock();
145             }
146         }
147         vid_insync = vid_commit;
148         LOG("recovery: sync vid_insync " << vid_insync);
149         if (primary == cfg->myaddr()) {
150             r = sync_with_backups(ml);
151         } else {
152             r = sync_with_primary(ml);
153         }
154         LOG("recovery: sync done");
155
156         // If there was a commited viewchange during the synchronization, restart
157         // the recovery
158         if (vid_insync != vid_commit)
159             continue;
160
161         if (r) {
162             myvs.vid = vid_commit;
163             myvs.seqno = 1;
164             inviewchange = false;
165         }
166         LOG("recovery: go to sleep " << insync << " " << inviewchange);
167         recovery_cond.wait(ml);
168     }
169 }
170
171 bool rsm::sync_with_backups(lock & rsm_mutex_lock) {
172     rsm_mutex_lock.unlock();
173     {
174         // Make sure that the state of lock_server is stable during
175         // synchronization; otherwise, the primary's state may be more recent
176         // than replicas after the synchronization.
177         lock invoke_mutex_lock(invoke_mutex);
178         // By acquiring and releasing the invoke_mutex once, we make sure that
179         // the state of lock_server will not be changed until all
180         // replicas are synchronized. The reason is that client_invoke arrives
181         // after this point of time will see inviewchange == true, and returns
182         // BUSY.
183     }
184     rsm_mutex_lock.lock();
185     // Start accepting synchronization request (statetransferreq) now!
186     insync = true;
187     cfg->get_view(vid_insync, backups);
188     backups.erase(find(backups.begin(), backups.end(), cfg->myaddr()));
189     LOG("rsm::sync_with_backups " << backups);
190     sync_cond.wait(rsm_mutex_lock);
191     insync = false;
192     return true;
193 }
194
195
196 bool rsm::sync_with_primary(lock & rsm_mutex_lock) {
197     // Remember the primary of vid_insync
198     std::string m = primary;
199     while (vid_insync == vid_commit) {
200         if (statetransfer(m, rsm_mutex_lock))
201             break;
202     }
203     return statetransferdone(m, rsm_mutex_lock);
204 }
205
206
207 /**
208  * Call to transfer state from m to the local node.
209  * Assumes that rsm_mutex is already held.
210  */
211 bool rsm::statetransfer(std::string m, lock & rsm_mutex_lock)
212 {
213     rsm_protocol::transferres r;
214     handle h(m);
215     int ret = 0;
216     LOG("rsm::statetransfer: contact " << m << " w. my last_myvs(" << last_myvs.vid << "," << last_myvs.seqno << ")");
217     rpcc *cl;
218     {
219         rsm_mutex_lock.unlock();
220         cl = h.safebind();
221         if (cl) {
222             ret = cl->call_timeout(rsm_protocol::transferreq, rpcc::to(1000),
223                     r, cfg->myaddr(), last_myvs, vid_insync);
224         }
225         rsm_mutex_lock.lock();
226     }
227     if (cl == 0 || ret != rsm_protocol::OK) {
228         LOG("rsm::statetransfer: couldn't reach " << m << " " << std::hex << cl << " " << std::dec << ret);
229         return false;
230     }
231     if (stf && last_myvs != r.last) {
232         stf->unmarshal_state(r.state);
233     }
234     last_myvs = r.last;
235     LOG("rsm::statetransfer transfer from " << m << " success, vs(" << last_myvs.vid << "," << last_myvs.seqno << ")");
236     return true;
237 }
238
239 bool rsm::statetransferdone(std::string m, lock & rsm_mutex_lock) {
240     rsm_mutex_lock.unlock();
241     handle h(m);
242     rpcc *cl = h.safebind();
243     bool done = false;
244     if (cl) {
245         int r;
246         auto ret = (rsm_protocol::status)cl->call(rsm_protocol::transferdonereq, r, cfg->myaddr(), vid_insync);
247         done = (ret == rsm_protocol::OK);
248     }
249     rsm_mutex_lock.lock();
250     return done;
251 }
252
253
254 bool rsm::join(std::string m, lock & rsm_mutex_lock) {
255     handle h(m);
256     int ret = 0;
257     string log;
258
259     LOG("rsm::join: " << m << " mylast (" << last_myvs.vid << "," << last_myvs.seqno << ")");
260     rpcc *cl;
261     {
262         rsm_mutex_lock.unlock();
263         cl = h.safebind();
264         if (cl != 0) {
265             ret = cl->call_timeout(rsm_protocol::joinreq, rpcc::to(120000), log,
266                     cfg->myaddr(), last_myvs);
267         }
268         rsm_mutex_lock.lock();
269     }
270
271     if (cl == 0 || ret != rsm_protocol::OK) {
272         LOG("rsm::join: couldn't reach " << m << " " << std::hex << cl << " " << std::dec << ret);
273         return false;
274     }
275     LOG("rsm::join: succeeded " << log);
276     cfg->restore(log);
277     return true;
278 }
279
280 /*
281  * Config informs rsm whenever it has successfully
282  * completed a view change
283  */
284 void rsm::commit_change(unsigned vid) {
285     lock ml(rsm_mutex);
286     commit_change(vid, ml);
287     if (cfg->ismember(cfg->myaddr(), vid_commit))
288         breakpoint2();
289 }
290
291 void rsm::commit_change(unsigned vid, lock &) {
292     if (vid <= vid_commit)
293         return;
294     LOG("commit_change: new view (" << vid << ") last vs (" << last_myvs.vid << "," <<
295             last_myvs.seqno << ") " << primary << " insync " << insync);
296     vid_commit = vid;
297     inviewchange = true;
298     set_primary(vid);
299     recovery_cond.notify_one();
300     sync_cond.notify_one();
301     if (cfg->ismember(cfg->myaddr(), vid_commit))
302         breakpoint2();
303 }
304
305
306 void rsm::execute(int procno, std::string req, std::string &r) {
307     LOG("execute");
308     handler *h = procs[procno];
309     VERIFY(h);
310     unmarshall args(req);
311     marshall rep;
312     std::string reps;
313     auto ret = (rsm_protocol::status)(*h)(args, rep);
314     marshall rep1;
315     rep1 << ret;
316     rep1 << rep.str();
317     r = rep1.str();
318 }
319
320 //
321 // Clients call client_invoke to invoke a procedure on the replicated state
322 // machine: the primary receives the request, assigns it a sequence
323 // number, and invokes it on all members of the replicated state
324 // machine.
325 //
326 rsm_client_protocol::status rsm::client_invoke(std::string &r, int procno, std::string req) {
327     LOG("rsm::client_invoke: procno 0x" << std::hex << procno);
328     lock ml(invoke_mutex);
329     std::vector<std::string> m;
330     std::string myaddr;
331     viewstamp vs;
332     {
333         lock ml2(rsm_mutex);
334         LOG("Checking for inviewchange");
335         if (inviewchange)
336             return rsm_client_protocol::BUSY;
337         LOG("Checking for primacy");
338         myaddr = cfg->myaddr();
339         if (primary != myaddr)
340             return rsm_client_protocol::NOTPRIMARY;
341         LOG("Assigning a viewstamp");
342         cfg->get_view(vid_commit, m);
343         // assign the RPC the next viewstamp number
344         vs = myvs;
345         myvs++;
346     }
347
348     // send an invoke RPC to all slaves in the current view with a timeout of 1 second
349     LOG("Invoking slaves");
350     for (unsigned i  = 0; i < m.size(); i++) {
351         if (m[i] != myaddr) {
352             // if invoke on slave fails, return rsm_client_protocol::BUSY
353             handle h(m[i]);
354             LOG("Sending invoke to " << m[i]);
355             rpcc *cl = h.safebind();
356             if (!cl)
357                 return rsm_client_protocol::BUSY;
358             int ignored_rval;
359             auto ret = (rsm_protocol::status)cl->call_timeout(rsm_protocol::invoke, rpcc::to(1000), ignored_rval, procno, vs, req);
360             LOG("Invoke returned " << ret);
361             if (ret != rsm_protocol::OK)
362                 return rsm_client_protocol::BUSY;
363             breakpoint1();
364             lock rsm_mutex_lock(rsm_mutex);
365             partition1(rsm_mutex_lock);
366         }
367     }
368     execute(procno, req, r);
369     last_myvs = vs;
370     return rsm_client_protocol::OK;
371 }
372
373 //
374 // The primary calls the internal invoke at each member of the
375 // replicated state machine
376 //
377 // the replica must execute requests in order (with no gaps)
378 // according to requests' seqno
379
380 rsm_protocol::status rsm::invoke(int &, int proc, viewstamp vs, std::string req) {
381     LOG("rsm::invoke: procno 0x" << std::hex << proc);
382     lock ml(invoke_mutex);
383     std::vector<std::string> m;
384     std::string myaddr;
385     {
386         lock ml2(rsm_mutex);
387         // check if !inviewchange
388         LOG("Checking for view change");
389         if (inviewchange)
390             return rsm_protocol::ERR;
391         // check if slave
392         LOG("Checking for slave status");
393         myaddr = cfg->myaddr();
394         if (primary == myaddr)
395             return rsm_protocol::ERR;
396         cfg->get_view(vid_commit, m);
397         if (find(m.begin(), m.end(), myaddr) == m.end())
398             return rsm_protocol::ERR;
399         // check sequence number
400         LOG("Checking sequence number");
401         if (vs != myvs)
402             return rsm_protocol::ERR;
403         myvs++;
404     }
405     std::string r;
406     execute(proc, req, r);
407     last_myvs = vs;
408     breakpoint1();
409     return rsm_protocol::OK;
410 }
411
412 /**
413  * RPC handler: Send back the local node's state to the caller
414  */
415 rsm_protocol::status rsm::transferreq(rsm_protocol::transferres &r, std::string src,
416         viewstamp last, unsigned vid) {
417     lock ml(rsm_mutex);
418     LOG("transferreq from " << src << " (" << last.vid << "," << last.seqno << ") vs (" <<
419             last_myvs.vid << "," << last_myvs.seqno << ")");
420     if (!insync || vid != vid_insync)
421         return rsm_protocol::BUSY;
422     if (stf && last != last_myvs)
423         r.state = stf->marshal_state();
424     r.last = last_myvs;
425     return rsm_protocol::OK;
426 }
427
428 /**
429  * RPC handler: Inform the local node (the primary) that node m has synchronized
430  * for view vid
431  */
432 rsm_protocol::status rsm::transferdonereq(int &, std::string m, unsigned vid) {
433     lock ml(rsm_mutex);
434     if (!insync || vid != vid_insync)
435         return rsm_protocol::BUSY;
436     backups.erase(find(backups.begin(), backups.end(), m));
437     if (backups.empty())
438         sync_cond.notify_one();
439     return rsm_protocol::OK;
440 }
441
442 // a node that wants to join an RSM as a server sends a
443 // joinreq to the RSM's current primary; this is the
444 // handler for that RPC.
445 rsm_protocol::status rsm::joinreq(string & log, std::string m, viewstamp last) {
446     auto ret = rsm_protocol::OK;
447
448     lock ml(rsm_mutex);
449     LOG("joinreq: src " << m << " last (" << last.vid << "," << last.seqno << ") mylast (" <<
450             last_myvs.vid << "," << last_myvs.seqno << ")");
451     if (cfg->ismember(m, vid_commit)) {
452         LOG("joinreq: is still a member");
453         log = cfg->dump();
454     } else if (cfg->myaddr() != primary) {
455         LOG("joinreq: busy");
456         ret = rsm_protocol::BUSY;
457     } else {
458         // We cache vid_commit to avoid adding m to a view which already contains
459         // m due to race condition
460         unsigned vid_cache = vid_commit;
461         bool succ;
462         {
463             ml.unlock();
464             succ = cfg->add(m, vid_cache);
465             ml.lock();
466         }
467         if (cfg->ismember(m, cfg->view_id())) {
468             log = cfg->dump();
469             LOG("joinreq: ret " << ret << " log " << log);
470         } else {
471             LOG("joinreq: failed; proposer couldn't add " << succ);
472             ret = rsm_protocol::BUSY;
473         }
474     }
475     return ret;
476 }
477
478 /*
479  * RPC handler: Send back all the nodes this local knows about to client
480  * so the client can switch to a different primary
481  * when it existing primary fails
482  */
483 rsm_client_protocol::status rsm::client_members(std::vector<std::string> &r, int) {
484     std::vector<std::string> m;
485     lock ml(rsm_mutex);
486     cfg->get_view(vid_commit, m);
487     m.push_back(primary);
488     r = m;
489     LOG("rsm::client_members return " << print_members(m) << " m " << primary);
490     return rsm_client_protocol::OK;
491 }
492
493 // if primary is member of new view, that node is primary
494 // otherwise, the lowest number node of the previous view.
495 // caller should hold rsm_mutex
496 void rsm::set_primary(unsigned vid) {
497     std::vector<std::string> c, p;
498     cfg->get_view(vid, c);
499     cfg->get_view(vid - 1, p);
500     VERIFY (c.size() > 0);
501
502     if (isamember(primary,c)) {
503         LOG("set_primary: primary stays " << primary);
504         return;
505     }
506
507     VERIFY(p.size() > 0);
508     for (unsigned i = 0; i < p.size(); i++) {
509         if (isamember(p[i], c)) {
510             primary = p[i];
511             LOG("set_primary: primary is " << primary);
512             return;
513         }
514     }
515     VERIFY(0);
516 }
517
518 bool rsm::amiprimary() {
519     lock ml(rsm_mutex);
520     return primary == cfg->myaddr() && !inviewchange;
521 }
522
523
524 // Testing server
525
526 // Simulate partitions
527
528 // assumes caller holds rsm_mutex
529 void rsm::net_repair(bool heal, lock &) {
530     std::vector<std::string> m;
531     cfg->get_view(vid_commit, m);
532     for (unsigned i  = 0; i < m.size(); i++) {
533         if (m[i] != cfg->myaddr()) {
534             handle h(m[i]);
535             LOG("rsm::net_repair: " << m[i] << " " << heal);
536             if (h.safebind()) h.safebind()->set_reachable(heal);
537         }
538     }
539     rsmrpc->set_reachable(heal);
540 }
541
542 rsm_test_protocol::status rsm::test_net_repairreq(rsm_test_protocol::status &r, int heal) {
543     lock ml(rsm_mutex);
544     LOG("rsm::test_net_repairreq: " << heal << " (dopartition " <<
545             dopartition << ", partitioned " << partitioned << ")");
546     if (heal) {
547         net_repair(heal, ml);
548         partitioned = false;
549     } else {
550         dopartition = true;
551         partitioned = false;
552     }
553     r = rsm_test_protocol::OK;
554     return r;
555 }
556
557 // simulate failure at breakpoint 1 and 2
558
559 void rsm::breakpoint1() {
560     if (break1) {
561         LOG("Dying at breakpoint 1 in rsm!");
562         exit(1);
563     }
564 }
565
566 void rsm::breakpoint2() {
567     if (break2) {
568         LOG("Dying at breakpoint 2 in rsm!");
569         exit(1);
570     }
571 }
572
573 void rsm::partition1(lock & rsm_mutex_lock) {
574     if (dopartition) {
575         net_repair(false, rsm_mutex_lock);
576         dopartition = false;
577         partitioned = true;
578     }
579 }
580
581 rsm_test_protocol::status rsm::breakpointreq(rsm_test_protocol::status &r, int b) {
582     r = rsm_test_protocol::OK;
583     lock ml(rsm_mutex);
584     LOG("rsm::breakpointreq: " << b);
585     if (b == 1) break1 = true;
586     else if (b == 2) break2 = true;
587     else if (b == 3 || b == 4) cfg->breakpoint(b);
588     else r = rsm_test_protocol::ERR;
589     return r;
590 }