一种全分布式文件索引及协作编辑机制的实现方法

摘要

本发明公开一种全分布式文件索引及协作编辑机制的实现方法，包括：将文件夹信息采用Key-value字典文件形式存储于Swift存储介质中，对文件夹操作变为文件夹索引文件修改操作；采用补丁提交方式进行文件更新；在API和Swift间建立中间层，接收提交的补丁文件；中间层负责合并向该节点提交的补丁；所有中间层节点协同在分布式线段树上合并得到合并所有更改的补丁；将原文件与补丁合并作为原文件最终版本。本发明既提供了分布式、高度稳定的文件索引系统，又统一了文件操作与文件夹操作，提出了一套离线协作编辑机制，弥补了Openstack？Swift为追求完全分布式而牺牲的文件操作原子性及不良的文件索引支持。

说明书

技术领域

本发明涉及互联网技术领域，尤其涉及一种全分布式文件索引及协作编辑 机制的实现方法。

背景技术

在“云”的概念如此流行的今天，云计算、云存储等应用已经较为成熟， 为人们生活带来便利。云存储，即将数据通过上传、下载或同步的方式托管至 云端，以其跨平台、限制弱、可靠性高的特征在网络普及率较高的现今发挥着 重要的作用，可免去用户在不同设备间拷贝数据的麻烦，并可给用户提供不会 丢失、不会损坏的重要数据备份仓库。在这样的背景下，各大商业云存储服务 纷纷崛起，从Dropbox、GoogleDocs到国内的百度网盘，但其依托的下层技术 都是各自实现的分布式对象存储系统：如Dropbox的对象容器是AmazonS3。

由于商业云存储技术细节均未知，故开源界也出现了海量的分布式文件系 统，如Hadoop框架下的HDFS，Ceph，以及Openstack项目的Swift。Swift号 称开源版的AmazonS3，提供任意大小的对象在任意集群上的存储服务。其有 以下几个优点：1、架构高度分布式，其担任任何角色的节点均可扩展，平等节 点的功能高度对称，不存在单点失败(SingleNodeFailure)。与之相比， HDFS的文件元数据与索引存储于单台机器；而Ceph在存储访问上有主从结构， 这都限制了其在超大集群的可扩展性。2、支持吞吐量大，由于其采取最终一致 (EventuallyConsistent)的策略，无需收到其他节点的阻塞即可完成数据存 取。

但是，相对其他云存储项目，Swift仍存在如下不足：1、原子操作过少， Swift仅支持读、写(覆盖)两个原子操作，相较而言Ceph支持追加(Append)和 缩减(Truncate)操作，结合其弱一致性，在Swift上存储有修改需求的元数据 文件较为困难。2、原生文件层次支持差，作为可用的文件系统，文件夹支持是 必不可少的。然而在Swift中，文件夹通过文件名前缀方式维护，导致对文件 夹的批量操作没有原子性，带来较差的使用体验。那么，在保留以Openstack 为代表的算法全分布式、完全可扩展的特色上增加文件的原子性更改操作、优 化文件系统层次处理方式则成了尚未完全探索的问题。

发明内容

本发明的目的在于通过一种全分布式文件索引及协作编辑机制的实现方 法，来解决以上背景技术部分提到的问题。

为达此目的，本发明采用以下技术方案：

一种全分布式文件索引及协作编辑机制的实现方法，其包括如下步骤：

S101、将文件夹信息采用Key-value字典文件形式存储于Swift存储介质 中，对文件夹的操作变为文件夹索引文件的修改操作；

S102、采用补丁提交方式进行文件更新；

S103、在使用者API和Swift间建立中间层，接收提交的补丁文件；

S104、中间层负责合并向该节点提交的补丁；

S105、所有的中间层节点协同在分布式线段树上合并得到合并所有更改的 补丁；

S106、将原文件与该补丁合并作为原文件最终版本。

特别地，所述步骤S101还包括：目录文件将转化为由该目录下文件/文件 夹名(Key)指向对应文件/文件夹索引在存储介质中的真实文件名(Value)的字 典，并对Key排序后按一定的格式转换为文件。

特别地，所述步骤S102中补丁文件在时间戳的配合下，与补丁合并运算满 足结合律、交换律，即组成阿贝尔半群；原文件和补丁文件合并后得到新版本 的目标文件；一切满足阿贝尔半群的补丁格式和合并运算均适用于步骤S102。

特别地，所述步骤S103中所述中间层部署于OpenstackSwift的Proxy节 点并承接原本应该调用SwiftAPI的HTTP请求，并根据对应业务逻辑代为调用 原SwiftAPI并将调用结果返回给中间层访问者；其业务逻辑包括但不限于：

