STAR 通过非对称副本消除分布式事务

STAR: Scaling Transactions through Asymmetric Replication 是 MIT 在 SIGMOD' 19 发表的一篇论文，利用一种较为新奇的方法消除了分布式数据库中的分布式事务，提升整体吞吐。但是也带来了延迟增大等一些副作用。

1.架构简介

现在常用的内存数据可以分为两种：（1）partitioning-based systems（2）non-partitioned systems。partitioning-based systems 在跨 partition 事务越少的情况下，表现越好，如果没有跨 partition 事务，那么系统的整体吞吐可以随着 partition 数目增多而线性增长。

STAR 是一个分布式的内存数据库，她不属于上述两种系统，而是利用非对称复制集（asymmetric replication），实现了一种新奇的相变算法（phase-switching protocol），分离了单 partition 的事务和跨 partition 的事务。

STAR 包含两类副本（因此称为非对称）：full replicas 和 partial replicas。显然，full replicas 包含了所有数据，但有可能是 primary records，也可能是 secondary records。每个 partial replica 只包含一部分数据，但 STAR 要求所有的 partial replicas 数据总和，应至少包含一个 full copy，这是为了防止 full replicas 都宕机后，集群陷入不可用状态。这里大家可能就要问了，如果还需要 full replicas 的存在，那岂不是没有解决数据量膨胀带来的空间不够的问题（which is 分布式数据库应该解决的）？这里需要说明一下，这篇论文作者所在的 MIT CSAIL 同样致力于新硬件的研究，他们认为目前云厂商已经可以提供超大内存的实例，例如 Amazon 和 Google Clouds 都可以提供 12 TB 的大内存实例（文章发表于2019年，现在应该有更大规格的了）。

STAR 间歇地通过两种状态接受用户的请求，分别是 partitioned phase 和 single-master phase。partitioned phase，无论 full replica 还是 partial replica，每个 node 处理一部分请求（类似于分布式数据库）；single-master phase，所有的请求都集中在一个 full replica 执行（类似于单机数据库）。假设目前集群中存在 f 个 full replicas 和 k 个 partial replicas，所有事务的写需要至少写 f + 1 个副本（f 个 full replicas 和至少一个 partial replica），因此 f 不宜设置过大，k 则可以设大一些。下图给出了一个 f=1，k=3的集群样例：

这种 phase switching 吸收了单机和分布式数据库的好处：

（1）single-master phase, 原来的分布式事务全部转为单机事务，不需要复杂的耗时的 2PC 协议，提升系统吞吐。

（2）partitioned phase, single-partition 事务并发运行在多个节点上，提升了系统并发度

下图是作者预测的根据 STAR 的模型，其性能随着节点数变化的图，不同曲线代表不同的分布式事务所占比率，显然分布式事务越少，扩展性越好。

STAR 的并发控制算法采用的是 Silo 的变种，Silo 是 MIT 13 年发的一篇针对多核数据库优化的 OCC 协议，其核心是 epoch-based group commit（每个线程维护一个本地 epoch），减少多个线程访问 global critical section 产生竞争，这样性能随着核数增长才会趋近线性。

STAR 默认是隔离级别是 serializable，但可以支持 RC 和 SI。支持 RC 的方式就是事务提交 validation 阶段跳过 read validation（即提交过程不再关注是否有别的事务读过）。支持 SI 则需要实现 MVOCC。

2.相变(phase switching)算法

phase switch 这个词，我自作主张翻译为相变，因为这里状态的改变，并非“阶段”，而是类似于物理概念里状态的改变。

2.1 两种状态

Partitioned Phase ：

限定只能执行单 partition 的事务，跨 partition 的事务需要等待到 Single-Master Phase 执行。在这个状态下，每个 partition 只有一个 worker 线程工作，从 client 处取一批事务单 partition 事务执行。正因为如此，事务执行过程不需要加锁和做 read validation。

Single-Master Phase

任何事务都能执行，因为 full replica 包含了全量数据。该阶段允许多线程并发执行。

每个阶段结束时需要保证该阶段所有的事务都被提交且持久化（在多副本上都写成功），回滚也是以 phase 为单位，因此每个 phase 的所有提交相当于 group commit，一起生效。

这里有一个问题论文没有解释，为什么 Partitioned Phase 每个 partition 只需单线程执行，而不是多线程去做？为什么Single-Master Phase 又要多线程执行呢？我的理解：单线程简单冲突少（本文是 OCC 并发控制），而且这一阶段的事务反正要一起生效，group commit 的已经保证了较大的吞吐。但是当整个系统退化为单机系统，所有请求由一个线程完成，效率过低。

2.2 相变

系统初始化是 Partitioned Phase，而后转化为 Single-Master Phase，然后不断的重复。为了将请求在某个特定的 phase 路由到正确的节点，路由节点需要知道系统的 partition 信息。

在 Partitioned Phase，工作线程从 clients 提取所有相关的事务到本地执行。当执行时间超过阈值 Tp，STAR 转化到 Single-Master Phase。在转换完成前，应该完成如下动作：

（1）STAR 停止所有 Worker 线程（不再接新请求，已经开始的需要做完）。

（2）所有的 replicas 获取 primary 的统计信息，知道事务已经执行到哪儿了。

（3）replica 回放到相同的位点。

（4）coordinator 节点做状态切换。

