website/docs/dev/tsavorite/reviv.md
Revivification in Tsavorite refers to reusing ("revivifying") Tombstoned (deleted) records, as well as in-memory source records for RCUs done by Upsert or RMW. This minimizes log growth (and unused space) for high-delete scenarios. It is used in the following cases:
There are two forms of revivification:
These are separate from the reuse of a record due to a RETRY return from CreateNewRecordXxx. In that case the record address is stored in the OperationState and CreateNewRecordXxx returns either RETRY_LATER or RETRY_NOW; when the CreateNewRecordXxx is attempted again, it will retrieve this record (if the length is still sufficient and it has not fallen below the minimal required address). Retry reuse is always enabled; revivification might not be.
This section describes the external API and command-line arguments for Revivification.
RevivificationSettingsThis struct indicates whether revivification is to be active:
EnableRevivification: If this is true, then at least in-chain revivification is done; otherwise, record revivification is not done (but Retry reuse still is).FreeRecordBins: If this array of RevivificationBin is non-null and non-empty, then revivification will include a freelist of records, as defined below.NumberOfBinsToSearch: By default, when looking for FreeRecords we search only the bin for the specified size. This is the number of additional next-higher bins to search if the initial bin has no available records.RevivifiableFraction: It may be desirable not to use a record that is too close to the ReadOnlyAddress; some apps will prefer that a newly-inserted record remain in the mutable region as long as possible. RevivifiableFraction limits the eligible range of revivification to be within this fraction of memory immediately belowthe TailAddress; it has the same semantics as LogSettings.MutablePercent, and cannot be greater than that. For example, if RevivifiableFraction is .2, TailAddress is 100,000, and HeadAddress is 50,000, then the .2 x 50,000 = 10,000 records closest to the tail will be eligible for reuse. This is done on an address-space basis, not record count, so the actual number of records that can be revivified will vary for variable-length records.RestoreDeletedRecordsIfBinIsFull Deleted records that are to be added to a RevivificationBin are elided from the hash chain. If the bin is full, this option controls whether the record is restored (if possible) to the hash chain. This preserves them as in-chain revivifiable records, at the potential cost of having the record evicted to disk while part of the hash chain, and thus having to do an I/O only to find that the record is deleted and thus potentially unnecessary. For applications that add and delete the same keys repeatedly, this option should be set true if the FreeList is used.UseFreeRecordPoolForCopyToTail When doing explicit CopyToTail operations such as Compaction, CopyToTail when reading from the immutable in-memory region, or disk IO, this controls whether the allocation for the retrieved records may be satisfied from the FreeRecordPool. These operations may require that the records be allocated at the tail of the log, to remain in memory as long as possible.RevivificationBinThis struct contains the definition of the free-list bins, which are lists of free addresses within a certain range of sizes.
RecordSize: The maximum size of records in this partition (the minimum size is either 16 or the previous bin's RecordSize + 8). These should be partitioned according to the anticipated record sizes for your app. Ignored if the TsavoriteKV uses fixed-length data; in that case there is only a single bin for fixed-length records.NumberOfRecords: The number of records (addresses) to be held in this bin. Tsavorite makes a best-effort attempt to partition the bin into segments to reduce sequential search among the various sizes.BestFitScanLimit: The maximum number of entries to scan for best fit after finding first fit; may be the special UseFirstFit value to use first-fit. Ignored for fixed-length datatypes.GarnetServer.exe supports the following commandline arguments for Revivification:
--reviv: A shortcut to specify revivification with default power-of-2-sized bins. This default can be overridden by --reviv-in-chain-only or by the combination of --reviv-bin-record-sizes and --reviv-bin-record-counts.--reviv-bin-record-sizes: The sizes of records in each revivification bin, in order of increasing size. Supersedes the default --reviv; cannot be used with --reviv-in-chain-only.--reviv-bin-record-counts: The number of records in each bin:
RevivificationBin.DefaultRecordsPerBin records.--reviv-bin-record-sizes is specified, then all bins have this number of records, else error.--reviv; cannot be used with --reviv-in-chain-only.--reviv-fraction: Fraction of mutable in-memory log space, from the highest log address down to the read-only region, that is eligible for revivification.reviv-search-next-higher-bins: Search this number of next-higher bins if the search cannot be satisfied in the best-fitting bin. Requires --reviv or the combination of --reviv-bin-record-sizes and --reviv-bin-record-counts.--reviv-bin-best-fit-scan-limit: Number of records to scan for best fit after finding first fit. Requires --reviv or the combination of --reviv-bin-record-sizes and --reviv-bin-record-counts. Values are:
RevivificationBin.UseFirstFit: Return the first address whose record is large enough to satisfy the request.RevivificationBin.BestFitScanAll: Scan all records in the bin for best fit, stopping early if we find an exact match.--reviv-in-chain-only: Revivify tombstoned records in tag chains only (do not use free list). Cannot be used with reviv-bin-record-sizes or reviv-bin-record-counts.This section describes the internal design and implementation of Revivification.
Because inline (string) record Values can grow and shrink, a record can have unused space between its current Value length and the space that was allocated for it. This unused space is tracked so that InPlaceWriter and InPlaceUpdater know how much room is available to grow in place later, and so that revivification can size records taken from the FreeRecordPool. Object values do not need this, because the record only stores a fixed-size object reference (an ObjectId) whose length does not change.
Each record carries this unused space as a filler length recorded in the record's RecordDataHeader (RDH). Specifically, the RDH's FillerWords field is an 8-bit count of 8-byte filler words that follow the Value (and any optional fields) at the end of the record. The record's total length is fully derived from the RDH — key length, value length, optionals, and FillerWords all sum to the allocated record size — so there is no separate length stored inside the Value data, and the filler bytes themselves are never read. Records that need more filler than FillerWords can represent are split: the record retains a portion of the filler and the excess becomes a separate invalid record.
Because the RDH is the authoritative source of record length, InPlaceWriter/InPlaceUpdater grow or shrink an inline Value by moving space between the Value and the filler: growing the Value decreases FillerWords by the same amount, and shrinking it increases FillerWords. The allocated record size is therefore unchanged.
Adjusting a record's Value length must be done carefully so we maintain the invariant that a log scan always sees a consistent record extent. A scan walks the log by computing each record's length and stepping to the next record; if it ever observed a partially-updated record it could miscompute the length and land in the middle of record data, mistaking it for a valid RecordInfo header.
This invariant is preserved because everything that defines a record's length lives in the single 8-byte RDH word (key length, value length, optional-field flags, and FillerWords). Length-affecting changes are built up in a local copy of the RDH and then published with one atomic word write, so a concurrent scanner observes either the pre-update or post-update state, never an intermediate. When an inline Value grows or shrinks, the change in value length is offset by an equal, opposite change in FillerWords, so the derived record length is identical before and after and the scan extent is stable throughout. Any space a value grows into is zero-initialized so no stale bytes are exposed.
The Tsavorite-provided inline value type is SpanByte, and the SpanByteFunctions variants do the right thing here.
The ISessionFunctions writer and updater callbacks operate on a LogRecord, which exposes the record's Key and Value directly, so a callback does not need to know the internals of value storage. When a new or reused record is being written (InitialWriter, InitialUpdater, CopyUpdater), the callback also receives a RecordSizeInfo (in RecordSizeInfo sizeInfo) describing the record's layout — including AllocatedInlineRecordSize (the total allocated inline size), MaxInlineValueSize (the largest inline Value the record can hold), and the IsRevivifiedRecord flag indicating the record is being reused rather than freshly allocated. In-place callbacks (InPlaceWriter, InPlaceUpdater) read the currently allocated and used sizes from the LogRecord/RDH to decide whether an update fits in place.
For SpanByte, the value space of a freshly-allocated record is initialized to a valid, zero-length SpanByte sized to the requested Value length, so the writer callbacks always see a valid destination Value. For a revivified record, the previous record's larger allocation is preserved (see Disposing Revivified Records), so the writer callbacks must be prepared to shrink the destination Value to the size they actually write.
The ISessionFunctions writer, updater, and deleter callbacks are the point at which an application disposes a Value. For object Values, Dispose() may be called from these callbacks; in particular, when logRecord.Info.Invalid (or recordInfo.Invalid) is true the callback is being invoked for a record that was allocated and populated but could not be appended to the log, so the application can release the object there.
Records that are removed from the log for reuse follow a separate path. When a record is put on the FreeList, revivified in-chain, or elided, Tsavorite invokes the allocator's record-disposal trigger, IRecordTriggers.OnDispose(ref LogRecord, DisposeReason), with a DisposeReason that identifies the event (for example RevivificationFreeList when the record is moved to the FreeList, Deleted when a record is tombstoned in place, and Elided when a record is removed from the hash chain without being freelisted). This gives the application the opportunity to release no-longer-needed objects as soon as possible, and lets Tsavorite adjust its heap-size accounting. For SpanByte there is nothing to free, so this is a no-op. Records materialized transiently from disk are disposed through the companion OnDisposeDiskRecord trigger instead.
Disposal-at-eviction (as opposed to reuse) is handled by a different trigger: when a page is evicted past HeadAddress, Tsavorite calls IRecordTriggers.OnEvict(ref LogRecord, EvictionSource) per non-tombstoned record, provided the store's CallOnEvict is true. In-chain tombstoned records keep a valid Key (needed for chain traversal) and are not put through the reuse-dispose path; their Value is disposed at delete time and their remaining resources are accounted for when the record is eventually elided or evicted.
When a record is actually reused (from the FreeList, in-chain, or from a Retry), Tsavorite hands the writer/updater callbacks a valid, consistent record. Preparing a reused record clears the filler, namespace, and record-type fields while preserving the inline Key/Value length information, and sets the record to a valid state — all published with a single atomic RDH word write so a concurrent scanner never sees an intermediate state (see Ensuring Log Integrity). The reused record's RecordSizeInfo.AllocatedInlineRecordSize retains the previous (possibly larger) record length and its IsRevivifiedRecord flag is set, so the callbacks know they are writing into a reused allocation and may shrink the destination Value as needed.
If the FreeList is not active, all Tombstoned records are left in the hash chain; and even if the FreeList is active, a deleted record may not be elidable. A subsequent Upsert or RMW of the same key will revivify the record if it has sufficient allocated value length.
In-Chain revivification is always active if RevivificationSettings.EnableRevivification is true. It functions as follows:
Delete() is done in the normal way; the Tombstone is set. If the Tombstoned record is at the tail of the tag chain (i.e. is the record in the HashBucketEntry) and the FreeList is enabled, then it will be moved to the FreeList. Otherwise (or if this move fails), it remains in the tag chain.Upsert() and RMW() will try to revivify a Tombstoned record:
If RevivificationSettings.FreeRecordBins is non-null and non-empty, this creates the freelist according to the RevivificationBin elements of the array. If the data types are fixed, then there must be one element of the array; otherwise there can be many.
When the FreeList is active and a record is deleted, if it is at the tail of the hash chain, is not locked, and its PreviousAddress points below BeginAddress, then it can be CASed (Compare-And-Swapped) out of the hash chain. If this succeeds, it is added to the freelist. Similar considerations apply to freelisting the source records of RCUs done by Upsert and RMW.
FreeList revivification functions as follows:
Delete() checks to see if the record is at the tail of the hash chain (i.e. is the record in the HashBucketEntry).
Delete() checks to see if its PreviousAddress points below BeginAddress. If not, then we must leave it; it may be the marker for a deleted record below it, and removing it from the tag chain would allow the earlier record to be reached erroneously..PreviousAddress into the HashBucketEntry.
Add the record onto the freelist. This Seals it, in case other threads are traversing the tag chain.
Add fails, it will be due to the bin being full. Rather than lose the record entirely, Tsavorite attempts to re-insert it as a deleted record.Upsert and RMW which perform RCU will check before doing the CAS to see that the source record is in the HashBucketEntry. If so and all other conditions apply, the source record is freelisted as for Delete (except that no attempt is made to reinsert it if Add to the freelist fails).Upsert() and RMW() will try to revivify a freelist record if they must create a new record:
TryTakeFreeRecord to remove a record from the freelist.TryTakeFreeRecord initializes the record by:
FreeRecordPool DesignThe FreeList hierarchy consists of:
FreeRecordPool, which maintains the bins, deciding which bin should be used for Enqueue and Dequeue.FreeRecordBins, one for each RevivificationBin in the RevivificationSettings with the corresponding number of records, max record size, and best-fit scan specification.FreeRecordEach bin is a separate allocation, so the pool uses a size index which is a cache-aligned separate vector of ints of the bin sizes that is sequentially searched to determine the bin size. This avoids pulling in each bin’s separate cache line to check its size.
FreeRecord DesignA FreeRecord contains a free log address and the epoch in which it was freed; its data is a 'long' containing:
RecordInfo.PreviousAddress, with the same number of bitsBecause this is only a long, we have atomic compare and exchange when setting and taking the address.
FreeRecordBin DesignThe records of the bin are of sizes between [previous bin's max record size + 8] and [current bin's max record size]. As a shortcut we refer to bins by their max record size, i.e. "the 64-byte bin" means "the bin whose min record size is 8 more than the max size of the previous bin, and whose max record size is 64."
Each bin has a cache-aligned vector of FreeRecord that operates as a circular buffer. Unlike FIFO queues, we don't maintain a read/write pointer, for the following reasons:
We wish to obtain a solution that has only one interlock on read and write operations, does not iterate the entire segment, and makes a best effort at best-fit. To accomplish this we use a strategy of segmenting the bin by record sizes.
For varlen Key and Value types, we segment bins based on the range of sizes at 8-byte alignment.
First, the max number of records in the bin is rounded up to a cache-aligned size, and may be further rounded up to ensure that each segment starts on a cache boundary. FreeRecords are 16 bytes as stated above so there are 4 per cache line. However, 4 elements is too small for a segment, so we will require a minimum segment size of 8 (2 cache lines). This is a defined constant MinSegmentSize so can be modified if desired.
We calculate bin segments by evenly dividing the number of records in the by by the range of possible 8-byte-aligned record sizes in the bin, with a minimum of two cache lines (8 items) per segment. Segments do not have read/write pointers; they are just the index to start at in the bin’s record array, calculated on the fly from the record size (if Adding) or the requested record size (if Taking).
Here are 3 examples of determining the size ranges, using bin definitions as follow:
The following segmenting strategies are used:
MinSegmentSize), and there are 1032 total elements in the bin. These segments start at indexes 0, 344, 688.MinSegmentSize-aligned 256, and therefore the segments start at 0, 256, 512, 768.MinSegmentSize, so instead we set the bin's segment count to MinSegmentSize and divide the bin record count by that to get the number of segments (rounded up to integer), and then set the segment size increment to the size range divided by segment count. We therefore have 16 segments, and thus we divide the size range by 16 to get the record size ranges for the segments. The number of records is the segment size multiplied by the segment count. The segments are:
An alternative to size-based partitioning would be to use the thread id, as LightEpoch does. However, for threadId-based partitioning there is no organization to the size; we could have a random distribution of sizes. With size-based partitioning, we will much more likely land on the size (or close to it) that we want, and overflowing will put us into the next-highest record-size partition half the time, potentially giving us near-best-fit with minimal effort. Additionally, size-based partitioning makes best-fit search for a request easier.
As the names imply, we have the option of first-fit or best-fit to satisfy a request. We allow both, via RevivificationBin.BestFitScanLimit:
UseFirstFit: The value is zero, so we do not scan; when a record is requested from the bin, it returns the first one that has a size >= the requested size, has an addedEpoch >= SafeToReclaimEpoch, and has an address >= the minAddress passed to the Take call.BestFitScanAll: The value is Int.MaxValue, so we scan the entire bin (possibly wrapping), keeping track of the best fit, then try to return that (which may fail if another thread returned it first, in which case we retry). If at any point there is an exact fit, that bin attempts to return that record.BestFitScanAll except that it limits the number of records to scan.For fixed-length Key and Value datatypes there is only one bin and of course no size-based partitioning. In this case we could use thread-id-based partitioning (as could any sufficiently large partition) to determine the index within the partition to start iterating from. However, threadId-based partitioning suffers from the possibility that the writers write to different partitions than the readers read from; in the worst case the readers must wrap all the way around through all partitions to get to the records. This may be offset by the reduced cache-line ping-ponging between processor caches if the first 4 records of the partition are repeatedly updated by different threads, but this has not been tried.
We do not want to maintain a per-operation counter of records in the FreeRecordPool or each FreeRecordBin because this would be an additional interlock per Add or Take. Because of this, we cannot have an "accurate at all times" indication of whether the pool or a bin are empty. However, checking empty bins is expensive, so we want to optimize this.
There are numerous "performance vs. accuracy" trade-offs for setting one or more coarse-grained flags indicating whether the pool and/or individual bins are empty:
The approach selected is to maintain bin-level isEmpty flags.
This Task to iterate bins to set isEmpty is done by the CheckEmptyWorker class, which uses a separate on-demand Task to do the bump. It does this in a loop that performs:
CheckEmptyWorker has a Start method that is called by FreeRecordPool.TryAdd. This Start method checks whether the worker task is already active, and launches it (via Task.Run) if not.
Because this is a persistent Task, it has a CancellationTokenSource that is signaled by CheckEmptyWorker.Dispose() when we are shutting down the TsavoriteKV.
For non-variable-length types, the record size is fixed, so the FreeRecordPool has only a single bin for it. Otherwise, it has the full range of variable-length bins.
When Adding a record to the pool:
FreeRecordPool.TryAdd.TryAdd call. TryAdd then returns true.TryAdd returns falseWhen Taking a record, we must:
HashTableEntry.Address is passed as a minimum required address. This is either a valid lower address or an invalid address (below BeginAddress).The operation then proceeds as:
FreeRecordPool.TryTake.TryTake returns true.TryTake returns false