杰普森:红色木筏1b3fbf6

2020-06-24 02:06:33

Redis是一种流行的内存数据结构服务器。从历史上看,Redis支持许多即席复制机制,但没有一种机制能保证比因果一致性更强的一致性。REDIS-RAFT的目标是通过RAFT共识算法给REDIS带来严格的可串行化。我们在Redis-RAFT的开发版本中发现了21个问题,包括健康集群中的部分不可用、崩溃、任何请求的无限循环、陈旧的读取、中止的读取、导致更新丢失的大脑分裂,以及在任何故障转移时完全丢失数据。除了一个问题(由于围绕快照的断言失败而导致的崩溃)之外,所有问题似乎都在最近的开发版本中得到了解决。这项工作由Redis实验室资助,并根据杰普森道德政策进行。

Redis是一种快速的单线程数据结构服务器,通常用作分布式应用程序之间的缓存、便签本、队列或协调机制。它提供对多种数据类型的操作,包括二进制blob、列表、集、排序集、映射、Geohash、计数器、通道、流等等。近年来,越来越多的生产用户将Redis部署为记录系统,促使人们更加关注安全和可靠性。

除了单个操作之外,Redis还支持Lua脚本和称为MULTI的事务机制,该机制允许客户端将操作组合到一个原子执行的批处理中。MULTI不提供交互式事务;只有在提交事务之后才能实现操作结果。WATCH命令允许事务检查键自上次读取以来是否保持不变-这是一个乐观并发控制原语。

Redis提供了几种复制机制,每种机制都有不同的权衡。Redis的初始复制机制将更新从主节点异步发送到辅助节点-辅助节点使用主节点在那个时间点恰好具有的任何内容覆盖它们的状态。故障转移是手动执行的,也可以通过Pacemaker等第三方监视程序执行。

2012年推出的Redis Sentinel允许节点在执行自主故障检测和领导人选举算法的外部进程的帮助下自动选择新的初选。Sentinel在网络分区期间丢失了数据,并在撰写本文时继续这样做:

通常,Redis+Sentinel作为一个整体是一个[原文如此]最终一致的系统,其中合并功能是最后的故障转移成功,并且来自旧主机的数据被丢弃以复制当前主机的数据,因此总是有丢失确认写入的窗口。

第二种复制策略是Redis Cluster,它提供透明分片和多数可用性。与Redis Sentinel类似,它使用异步复制,在某些类型的网络故障期间可能会丢失确认的写入:

通常,在较小的窗口中可能会丢失确认的写入。当客户端位于少数分区时,丢失确认写入的窗口更大。

Redis实验室的商业产品Redis Enterprise包括第三种复制策略,称为“主动-主动地理分布”,该策略基于无冲突复制数据类型(CRDT)。集合使用观察删除的集合,计数器使用新的可重置计数器实现,并按键映射合并更新。某些数据类型(如字符串和映射值)使用上次写入胜出进行解析,这可能会丢失更新。

Redis Sentinel、Redis Cluster和Active-Active Geo-Distribution都允许丢失更新-至少对于某些工作负载是这样。为了降低这种风险,Redis包括一个等待命令,它可以确保先前的写入是“持久的,即使一个节点着火并且永远不会回到集群”。此外,Redis Enterprise声称“完全符合ACID,支持多个、EXEC、WAIT、DIRED和WATCH命令”。

那么,Redis Enterprise会丢失更新吗?或者是“全酸”?Redis-RAFT文档对ACID的说法提出了质疑,1指出WAIT“并不能使系统整体上具有很强的一致性”。在与杰普森的讨论中,Redis实验室澄清说,Redis Enterprise可以提供ACID特性,但只能提供1。)。在没有任何形式的复制的情况下,2)。预写日志必须在每次写入时设置为fsync,并设置为3。)。事务失败时无法回滚。这些因素没有明确的记录,但Redis实验室计划在未来记录这些因素。

简而言之,希望容错且不丢失更新的用户需要比现有Redis复制系统更强大的功能。于是:红色救生筏。

第四种Redis复制机制是Redis-RAFT,它使用RAFT一致性算法跨一组节点复制Redis的状态机。

