fix-ubik-lowest-host-comparison-algorithm-20010403
[openafs.git] / 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[0]) <= 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 %s %s\n",
298                                 afs_inet_ntoa(otherHost),
299                        (astate?"(in quorum)":"(NOT in quorum)"));
300         }
301
302         vote = now;                 /* vote yes */
303         ubik_lastYesTime = now;     /* remember when we voted yes */
304         lastYesClaim = astart;      /* remember for computing when sync site expires */
305         lastYesHost = otherHost;    /* and who for */
306         lastYesState = astate;      /* remember if site is a sync site */
307         ubik_dbVersion = *avers;    /* resync value */
308         ubik_dbTid = *atid;         /* transaction id, if any, of active trans */
309         urecovery_CheckTid(atid);   /* check if current write trans needs aborted */
310     }
311     return vote;
312 }
313
314 /* handle per-server debug command, where 0 is the first server.  Basic network
315    debugging hooks. */
316 SVOTE_SDebug(rxcall, awhich, aparm)
317     struct rx_call *rxcall;
318     afs_int32 awhich;
319     register struct ubik_sdebug *aparm;
320 {
321     afs_int32 code, isClone;
322     code = SVOTE_XSDebug(rxcall, awhich, aparm, &isClone);
323     return code;
324 }
325
326 SVOTE_XSDebug(rxcall, awhich, aparm, isclone)
327     afs_int32 *isclone;
328     struct rx_call *rxcall;
329     afs_int32 awhich;
330     register struct ubik_sdebug *aparm; 
331 {
332     register struct ubik_server *ts;
333     register int i;
334     for(ts=ubik_servers; ts; ts=ts->next) {
335         if (awhich-- == 0) {
336             /* we're done */
337             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
338             for ( i=0; i < UBIK_MAX_INTERFACE_ADDR-1; i++)
339                 aparm->altAddr[i] = ntohl(ts->addr[i+1]);
340             aparm->lastVoteTime = ts->lastVoteTime;
341             aparm->lastBeaconSent = ts->lastBeaconSent;
342             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
343             aparm->lastVote = ts->lastVote;
344             aparm->up = ts->up;
345             aparm->beaconSinceDown = ts->beaconSinceDown;
346             aparm->currentDB = ts->currentDB;
347             *isclone = ts->isClone;
348             return 0;
349         }
350     }
351     return 2;
352 }
353
354 SVOTE_XDebug(rxcall, aparm, isclone)
355     struct rx_call *rxcall;
356     register struct ubik_debug *aparm;
357     afs_int32 *isclone;
358 {
359     afs_int32 code;
360
361     code = SVOTE_Debug(rxcall, aparm);
362     *isclone = amIClone;
363     return code;
364 }
365
366 /* handle basic network debug command.  This is the global state dumper */
367 SVOTE_Debug(rxcall, aparm)
368     struct rx_call *rxcall;
369     register struct ubik_debug *aparm; {
370     int  i;
371     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
372      * integers in host order. */
373     
374     aparm->now = FT_ApproxTime();
375     aparm->lastYesTime = ubik_lastYesTime;
376     aparm->lastYesHost = ntohl(lastYesHost);
377     aparm->lastYesState = lastYesState;
378     aparm->lastYesClaim = lastYesClaim;
379     aparm->lowestHost = ntohl(lowestHost);
380     aparm->lowestTime = lowestTime;
381     aparm->syncHost = ntohl(syncHost);
382     aparm->syncTime = syncTime;
383
384     /* fill in all interface addresses of myself in hostbyte order */
385     for ( i=0; i < UBIK_MAX_INTERFACE_ADDR; i++)
386         aparm->interfaceAddr[i] = ntohl(ubik_host[i]);   
387
388     aparm->amSyncSite = ubik_amSyncSite;
389     ubeacon_Debug(aparm);
390     
391     udisk_Debug(aparm);
392     
393     ulock_Debug(aparm);
394
395     /* Get the recovery state. The label of the database may not have 
396      * been written yet but set the flag so udebug behavior remains.
397      * Defect 9477.
398      */
399     aparm->recoveryState = urecovery_state;
400     if ((urecovery_state & UBIK_RECSYNCSITE) && 
401         (urecovery_state & UBIK_RECFOUNDDB ) &&
402         (urecovery_state & UBIK_RECHAVEDB  ) ) {
403        aparm->recoveryState |= UBIK_RECLABELDB;
404     }
405     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
406     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
407     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
408     aparm->tidCounter = ubik_dbase->tidCounter;
409     
410     if (ubik_currentTrans) {
411         aparm->currentTrans = 1;
412         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
413         else aparm->writeTrans = 0;
414     }
415     else {
416         aparm->currentTrans = 0;
417     }
418
419     aparm->epochTime = ubik_epochTime;
420
421     return 0;
422 }
423
424 SVOTE_SDebugOld(rxcall, awhich, aparm)
425     struct rx_call *rxcall;
426     afs_int32 awhich;
427     register struct ubik_sdebug_old *aparm; {
428     register struct ubik_server *ts;
429     register int i;
430     for(ts=ubik_servers; ts; ts=ts->next) {
431         if (awhich-- == 0) {
432             /* we're done */
433             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
434             aparm->lastVoteTime = ts->lastVoteTime;
435             aparm->lastBeaconSent = ts->lastBeaconSent;
436             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
437             aparm->lastVote = ts->lastVote;
438             aparm->up = ts->up;
439             aparm->beaconSinceDown = ts->beaconSinceDown;
440             aparm->currentDB = ts->currentDB;
441             return 0;
442         }
443     }
444     return 2;
445 }
446
447
448 /* handle basic network debug command.  This is the global state dumper */
449 SVOTE_DebugOld(rxcall, aparm)
450     struct rx_call *rxcall;
451     register struct ubik_debug_old *aparm; {
452     int  i;
453     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
454      * integers in host order. */
455     
456     aparm->now = FT_ApproxTime();
457     aparm->lastYesTime = ubik_lastYesTime;
458     aparm->lastYesHost = ntohl(lastYesHost);
459     aparm->lastYesState = lastYesState;
460     aparm->lastYesClaim = lastYesClaim;
461     aparm->lowestHost = ntohl(lowestHost);
462     aparm->lowestTime = lowestTime;
463     aparm->syncHost = ntohl(syncHost);
464     aparm->syncTime = syncTime;
465
466     aparm->amSyncSite = ubik_amSyncSite;
467     ubeacon_Debug(aparm);
468     
469     udisk_Debug(aparm);
470     
471     ulock_Debug(aparm);
472
473     /* Get the recovery state. The label of the database may not have 
474      * been written yet but set the flag so udebug behavior remains.
475      * Defect 9477.
476      */
477     aparm->recoveryState = urecovery_state;
478     if ((urecovery_state & UBIK_RECSYNCSITE) && 
479         (urecovery_state & UBIK_RECFOUNDDB ) &&
480         (urecovery_state & UBIK_RECHAVEDB  ) ) {
481        aparm->recoveryState |= UBIK_RECLABELDB;
482     }
483     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
484     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
485     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
486     aparm->tidCounter = ubik_dbase->tidCounter;
487     
488     if (ubik_currentTrans) {
489         aparm->currentTrans = 1;
490         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
491         else aparm->writeTrans = 0;
492     }
493     else {
494         aparm->currentTrans = 0;
495     }
496
497     aparm->epochTime = ubik_epochTime;
498
499     return 0;
500 }
501
502
503 /* get the sync site; called by remote servers to find where they should go */
504 SVOTE_GetSyncSite(rxcall, ahost)
505     register struct rx_call *rxcall;
506     register afs_int32 *ahost; {
507     register afs_int32 temp;
508
509     temp = uvote_GetSyncSite();
510     *ahost = ntohl(temp);
511     return 0;
512 }
513
514 ubik_dprint(a,b,c,d,e,f,g,h)
515     char *a, *b, *c, *d, *e, *f, *g, *h; {
516     ViceLog(5, (a,b,c,d,e,f,g,h));
517 }
518
519 ubik_print(a,b,c,d,e,f,g,h)
520   char *a, *b, *c, *d, *e, *f, *g, *h;
521 {
522   ViceLog(0, (a,b,c,d,e,f,g,h));
523 }
524
525 /* called once/run to init the vote module */
526 uvote_Init() {
527     /* pretend we just voted for someone else, since we just restarted */
528     ubik_lastYesTime = FT_ApproxTime();
529     return 0;
530 }