Datastore 冲突解决第一部分-离线冲突解决基础

# Datastore 冲突解决第一部分-离线冲突解决基础

> 原文地址 https://blogs.dropbox.com/developers/2013/07/how-the-datastore-api-handles-conflicts-part-1-basics-of-offline-conflict-handling/
## 关于

看了这篇冲突解决， 再回顾一下之前 datastore api 介绍的翻译，觉得受益良多， 也将这篇文章翻译一下（非直译）
## 介绍

datastore 的底层实现由很多不错的想法， 其中最基本的一个是将变更（changes）表示为对象，将变更对象作为基本单元在客户端和服务端传输，拷贝，序列化，持久化。

Dropbox server 存储了 datastore 完全的变更列表，以及 datastore 的快照（或者 state）, 快照可以通过执行变更列表中的所有变更来获取（实际获取快照的方法不是这样的，应该会更有效率）

变更在服务器中的存储方式是以 delta 为单位的，也即 change_list = [delta...], delta 为变更的列表和 一个版本号组成 即 delta = (revision_number, [change...]) . 这样的定义方式，我们就可以通过版本号可以指向特定 datastore 快照， datastore 的初始化状态完全为空，版本号为 0， 每次增加一个 delta 版本号 +1.

> 重上面的描述来讲，这样的定义很像 git 代码仓库， 每次 commit 相当于一个 delta， 每个 commit有多个变更，可以通过 commit 历史来获取所有文档
## 示例场景

为了方便，下面的示例是为了方便表达而伪造的，两个概念：
1. datastore snapshot
2. deltas

一个空的 datastore snapshot

**Datastore: revision 0**

| Table ID | Record ID | Values |
| --- | --- | --- |

**Datastore: revision 1**

| Table ID | Record ID | Values |
| --- | --- | --- |
| T1 | r1 | name="jack", age=6 |
| T2 | r2 | name="Jill", age=5 |

**deltas**

| Base revision | Changes |
| --- | --- |
| 0. | insert T1:r1{name="jack, age=6"}; insert T1:r2{name="Jill", age=5} |
| 1. | update T1:r2 {age=6} |
| 2. | delete T1:r1; insert T1:r3 {name="Fred", age=42} |

执行 delta 0 过后 Datastore 为 revision 1， 执行 delta1 过后 datastore 为

**Datastore: revision 2**

| Table ID | Record ID | Values |
| --- | --- | --- |
| T1 | r1 | name="jack", age=6 |
| T2 | r2 | name="Jill", age=**6** |

执行 delta 2 过后， datastore 为

**Datastore: revision 3**

| Table ID | Record ID | Values |
| --- | --- | --- |
| T1 | r2 | name="Jill", age=6 |
| T2 | r3 | name="**Fred**", age=**42** |

每个 delta 都是由一个特定的 client 发出来， 有可能 delta 0 由 client A 发出， delta 1 由 client B 发出， delta 2 又由 A 发出。 （并没有记录 delta 是有哪个设备发出的， 因为这种关联和构建 datastore 无关）

当 client 在线的时候，Dropbox 服务器将 delta列表同步到 client（通过 http 长轮训实现）

场景可以秒杀为
1. A ----delta0----> server ----delta0-----> B (ok)
2. A <----delta1---- server <----delta1----- B (ok)
3. B 离线
4. A ----delta2----> server -----> ?

算法支持任意多的设备间同步
## 冲突

上面的场景因为 B 离线， B 此时的 datastore 快照的版本为 2， 但是 A 和 server 的版本已经为 3 了

此时用户在 B 上对数据做了修改，当 B 重新上线过后，B 尝试将 delta 发送给 server

| Base revision | changes |
| --- | --- |
| 2. | update T1:r2 {age=7} |

server 知道自己已经是版本 3 了， 所以拒绝了 B 的请求，服务器的判断依据不是 内容，而是依据版本号， 如果基础版本号和服务器的版本号不同，那么直接拒绝请求

当服务器拒绝请求的同时，会将 B 滞后的 delta 发送回来， B 更新了滞后的 delta 过后，再讲 changes 发送给 服务器， 服务器再将 B 的更新同步给 A

假设 B 的修改为

```
update T1:r2 {age=7} [rejected]
```

B 滞后的修改为

```
delete T1:r1; insert T1:r3 {name="Fred", age=42} [accepted]
```

最终的结果是很顺利，无论以怎样的顺序执行这两个改变都会得到同样的结果，解决这样的冲突时很简单的