五大实例详解，携程 Redis 跨机房双向同步实践( 二 ) _Redis

文章插图

下面这个问题就是由时钟问题引起的。大家知道，不同的互联网组件之间是靠着 NPT-Server 这一工具来达到时间的一致性的，但是不同的网络区域之间的 NTP-Server 却并不一定是同步的。即使同步，时钟的准确性往往取决于网络的稳定性（这一点与网络延迟无关，也就是说即时延迟是中美之间大概 200~300ms，如果是稳定的延迟，那么 NTP-Server 的同步也基本稳定）。
如下图所示，在下面的 Redis（我们称之为 Redis-B）的网络域的物理时钟（Wall Clock），比上面的 Redis（我们称之为 Redis-A）的网络域的时钟慢，在 Redis-A 上一个很早的操作发生之后，Redis-B 方才收到关于同样Key的操作。从逻辑上讲我们更希望 Redis-B 的操作作为最终结果，然而由于时钟的快慢，如果使用 Last Write Wins 的策略，反而是早些时候在 Redis-A 上面的操作占了上风，最终值为 VAL1 。

文章插图

2.4 Vector Clock
那么时钟快慢带来的问题，是否无可避免？其实未必。
以上面的问题为例，是不需要冲突处理的，只是单从 Wall Clock，我们无法判定逻辑操作的时间。所以引入了一个叫 Vector Clock 的逻辑时钟，来表示一个操作的发生时刻。
以下图为例，全局有两个点，我们通过两个向量来表示发生过的逻辑操作。

文章插图

这里不展开讲了，具体 Vector Clock 是如何定义的，有专门的论文论述。而 AWS 闻名遐迩的 DynamoDB，更是通过对 Vector Clock 的理论改进，找到了更加适合自己的一种叫 Version Clock 的理论依据，感兴趣的同学可以 google。
三、Tomstone -- 忆往昔才能看今朝3.1 Delete
前面讲了数据回环复制的处理、数据一致性的处理，这样一个简单的分布式K/V 数据库就诞生了，但是删除操作依然会成为系统的“阿喀琉斯之踵” 。
请看下图，假设我们已经存在了一个Key，在同一时刻 Redis-A（依照上文惯例，我们称上面的 Redis 为 Redis-A）收到了更新请求，设置 Key 为 VAL，而 Redis-B 却收到了 Delete 的命令，两个 Redis 互相同步之后，发现数据不一致了。

文章插图

问题的根源在哪里呢？在于 Delete 操作，将 Redis-B 上的值删除了，当 SET KEY=VAL 的更新操作到达之时，便没有了可以比较的对象。
3.2 Tomstone
这个问题该如何处理？既然是没有对象可比，我们创造一个对象不就可以了吗？于是诞生了 Tomstone —— 被删除对象的栖身地。对象的删除，我们只做逻辑删除，并不会将对象真正地从内存中抹去，而是放置在一个叫做 Tomstone 的地方，让其他后续的命令，能够和之前的命令有一个对比。数据的存留与否也就有了判定的依据。
四、GC -- CRDT 取经之路的通天河GC -- Garbage Collection，很多语言都有这个特性，像 JAVA，Go 。无独有偶，我们这里所说的 GC，原则和这些语言无异，都是为了处理一类不再使用，但是又占有资源（通常是内存资源）的一些数据的回收。
4.1 GC 的痛点
上一小节，我们简单介绍了 Tomstone 的概念，GC 也是由于 Tomstone 的引入而带来的在实践中不得不面对的问题，如下图所示：

文章插图

随着时间的推移，我们 Tomstone 中的对象会越来越多，直到吃掉你的全部内存，然后程序崩溃。
4.2 GC的解决方案 -- VectorClock 的灵活妙用
如何 GC 的问题，其实不如说是什么对象可以 GC，这里我们也举两个经典的GC算法：

寻根法（GC Root）
引用计数法（Reference Count）

两种算法各有优劣，Reference Count 可以方便地及时发现需要 GC 的对象，却无法解决循环引用的问题；GC Root 可以解决循环引用的问题，却给 GC 扫描带来了一定负担。
我们的系统，采用了类似 RC 的算法来实现 GC：如果发现其他所有同步的 Redis Peer Master 都已经知道了某个对象被删除的事实，那么这个对象，就可以被永久删除（也就是 GC）了。
怎么发现对方知道某个对象被删除了呢，前面有提到每个 Redis 都有自己的 Vector Clock，而 Vector Clock是和操作绑定的，只需 Redis 之间互通有无，互相了解到对方的 Vector Clock，那么如何发现某个对象是否过期的问题也迎刃而解。