一种基于可擦除编码和链式备份的分布式存储系统

摘要

本发明公开了一种基于可擦除编码和链式备份的分布式存储系统，包括：由多台代理服务器组成的代理服务器集群以及由多个物理存储节点组成的对象存储集群。该装置通过结合传统的应用于分布式存储系统中的链式备份方法与可擦除编码的存储方法，在读写性能和存储空间效率之间取得了良好的平衡；相比起传统的多副本备份方法，本发明装置在大大降低了存储开销的同时，维持了同样高效的读写响应性能；相比起纯可擦除编码的存储方案，本发明装置极大地提高了数据对象的读写效率，增强了分布式存储系统的可用性。

说明书

技术领域

本发明属于计算机信息管理技术领域，具体涉及一种基于可擦除编码和链 式备份的分布式存储系统。

背景技术

随着云计算和移动互联网的进一步普及和深入应用，各类网上应用和服务 正在各行各业中扮演着更为重要的角色，而随着互联网应用的用户基数急剧上 升，全球的信息总量也正在以爆炸性的速度在增长。云存储技术是云计算技术 的基石，底层的数据管理，数据存储，以及数据处理系统的稳定性与高效性， 都直接影响到上层应用的运作。传统意义上的数据库与文件系统已经无法满足 海量的跨界的数据存储需求，尤其在一些重要的应用行业领域，如医疗，金融， 政务等系统中，系统用户对于系统数据的可用性，系统响应的高效性，以及数 据的可靠性有着极高的要求。由于在大数据时代，各行各行业每天新增的数据 量都在以指数级的速度在增长，对于服务提供商来说，如何减少存储数据的空 间成本，同时又能保证良好的系统吞吐量，这是所有服务提供商所要面临解决 的重要挑战。

在最常见的分布式对象存储系统当中，用户的所有数据都被系统理解为一 个个对象，然后会把这些对象在系统中完全等同地存放N(N≥3)份，这N个 副本被系统组织成一条链，这条链上的所有节点都遵循系统制定的关于处理读 写请求与维持数据一致性的协议，这种最常用的数据对象管理方法称为链式备 份。链式备份带来的最大的好处就是良好的系统吞吐量，因为对于每个来自客 户端的读写请求，系统只需要指派这条链上的其中一个节点去进行处理和响应， 在均衡了系统的负载的同时，还减少了节点之间的通讯网络开销，因此可以达 到低延迟的响应效果。但正如上述，在数据量激增的大数据时代，链式备份方 法显示出了它最大的缺点：极高的存储空间开销。以比较常见的四副本方案为 例，若用户向存储系统写入一份体积大小为V的数据，那么系统中最终会存在 一条长度为4的关于这个对象的链，总体积为4V，换句话说，四副本的链式备 份会产生300％的额外存储空间开销。如此高的额外空间开销在经济上对于服 务提供商来说，将是难以承受的。

为了解决分布式存储系统中，链式备份方案所带来的高额空间开销的问题， 业界更多地关注一种从RAID(独立冗余磁盘阵列)改良过来的技术：可擦除编 码技术。可擦除编码技术可以用两个参数表示：k和m，其基本原理和操作方法 可以描述为：用户上传一份对象后，系统会对这份对象进行(k，m)形式的编 码，最终会得到k个数据子块，以及m个校验子块，这k+m个子块都会被分配 并存储在不同的物理服务器上。可擦除编码的一个性质就是，一个(k，m)的 方案，最多可以忍受m个子块的丢失，即只要少于或等于m个子块是无效的， 那么这个完整的对象都可以通过解码程序，利用剩下的有效的子块恢复出来， 假设对象的体积大小是V，那么每一个子块的体积大小都是V/k。因此，一个(6,3) 的可擦除编码方案所提供的容灾性与四副本链式备份所提供的容灾性是一样 的：都可以使系统忍受最多三个不同的节点的失效，而依然可以对用户提供某 个对象的访问，在这个前提下，(6,3)的可擦除编码只需要额外50％的存储空间 开销，仅仅为四副本链式备份的六分之一。可擦除编码因为其突出的空间效率 而受到越来越多的关注，但它也存在严重的缺点：每次读和写一个对象，都必 须启动编码和解码程序，CPU的计算开销与节点之间的传输网络开销，将会大 大降低系统响应客户请求的效率，成为系统吞吐量的瓶颈。因此，可擦除编码 虽然可以降低链式备份所带来的高昂的空间开销，但却无法满足较高的良好的 系统响应效率。

