跳到主要内容

复活

Tsavorite 中的复活是指重复使用（“复活”）已 Tombstoned（已删除）的记录，以及 Upsert 或 RMW 执行 RCU 时使用的内存中源记录。这最大限度地减少了高删除场景的日志增长（和未使用的空间）。它用于以下情况：

  • 添加新记录的 Upsert、RMW 或 Delete 操作
  • 通过 Read 或 RMW 执行 IO 的 CopyToTail（或从日志的不可变区域读取并复制到尾部）
  • 复活不用于 ReadCache

复活有两种形式

  • 链内复活：Tombstoned 记录保留在哈希链中。如果后续对同一键的 Upsert 或 RMW 操作具有足够的 Value 长度，则会复活该记录。
  • 空闲列表：维护一个空闲列表，将已 Tombstoned 且位于哈希链尾部（直接从哈希表指向）的记录从哈希链中删除，并保存在空闲列表（默认按 2 的幂次分箱，每个箱有多个段的循环缓冲区集合）中。

这些与因 CreateNewRecordXxx 返回 RETRY 而导致的记录重用不同。在这种情况下，记录地址存储在 PendingContext 中，CreateNewRecordXxx 返回 RETRY_LATER 或 RETRY_NOW；当再次尝试 CreateNewRecordXxx 时，它将检索此记录（如果长度仍然足够且未低于所需的最小地址）。重试重用始终启用；复活可能不会。

外部接口​

本节介绍复活的外部 API 和命令行参数。

RevivificationSettings​

此结构指示复活是否活动

  • EnableRevivification：如果为 true，则至少执行链内复活；否则，不执行记录复活（但重试重用仍然执行）。
  • FreeListBins：如果此 RevivificationBin 数组非空，则复活将包含记录的空闲列表，如下所述。
  • SearchNextHigherBin：默认情况下，查找空闲记录时只搜索指定大小的箱。如果设置此项，则如果初始箱中没有记录，也会搜索下一个更高的箱。
  • RevivifiableFraction：可能不希望使用距离 ReadOnlyAddress 太近的记录；一些应用程序更希望新插入的记录尽可能长时间地保留在可变区域中。RevivifiableFraction 将复活的合格范围限制为紧邻 TailAddress 下方内存的此分数内；它具有与 LogSettings.MutablePercent 相同的语义，并且不能大于该值。例如，如果 RevivifiableFraction 为 0.2，TailAddress 为 100,000，HeadAddress 为 50,000，则最接近尾部的 0.2 x 50,000 = 10,000 条记录将有资格进行重用。这是基于地址空间完成的，而不是记录计数，因此可复活的记录的实际数量对于可变长度记录会有所不同。
  • RestoreDeletedRecordsIfBinIsFull 要添加到 RevivificationBin 的已删除记录将从哈希链中省略。如果 bin 已满，此选项控制是否将记录（如果可能）恢复到哈希链。这会将它们保留为链内可复活记录，代价是记录可能在哈希链中时被逐出到磁盘，从而不得不进行 I/O 才能发现记录已删除，因此可能是不必要的。对于重复添加和删除相同键的应用程序，如果使用 FreeList，则应将此选项设置为 true。
  • UseFreeRecordPoolForCopyToTail 执行显式 CopyToTail 操作（例如压缩、从不可变内存区域读取时执行 CopyToTail 或磁盘 I/O）时，这控制是否可以从 FreeRecordPool 满足检索到的记录的分配。这些操作可能要求记录分配在日志的尾部，以便尽可能长时间地保留在内存中。

RevivificationBin​

此结构包含空闲列表箱的定义，空闲列表箱是特定大小范围内空闲地址的列表。

  • RecordSize：此分区中记录的最大大小（最小大小为 16 或前一个箱的 RecordSize + 8）。应根据应用程序预期的记录大小进行分区。如果 TsavoriteKV 使用固定长度数据，则忽略此项；在这种情况下，固定长度记录只有一个箱。
  • NumberOfRecords：此箱中要保留的记录（地址）数量。Tsavorite 尽力将箱分成多个段，以减少在各种大小之间的顺序搜索。
  • BestFitScanLimit：找到第一个匹配项后，扫描最佳匹配项的最大条目数；可以使用特殊的 UseFirstFit 值来使用第一个匹配项。对于固定长度数据类型，忽略此项。

