跳到主要内容

锁定

Tsavorite 中有三种锁定模式，由 Tsavorite 构造函数上的 ConcurrencyControlMode 值设置

  • LockTable：Tsavorite 的哈希索引桶用于保存锁状态。锁表锁定可以是手动或瞬时锁定
    • 手动：Garnet 在事务开始时调用 LockableContext 或 LockableUnsafeContext（以下统称为 Lockable*Context）上的 Lock 方法，传入一个有序的键数组，并且必须在事务完成时调用 Unlock。Tsavorite 在这些会话上下文中的单个操作期间不尝试锁定。
    • 瞬时：Tsavorite 在数据操作（Upsert、RMW、Read 或 Delete）期间获取和释放单个键的锁。这些在这里统称为 InternalXxx，代表实现它们的内部方法。
  • None：Tsavorite 不进行任何锁定。

所有锁都通过在 Interlocked.CompareExchange 和 Thread.Yield() 上自旋获得，并且自旋计数有限，以避免死锁；如果它们在此时间内未能获得所需的锁，操作将重试。

如上所述，手动锁定是通过从 ClientSession 获取 Lockable*Context 实例来完成的。目前有 4 种 *Context 实现；所有都是 struct 用于内联。所有 *Context 都作为 ClientSession 上以类型命名的属性获得（例如 clientSession.LockableContext）。每个 *Context 的特性是

  • BasicContext：这与 ClientSession 完全相同，内部直接调用 ClientSession 的方法并重用 ClientSession 的 TsavoriteSession。它提供安全的 epoch 管理（在每次调用时获取和释放 epoch）和瞬时锁定。
  • UnsafeContext : IUnsafeContext：这提供瞬时锁定，但不是由 Tsavorite 每次操作处理的安全 epoch 管理，而是支持由客户端通过 BeginUnsafe() 和 EndUnsafe() 控制的“不安全”手动 epoch 管理；客户端有责任正确进行这些调用。UnsafeContext API 方法调用内部 ContextRead 等方法，而不进行“安全”API 方法所做的 epoch 保护的 Resume 和 Suspend（在 try/finally 中）。
  • LockableContext : ILockableContext：这提供安全的 epoch 管理，但不是瞬时锁定，这需要通过 BeginLockable 和 EndLockable 进行手动锁定。此要求确保在调用任何访问这些键的方法之前获取所有锁。
  • LockableUnsafeContext : ILockableContext, IUnsafeContext：这结合了手动 epoch 管理和手动锁定，暴露了两组方法。

除了 Lock 方法，Tsavorite 还支持

  • TryLock：接受一个键数组，如果所有锁都已获得则返回 true，否则返回 false（并且释放所有已获得的锁）
  • TryPromoteLock：接受一个单个键，如果该键的锁可以从读取升级为排他锁，则返回 true。

注意事项​

所有键的手动锁定必须以确定性顺序锁定键，并以相反顺序解锁，以避免死锁。

锁自旋是有限的，以避免以下死锁

  • Lockable*Context LC1 独占锁定 k1
  • BasicContext BC1 尝试在 k1 上获取排他瞬时锁，并在持有 epoch 时自旋
  • LC1 对 k1 执行 RMW，导致 CopyUpdate；这会执行 BlockAllocate，发现它必须刷新日志头部的页面以在尾部腾出空间。
    • 因此，LC1 调用 BumpCurrentEpoch(... OnPagesClosed)
    • 由于 BC1 持有 epoch，OnPagesClosed() 调用永远不会被处理，因此我们发生死锁。通过确保锁的自旋次数有限，我们强制上述一个或两个会话释放其已获得的任何锁，并返回调用堆栈以通过 RETRY_LATER 重试操作（这会刷新 epoch，允许其他操作（例如上面提到的 OnPagesClosed()）完成）。

瞬时锁绝不会跨待处理的 I/O 或其他 Wait 操作持有。所有数据操作的低级实现者（InternalRead、InternalUpsert、InternalRMW 和 InternalDelete——统称为 InternalXxx）在调用退出时释放这些锁；如果操作必须重试，则在正常操作中重新获取锁。

示例​

