JustForFun

关于 Spanner 的若干猜测

Posted by w@hidva.com on November 10, 2021

前言

Spanner 是之前就读过的论文, 但奈何当时对 PG 事务那一套, 快照, MVCC 比较推崇, 我在 KuiBaDB 中也完整地实现了事务, 快照, MVCC 这些概念, 根据这里实现得来的经验结合最近在 Hologres 接触到的新知识. 忽然意识到 PG 的事务模型可扩展性或许不是很好? 后续有空做几个试验测试下. 这篇文章不是 Spanner 介绍文章, 而是对 Spanner 论文一些我感觉模糊的地方所做的猜测. 非常欢迎/希望一起交流一下.

锁的实现

如 Spanner 论文所示, 仅有 paxos group leader 上具有 lock table, The lock table contains the state for two-phase locking: it maps ranges of keys to lock states. 我个人理解这里 lock table 为 HashMap<KeyRange, LockState>, LockState 定义如下;

struct LockState {
    cols: HashMap<ColumnId, LockMode>,  // Spanner lock object 是到列粒度的.
    prepared_ts: timestamp, //
    // ...
}

lock table 中元素的 KeyRange 应该互相之间没有交集, 我猜的, 毕竟这样应该好管理一些. 即然 lock 是发生在 paxos group 粒度的. 那么有个问题一个事务内多次 range scan 是如何避免看到新插入 key 的呢? 即如下场景:

事务1                                               事务2
begin;
select * from t where primary_key_col > 3;
                                                insert into t(primary_key_col) values(4)
select * from t where primary_key_col > 3;
end;

spanner 会保证事务内两次 select 看到同样的结果, 这个是通过锁保证的, 第一次 select 会 ReaderShared 锁, 阻塞事务 2 insert 要加的 Exclusive(由 WriterShared 升级而来)锁. 即然锁是发生在 paxos group 粒度, 意味着事务 1, 2 涉及到的 paxos group 肯定会有个交集, 这个交集中的 paxos group 检测到两个事务锁冲突, 那么这背后具体发生了什么.

猜想11: insert 会新插入行, 会生成一个新的 directory, 会需要为新的 dir 选择 paxos group, 此时总是会为这种新 directory 选择一个特定的 paxos group G1, 同时 key rang scan 每次也都会扫描 G1, 即 key range scan 总会在 G1 上加 ReaderShared 锁, insert 也总会在 G1 上加 WriterShared 锁, 此时由 G1 负责检测事务 1, 2 的冲突.

但另有一个问题, 比如 t2 INTERLEAVE IN PARENT t 的情况, 此时 insert t2 并不会生成一个新的 directory, 而是继续使用 t 中已经存在的一个 directory, 这时如何保证这个 directory 所在 paxos group 与 key rang scan 有交集呢? 所以 key rang scan 会在所有的 paxos group 上加 ReaderShared 锁?! 本来我想得是 key range scan 会有个 paxos group 裁剪的策略, 比如如上 primary_key_col > 3 可以避免扫描哪些 primary_key_col <=3 directory 所在的 paxos group, 但这样子的话看来这个裁剪不能有咯. 当然还有另外一个可能,

猜想21: 即 key rang scan 总会对表某个 paxos group G2 上加锁, insert 时也总会在 G2 上加锁, 即使 insert 的数据可能不在 G2 上. 进一步延伸每个表都会有一个仲裁 paxos group, G2 就是表 t 的仲裁 paxos group.

WriterSharedTimestamp

spanner 是支持如下建表的, 即 primary key 中包含 allow_commit_timestamp.

CREATE TABLE t2 (  UserId     INT64 NOT NULL,  DocumentId INT64 NOT NULL,  Ts         TIMESTAMP NOT NULL OPTIONS (allow_commit_timestamp=true),  Delta      STRING(MAX),) PRIMARY KEY (Ts, UserId, DocumentId)

