Master Leases for Berkeley DB

What are Master Leases?

1. Authoritative reads: a guarantee that the data being read by the application is durable and can never be rolled back.
2. Freshness: a guarantee that the data being read by the application at the master is not stale.
3. Master viability: a guarantee that a current master with valid leases will not encounter a duplicate master situation.
   

Requirements

• After turning them on, users can choose to ignore them in reads or not.
• We are providing read authority on the master only.  A read on a client is equivalent to a read while ignoring leases.
• We guarantee that data committed on a master that has been read by an application on the master will not be rolled back.  Data read on a client or while ignoring leases or data successfully updated/committed but not read, may be rolled back.
  
• A master will not return successfully from a read operation unless it holds a majority of leases unless leases are ignored.
• Master leases will remove the possibility of a current/correct master being "shot down" by DUPMASTER.  NOTE: Old/Expired masters may discover a later master and return DUPMASTER to the application however.
  
• Any send callback failure must result in premature lease expiration on the master.
  
• Users who change the system clock during master leases void the guarantee and may get undefined behavior.  We assume time always runs forward.
  
• Clients are forbidden from participating in elections while they have an outstanding lease granted to another site.
• Clients are forbidden from accepting a new master while they have an outstanding lease granted to another site.
• Clients are forbidden from upgrading themselves to master while they have an outstanding lease granted to another site.
• When asked for a lease grant explicitly by the master, the client cannot grant the lease to the master unless the LSN in the master's request has been processed by this client.
  

• Users must implement (Base API users on their own, RepMgr users via configuration) a majority (or larger) ACK policy.
  
• The application must use the election mechanism to decide a master. It may not simply declare a site master.
• The send callback must return an error if the majority ACK policy is not met for PERM records.
• Users must set the number of sites in the group.
• Using leases in a replication group is all-or-none.  Therefore, if a site knows it is using leases, it can assume other sites are also.
  
• All applications that care about read guarantees must forward or perform all reads on the master.  Reading on the client means a read ignoring leases.

There are some open questions remaining.

• There is one major showstopper issue, see Crashing - Potential problem near the end of the document.  We need a better solution than the one shown there (writing to disk every time a lease is granted). Perhaps just documenting that durability means it must be flushed to disk before success to avoid that situation?
  
• What about db->join?  Users can call join, but the calls on the join cursor to get the data would be subject to leases and therefore protected.  Ok, this is not an open question.
• What about other read-like operations?  Clearly DB->get, DB->pget, DBC->get, DBC->pget need lease checks.  However, other APIs use keys.  DB->key_range provides an estimate only so it shouldn't need lease checks. DB->stat provides exact counts to bt_nkeys and bt_ndata fields.  Are those fields considered authoritative that providing those values implies a durability guarantee and therefore DB->stat should be subject to lease verification?  DBC->count provides a count for the number of data items associated with a key.  Is this authoritative information? This is similar to stat - should it be subject to lease verification?
  
• Do we require master lease checks on write operations?  I think lease checks are not needed on write operations.  It doesn't add correctness and adds a lot of complexity (checking leases in put, del, and cursors, then what about rename, remove, etc).
  
• Do master leases give an iron-clad guarantee of never rolling back a transaction? No, but it should mean that a committed transaction can never be read on a master unless the lease is valid.  A committed transaction on a master that has never been presented to the application may get rolled back.
  
• Do we need to quarantine or prevent reads on an ex-master until sync-up is done?  No.  A master that is simply downgraded to client or crashes and reboots is now a client.  Reading from that client is the same as saying Ignore Leases.
• What about adding and removing sites while leases are active?  This is SR 14778.  A consistent nsites value is required by master leases.    It isn't clear to me what a master is supposed to do if the value of nsites gets smaller while leases are active.  Perhaps it leaves its larger table intact and simply checks for a smaller number of granted leases?
  
• Can users turn leases off?  No.  There is no planned turn leases off API.
• Clock skew will be a percentage.  However, the smallest, 1%, is probably rather large for clock skew.  Percentage was chosen for simplicity and similarity to other APIs.  What granularity is appropriate here?

API Changes

Lease Timeout

db_timeout_t lease_timeout;
db_timespec lease_duration;

Using Leases

    dbenv->rep_set_lease(DB_ENV *dbenv, u_int32_t clock_scale_factor, u_int32_t flags)

#define REP_F_START_CALLED <some bit value>

if (ret == 0 ) {
	REP_SYSTEM_LOCK
	F_SET(rep, REP_F_START_CALLED)
	REP_SYSTEM_UNLOCK
}