GarnetServer.exe 命令行参数​

GarnetServer.exe 支持以下用于复活的命令行参数

  • --reviv：指定默认的 2 的幂次大小箱的复活的快捷方式。此默认值可以通过 --reviv-in-chain-only 或 --reviv-bin-record-sizes 和 --reviv-bin-record-counts 的组合来覆盖。
  • --reviv-bin-record-sizes：对于主存储，每个复活箱中记录的大小，按大小递增的顺序。取代默认的 --reviv；不能与 --reviv-in-chain-only 一起使用。
  • --reviv-bin-record-counts：对于主存储，每个箱中的记录数量
    • 默认（未指定）：如果指定了 reviv-bin-record-sizes，则每个箱有 RevivificationBin.DefaultRecordsPerBin 条记录。
    • 一个数字：如果指定了 --reviv-bin-record-sizes，则所有箱都有此数量的记录，否则出错。
    • 多个逗号分隔的数字：如果指定了 reviv-bin-record-sizes，则它必须与该数组的大小相同，否则出错。这定义了每个箱的记录数量并取代了默认的 --reviv；不能与 --reviv-in-chain-only 一起使用。
  • --reviv-fraction：可变内存日志空间的比例，从最高日志地址到只读区域，有资格进行复活。适用于主存储和对象存储。
  • reviv-search-next-higher-bins：如果搜索无法在最合适的箱中满足，则搜索此数量的下一个更高的箱。需要 --reviv 或 --reviv-bin-record-sizes 和 --reviv-bin-record-counts 的组合。
  • --reviv-bin-best-fit-scan-limit：找到第一个匹配项后，扫描最佳匹配项的记录数量。需要 --reviv 或 --reviv-bin-record-sizes 和 --reviv-bin-record-counts 的组合。值为
    • RevivificationBin.UseFirstFit：返回其记录足够大以满足请求的第一个地址。
    • RevivificationBin.BestFitScanAll：扫描箱中所有记录以查找最佳匹配项，如果找到精确匹配项则提前停止。
    • 其他数字：在第一个匹配项后，将扫描限制为这么多记录，最多不超过箱的记录计数。
  • --reviv-in-chain-only：仅在标记链中复活 Tombstoned 记录（不使用空闲列表）。不能与 reviv-bin-record-sizes 或 reviv-bin-record-counts 一起使用。也适用于对象存储。
  • --reviv-obj-bin-record-count：对象存储的单个空闲记录箱中的记录数量。对象存储只有一个箱，与主存储不同。除非主存储使用空闲记录列表，否则忽略此项。

内部实现​

本节描述复活的内部设计和实现。

维护额外值长度​

由于可变长度记录值可以增长和缩小，我们除了值数据之外，还必须存储值的实际长度。固定长度数据类型（包括对象）不需要存储此项，因为它们的长度不会改变。

此记录长度存储适用于复活和非复活场景。ConcurrentWriter 和 InPlaceUpdater 可能会更改记录大小，并且需要知道如果它们以后要在原地增长，有多少可用空间。

  • ConcurrentWriter 和 InPlaceUpdater 中的原地更新使用此功能来设置 UpsertInfo 和 RMWInfo 属性 UsedValueLength 和 FullValueLength。这些属性将在下面讨论。
  • 复活需要此功能来满足来自 FreeRecordPool 的请求，然后还需要设置 UpsertInfo 和 RMWInfo 属性 UsedValueLength 和 FullValueLength。

存储额外的值长度是通过将已使用的值长度（值的当前长度）向上舍入到 int 边界，然后如果分配的值空间大于等于 4 字节，则将额外长度存储在（值起始位置加上向上舍入的已用空间）处。因此，完整值大小是向上舍入的已用值大小加上额外值大小。如果可以存储此额外长度，则设置 RecordInfo.Filler 位以指示存在额外长度。可变长度日志分配是 8 字节（RecordInfo 大小）对齐的，因此任何小于 sizeof(int) 的额外长度都可以通过此向上舍入推断出来。

确保日志完整性​