我本来有一点想不明白的是, spanner 需要根据 primary key 确定表所在 directory, 从而确定所在 paxos group, 之后根据在 paxos group 上提交时间戳来改写 allow_commit_timestamp 列. 所以如果 primary key 中就包含了 allow_commit_timestamp, 那么该如何确定 directory, 后来一想也简单:

猜想1: 总是固定选择一个特定的 paxos group G2, 反正这种包含 commit timestamp 列的插入肯定会对应着一个新的 directory, 总是为这个新 directory 选择 G2 也是合理的, 当 G2 负载高的时候再慢慢迁移 G2 上 directory 到其他 paxos group.

但结合上面锁行为发生在 paxos group leader lock manager 的设定, WriterSharedTimestamp 还有存在必要么? 以 t2 表为例, 如下两条 insert 必然要选择同样的 paxos group, 如果 insert 1 发生在 paxos group G3, insert 2 发生在 G4, 那么由于 G3 上的 WriterSharedTimestamp 感知不到 G4 上的 WriterSharedTimestamp 锁, 导致 insert 1, 2 可能会并发执行, 导致 insert 1, 2 可能会具有相同的 COMMIT TIMESTAMP, 这就会导致相同的主键却位于不同的 paxos group 上这个 BUG!

insert into t2(Ts, UserId, DocumentId) values(PENDING_COMMIT_TIMESTAMP(), 1, 1); -- 1
insert into t2(Ts, UserId, DocumentId) values(PENDING_COMMIT_TIMESTAMP(), 1, 1); -- 2

所以一定要为 insert 1, 2 选择同样的 paxos group, 但考虑到同一 paxos group 事务总是串行提交的, 即使不加 WriterSharedTimestamp 锁, insert 1, 2 也会串行提交, 也会拿到不同的 COMMIT TIMESTAMP. 但既然 Spanner 引入了 WriterSharedTimestamp 锁, 所以我的猜测是,

猜想2: Spanner 会为每个表选择一个仲裁 paxos group, 即上文中的 G2, 之后 insert 1, 2 都会先在 G2 上加 WriterSharedTimestamp 锁, 在加锁成功之后, 才任选一个 paxos group 处理 insert. 这样 insert 1, 2 会位于不同的 paxos group, 由仲裁 paxos group G2 + WriterSharedTimestamp 来串行化这种行为.

但这样的话既然总是串行做的, 是不是猜想 1 效率更好一点?

Paxos Leader Lease

The simplest means to ensure the disjointness of Paxos-leader-lease intervals would be for a leader to issue a synchronous Paxos write of the lease interval, whenever it would be extended. A subsequent leader would read the interval and wait until that interval has passed.

我理解这里是说选择 leader 另一种操作是发起一轮 paxos 投票, 之后 leader 在每次租约末期再发起一轮 paxos 投票来延长续期. 在 Spanner 这里, 其 leader 选举链路如论文所述, 并不需要发起一次 paxos 投票, 但 spanner leader 选举链路与 paxos 投票看起来开销差不多, 毕竟 spanner leader 选举链路也需要 logs a lease vote, 该涉及到的 rpc 调用与 disk io 都没有减少. 不过 spanner 有个好处是在续约时, 如下所述, 在 leader 频繁进行 paxos writes 的情况下, replica 会自动延长 lease vote, 并且 logs a lease vote 可以作为业务 paxos write 负载一部分, 这里与一次正常的 paxos 投票开销就省了不少.

A replica extends its lease vote implicitly on a successful write, and the leader requests lease-vote extensions if they are near expiration.

事务

T_safe_TM, 若在 replica 视角内没有 prepared transaction, 则 T_safe_TM = ∞. 若在 replica 视角内有 prepared transaction, 则此时每个 prepared transaction 对应 prepare record 都有一个 timestamp, 即 S_prepare, 此时 T_safe_TM = 所有 prepared transaction 对应 S_prepare - 1.

Q: 为什么要减去 1?

