区间树时钟简介
2024-11-24
本文简要介绍了区间树时钟 (ITC) 的概念及其在分布式系统中追踪因果关系的应用。在主从复制文件系统中，需要判断不同节点事件的先后顺序以解决数据冲突。传统的版本向量方法在节点频繁加入和离开的动态系统中会遇到“actor explosion”问题，即版本向量中唯一节点标识符的数量不断增加。ITC 通过将实值区间[0, 1]分配给各个节点，并用整数曲线表示事件发生，来解决这个问题。新节点加入系统时，从现有节点分叉一部分区间；事件发生时，节点增加其区间内曲线的数值；节点离开时，将其区间合并回其他节点。ITC 的优势在于节点只需知道自己的区间信息，无需全局节点标识符，且曲线复杂度可控，可高效编码。
未分类
区间树时钟