System|Concurrency|分布式事务

本文为CSE,IPADS,SE,SJTU课程笔记

摘要

在分布式系统中，为了保证事务仍然具备原子性和一致性，我们引入了多种机制。本文配套MIT yfs lab进行最佳。

原子性：Two-phase Commit

乐观一致性：Timestamp

悲观一致性：RSM/Paxos

背景

我们设定一个常见的垂直分库情景，Client+ 1 Coordinator+ 2 Servers。

Coordinator与Server都各自存储log，对于A-M的请求被Coordinator转发给Server1，N-Z的请求被转发给Server2。

分布式导致的问题

丢包、延迟、重复请求

我们使用RPC可以在一定程度上保证传输。（at least/most once）

崩溃

Two-phase Commit（原子性）

这里的箭头不是tcp的ack，而是单独的包。

Phase-1: preparation

• 低层次事务： abort/ tentatively commit
• 高层次事务：根据低层次事务的结果评估，所有低层次均未abort才能commit

Phase-2: commitment

• 顶层事务：abort/commit（事务最终状态）
• 嵌套事务: abort /tentatively committed（事务临时状态，可回退）

简单总结一下，就是Coordinator会直到所有Server的事务都tentatively commit之后，才认为Client的事务可以commit。

这个模型可以推广到更多层，直到最顶层的事务commit前，所有嵌套事务都只是tentatively。

Failure Handling

在返回OK前，由于不是checkpoint（均为tentatively），这个事务肯定能够安全回退。

在返回OK后，我们认为事务已经完成，但是实际上我们并没有已经修改tentatively，而是在发出commit请求之后才正式修改server端的状态。我们把OK这个点称为PREPARED，如果在OK之后：

仅仅丢包- 超时重发即可

server挂了-我们持有prepare的log，因此可以向coordinator询问是否已经ok，如果ok了，那么说明已经过了checkpoint，重复之前没有进行的commit过程。如果没有ok，那么说明是在prepare之后，ok前崩溃的，那么整个事务应该是Abort状态，因此不进行commit。

coordinator挂了-我们持有ok的log，因此可以对所有server再次发出commit。（commit幂等性）

通过这样的过程，我们可以将prepare而没有commit的所有事务均recover为committed。

Replication（Consistency）

为了鲁棒性，我们一般持有多个备份，那么保证这些备份之间的一致性就是关键。不同场景下，我们通常存在两种备份机制

• 乐观-允许不一致性，延迟修复（Timestamp）
• 悲观-强一致性（RSM&Paxos）

Timestamp（optimistic）

使用时间戳，本地记录最后一次同步时的时间。如果同步后：

• A未修改，B修改，则A同步为B的内容。
• A修改，B修改，则Merge（同git，冲突需要手动解决）。

差不多就是git等分布式版本管理工具的机制，这样的做法能够不遗漏所有的修改。那么我们如何保证不同机器时间戳同步呢？

日历时间戳

时间戳自1970/1/1开始计数，断电时通过主板上的电池依然保持计数。然而，由于物理原因，必然可能发生计数错误，因此同步时间戳很重要。我们使用NTS时间服务器作为标准，但是由于网络延迟，我们需要先计算出可能的延迟。下面是一个简易的算法，当然这个算法假设来回的延迟相同，如果想要更精确可能需要多次取样：

sync(server):
 t_begin = local_time
 tsrv = getTime(server)
 t_end = local_time
 delay = (t_end-t_begin) / 2
 offset = (t_end-delay) - tsrv
 local_time = local_time - offset

时钟同步

如果时间倒流了,那么就可能出现很多bug(是你,Bite The Dust!),例如,定时的操作会执行两次,gettime的差值变为负数.因此我们不能这么暴力,而是调整时钟频率,慢慢调整.

sync(server):
 t_begin = local_time
 tsrv = getTime(server)
 t_end = local_time
 delay = (t_end-t_begin) / 2
 offset = (t_end-delay) - tsrv
 freq = base + ε * sign(offset)
 sleep(freq * abs(offset) / ε)
 freq = base