综上可见，在大数据的时代背景下，用户希望得到低时延，流畅的互联网 服务体验，而服务提供商希望分布式存储系统能够以高吞吐的状态支撑上层应 用，同时降低存储日益剧增的数据量所带来的巨大的空间开销。如何改进现有 的分布式存储系统中的数据管理方法，在保证数据的可靠性，系统的高可用性 的同时，又能从一定程度上减少存储数据所带来的空间额外开销，保持分布式 对象存储系统的良好的访问响应效率，成为本领域技术人员迫切需要解决的一 个重要问题。

发明内容

针对现有技术所存在的上述技术问题，本发明提供了一种基于可擦除编码 和链式备份的分布式存储系统，能够使分布式对象存储系统以较低的存储空间 开销，维持较高的系统可用性与响应性能。

一种基于可擦除编码和链式备份的分布式存储系统，包括：由多台代理服 务器组成的代理服务器集群以及由多个物理存储节点组成的对象存储集群；

所述的代理服务器根据客户端发送的请求报文中所包含的对象ID，计算出 对象ID所对应的哈希值并将该请求导向到对象存储集群中对应的物理存储节点 上，同时维护对象存储集群中各物理存储节点的相关元数据信息，进而根据环 形一致性哈希算法，按照一定的层次结构来组织所有物理存储节点；

所述的物理存储节点用于存储数据且具有唯一的设备标识号，每一份数据 即为一个对象，每个对象同时以两种形式存储于对象存储集群中：第一种形式 是以完整的备份模式存储在某一台物理存储节点上，该物理存储节点对应为对 象的主节点；第二种形式是以可擦除编码的方式对对象进行编码，编码后生成k 个数据块和m个校验块，这k+m个块分别存储于k+m个物理存储节点上，每 个块的大小均为对象大小的1/k；存放数据块的物理存储节点为数据节点，存放 校验块的物理存储节点为校验节点；k和m均为大于0的自然数。

对于任一对象，负责存储该对象的主节点、k个数据节点以及m个校验节 点的设备标识号是连续的且这1+k+m个节点组成了一条链，其中k个数据节点 和m个校验节点组合成这条链的编码子链。

优选地，经代理服务器集群初始化安排过后的对象存储集群被分成若干个 容灾域，不同容灾域之间是存在地理隔离的或是存在电源总线隔离的，对应存 储k个数据块和m个校验块的k+m个物理存储节点处于不同的容灾域上。若某 个容灾域受到某一外界因素而导致数据丢失或暂时不能工作，这个容灾域上所 发生的错误不会牵连到任何另外的容灾域中的物理存储节点。

所述的客户端发送的请求分为三种：下载请求、上传请求和以及更新请求。

对于上传请求，代理服务器收到请求后将该请求导向到对应的主节点，主 节点直接与客户端进行通讯，在对象完全写入主节点后，主节点启动编码流程 并生成k个数据块和m个校验块，然后并行地将这些块写入到主节点对应编码 子链中的物理存储节点中；编码子链中所有的物理存储节点均返回给主节点写 入成功的响应后，主节点向客户端返回对象上传操作处理完毕的消息。

对于更新请求，客户端将更新内容及其相对于被更新对象的偏移量记录在 该请求报文中发送给代理服务器，代理服务器收到请求后会根据偏移量和被更 新对象的大小计算出目标导向的数据节点的设备标识号；目标导向的数据节点 从客户端接收更新内容以进行更新得到新的数据块，并利用新的数据块和旧的 数据块计算出一个差异矩阵，然后该数据节点并行地完成以下两个操作：第一， 立即将新的数据块替换旧的数据块；第二，将差异矩阵传送到被更新对象对应 编码子链中每个校验节点上；校验节点收到差异矩阵后，将该差异矩阵存放到 节点内从属于被更新对象的更新缓冲区里，并以客户端ID和请求报文的操作时 间戳联合作为该次更新操作的版本号。

所述的代理服务器根据以下公式计算目标导向的数据节点的设备标识号：

DN_ID＝被更新对象ID的哈希值+1+偏移量|(对象大小/k)

其中：DN_ID为目标导向的数据节点的设备标识号，|表示整除。