A: 设想下不减 1 的情况. 对于一个分布式事务 T1; 其在所有 paxos group 上 prepare timestamp 都为 t1, 此时假设系统中只有这一个事务, 这些 paxos group replica 上 T_safe_TM = t1, T_safe 也是 t1; spanner 为 T1 选择的 commit timestamp 也是 t1, 之后 spanner 下发 COMMIT PREPARED with timestamp t1 到参与 paxos group G1, G2 上; paxos group G1 完成 commit prepared paxos write 的 apply, G2 尚未完成; 与此同时有一个 snapshot transaction T2 with timestamp = t1, 此时 T2 便会看到 G1 上已经提交的内容, 但看不到 G2 上未提交的内容, 导致 T1 对于 T2 而言不再是原子性的. 所以这里减 1 便达到了 GP 里面分布式快照的效果.

按照上面对 T_safe 的算法有个问题, 对于一个集群, 在我们不再发起写事务后, T_safe 将不再前进, 而保持一个固定值. 这时我们发起一个 key range scan, key range scan 会使用 TT.now().latest, 该假设来源论文如下内容:

The client avoids a negotiation round, and just executes its reads at S_read = TT.now().latest (which may wait for safe time to advance).

那么由于此时没有写事务, T_safe 无法前进, 所以 key range scan 将找不到满足的 replica 而永远阻塞直至有写事务出现, 这河里么? 这不河里! 我个人猜测是

猜想 14: T_safe_Paxos 对于 paxos group leader 总是为 ∞! paxos group leader 上的数据总是最新的, 其可以用于处理任何 timestamp Ts read, 在 Ts 之前提交的事务会确保已经写入了 paxos group leader. 而相对地对于 replica, 由于 paxos group leader 在大多数成员同意之后就返回, 所以对于一个 replica 不确定其上数据是最新的, replica 上可能尚未包含一些已经提交事务的数据, 所以 replica 不能用于服务任何 Timestamp read.

当然也可能是另外一个情况, 毕竟 paxos group leader 是知道哪些大多数 replica 投票同意自己发起的 paxos write, 即这些 replica 可以认为也是拥有最新的数据的, 所以其在收到 TT.now().latest read 时, 会将请求转发到这些 replica 之一进行处理. 但考虑到 Spanner paxos 是 multi-decree 并发投票串行 apply, 所以投票同意的大多数 replica 并不意味着已经 apply 到最新数据, 即不确定这些 replica 拥有最新的数据, 所以这条路子行不通.

Spanner 实际做法是引入了 MinNextTS(), 这一做法是猜想 14 相比是此时 paxos group non-leader replica 仍可用来处理 read, 具体在下面介绍.

2PC

