在分布式系统中，存在许多基本问题：高效的分布式事务，一次精确的数据处理，物理时钟的精确同步。 为了解决后一个问题，发明了不同类型的逻辑时钟 。
然而， 矢量时钟具有令人不快的特性：它们在不存在的事件之间引入条件依赖性，而在实际存在的条件下丢失。
但是，您可以提出更可靠的建议-Kronos。 在本文中，我们将研究因果关系会计算法及其在构建具有分布式事务的键值存储库中的应用。
问题所在
如前所述，逻辑时钟存在许多问题：
出现不存在的依赖关系是因为逻辑时钟对事件引入了完整的顺序 -也就是说，任何两个事件中的任何一个都可以说是有条件的，而有条件的则是有条件的。 合同是有条件的，因为不可能精确地确定事件之间的关系，包括由于相对论引起的特殊情况。
另一方面，逻辑时钟仅考虑通过系统内的消息进行互连。 如果连接了两个事件，但是在系统外部（例如，通过用户）（在系统的一个部分中将货物添加到购物篮中->订单付款），则逻辑时钟可能会错过这种关系。
无法从外部访问逻辑时钟，并且也很难互连多个独立组件（分布式文件系统，请求处理服务，分析）。
解决方案
Kronos在2014年发表的一篇文章：“事件订购服务的设计和实现”中提出了一种解决方案-一种独立的服务，它将考虑事件中的因果关系。
Kronos内部的主要抽象是引入部分排序的事件。 因果关系是可传递的-例如，如果我们知道文件的创建先于其更改，并且更改先于删除，则可以得出一个合理的结论，即创建是在删除之前进行的。
最低API可以通过以下方法定义：
| 方法 | 结果 | 评注 |
|---|
create_event() | e | 在Kronos中创建一个新事件 |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | 对于每对请求，它返回因果关系的方向或事件的同时性 |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | 对于每对请求，设置因果关系的方向 |
acquire_ref(e) | OK | 增加此事件的参考计数器。 |
release_ref(e) | OK | 减少此事件的引用计数。 |
实作
该系统基于事件的定向图是合乎逻辑的，它具有有效的广度优先搜索来检查事件之间的关系，故障时的稳定机制以及垃圾收集。
从API可以看出， assign_order请求assign_order接受因果关系类型： must或assign_order 。 must对应于严格的不变量-例如， _->_ ，如果与must关系冲突，则prefer可能不适用。 使用prefer一个示例是，较早发出的请求可以更早地打包，但这不会影响正确性。
有效的BFS
在我们的情况下，图表可能很大，但是将要执行验证请求的事件通常会很接近。 因此，在这种情况下，必须更快地运行BFS。
在标准实现中，最长的地方是访问顶点数组的初始化，该过程总是花费与图中顶点数相等的时间。 相反，您可以使用哈希表或应用其他技巧。
垃圾收集
从表中可以看到，还有两个方法： acquire_ref和release_ref 。
在Kronos内部，为每个事件存储了一个参考计数器。 当某些服务处理事件或保留添加在当前事件之后发生的新事件的能力时，它会存储链接。 当这种需求消失时，该服务将调用release_ref 。
当满足所有条件时，Kronos将删除该事件：
- 链接数达到零
- 之前的所有事件已从图中删除。
这种方法不会限制可能的查询，但是可以节省Kronos内部的内存。
应用领域
考虑使用具有分布式事务的键值存储示例的系统使用。
假设有几个服务器，每个服务器负责一系列密钥。
每个事务对应于Kronos中的一个事件。 对于每个密钥，服务器必须存储该密钥参与的最后一笔交易的编号。 客户端创建一个事件并将其编号发送到其密钥受此事务影响的所有服务器。 服务器正在尝试在Kronos中创建当前交易号和为此键保存的先前事件之间的依赖关系。 如果您无法创建依赖关系，则该事务将被视为不成功（请注意，到目前为止，尚未与数据进行任何交互）。
如果所有添加依赖项操作成功完成-这意味着将进行事务并且可以执行该事务。 服务器从客户端那里了解到这一点，并开始执行部分事务。
请注意，此类交易将为ACID ：
- 原子性 ：交易不会在Kronos中安排，或安排在所有节点上执行。
- 一致性 ：自动在KV存储库中。
- 隔离 ：如果两个事务根据数据相交，则它们将通过Kronos中的因果关系进行连接，这意味着一个事务将在另一个事务之前执行。
- 持久性 ：由于Kronos具有耐摔性，并且假定保管库的每个副本也是稳定的，因此唯一要证明的是未决交易数据的持久性。 实际上，如果客户端将事务标记为成功，但是服务器上的记录尚未完成，则很容易建立该事实，因为服务器还跟踪事务的完成部分。
性能表现
实施这种KV存储确实可以有效。 原始文章引用的数据表明，所描述的KV存储实现比基于锁的事务快4倍。
而且，与MongoDB相比，尽管MongoDB不使用分布式事务，但位于Kronos之上的系统仅落后6％。
分析方法
但是，Kronos的操作有几个缺点。
- 首先，访问Kronos有开销–每个请求将至少需要一个呼叫。
- Kronos也将是一个单点故障-本文的作者没有提供分割事件图的方法。
- 向系统中添加许多方法会很好。 例如，在具有KV存储的示例中，最好有一个回调来通知服务器事务状态-将其成功地添加到具有所有必要依赖项的图形中-或者相反，事务无法完成。
然而，所描述的系统允许灵活地控制事件之间的因果关系，从而确保对必要的不变量的可预测的依从性。
结论
关于这一点，我们在GoTo学校向分布式系统的方向教学生和学童。
并且有算法和应用程序 ，应用程序编程，生物信息学和数据分析
10月27日至11月4日来我们的秋季学校 ，或一月初来我们的冬季学校 。
如果您不再是学生或男生，那就来教书 。