间隔树时钟

我想收集一些有关间隔树时钟的笔记，这些年来我一直在脑海里。 PauloSérgioAlmeida，Carlos Baquero和Victor Fonte在2008年的论文中介绍了间隔树时钟。这是我所见过的最有趣，最易读的论文之一，但我不记得有很多生产系统都在使用该机制，而且我也不完全清楚为什么。这些年来，当我讨论它时，我几次意识到我提出了一种模式，该模式可能使它比其他人所想的更实用，但从未真正写下来。

我不是学术人员，因此我对其中的任何形式都采用零形式主义。我在这里写的东西只是我在“听起来像应该工作”，这是我要去做的。

这篇论文真的很棒，因为作者不仅仅满足于证明其合理性的数学，他们还使用数据结构的直观表示来帮助理解它：

间隔树时钟的工作方式与矢量时钟相当，因为您可以跟踪因果关系，找出冲突等。但是，它的主要不同之处在于，它旨在用于群集成员可能会不断变化的非常动态的环境中。

这样做的技巧是将时钟基于节点之间可分割的ID，以便集群的任何单个成员都可以细分其自己的密钥空间，并将其中的一小部分交给另一个（作为fork），或者实现团聚他们中的任何两个在一起（作为联接）。

{{1,0}，0} {{0,1}，0} {0，1}█▒▒▒▒█▒▒▒▒██

这三个ID仍然是唯一的，并且仍然可以完美地合并或细分。例如，我可以将第一个ID与第三个ID结合起来并获得：

但是，该ID仅是时钟的一半。时钟通过根据ID递增计数器来工作。仅当两个组件都在附近时，您才具有完整的间隔树时钟时间戳。

您可以在分隔线下方看到深灰色的ID，并在其顶部看到事件计数器。在第2步，两个节点都增加了计数器，因为它们已看到事件或修改了事物。

本文在时间戳上定义了以下操作，这可能有助于解释先前的图像如何工作：

fork：使用一个时钟，并在事件计数器相同的情况下对其进行新表示，但是ID部分如上所述。这是在步骤1、3和7发生的情况

事件：根据时钟的ID在时钟顶部增加计数器。这就是在2、4（底部）和6（顶部）发生的情况。

join：合并两个时间戳并获取一个新的时间戳。这是在5和8发生的情况

窥视：创建时间戳的副本，但具有NULL ID，以便可以读取事件计数器，但不能递增事件计数器。在图中未显示。

sync：join + fork的原子组成。这未在图中显示，但可以认为是保留它们的ID，但合并事件计数器。

该算法变得更有效，因为它可以处理自己在时钟组件中的等效项，以减少其复杂性和大小，而不会丢失信息：

由于假定ID空间在集群成员之间是不重叠的，因此最后一个图像显示您不需要增加与ID匹配的所有空间，而只是其中一部分。在这种情况下，该算法可确保在增加计数器值并为其添加信息时，数据集的数字表示更加紧凑。这是本文的另一个示例：

ITC的问题在于，如果您从未处理过数据结构及其操作，就很难将其转换为功能系统。

第一次查看它们时，我是在IRC上与一位朋友讨论的，我们只是摸索着试图弄清楚我们应该如何通过简单的键/值存储实际使用这些东西，因为这些通常很容易推理一下。这是我们问的几个问题。

您是否为每条记录和每条记录使用一个ID，然后从那里递增事件？在节点A和B以及用户与其中任何一个进行交互的情况下，这似乎可以正常工作：

用户将数据写入A，这将创建ID 1 =████，并将计数器也增加到1 =████。

A通过分叉戳记与B同步，并提供ID {1,0} =██▒▒和{0,1} =▒▒██。计数器仍为1 =████。

这样我们就可以同步了。每当我们交换步骤2和3时，都会发生此问题：

用户将数据写入A，这将创建ID 1 =████，并将计数器也增加到1 =████。

用户将数据写入B，B创建ID 1 =████，计数器也增加到1 =████。

由于时钟相同，系统只能假设两个数据集相等。

显然，如果没有严格地与要写入的单个节点（粘性）进行交互，则我们无法为每个记录动态创建ID。该方案可能会很好地跟踪整个系统的日志进度（因为通常只有一个入口点），但是对于键/值存储来说不够通用，因为该算法的显式要求之一是ID空间不重叠，我们可以轻松突破这一要求！

因此，我们需要确保有一条规则指出系统中仅存在不同的ID，这意味着我们不能只在需要时创建ID。我们得出结论，ID划分必须匹配每个节点的生命周期，而不是记录的生命周期。

因此，我们可以将种子ID附加到节点本身，然后要求对等方派生它们的ID。必须注意，首先首先使用单个根节点初始化集群，以避免出现这样的情况：我们启动具有许多节点的新集群，其中两个节点同时启动，并且都采用相同的ID。

引导根节点后，其他任何数量的节点都可以通过向其他任何对等方请求其ID的派生来开始加入。

