系列文章:

快照隔离在一些分布式系统中的实现 (1) - 什么是快照隔离
快照隔离在一些分布式系统中的实现 (2) - Omid1

Omid1 发表于论文 Omid: Lock-free transactional support for distributed data stores。论文作者在之后的另一篇论文中对它的设计做了一些改进，并将 Omid 原本的设计称为 Omid1。为了方便，接下来我都会用 Omid 来指代 Omid1.

Omid 是什么

根据论文的描述，Omid 是一个用来为已有的数据存储系统支持事务的工具，并且事务是实现是 lock-free 的。这里有几个关键词：

  1. 工具
  2. 事务
  3. Lock Free

用更直白的话说，Omid 是一个外挂/插件。它可以和已有的数据存储服务（例如论文中使用的 HBase）组合，实现事务的支持。基于已有的存储服务是一个很有意思的设计选择。之前也有一些论文使用了相同的思路，比如Precolator就使用了Bigtable。使用已有的系统可以节省很多开发和运维成本。同时这些系统也已经经受了时间的考验，在性能上都没什么问题。

既然这个系列是关于快照隔离，很明显，Omid 支持的事务也选择了支持快照隔离等级。接下来，我们一起来看一看 Omid 是怎么支持快照隔离的。

Omid 的设计思路

在这个系列的第一篇文章里，我们已经介绍了快照隔离的一般实现思路。没有读过也没关系，这里我们再重复一下这个设计思路：

  1. 数据存储层会维护每个数据的多个版本。
  2. 事务开始前会分配一个开始时间戳 *Tstart*。
  3. 事务会记录自己修改的所有数据集合。
  4. 事务提交之前先会分配一个提交时间戳 *Tcommit*。
  5. 分配完时间戳之后会检查是否有事务和自己的修改数据集合有交集，并且该事务的提交时间戳在 (Tstart, Tcommit) 之间。

简而言之，根据这个实现思路，快照隔离的实现往往需要两个东西：

  1. 数据多版本
  2. 单调递增的(逻辑)时间戳

在 Omid 的设计中，数据多版本是通过 HBase 实现的。而单调递增的时间戳则是通过一个中心化的服务实现的，论文中将它称为 transaction status oracle，以下简称 TSO。这个服务除了分配时间戳之外，还会用来判断事务是否提交。

Omid 的实现简介

其实看到这里，Omid 的大概实现相信已经比较清楚了。我们分别通过 Omid 使用的数据结构，和读写操作的伪代码来了解它的实现原理。

数据结构

为了满足快照隔离的实现，Omid 分别在 HBase 和 TSO 中维护了不同的数据。

HBase 中主要保存了数据的多个版本。对于每一个 key，HBase 本身就会保存这个 key 对应的多个历史版本数据，并且每个版本的数据都有对应的时间戳。

TSO 中则维护了两张表，分别是 Commit 和 Last Commit Timestamp。Commit 表维护了从事务 ID 到它提交时间戳的映射。由于事务开始时间的时间戳是唯一的，Omid 直接使用了开始时间戳作为事务 ID。Last Commit Timestamp 表维护了从每一个 Key 到最近修改它并且提交成功的事务的 *Tcommit*。

伪代码

实现的关键部分主要是事务的开始，事务的提交，已经数据的读写。我们分别来看一下这几个操作的逻辑。

事务的开始

客户端会对 TSO 发起一个 RPC 调用，获得一个时间戳。

1
2
3
4
5
// Implemented by TSO
txn_timestamp start() {
  auto t_start = assign_timestamp();
  return t_start;
}

事务的提交

客户端会之前获得的事务开始时间戳 Tstart 以及修改的 key 的集合发送给 TSO。TSO 判断事务是否能够提交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Implemented by TSO
txn_commit_result commit(txn_timstamp t_start, set keys) {
    for (auto key : keys) {
        if (last_commit(key) > t_start) {
            // 因为提交时间戳一定比 last_commit 大，所以只需要判断 last_commit 是否大于 t_start
            return abort;
        }
    }

    auto t_commit = assign_timestamp();
    for (auto key : keys) {
        last_commit(key) = t_commit
    }
    return commit;
}

数据的读写

数据的写相对比较简单，完全在客户端实现。客户端在 HBase 中将 (key, t_start) 的值设置为对应的 value 即可。注意这个写操作是在事务提交之前做的，这也就意味着 HBase 中存储的值并不一定提交成功，在读取的时候需要通过 TSO 做判断。

数据的读比较复杂，下面是它的伪代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
value read(key key, txn_timstamp t_start) {
    txn_timestamp end = t_start;
    while (true) {
        list<value> values = read_n_values_before(key, 10, end);
        if (values.empty()) {
            return nullptr;
        }

        for (auto value : values) {
            if (in_snapshot(value, t_start)) {
                return value;
            }
        }
        update end to the earliest timestamp of values.
    }
    return nullptr;
}

