基于平衡区组的数据编码分布式一致性算法设计.pdf

第 卷 第 期 年 月天 津理工大学学报 .收稿日期:修订日期:基金项目:国家自然科学基金():/基于平衡区组的数据编码分布式一致性算法设计汪玲徐光平(天津理工大学 计算机科学与工程学院 天津)摘要:为降低分布式环境下的存储和网络开销问题 采用纠删码比采用副本策略更高效 虽然将纠删码与 相结合 但面临多节点故障时性能突降的问题 提出一种将纠删码结合平衡区组的分布式一致性算法 当系统检测到 个故障节点时 领导者分发数据包会增加 个编码包 测试时 在 基础上实现了 和分布式一致性算法通过逐渐增加系统中的故障节点 验证了该方法的有效性 在出现故障时 该算法相比 的延迟和吞吐量效率更优关键词:分布式计算机 一致性算法 协议 纠删码中图分类号:文献标识码:文章编号:()():./.:分布式系统是一组独立的计算机间通过网络连接形成的一个整体对外提供服务的系统 从用户角度 无需考虑为其服务的究竟是哪些服务器 为保证分布式系统的可靠性 需在系统多个节点上保存数据的多个副本 这样 即使若干服务器出现故障 其他服务器也可读取到已写入系统的数据 随着大数据和云计算的到来 分布式环境下的存储问题已受到越来越多的关注由布鲁尔理论()可知 对于一个分布式系统来说在无法保证出现分区故障时 能对所有客户端均可用 且能保证数据的强一致性(线性一致性)然而 对于一个现实的系统来说 网络出现分区故障是难以避免的 所以 系统需在可用性和强一致性中做出权衡 传统的分布式算法如两阶段提交协议、阶段提交协议等 均具有原理简单、实现方便、可达到数据强一致性的特点 但也存在明显的容错性差及单点故障等问题 为此 提出一种基于消息传递模型且具有高度容错性的一致性协议 为解决各种情况下的分布式问题 如网络延迟和带宽的不同、工作负载的不同及数据中心地理位置的不同 年 月汪玲 等:基于平衡区组的数据编码分布式一致性算法设计等 基于 协议衍生出了诸多算法 如 及 等 文献 针对 算法晦涩难懂、难以实现等缺点 提出一种便于工程实现的一致性算法 虽然 协议便于理解且较容易实现 但对于 来说 并没有提高运行效率 所以 针对 协 议 进 行 改 进 并 提 升 效 率 变 得 尤 为 重 要是将 与里德 所罗门()纠删码结合的一致性算法 在系统可和足够数量的健康节点交流时 发送编码后的大小为/的编码包 否则发送大小为 的副本数据 但是这样的设计需运行在稳定的集群中 否则当系统出现少量故障时 切换机制会由纠删码导致的节约存储和网络开销优势丢失为此 针对系统检测到少量节点故障时 故障切换带来的性能突降问题 文中提出一种利用纠删码与平衡区组设计的基于编码包排布放置的一致性算法 可在不稳定的系统中有效采用纠删码带来性能优化 提高出现特定数量故障节点情况下的存储效率和传输性能 增加整个系统的稳定性 背景知识 是管理复制日志的一致性算法 它是基于复制状态机实现的 将分布式系统中的每个节点抽象为一个复制状态机 只要保证这些节点的初始状态相同 且所有节点按照相同的顺序执行相同的操作即可保证所有节点能达成一致的状态 节点状态转换图如图 所示 集群中的节点状态可划分为 种:领导者、跟随者和候选者通常情况下 系统中只有一个领导者 剩余节点都为跟随者 领导者接收客户端的请求 并将每条请求转化为 条日志 以附加方式添加到日志中 然后向跟随者发送这些请求 跟随者接收到领导者的消息后发送回复 中的日志仅从领导者单向复制给跟随者 而跟随者只接受来自领导者的日志且不对日志做任何修改 在集群中 旧的领导者崩溃或断开连接时 跟随者会转化为候选者 赢得系统中大多数节点投票的跟随者会被选为新的领导者图 节点状态转换图 假设系统总节点数为 则 可容忍 个节点的故障 其中 因为候选者须获得半数以上的投票才能成为领导者 集群中最多只能竞选出 位领导者 保证了集群的安全性 纠删码纠删码()是一种编码容错技术 相对于副本策略 在保证一定容错能力的同时 具有更高的存储利用率 纠删码技术主要是通过纠删码算法将 块原始数据通过一定的编码方式得到 块冗余数据 然后将原始数据和冗余数据(块)全部保存 这样 即使丢失任意 块数据片段也可恢复原始数据 以此到达容错的目的 通过原始数据得到冗余数据的过程称为编码 将数据片段拼接为原始数据的过程称为解码 空间利用率为/()常用的编码为 编码 文中简记为 ()是将纠删码结合到 算法中的一种改进算法 在 中 通过将编码后的数据采用 发送到其他节点中时 会出现无法容忍 个节点故障的问题 为保证系统的高可用性 通过结合全副本复制和编码复制两种方式来运行 中采用 ()编码 所以 每个编码后的数据包与节点一一对应 即每个节点只保存同一条日志的一个编码包 正常情况下 为降低网络开销和磁盘存储 领导者会将编码后的日志发送给跟随者 当健康节点个数小于 个时 将会采用全副本复制 此时等同于 平衡区组设计设 .是 .上的一个区组设计 其中 区组 包含 个处理(称为区组 的大小)任意处理 在区组 中出现的次数为()()为处理 在区组 的重复数 任意一对处理()在区组 的相遇天津理工大学学报第 卷 第 期数定义为()()()将重复数恒为常数 且经不同处理的相遇数也恒为常数的区组设计 称为平衡区组设计()基于 方法的纠删编码包放置的一致性算法 引入纠删码后 只有在系统状态最好时才能将纠删码降低存储和网络开销的性能发挥出来而 切换为全复制的原因就是为保证系统出现故障时整个集群的故障容忍度仍为 个 所以 在如何最大限度地利用纠删码的同时 保持系统的高可用性是文中的主要研究内容设系统共有 个服务器 为保证能达到和 及 相同的可用性 该系统可容忍的最大故障节点数为 采用 ()编码 和 满足 采用编码包分发时 将 个包发送给 个节点 它们以一一对应的方式保存和恢复数据 因为每个节点最多只能收到同一条日志的一个编码包 所以 当节点出现故障 领导者收到的回复消息不足时 无法满足提交日志的至少有 个节点的要求 于是 切换为全副本复制为保证高可用性 在不同的节点上保存多个数据包 提高每个节点的数据存储量 以应对部分节点故障的情况 数据包的个数由系统状态决定 该算法是基于 方法的纠删编码包放置的一致性算法 记为 当系统中没有故障节点时 领导者给每个节点发送一个包 而在出现 个故障节点时 每个节点保存 个数据包 通过以下定理证明文中方法可容忍 个节点故障 且出现 个故障时 需在每个节点保存 个包定理:当系统中只有 个节点时 提交 条日志 则需在 个节点中均保存日志 的 个编码包(等同于完整日志的数据包的个数)证明:假设当前系统共有 个节点 其中时刻有 个节点 能够正常运行 若 时刻 中出现 个节点故障 另外 个节点 恢复可用(至少保证系统中有 个节点正常运行)为保证在 时刻写入的日志 不会丢失 在原先的节点 中必须保证每个节点都保存了足够恢复出完整日志 的数据包数量 根据()编码可知 每个节点需保存 份数据包 日志复制当一个节点收到来自客户端的请求时 且此时该节点是 集群的领导者 它会为该请求分配一个日志序列号()并结合领导者目前的任期号附加到自己的日志中 领导者收到跟随者的心跳时 会给他们发送附加日志远程过程调用()来同步日志编码包分发流程如图 所示图 编码包分发流程 领导者将该日志的内容部分采用 ()编码为 份 将该日志的序列号及任期号作为唯一标识结合编码后的数据包分发给不同的节点 对于拥有相同的任期号及序列号的日志 可认为他们相当于 中的同一条日志 符合 的日志匹配特性 日志编码后领导者即可给跟随者发送消息 日志内的编码包数量由领导者上一轮收到的心跳决定 假设系统中共有 个服务器 系统的故障容忍个数为 采用 ()编码其中 和 满足 为应对不同故障下的各种情景 文中设计了基于平衡区组的分层存储方式 根据节点个数不同 设计不同的策略来保存不同的编码包个数 的分布策略 节点的设计方案为 则区组个 年 月汪玲 等:基于平衡区组的数据编码分布式一致性算法设计数 处理的次数(即单因子的水平数)区组大小向量()()由平衡区组设计定义可知单因子每个水平的重复度和任意两个水平的相遇度 水平 的重复度()()水平 和水平 的相遇度()()()则单因子的相遇度矩阵 该矩阵为对称矩阵 由于该设计的重复度和不同处理的相遇度均恒为常数 所以 该设计为平衡区组设计允许两个节点故障 时 采用 ()编码 在系统没有故障节点时 每个服务器保存 个编码包 当有 个节点出现故障时 每个节点保存两个编码包 当有两个节点出现故障 即出现 节点时可容忍的最大故障数 时 每个节点保存 个编码包因为系统采用 ()编码 所以 个编码包相当于 个完整的副本大小当集群中 个节点均正常运行时 每个节点均保存个编码包 即使此时有两个节点宕机 由 ()可知 在剩余的任意 个节点中均可获取 种不同的编码包 因此 能恢复出完整的数据 当只有 个节点正常运行时 在每个节点保存两个编码包 即使这 个节点中出现任意一个故障 系统仍能满足日志可恢复的要求 由于 节点是最小可正常运行节点数由定理可知 所有节点应保存相当与完整副本数据大小的数据量 此时 每个节点保存 个数据包 为 的分布策略 节点的设计方案为则区组个数为 处理的次数(即单因子的水平数)区组大小向量 ()()由平衡区组设计定义可知单因子每个水平的重复度和任意两个水平的相遇度 水平 的重复度()()水平 和水平 的相遇度为()()()则单因子的相遇度矩阵 该矩阵为对称矩阵 由于该设计的重复度和不同处理的相遇度均恒为常数 所以 该设计为平衡区组设计采用 ()编码 没有节点故障时 每个服务器保存一个编码包 当有 个节点出现故障时每个服务器存两个编码包 当有两个节点故障时 各保存 个编码包 在只有 个节点运行时 每个节点保存 个编码包(等同于完整的数据)不同的序号代表每次增加编码包时其位置排布 如需保存 个编码包 则给不同节点发送 位置的数据包 如需两个编码包 则给不同节点发送 位置的两个编码包如需 个编码包时 则发送 位置的数据 同样 最坏的情况下由定理可知 需给每个节点发送 位置的 个编码包 提交条件将编码后的日志发送给其他节点后 领导者需等待跟随者的回复 由上述分布策略可知 当系统有 个节点时 每个节点保存 个编码包 当有 个节点时 每个节点仅保存 个编码包 当运行节点个数减少 个时 领导者需给每个节点发送的编码包数量加 所以 当领导者判定集群有 个节点正常运行时 领导者需保证对于每一条日志每个节点至少都要保存 个编码包 这样 任意 个节点均可恢复出完整的日志 所以 当领导者至少收到 个节点回复收到 个编码包 即可认为该条日志可安全地被提交 不同算法的性能对比如表 所示 在集群中 所天津理工大学学报第 卷 第 期有已提交的日志均不会丢失 即使领导者中可能只有部分数据 预领导者阶段时 这些数据也会被恢复表 不同算法的性能对比 性能对比(无故障)(超过 个故障)存储消耗/()()()/网络带宽/()()/活性 领导者选举在 中 初始状态下 所有的节点都是跟随者 如果它收到来自领导者的心跳或者候选者的消息就会继续保持跟随者身份 领导者会定时给集群中所有节点发送心跳 以维护自己的领导者身份 当 个节点超过一定的时间没有收到来自领导者的心跳 会立即触发选举超时 将自己的身份转变为候选者 并给自己投一票 然后给集群中所有节点发送请求投票 当候选者收到 个投票(包含自身)时 该节点选举成功 转换为领导者的同时 给其他节点发送心跳图 为 节点状态转换图 与 不同的是 当一个新的领导者选举成功后 只保存了日志的部分编码包 所以 需收集这些日志的所有编码包恢复完整的日志 即可给落后的节点继续发送日志该阶段称为预领导者阶段 表 为预领导者 的参数 领导者向所有跟随者发送请求 包含当前的 任期号、最后 条日志的索引及需恢复的第 条日志的索引 跟随者接收到该请求后 判断自己的任期号是否大于领导者的任期号 如任期号大于领导者的任期号 则返回错误 无需再继续处理 再判断领导者的日志长度是否大于自己的 条日志 如不满足 则返回错误 如前两者均满足 跟随者会在自己的日志中将从领导者需要的日志索引开始将所有日志数据返回 领导者接收到 个回复后 即可恢复出完整的日志数据 整个领导者选举过程全部结束 领导者可给跟随者发送日志复制 图 节点状态转换图 表 预领导者 的参数 参数返回值判定条件领导者的任期号领导者需要解码的第 个索引领导者的最大日志的索引跟随者的任期号 跟随者返回的日志当 时返回 当 跟随者的第 个日志时 返回 新选举出来的领导者中可能会有尚未提交的日志 这些日志中的编码包数量可能为 个或更多 新领导者会向所有节点请求数据 然后等待 个节点的回复 所以 这部分日志不能总被恢复出来 对于索引值大于已提交日志索引的这些日志 若从某 条日志开始 领导者无法收集到 个编码包 当领导者收到 个节点的预领导者回复后 领导者即可从已应用的索引位置开始逐条恢复数据 直至无法恢复的日志结束 待这些工作完成后 预领导者阶段结束 在预领导者阶段 新领导者会持续发送心跳 以此维护自己的领导者身份 预领导者阶段结束后 系统正常接收客户端的请求 在日志复制过程中 对于每 条日志 领导者均可保证 个节点中至少保存 个编码包 所以 在日志收集过程中 新领导者即可在 个(包含自己)节点中收集到已提交日志的至少 个编码包 恢复出完整日志 保证了数据的一致性 试验验证 通过采用 语言和 框架 在 模型基础上改进实现 及 纠删码采用的是里德所罗门编码 通过采用 作为各节点间的通信方式 包含实现日志复制的复制日志、实现领导者投票的请求投票 及实现预领导者阶段的请求日志 年 月汪玲 等:基于平衡区组的数据编码分布式一致性算法设计在试验中 将心跳间隔设置为 选举超时为 个心跳的时长 分别设计了 为 和 时的两种节点数量 客户端发送的数据值大小设置为 读取操作和写入操作均需写入日志 试验只测试了写入操作比例为 的情景 为保证试验公平始终保持 和 环境参数设置相同 仅通过比较故障节点数目不同对试验的影响 这些日志是不可恢复的 将这条日志及其之后的日志安全删除当节点为 时 出现 个故障节点的试验结果如图 所示图 当节点为 时出现 个故障节点的试验结果 随着数据值的增大 客户端提交每条日志的延迟也逐渐增大 吞吐量则逐渐增加直至瓶颈 当系统中有 个节点 其中 个节点出现故障时 无法发送编码包 切换为全副本复制 而 仅给每个节点发送两份数据包 所以 此时 的延迟和吞吐量明显优于 但无故障和出现两个故障时 两种方法发送的数据包大小相同 分别为 个包和 个包 因此 延迟和吞吐量没有差异 当 时 的吞吐量也会随着故障节点的增大而减小 发生不同数量的节点故障时 的吞吐量如图 所示 当 时 发生不同数量的节点故障时 的吞吐量如图 所示 的吞吐量会随着故障节点的增多而降低图 发生不同数量的节点故障时 的吞吐量 节点数量为 时的写入延迟分别出现 个故障和两个故障 两种情况下 的延迟都低于 如图 所示图 节点数量为 时的写入延迟 天津理工大学学报第 卷 第 期 结论 随着 在越来越多的系统中得到应用 降低 的存储和网络开销是很有必要的 所以 如何有效的降低存储且不对系统的可用性造成影响是文中主要解决的内容 中利用纠删码分发数据时 不适用于节点不稳定的环境中 提出将纠删码结合平衡区组设计的方法 通过实时判断系统中可用节点的个数来发送不同数量的数据包 既保证了系统的存储效率 也保证了它的高可用性 试验结果表明:节点系统中出现 个故障及 节点系统中出现 个故障的情况下 的延迟相较于 分别提升了 和 参 考 文 献.:.():.():.():.:.():.:/:.():.:/:.:/:./:./:.:/:.朱永振 徐光平.一类基于极图理论的局部修复编码的性质及构造.天津理工大学学报 ():./:.:.():.黄文依 王劲松 林胜.可视化操作研究与实现.天津理工大学学报 ():./:.:.作者简介:汪玲()女 硕士研究生 研究方向:分布式算法等:徐光平(通信作者)()男 教授 博士 研究方向:分布式存储等: