揮手前

我是LITALICO的管理营养师Sadalsuud。我最喜欢的食物是比萨。

我以前就创作一些装置艺术作品并在Twitter上发布过，入职几天后发现公司的CTO @takish是我的粉丝。
之后发生了一些事情，我参加了公司内部的黑客马拉松活动，也参与了这个圣诞日历的创作。

因此，这是” LITALICO工程师降临日历2017 “的第12篇文章。

如果阅读变得乏味的话，只要看最后的gif后就可以回去了，非常感激。

分散数据库的表面谈话

在分布式数据库中，数据库被分成多个集群，并将处理任务分散到每个节点上。
AWS的NoSQL数据库Amazon DynamoDB被描述如下。

DynamoDB会自动将数据和流量在足够数量的服务器间进行分布，并保持一致的高速性能，满足吞吐量和存储的需求。所有数据都保存在固态硬盘(SSD)上，并通过自动在一个AWS地区内多个可用性区之间复制来实现高可用性和数据强大性。

据说在这种分散系统中，需要将在某个节点上发生的处理情况通知整个系统，以确保系统正常运行而不出故障。

因为尽管数据是分布式的，但它仍是一个数据库。所以，如果在复制的某个节点中 x=a，但在另一个复制节点中则是 x=b，这将导致一致性降低。因此，发生在某个节点上的事件将被通知到所有节点（多播）。

然而，即使发生了多播，每个接收节点都需要判断并更新x=a和x=b两个值中哪一个是最新的，以确定前后关系。

在非分散系统中，如果有时间戳，可以判断事件发生的时间。但是在分散系统中却不行，因为在分散的节点之间没有共同可用的“时钟”。

如果那样的话，我想要建立一个能够提供共同时间的服务器……但据说在不同时钟的不同节点之间拥有足够准确的绝对时间来比较事件的先后关系并不容易。

在这种情况下使用的概念是“逻辑时钟”。逻辑时钟不是指示事件发生的“何时”，而是指示事件发生的“顺序”。

用于表示顺序的机制之一是向量时间戳（Vector Clock）。

向量时钟（Vector Clock）的机制。

对于向量时间戳本身存在以下规则（注：实际在数据库中运行的向量时间戳的机制似乎是基于这里所描述的机制的发展。详细内容见后文）。

前提

全ノード数を n としたとき、各ノードではそれぞれ n次元のベクトルを持つようにします。
このn次元ベクトル各成分には、そのノードが知っている、各ノードで起こったイベントの数が割り当てられています。そこには自分自身のイベント数を割り当てるベクトル成分もあります。

更新のルール

自ノードでイベントが発生したときには、n次元ベクトルの自身が該当する成分をインクリメントします。
自ノードから周知メッセージを他のプロセスへ送信する場合は、自身のn次元ベクトルを添えて送り、そのあとにn次元ベクトルの自身が該当する成分をインクリメントします。
メッセージを受信したときは、まず自身が該当する成分をインクリメントしたあと、メッセージに含まれるn次元ベクトルと、自身の保持するn次元ベクトルを比較し、それぞれの成分に対して大きいほうの値をベクトルタイムスタンプとして保持します。

请看下面的例子。

由于总节点数为2，因此每个节点将具有2维向量。

而且，P1的向量中，第一个元素保存了自己的事件次数，第二个元素保存了当时已知的P2的事件次数。

起初，在P1上发生了一个名为A的事件。由于事件的发生，规则被接管并对自身进行了增量操作。[0,0] → [1,0]

接下来，P2会向P1发送一条消息。这条消息附带的是[0,1]。这表示P2发生了一次事件，所以首先将P1的相应组件加一，然后将P2接收到的事件次数存入相应的组件中。[1,0]变成[2,1]。

接着，C中也有活动，在增加自己的向量后，[2,1]变成[3,1]。
然后在D中给P2发送信息。[3,1]变成[4,1]。