以下是上述两种用例的示例，摘自 LockableUnsafeContextTests.cs 中的单元测试

    var luContext = session.GetLockableUnsafeContext();
    luContext.BeginUnsafe();
    luContext.BeginLockable();

    var keys = new[]
    {
        new FixedLengthLockableKeyStruct<long>(readKey24, LockType.Shared, luContext),      // Source, shared
        new FixedLengthLockableKeyStruct<long>(readKey51, LockType.Shared, luContext),      // Source, shared
        new FixedLengthLockableKeyStruct<long>(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.EndLockable();
    luContext.EndUnsafe();

内部设计​

本节涵盖 Tsavorite 锁定的内部设计和实现。

操作数据结构​

需要跟踪主哈希表条目信息、上面定义的“源”记录以及与操作相关的其他基于栈的数据。这些变量放置在 InternalXxx 级别位于栈上的结构中。

HashEntryInfo​

这用于哈希链遍历和 CAS 更新。它主要由以下组成

  • 键的哈希码和相关标签。
  • 在填充 HashEntryInfo 时 HashBucketEntry 的稳定副本。
    • 这同时具有 Address（可能包含或不包含读缓存位）和 AbsoluteAddress（Address 剥离了读缓存位）访问器。
  • 一个指向活动 HashBucketEntry 的指针（以不安全的“C/C++ *”意义），该指针可能在当前操作进行时被其他会话更新。
    • 与稳定副本一样，这有两个地址访问器：CurrentAddress（可能包含或不包含读缓存位）和 AbsoluteCurrentAddress（CurrentAddress 剥离了读缓存位）。
  • 一种方法，用于使用“活动”指针的当前信息更新 HashBucketEntry 的稳定副本。

RecordSource​

这实现为 RecordSource，并携带识别源记录和该记录的锁信息的信息

  • 是否存在内存中的源记录，如果存在
    • 其逻辑和物理地址
    • 它是在读缓存还是主日志中
    • 它是否被锁定
  • 此键哈希在主日志中的最新逻辑地址。如果没有读缓存记录，则这与 HashEntryInfo 地址相同；
  • 如果链中存在读缓存记录，则 RecordSource 包含最低的读缓存逻辑和物理地址。这些用于将新的主日志记录“拼接”到读缓存记录和主日志记录之间的间隙中；请参阅下面的 ReadCache。
  • 源记录（如果存在）所在的日志（读缓存或 hlog）。除非存在源读缓存记录，否则这是 hlog。
  • 是否获取了 LockTable 锁。这与内存中锁是互斥的；只有一个应该设置。

OperationStackContext​

这包含栈上操作所需的所有信息，从而大大缩小了参数列表。它包含

  • 此操作的 HashEntryInfo 和 RecordSource。这些通常一起使用，在某些情况下，例如当 hlog.HeadAddress 由于 epoch 刷新而更改时，RecordSource 在操作期间从 HashEntryInfo 重新初始化。
  • 为操作创建的新记录的逻辑地址。这会向上层链传递，以便 try/finally 可以在异常时将其设置为无效和非暂时性，而无需在 CreateNewRecord* 方法中支付嵌套 try/finally 的成本。

锁位置​

本节讨论锁的实际存储位置。

LockTable​

对于 HashTable 锁定，键被哈希到其代码，然后取模以找到哈希表桶索引。此桶由 8 个 HashBucketEntries 的向量组成（缓存对齐，因为每个 HashBucketEntry 只包含一个“long”）。条目按“标签”组织，标签是哈希码的顶部 14 位。第 8 个 HashBucketEntry 用作溢出桶的链表；其 Address 属性是一个单独的分配，指向一个溢出桶。因此，如果找到超过 7 个标签，则一个桶包含 7 个条目和一个指向另一个桶的指针。

以下是“标签”逻辑的简化概述，以 FindOrCreateTag 为例

  • 迭代所有桶（包括溢出桶）的前 7 个条目。如果找到标签，则使用该条目。
  • 否则，如果找到一个空条目，则将此标签分配给第一个空条目并使用该条目。
  • 否则，添加一个溢出桶并重复该桶中的前两个步骤。（FindTag 更简单，因为它不需要添加条目；如果未找到标签，则返回 false）。

对于第一个桶，其溢出条目的标签位用于锁定；有关详细注释，请参阅 HashBucket 类。有 16 个标签位；对于锁定，15 位用于共享（读取）锁定，1 位用于排他锁定。

因此，通过锁定其 HashBucket 间接锁定键。这可能导致锁定多个键（所有哈希到该桶的键），而不仅仅是所需的键。

RecordInfo​

一些相关的 RecordInfo 位

  • Sealed：标记为 Sealed 的记录已被更新取代（并且该记录可能位于 Revivification FreeList 中）。Sealing 是必要的，因为否则一个线程可能会执行一个 RCU（读取、复制、更新），其值太大而无法成为 IPU（就地更新），同时另一个线程可能会执行一个足够小的值的 IPU。遇到 Sealed 记录的线程应立即返回 RETRY_LATER（它必须是 RETRY_LATER 而不是 RETRY_NOW，因为拥有 Seal 的线程必须执行另一个操作，例如插入到尾部，以使事物处于一致状态；此操作可能需要 epoch 刷新）。

    • Sealing 是通过 RecordInfo.Seal 完成的。这仅在 LockTable 条目已经排他锁定时完成，因此 Seal() 执行一个简单的位操作。

  • Invalid：这表示该记录将被跳过，使用其 .PreviousAddress 沿链移动，而不是重新开始。这种“跳过”语义主要与读缓存相关；我们不应该在主日志的哈希链中存在无效记录。实际上，任何不在哈希链中的主日志记录必须标记为 Invalid。

    • 在 ReadCache 中，我们不密封记录；Seal 的语义是当找到 Sealed 记录时操作重新开始。对于非 readcache 记录，这会导致执行从主日志记录的尾部重新开始。然而，readcache 记录位于哈希链的开头，在主日志记录之前；因此，重新开始将再次从哈希桶开始，遍历读缓存记录，并再次命中 Sealed 记录，无限循环。
    • 因此，当 readcache 记录不再是最新时，我们将其设置为 Invalid；这允许遍历继续，直到读缓存链链接到第一个主日志记录。

    此外，记录可能由于以下原因之一从标签链中省略（删除）

    • 记录已被删除
    • 记录是 RCU 的“源”

    在这些情况下，如果记录的 PreviousAddress 指向 hlog.BeginAddress 以下，我们将删除该记录，这样我们就不必浪费 IO 来确定它是一个被取代的记录。

    • 如果为 Revivification 启用了此类省略的记录，则将其放入 FreeList 中。

锁定流程​

当 ConcurrencyControlMode 为 LockTable 时，Internalxxx

我们在操作开始时获取键哈希，因此如果我们不在 Lockable*Context 中，我们会锁定其桶（如果我们在其中，我们稍后断言键已被锁定）。

在此之后，请求的操作在 try/finally 块中执行，其“finally”释放锁。

对于 RCU 类操作，例如 RMW 或内存中（包括读缓存中）记录的 Upsert，源记录被密封（并且可能使其无效以允许其被释放用于 Revivification）。

类似的锁定逻辑适用于待处理的 IO 完成例程：ContinuePendingRead、ContinuePendingRMW 和 ContinuePendingConditionalCopyToTail。

ReadCache​

读缓存是从磁盘读取的记录的缓存。对于变得“热”的记录（多次读取），这可以节省多次 IO。它的大小在 TsavoriteKV 启动时确定，并且没有磁盘组件；当有足够的新记录添加到尾部以超出内存大小规范时，读缓存中的记录将从头部逐出而无需写入磁盘。

当启用 ReadCache 时，ReadCache 中的记录会插入到从 HashBucketEntry 开始的标签链中（这些记录通过设置 TsavoriteKV.UseReadCache 和在 RecordInfo 中设置 ReadCache 位来标识为 ReadCache）。所有 ReadCache 记录都位于任何主日志记录之前。因此（使用 r#### 表示 ReadCache 记录，m#### 表示主日志记录）

  • 当哈希链中没有 ReadCache 条目时，它看起来像：HashTable -> m4000 -> m3000 -> m...
  • 当哈希链中有 ReadCache 条目时，它看起来像：HashTable -> r8000 -> r7000 -> m4000 -> m3000 -> m...

作为术语说明，r#### 记录的子链被称为该哈希链的 ReadCache 前缀链。

如果键在读缓存中找到，则 RecordSource.Log 设置为读缓存，逻辑地址设置为读缓存记录的逻辑地址（具有 ReadCache 位）。如果操作是成功的更新（总是 RCU；读缓存记录本身从不更新），则发生以下步骤

  • 新版本的记录“拼接”到读缓存前缀后的标签链中
  • 读缓存“源”记录无效。

使用上面的示例并假设 r8000 的更新，结果链将是

  • HashTable -> r8000 (无效) -> r7000 -> mxxxx (新) -> m4000 -> m3000 -> m...
  • 在此示例中，请注意主日志和读缓存之间的记录地址空间完全不同；“xxxx”用作“新地址”来象征这一点。

此拼接操作要求我们处理标签链尾部（在 HashEntryInfo 中）以及拼接点的更新。这不能作为单个原子操作完成。为了解决这个问题，我们分离读缓存前缀链，在尾部插入新记录，然后重新附加分离的记录。有关具体细节，请参阅 DetachAndReattachReadCacheChain。我们可能会重新附加失败，但这可以接受（相对于更复杂和昂贵的锁定），因为此类失败应该很少见，并且读缓存只是一个性能优化。