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