Redis-RAFT声称将使Redis“有效地成为CP系统”。将所有作业放入筏板测井应允许作业线性化。由于不同密钥上的操作通过相同的RAFT状态机,并且由于多个事务被实现为单个RAFT操作,因此Redis-RAFT还应该提供严格的可串行化-无论是对于单个操作还是对于事务。

Redis-Raft于2018年2月作为概念验证开始,Redis Labs自2019年年中以来一直致力于发布生产版本。在我们的合作期间,Redis-RAFT不向公众开放,但Redis Labs计划在Redisconf 20上提供源代码,并计划将其作为Redis7.0的一部分进行全面发布。

我们使用Jepsen测试库为Redis-RAFT设计了一个测试套件。因为redis-raft依赖于Redis不稳定分支中的特性,所以我们在Redis f88f866和6.0.3上运行了我们的测试,并从1b3fbf6到e0123a9运行了Redis-raft的开发构建。所有测试都在LXC和EC2上的5节点Debian9集群上运行。我们在测试过程中引入了许多错误,包括进程暂停、崩溃、网络分区、时钟偏差和成员资格更改。

以前的Jepsen测试依赖于各种各样的工作负载,每个工作负载都旨在检测不同的异常,或者补偿其他工作负载中的性能限制。在过去的一年里,杰普森与加州大学圣克鲁斯分校的Peter Alvaro合作设计了一种新型的一致性检查器,它在广泛的事务和单键操作中以线性(而不是指数)的时间运行,可以验证广泛的安全属性,直至严格的序列化,并为违反的安全属性提供易于理解的本地化反例。我们叫这个跳棋手Elle。

我们在这个分析中专门使用了Elle,测量了Redis在列表交易方面的安全性。每个事务(或单个操作)由一组不断演变的小键集上的读取和附加操作组成。读取使用LRANGE返回列表的当前状态,并使用RPUSH将不同的元素添加到列表的末尾。ELL推断这些事务之间的依赖关系,包括写-写、写-读和读-写数据依赖关系以及实时顺序,并在依赖关系图中查找循环作为严格可串行化违规的证据。

我们在Redis-raft中发现了21个问题,从暂时不可用到可能使编写正确的客户端程序变得困难、完全丢失数据的行为。

RAFT是一种基于领导者的协议:请求不能由追随者执行,而必须发送给领导者。Redis客户可以遵循重定向将其操作直接提交给领导者(希望是当前的),或者,使用Follower-Proxy=yes选项,Redis的追随者可以代表客户将请求代理给领导者。

在启用此代理模式的情况下,我们发现对redis-raft 1b3fbf6执行任何写操作都会将集群发送到无限循环:该操作将反复应用于日志,使RAFT日志膨胀,并(取决于写入)Redis的内存和磁盘状态。