每个对象在校验节点内的更新缓冲区的长度均是固定的；若当前更新操作 时，更新缓冲区已满，则将最旧的差异矩阵从更新缓冲区中删除以腾出空间存 放新的差异矩阵。

对于下载请求，代理服务器收到请求后将该请求导向到对应的主节点，若 主节点能够正常处理该请求，则由主节点从本地磁盘上顺序读出被请求对象， 并返回给客户端；若主节点无法正常处理该请求，则代理服务器将该请求导向 到对应编码子链上的第一个物理存储节点上，该物理存储节点并发地向编码子 链中其余物理存储节点转发该请求，并等待其他物理存储节点的回应；若收到 其他所有数据节点的回应，该物理存储节点则忽略来自校验节点的回应信息并 接收来自其他数据节点的数据块传输，数据块传输完毕并按顺序组装完成后， 由该物理存储节点向客户端返回被请求对象；若未收全其他所有数据节点的回 应，该物理存储节点则启动解码程序来恢复被请求对象，即从收到回应消息的 物理存储节点中任意选择k个，并根据这k个物理存储节点上所保存的数据块 或校验块并行地进行解码，将恢复后的被请求对象返回给客户端，同时将遗失 的数据块重新写入对应的数据节点中。

对于更新请求，编码子链采用惰性重构的策略来主节点上的备份对象进行 重构及覆盖，若编码子链中的对象每次被更新后且对应在主节点上的备份对象 未进行重构，则将校验节点上操作时间戳最大的差异矩阵标识为脏的并从编码 子链中自定义一数据节点周期性地查询主节点的繁忙状态，若主节点响应并接 受对象重构，则该数据节点会发起解码重构程序，将最新版本的数据块从编码 子链中各数据节点上传至主节点上；当主节点重构并覆盖旧版本的对象完毕后， 主节点向编码子链中各数据节点发出确认信息，编码子链中各校验节点则把对 应的差异矩阵标识为干净的。

对于下载请求，若被请求对象存在多个差异矩阵，则编码子链和主节点会 按照以下策略选取相应版本的对象返回给客户端：

若操作时间戳最大的差异矩阵是干净的，若主节点能够正常处理该请求则 由主节点返回被请求对象给客户端，若主节点无法正常处理该请求则由编码子 链通过解码恢复返回被请求对象给客户端；

若操作时间戳最大的差异矩阵是脏的，同时该差异矩阵对应更新操作的客 户端ID与发送当前下载请求的客户端ID是相同的，则由编码子链通过解码恢 复返回被请求对象给客户端；

若操作时间戳最大的差异矩阵是脏的，但该差异矩阵对应更新操作的客户 端ID与发送当前下载请求的客户端ID不相同，则根据上述操作按操作时间戳 递减的顺序判断下一个差异矩阵；

若判断到最后一个差异矩阵仍是脏的且该差异矩阵对应更新操作的客户端 ID与发送当前下载请求的客户端ID不相同，则根据编码子链中校验节点更新缓 冲区中除最小操作时间戳以外的其他所有差异矩阵所对应的更新操作进行还 原，将还原得到的所有数据块上传至主节点使其对备份对象进行重构，进而将 主节点重构得到的对象返回给客户端。

由于采取了上述的技术方案，本发现与现有技术相比，具有如下显著的有 益效果：

(1)本发明分布式存储装置相比起传统的多副本备份的存储方案，在维持 同样水平的读写效率和系统吞吐量，以及相同的容灾性等级的前提条件下，极 大地减少了存储空间的额外开销；本发明装置在采用(1,6,3)参数组的情况下， 相比具有相同容灾能力的四副本冗余备份方案，节省了250％的额外存储空间 开销。

(2)本发明分布式存储装置通过引入可擦除编码子链结构，可以高效地支 持随机写操作，而传统的多副本冗余备份在应对随机写请求时，只能通过完全 覆盖N个副本的方法来完成对请求的响应，本发明分布式存储装置在处理随机 写请求时节省了大量的节点之间的网络传输开销，以及大量的磁盘写入操作。

(3)本发明分布式存储装置相比起纯可擦除编码存储方案，在略微增加存 储空间额外开销的同时，极大地提升了处理客户端各类响应请求的性能，尤其 在读请求方面，而读请求在现代互联网服务和应用的各种场景当中都占了极高 的比例，因此本发明装置应用在各类现实场景当中时，可以获得比纯可擦除编 码的方案获得更出色的性能和表现。

附图说明