必须小心地存储额外的值长度，以便我们保持未使用的空间归零的不变性。这是必要的，因为日志扫描假设它们在先前的记录长度之后遇到的任何非零数据都是有效的 RecordInfo 头部。如果额外长度在设置 Filler 位之前设置，或者 Filler 位在额外长度归零之前被清除，则日志扫描可能会暂时看到短长度，落在非零额外长度上，并认为它是有效的 RecordInfo。另一个方向是安全的：Filler 位可能已设置，但额外长度为零。在这种情况下，扫描会看到一个归零的 RecordInfo (RecordInfo.IsNull())，并假定它是未初始化的空间，并按 RecordInfo 的大小（8 字节）向前移动。

即使没有 Filler 位，当可变长度值缩小时，也遵循此不变性。当值缩小时，新（较短）大小之外的数据必须在设置较短大小之前归零。

综合这两点，当我们调整可变长度值长度时，我们必须

  • 清除额外值长度。
  • 移除 Filler 位。
  • 将新（较短）大小之外的额外值数据空间归零。
  • 设置新（较短）值长度。
  • 设置 Filler 位。
  • 将额外值长度设置为正确的D新值。

Tsavorite 提供的可变长度实现是 SpanByte，SpanByteFunctions 变体在此处执行正确的操作。

UpdateInfo 记录长度管理​

对于可变长度数据类型，UpsertInfo、RMWInfo 和 DeleteInfo 有两个字段，允许相关的 IFunctions 回调了解记录长度（无需了解值存储的内部结构）

  • UsedValueLength：实际使用的值空间量。
  • FullValueLength：为值分配的完整空间；这是记录初始插入时请求的值大小，向上舍入到 8 字节对齐。

对于 SpanByte，带 (physicalAddress, physicalAddress + allocatedSize) 的 VariableLenghtBlittableAllocator.GetValue 重载调用 IVariableLengthStructureSettings 的默认 SpanByte 实现，实际上会将值空间初始化为一个有效的 SpanByte，其中包含请求的值长度（最多可容纳的最大元素数量）。但是，其他可变长度数据类型可能不会这样做。

DisposeForRevivification​

通常，IFunctions 的 Dispose* 函数旨在处理不写入日志的数据（通常是由于 CAS 失败或 SingleWriter、InitialUpdater 或 CopyUpdater 中的失败）。写入日志的数据（如果注册了 OnEvictionObserver）将被 OnEvictionObserver 看到。然而，复活的记录是从日志中获取并重复使用的；因此，它们必须给应用程序提供 Dispose() 的机会。

为了处理这个问题，添加了一个新的 DisposeForRevivification IFunctions 方法。当记录被移动到 FreeList、从链内或空闲列表复活，或者从 Retry 重用时，它都有一个 Key 和可能一个 Value。Tsavorite 会两次调用 DisposeForRevivification

  • 在记录被放入 FreeList 时。在这种情况下，newKeySize 参数为 -1，表示我们尚未重用它。此调用的主要原因是尽快释放不再使用的对象。对于非对象类型，这的成本最小；固定长度类型不执行任何操作，唯一 Garnet 可变长度类型是 SpanByte，它此时也不需要执行任何操作（没有分配）。
    • DisposeForRevivification 不会为链内 Tombstoned 记录调用；键必须保持有效，并且值将在逐出时释放。
    • DisposeForRevivification 不会为在添加 Retry-recycled 记录到 PendingContext 时调用，因为在检索它们时会调用它，并且这总是会完成（我们总是重试）。
  • 在重用时，无论是从 FreeList 还是链内，或者从 Retry 重用，如果从 FreeList 重用，newKeySize 将设置为新键的实际大小。这仅与可变长度类型和 Garnet 有关，对于 Garnet，这意味着仅限于 SpanByte，它确保记录始终零初始化，以便它在任何时候都对扫描“有效”。在重用时，Tsavorite 保证记录中包含有效的 Key 和 Value（即使 Value 是默认值），并以以下方式调用 DisposeForRevivification
  • 清除额外的 Value 长度和填充符（额外的 Value 长度保留在局部变量中）。
  • 如果记录是从空闲列表中检索到的，则调用 DisposeForRevivification，其中 newKeySize > 0。
    • 如果 DisposeForRevivification 清除 Value 和可能的 Key，则它必须按照维护额外 Value 长度中所述的协议，在已用空间之后将数据归零。SpanByte 不需要清除任何东西，因为 SpanByte 不包含任何需要释放的东西。
    • 在可能与早期版本存在重大更改的情况下，任何非 SpanByte 可变长度实现必须要么实现 DisposeForRevivification 以将空间零初始化，要么必须修改其 SingleWriter、InitialUpdater 和 CopyUpdater 实现以识别现有值并以类似于 ConcurrentWriter 或 InPlaceUpdater 的方式处理它。
      • 对于 SpanByte，SingleWriter 等在非复活记录的目标中将具有有效的目标值，因为 VariableLengthBlittableAllocator.GetAndInitializeValue（在记录分配后调用）调用 IVariableLengthStructureSettings 的默认 SpanByte 实现，并且实际上将值空间初始化为包含整个请求值大小的有效 SpanByte。对于新分配（未复活）的记录，值数据初始化为零；对于复活的记录，不保证这一点；仅保证 usedValueLength 之后的值空间归零，因此 SingleWriter 等必须准备好缩小目标值。

