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("join request from " << m << "; last=(" << last.vid << "," << last.seqno << "), mylast=(" <<
 450             last_myvs.vid << "," << last_myvs.seqno << ")");
 451     if (cfg->ismember(m, vid_commit)) {
 452         LOG(m << " is still a member -- nothing to do");
 453         log = cfg->dump();
 454     } else if (cfg->myaddr() != primary) {
 455         LOG("but I, " << cfg->myaddr() << ", am not the primary, " << primary << "!");
 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         LOG("calling down to config layer");
 461         unsigned vid_cache = vid_commit;
 462         bool succ;
 463         {
 464             ml.unlock();
 465             succ = cfg->add(m, vid_cache);
 466             ml.lock();
 467         }
 468         if (cfg->ismember(m, cfg->view_id())) {
 469             log = cfg->dump();
 470             LOG("ret " << ret << " log " << log);
 471         } else {
 472             LOG("failed; proposer couldn't add " << succ);
 473             ret = rsm_protocol::BUSY;
 474         }
 475     }
 476     return ret;
 477 }
 478
 479 /*
 480  * RPC handler: Send back all the nodes this local knows about to client
 481  * so the client can switch to a different primary
 482  * when it existing primary fails
 483  */
 484 rsm_client_protocol::status rsm::client_members(std::vector<std::string> &r, int) {
 485     std::vector<std::string> m;
 486     lock ml(rsm_mutex);
 487     cfg->get_view(vid_commit, m);
 488     m.push_back(primary);
 489     r = m;
 490     LOG("rsm::client_members return " << m << " m " << primary);
 491     return rsm_client_protocol::OK;
 492 }
 493
 494 // if primary is member of new view, that node is primary
 495 // otherwise, the lowest number node of the previous view.
 496 // caller should hold rsm_mutex
 497 void rsm::set_primary(unsigned vid) {
 498     std::vector<std::string> c, p;
 499     cfg->get_view(vid, c);
 500     cfg->get_view(vid - 1, p);
 501     VERIFY (c.size() > 0);
 502
 503     if (isamember(primary,c)) {
 504         LOG("set_primary: primary stays " << primary);
 505         return;
 506     }
 507
 508     VERIFY(p.size() > 0);
 509     for (unsigned i = 0; i < p.size(); i++) {
 510         if (isamember(p[i], c)) {
 511             primary = p[i];
 512             LOG("set_primary: primary is " << primary);
 513             return;
 514         }
 515     }
 516     VERIFY(0);
 517 }
 518
 519 bool rsm::amiprimary() {
 520     lock ml(rsm_mutex);
 521     return primary == cfg->myaddr() && !inviewchange;
 522 }
 523
 524
 525 // Testing server
 526
 527 // Simulate partitions
 528
 529 // assumes caller holds rsm_mutex
 530 void rsm::net_repair(bool heal, lock &) {
 531     std::vector<std::string> m;
 532     cfg->get_view(vid_commit, m);
 533     for (unsigned i  = 0; i < m.size(); i++) {
 534         if (m[i] != cfg->myaddr()) {
 535             handle h(m[i]);
 536             LOG("rsm::net_repair: " << m[i] << " " << heal);
 537             if (h.safebind()) h.safebind()->set_reachable(heal);
 538         }
 539     }
 540     rsmrpc->set_reachable(heal);
 541 }
 542
 543 rsm_test_protocol::status rsm::test_net_repairreq(rsm_test_protocol::status &r, int heal) {
 544     lock ml(rsm_mutex);
 545     LOG("rsm::test_net_repairreq: " << heal << " (dopartition " <<
 546             dopartition << ", partitioned " << partitioned << ")");
 547     if (heal) {
 548         net_repair(heal, ml);
 549         partitioned = false;
 550     } else {
 551         dopartition = true;
 552         partitioned = false;
 553     }
 554     r = rsm_test_protocol::OK;
 555     return r;
 556 }
 557
 558 // simulate failure at breakpoint 1 and 2
 559
 560 void rsm::breakpoint1() {
 561     if (break1) {
 562         LOG("Dying at breakpoint 1 in rsm!");
 563         exit(1);
 564     }
 565 }
 566
 567 void rsm::breakpoint2() {
 568     if (break2) {
 569         LOG("Dying at breakpoint 2 in rsm!");
 570         exit(1);
 571     }
 572 }
 573
 574 void rsm::partition1(lock & rsm_mutex_lock) {
 575     if (dopartition) {
 576         net_repair(false, rsm_mutex_lock);
 577         dopartition = false;
 578         partitioned = true;
 579     }
 580 }
 581
 582 rsm_test_protocol::status rsm::breakpointreq(rsm_test_protocol::status &r, int b) {
 583     r = rsm_test_protocol::OK;
 584     lock ml(rsm_mutex);
 585     LOG("rsm::breakpointreq: " << b);
 586     if (b == 1) break1 = true;
 587     else if (b == 2) break2 = true;
 588     else if (b == 3 || b == 4) cfg->breakpoint(b);
 589     else r = rsm_test_protocol::ERR;
 590     return r;
 591 }