一、读取某个文件内容的请求，中间层将向Swift发起读取与总补丁合并 后的文件的请求；若该文件不存在，则发起获取原文件请求；最后返回请求结 果以及文件；

二、修改/增加某文件内容的请求，中间层将向Swift提交补丁文件，并着 手合并以得到总补丁文件；

三、访问某文件夹的文件的请求，中间层将向Swift提交查询请求，读取 根目录索引文件并从中获取下一级目录的文件名，而后读取下一级目录索引文 件，依次递推寻找到目标文件在存储介质中的文件名；

四、增加/删除某文件夹的请求，中间层将向Swift提交修改索引文件的补 丁。

特别地，所述步骤S104包括；某节点部署的中间层在提交补丁文件后，开 始将针对该文件通过该节点提交的全部补丁文件进行合并，尚未合并的内部补 丁由单项链表组成，合并线程从链表上任意项着手，将其合并并将链表指针指 向下一个文件；其中，链表指针信息由Swift的文件Metadata存储。

特别地，所述步骤S105包括：维护一个分布式线段树，树上节点为其子树 树根节点对应的中间层提交补丁的总和；当中间层节点内部补丁更新时，沿分 布式线段树自底向上更新。

特别地，所述步骤S105中分布式线段树为一棵拥有特殊编号规则的二叉 树，树中叶节点对应着不同的中间层节点，非叶节点为虚拟节点，用于汇总其 子节点的补丁信息；每一个非叶节点的汇总信息均为其左右子节点(若仅有一 个子节点则只计入该节点)的补丁之和。

特别地，所述步骤S105中分布式线段树的编号公式如下：

一、对于中间层节点n∈Z≥0，对应的树上叶节点编号为i＝(n＜＜1)+1；

二、对于非叶节点i，其左右子节点及父节点分别编号为

parent(i)＝(i^(i&-i))|((i&-i)＜＜1)

left(i)＝i-((i&-i)＞＞1)