F_CLR(rep, REP_F_START_CALLED);

db_timeout_t tmp;
tmp = (db_timeout_t)((double)rep->lease_timeout / ((double)rep->clock_skew / (double)100));
rep->lease_duration = DB_TIMEOUT_TO_TIMESPEC(&tmp);

tmp = (db_timeout_t)((double)rep->lease_timeout * ((double)rep->clock_skew / (double)100));

Read Operations

• Db->get
• Db->pget
• Dbc->get
• Dbc->pget

if (IS_REP_CLIENT(dbenv)) {
	[get to rep structure]
	if (FLD_ISSET(rep->config, REP_C_LEASE) && !LF_ISSET(DB_IGNORE_LEASE)) {
		db_err("Read operations must ignore leases or go to master");
		ret = EINVAL;
		goto err;
	}
}

if (IS_REP_MASTER(dbenv) && !LF_ISSET(DB_IGNORE_LEASE)) {
	[get to rep structure]
	if (FLD_ISSET(rep->config, REP_C_LEASE) &&
	    (ret = __rep_lease_check(dbenv)) != 0) {
		/*
		 * We don't hold the lease.
		 */
		goto err;
	}
}

Nsites and Elections

Lease Management

Message Changes

struct __rep_lease_grant {
	db_timespec msg_time;
#ifdef DIAGNOSTIC
	db_timespec expire_time;
#endif
} REP_GRANT_INFO;

• Its EID (parameter to rep_send_message and rep_process_message)
  
• The PERM LSN this message acknowledged (sent in the control message)
• Unique identifier echoed back to master (msg_time sent in message as above)

Local State Management

db_timespec grant_expire;

db_timespec mytime;
DB_LSN perm_lsn;
DBT lease_dbt;
REP_GRANT_INFO gi;


timespecclear(&mytime);
timespecclear(&newgrant);
memset(&lease_dbt, 0, sizeof(lease_dbt));
memset(&gi, 0, sizeof(gi));
__os_gettime(dbenv, &mytime);
timespecadd(&mytime, &rep->lease_duration);
MUTEX_LOCK(rep->clientdb_mutex);
perm_lsn = lp->max_perm_lsn;
MUTEX_UNLOCK(rep->clientdb_mutex);
REP_SYSTEM_LOCK(dbenv);
if (timespeccmp(mytime, rep->grant_expire, >))
	rep->grant_expire = mytime;
gi.msg_time = msg->msg_time;
#ifdef DIAGNOSTIC
gi.expire_time = rep->grant_expire;
#endif
lease_dbt.data = &gi;
lease_dbt.size = sizeof(gi);
REP_SYSTEM_UNLOCK(dbenv);
__rep_send_message(dbenv, eid, REP_LEASE_GRANT, &perm_lsn, &lease_dbt, 0, 0);

Maintaining Leases on the Master/Rep_start

struct  {
	int eid;			/* EID of client site. */
	db_timespec start_time;	/* Unique time ID client echoes back on grants. */
	db_timespec end_time;	/* Master's lease expiration time. */
	DB_LSN lease_lsn;	/* Durable LSN this lease applies to. */
	u_int32_t flags;	/* Unused for now?? */
} REP_LEASE_ENTRY;

Granting Leases

1. Pulls the echoed timespec from the client message, into msg_time.
   
2. Finds the entry in its lease table for the client's EID.  It walks the table searching for the ID.  EIDs of DB_EID_INVALID are illegal.  Either the master will find the entry, or it will find an empty slot in the table (i.e. it is still populating the table with leases).
3. If this is a previously unknown site lease, the master initializes the entry by copying to the eid, start_time, and lease_lsn fields.  The master also computes the end_time based on the adjusted rep->lease_duration.
4. If this is a lease from a previously known site, the master must perform timespeccmp(&msg_time, &table[i].start_time, >) and only update the end_time of the lease when this is a more recent message.  If it is a more recent message, then we should update the lease_lsn to the LSN in the message.
5. Since lease durations are computed taking the clock skew into account, clients compute them based on the current time and the master computes it based on original sending time, for diagnostic purposes only, I also plan to send the client's expiration time.  The client errs on the side of computing a larger lease expiration time and the master errs on the side of computing a smaller duration.  Since both are taking the clock skew into account, the client's ending expiration time should never be smaller than the master's computed expiration time or their value for clock skew may not be correct.
   

Refreshing Leases

Lazy Lease Refreshing on Read

