src/ubik/vote.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afs/param.h>
  11 #include <sys/types.h>
  12 #ifdef AFS_NT40_ENV
  13 #include <winsock2.h>
  14 #else
  15 #include <sys/file.h>
  16 #include <netinet/in.h>
  17 #endif
  18 #include <afs/afsutil.h>
  19 #include <lock.h>
  20 #include <rx/xdr.h>
  21 #include <rx/rx.h>
  22 #include <afs/afsutil.h>
  23 #include <time.h>
  24
  25 #define UBIK_INTERNALS
  26 #include "ubik.h"
  27 #include "ubik_int.h"
  28
  29 /*
  30     General Ubik Goal:
  31     The goal is to provide reliable operation among N servers, such that any
  32     server can crash with the remaining servers continuing operation within a
  33     short period of time.  While a *short* outage is acceptable, this time
  34     should be order of 3 minutes or less.
  35
  36     Theory of operation:
  37
  38     Note: SMALLTIME and BIGTIME are essentially the same time value, separated
  39     only by the clock skew, MAXSKEW.  In general, if you are making guarantees
  40     for someone else, promise them no more than SMALLTIME seconds of whatever
  41     invariant you provide.  If you are waiting to be sure some invariant is now
  42     *false*, wait at least BIGTIME seconds to be sure that SMALLTIME seconds
  43     has passed at the other site.
  44
  45     Now, back to the design:
  46     One site in the collection is a special site, designated the *sync* site.
  47     The sync site sends periodic messages, which can be thought of as
  48     keep-alive messages.  When a non-sync site hears from the sync site, it
  49     knows that it is getting updates for the next SMALLTIME seconds from that
  50     sync site.
  51
  52     If a server does not hear from the sync site in SMALLTIME seconds, it
  53     determines that it no longer is getting updates, and thus refuses to give
  54     out potentially out-of-date data.  If a sync site can not muster a majority
  55     of servers to agree that it is the sync site, then there is a possibility
  56     that a network partition has occurred, allowing another server to claim to
  57     be the sync site.  Thus, any time that the sync site has not heard from a
  58     majority of the servers in the last SMALLTIME seconds, it voluntarily
  59     relinquishes its role as sync site.
  60
  61     While attempting to nominate a new sync site, certain rules apply.  First,
  62     a server can not reply "ok" (return 1 from ServBeacon) to two different
  63     hosts in less than BIGTIME seconds; this allows a server that has heard
  64     affirmative replies from a majority of the servers to know that no other
  65     server in the network has heard enough affirmative replies in the last
  66     BIGTIME seconds to become sync site, too.  The variables ubik_lastYesTime
  67     and lastYesHost are used by all servers to keep track of which host they
  68     have last replied affirmatively to, when queried by a potential new sync
  69     site.
  70
  71     Once a sync site has become a sync site, it periodically sends beacon
  72     messages with a parameter of 1, indicating that it already has determined
  73     it is supposed to be the sync site.  The servers treat such a message as a
  74     guarantee that no other site will become sync site for the next SMALLTIME
  75     seconds.  In the interim, these servers can answer a query concerning which
  76     site is the sync site without any communication with any server.  The
  77     variables lastBeaconArrival and lastBeaconHost are used by all servers to
  78     keep track of which sync site has last contacted them.
  79
  80     One complication occurs while nominating a new sync site: each site may be
  81     trying to nominate a different site (based on the value of lastYesHost),
  82     yet we must nominate the smallest host (under some order), to prevent this
  83     process from looping.  The process could loop by having each server give
  84     one vote to another server, but with no server getting a majority of the
  85     votes.  To avoid this, we try to withhold our votes for the server with the
  86     lowest internet address (an easy-to-generate order).  To this effect, we
  87     keep track (in lowestTime and lowestHost) of the lowest server trying to
  88     become a sync site.  We wait for this server unless there is already a sync
  89     site (indicated by ServBeacon's parameter being 1).
  90 */
  91
  92 afs_int32 ubik_debugFlag        = 0;            /* print out debugging messages? */
  93
  94 /* these statics are used by all sites in nominating new sync sites */
  95 afs_int32 ubik_lastYesTime = 0; /* time we sent the last *yes* vote */
  96 static afs_uint32 lastYesHost = 0xffffffff; /* host to which we sent *yes* vote */
  97 /* Next is time sync site began this vote: guarantees sync site until this + SMALLTIME */
  98 static afs_int32 lastYesClaim = 0;
  99 static int lastYesState = 0;    /* did last site we voted for claim to be sync site? */
 100
 101 /* used to guarantee that nomination process doesn't loop */
 102 static afs_int32 lowestTime = 0;
 103 static afs_uint32 lowestHost = 0xffffffff;
 104 static afs_int32 syncTime = 0;
 105 static afs_int32 syncHost = 0;
 106
 107 /* used to remember which dbase version is the one at the sync site (for non-sync sites */
 108 struct ubik_version ubik_dbVersion;     /* sync site's dbase version */
 109 struct ubik_tid ubik_dbTid;             /* sync site's tid, or 0 if none */
 110
 111 /* decide if we should try to become sync site.  The basic rule is that we
 112  * don't run if there is a valid sync site and it ain't us (we have to run if
 113  * it is us, in order to keep our votes).  If there is no sync site, then we
 114  * want to run if we're the lowest numbered host running, otherwise we defer to
 115  * the lowest host.  However, if the lowest host hasn't been heard from for a
 116  * while, then we start running again, in case he crashed.
 117  *
 118  * This function returns true if we should run, and false otherwise.
 119  */
 120 int uvote_ShouldIRun() {
 121     register afs_int32 now;
 122
 123     now = FT_ApproxTime();
 124     if (BIGTIME + ubik_lastYesTime < now) return 1;    /* no valid guy even trying */
 125     if (lastYesState && lastYerHost != ubik_host[0]) return 0; /* other guy is sync site, leave him alone */
 126     if (ntohl((afs_uint32) lastYesHost) < ntohl((afs_uint32) ubik_host[0]))
 127         return 0;    /* if someone is valid and better than us, don't run */
 128     /* otherwise we should run */
 129     return 1;
 130 }
 131
 132 /* Return the current synchronization site, if any.  Simple approach: if the
 133  * last guy we voted yes for claims to be the sync site, then we we're happy to
 134  * use that guy for a sync site until the time his mandate expires.  If the guy
 135  * does not claim to be sync site, then, of course, there's none.
 136  *
 137  * In addition, if we lost the sync, we set urecovery_syncSite to an invalid
 138  * value, indicating that we no longer know which version of the dbase is the
 139  * one we should have.  We'll get a new one when we next hear from the sync
 140  * site.
 141  *
 142  * This function returns 0 or currently valid sync site.  It can return our own
 143  * address, if we're the sync site.
 144  */
 145 afs_int32 uvote_GetSyncSite() {
 146     register afs_int32 now;
 147     register afs_int32 code;
 148
 149     if (!lastYesState) code = 0;
 150     else {
 151         now = FT_ApproxTime();
 152         if (SMALLTIME + lastYesClaim < now) code = 0;    /* last guy timed out */
 153         else code = lastYesHost;
 154     }
 155     return code;
 156 }
 157
 158 /* called by the sync site to handle vote beacons; if aconn is null, this is a
 159  * local call; returns 0 or time whe the vote was sent.  It returns 0 if we are
 160  * not voting for this sync site, or the time we actually voted yes, if
 161  * non-zero.
 162  */
 163 SVOTE_Beacon(rxcall, astate, astart, avers, atid)
 164     register struct rx_call *rxcall;
 165     afs_int32 astate;
 166     struct ubik_version *avers;
 167     struct ubik_tid *atid;
 168     afs_int32 astart;
 169 {
 170     register afs_int32 otherHost;
 171     register afs_int32 now;
 172     afs_int32 vote;
 173     struct rx_connection *aconn;
 174     struct rx_peer *rxp;
 175     struct ubik_server *ts;
 176     int isClone = 0;
 177
 178     now = FT_ApproxTime();                      /* close to current time */
 179     if (rxcall) {                               /* caller's host */
 180         aconn = rx_ConnectionOf(rxcall);
 181         rxp = rx_PeerOf(aconn);
 182         otherHost = rx_HostOf(rxp);
 183
 184                 /* get the primary interface address for this host.  */
 185                 /* This is the identifier that ubik uses. */
 186         otherHost = ubikGetPrimaryInterfaceAddr(otherHost);
 187         if ( !otherHost )
 188         {
 189                 ubik_dprint("Received beacon from unknown host %s\n",
 190                                         afs_inet_ntoa(rx_HostOf(rxp)));
 191                 return 0; /* I don't know about you: vote no */
 192         }
 193         for (ts = ubik_servers; ts; ts = ts->next) {
 194             if (ts->addr[0] == otherHost) break;
 195         }
 196         if (!ts) ubik_dprint("Unknown host %x has sent a beacon\n", otherHost);
 197         if (ts && ts->isClone) isClone = 1;
 198     } else {
 199         otherHost = ubik_host[0];                       /* this host */
 200         isClone = amIClone;
 201     }
 202
 203     ubik_dprint("Received beacon type %d from host %s\n", astate,
 204                                 afs_inet_ntoa(otherHost));
 205
 206     /* compute the lowest server we've heard from.  We'll try to only vote for
 207        this dude if we don't already have a synchronization site.  Also, don't
 208        let a very old lowestHost confusing things forever.  We pick a new
 209        lowestHost after BIGTIME seconds to limit the damage if this host
 210        actually crashes.  Finally, we also count in this computation: don't
 211        pick someone else if we're even better!
 212
 213        Note that the test below must be <=, not <, so that we keep refreshing
 214        lowestTime.  Otherwise it will look like we haven't heard from
 215        lowestHost in a while and another host could slip in.  */
 216
 217
 218     /* First compute the lowest host we've heard from, whether we want them
 219        for a sync site or not.  If we haven't heard from a site in BIGTIME
 220        seconds, we ignore its presence in lowestHost: it may have crashed.
 221        Note that we don't ever let anyone appear in our lowestHost if we're
 222        lower than them, 'cause we know we're up. */
 223     /* But do not consider clones for lowesHost since they never may become
 224        sync site */
 225     if (!isClone &&
 226         (ntohl((afs_uint32) otherHost) <= ntohl((afs_uint32) lowestHost)
 227         || lowestTime + BIGTIME < now)) {
 228         lowestTime = now;
 229         lowestHost = otherHost;
 230     }
 231     /* why do we need this next check?  Consider the case where each of two
 232        servers decides the other is lowestHost.  Each stops sending beacons
 233        'cause the other is there.  Not obvious that this process terminates:
 234        i.e. each guy could restart procedure and again think other side is
 235        lowest.  Need to prove: if one guy in the system is lowest and knows
 236        he's lowest, these loops don't occur.  because if someone knows he's
 237        lowest, he will send out beacons telling others to vote for him. */
 238     if (!amIClone &&
 239         (ntohl((afs_uint32) ubik_host) <= ntohl((afs_uint32) lowestHost)
 240         || lowestTime + BIGTIME < now)) {
 241         lowestTime = now;
 242         lowestHost = ubik_host[0];
 243     }
 244
 245     /* tell if we've heard from a sync site recently (even if we're not voting
 246        for this dude yet).  After a while, time the guy out. */
 247     if (astate) {   /* this guy is a sync site */
 248         syncHost = otherHost;
 249         syncTime = now;
 250     }
 251     else if (syncTime + BIGTIME < now) {
 252        if (syncHost) {
 253           ubik_dprint("Ubik: Lost contact with sync-site %d.%d.%d.%d (NOT in quorum)\n",
 254                       ((syncHost>>24)&0xff), ((syncHost>>16)&0xff),
 255                       ((syncHost>> 8)&0xff), (syncHost      &0xff));
 256        }
 257        syncHost = 0;
 258     }
 259
 260     /* decide how to vote */
 261     vote = 0;               /* start off voting no */
 262
 263     /* if we this guy isn't a sync site, we don't really have to vote for him.
 264        We get to apply some heuristics to try to avoid weird oscillation sates
 265        in the voting procedure. */
 266     if (astate == 0) {
 267         /* in here only if this guy doesn't claim to be a sync site */
 268
 269         /* lowestHost is also trying for our votes, then just say no. */
 270         if (ntohl(lowestHost) != ntohl(otherHost)) {
 271             return 0;
 272         }
 273
 274         /* someone else *is* a sync site, just say no */
 275         if (syncHost && syncHost != otherHost)
 276             return 0;
 277     } else  /* fast startup if this is the only non-clone */
 278     if (lastYesHost == 0xffffffff && otherHost == ubik_host[0]) {
 279         int i = 0;
 280         for (ts = ubik_servers; ts; ts = ts->next) {
 281             if (ts->addr[0] == otherHost) continue;
 282             if (!ts->isClone) i++;
 283         }
 284         if (!i) lastYesHost = otherHost;
 285     }
 286
 287
 288     if (isClone) return 0; /* clone never can become sync site */
 289
 290     /* Don't promise sync site support to more than one host every BIGTIME
 291        seconds.  This is the heart of our invariants in this system. */
 292     if (ubik_lastYesTime + BIGTIME < now || otherHost == lastYesHost) {
 293         if ((ubik_lastYesTime+BIGTIME < now) ||
 294             (otherHost != lastYesHost) ||
 295             (lastYesState != astate)) {
 296            /* A new vote or a change in the vote or changed quorum */
 297            ubik_dprint("Ubik: vote 'yes' for %d.%d.%d.%d %s\n",
 298                        ((otherHost>>24)&0xff), ((otherHost>>16)&0xff),
 299                        ((otherHost>> 8)&0xff), (otherHost      &0xff),
 300                        (astate?"(in quorum)":"(NOT in quorum)"));
 301         }
 302
 303         vote = now;                 /* vote yes */
 304         ubik_lastYesTime = now;     /* remember when we voted yes */
 305         lastYesClaim = astart;      /* remember for computing when sync site expires */
 306         lastYesHost = otherHost;    /* and who for */
 307         lastYesState = astate;      /* remember if site is a sync site */
 308         ubik_dbVersion = *avers;    /* resync value */
 309         ubik_dbTid = *atid;         /* transaction id, if any, of active trans */
 310         urecovery_CheckTid(atid);   /* check if current write trans needs aborted */
 311     }
 312     return vote;
 313 }
 314
 315 /* handle per-server debug command, where 0 is the first server.  Basic network
 316    debugging hooks. */
 317 SVOTE_SDebug(rxcall, awhich, aparm)
 318     struct rx_call *rxcall;
 319     afs_int32 awhich;
 320     register struct ubik_sdebug *aparm;
 321 {
 322     afs_int32 code, isClone;
 323     code = SVOTE_XSDebug(rxcall, awhich, aparm, &isClone);
 324     return code;
 325 }
 326
 327 SVOTE_XSDebug(rxcall, awhich, aparm, isclone)
 328     afs_int32 *isclone;
 329     struct rx_call *rxcall;
 330     afs_int32 awhich;
 331     register struct ubik_sdebug *aparm;
 332 {
 333     register struct ubik_server *ts;
 334     register int i;
 335     for(ts=ubik_servers; ts; ts=ts->next) {
 336         if (awhich-- == 0) {
 337             /* we're done */
 338             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
 339             for ( i=0; i < UBIK_MAX_INTERFACE_ADDR-1; i++)
 340                 aparm->altAddr[i] = ntohl(ts->addr[i+1]);
 341             aparm->lastVoteTime = ts->lastVoteTime;
 342             aparm->lastBeaconSent = ts->lastBeaconSent;
 343             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
 344             aparm->lastVote = ts->lastVote;
 345             aparm->up = ts->up;
 346             aparm->beaconSinceDown = ts->beaconSinceDown;
 347             aparm->currentDB = ts->currentDB;
 348             *isclone = ts->isClone;
 349             return 0;
 350         }
 351     }
 352     return 2;
 353 }
 354
 355 SVOTE_XDebug(rxcall, aparm, isclone)
 356     struct rx_call *rxcall;
 357     register struct ubik_debug *aparm;
 358     afs_int32 *isclone;
 359 {
 360     afs_int32 code;
 361
 362     code = SVOTE_Debug(rxcall, aparm);
 363     *isclone = amIClone;
 364     return code;
 365 }
 366
 367 /* handle basic network debug command.  This is the global state dumper */
 368 SVOTE_Debug(rxcall, aparm)
 369     struct rx_call *rxcall;
 370     register struct ubik_debug *aparm; {
 371     int  i;
 372     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
 373      * integers in host order. */
 374
 375     aparm->now = FT_ApproxTime();
 376     aparm->lastYesTime = ubik_lastYesTime;
 377     aparm->lastYesHost = ntohl(lastYesHost);
 378     aparm->lastYesState = lastYesState;
 379     aparm->lastYesClaim = lastYesClaim;
 380     aparm->lowestHost = ntohl(lowestHost);
 381     aparm->lowestTime = lowestTime;
 382     aparm->syncHost = ntohl(syncHost);
 383     aparm->syncTime = syncTime;
 384
 385     /* fill in all interface addresses of myself in hostbyte order */
 386     for ( i=0; i < UBIK_MAX_INTERFACE_ADDR; i++)
 387         aparm->interfaceAddr[i] = ntohl(ubik_host[i]);
 388
 389     aparm->amSyncSite = ubik_amSyncSite;
 390     ubeacon_Debug(aparm);
 391
 392     udisk_Debug(aparm);
 393
 394     ulock_Debug(aparm);
 395
 396     /* Get the recovery state. The label of the database may not have
 397      * been written yet but set the flag so udebug behavior remains.
 398      * Defect 9477.
 399      */
 400     aparm->recoveryState = urecovery_state;
 401     if ((urecovery_state & UBIK_RECSYNCSITE) &&
 402         (urecovery_state & UBIK_RECFOUNDDB ) &&
 403         (urecovery_state & UBIK_RECHAVEDB  ) ) {
 404        aparm->recoveryState |= UBIK_RECLABELDB;
 405     }
 406     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
 407     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
 408     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
 409     aparm->tidCounter = ubik_dbase->tidCounter;
 410
 411     if (ubik_currentTrans) {
 412         aparm->currentTrans = 1;
 413         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
 414         else aparm->writeTrans = 0;
 415     }
 416     else {
 417         aparm->currentTrans = 0;
 418     }
 419
 420     aparm->epochTime = ubik_epochTime;
 421
 422     return 0;
 423 }
 424
 425 SVOTE_SDebugOld(rxcall, awhich, aparm)
 426     struct rx_call *rxcall;
 427     afs_int32 awhich;
 428     register struct ubik_sdebug_old *aparm; {
 429     register struct ubik_server *ts;
 430     register int i;
 431     for(ts=ubik_servers; ts; ts=ts->next) {
 432         if (awhich-- == 0) {
 433             /* we're done */
 434             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
 435             aparm->lastVoteTime = ts->lastVoteTime;
 436             aparm->lastBeaconSent = ts->lastBeaconSent;
 437             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
 438             aparm->lastVote = ts->lastVote;
 439             aparm->up = ts->up;
 440             aparm->beaconSinceDown = ts->beaconSinceDown;
 441             aparm->currentDB = ts->currentDB;
 442             return 0;
 443         }
 444     }
 445     return 2;
 446 }
 447
 448
 449 /* handle basic network debug command.  This is the global state dumper */
 450 SVOTE_DebugOld(rxcall, aparm)
 451     struct rx_call *rxcall;
 452     register struct ubik_debug_old *aparm; {
 453     int  i;
 454     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
 455      * integers in host order. */
 456
 457     aparm->now = FT_ApproxTime();
 458     aparm->lastYesTime = ubik_lastYesTime;
 459     aparm->lastYesHost = ntohl(lastYesHost);
 460     aparm->lastYesState = lastYesState;
 461     aparm->lastYesClaim = lastYesClaim;
 462     aparm->lowestHost = ntohl(lowestHost);
 463     aparm->lowestTime = lowestTime;
 464     aparm->syncHost = ntohl(syncHost);
 465     aparm->syncTime = syncTime;
 466
 467     aparm->amSyncSite = ubik_amSyncSite;
 468     ubeacon_Debug(aparm);
 469
 470     udisk_Debug(aparm);
 471
 472     ulock_Debug(aparm);
 473
 474     /* Get the recovery state. The label of the database may not have
 475      * been written yet but set the flag so udebug behavior remains.
 476      * Defect 9477.
 477      */
 478     aparm->recoveryState = urecovery_state;
 479     if ((urecovery_state & UBIK_RECSYNCSITE) &&
 480         (urecovery_state & UBIK_RECFOUNDDB ) &&
 481         (urecovery_state & UBIK_RECHAVEDB  ) ) {
 482        aparm->recoveryState |= UBIK_RECLABELDB;
 483     }
 484     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
 485     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
 486     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
 487     aparm->tidCounter = ubik_dbase->tidCounter;
 488
 489     if (ubik_currentTrans) {
 490         aparm->currentTrans = 1;
 491         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
 492         else aparm->writeTrans = 0;
 493     }
 494     else {
 495         aparm->currentTrans = 0;
 496     }
 497
 498     aparm->epochTime = ubik_epochTime;
 499
 500     return 0;
 501 }
 502
 503
 504 /* get the sync site; called by remote servers to find where they should go */
 505 SVOTE_GetSyncSite(rxcall, ahost)
 506     register struct rx_call *rxcall;
 507     register afs_int32 *ahost; {
 508     register afs_int32 temp;
 509
 510     temp = uvote_GetSyncSite();
 511     *ahost = ntohl(temp);
 512     return 0;
 513 }
 514
 515 ubik_dprint(a,b,c,d,e,f,g,h)
 516     char *a, *b, *c, *d, *e, *f, *g, *h; {
 517     ViceLog(5, (a,b,c,d,e,f,g,h));
 518 }
 519
 520 ubik_print(a,b,c,d,e,f,g,h)
 521   char *a, *b, *c, *d, *e, *f, *g, *h;
 522 {
 523   ViceLog(0, (a,b,c,d,e,f,g,h));
 524 }
 525
 526 /* called once/run to init the vote module */
 527 uvote_Init() {
 528     /* pretend we just voted for someone else, since we just restarted */
 529     ubik_lastYesTime = FT_ApproxTime();
 530     return 0;
 531 }