right(i)＝i+((i&-i)＞＞1

其中>><<^&|分别代表逻辑右移、逻辑左移、按位异或、按位与、 按位或。

特别地，所述步骤S106具体包括：将分布式线段树树根的总补丁与原文件 进行合并，而后得到最新版文件存储于Swift用于读取。

本发明提出的全分布式文件索引及协作编辑机制的实现方法既提供了分布 式、高度稳定的文件索引系统，又统一了文件操作与文件夹操作，提出了一套 离线协作编辑机制，弥补了OpenstackSwift项目为追求完全分布式而牺牲的 文件操作原子性以及不良的文件索引支持。

附图说明

图1为本发明实施例提供的全分布式文件索引及协作编辑机制的实现方法 流程图；

图2为本发明实施例提供的文件目录索引的文件结构示意图；

图3为本发明实施例提供的中间层业务示意图；

图4为本发明实施例提供的分布式线段树编号示意图；

图5为本发明实施例提供的从某中间层节点提交的补丁文件合并流程图。

具体实施方式

为了便于理解本发明，下面将参照相关附图对本发明进行更全面的描述。 附图中给出了本发明的较佳实施例。但是，本发明可以以许多不同的形式来实 现，并不限于本文所描述的实施例。相反地，提供这些实施例的目的是使对本 发明的公开内容理解的更加透彻全面。除非另有定义，本文所使用的所有的技 术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文 中在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是 旨在于限制本发明。本文所使用的术语“及/或”包括一个或多个相关的所列 项目的任意的和所有的组合。

请参照图1所示，图1为本发明实施例提供的全分布式文件索引及协作编 辑机制的实现方法流程图。

本实施例中全分布式文件索引及协作编辑机制的实现方法具体包括：

S101、将文件夹信息采用Key-value字典文件形式存储于Swift存储介质 中，对文件夹的操作变为文件夹索引文件的修改操作。

目录文件将转化为由该目录下文件/文件夹名(Key)指向对应文件/文件夹 索引在存储介质中的真实文件名(Value)的字典，并对Key排序后按一定的格式 转换为文件。其中，Key值为该文件夹下某子文件/子文件夹的名称，而Value 值对应的是该文件/文件夹索引文件在Swift中存储的真实名称。由虚拟文件系 统名称建立向真实名称的映射，从而在输入虚拟文件系统路径时根据路径一步 步读取文件索引，找到其在Swift中存储的真正名称并提供访问。由于该文件 也需要固化在存储介质，故需要有合适的顺序表达形式描述之。一种文件结构 描述方式见如图2所示，文件首通过若干字节鉴定文件头，而后按Key值字典 序顺序存储每一项的Key大小、Value大小、该更改时间戳(用于补丁合并， 下文S2详解)以及Key值、Value值，字符串编码为utf-8。最后，一个四字 节的0值将标志着文件的结束。

S102、为弥补全分布式算法不能实现原子性更改的弊端，采用补丁提交方 式进行文件更新。

补丁文件在时间戳的配合下，与补丁合并运算满足结合律、交换律，即组 成阿贝尔半群；原文件和补丁文件合并后得到新版本的目标文件；一切满足阿 贝尔半群的补丁格式和合并运算均适用于步骤S102。代数表示如下：补丁文件 为P_i，合并运算符为+，则补丁文件以及在其上定义的合并运算必须满足：

P₁+P₂＝P₂+P₁

P₁+P₂+P₃＝P₁+(P₂+P₃)

以文件系统索引文件的补丁合并操作为例，其大致步骤如下：

S102.1、将两个文件从结构化文件中读取、恢复为字典文件。

S102.2、合并两个字典，对于只出现于一个字典的Key-Value对，原封不 动地保留；对于同时出现在两个字典的Key值，则取其对应的时间戳Ts更高的 Value值并保留进新字典，另一项作废。若两个时间戳相等，由于时间戳的秒 级精确性，该情况被判定为一次不可解决冲突，随机保留一边的Value。

S102.3、将合并后的字典转换为结构化的文件(结构见上文步骤S101)， 得到合并结果。

容易证明，以上合并操作是满足交换律、结合律的，故与索引文件一起组 成阿贝尔半群，为该系统中有效的文件类型。

S103、在使用者API和Swift间建立中间层，接收提交的补丁文件。

中间层部署于OpenstackSwift的Proxy节点并承接原本应该调用Swift API的HTTP请求，并根据对应业务逻辑代为调用原SwiftAPI并将调用结果返 回给中间层访问者；其业务逻辑包括但不限于：

一、读取某个文件内容的请求，中间层将向Swift发起读取与总补丁合并 后的文件的请求；若该文件不存在，则发起获取原文件请求；最后返回请求结 果以及文件；

二、修改/增加某文件内容的请求，中间层将向Swift提交补丁文件，并着 手合并以得到总补丁文件；

三、访问某文件夹的文件的请求，中间层将向Swift提交查询请求，读取 根目录索引文件并从中获取下一级目录的文件名，而后读取下一级目录索引文 件，依次递推寻找到目标文件在存储介质中的文件名；

四、增加/删除某文件夹的请求，中间层将向Swift提交修改索引文件的补 丁。

中间层对原API访问的劫持方式如图3所示。其处理方式包括：(与上文四 个样例业务逻辑相对，仅为诸多业务逻辑的典型范例，并不限制本发明在满足 特征描述的前提下扩展其他如删除文件、文件枚举等其他业务)

一、解析读取文件的文件地址，依次向Swift服务发送请求读取索引文件 找到请求的文件在存储介质中的真实名称，并下载、转发该文件给用户请求。

二、解析写文件的文件地址，若原文件不存在，则新分配一个文件名并将 其上传至Swift，而后修改该文件父文件夹对应索引文件，加入以该文件对外 显示文件名到分配的实际文件名的Key-Value对；若原文件存在，则提取出需 要修改的部分，并将其以补丁文件的形式提交，补丁文件命名方式见下文S104。

三、过程类似业务一的处理流程，但不将文件下载给用户而只是返回其真 实文件名。

四、由于文件夹也为文件，在新建文件夹时等价于在该位置上传空白索引 文件(空白模板，需要保留KVMP文件头以及4字节结尾符号)；删除文件只需 修改父文件夹索引文件。

S104、中间层负责合并向该节点提交的补丁。某节点部署的中间层在提交 补丁文件后，开始将针对该文件通过该节点提交的全部补丁文件进行合并，尚 未合并的内部补丁由单项链表组成，合并线程从链表上任意项着手，将其合并 并将链表指针指向下一个文件；其中，链表指针信息由Swift的文件Metadata 存储。其命名规则如下：对于真实文件名为EXACT_NAME的文件，其通过中间层 i提交的第j号补丁文件命名为EXACT_NAME.PROXYi.PATCHj。而每个文件的 Metadata中存储其在链表上指向下一个内部补丁的补丁编号。在补丁刚被创建 时，此编号为自身编号+1，指向一个不存在的文件。添加了Metadata后的补丁 文件将被存入Swift，自然地，其位于链表表尾。而后若有新补丁加入，自动 填充了下一个补丁编号，而前一个补丁中存储下一个补丁的编号也就自然有了 实际文件，链表得以延长。

进行内部合并时，合并线程工作流程如下：

S104.1、合并线程在创建时被分配了一个合并点pinpoint。该合并点合法 当且仅当不存在任何其他合并线程(其合并点为pinpoint’)，pinpoint’ ＝pinpoint或pinpoint’在链表上的后继是pinpoint。

S104.2、合并线程读取pinpoint号补丁。以及其Metadata中记录的链表 后继号next。

S104.3、合并线程读取next号补丁，与pinpoint补丁合并。

S104.4、合并后的pinpoint号补丁链表后继号为原next号补丁的后继， 并将该合并后文件写回Swift替换原有pinpoint号补丁。

S104.5、重复上述S104.1，注意的是如果之前合并结果在内存中依然存在， 可免去重复读取。直到next号补丁不存在，线程结束。

该合并可在pinpoint均合法的条件下多线程并发进行，而最小线程、即最 经典的合并模型为pinpoint＝0的单线程执行。

S105、所有的中间层节点协同在分布式线段树上合并得到合并所有更改的 补丁。分布式线段树如图4所示，分布式线段树为一棵拥有特殊编号规则的二 叉树，树中叶节点对应着不同的中间层节点，非叶节点为虚拟节点，用于汇总 其子节点的补丁信息；每一个非叶节点的汇总信息均为其左右子节点(若仅有 一个子节点则只计入该节点)的补丁之和。分布式线段树的编号公式如下：

一、对于中间层节点n∈Z≥0，对应的树上叶节点编号为i＝(n＜＜1)+1。

二、对于非叶节点i，其左右子节点及父节点分别编号为

parent(i)＝(i^(i&-i))|((i&-i)＜＜1)

left(i)＝i-((i&-i)＞＞1)

right(i)＝i+((i&-i)＞＞1

其中>><<^&|分别代表逻辑右移、逻辑左移、按位异或、按位与、 按位或。

维护一个分布式线段树，树上节点为其子树树根节点对应的中间层提交补 丁的总和；当中间层节点内部补丁更新时，沿分布式线段树自底向上更新。

分布式线段树的更新的一种实施方式如下：

S105.1、某节点由于0号内部补丁更新，着手启动分布式线段树更新线程。

S105.2、线程使用公式i＝(n＜＜1)+1计算出本中间层节点对应的分布式线段 树树节点编号。并以其为当前节点。

S105.3、利用公式parent(i)＝(i^(i&-i))|((i&-i)＜＜1)计算出当前节点的父 节点，并更新该节点的补丁数据，具体方法如下：

S105.3.1、采集该节点的左右儿子节点对应的补丁，若该子节点为叶节点， 表示其对应着一个中间层节点，则取该中间层节点的0号补丁(总补丁)为其 内容；否则取树节点对应的补丁。

S105.3.2、若左右儿子中补丁有不存在的(如某叶节点对应的中间层从来 没提交过补丁，或不存在该中间层节点)，则存在的子节点补丁作为本节点补丁 数据准备更新；若左右子节点补丁均存在，则将其合并后作为本节点补丁数据 准备更新。注意记录获取左右儿子补丁的精确到毫秒的时间戳Tl,Tr，下一步 将使用。若左右儿子补丁均不存在，终止外部合并线程。

S105.3.3、发送请求获取该节点对应补丁在存储介质中的metadata，比对 其Tl’,Tr’，若Tl<＝Tl’且Tr<＝Tr’，证明本地版本已过期，有其他中间层节 点更新了Swift，本地版本丢弃，终止合并线程。

否则，若Tl<Tl’或Tr<Tr’，证明本地版本和Swift版不一致且更新时间 不可互相覆盖，则重新获取左右儿子数据着手更新，回到S105.3.1。

否则，本地版本新于Swift版，可连同更大的时间戳Tl,Tr提交给Swift 存储。

需要注意的是，该方法并不能完全阻止多服务器的情况下读写非原子性带 来的信息更新不全面的问题，在高并发下该情况尤为严重。然而考虑到Swift 本身最终一致性，该算法具有的最终一致性是合理的。若需要高实时、强一致 的数据合并，可在一台服务器的内存中合并并将补丁定期提交。

S105.4、父节点作为当前节点，重复步骤二。若当前节点已经没有父节点， 则将其和原文件合并，作为cversion文件提交(该文件即是读取请求时访问的 文件)。

S106、将原文件与该补丁合并作为原文件最终版本。将分布式线段树树根 的总补丁与原文件进行合并，而后得到最新版文件存储于Swift用于读取。其 中内部补丁合并、外部合并的具体流程如图5所示。

另外，本系统还包括用于实现上述方法各步骤的模块、子模块、单元、子 单元，为避免重复说明，不再赘述。

本发明的技术方案既提供了分布式、高度稳定的文件索引系统，又统一了 文件操作与文件夹操作，提出了一套离线协作编辑机制，弥补了Openstack Swift项目为追求完全分布式而牺牲的文件操作原子性以及不良的文件索引支 持。

注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员 会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进 行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽 然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以 上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例， 而本发明的范围由所附的权利要求范围决定。