/*
 * Use lp->max_perm_lsn on the master (currently not used on the master)
 * to keep track of the last PERM record written through the logging system.
 * need to initialize lp->max_perm_lsn in rep_start on role_chg.
 */
call __rep_send_message on the last PERM record the master wrote, with DB_REP_PERMANENT
if failure
	expire leases
	return lease expired error to caller
else /* success */
	recheck lease table
	/*
	 * We need to recheck the lease table because the client
	 * lease grant messages may not be processed yet, or got
	 * lost, or racing with the application's ACK messages or
	 * whatever. 
	 */
	if we have a majority of valid leases
		return success
	else
		return lease expired error to caller 

Ongoing Update Refreshment

1. Adding the timestamp to the REP_CONTROL structure.  If this option is chosen, then the code trivially sends back the timestamp in the client's reply.  There is no special processing done by either side with the message contents.  So, on a PERM log record, the master will send a non-zero timestamp.  On a normal log record the timestamp will be zero or some known invalid value.  If the client sees a non-zero timestamp, it sends a REP_LEASE_GRANT with the lp->max_perm_lsn after applying that log record.  If it is zero, then the client does nothing different.  The advantage is ease of code.  The disadvantage is that for mixed version systems, the client is now dealing with different sized control structures.  We would have to retain the old control structure so that during a mixed version group the (upgraded) clients can use, expect and send old control structures to the master.  This is unfortunate, so let's consider additional implementations that don't require modifying the control structure.
   
2. Adding a new REPCTL_LEASE flag to the list of flags for the control structure, but do not change the control structure fields.  When a master wants to send a message that needs a lease ack, it sets the flag.  Additionally, instead of simply sending a log record DBT as the rec parameter for replication, we would send a new structure that had the timestamp first and then the record (similar to the bulk transfer buffer).  The advantage of this is that the control structure does not change.  Disadvantages include more special-cased code in the normal code path where we have to check the flag.  If the flag is set we have to extract the timestamp value and massage the incoming data to pass on the real log record to rep_apply.  On bulk transfer, we would just add the timestamp into the buffer.  On normal transfers, it would incur an additional data copy on the master side.  That is unfortunate.  Additionally, if this record needs to be stored in the temp db, we need some way to get it back again later or rep_apply would have to extract the timestamp out when it processed the record (either live or from the temp db).
   
3. Adding a different message type, such as REP_LOG_ACK.  Similarly to REP_LOG_MORE this message would be a special-case version of a log record.  We would extract out the timestamp and then handle as a normal log record.  This implementation is rejected because it actually would require three new message types: REP_LOG_ACK, REP_LOG_ACK_MORE, REP_BULK_LOG_ACK.  That is just too ugly to contemplate.

Gap processing

Handling Incoming Lease Grants

REP_SYSTEM_LOCK
msg_timestamp = cntrl->timestamp;
client_lease = __rep_lease_entry(dbenv, client eid)
if (client_lease == NULL)
	initial lease for this site, DB_ASSERT there is space in the table
	add this to the table if there is space
} else 
	compare msg_timestamp with client_lease->start_time
	if (msg_timestamp is more recent && msg_lsn >= lease LSN)
		update entry in table
REP_SYSTEM_UNLOCK

Expiring Leases

REP_SYSTEM_LOCK
for each entry in the lease table
	entry->end_time = entry->start_time;
REP_SYSTEM_UNLOCK

Checking Leases

#define MAX_REFRESH_TRIES	3
DB_LSN lease_lsn;
REP_LEASE_ENTRY *entry;
u_int32_t min_leases, valid_leases;
db_timespec cur_time;
int ret, tries;

	tries = 0;
retry:
	ret = 0;
	LOG_SYSTEM_LOCK
	lease_lsn = lp->lsn
	LOG_SYSTEM_UNLOCK
	REP_SYSTEM_LOCK
	min_leases = rep->nsites / 2;
	__os_gettime(dbenv, &cur_time);
	for (entry = head of table, valid_leases = 0; entry != NULL && valid_leases < min_leases; entry++)
		if (timespec_cmp(&entry->end_time, &cur_time) >= 0 && log_compare(&entry->lsn, lease_lsn) == 0)
			valid_leases++;
	REP_SYSTEM_UNLOCK
	if (valid_leases < min_leases) {
		ret =__rep_lease_refresh(dbenv, ...);
		/*
		 * If we are successful, we need to recheck the leases because 
		 * the lease grant messages may have raced with the PERM
		 * acknowledgement.  Give those messages a chance to arrive.
		 */
		if (ret == 0) {
			if (tries <= MAX_REFRESH_TRIES) {
				/*
				 * If we were successful sending, but not successful in racing the
				 * message thread, yield the processor so that message
				 * threads may have a chance to run.
				 */
				if (tries > 0)
					/* __os_sleep instead?? */
					__os_yield()
				tries++;
				goto retry;
			} else
				ret = DB_RET_LEASE_EXPIRED;
		}
	}
	return (ret);

Elections

1. The simplest coding solution for DB would be simply to refuse to participate in the election if this site has a current lease granted to a master.  We would detect this situation and return EINVAL.  This is correct behavior and trivial to implement.  The disadvantage of this solution is that the application would then be responsible for repeatedly attempting an election until the lease grant expired.
   
2. The more satisfying solution is for DB to wait the remaining time for the grant.  If this client hears from the master during that time the election does not take place and the call to rep_elect returns with the information for the current/old master.

Election Code Changes

if (leases_configured && (my_grant_still_valid || lease_never_granted) {
	if (lease_never_granted)
		wait_time = lease_timeout
	else
		wait_time = grant_expiration - current_time
	F_SET(REP_F_EPHASE0);
	__rep_send_message(..., REP_MASTER_REQ, ... REPCTL_LEASE);
	ret = __rep_wait(..., REP_F_EPHASE0);
	if (we found a master)
		return
} /* if we don't return, fall out and proceed with election */

if (I am master) {
	...
	__rep_send_message(REP_NEWMASTER...)
	if (F_ISSET(rp, REPCTL_LEASE))
		__rep_lease_refresh(...)
}

Elections and Quiescient Systems

Other Implementation Details

Role Changes

1. A master downgrading to a client. When a master downgrades to a client, it can do so immediately after it has proactively expired all existing leases it holds.  This situation is similar to an error from the send callback, and it effectively cancels all outstanding leases held on this site.  Note that if this master expires its leases, it does not have any effect on when the clients' lease grants expire on the client side.  The clients must still wait their full expected grant time.
   
2. A client upgrading to master. If a client is upgrading to a master but it has an outstanding lease granted to another site, the code will return an EINVAL error.  This situation only arises if the application simply declares this site master.  If a site wins an election then the election itself should have waited long enough for the granted lease to expire and this state should not arise then.
3. A client finding a new master. When a client discovers a new and different master, via a REP_NEWMASTER message then the client cannot accept that new master until its current lease grant expires.  This situation should only occur when a site declares itself master without an election and that site's lease grant expires before this client's grant expires.  However, it is possible for this situation to arise with elections also.  If we have 5 sites holding an election and 4 of those sites have leases expire at about the same time T, and this site's lease expires at time T+N and the election timeout is < N, then those 4 sites may hold an election and elect a master without this site's participation.  A client in this situation must call __rep_wait with the time remaining on its lease.  If the lease is expired after waiting the remaining time, then the client can accept this new master.  If the lease was refreshed during the waiting period then the client does not accept this new master and returns.
   

DUPMASTER

• On the current master and all current clients - If the current master receives an update message or other conflicting message from the old master then that message will be ignored because the generation number is out of date.
• On the old master - If the old master receives an update message from the current master, or any other message with a later generation from any site, the new generation number will trigger this site to return DB_REP_DUPMASTER.  However, instead of broadcasting out the REP_DUPMASTER message to shoot down others as well, this site, if leases are configured, will call __rep_lease_check and if they are expired, return the error.  It should be impossible for us to receive a later generation message and still hold a majority of master leases.  Something is seriously wrong and we will DB_ASSERT this situation cannot happen.
  

Client to Client Synchronization

Interaction Matrix

Crashing - Potential Problem

1. A master and 4 clients are all up and running.
2. The master commits a txn and all 4 clients refresh their lease grants at time T.
3. All 4 clients have the txn and log records in the cache.  None are flushing to disk.
4. All 4 clients have responded to the PERM messages as well as refreshed their lease with the master.
5. All 4 clients hit the same application coding error and crash (machine/OS stays up).
6. Master authoritatively reads data in txn from step 2.
7. All 4 clients restart the application and run recovery, thus the txn from step 2 is lost on all clients because it isn't any logs.
   
8. A network partition happens and the master is alone on its side.
9. All 4 clients are on the other side and elect a new master.
10. Partition resolves itself and we have duplicate masters, where the former master still holds all valid lease grants.
    

Upgrade/Mixed Versions

Testing