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