这在逻辑上可以很好地工作，但是有一个隐藏的代价：如果您按照白皮书（id +事件计数器）中所述保留时间戳，并且拆分自己的ID的节点有1000万条记录，则必须立即重写这1000万个时间戳。如果您不这样做，则可能出现以下情况：

A：{1,0} =██▒▒B：{0，{1,0} =▒▒█▒C：{0，{0,1}} =▒▒▒█------ -------- ------------------ ------------------- K1：███ █K1：████K1：██████▒▒██▒▒██▒▒... ... ... KN：▒▒██KN：▒▒██KN：▒▒ ██▒▒██▒▒██▒▒██

那那里是什么？那么，同步表中的每个条目都没有被分叉，并且共享相同的ID。任何写操作都将重复使用相同的██▒▒节点ID，并以不跟踪因果关系的方式递增事件。每当A递增K1时，事情就起作用了，但是如果它开始写入KN，它将看起来像是B的旧版本向其写入的操作，这将与B和C当前的操作发生冲突。在派生之后（立即或在稍后的访问时间之前）重写每个条目将产生一个更安全的方法：

A：{1,0} =██▒▒B：{0，{1,0} =▒▒█▒C：{0，{0,1}} =▒▒▒█------ -------- ------------------ ------------------- K1：███ █K1：████K1：██████▒▒▒▒█▒▒▒▒█... ... ... KN：▒▒██KN：▒▒██KN：▒▒ ██▒▒██▒▒█▒▒▒▒█

现在，这可以使每个节点在跟踪因果关系时独立地修改时间戳，但是每次您派生一个节点时都要重写整个表，这将是非常昂贵的，并且很烦人。

一个更好的解决方案是将时钟分解为两个独立的组件：节点全局存储ID，每个记录仅包含事件计数器。在每个操作中，我们通过在每个操作上提交节点的ID，并在其余操作上提交事件计数器，来动态地重建时间戳。由于事件计数器是单调的，并且节点ID很少更改，因此我们可以以这种方式获得更便宜，更简单的方法。

这需要我们将间隔树时钟的设计稍微扩展一点，以支持“爆炸”和“重建”操作，这些操作可以拆分并重新加入时钟的单个ID +事件计数器部分。通过这种设计，我们可以前进并定义以下（非正式）协议。

为了有效，该协议要求我们打破几层抽象。这通常是一个坏主意，但是让所有层都知道它们正在携带间隔树时钟的折衷往往会超过重写每个ID拆分中的所有条目的代价。

要处理的第一步是ID传播，其中群集中的给定节点允许另一个节点加入并开始递增事件。

事实结束后加入群集的任何节点都必须联系至少另一个对等节点，并要求提供其ID的分支。理想情况下，对等体是随机选择的，以避免无限期地细分ID的相同部分，从而给出次优的ID空间。分叉节点选择任一侧，并覆盖其在永久存储区中的现有ID值（然后，它应等待所有使用旧ID进行的操作终止）

为了帮助减少ID和事件空间，离开群集的任何节点都可以：将其数据集与群集的其余（或部分）同步（请参见下面的数据传播）。

随机选择一个对等节点，并为其返回ID，以便将其加入自己的节点。另一个节点可以直接接受该ID。如果发生故障或超时，请不要重试发送ID。它只是迷路了。您可能希望将其记录在某处，以便管理员稍后可以手动调整值。

为了防止分叉节点将拆分ID发送到远端，然后崩溃重新启动或丢失更改，必须执行步骤2。如果发生这种情况，则整个集群的因果关系将被忽略，因为ID空间现在重叠了。因果关系已损坏。

步骤3必须看到步骤c，d和e以该特定顺序发生，以避免崩溃重新启动的情况可能要求立即将相同的ID加入到各个远程节点上。这将导致冲突和因果关系的恶化。步骤a和b是可选的（或可以与其他步骤一起使用），但是，如果有的话，可以避免数据丢失。

从这一点开始，取决于您要与版本向量还是向量时钟等效，这条路就已经存在。它们相同但不同。

基本上，相同的逻辑时钟机制可用于任何目的。区别在于您要跟踪的内容：

如果要跟踪对数据集（即数据库中的数据）的修改的因果顺序，则需要版本向量

如果要跟踪系统中事件的因果顺序（即跟踪“谁听说过此信息？”的信息流），则需要矢量时钟。

区别非常简单：为了与版本向量等效，在修改数据时增加事件计数器。对于等效向量时钟，无论何时发送或接收消息，都必须增加事件计数器。

即使区分很简单，也可能产生重要的后果。如果只需要版本向量，则可以跳过一些更新操作并获得一定的效率，甚至可以查看诸如虚线版本向量（DVV）之类的变体来代表客户端进行更改。请注意，尽管ITC可以用作版本向量，但它们不允许类似DVV的用法。另一方面，版本向量携带的信息较少：如果您要进行“一致剪切”，它们将不会像向量时钟那样“准确”。

推送数据以使其同步时，仅将事件计数器的每个条目发送到远程节点，而不发送ID。

接收数据时：如果当前戳记小于接收到的戳记，则将新的戳记与新的数据一起存储

在发生冲突的情况下，存在两种选择，要么是现场解决冲突，要么是跟踪冲突。但是，两个选项都可以在单个时钟下跟踪。要运行该时钟，只需同时连接两个时钟。因为我们只有远程事件，所以我们可以简单地调用：{_，EventCounter} = explode（％仅抓取事件，我们知道ID已经为事件（％增加事件计数器的联接（％合并事件标记peek（重建（LocalId ，RemoteEvent）），将远程图章作为只读重建（LocalId，LocalEvent）％完成一个完整的本地图章）））。

对于步骤2，要注意的一件事是客户。如果客户端在节点外部，则它是分布式系统的一部分。如果写入来自没有时钟信息的一​​方，则除非它与事件一起提交事件计数器，否则我们不一定可以假定它知道已有的数据或冲突。从本质上讲，我们必须考虑将这样的客户视为系统中的流氓参与者。为了使客户行事，它必须能够提交邮票，并且要使客户提交邮票，它必须首先读取数据，在此我们可以假定其内容已得到确认。如果在写入时提交了事件计数器，我们可以在写入时进行冲突检测。如果未提交任何内容，则我们可以始终粉碎该条目（last-write-wins），也可以声明冲突以待日后解决。

在4.d中描述的最后一个序列很有趣。因为我们只有三部分数据（本地ID，本地事件，远程事件）而缺少一个（远程ID），所以我们用自己的本地ID代替远程事件，然后使用“ peek”原语来还给我们一个ID为空的可合并事件时钟。然后，我们将它们重新连接在一起，以提供最新的完整本地时钟。由于我们要么选择了获胜者，要么开始跟踪冲突，所以数据已更改，因此我们必须增加事件计数器。然后，我们可以提取该部分进行存储。

现在，此印章比任何一个基本印章都要大，并且加价幅度将确保拥有任一副本的任何第三方现在都将被粉碎（或者，如果他们进行了修改，现在也将看到冲突）。

对于矢量时钟等效，与版本矢量方法相比，只需更改步骤3和4：

当推送数据以使其同步时，增加事件计数器并存储它。然后仅将事件计数器的每个条目发送到远程节点，而不发送ID。

接收数据时：如果当前戳记> =接收到的戳记，则合并两个计数器并在存储之前将其与本地标识一起递增

如果当前标记小于<接收到的标记，则将新标记与新数据一起存储，但是合并两个计数器并在存储之前使用本地ID对其进行递增

在这种情况下，我没有考虑过从备份还原。数据集应该可以安全恢复，因为事件时钟是单调的，并且应该能够独立进行比较（如数据同步的步骤4.d所示）。但是，如果任何节点先前已将自己从集群中删除，则恢复该节点存在风险，因为它可能会通过使用既有ID或现有ID的子集开始破坏时间表。

如果无法完全确定该ID是否仍然有效且尚未停用，请放弃该ID。 id空间将无限期地增长，但是其空间比版本向量或向量时钟本来要小得多。

我的假设是，到那时，您需要一种审核机制来查找已分配但不再使用的ID，并将其折回到正在运行的实例的ID中。为了保持备份正常运行，我希望有人在获得ID之前先等待给定的延迟。例如，如果您进行每日备份，则可以合理地假设，当您有六个新快照时，您不会带回一个星期的实例，因此可以安全地获取其ID。在仍然需要访问的情况下，您将陷入一种数据恢复模式，在这种情况下，您将不得不手工做一些花哨的事情（例如，使用新的派生ID重新启动实例，同时保留旧事件并查看有多少事件）。产生的冲突）。

我还没有真正检查过那里有什么意义，但是我不得不假设运送这种系统的人可能希望支持“仅使用”模式，其中从备份中带回的节点将尝试本地同步来自对等方的数据仅在实际尝试将所有数据运送到其他节点并传播潜在冲突之前检查冲突。

我写完这篇文章后，我不希望本文提出的内容有太多—而不是我所需要的形式主义，这需要更多的形式主义—但我希望看到它读起来更频繁。它所承诺的真正伟大的事情之一是可以在“大多数为脱机”设置中实现最终的一致性，而该选项具有非常有限的能力来知道实际群集的大小。

在过去的几年中，CRDT研究是其中大部分努力的方向，但我不知道这始终是处理事情的最安全方法。当您构建一个协作工具来端到端控制体验和工件时，这当然很有意义。在许多情况下，变更集不一定能以单调的方式合并，并且检测冲突是一件好事。其中一个例子可能是由不关心在结构上可合并的系统产生的工件，例如渲染文档或视频的版本，或者形成了格式数据，其中不同人的冲突条目无法安全地调和并需要特定于域的解析，例如我想象的处方药可能会发生的情况。

我个人一直在想办法在侧面（连续不断）制作一个点对点的保管箱，但从未真正走得太远，因为我一直被分散在做其他事情上的注意力，但我总是想象间隔树时钟将是正确的数据结构。