链内复活​

如果 FreeList 不活动，所有 Tombstoned 记录都保留在哈希链中；即使 FreeList 活动，已删除的记录也可能无法省略。如果后续对同一键的 Upsert 或 RMW 操作具有足够的分配值长度，则会复活该记录。

如果 RevivificationSettings.EnableRevivification 为 true，则链内复活始终处于活动状态。其功能如下：

  • Delete() 以正常方式完成；设置 Tombstone。如果 Tombstoned 记录位于标记链的尾部（即是 HashBucketEntry 中的记录）并且 FreeList 已启用，则它将被移动到 FreeList。否则（或如果此移动失败），它将保留在标记链中。
  • Upsert() 和 RMW() 将尝试复活一个 Tombstoned 记录
    • 如果记录足够大，我们通过以下方式重新初始化其 Value：
      • 清除额外的 Value 长度和填充符，并按照维护额外 Value 长度中所述调用 DisposeForRevivification。
      • 移除 Tombstone。

空闲列表复活​

如果 RevivificationSettings.FreeBinList 不为空，则它会根据数组的 RevivificationBin 元素创建空闲列表。如果数据类型是固定的，则数组必须有一个元素；否则可以有多个元素。

当空闲列表处于活动状态并且记录被删除时，如果它位于哈希链的尾部，未被锁定，并且其 PreviousAddress 指向 BeginAddress 以下，则可以将其 CAS（比较并交换）出哈希链。如果成功，它将被添加到空闲列表。Upsert 和 RMW 执行的 RCU 的源记录的空闲列表化也适用类似的考虑。

空闲列表复活的功能如下：

  • Delete() 检查记录是否位于哈希链的尾部（即是否为 HashBucketEntry 中的记录）。
    • 如果不是，那么由于复杂性，我们不会尝试将其加入空闲列表：TracebackForKeyMatch 需要返回其 .PreviousAddress 指向此记录的下一个更高记录，并且我们需要检查该下一个更高记录是否也已加入空闲列表（并且可能已复活）。
    • 否则，Delete() 检查其 PreviousAddress 是否指向 BeginAddress 以下。如果不是，则我们必须保留它；它可能是其下方已删除记录的标记，将其从标记链中移除将允许错误地访问早期记录。
    • 否则，我们尝试将新 Tombstoned 记录的 .PreviousAddress CAS（比较并交换）到 HashBucketEntry 中。
      • 由于并发插入，CAS 可能会失败
    • 如果成功，则我们将记录 Add 到空闲列表。这会将其密封，以防其他线程正在遍历标记链。
      • 如果此 Add 失败，则将是因为箱已满。Tsavorite 不会完全丢失记录，而是尝试将其重新插入为已删除的记录。
  • 执行 RCU 的 Upsert 和 RMW 将在执行 CAS 之前检查源记录是否在 HashBucketEntry 中。如果是，并且所有其他条件都适用，则源记录将像 Delete 一样加入空闲列表（不同之处在于，如果 Add 到空闲列表失败，则不尝试重新插入）。
  • Upsert() 和 RMW() 如果必须创建新记录，将尝试复活一个空闲列表记录
    • 它们调用 TryTakeFreeRecord 从空闲列表中删除记录。
    • 如果成功，TryTakeFreeRecord 通过以下方式初始化记录：
      • 清除额外的 Value 长度和填充符，并按照维护额外 Value 长度中所述调用 DisposeForRevivification。
      • 取消密封记录；纪元管理保证没有人仍在执行，他们在记录进入空闲记录池之前看到了此记录。

