两个客户端Alice和Bob正在尝试同时写入有两个节点的最终一致的webscale数据库 。 当Alice写的第一个值成功同步时 ， Alice的第二次写入恰好与Bob的同时发生 。 在这种情况下 ， 数据库必须解决冲突 ， 以便所有节点之间的数据保持一致 。 在LWW的情况下 ， 将通过比较每次写入的时间戳来选择最新的写入 。
如果时钟完全同步 ， LWW可以完美地工作 ， 但是 ， 如果时钟同步性差并且第一个节点的时钟漂移到第二个节点之前 ， 则LWW变为Lucky Write Wins - 连接到幸运节点的客户端总是赢得冲突 。
NTP
确保群集中不同节点上的时钟同步的标准方法是使用网络时间协议（NTP） 。
NTP不仅有助于同步时钟 ， 还有助于传播闰秒标志 。
处理闰秒的传统方法是“飞跃涂抹” 。 负责飞跃模糊的NTP服务器可以在引入第二个之前的12小时之前和之后的12小时内分配额外的秒 。
在这24小时内的挂钟时间越来越慢 ， 每秒钟的时间延长了1/86400 ， 这可能会令人惊讶 ， 但不会比跳回时间更令人惊讶 。
问题是没有多少NTP服务器支持跳跃模糊 ， 公共NTP服务器绝对不会 。
主要的云提供商Google和AWS都为NTP服务提供了飞跃涂抹支持 。 如果您的应用程序托管在提供NTP服务的平台上并且您关心时钟同步 ， 那么检查NTP同步是否与提供商的NTP服务一起设置是值得的 。
它不仅可以帮助避免应用闰秒的恶劣后果 ， 而且还可以显着降低同步错误 ， 因为在单个数据中心内网络延迟通常要低得多 。
在最好的情况下 ， 使用本地NTP服务器可以将时钟漂移降低到毫秒甚至微秒 ， 但最坏的情况是什么？关于这个主题的研究不多 ， 但Google Spanner论文中提到了一些值得注意的结果 。
在同步之间 ， 守护进程宣告缓慢增加的时间不确定性 。 ε来自保守应用的最坏情况本地时钟漂移 。 ε还取决于时间主站的不确定性和时间主站的通信延迟 。
在我们的生产环境中 ， ε通常是时间的锯齿函数 ， 在每个轮询间隔内从大约1到7毫秒变化 。 ε？因此大部分时间都是4毫秒 。 守护程序的轮询间隔当前为30秒 ， 当前应用的漂移率设置为200微秒/秒 ， 它们共同占据了0到6毫秒的锯齿边界 。
- Spanner：Google的全球分布式数据库
逻辑时钟
即使我们集群中的监控显示时钟与微秒精度同步 ， 我们也需要谨慎 ， 如果这种假设的失败是不可接受的 ， 我们的软件就不应该依赖它 。 因此 ， 如果失败是不可接受的 ， 我们需要知道分布式系统中事件的顺序 ， 那么我们能做些什么呢？与往常一样 ， 学术界提出了许多解决方案 。
1.Lamport时钟
我们需要的是对系统时钟的可靠替代 ， 因此对于每两个事件A和B ， 我们可以说A发生在B之前 ， 或B发生在A之前 。 事件之间的这种顺序称为总顺序 。
在“时间 ， 时钟和分布式系统中事件的排序”一文中 ， Leslie Lamport描述了“之前发生”关系和逻辑时钟 ， 可用于使用以下算法定义一组事件的总顺序 。
发送消息：
time = time + 1;send(message time);
收到消息：
(message ts) = receive();time = max(ts time) + 1;
在这种情况下 ， 每个参与者Alice和Bob每次发送消息时将通过维护增加的time计数器来维持当前时间的共享视图 ， 并且当接收到消息时 ， time总是大于上次接受消息时最后观察到的计数器 。 这样 ， 如果Alice更新数据库的值为2 ， 并告诉Bob关于最后一个已知状态 ， Bob的最终写入是先查看Alice计数器 ， 因此它被选为数据库的最终状态 。
只要我们需要定义系统中捕获因果关系的事件的总顺序 ， 这就完美地工作 。 重要的是要注意 ， 具有总顺序意味着并发事件将以某种方式排序 ， 而不一定是最合乎现实逻辑的方式 。 向量时钟解决这个问题 。
矢量时钟/向量时钟
为了处理真正的并发事件 ， 我们需要一个新的定义或命令 ， 它能够表达事件可以同时发生的情况 。 这种顺序称为部分顺序 。 这意味着对于任何两个事件A和B ， 可以说A是否发生在B之前 ， B发生在A或A和B同时发生之前 。
为了确定部分顺序 ， 可以使用以下算法 ， 其中每个actor都有一个单独的时间计数器 ， 并跟踪系统中任何其他actor的最新时间戳 。
发送消息：