// 需要访问 TSO
bool in_snapshot(value value, txn_timstamp t_start) {
    // 写下这个 value 的事务的开始时间戳
    txn_timestamp value_start_timestamp = value.txn_start_timestamp();
    txn_timestamp value_commit_timstamp = commit_table(value_start_timstamp);
    return value_commit_timstamp != nullptr // 意味着写这个值的事务提交成功了
        && value_commit_timstamp < t_start; // 意味着写这个值的事务在当前事务之前提交
}

问题和 Omid 的解决方案

上面的实现思路虽然很简单，但是在性能上会有一些问题。

  1. HBase 中没有提交的事务写入的数据会额外占据空间，同时老版本的数据也会。
  2. commit表会随着运行时间不断增大。
  3. last commit表和 key 的数量成正比，TSO 作为单节点无法在内存中存储全部。
  4. in_snapshot需要访问 TSO，一个事务会访问很多次，造成 TSO 压力过大。
  5. TSO 的稳定性。

为了解决这些问题，Omid 在实现上做了一些优化。我们接下来一一分析。

HBase 中的数据

对于没有提交成功的事务的数据，客户端在收到提交失败的响应之后，可以自行删除刚刚写入的数据。与此同时，Omid 也会定期执行清理工作，通过判断一个 cell 的版本号是否在 commit 表中有对应的数据来决定是否需要清理。

对于老版本的数据，我们只需要保证当前还未执行完的事务能够访问他们需要读取的数据版本即可。TSO 通过维护一个 watermark 来记录所有分配但是还没有提交的事务即可。对于那些很久都没有提交的事务（有可能是 Client 进程挂了），TSO 也可以通过一个 TTL 来忽略，如果对应的 Client 又浪子回头提交事务，TSO 直接拒绝事务即可，不影响正确性。

commit 表的规模控制

和 HBase 数据规模控制的思路类似，commit 表可以在不影响正确性的情况下，丢弃很老的 entry。与此同时，TSO 会维护一个 Tmax*。这个 *Tmax 是所有丢弃的 entry 中提交时间戳的最大值，同时对事务提交代码做这样的改动：

1
2
3
4
5
6
7
8
// Implemented by TSO
txn_commit_result commit(txn_timstamp t_start, set keys) {
    // t_start 太老了
    if (t_max > t_start) {
        return abort;
    }
    // 和之前一样
}

这样的改动可能会有一些 false positive，但是概率不会太大，我们可以通过修改 commit 表的最大大小来控制这个概率。注意，即使错误的 abort 一个事务，也是不会影响正确性的。

做了这个优化之后，虽然 commit 方法可以正常工作，但是 in_snapshot 方法的正确性会受到影响，因为通过查看表中是否有某个版本来决定事务是否提交会出错。为此，TSO 又维护了一个被 abort 的事务 ID 列表，并对 in_snapshot 方法做如下修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 需要访问 TSO
bool in_snapshot(value value, txn_timstamp t_start) {
    txn_timestamp value_start_timestamp = value.txn_start_timestamp();
    txn_timestamp value_commit_timstamp = commit_table(value_start_timstamp);
    if (value_commit_timstamp != nullptr) { // 意味着写这个值的事务提交成功了
        // 意味着写这个值的事务在当前事务之前提交
        return value_commit_timstamp < t_start;
    }

    // 如果 commit 表中没有，可能是因为数据被 recycle 了，需要单独判断
    if (t_max < value_start_timestamp) {
        // t_start > t_max 说明不是因为 recycle 导致找不到
        return false;
    } else if (value_start_timestamp in abort_list) {
        // 在 abort 集合中，说明没有提交成功
        return false;
    }
    return true;
}

为了控制 abort 列表的大小，我们在清空 HBase 中无效数据的时候，也会顺便清理。

last commit 表的规模控制

为了控制 last commit 表的规模，Omid 使用 HBase 的 key 的 hash 值作为自己的 key，通过牺牲精度来换取空间。同时，如果某一个 entry 的时间戳如果小于 *Tmax*，我们也可以删除它。

TSO in_snapshot 的调用频率

之所以 in_snapshot 需要访问 TSO 是因为需要访问 commit 表。为了解决这个问题，Omid 利用 commit 表实际上是 append only 的特性，提出了一个巧妙的解决方案，将 commit 表的数据同步给客户端，以减少网络 I/O。而将 commit 表的数据同步给客户端的操作，是在客户端调用 TSO 开始一个事务的时候执行的，注意到 TSO 只需要将返回给客户端的时间戳之前的 commit 表的数据同步到客户端，就可以满足这个事务执行过程中 in_snapshot 的需求了。

TSO 的稳定性

Omid 通过使用 replica 来保证 TSO 的稳定性。当 TSO 挂了的时候，一个 replica 成为新的 TSO 需要恢复

  1. commit 表
  2. abort 列表
  3. Tmax
  4. last commit 表

对于前三者，Omid 使用 WAL 保证数据的持久化。Replica 在恢复是会重放 WAL 保证数据完整性。
至于 last commit 表，由于只用来检测写冲突，我们可以通过无脑 abort 所有比 replica 上位之后第一个事务还要早的事务，来避免恢复这个表。