当P2收到消息时，它会将自己的组件递增后，从消息中获取P1的组件。[0,2]→[3,3]

这样，向量时间戳将逐渐生成。

在使用向量时间戳进行前后关系比较时，需要对每个成分进行比较。

・如果在某一时间点，向量时间戳β的所有成分都比比较对象α大，则可以判断β发生在α之后。（即使存在相等的成分）

・如果在某一时间点，向量时间戳β的所有成分都比比较对象α小，则可以判断β发生在α之前。（即使存在相等的成分）

・如果在某一时间点，向量时间戳β和比较对象α的任意一个成分的大小关系均不成立，则无法判断α和β的前后关系。

在中文中，可以这样表达：
就像刚才的例子一样，在F[0,1]和C[3,1]中，C的每个元素都比F的值大。
因此可以判断C发生的时间比F晚。

那么，A和E的关系如何呢？
在A[1,0]和E[0.1]中，第一个元素A更大，但是第二个元素E更大。
因此，在这种情况下，我们无法判断A和B的关系是哪个先发生的。

在使用向量时间戳时，发送消息时必须确保发送节点和接收节点之间有比较前后顺序的关系。

通过更改每个节点的事件初始值并增加一个节点，生成了下图。

即使在这种情况下，也可以使用相同的规则进行每个节点之间的比较。

在中国，不需要考虑其他选项，在两个向量F[5,16,0]和C[9,16,0]之间，前两个向量中C的值更大，最后一个向量有相同的值，因此可以判断C发生在稍后。然而，在C[9,16,0]和H[5,16,4]之间，由于所有的向量都没有共同的大小关系，所以无法确定哪个向量先发生。

在向量时间戳中，尽管无法在所有情况下明确顺序关系，但如果消息在适当的时间发送，则可以成为显示处理因果关系的证据。

让我们试着将其可视化！

这个系统的可视化如下所示。
三个节点之间相互发送消息，并且在事件发生、消息发送和接收的时机更新向量时间戳。

消息到达的时间会因情况不同而有所差异，这是考虑到现实情况和网络状态可能导致的问题。

可视化的实施

由于要进行可视化，我希望能够实现可扩展性，并且能够动态地增加或减少节点的数量。然而，由于v4不擅长保持值，因此我想不到一个好的实现方法。最终，处理变得非常混乱和复杂，下面是这个补丁的整体情况。

我已经领略到了面向对象编程的伟大之处。

在确保因果一致性时，在数据库中的使用。

上述介绍的是向量时间戳的概念，然而为了确保数据库的因果一致性，实际上只有在数据写入时发送消息时才会进行值的递增操作。

假设P1持有[7,3]，并从P2收到了[6,5]。如果在P1这一边将持有的P2事件从3更新到5，那么P1将在不知情的情况下直接将4号事件转为5号进行更新。

为了防止这种情况发生，在实际处理中，当接收到不连续的时间戳时，将暂时保留更新，并等待尚未到达的消息的到达。

最后

当然，保持一致性不仅仅依靠于此向量时间戳，还有其他各种算法在起作用。
总之，算法如果被转换成影像，会很有情感对吧……。
在写这些的同时，我也想试着制作“Two-Phase Commit”的可视化效果，所以以后会尝试一下。
→我做好了！

(此处展示了我平时创作的作品等)

在处理内容时，我会参考各种文章和文献，以确保没有错误。但是，由于我只是一个像蘑菇一样茁壮成长的营养师，如果有任何错误，请务必指出，将不胜感激。

明天是@kazuis先生的「在确定新系统架构时要考虑的事项」！敬请期待！

我参考了以下网站和资料。

enPiT（東大・東工大）云系统基础（排序）
关于分散系统一致性的趋势
分散系统第7章（上半部分）
向量时钟：kei@sodan
因果排序：kei@sodan
分散系统读书会第06章-同步（上篇）
同步（2）互斥控制