在 Single-Master Phase，工作线程从 client 拉取所有请求。由于事务可以并发执行，这里有一个优化：当隔离级别为 RC 时，可以将只读事务路由到 replicas，提升性能。之所以 RC 隔离级别才可以这么做是因为：OCC 并发控制本身可以避免 RU（OCC只有提交时才写入DB），因此 RC 是最低隔离级别，RC 隔离级别下不用做 Read Validation。而更高级别的隔离级别，在 replica 上读了数据，这个行为 Primary 不知道，因此事务提交时，无法感知已经有事务读过了这条记录从而让事务成功提交，更改了数据，导致无法实现 Serializable/RR。当执行时间超过阈值 Ts，STAR 转化到 partitioned phase。

上述 Tp 和 Ts 可以通过以下公式得到：

其中 e 为用户设置的一次相变周期的时长。tp 和 ts 是两个阶段的 throughput，P 指的是跨 partition 事务的百分比。tp，ts 和 P是系统实时收集的信息，e是一个经验值，其设置的太大，显然会影响延时，论文给出设最佳值为 10 ms ，latancy 在正常范围内时，吞吐效果也较好。

对于单 partition 事务，在哪个阶段执行都可以。

2.3 Fault Tolerance

日志定期刷盘，在某个 phase 结束时，要保证所有的记录在所有的 replica 上落盘。为了减少recovery time，后台定期 checkpoint ，checkpoint 的单位是 phase。

Failure 检测 ：

coordinator 会在相变发生时检测节点。失败的节点会被广播给所有节点，这样其他节点会忽略这些失败节点。coordinator 本身可以由 Paxos 或 raft 保证高可用。一旦检测到节点失败，系统回退到上一个成功的 phase。

Recovery：

恢复分为如下几种情况，这里 one complete partial replica 指的是多个节点可以凑齐全部数据

(1) At least one full replica and one complete partial replica remain.

例如下图2/6/7 挂掉，有系统仍然可以正常进行，故障节点自行恢复。

(2) No full replicas remain but at least one complete partial replica remains.

例如上图 1 和 2 挂掉，系统回退到传统分布式数据库的状态。直到节点恢复正常

(3) No complete partial replicas remain but at least one full replica remains.

系统可以正常运行，只不过在 partitioned phase，发往丢失partition的请求得重新路由到 full replica，直到恢复正常。

(4) No full replicas or complete partial replicas remain.

停写，直到恢复正常。

3.Replication

由于两种状态下，事务执行的方式是不同的（单线程和多线程），因此 STAR 采用不同的复制策略以求网络开销最小和性能最优。具体地，Single-Master phase，需要复制全量 records，而 Partitioned phase 只需要复制 Operations。

Partitioned phase 每个节点单线程执行，因此 replica 可以只复制更改值（例如某个 update 语句只修改了一个属性，其他属性不变），因为事务在主备上执行的顺序是确定且一致的。也可以直接复制 operation，以减少网络负载。例如在 TPC-C 测试中，Customer 表有一个很长的 string 类型的字段，这个字段经常需要在后面拼接新的短 string，显然主备间传输拼接短 string 这个 operation，比传输这个长 string 要划算。

Single-Master phase 事务是多线程并发执行的，所以它们在 replica 上回放的顺序可能与 primary 上执行的顺序不同，为了保证主备一致性，需要采用 Thomas Write Rule （TWR，OCC 并发控制中常用的写写冲突处理方法，这里略过证明其可以保证主备一致性的原理，其实就是 Tid 更大的写 wins，参考： https://www. geeksforgeeks.org/thoma s-write-rule-in-dbms/ ），而 TWR 就需要记录完整的 value，避免备库回放时，某个包含完整记录的事务回滚，不包含完整记录的事务却回放成功，导致结果不全。

例如如下两个事务 T1 与 T2 ，R1 和 R2 是两条不同记录。

T1: R1.A = R1.B + 1; R2.C = 0

假如 replica 先回放 T2，T1因为违反 TWR 而回滚，T2只回放 B 不带有 A 的信息的话，A 的信息就丢失了，主备不一致（下图左）。因此，此时同步的应该是 T2 执行后的 full value。而下图中间，T2 保存了完整的 value，即使 T1 回滚也没事。

注：Primary 执行的顺序是 T1 T2

4.Evaluation

这里列一些关键的实验结果，更详细的，读者可以自行查阅论文。

4.1 性能对比-吞吐

注：PB. OCC：单机 OCC ；Dist. OCC：分布式 OCC；Dist. S2PL：分布式 2PL，后两者都采用 2PC 协议。

1.上图（a）和（b）是异步复制性能对比，没有分布式事务时，STAR 性能与 Dist. OCC/Dist. S2PL 接近，均好于 PB. OCC，随着分布式事务所占比例增高，Dist. OCC/Dist. S2PL 性能下降很快，因为 2PC 协议会大幅提高持锁时间，影响并发。STAR 下降缓慢，明显优于 Dist. OCC/Dist. S2PL，当全部为分布式事务时，STAR 达到性能下限，也就是纯单机内存数据库。

2.上图（c）和（d）是同步复制性能对比， Dist. OCC/Dist. S2PL/PB. OCC 性能极具下跌，已经看不到 STAR 的尾灯了，因此图里没将 STAR 画出来。作者描述，YCSB 场景下 STAR 性能是其他的 7 倍，TPCC 场景下达到 15 倍。主要原因是同步复制需要的持锁时间大大加长，即使单机事务也会执行更久。但是 STAR 是一个 Phase 较大批量处理的，因此性能更好，但带来的问题就是一旦失败，更多事务将失败。

4.2 性能对比-延时

STAR 的 epoch-based group commit，必然导致延时固定且长。

4.3 相变的代价

每个 Phase 时间越久，相变的 Cost 占比肯定更低。如上图（a），作者认为 Phase 时间为 10 ms 时可以平衡相变的 overhead，性能和延时。