Spanner 这里 2PC 链路与 Greenplum 的很是相似. 当 Spanner 上一个 2PC 事务准备提交时:

  1. The client chooses a coordinator group and sends a commit message to each participant’s leader with the identity of the coordinator and any buffered writes. 除了 client 发起之外, 另一种做法可以是 client 将所有 buffered write 发送给 coordinator, 由 coordinator 将 buffered write 分发给不同的 participant leader, 并开始 2PC. 很显然这种做法会导致一份 buffered write 传输了多次, 效率不高.

  2. A non-coordinator-participant leader
    1. acquires write locks,
    2. chooses a prepare timestamp that must be larger than any timestamps it has assigned to previous transactions (to preserve monotonicity),
    3. logs a prepare record through Paxos
    4. notifies the coordinator of its prepare timestamp

    和 GP segment 完成 prepare 之后, 接下来的 commit prepared 最终一定能成功一样, 当 participant leader 完成 prepare record 写入之后, 意味着接下来的 commit prepared 一定能成功.

  3. the coordinator leader
    1. acquires write locks,
    2. chooses the commit timestamp s = TT.now().latest, 后记为 t_abs_commit.latest, for the entire transaction after hearing from all other participant leaders. The commit timestamp s must be
      • greater than or equal to all prepare timestamps (to satisfy the constraints discussed in Section 4.1.3),
      • greater than TT.now().latest at the time the coordinator received its commit message, 为了遵循 4.1.2 提到的 Start rule
      • greater than any timestamps the leader has assigned to previous transactions (again, to preserve monotonicity).
    3. logs a commit record through Paxos. 类似于 GP 的 XLOG_XACT_DISTRIBUTED_COMMIT record. 这条 record 标记着两阶段事务成功提交了! 但此时两阶段事务还没有结束, 还有很多活要干, 还会遇到各种各样的失败, 但最终两阶段事务一定是能成功提交完成的.

  4. the coordinator leader waits until TT.after(s), 即 4.1.2 提到的 COMMIT wait rule. the expected wait is at least 2 * E, 这里 E 是 TrueTime 的平均误差, 考虑到 s = t_abs_commit.latest:

        t_abs_commit         s = t_abs_commit.latest
        |                       |                                  |                              |
        | -------- E ---------- |  --------------- E ------------- | ------------- E ------------ |
        |                       |                                  |                              |

    别忘了 s 是第 3.2 步确定的, 考虑到 3.3 步也需要花费一点时间, 所以很可能的一种场景是 3.3 步骤完成之后, TT.after(s) 一定为 true 了, 即不需要实质性等待了.

  5. the coordinator sends the commit timestamp to the client and all other participant leaders.

  6. Each participant leader logs the transaction’s outcome through Paxos. All participants apply at the same timestamp and then release locks. 这里 Each participant 我理解是本次 2PC 事务涉及到的所有 participant, 包含了 coordinator. 这里会再发起一次 paxos write, 该 paxos write 包含了 participant 各自的 buffered write, 这个 paxos write 对应的状态机行为是: 将 buffered write 写入到 tablet wal log 中, 以及 tablet memtable 中.

上面介绍了 Spanner 2PC 事务链路, 接下来分析链路中每一个点对应的 failover 措施:

Q: 在 2.4 部分 participant 发送了 prepare timestamp 给 coordinator 之后, coordinator paxos group 切主了怎么办?

A: 在 Greenplum 中, 在 master 切主之后, master 会收集所有 segments 上已经 prepare 的事务, 之后 abort prepared 这些事务. 这条路子在 Spanner 上行不通, Spanner prepare 请求是 client 发送的, 不是 coordinator, 当 coordinator 切主之后, 收集 participant leader 上已经 prepare transaction 时, 某些 prepare transaction 对应的 prepare request 尚未到达 participant leader, 导致 coordinator 收集到的 prepare transaction 不全. 更不用说 coordinator 切主之后, 并不晓得有哪些 participant 参与了 2PC 事务, coordinator 需要向 universe 中所有 paxos group 下发收集 prepare 事务请求这一浩瀚的工作量了.

所以 Spanner 中做法应该是 2.4 步之后, 若 participant 指定时间内没有收到 coordinator 响应, 则周期性重试 2.4 步. 对于 coordinator participant leader 其内存中维护着 <2pc-tx-id, 2pc-state> 的 map, 当 coordinator participant leader 收到 client 发来的 prepare 请求, 或者 non-coordinator-participant leader 发来的 prepare timestamp 之后, 如果 map 中指定 2pc 事务尚不存在的话都会在 map 中新建一项, 并更新相应的状态, 这个状态应该会包含最近一次状态变化对应的时间戳. coordinator participant leader 也会周期性扫描 map, 对于指定时间内状态没有变化的 2pc, 标记为 aborted, 并下发 abort prepared 给哪些已经成功 prepare 的 participant leader. 这个 map 不需要持久化, coordinator participant leader 切主之后新 leader 上该 map 为空.

回到问题, 假设 2pc 事务涉及到 3 个 participant leader: 1P, 2P, 3P; 1P, 2P 在发送 prepare timestamp 给 coordinator participant leader CPL 之后, CPL 切主了, 后以 CPL1, CPL2 区分, CPL2 map 为空, 3P 发送 prepare timestamp 给 CPL2, 此时 CPL map 填充了相应项, 之后 1P, 2P 再次重试 2.4 步给新 CPL2, CPL2 根据其 map 中 2pc 事务状态感知到收到了所有 prepare 之后继续进行二阶段提交链路. 也有另外一种可能, 当 3P 发送 prepare timestamp 给 CPL2 之后, 1P, 2P 由于某种原因挂起, 导致 CPL2 未在指定时间内收到所有的 prepare timestamp, 此时 CPL2 会 abort 2PC, 并下发 abort prepared 给 3P.

