本文为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)
崩溃
这里的箭头不是tcp的ack,而是单独的包。
Phase-1: preparation
Phase-2: commitment
简单总结一下,就是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。
为了鲁棒性,我们一般持有多个备份,那么保证这些备份之间的一致性就是关键。不同场景下,我们通常存在两种备份机制
使用时间戳,本地记录最后一次同步时的时间。如果同步后:
差不多就是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发生.大于同理.否则并行,我们认为存在冲突(没有看到其他机器的最新版本)
矢量时间戳带来了几个特性
相比而言,日历时间戳还是有一定的好处
某些场景下,不一致性是不容许存在的,例如lock server。因此我们牺牲一定的性能,来保证强一致性。
Strawman
Client每次请求
个server。问题在于,如果
个服务器没同时连接,那么服务器就会发生不一致。(Network Partition)
Majority
Client每次请求
个server,如果能够连接到超过一半 (
)的server,那么才能执行操作。
Quorum
,这样两个majority之间必然存在交集。
读的workload重时,读的额度就应该适当减少,vice versa。
然而,由于客户端的请求到不同服务器的延迟不同,因此不同服务器看到的请求顺序可能不同(类似于内存一致性模型中的Processor Consistency,服务器类比为CPU)。
为了保证不同服务器看到的请求顺序相同,因此我们引入复制状态自动机,以确保服务器的状态转移一致。
所有的操作都是决定性的,所有备份具有相同的初始状态,那么只要输入的操作顺序相同,就能保证所有服务器的状态一致。我们通过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的心跳数据。
Coordinator不需要每次都请求View Server,可以本地缓存view,只需要在failure时更新Primary即可。
Rule
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