2 * Copyright 2000, International Business Machines Corporation and others.
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
10 #include <afsconfig.h>
11 #include <afs/param.h>
16 #ifdef AFS_PTHREAD_ENV
17 # include <opr/lock.h>
19 # include <opr/lockstub.h>
23 #include <afs/afsutil.h>
25 #define UBIK_INTERNALS
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 \b short outage is acceptable, this time
34 * should be order of 3 minutes or less.
36 * Theory of operation:
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 * \b false, wait at least #BIGTIME seconds to be sure that #SMALLTIME seconds
43 * has passed at the other site.
45 * Now, back to the design:
46 * One site in the collection is a special site, designated the \b 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
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.
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
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.
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).
92 afs_int32 ubik_debugFlag
= 0; /*!< print out debugging messages? */
94 struct vote_data vote_globals
;
98 * \brief Decide if we should try to become sync site.
100 * The basic rule is that we
101 * don't run if there is a valid sync site and it ain't us (we have to run if
102 * it is us, in order to keep our votes). If there is no sync site, then we
103 * want to run if we're the lowest numbered host running, otherwise we defer to
104 * the lowest host. However, if the lowest host hasn't been heard from for a
105 * while, then we start running again, in case he crashed.
107 * \return true if we should run, and false otherwise.
110 uvote_ShouldIRun(void)
113 int code
= 1; /* default to yes */
116 now
= FT_ApproxTime();
117 if (BIGTIME
+ vote_globals
.ubik_lastYesTime
< now
)
119 if (vote_globals
.lastYesState
&& vote_globals
.lastYesHost
!= ubik_host
[0]) {
120 code
= 0; /* other guy is sync site, leave him alone */
123 if (ntohl((afs_uint32
)vote_globals
.lastYesHost
) < ntohl((afs_uint32
)ubik_host
[0])) {
124 code
= 0; /* if someone is valid and better than us, don't run */
134 * \brief Return the current synchronization site, if any.
136 * Simple approach: if the
137 * last guy we voted yes for claims to be the sync site, then we we're happy to
138 * use that guy for a sync site until the time his mandate expires. If the guy
139 * does not claim to be sync site, then, of course, there's none.
141 * In addition, if we lost the sync, we set #urecovery_syncSite to an invalid
142 * value, indicating that we no longer know which version of the dbase is the
143 * one we should have. We'll get a new one when we next hear from the sync
146 * \return 0 or currently valid sync site. It can return our own
147 * address, if we're the sync site.
150 uvote_GetSyncSite(void)
156 if (!vote_globals
.lastYesState
)
159 now
= FT_ApproxTime();
160 if (SMALLTIME
+ vote_globals
.lastYesClaim
< now
)
161 code
= 0; /* last guy timed out */
163 code
= vote_globals
.lastYesHost
;
170 * \brief called by the sync site to handle vote beacons; if aconn is null, this is a
173 * \returns 0 or time when the vote was sent. It returns 0 if we are
174 * not voting for this sync site, or the time we actually voted yes, if
178 SVOTE_Beacon(struct rx_call
* rxcall
, afs_int32 astate
,
179 afs_int32 astart
, struct ubik_version
* avers
,
180 struct ubik_tid
* atid
)
185 struct rx_connection
*aconn
;
187 struct ubik_server
*ts
;
191 if (rxcall
) { /* caller's host */
192 aconn
= rx_ConnectionOf(rxcall
);
193 rxp
= rx_PeerOf(aconn
);
194 otherHost
= rx_HostOf(rxp
);
196 /* get the primary interface address for this host. */
197 /* This is the identifier that ubik uses. */
198 otherHost
= ubikGetPrimaryInterfaceAddr(otherHost
);
200 ubik_dprint("Received beacon from unknown host %s\n",
201 afs_inet_ntoa_r(rx_HostOf(rxp
), hoststr
));
202 return 0; /* I don't know about you: vote no */
204 for (ts
= ubik_servers
; ts
; ts
= ts
->next
) {
205 if (ts
->addr
[0] == otherHost
)
209 ubik_dprint("Unknown host %x has sent a beacon\n", otherHost
);
210 if (ts
&& ts
->isClone
)
213 otherHost
= ubik_host
[0]; /* this host */
217 ubik_dprint("Received beacon type %d from host %s\n", astate
,
218 afs_inet_ntoa_r(otherHost
, hoststr
));
220 /* compute the lowest server we've heard from. We'll try to only vote for
221 * this dude if we don't already have a synchronization site. Also, don't
222 * let a very old lowestHost confusing things forever. We pick a new
223 * lowestHost after BIGTIME seconds to limit the damage if this host
224 * actually crashes. Finally, we also count in this computation: don't
225 * pick someone else if we're even better!
227 * Note that the test below must be <=, not <, so that we keep refreshing
228 * lowestTime. Otherwise it will look like we haven't heard from
229 * lowestHost in a while and another host could slip in. */
232 /* First compute the lowest host we've heard from, whether we want them
233 * for a sync site or not. If we haven't heard from a site in BIGTIME
234 * seconds, we ignore its presence in lowestHost: it may have crashed.
235 * Note that we don't ever let anyone appear in our lowestHost if we're
236 * lower than them, 'cause we know we're up. */
237 /* But do not consider clones for lowesHost since they never may become
240 now
= FT_ApproxTime(); /* close to current time */
242 && (ntohl((afs_uint32
)otherHost
) <= ntohl((afs_uint32
)vote_globals
.lowestHost
)
243 || vote_globals
.lowestTime
+ BIGTIME
< now
)) {
244 vote_globals
.lowestTime
= now
;
245 vote_globals
.lowestHost
= otherHost
;
247 /* why do we need this next check? Consider the case where each of two
248 * servers decides the other is lowestHost. Each stops sending beacons
249 * 'cause the other is there. Not obvious that this process terminates:
250 * i.e. each guy could restart procedure and again think other side is
251 * lowest. Need to prove: if one guy in the system is lowest and knows
252 * he's lowest, these loops don't occur. because if someone knows he's
253 * lowest, he will send out beacons telling others to vote for him. */
255 && (ntohl((afs_uint32
) ubik_host
[0]) <= ntohl((afs_uint32
)vote_globals
.lowestHost
)
256 || vote_globals
.lowestTime
+ BIGTIME
< now
)) {
257 vote_globals
.lowestTime
= now
;
258 vote_globals
.lowestHost
= ubik_host
[0];
261 /* tell if we've heard from a sync site recently (even if we're not voting
262 * for this dude yet). After a while, time the guy out. */
263 if (astate
) { /* this guy is a sync site */
264 vote_globals
.syncHost
= otherHost
;
265 vote_globals
.syncTime
= now
;
266 } else if (vote_globals
.syncTime
+ BIGTIME
< now
) {
267 if (vote_globals
.syncHost
) {
269 ("Ubik: Lost contact with sync-site %s (NOT in quorum)\n",
270 afs_inet_ntoa_r(vote_globals
.syncHost
, hoststr
));
272 vote_globals
.syncHost
= 0;
275 /* decide how to vote */
276 vote
= 0; /* start off voting no */
278 /* if we this guy isn't a sync site, we don't really have to vote for him.
279 * We get to apply some heuristics to try to avoid weird oscillation sates
280 * in the voting procedure. */
282 /* in here only if this guy doesn't claim to be a sync site */
284 /* lowestHost is also trying for our votes, then just say no. */
285 if (ntohl(vote_globals
.lowestHost
) != ntohl(otherHost
)) {
289 /* someone else *is* a sync site, just say no */
290 if (vote_globals
.syncHost
&& vote_globals
.syncHost
!= otherHost
)
292 } else if (vote_globals
.lastYesHost
== 0xffffffff && otherHost
== ubik_host
[0]) {
293 /* fast startup if this is the only non-clone */
295 for (ts
= ubik_servers
; ts
; ts
= ts
->next
) {
296 if (ts
->addr
[0] == otherHost
)
302 vote_globals
.lastYesHost
= otherHost
;
307 goto done_zero
; /* clone never can become sync site */
309 /* Don't promise sync site support to more than one host every BIGTIME
310 * seconds. This is the heart of our invariants in this system. */
311 if (vote_globals
.ubik_lastYesTime
+ BIGTIME
< now
|| otherHost
== vote_globals
.lastYesHost
) {
312 if ((vote_globals
.ubik_lastYesTime
+ BIGTIME
< now
) || (otherHost
!= vote_globals
.lastYesHost
)
313 || (vote_globals
.lastYesState
!= astate
)) {
314 /* A new vote or a change in the vote or changed quorum */
315 ubik_dprint("Ubik: vote 'yes' for %s %s\n",
316 afs_inet_ntoa_r(otherHost
, hoststr
),
317 (astate
? "(in quorum)" : "(NOT in quorum)"));
320 vote
= now
; /* vote yes */
321 vote_globals
.ubik_lastYesTime
= now
; /* remember when we voted yes */
322 vote_globals
.lastYesClaim
= astart
; /* remember for computing when sync site expires */
323 vote_globals
.lastYesHost
= otherHost
; /* and who for */
324 vote_globals
.lastYesState
= astate
; /* remember if site is a sync site */
325 vote_globals
.ubik_dbVersion
= *avers
; /* resync value */
326 vote_globals
.ubik_dbTid
= *atid
; /* transaction id, if any, of active trans */
329 urecovery_CheckTid(atid
, 0); /* check if current write trans needs aborted */
341 * \brief Handle per-server debug command, where 0 is the first server.
343 * Basic network debugging hooks.
346 SVOTE_SDebug(struct rx_call
* rxcall
, afs_int32 awhich
,
347 struct ubik_sdebug
* aparm
)
349 afs_int32 code
, isClone
;
350 code
= SVOTE_XSDebug(rxcall
, awhich
, aparm
, &isClone
);
355 SVOTE_XSDebug(struct rx_call
* rxcall
, afs_int32 awhich
,
356 struct ubik_sdebug
* aparm
, afs_int32
* isclone
)
358 struct ubik_server
*ts
;
360 for (ts
= ubik_servers
; ts
; ts
= ts
->next
) {
363 aparm
->addr
= ntohl(ts
->addr
[0]); /* primary interface */
364 for (i
= 0; i
< UBIK_MAX_INTERFACE_ADDR
- 1; i
++)
365 aparm
->altAddr
[i
] = ntohl(ts
->addr
[i
+ 1]);
366 aparm
->lastVoteTime
= ts
->lastVoteTime
;
367 aparm
->lastBeaconSent
= ts
->lastBeaconSent
;
368 memcpy(&aparm
->remoteVersion
, &ts
->version
,
369 sizeof(struct ubik_version
));
370 aparm
->lastVote
= ts
->lastVote
;
372 aparm
->beaconSinceDown
= ts
->beaconSinceDown
;
373 aparm
->currentDB
= ts
->currentDB
;
374 *isclone
= ts
->isClone
;
382 SVOTE_XDebug(struct rx_call
* rxcall
, struct ubik_debug
* aparm
,
387 code
= SVOTE_Debug(rxcall
, aparm
);
393 * \brief Handle basic network debug command. This is the global state dumper.
396 SVOTE_Debug(struct rx_call
* rxcall
, struct ubik_debug
* aparm
)
399 /* fill in the basic debug structure. Note the the RPC protocol transfers,
400 * integers in host order. */
402 aparm
->now
= FT_ApproxTime();
403 aparm
->lastYesTime
= vote_globals
.ubik_lastYesTime
;
404 aparm
->lastYesHost
= ntohl(vote_globals
.lastYesHost
);
405 aparm
->lastYesState
= vote_globals
.lastYesState
;
406 aparm
->lastYesClaim
= vote_globals
.lastYesClaim
;
407 aparm
->lowestHost
= ntohl(vote_globals
.lowestHost
);
408 aparm
->lowestTime
= vote_globals
.lowestTime
;
409 aparm
->syncHost
= ntohl(vote_globals
.syncHost
);
410 aparm
->syncTime
= vote_globals
.syncTime
;
411 memcpy(&aparm
->syncVersion
, &vote_globals
.ubik_dbVersion
, sizeof(struct ubik_version
));
412 memcpy(&aparm
->syncTid
, &vote_globals
.ubik_dbTid
, sizeof(struct ubik_tid
));
414 /* fill in all interface addresses of myself in hostbyte order */
415 for (i
= 0; i
< UBIK_MAX_INTERFACE_ADDR
; i
++)
416 aparm
->interfaceAddr
[i
] = ntohl(ubik_host
[i
]);
418 aparm
->amSyncSite
= beacon_globals
.ubik_amSyncSite
;
419 ubeacon_Debug(aparm
);
425 /* Get the recovery state. The label of the database may not have
426 * been written yet but set the flag so udebug behavior remains.
429 aparm
->recoveryState
= urecovery_state
;
430 if ((urecovery_state
& UBIK_RECSYNCSITE
)
431 && (urecovery_state
& UBIK_RECFOUNDDB
)
432 && (urecovery_state
& UBIK_RECHAVEDB
)) {
433 aparm
->recoveryState
|= UBIK_RECLABELDB
;
435 aparm
->activeWrite
= (ubik_dbase
->flags
& DBWRITING
);
436 aparm
->tidCounter
= ubik_dbase
->tidCounter
;
438 if (ubik_currentTrans
) {
439 aparm
->currentTrans
= 1;
440 if (ubik_currentTrans
->type
== UBIK_WRITETRANS
)
441 aparm
->writeTrans
= 1;
443 aparm
->writeTrans
= 0;
445 aparm
->currentTrans
= 0;
448 aparm
->epochTime
= version_globals
.ubik_epochTime
;
454 SVOTE_SDebugOld(struct rx_call
* rxcall
, afs_int32 awhich
,
455 struct ubik_sdebug_old
* aparm
)
457 struct ubik_server
*ts
;
459 for (ts
= ubik_servers
; ts
; ts
= ts
->next
) {
462 aparm
->addr
= ntohl(ts
->addr
[0]); /* primary interface */
463 aparm
->lastVoteTime
= ts
->lastVoteTime
;
464 aparm
->lastBeaconSent
= ts
->lastBeaconSent
;
465 memcpy(&aparm
->remoteVersion
, &ts
->version
,
466 sizeof(struct ubik_version
));
467 aparm
->lastVote
= ts
->lastVote
;
469 aparm
->beaconSinceDown
= ts
->beaconSinceDown
;
470 aparm
->currentDB
= ts
->currentDB
;
479 * \brief Handle basic network debug command. This is the global state dumper.
482 SVOTE_DebugOld(struct rx_call
* rxcall
,
483 struct ubik_debug_old
* aparm
)
486 /* fill in the basic debug structure. Note the the RPC protocol transfers,
487 * integers in host order. */
489 aparm
->now
= FT_ApproxTime();
490 aparm
->lastYesTime
= vote_globals
.ubik_lastYesTime
;
491 aparm
->lastYesHost
= ntohl(vote_globals
.lastYesHost
);
492 aparm
->lastYesState
= vote_globals
.lastYesState
;
493 aparm
->lastYesClaim
= vote_globals
.lastYesClaim
;
494 aparm
->lowestHost
= ntohl(vote_globals
.lowestHost
);
495 aparm
->lowestTime
= vote_globals
.lowestTime
;
496 aparm
->syncHost
= ntohl(vote_globals
.syncHost
);
497 aparm
->syncTime
= vote_globals
.syncTime
;
498 memcpy(&aparm
->syncVersion
, &vote_globals
.ubik_dbVersion
, sizeof(struct ubik_version
));
499 memcpy(&aparm
->syncTid
, &vote_globals
.ubik_dbTid
, sizeof(struct ubik_tid
));
501 aparm
->amSyncSite
= beacon_globals
.ubik_amSyncSite
;
502 ubeacon_Debug((ubik_debug
*)aparm
);
504 udisk_Debug((ubik_debug
*)aparm
);
506 ulock_Debug((ubik_debug
*)aparm
);
508 /* Get the recovery state. The label of the database may not have
509 * been written yet but set the flag so udebug behavior remains.
512 aparm
->recoveryState
= urecovery_state
;
513 if ((urecovery_state
& UBIK_RECSYNCSITE
)
514 && (urecovery_state
& UBIK_RECFOUNDDB
)
515 && (urecovery_state
& UBIK_RECHAVEDB
)) {
516 aparm
->recoveryState
|= UBIK_RECLABELDB
;
518 aparm
->activeWrite
= (ubik_dbase
->flags
& DBWRITING
);
519 aparm
->tidCounter
= ubik_dbase
->tidCounter
;
521 if (ubik_currentTrans
) {
522 aparm
->currentTrans
= 1;
523 if (ubik_currentTrans
->type
== UBIK_WRITETRANS
)
524 aparm
->writeTrans
= 1;
526 aparm
->writeTrans
= 0;
528 aparm
->currentTrans
= 0;
531 aparm
->epochTime
= version_globals
.ubik_epochTime
;
538 * \brief Get the sync site; called by remote servers to find where they should go.
541 SVOTE_GetSyncSite(struct rx_call
* rxcall
,
546 temp
= uvote_GetSyncSite();
547 *ahost
= ntohl(temp
);
552 ubik_dprint_25(const char *format
, ...)
556 va_start(ap
, format
);
557 vViceLog(25, (format
, ap
));
562 ubik_dprint(const char *format
, ...)
566 va_start(ap
, format
);
567 vViceLog(5, (format
, ap
));
572 ubik_vprint(const char *format
, va_list ap
)
574 vViceLog(0, (format
, ap
));
578 ubik_print(const char *format
, ...)
582 va_start(ap
, format
);
583 ubik_vprint(format
, ap
);
588 * \brief Called once/run to init the vote module
594 /* pretend we just voted for someone else, since we just restarted */
595 vote_globals
.ubik_lastYesTime
= FT_ApproxTime();
597 /* Initialize globals */
598 vote_globals
.lastYesHost
= 0xffffffff;
599 vote_globals
.lastYesClaim
= 0;
600 vote_globals
.lastYesState
= 0;
601 vote_globals
.lowestTime
= 0;
602 vote_globals
.lowestHost
= 0xffffffff;
603 vote_globals
.syncTime
= 0;
604 vote_globals
.syncHost
= 0;
611 uvote_set_dbVersion(struct ubik_version version
) {
613 vote_globals
.ubik_dbVersion
= version
;
617 /* Compare given version to current DB version. Return true if equal. */
619 uvote_eq_dbVersion(struct ubik_version version
) {
623 if (vote_globals
.ubik_dbVersion
.epoch
== version
.epoch
&& vote_globals
.ubik_dbVersion
.counter
== version
.counter
) {
631 * \brief Check if there is a sync site and whether we have a given db version
633 * \return 1 if there is a valid sync site, and the given db version matches the sync site's
637 uvote_HaveSyncAndVersion(struct ubik_version version
)
643 now
= FT_ApproxTime();
644 if (!vote_globals
.lastYesState
|| (SMALLTIME
+ vote_globals
.lastYesClaim
< now
) ||
645 vote_globals
.ubik_dbVersion
.epoch
!= version
.epoch
||
646 vote_globals
.ubik_dbVersion
.counter
!= version
.counter
)