Q: Spanner ensures that a prepare or commit record is only logged while all locks are still held.

A: 这个好奇是咋确保的, 一个想法是通过锁. 比如如下伪代码:

lmgr.lock(); // 锁住 LMGR. 类似于 PG LWLockAcquire(LockHashPartitionLock(hashcode), LW_EXCLUSIVE);
check_lock_valid(); // 检测锁是否仍然持有
paxos_write_prepare_record();
lmgr.unlock();

但很显然这样持有锁时间太长了, paxos_write_prepare_record() 可是涉及到 rpc 与 disk io fsync 之类的. 另一个想法是:

lmgr.lock()
// 检测锁是否仍然被当前事务, 并标记当前 2pc 持有的锁为 uncanceled, 不可取消, 此时 wound-wait 死锁检测
// 遇到这种 uncanceled lock 不会再 kill 锁的持有者.
check_and_tag_lock_uncanceled();
lmgr.unlock();
paxos_write_prepare_record();

prepare record 会包含持有着锁的信息, 当 non-coordinator-participant leader 切主之后, 新 NCPL replay paxos record, 会再次把指定的锁再次加上并标记为 uncanceled.

Q: 2.4 某个 participant leader 持久化 paxos write 之前/之后切主了该咋整?

A: 若 participant leader 在持久化 paxos write 之前切主, 则对于新的 participant leader 是不知道 2pc prepare 这回事的, 我理解此时 CPL 会在等待指定时间之后发生没有收到所有的 prepare timestamp 而标记事务 aborted. 若 PL 在 paxos write 之后切主, 则其会 replay prepare record, 正常完成两阶段事务的处理.

关于第 4 步的 wait, 我有一个大胆的想法, 就是不 wait, 直接进行第 5 步, 由收到第 5 步 request 的 client/participant leader 进行 wait, 这样在经过又一轮 rpc 之后, 实际需要 wait 的时长应该进一步降低了. 但想来没有必要, 根据论文中的数据, 经过第 3.3 步骤之后, 基本上就不需要实质性 wait 了.