空闲列表复活的并发控制考量​

空闲列表复活要求 ConcurrencyControlMode 不为 ConcurrencyControlMode.None；否则标记链可能不稳定，标记链中的第一条记录可能会在线程从其回溯时被复活和重用。

  • 线程 1：从 HashBucketEntry 获取第一个记录地址
  • 线程 2：删除并省略第一个记录，将其放入复活空闲列表
  • 线程 3：用不同的键复活该记录，设置其 .PreviousAddress
  • 线程 1：跟随前一个 .PreviousAddress，现在位于一个完全不同的标记链上。这仅对标记链中的第一条记录（HashBucketEntry 中最尾部的记录）可能；我们不会省略标记链中间的记录。

对于 ConcurrencyControlMode.LockTable，因为唯一的当前 LockTable 实现是通过 HashBucket 并且 HashBucket 级别的锁定高于标记链，所以我们几乎免费获得了一个稳定的标记链。代价是必须在调用 TracebackForKeyMatch 之前锁定 HashBucket。

FreeRecordPool 设计​

空闲列表的层次结构包括

  • FreeRecordPool，它维护箱，决定哪个箱应该用于 Enqueue 和 Dequeue。
  • 多个 FreeRecordBin，每个 RevivificationSettings 中的 RevivificationBin 对应一个，具有相应的记录数量、最大记录大小和最佳匹配扫描规范。
  • 箱的每个元素都是一个 FreeRecord

每个箱都是单独分配的，因此池使用大小索引，这是一个缓存对齐的独立整数向量，用于按顺序搜索以确定箱大小。这避免了拉入每个箱的单独缓存行以检查其大小。

FreeRecord 设计​

一个 FreeRecord 包含一个空闲日志地址和它被释放的纪元；它的数据是一个“long”，包含

  • 地址（48 位）和
  • 地址处记录的大小（16 位）。如果大小 > 2^16，则记录为“超大”，其确切大小从 hlog 获取。
    • 地址的存储方式与 RecordInfo.PreviousAddress 类似，具有相同的位数
    • 大小移位到地址上方，使用剩余的位。因此它限制为 16 位；任何超过该大小的空闲记录都进入超大箱。

因为这只是一个 long，所以在设置和获取地址时，我们有原子比较和交换。

FreeRecordBin 设计​

箱中的记录大小介于 [前一个箱的最大记录大小 + 8] 和 [当前箱的最大记录大小] 之间。作为快捷方式，我们按最大记录大小引用箱，即“64 字节箱”表示“最小记录大小比前一个箱的最大大小大 8，最大记录大小为 64 的箱”。

每个箱都有一个缓存对齐的 FreeRecord 向量，它作为循环缓冲区运行。与 FIFO 队列不同，我们不维护读/写指针，原因如下：

  • 箱中的某些记录可能小于给定分配请求的大小要求；这可能意味着在找到匹配项之前跳过许多记录。使用纯 FIFO 方法会丢失大量记录。保持读/写指针的唯一解决方案是重新排队跳过的记录，或某种在读指针之前预读的变体，这会引入复杂性，例如可能阻塞后续写入（读指针可能“冻结”，但其后有许多开放元素，写入指针无法前进到）。
  • 维护读写指针需要在每次调用时进行互锁，此外还要对 FreeRecord 本身进行 Add/Remove 互锁。

我们希望获得一种解决方案，在读写操作上只有一个互锁，不迭代整个段，并尽力实现最佳匹配。为此，我们采用按记录大小对箱进行分段的策略。

可变长度箱分段​

对于可变长度 Key 和 Value 类型，我们根据 8 字节对齐的大小范围对箱进行分段。