图1为本发明基于可擦除编码与链式备份的分布式存储装置的结构示意图。

图2为本发明基于多版本的链式备份机制处理来自客户端写请求的流程示 意图。

图3为本发明基于多版本的链式备份机制处理来自客户端读请求的流程示 意图。

具体实施方式

为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技 术方案进行详细说明。

如图1所示，在实际运行应用环境当中，本发明分布式对象存储系统主要 包括以下三个部分，客户端代表了运行在用户的PC机上或移动终端设备上的线 程，可以是web浏览器，或app客户端；代理服务集群(Proxy Server Cluster， PSC)负责处理与客户端之间的通讯，包括接受客户端发送过来的对象的读写请 求，还负责与对象存储集群(Object Storage Cluster，OSC)之间的通讯，主要 是将客户端发送过来的请求经过内部的算法处理后，发送到OSC中的某几个特 定的物理存储节点(Storage Node，SN)上；对象存储集群OSC包含了多个， 一般是上百个物理存储节点，图中的每个黑色实心圈都代表了一个物理存储节 点，这些节点上存储着所有对象的数据。图1还标明了本发明装置在分布式对 象存储系统中的具体应用位置，其中的操作主要包括以下流程：

(1)每个数据中心都可以看做是一个分布式对象存储系统，而数据中心之 间的数据可以看作是完全同步的。每个分布式对象存储系统包含了客户端， OSC，和PSC这三个主要组件。

(2)PSC负责初始化一切OSC的部署信息，OSC中的SN都有唯一的设 备标识号SN_ID，并由PSC根据环形一致性哈希算法，按照环形层次结构来组 织所有的SN。

(3)存储系统中的每个对象都会有一个唯一的对象标识Obj_ID，OSC会 为每一份对象文件以两种形式保存：首先保存在其中一台SN上保存对象的完整 的备份，这台SN称为该对象的主节点(Master Node，MN)；MN使用编码程 序将这份完整的对象数据计算成k个数据子块和m个校验子块，并将k+m个块 发送并保存到k+m个独立的SN上。这k+m个SN处于不同容灾域中，每一个 块的大小的均为所从属的对象的体积大小的1/k。存放原始数据块的SN称为数 据节点(DataNode，DN)，存放校验块的SN则称为校验节点(Parity Node，PN)。

(4)对于步骤(3)中的对象保存和管理方案，这1+k+m个SN组成了一 条混合的保存该对象的链，称为(1，k，m)参数组装置，MN以外的部分称为 可编码子链(Erasure Coded Chain，ECC)。链内所有的SN之间会定期通过交换 心跳信息来获取其他节点的运行情况，每个节点通过每个对对象的附属元数据 知道自身在链中的位置，以及其他节点的位置和SN_ID。

(5)PSC接收来自客户端的Restful接口形式的对象读写请求，根据请求类 型的不同，由代理服务器集群PSC导向到特定的SN上；

(6)SN节点完成对请求的处理，并和客户端之间直接进行对象的传输。

图2是基于多版本的链式备份机制处理来自客户端的写请求的流程示意图， 具体地包括以下步骤：

(1)PSC根据客户端发送过来的请求报文中的请求类型字段，判断该写请 求为上传请求或是更新请求。

(2)若判断结果为上传请求，PSC会通过计算Obj_ID的哈希值，映射到 对应的OSC中的某一个SN上，此SN则称为该对象的MN，然后MN直接与 客户端进行通讯，客户端直接发送对象到MN上。

(3)在步骤(2)中，对象完全写入MN后，MN会启动编码流程并生成 k+m个块，然后并行地将这些块写入到对应的ECC中的SN中。ECC中所有的 SN均返回写入成功的响应后，MN向客户端返回对象上传操作处理完毕的消息。

(4)对于步骤(1)中的判断结果，若客户端发送的是更新请求，那么PSC 则会通过请求报告中的随机写偏移量，对象的大小，以及参数k，计算出目标导 向DN，计算公式为：SN_ID＝Obj_ID哈希值+偏移量％(对象大小/k)+1。

(5)计算出导向的DN后，该DN从客户端接收需要更新的数据，并利用 新的数据块和旧的数据块根据编码矩阵计算出一个差异矩阵(Delta)，然后该 DN并行地完成以下两个操作：第一，立即更新其磁盘上相对应的数据子块；第 二，将计算出的Delta传送到每一个PN上。