timer_intr(): # on every oscillator tick
 local_time = local_time + 1/freq

此外,我们还想提升时钟精度本身,以免每次都有很长的时间不同步.我们可以长期来观测本地和远端的速度,并调整本地的时钟频率.

总体来说就是一个负反馈操作,具体的实现得控制论.

矢量时间戳

按照上面的实现,我们很难实现真正意义上的同步,因此我们可以不关注时间的绝对值,只关注先后顺序.

Vector clock space time (图片来源: wikipedia)

只有矢量V1的所有维度均小于V2,才能认为V1早于V2发生.大于同理.否则并行,我们认为存在冲突(没有看到其他机器的最新版本)

矢量时间戳带来了几个特性

• 只有同一个节点下的机器才有比较意义
• 无需时间同步
• 只需要单调计数器

相比而言,日历时间戳还是有一定的好处

• 袖珍-矢量时间戳随着机器数量增多,大小会变得很大.
• 跨系统-矢量时间戳在跨系统时没有其逻辑含义.

RSM(pessimistic)

某些场景下，不一致性是不容许存在的，例如lock server。因此我们牺牲一定的性能，来保证强一致性。

Strawman

Client每次请求

[公式]

个server。问题在于，如果

[公式]

个服务器没同时连接，那么服务器就会发生不一致。（Network Partition）

Majority

Client每次请求

[公式]

个server，如果能够连接到超过一半 （

[公式]

）的server，那么才能执行操作。

Quorum

[公式]

，这样两个majority之间必然存在交集。

读的workload重时，读的额度就应该适当减少，vice versa。

然而，由于客户端的请求到不同服务器的延迟不同，因此不同服务器看到的请求顺序可能不同（类似于内存一致性模型中的Processor Consistency，服务器类比为CPU）。

RSM（replicated state machine）

为了保证不同服务器看到的请求顺序相同，因此我们引入复制状态自动机，以确保服务器的状态转移一致。

所有的操作都是决定性的，所有备份具有相同的初始状态，那么只要输入的操作顺序相同，就能保证所有服务器的状态一致。我们通过Primary/Backup模型来保证这样的假设。

Primary/Backup Model

Primary负责与Client交互，Backup负责备份。收到请求时，Primary通知所有Backup执行对应的操作，并在所有Backup均执行后才请求成功。

如果多个C同时连接到一个Primary，其中某个C发生错误，导致切换Backup为Primary。那么这几个C连接不同的Primary，就会导致不一致。因此，我们引入全局的View Server，而不是让C决定谁是Primary。

View Server

仅仅负责记录谁是Primary，谁是Backup，每一组记录以一个view number标识。View Server接受所有Replicas的心跳数据。

Failure Handling

Coordinator不需要每次都请求View Server，可以本地缓存view，只需要在failure时更新Primary即可。

Rule

• Primary必须等待所有backup接受请求
• Backup必须拒绝所有直接的Coordinator请求。
• Primary必须拒绝backup的请求
• Primary必须是上一个view的Primary或者Backup

Primary无法连接时

Primary disconnect -> View 改变 -> Coordinator 请求 ->

Backup 收到任命 -> 请求成功

View Server决定谁是下一个Primary，并改变View。请求将会被发给新的Primary

Primary disconnect -> View 改变 -> Coordinator 请求 ->

-> Backup 拒绝请求 -> Backup 收到任命 -> Coordinator 重发 -> 请求成功

在Backup收到任命前，不会响应Coordinator的请求，然后Coordinator可以重发，直到Backup收到任命变为Primary后接受请求。

如果Primary并没有崩溃，只是无法连接View Server。

Primary disconnect -> Coordinator 请求 -> View 改变

-> Backup 收到任命 -> 旧Primary接受请求-> 新Primary拒绝请求 -> 请求失败

旧Primary无法从新的Primary处获得ACK，因此Rule 1不成立。

Primary disconnect -> Coordinator 请求 -> View 改变

-> 旧Primary接受请求 -> Backup 收到任命 ->请求成功 由于实际的任命还没有下达，相当于使用之前的Primary/Backup