首先，箱中的最大记录数会向上舍入到缓存对齐的大小，并且可能会进一步向上舍入以确保每个段都从缓存边界开始。如上所述，FreeRecord 是 16 字节，因此每行有 4 个。但是，4 个元素对于一个段来说太小了，因此我们将要求最小段大小为 8（2 个缓存行）。这是一个定义的常量 MinSegmentSize，因此如果需要可以修改。

我们通过将箱中的记录数量除以箱中可能存在的 8 字节对齐记录大小范围来计算箱段，每个段至少包含两个缓存行（8 个项目）。段没有读/写指针；它们只是箱记录数组中开始的索引，根据记录大小（如果添加）或请求的记录大小（如果取用）动态计算。

以下是确定大小范围的 3 个示例，使用的箱定义如下：

  • 一个 32 字节箱和一个 64 字节箱，都包含 1024 条记录
  • 我们将忽略介于两者之间的箱，但它们以最大记录大小 2k 结束
  • 一个最大记录大小为 4k 并包含 256 条记录的箱。此示例取自

使用以下分段策略：

  • 32 字节箱的最小大小为 16，因为它是第一个箱。由于大小被视为 8 的倍数或更大，因此它有 3 种可能的记录大小：16、24、32。因此，我们创建大小为 1024/3 的内部段，然后将其向上舍入，使每个段的记录计数是 4 的倍数。因此，每个段有 344 个元素（1024/3 是 341.33...；向上舍入到 MinSegmentSize 的倍数），并且箱中共有 1032 个元素。这些段从索引 0、344、688 开始。
  • 64 字节箱的最小记录大小为 40（比前一个箱的最大值大 8）。根据上述规定，它有 4 种可能的记录大小：40、48、56、64。1024 可以被 4 整除，得到 MinSegmentSize 对齐的 256，因此段从 0、256、512、768 开始。
  • 较大箱的大小范围可能的大小太多，无法为每个大小创建一个段，因此使用不同的段计算策略。在这种情况下，大小范围为 2k，除以 8 是箱内 256 种可能的记录大小。将箱记录计数除以这个数得到 4，低于所需的 MinSegmentSize，因此我们改为将箱的段计数设置为 MinSegementSize，然后将箱记录计数除以该值以获取段数（向上取整），然后将段大小增量设置为大小范围除以段数。因此我们有 16 个段，我们将大小范围除以 16 以获取段的记录大小范围。记录数是段大小乘以段数。段是
    • 段 0 从索引 0 开始，最大记录大小为 2k+16（因此，该段可能包含以下大小的混合记录：2k+8、2k+16）
    • 段 1 从索引 8 开始，最大记录大小为 2k + 16*2
    • 段 2 从索引 16 开始，最大记录大小为 2k+16*3
    • 以此类推
  • 本质上，这些分区是迷你箱，我们可以根据记录或请求大小高效地计算它们的起始偏移量。

除了基于大小的分区之外，还可以使用线程 ID，就像 LightEpoch 一样。然而，基于线程 ID 的分区对大小没有组织；我们可能有一个随机的大小分布。使用基于大小的分区，我们更有可能找到我们想要的大小（或接近它），并且溢出会在一半时间将我们放入下一个最高记录大小分区，这可能会以最小的努力提供接近最佳匹配。此外，基于大小的分区使得对请求的最佳匹配搜索更容易。

最佳匹配和首次匹配​

顾名思义，我们有首次匹配或最佳匹配的选项来满足请求。我们通过 RevivificationBin.BestFitScanLimit 允许两者

  • UseFirstFit：值为零，因此我们不扫描；当从箱中请求记录时，它返回第一个大小 >= 请求大小、添加纪元 >= SafeToReclaimEpoch 且地址 >= 传递给 Take 调用的 minAddress 的记录。
  • BestFitScanAll：值为 Int.MaxValue，因此我们扫描整个箱（可能循环），记录最佳匹配，然后尝试返回该匹配（如果另一个线程首先返回它，则可能会失败，在这种情况下我们重试）。如果在任何时候存在精确匹配，该箱会尝试返回该记录。
  • 其他数字 < 箱记录计数：类似于 BestFitScanAll，但限制扫描的记录数量。
固定长度箱​

