[Day 26] Replication (4-3) - Leaderless Replication - Detecting Concurrent Writes & 结论

延续 (Day 25)

Detecting Concurrent Writes

Dynamo-style 资料库允许多个 client 同时写同一个 key 的资料，意味者资料的冲突势必会发生，虽然可以提升成 Read repair (Day 24) 和 hinted handoff (Day 25) 的问题 (也就是当节点挂掉问题来处理)，但这冲突追根究底是资料在到达多个节点时的顺序不同，一个简单的例子来说如下图：

• Node 1 接收了 A 的写入，但没接收到 B 的写入需求 (可能是网路问题)。
• Node 2 先接收了 A 的写入，然後是 B 的写入。
• Node 3 先接收了 B 的写入，然後是 A 的写入。

如果我们只是简单覆盖资料过去，最後在取得 X 的资料时，每个节点的资料会不一致，为了资料在每个 replica 的 eventual consistency (Day 22)，你不能指望资料库像个黑盒子般的解决冲突，现在我们就来看看这其中有什麽黑科技吧！

Last write wins (discarding concurrent writes)

最後写的是老大！Last write wins (LWW) 这个方法就是只保留 最近 的资料，然後覆写和舍弃旧的资料；这里最有趣的问题是什麽是 最近 ? 你可以选一个最大的 timestamp，你也可以选一个最大的资料版本号，LWW 也是 Cassandra 唯一支援的解冲突演算法。

LWW 是以资料库的耐用性为成本，如果我们有多个并行写入到同一个 key，尽管符合 w 的 quorums 量 (Day 24)，但最终只会有一笔资料存活下来，其他的资料会被安静的被干掉。

另外如果遗失资料是不被同意的，LWW 是个很烂的解冲突方法，这时唯一的方法就只能确保每笔资料只会写入一次，然後另资料成为不可变，Cassandra 就使用 UUID 做它的唯一 key。

The “happens-before” relationship and concurrency

首先要了解一下什麽是 happens-before relationship 和 concurrency (并发性)：

• happens-before relationship

  以下图为例子来说明，Client B 更新资料时是依赖於 Client A 所新增的值 (value = value + 1)，换句话说 B 的操作一定比 A 之後，也可说 B 是 因果依赖 (causally dependent) 在 A 上。

  

• concurrency

  如最上面贴过的图 5-12，Client A 和 B 的操作可视为 concurrent (并行)，因为它们俩并不知道另一个 Client 是否有针对同一个 key 做操作，也就没有谁依赖谁的关系了。

一个操作是否在另一个操作之後 是判断是否为并发的关键，所以说 2 个操作 A 和 B 只会有 3 个关系：A 在 B 之前发生、B 在 A 之前发生、或者 A 和 B 为 concurrent (并发)，所以我们会需要一个演算法来帮助我们若是 happend-before 关系我们需要覆写旧的值，若是并行则需要解决冲突。

Capturing the happens-before relationship

我们就用一个简单化的购物车例子 (replica 只有一份) 来说明演算法怎麽工作吧，请先看下图：

图 5-13 示范了 2 个 client 同时操作购物车时之间的资料依赖关系，一开始的购物车是空的，各步骤的解释如下：

1. Client 1 新增了 milk (牛奶) 到购物车里，这是该 key 的第一次新增，所以资料库储存後也指派成 version 1，然後在回覆刚刚新增的资料给 Client 端。
2. Client 2 新增了 eggs (蛋) 到购物车里，Client 2 并不知道 Client 1 已经并行且成功的新增了 milk (牛奶) 到购物车里，资料库对 Client 2 的写入指派成 version 2，然後将 eggs 和 milks 分开来存，最後在回覆这 2 个值给 Client 2。
3. Client 1 不知 Client 2 新增 eggs 成功，他这时想新增 flour (面粉) 至购物车里，所以 Client 1 认为此时购物车应该是 [milk, flour] ，所以就随着先前取得的 version 1 一起传给资料库，跟它说我想覆写 version 1 的资料成为 [milk, flour]，但是这里已经有个并行写入的 [eggs] ，因此资料库就对 [milk, flour] 指派了个 version 3 的编号，并覆写了 version 1 的 [milk]，同时保留 version 2 的值 [eggs]，然後把留下来的所有值回传给 Client 1 。
4. 同时，Client 2 想新增 ham (火腿) 至购物车中，Client 2 此时并不知道 Client 1 已新增成功 flour，Client 2 先前已从资料库接收到 2 个值 [milk] 和 [eggs]，所以 client 端可以合并他们并加入想要新增的 ham (火腿) 成为新的值 [milk, eggs, ham]，Client 2 一样随着前一个接收到的 version 2 编号一起将新值传给资料库，资料库一样知道 version 2 的 [eggs] 要被覆写成新的值，但此时有并行的 version 3 [milk, flour] 存在，所以就保留 version 3，并将 [milk, eggs, ham] 指派成 version 4。
5. 最後，Client 1 想新增 bacon (培根)，一样合并 version 3 中的资料成为 [milk. flour, eggs, bacon]，并告知资料库要覆写 version 3 (注意 verison 2 的 eggs 已被上一步覆写了)，一样因为有并行的 [eggs, milk, harm] 资料存在，所以资料库也是持续保留这 2 个值。

图 5-13 的资料流可以视觉化成下图，自从另一个 Client 在做并行操作後，每一个 client 都没有维持在最新资料，但旧的 version 资料最终还是会被覆写成新的，且没有资料会遗失。

这里要留意的是写入时务必要搭配 version 编号，否则不会覆写任何资料。

Merging concurrently written values

这个演算法虽然可以不让资料被舍弃，相对的它会造成 Client 额外的工作，Client 必须做合并的工作，写入冲突在 Day 23 时有介绍过，依不同场景能选择不同方法，最简单的方法就是上面介绍过的 LWW；图 5-13 的购物车例子是使用 union (联集) 方法。

合并的工作是很复杂且容易错误的，需要努力为其设计资料结构执行，有兴趣的可以找书看 “Automatic Conflict Resolution” on page 174 讲 Riak 怎麽为其设计一个资料型态来做合并。

Version vectors

图 5-13 介绍的例子是针对单一 replica，那本章的重点 leaderless replication 呢？

这时我们就需要每个 replica 中的每个 key 都会有自己的 version 编号，这个 version 的集合称为 version vetor ，这个 version vector 会让资料库区分哪些是覆写，哪些是并行来的资料，然後其他的处理概念跟单一 replica 差不多。

总结

终於到总结啦！

Replication 这章首先在讲做分散式资料的原因：Scalability, Fault tolerance/high availability (容错 / 高可用性), Latency 。

最後在讲做 replication 的方式：

Single-leader replication (Day 21, Day 22)

Multi-leader replication (Day 23)

Leaderless replication (Day 24 ~ Day 26)

明天，就会进入了 partition 环节，如何把大的资料集切成小的。