并发写检测

上图:

最后写胜出(last write wins)

让后来的写操作覆盖之前的数据

只要保证两点:

  • 时间的相对概念;
  • 每个写操作都会到达每个副本。

为了保证第一点,为每个写操作附加一个写操作发生的时间戳。当所有副本接收到对同一个数据的并发写操作时,取最后一个写,抛弃其他的写,而且每个副本都这么做!

这种方法解决了写冲突,但是可能会丢失持久性:因为对同一个 key 的多个写只会被保留一个!

为了保证数据不被丢失,一种方法是:

对每个 key 的写操作都是唯一的。因此就不存在并发写操作了。比如,在 Cassandra 中,推荐使用 UUID 作为 KEY。

之前发生 和 并发 的关系

到底什么是并发

操作 A 在操作 B 之前发生:如果 B 知道 A 的存在,或者 B 操作取决于 A,或者 B 基于 A。

两个操作是并发的:当没有任何一个操作发生在另一个操作之前。

所以两个操作之间有三种可能的关系:

1
2
3
- A 在 B 之前发生;
- B 在 A 之前发生;
- A 和 B 是并发的。

关于并发和时间的关系,看这个解释:

捕获和之前发生的关系

一个检测两个操作之间关系的算法:

这个操作其实是有点复杂的,请仔细阅读上面的图,注意后面每次给客户端返回的时候都返回两条数据以及一个版本号

从图中可以看到,旧版本的数据总会被更新,并且没有任何写操作丢失。

注意到一点:数据库可以通过版本决定两个操作是否是并发的。这个算法是这样的:

  • 每个 Key 都有一个版本号,对这个 Key 的每次写操作都会增加版本号,并且这个版本号和更新后的数据共同存储;
  • 对这个 Key 的读操作会返回所有没有被覆盖的数据和最新的版本号。客户端在写之前必须先读。
  • 当客户端对一个 Key 写的时候,这个写操作必须包含上一次读的版本号,并且必须将上次写后接收到的所有数据合并后一起发送过去。
  • 当接收到一个带有Old版本号的写操作时,服务端可以用这个 Value 覆盖比这个 Old 版本号更小的版本的数据,但必须保留号更高的数据。

合并数据

上面这个算法看起来很完美,唯一的问题是:客户端需要做大量的操作,主要是合并数据。

合并数据是个头疼的问题,特别是当有删除操作时:这时需要一个标志表明这个版本包含删除操作。(被称作 tombstone),在之前的日志压缩章节中有类似的描述。

版本向量

当架构从单节点变成无主多节点后,使用 版本向量 来记录本节点的数据和版本的同时也记录其他节点的版本。

总的来说,版本向量是很有用很有用的。

这一章就到这儿了。