(6)m个PN收到来自该DN的Delta后，将该Delta存放到从属于该对象 的更新缓冲区里，并以客户端ID和操作时间戳作为该次更新操作的版本号。每 个对象的更新缓冲区的长度均是固定的，若更新的操作的版本数超过了缓冲区 长度，则把最旧的版本删除出缓冲区。每次更新请求所产生的新版本都被标识 为“脏”的，表示着该更新版本只在ECC上存在，MN上的完整的对象备份尚未 更新到该版本，若MN上的完整对象备份也更新到了这个版本，则这个版本被 改为“干净”的。

(7)在步骤(6)中，ECC采用惰性重构的策略来决定和选择对MN上完 整对象备份进行重构和覆盖写入的时机，若一个对象被更新过大于或等于一次， 但该对象在MN上的完整备份还没进行过重构，则对应的DN和PN关于该版本 的状态则标识为“脏”的。DN会周期性地查询MN的繁忙状态，若MN响应该 对象可用于重构覆盖，则对应的DN会发起解码重构程序，将最新版本的对象 子块从ECC的各个SN上传送到MN上。在MN重构并覆盖旧版本的对象完毕 后，向ECC的各个SN发出ACK确认信息，各个SN则把对应的版本标识为“干 净”的。

图3是基于多版本的链式备份机制处理来自客户端的读请求的流程示意图， 具体地包括以下步骤：

(1)PSC通过读请求报文中Obj_ID，通过哈希值计算，将该请求导向到该 对象的MN上。

(2)MN查询其Obj_Table，若该对象存在与本地磁盘上，并且MN能够 正常完成该读请，则由MN从本地磁盘上顺序读出被请求对象，并返回给客户 端。

(3)在步骤(2)中，若MN经过查询后找不到该对象的信息，则向用户 返回无法找到对象的响应。

(4)在步骤(2)中，若MN因为短暂性宕机或者磁盘暂时性失效，无法 正常处理该读请求，PSC会将该读请求重导向到ECC上的第一个DN上。该SN 会并发地向ECC中其余的SN转发该读请求，并等待其他SN的回应。

(5)在步骤(4)中，若ECC上的第一个DN若收到所有其他DN的回应， 则表示ECC子链上所有的原始数据子块均可用，该忽略来自所有PN的回应信 息，并接收来自其他DN的数据块的传输。k-1个数据块传输完毕并按照顺序组 装完毕后，向客户端返回该对象。

(6)在步骤(4)中，若ECC中的第一个DN没有收到所有来自其他DN 的回应消息，但总共收到了大于或等于k个SN的回应消息，则必须要启动解码 程序来恢复该对象。任意选择k个返回了消息的ECC中的SN，并行地进行解 码程序，将对象恢复后返回给客户端，同时将遗失的子块重新写入对应的DN 或PN中。

(7)在步骤(6)中，若ECC的第一个DN没有收到所有来自其他DN的 回应消息，并且收到的回应信息的数量小于k，则说明该对象在装置上已彻底丢 失或失效，返回读取失败的响应至客户端。

(8)在步骤(5)和(6)中，若被读对象只存在一个版本，则向客户端返 回该版本。若被读对象存在多个更新版本，则ECC会按照一定策略来选取合适 的版本返回给客户端。

(9)在步骤(8)中，若该对象最新的版本，即时间戳最大的版本，是干 净的，则返回这个最新并干净的版本给客户端；若最新的版本是脏的，同时这 个版本的修改者客户端ID与该次读请求的客户端ID是相同的，则返回该版本； 若最新的版本是脏的，但这个版本的修改者客户端ID与该次读请求的客户端ID 不相同，则按照时间戳的变小的顺序往下一个版本查询；直至找到一个干净的 版本，或者修改者客户端ID与该次请求客户端ID相同的版本，重构并返回这 个版本给客户端，若没有找到符合以上所有条件的版本，则返回缓冲区中所记 录的标识着最小时间戳的版本的版本给客户端。

上述的对实施例的描述是为便于本技术领域的普通技术人员能理解和应用 本发明。熟悉本领域技术的人员显然可以容易地对上述实施例做出各种修改， 并把在此说明的一般原理应用到其他实施例中而不必经过创造性的劳动。因此， 本发明不限于上述实施例，本领域技术人员根据本发明的揭示，对于本发明做 出的改进和修改都应该在本发明的保护范围之内。