website/docs/dev/tsavorite/locking.md
Locking is always on in Tsavorite. It is done by locking the HashIndex bucket. There are two modes of locking; these are automatic based on what sessions the caller uses:
Lock method on TransactionalContext or TransactionalUnsafeContext (hereafter referred to collectively as Transactional*Context) at the beginning of a transaction, passing an ordered array of keys, and must call Unlock when the transaction is complete. Tsavorite does not try to lock during individual operations on these session contexts.InternalRUMD for the internal methods that implement them: Read, Upsert, rMw, and Delete.All locks are obtained via spinning on Interlocked.CompareExchange and Thread.Yield() and have limited spin count, to avoid deadlocks; if they fail to acquire the desired lock in this time, the operation retries.
As noted above, manual locking is done by obtaining the Transactional*Context instance from a ClientSession. There are currently 4 *Context implementations; all are struct for inlining. All *Context are obtained as properties on the ClientSession named for the type (e.g. clientSession.TransactionalContext). The characteristics of each *Context are:
BasicContext: This is exactly the same as ClientSession, internally calling directly through to ClientSession's methods and reusing ClientSession's TsavoriteSession. It provides safe epoch management (acquiring and releasing the epoch on each call) and Transient locking.UnsafeContext : IUnsafeContext: This provides Transient locking, but rather than safe epoch management handled per-operation by Tsavorite, this supports "unsafe" manual epoch management controlled by the client via BeginUnsafe() and EndUnsafe(); it is the client's responsibility to make these calls correctly. UnsafeContext API methods call the internal ContextRead etc. methods without doing the Resume and Suspend (within try/finally) of epoch protection as is done by the "Safe" API methods.TransactionalContext : ITransactionalContext: This provides safe epoch management, but rather than Transient locking, this requires Manual locks via BeginTransactional and EndTransactional. This requirement ensures that all locks are acquired before any methods accessing those keys are called.TransactionalUnsafeContext : ITransactionalContext, IUnsafeContext: This combines manual epoch management and manual locking, exposing both sets of methods.In addition to the Lock methods, Tsavorite supports:
TryLock: Accepts an array of keys and returns true if all locks were acquired, else false (and any locks that were acquired are released)TryPromoteLock: Accepts a single key and returns true if the key's lock could be promoted from Read to Exclusive.All manual locking of keys must lock the keys in a deterministic order, and unlock in the reverse order, to avoid deadlocks.
Lock spinning is limited in order to avoid deadlocks such as the following:
Transactional*Context LC1 exclusively locks k1BasicContext BC1 tries to acquire an exclusive Transient lock on k1, and spins while holding the epochTransient locks are never held across pending I/O or other Wait operations. All the data operations' low-level implementors (InternalRead, InternalUpsert, InternalRMW, and InternalDelete--collectively known as InternalRUMD) release these locks when the call is exited; if the operations must be retried, the locks are reacquired as part of the normal operation there.
Here is an example of the above two use cases, condensed from the unit tests in TransactionalUnsafeContextTests.cs:
var luContext = session.TransactionalUnsafeContext;
luContext.BeginUnsafe();
luContext.BeginTransaction();
var keys = new[]
{
new FixedLengthTransactionalKeyStruct(readKey24, LockType.Shared, luContext), // Source, shared
new FixedLengthTransactionalKeyStruct(readKey51, LockType.Shared, luContext), // Source, shared
new FixedLengthTransactionalKeyStruct(resultKey, LockType.Exclusive, luContext), // Destination, exclusive
};
// Sort the keys to guard against deadlock
luContext.SortKeyHashes(keys);
Assert.IsTrue(luContext.TryLock(keys));
luContext.Read(key24, out var value24);
luContext.Read(key51, out var value51);
luContext.Upsert(resultKey, value24 + value51);
luContext.Unlock(keys);
luContext.EndTransaction();
luContext.EndUnsafe();
This section covers the internal design and implementation of Tsavorite's locking.
There are a number of variables necessary to track the main hash table entry information, the 'source' record as defined above, and other stack-based data relevant to the operation. These variables are placed within structs that live on the stack at the InternalRUMD level.
This is used for hash-chain traversal and CAS updates. It consists primarily of:
HashBucketEntry at the time the HashEntryInfo was populated.
Address (which may or may not include the readcache bit) and AbsoluteAddress (Address stripped of the readcache bit) accessors.HashBucketEntry that may be updated by other sessions as our current operation proceeds.
CurrentAddress (which may or may not include the readcache bit) and AbsoluteCurrentAddress (CurrentAddress stripped of the readcache bit).HashBucketEntry with the current information from the 'live' pointer.This is implemented as RecordSource<TKey, TValue> and carries the information identifying the source record and lock information for that record:
LatestLogicalAddress); this is the first main-log address below any readcache prefix. If there are no readcache records, then this is the same as the HashEntryInfo Address.PreviousAddress to LatestLogicalAddress and CAS's the record into the hash entry, which atomically detaches (drops) the entire readcache prefix; see ReadCache below. (RecordSource no longer tracks a "lowest readcache" splice address — the latch-free design has no splice.)This contains all information on the stack that is necessary for the operation, making parameter lists much smaller. It contains:
HashEntryInfo and RecordSource<TKey, TValue> for this operation. These are generally used together, and in some situations, such as when hlog.HeadAddress has changed due to an epoch refresh, RecordSource<TKey, TValue> is reinitialized from HashEntryInfo during the operation.CreateNewRecord* method.This section discusses where locks are actually stored.
For HashTable locking, the key is hashed to its code which is modulo'd to find the hash table bucket index. This bucket consists of a vector of 8 HashBucketEntries (cache-aligned, as each HashBucketEntry contains only a 'long'). The entries are organized by 'tags', which are the upper 14 bits of the hashcode. The 8th HashBucketEntry is used as a linked list to an overflow bucket; its Address property is a separate allocation that points to an overflow bucket. Thus, a bucket contains 7 entries and a pointer to another bucket if more than 7 tags have been found.
Following is a simplified overfire of the 'tag' logic, using FindOrCreateTag as an example:
FindTag is simpler, since it does not have to add an entry; it returns false if the tag is not found).For the first bucket, the tag bits of its overflow entry are used for locking; see the HashBucket class for detailed comments. There are 16 tag bits; for locking, 15 bits are used for shared (Read) locking and one bit for exclusive locking.
Thus, a key is locked indirectly, by having its HashBucket locked. This may result in multiple keys being locked (all keys that hash to that bucket) rather than just the required key.
Some relevant RecordInfo bits:
Sealed: A record marked Sealed has been superseded by an update (and the record may be in the Revivification FreeList). Sealing is necessary because otherwise one thread could do an RCU (Read, Copy, Update) with a value too large to be an IPU (In-Place Update), while at the same time another thread could do an IPU with a value small enough to fit. A thread encountering a Sealed record should immediately return RETRY_LATER (it must be RETRY_LATER instead of RETRY_NOW, because the thread owning the Seal must do another operation, such as an Insert to tail, to bring things into a consistent state; this operation may require epoch refresh).
RecordInfo.Seal. This is only done when the LockTable entry is already exclusively locked, so Seal() does a simple bitwise operation.Invalid: This indicates that the record is to be skipped, using its .PreviousAddress to move along the chain, rather than restarted. This "skipping" semantic is primarily relevant to the readcache; we should not have invalid records in the main log's hash chain. Indeed, any main-log record that is not in the hash chain must be marked Invalid.
ReadCache we do not Seal records; the semantics of Seal are that the operation is restarted when a Sealed record is found. For non-readcache records, this causes the execution to restart at the tail of the main-log records. However, readcache records are at the beginning of the hash chain, before the main-log records; thus, restarting would start again at the hash bucket, traverse the readcache records, and hit the Sealed record again, ad infinitum.readcache records use Invalid (skip) rather than Sealed (restart): an Invalid readcache record — e.g. an abandoned/failed best-effort read-cache insert — is skipped via its .PreviousAddress so traversal continues to the first main-log record. A value-changing update does not invalidate individual readcache records: it detaches the entire readcache prefix with one hash-entry CAS (see ReadCache below), and the orphaned records stay Valid until eviction reclaims them at page close.Additionally, records may be elided (removed) from the tag chain for one of the following reasons:
In these cases, if the record's PreviousAddress points below hlog.BeginAddress, we remove the record so we do not have to waste an IO to determine that it is a superseded record.
We obtain the key hash at the start of the operation, so we lock its bucket if we are not in a Transactional*Context (if we are, we later Assert that the key is already locked).
Following this, the requested operation is performed within a try/finally block whose 'finally' releases the lock.
For RCU-like operations such as RMW or Upsert of an in-memory main-log record, the source record is sealed (and, if elidable, may be invalidated to allow it to be freelisted for Revivification). For an in-ReadCache source the record is not sealed or elided; the update detaches the entire readcache prefix with one hash-entry CAS (see ReadCache), leaving the orphaned records Valid for page-close reclamation.
Similar locking logic applies to the pending IO completion routines: ContinuePendingRead, ContinuePendingRMW, and ContinuePendingConditionalCopyToTail.
The readcache is a cache for records that are read from disk. In the case of record that become 'hot' (read multiple times) this saves multiple IOs. It is of fixed size determined at TsavoriteKV startup, and has no on-disk component; records in the ReadCache are evicted from the head without writing to disk when enough new records are added to the tail to exceed the memory-size specification.
When the ReadCache is enabled, records from the ReadCache are inserted into the tag chain starting at the HashBucketEntry (these records are identified as ReadCache by a combination of TsavoriteKV.UseReadCache being set and the ReadCache bit in the RecordInfo is set). All ReadCache records come before any main log record. So (using r#### to indicate a ReadCache record and m#### to indicate a main log record):
ReadCache entries in a hash chain, it looks like: HashTable -> m4000 -> m3000 -> m...ReadCache entries in a hash chain, it looks like: HashTable -> r8000 -> r7000 -> m4000 -> m3000 -> m...As a terminology note, the sub-chain of r#### records is referred to as the ReadCache prefix chain of that hash chain.
If the key is found in the readcache, then the RecordSource<TStoreFunctions, TAllocator>.Log is set to the readcache, and the logicalAddress is set to the readcache record's logicalAddress (which has the ReadCache bit). If the operation is a successful update (which will always be an RCU; readcache records are never themselves updated), the new record is published with a single CAS on the HashBucketEntry that detaches the readcache prefix:
PreviousAddress already pointing at the first main-log record below the readcache prefix.HashBucketEntry atomically commits the update and detaches (drops) the entire readcache prefix from the reachable chain. The dropped records are orphaned and reclaimed by ReadCacheEvict when their pages are closed; no interior record is mutated and no readcache record is individually invalidated.Using the above example and assuming an update of the key cached at r8000, the resulting chain would be:
HashTable -> mxxxx (new) -> m4000 -> m3000 -> m...Because the only structural mutation is the single HashBucketEntry CAS, this operation is latch-free with respect to readcache structure: a competing readcache promotion (or another update) for the same key contends on the same HashBucketEntry word, so the loser of the CAS retries and observes the winner. See the read cache design doc for the full latch-free model.