跳到主要内容

Garnet 中的轻量级纪元保护（无锁惰性同步）

背景​

我们需要确保共享变量在没有确定性顺序的情况下不同时被读取和修改。语言提供的常用并发原语（如互斥锁和信号量）要求线程频繁地相互同步。这种跨线程同步开销很大；纪元保护减少了跨线程同步的频率。

纪元保护（万米高空视角）​

  • LightEpoch 提供了一种同步机制，其中写路径不需要阻塞线程，而是可以作为回调动作任务入队。写路径被移交给 LightEpoch 实例，以确保当另一个线程可能“获取”了纪元或在给定版本中读取状态时，写操作不会运行。

  • 作为用户，您可以使用纪元保护自信地查看共享变量的最新状态，而不必担心其状态的变化。整个纪元系统仅在线程查看完状态版本后才更新状态。

  • 使用 LightEpoch 是因为它可以在看到先前状态的其他线程不再执行之后运行某些操作（这是纪元控制的基础）。它并不是真正的“互斥”。它更像是在地址边界内操作，以避免冲突。简而言之：线程通过声明“我在此纪元中活跃”（其中“纪元”是一个计数器）来“保护”当前纪元。当它们完成时，它们会移除该保护。当某些会更改共享变量（如“HeadAddress”）的操作即将运行时，它是通过“提升”纪元来完成的，这会增加计数器，然后等待直到没有其他线程使用受保护的先前值进行操作。变量在提升之前设置，以便任何看到新计数器值的线程也看到更新后的变量（同样，例如，“HeadAddress”），这样我们就知道可以安全地操作到当前的“HeadAddress”，它在先前的值之后。

实现细节​

  • 有一个系统范围的 LightEpoch 线程数组，包含 N 个条目，其中 N = max(128, ProcessorCount * 2)。这意味着给定的 LightEpoch 最多支持 128 个线程。在代码中，您可能会注意到，虽然我们将表分配并设置为变量 tableRaw，但与纪元表的所有交互都通过 tableAligned 进行。此优化是为了适应现代处理器和 L1-L3 缓存的缓存行大小（64 字节缓存行大小）。当线程成为纪元保护系统的一部分时，我们将其添加到纪元表中，并在纪元表中为该线程存储一个线程本地纪元。在添加到纪元表开始时，线程本地纪元被设置为当前的全局纪元。

  • 每次我们“获取”一个纪元时，线程都将声称拥有一个纪元计数器。任何新的传入线程都只会在这个纪元之后才接管纪元。

  • 每个有权访问 LightEpoch 对象的线程都可以提升全局纪元（在 LightEpoch 类实例的范围内全局，跨线程共享）。

  • 我们可以添加触发动作，当所有线程都通过了安全纪元时执行 (对于每个线程 T：SafeEpoch <= 线程本地纪元 <= 全局纪元)。由于系统在一个系统可访问的纪元表中保存所有线程本地纪元，我们可以扫描并找到一个安全纪元。这使我们能够拥有一个精确调用一次的函数，该函数依赖于所有线程逻辑协调，并且在纪元结束时没有为触发器执行任何代码。

  • 如果您仔细观察，epoch.Resume() 的主要作用是让线程在纪元表中找到一个空闲条目，将其 ID 放入其中，并“声明”当前纪元（下一个线程将纪元增加 1 并声明下一个纪元）。在 epoch.Resume() 内部有一个循环；如果当前目标纪元条目已被另一个线程占用，当前线程将让步。当它醒来时，它将尝试占用下一个条目。如果纪元表已满，其余线程将继续让步。

相关公共方法及使用方法​

  1. ThisInstanceProtected：告诉我们调用线程是否在纪元表中拥有一个条目，即当前是否参与纪元保护。如果没有，您可以通过调用 Resume 使其参与纪元保护。

  2. ProtectAndDrain：将当前线程标记为已更新纪元的拥有者，并执行到那时为止的动作清理。这由 Resume 内部使用。它通过清理挂起的动作来刷新共享变量。通常在循环中使用，以确保我们逐步清理动作。

  3. Suspend：使用此方法放弃对纪元的拥有权。如果调用 Suspend 的线程是 LightEpoch 系统中最后一个活动的线程，则会调用挂起的动作/写入。

  4. Resume：当线程需要查看共享变量的最新状态（所有其他线程都认为安全的状态）时使用此方法。它充当一个时间边界，在使用共享变量之前应用挂起的动作/写入。

  5. BumpCurrentEpoch(Action)：使用此方法在以后安全更改共享变量状态的时间边界处安排写入或动作。如果在此迭代过程中发现可以清理的值，则此调用可能会清理动作。