对于固定长度的键和值数据类型，只有一个箱，当然没有基于大小的分区。在这种情况下，我们可以使用基于线程 ID 的分区（任何足够大的分区也可以）来确定分区内开始迭代的索引。然而，基于线程 ID 的分区存在写入器写入不同分区而读取器从不同分区读取的可能性；在最坏的情况下，读取器必须绕过所有分区才能获取记录。这可能可以通过减少处理器缓存之间的高速缓存行乒乓来抵消，如果分区的前 4 条记录被不同线程重复更新，但这尚未尝试。

检查空箱​

我们不希望在 FreeRecordPool 或每个 FreeRecordBin 中维护每个操作的记录计数器，因为这将是每个 Add 或 Take 的额外互锁。因此，我们无法随时准确地指示池或箱是否为空。然而，检查空箱是昂贵的，所以我们希望优化这一点。

对于设置一个或多个粗粒度标志以指示池和/或单个箱是否为空，存在许多“性能与准确性”的权衡

  • 在池级别执行此操作需要与所有箱协调
  • 在箱级别执行此操作需要知道请求映射到哪个箱，这需要一些计算
  • 显然，“空”标志由 Add 设置为 false。然而，当 Take 移除最后一个标志时，将其设置为 true 并不容易，因为可能同时发生 Add 操作。

选择的方法是维护箱级别的 isEmpty 标志。

  • Add 总是将 isEmpty 设置为 false。
  • 我们不在 Take() 上清除 isEmpty，因为这可能导致由于 Add 而丢失“isEmpty = false”标志。
  • 我们维护一个工作任务，定期迭代所有箱以将 IsEmpty 设置为 true。

此迭代箱以设置 isEmpty 的任务由 CheckEmptyWorker 类完成，该类使用一个单独的按需 Task 来执行此操作。它在一个执行以下操作的循环中执行此操作：

  • 等待 1 秒
  • 扫描：扫描整个池中的每个箱
    • 如果箱已标记为 isEmpty，则不执行任何操作
    • 否则，遍历箱中的所有条目
      • 如果找到一个具有有效地址的，则退出该箱的循环
      • 否则，设置该箱的 isEmpty 标志。

CheckEmptyWorker 有一个 Start 方法，由 FreeRecordPool 的 Add 或 Take 调用。此 Start 方法检查 CheckEmptyWorkerWorker 是否已启动，如果未启动则启动它。

由于这是一个持久任务，因此它有一个 CancellationTokenSource，当 TsavoriteKV 关闭时，由 CheckEmptyWorker.Dispose() 发出信号。

固定长度与可变长度​

对于非可变长度类型，记录大小是固定的，因此 FreeRecordPool 只有一个箱。否则，它具有完整范围的可变长度箱。

将记录添加到池中​

将记录添加到池中时

  • 调用方调用 FreeRecordPool.TryAdd。
  • TryAdd 扫描大小索引以查找箱索引
  • 调用该索引处的箱以添加记录
    • 该箱根据记录大小计算段偏移量，然后进行线性扫描以查找空闲空间（或地址小于 hlog.ReadOnlyAddress 的空间）。
    • 如果找到，则将记录及其地址、大小（如果小于 16 位）以及 TryAdd 调用时的 currentEpoch 添加到其中。然后 TryAdd 返回 true。
    • 否则 TryAdd 返回 false

从池中获取记录​

获取记录时，我们必须

  • 确定与请求大小对应的箱
  • 如果箱为空，则返回
  • 否则，任何返回的地址都必须保持哈希链向下指向的不变性；HashTableEntry.Address 作为最小所需地址传递。这要么是一个有效的较低地址，要么是一个无效地址（低于 BeginAddress）。

操作然后进行如下：

  • 调用方调用 FreeRecordPool.TryTake。
  • TryTake 扫描大小索引以查找箱索引
  • 调用该索引处的箱以尝试获取记录
    • 该箱根据记录大小计算段偏移量，然后进行线性扫描以查找大小 >= 所需大小且地址 >= 传递给调用的 minAddress 的记录。有关返回哪些可用记录的讨论，请参阅最佳匹配和首次匹配。
    • 如果它找到匹配此项的记录并成功地将箱 CAS 为空，则返回记录，并且 TryTake 返回 true。
    • 否则 TryTake 返回 false