Q: WHY commit timestamp must be greater than or equal to all prepare timestamps (to satisfy the constraints discussed in Section 4.1.3

A: 设想一下, 如果允许 commit timestamp < 某个 prepared timestamp. 即有如下场景, 2PC 事务 Tx 在 participant leader 1P, 2P, 3P 对应的 prepare timestamp 分别是 P1, P2, P3, P1 < P2 < P3, 事务 commit timestamp = P3 - 1. coordinator participant leader 下发 COMMIT PREPARED 命令, 1P, 2P 执行成功, 3P 尚未收到 COMMIT PREPARED. 此时 3P 上 T_safe = P3 - 1; 1P, 2P T_safe >= P3 - 1 这时有一 read timestamp = P3 - 1 的 snapshot transaction 读取 1P, 2P, 3P, 由于 1P, 2P, 3P T_safe 均满足 read timestamp 要求, 允许 snapshot transaction 读取数据, snapshot transaction 能看到 Tx 已经在 1P, 2P 上成功提交的数据, 但看不到 Tx 在 3P 上的数据, 即 snapshot transaction 看到了 Tx 的中间状态, 这就是 bug.

事务与锁

Transactional reads and writes use strict two-phase locking, Spanner 采用 S2PL 协议. 在 Spanner 2PC 链路中, 锁相关操作如下:

  1. 事务中的读操作, 会在 participant leader 加读锁, 此时只会更改 participant leader 内存中 lock table, 不会有持久化行为. 我理解论文 Lock state is only logged during transaction prepare 的意思是指仅当 prepare 期间, 对 lock state 的修改才会被持久化
  2. 在 Prepare 时, 加写锁, 写 Prepare log. 如上所示, 这里会通过 check_and_tag_lock_uncanceled() 来检测所有 read lock/write lock 是否仍然被持有, 并标记为 uncanceled.
  3. 按照 S2PL 约定, prepare 成功之后, 这里可以释放 read lock 了.
  4. 收到 coordinator 发来的 COMMIT PREPARED, 并完成 COMMIT 之后, 释放 write lock.

4.2.2. Snapshot Transactions

这节注重描述如何在不违背 external consistency 前提下, 尽量使用较小的 read timestamp 来避免阻塞. 论文介绍了一种场景下的优化, 即当通过 scope expression 判断 snapshot transaction 所有 read 都只会发生在一个 paxos group 上, 并且该 paxos group 上没有 prepared transaction 时, 使用 LastTs() 作为 read timestamp. 这里 Define LastTS() to be the timestamp of the last committed write at a Paxos group, 以下图为例, 我理解是指 CommiT(Tx2) 对应 paxos write 的 timestamp.

# 某一 paxos group 上 paxos write 序列,                      尚未发生的 paxos write
+--------------+--------------+-------------+--------------+
| Prepare(Tx1) | Prepare(Tx2) | Commit(Tx2) | Prepare(Tx3) | Commit(Tx1) | Commit(Tx2)
+--------------+--------------+-------------+--------------+

我不明白的是, 如果 snapshot transaction 只涉及到一个 paxos group, 为啥 paxos group 上存在 prepared transaction, 就要使用 TT.now().latest, 而不能使用 LastTS(). 以下图为例, 此时存在 prepared transaction Tx1, Spanner 使用 TT.now().latest 作为 snapshot transaction read timestamp, 但这里 TT.now().latest 完全有可能等于 LastTS(), 即 LastTS() 所可能导致的副作用, 使用 TT.now().latest 一样能遇到.

# 图 2, 某一 paxos group 上 paxos write 序列,
+--------------+--------------+-------------+
| Prepare(Tx1) | Prepare(Tx2) | Commit(Tx2) |
+--------------+--------------+-------------+

当然在如下场景中, 使用 LastTs() 与 TT.now().latest 是有不同之处的, 使用 TT.now().latest 会由于 T_safe 导致 snapshot transaction 需要等待 Tx3 Commit 完毕才能执行, 而使用 LastTs() 则不需要等待 Tx3 执行完毕. 若使用 LastTs(), 在 snpashot transaction 执行不同时间点, Tx3 也可能处于不同状态, 可能是 prepare 中, 可能是提交中, 即 snapshot transaction 在扫描 tablet 时可能会看到 Tx3 的数据, 但由于 LastTs() < Tx3.comit_timestamp, 所以也会忽略 Tx3 数据, 所以也没啥大问题啊==

# 某一 paxos group 上 paxos write 序列,
+--------------+-------------+--------------+
| Prepare(Tx2) | Commit(Tx2) | Prepare(Tx3) |
+--------------+-------------+--------------+

后语

我在 KuiBaDB 实现 PG 事务, 快照, MVCC 时也感觉到时刻维护着一个运行中事务列表, 快照通过这个运行中事务列表表示, 通过这个运行中事务列表作可见性判断, 事务中的数据直接写入到文件这几点感觉在高并发下, 尤其是 Hologres 论文中提到的高并发场景, 这几点将是个不小的开销, 可能会制约 PG 在高并发场景下的表现. 对 Spanner, Hologres 的了解也促使我抛弃当前已经在 KuiBaDB 中实现的事务模型, 列存模型.

关于 TrueTime, 我挺好奇为啥各大云厂商没有上线 TrueTime 实现咧? 这个成本不是不高么, 而且云环境下成本也能被均摊来着. 而且需求应该也不小了, 毕竟 Spanner 已经验证了 TrueTime 可行性, 在 TrueTime 作为基础设施之后, 数据库实现上也能大大受益, 也不用整 TSO, HLC 这些操作了, 大家直接用 TrueTime 好了==

CATALOG