此问题(#13)是由丢失的再入检查引起的。Redis-RAFT的工作方式是截取客户端命令(例如,设置密钥Val)并将其重写为特殊的RAFT命令(RAFT设置密钥Val)。然后,通过RAFT日志复制该RAFT命令,一旦提交,就解开包装(生成SET KEY VAL),并将其应用于本地状态机。然而,拦截代码随后会将该命令识别为需要发送到RAFT日志的命令,再次将其包装在RAFT命令中,然后通过协商一致系统将其发回。在d589127版本中,向拦截逻辑添加可重入性检查解决了该问题。

当我们在没有跟随者代理的情况下评估Redis-raft 1b3fbf6时,我们发现任何故障转移都会导致所有提交的数据丢失。新当选的领导人将带着一个全新的国家上线。此问题在CLI和附加测试中几乎可以重现。

此问题(#14)是由与#13相同的缺少重入性检查引起的。当领导者处理操作时,它会将其应用到其本地状态机。然而,追随者会拦截该操作,将其转换为筏子操作,然后(代理模式被禁用)拒绝该操作,因为他们不是领导者。

RAFT论文包括执行在线成员更改的算法。当节点被添加到集群或从集群中移除时,RAFT进入特殊的联合协商模式,在该模式中,大多数原始成员和大多数新成员在提交之前必须就每个操作达成一致。一旦原始群集的大多数已确认新成员身份,群集将恢复正常操作,只需要大多数新成员确认即可。

Redis-RAFT d589127没有正确实现该系统。领导者可以独立执行成员更改,而无需得到任何其他节点的确认。领导者可以通过网络分区、进程暂停或崩溃来隔离,成功删除集群中的所有其他节点,声明自己是所产生的单节点集群的唯一领导者,并继续自己执行任意操作。给定n个节点和一个足够病态的操作符,Redis-RAFT可以分成n个独立的簇,每个簇都偏离原始簇历史的某个公共前缀。

此问题(#17)是由底层RAFT库中的错误引起的:RAFT_LOGTYPE_REMOVE_NODE被排除在被视为投票配置更改的日志条目类型集之外。版本8da0c77解决了问题。

在版本d589127中,我们发现终止和重新启动节点会导致在节点启动后出现一段很短的时间窗口,在此窗口中,节点可以返回读取的空状态,而不是提交状态。此错误是暂时的:几秒钟后,读取将再次观察到预期值。

例如,客户端可能执行将89附加到键0的事务,并读取结果列表:

然后,在进程启动之后,在新启动的节点上读取键0将不会返回任何元素:

Redis团队追踪到这个问题(#18)是底层RAFT库中的一个bug造成的。每当选举新的领导人时,该领导人都应该向其追随者发布无操作日志条目,以确定当前的状态是什么。随Redis-RAFT打包的RAFT库中缺少此行为。拉出较新的版本有助于解决该问题,Redis-raft dfd91d4不再表现出此行为。

版本d589127和8da0c77在正常运行时也显示读数过期,没有任何故障。例如,考虑这对事务,其中T1在T2开始之前3.25秒完成:

如果Redis-RAFT是可线性化的,那么T1附加到键1的11在T2的读取中应该是可见的-但是相反,T2只观察到[589]。这是一本过时的读物:一种对过去的看法。

与18号一样,这个问题(19号)的关键在于领导人上台后没有发布禁止操作;dfd91d4中也解决了这个问题。

在版本8da0c77到73ad833中,我们发现运行状况良好的群集往往会出现无明显原因的部分停机-网络延迟为亚毫秒级,如果没有故障注入,某些节点会返回NOLEADER数百秒,然后恢复,就像什么都没有发生一样。有时,节点会开始新连接超时,而不是返回NOLEADER。

Redis实验室将此问题(#21)追溯到队头阻塞问题,当新节点成为领导者时,来自追随者的代理命令可能会延迟(可能无限期)RAFT消息,从而导致RAFT操作在选举后在某些节点上停滞。激进的默认超时加剧了这个问题,这会导致选举在其他健康的集群中频繁发生。

为了解决此问题,Redis实验室为代理命令添加了超时机制,并调整了默认超时以减少由于节点响应时间的正常变化而导致的虚假选举。这些补丁已在6fca76c上应用。从b9ee410开始,Redis-RAFT每隔几分钟就会偶尔出现一次NOLEADER打嗝,但它们在几秒钟内就会消失。

在版本dfd91d4中,我们观察到似乎已中止的读取涉及网络分区和进程崩溃。操作将失败,并显示NOLEADER错误代码,但其影响对以后的事务仍然可见。例如,从追加测试运行中获取这对事务:

在这里,T1因NOLEADER而失败,但是T2能够观察到T1的写入。Redis实验室的工程师证实,NOLEADER表明某个操作肯定失败,这意味着这对事务构成了中止的读取。

e657423版本中的协议级修复包解决了这个问题(#23);此后我们再也没有观察到它。

在Redis中,人们通过发送MULTI、一系列命令和最后一个要提交的EXEC或要放弃以中止的EXEC来开始事务。这使得Redis客户端可以直接提供某种类型的事务流控制上下文,例如使用异常处理程序:

这段代码很简单,有时也能正常工作。然而,在Redis-RAFT中,可以(并且经常这样做)调用丢弃!失败,例如用于NOLEADER、NOTLEADER等。这会使连接处于多状态,操作由Redis缓冲。后续调用将在先前的MULTI上下文中执行,这可能会导致混乱的结果:事务可能与意外的影响混合在一起,EXEC的返回值可能是用于完全不同操作的那些值,等等。正确使用MULTI需要仔细注意跟踪连接状态。

出现此问题(#25)是因为Redis-raft单独对每个命令执行集群状态检查,而不是在本地服务器上缓冲命令并在EXEC上提交整个批次。在版本f4bb49f中,通过将多状态机移动到本地节点,允许它在内存中缓冲操作并将它们提交到原子批处理中,解决了这个问题。

在dfd91d4版本中,我们发现网络分区和进程崩溃可能会导致Redis使用不同查询的答案回复查询。例如,客户端可以执行单个读取…。

这是对MULTI.EXEC事务的回复,该事务执行两次追加(分别生成长度为3和4的列表),然后执行列表读取(返回2,4,…)。。值得注意的是,此响应与客户端的请求无关,也与此客户端发出的任何其他请求无关-在此特定情况下,客户端使用新连接执行LRANGE请求。与#25类似,这可能会导致类型错误或静默数据损坏,具体取决于响应类型是否恰好与请求者预期的类型匹配。

此问题(#26)涉及Redis-raft的代理机制中的多个错误。在Redis命令处理程序中,对代理命令的回复意外地路由到Redis-RAFT上下文,而不是请求上下文。领导者需要立即应用预先捆绑的多笔交易,而不是重新捆绑。Redis实验室还在异步上下文清理中添加了更多防御性错误处理。

在版本f88f866中,我们发现了另一个分裂大脑的情况,这一次涉及成员更改和进程崩溃。两个节点可能会偏离共同的历史记录,甚至会将相同的操作应用于不同的本地状态。例如,考虑这些关键字81的读取:在节点N1上执行的事务T2和T4观察以171和172开始的列表,而在节点N5上执行的T1和T3改为以176开始。

请注意,178和208的附加项应用于分裂脑的两侧,位于不同的前缀之上!

Redis实验室将此问题(#28)追溯到集群成员系统。底层RAFT库假设节点将被降级,然后从集群中删除,而不是直接删除。还有一个问题是,节点在从群集中删除后只是退出,而将其数据文件留在原地。将已删除的节点重新加入群集可能会导致它违反安全不变量。Redis实验室通过强制删除的节点在终止前存档其本地状态来解决此问题。从bc9552f版本开始,Redis-RAFT不再随着成员的改变而表现出分裂的大脑。

在bc9552f版本中,我们发现了启动后的另一个空读情况,这是由成员资格更改和进程崩溃共同触发的。如果节点在成员身份更改后启动,它可能会临时返回空值,而不是提交的数据。例如…。

这里,节点在T2之前重新启动。此问题相对较少-需要几个小时的随机故障注入才能发现,需要五分钟以上才能重现目标故障。

Redis实验室将此问题(#30)追溯到启动时日志加载过程中的两个错误。首先,当一个节点的日志表明只存在一个(投票)节点时,日志加载代码中的一个特殊情况应该允许Redis-raft将其日志视为完全提交,但是该代码路径计算所有节点,而不是投票节点。其次,在日志加载过程中,Redis-RAFT错误地对待以前属于集群一部分的节点,就好像它们仍然是活动的一样,并且可以与它们交换消息。节点甚至可以向自己发送消息。这两个问题都在73ad833中得到了解决。

使用redis-raft b9ee410,我们观察到节点在正常操作下偶尔会崩溃,原因是callRaftPeriodic中的断言失败。此问题(#42)似乎链接到pollSnapshotStatus的意外返回值。瑞迪斯实验室正在调查。

在b9ee410中,我们发现,随着进程崩溃、暂停、分区和成员资格的更改,节点经常处于不可恢复的磁盘状态,其中它们的快照文件是在日志中的第一个条目之前从日志索引中获取的。任何启动节点的尝试都会死机,记录类似Log Initial Index(1478)的内容与快照最后一个索引(1402)不匹配,将中止。多个节点遇到问题。

我们没有时间缩小这个bug(#43)发生的条件,也无法确定原因。但是,此问题不再出现在e0123a9中。

版本b9ee410展示了另一个分裂大脑的情况,我们在进程崩溃、暂停、分区和成员更改的测试中反复观察到这种情况。与前面的分裂大脑问题一样,集群中的一些节点可能会偏离历史的共享前缀,从而允许读取和更新独立进行。更新可能会丢失,这取决于历史记录的哪些分支幸存下来。

此行为(#44)似乎源于节点STA上的快照加载过程中的错误。

..