一种基于一致性散列的结构化数据存储、查询和迁移方法

摘要

本发明公开了一种基于一致性散列的结构化数据存储、查询和迁移方法，步骤如下：建立基于一致性散列的HDFS数据存储模型，基于此模型进行数据存储和数据查询，当有数据节点加入或失效时，实施数据迁移；所述数据存储方法是将待写入文件的各数据块进行一致性散列得到数据块Hash值，然后根据数据块Hash值，在节点Hash链中查找该数据块的存储节点并将数据块内容存入其存储节点。本发明基于HDFS集群主从结构，应用一致性散列，使结构化数据均匀分散在HDFS集群的各个数据节点上，有效地提高并行遍历数据的效率，当数据节点数量发生变化时，可大大减少数据迁移所涉及的节点数量和总迁移数据量，提高数据存储系统的运行性能。

说明书

技术领域

本发明涉及计算机应用技术领域，尤其涉及一种基于一致性散列的结构化数据存储、查 询和迁移方法。

背景技术

对于海量结构化数据的存储与管理，以Hadoop分布式文件系统(Hadoop Distributed File  System,HDFS)作为底层存储的关系型数据库是目前主要的解决方案。HDFS的基本思想是 将一个文件分成若干个固定大小的数据块进行存储，其架构采用主/从结构体系，一个HDFS 集群包含一个名字节点(Namenode)和若干个数据节点(Datanode)。其中名字节点为主节 点，负责控制外部客户机的访问以及存储整个系统的元数据，元数据包括命名空间、文件到 数据块的映射、系统配置信息等；而数据节点则是从属节点，用来存储实际文件数据，即HDFS 数据块。为提高数据的可靠性和可用性，每个数据块都默认保存三份冗余，每个备份副本存 储于不同的数据节点上。对外部应用而言，HDFS如同传统的分布式文件系统，可以对文件 进行创建、删除、移动等操作。

然而，上述解决方案存在的问题是：

1.存储不均衡，严重影响并行遍历效率

HDFS在对表数据进行存储时，是根据集群中各数据节点的负载情况来选择数据块的存 储节点的，负载较少的数据节点被优先选择用来存储，这种存储策略不考虑所存储数据块之 间的关联，当数据流量很大时，由于大部分数据块会存储到负载较少的节点上，因而使隶属 于同一个表的数据块分布不均衡，因而严重降低了遍历数据的并行效率，造成较大的数据库 查询延迟。

2.数据迁移涉及所有节点，严重影响系统的运行性能

在部署HDFS的集群中，数据节点的加入和失效是常态。为保证集群中各个数据节点的 负载均衡，当数据节点数量变化时需要进行数据迁移。如：当部署HDFS的集群中有新的数 据节点加入时，其他所有的节点都要将部分数据迁移到新节点；而当有节点失效时，系统会 将失效节点在冗余节点上的备份均匀地迁移到其他节点上。无论是节点加入还是节点失效， 数据迁移均涉及HDFS系统中所有的数据节点，造成大量的迁移负载，致使网络拥塞，极大 地影响了HDFS系统的运行性能。

一致性散列算法具有以下三个特点：1.平衡性，即：将关键字进行一致性散列后，可以 根据散列值将其均匀地分布在地址空间中。2.单调性，指当地址空间增大或减小时，通过一 致性散列得到的散列值能够映射到新的地址空间，而不是原来的地址空间。3.分散性，是指 当用户通过散列过程将关键字映射到地址空间时，一致性散列算法会避免因可见范围不同而 出现的映射结果不一致的情况。一致性散列目前主要用于P2P环境和分布式缓存等技术，本 发明将一致性散列思想用于HDFS结构化数据存储领域，并对现有一致性散列的对等结构进 行改进，使其应用于HDFS的主从结构体系。

发明内容

本发明的目的是为了解决HDFS系统所存在的上述两个问题，提供一种基于一致性散列 的结构化数据存储、查询和迁移方法，它的优点是：(1)利用一致性散列对数据块进行存储， 使文件所对应的数据块均匀分散在集群中的各个节点上，因而有效地提高了并行遍历数据的 效率。(2)当数据节点数量发生变化时，如：节点增加或失效，只需要在新增节点或失效节 点的相邻节点发生数据迁移，因而大大减少数据迁移所涉及的节点数量和总迁移数据量，提 高了HDFS系统的运行效率。

本发明所采用的技术方案如下：

定义1数据块Hash值：对HDFS系统中数据块B，以其数据块标号为关键字进行一致 性散列，所得散列值H_b(B)称为数据块B的Hash值。

定义2节点Hash值：对HDFS系统中数据节点D，以其物理地址为关键字进行一致性 散列，所得散列值H_d(D)称为数据节点D的Hash值。

定义3节点Hash链：设<H_d₁,H_d₂,…,H_d_n>为HDFS系统中各数据节点的Hash值按 照自小到大的顺序进行排序所得序列，其中：H_d_k＜H_d_k+1，(1≤k＜n)，记DN(H_d_k)表示H_d_k所对应的数据节点，则线性结构[DN(H_d₁),DN(H_d₂),…,DN(H_d_n)]称为该HDFS系统的节点 Hash链，其中，DN(H_d_k+1)称为DN(H_d_k)的后继节点，同时定义DN(H_d_n)的后继节点为 DN(H_d₁).

基于一致性散列的结构化数据存储方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值，对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

基于一致性散列的结构化数据存储、查询方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值；对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

步骤(3a)：数据查询：首先从名字节点中查找待查询文件所对应的数据块，并计算这些 数据块的Hash值，然后分别根据所得数据块Hash值，按照步骤(2)所述的查找方法，在 Hash链元数据表中查找各数据块所对应的存储节点，在存储节点上进行数据块的读取。

基于一致性散列的结构化数据存储、迁移方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值；对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

步骤(3b)：数据迁移，包括：

步骤(3b-1)：当部署HDFS的集群中有新数据节点加入时，首先计算出新数据节点的 Hash值，并依据所得Hash值，通过二分插入排序算法在Hash链元数据表中插入新数据节点 的记录，然后将Hash链中新数据节点的后继节点上Hash值小于或等于新节点Hash值的数 据块迁移到新节点上，最后在名字节点上对新数据节点及其后继节点的信息进行更新；

步骤(3b-2)：当部署HDFS的集群中出现失效节点时，首先从名字节点中读取该失效节 点的信息，计算该失效节点的Hash值，并通过二分查找算法在Hash链元数据表中找到失效 节点的记录，然后将失效节点的数据块从其冗余节点上恢复到失效节点的首个非失效后继节 点上，最后从Hash链元数据表中删除失效节点记录，从名字节点中删除失效节点信息，并更 新恢复节点信息。

所述步骤(1)包括：

步骤(1-1)：计算数据节点Hash值：选取一致性Hash函数，对部署HDFS系统的集群 的各数据节点，将其物理地址以ASCII码字符串形式作为关键字进行一致性散列，得到各数 据节点的Hash值；

步骤(1-2)：构造节点Hash链：对于部署HDFS系统的集群，将集群中所有数据节点均 按照步骤(1-1)所述方法计算节点Hash值，并根据所述节点Hash值由小到大对数据节点进 行排序，形成节点Hash链；

步骤(1-3)：存储Hash链元数据表：将节点Hash链中所有数据节点的物理地址和Hash 值的映射记录，以顺序表形式存储于HDFS系统的名字节点上，形成Hash链元数据表，当 HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中。

所述步骤(2)包括：

将待写入文件所对应的每一个数据块，按照以下步骤进行数据存储，直至所有的数据块 均被存储到HDFS系统的数据节点中：

步骤(2-1)：计算数据块Hash值：选取与所述步骤(1-1)相同的一致性Hash函数，以 当前数据块的块标号为关键字进行一致性散列，得到当前数据块的Hash值；所述数据块标号 是指数据块的唯一性标识号；

步骤(2-2)：查找数据块的存储节点：以当前数据块Hash值为查找关键字，通过二分查 找算法，在Hash链元数据表中查找第一个节点Hash值大于或等于该数据块Hash值的数据 节点，所得数据节点即为当前数据块所对应的存储节点；

步骤(2-3)：存储数据块：将当前数据块内容存储到步骤(2-2)查找所得的存储节点上；

步骤(2-4)：将数据块及其存储节点信息写入名字节点。

所述步骤(3a)包括：

当客户向HDFS系统提出读取文件请求时，按以下步骤完成查询：

步骤(3a-1)：从名字节点中查找该文件所对应的数据块；

步骤(3a-2)：对每一个数据块分别按照步骤(2-1)所述方法计算数据块Hash值；

步骤(3a-3)：按照步骤(2-2)所述方法查找当前数据块所对应的存储节点；

步骤(3a-4)：将当前数据块内容从其所对应的存储节点上读出。

所述步骤(3b-1)包括如下步骤：

步骤(3b-1-1)：对新加入的数据节点在名字节点进行注册，加入HDFS集群中；

步骤(3b-1-2)：按照步骤(1-1)所述方法计算新数据节点的Hash值；

步骤(3b-1-3)：采用二分插入排序算法，在Hash链元数据表中插入新数据节点的物理 地址与Hash值的映射记录；

步骤(3b-1-4)：在Hash链中找到新数据节点的后继节点，将所述后继结点中数据块Hash 值小于或等于新数据节点Hash值的数据块全部迁移到新数据节点上；

步骤(3b-1-5)：在名字节点上对新数据节点及其后继节点的信息进行更新。

所述步骤(3b-2)包括如下步骤：

步骤(3b-2-1)：从名字节点中读取失效节点的物理地址、失效节点上各数据块标号及其 冗余节点位置；

步骤(3b-2-2)：按照步骤(1-1)所述方法计算失效节点的Hash值；

步骤(3b-2-3)：根据失效节点的Hash值，通过二分查找算法，在Hash链元数据表中找 到该失效节点，记录其第一个未失效后继节点，作为该失效节点的恢复节点；

步骤(3b-2-4)：对存储于失效数据节点上的所有数据块，将其存储在冗余节点的副本拷 贝到步骤(3b-2-3)所述的恢复节点上；

步骤(3b-2-5)：从Hash链元数据表中删除该失效节点的记录；

步骤(3b-2-6)：从名字节点中删除失效节点信息，并更新恢复节点信息。

本发明的有益效果：

(1)本发明基于一致性散列对HDFS系统的数据块进行存储，每个数据块根据Hash值 确定所对应的存储节点，由于一致性散列能够使文件所对应的数据块均匀分散在集群的各个 数据节点上，因而大大提高了并行遍历数据的效率。

(2)当数据节点数量发生变化时，如：节点加入或失效，只需要在新添节点或失效节点 的相邻节点发生数据迁移，大大减少了数据迁移所涉及的节点数量和总迁移数据量，从而有 效地提高了HDFS系统的运行性能。

附图说明

图1是本发明的基于一致性散列的结构化数据存储主流程图；

图2是本发明的基于一致性散列的结构化数据存储、查询主流程图；

图3是本发明的基于一致性散列的结构化数据存储、迁移主流程图；

图4是数据节点Hash链结构示意图；

图5是节点Hash链元数据表示意图；

图6是数据节点Hash链构造过程示意图；

图7是HDFS数据块存储过程示意图；

图8是节点添加时数据迁移过程示意图；

图9是节点失效时数据迁移过程示意图。

具体实施方式

下面结合附图与实施例对本发明作进一步说明。

定义1数据块Hash值：对HDFS系统中数据块B，以其数据块标号为关键字进行一致 性散列，所得散列值H_b(B)称为数据块B的Hash值。

定义2节点Hash值：对HDFS系统中数据节点D，以其物理地址为关键字进行一致性 散列，所得散列值H_d(D)称为数据节点D的Hash值。

定义3节点Hash链：设<H_d₁,H_d₂,…,H_d_n>为HDFS系统中各数据节点的Hash值按 照自小到大的顺序进行排序所得序列，其中：H_d_k＜H_d_k+1，(1≤k＜n)，记DN(H_d_k)表示H_d_k所对应的数据节点，则线性结构[DN(H_d₁),DN(H_d₂),…,DN(H_d_n)]称为该HDFS系统的节点 Hash链，其中，DN(H_d_k+1)称为DN(H_d_k)的后继节点，同时定义DN(H_d_n)的后继节点为 DN(H_d₁).

如图1所示，基于一致性散列的结构化数据存储方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值；对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

如图2所示，基于一致性散列的结构化数据存储、查询方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值；对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

步骤(3a)：数据查询：首先从名字节点中查找待查询文件所对应的数据块，并计算这些 数据块的Hash值，然后分别根据所得数据块Hash值，按照步骤(2)所述的查找方法，在 Hash链元数据表中查找各数据块所对应的存储节点，在存储节点上进行数据块的读取。

如图3所示，基于一致性散列的结构化数据存储、迁移方法，包括如下步骤：

步骤(1)：建立数据存储模型：首先对部署HDFS的集群中所有数据节点，以数据节点 的物理地址为关键字进行一致性散列，得到节点Hash值；然后根据所述节点Hash值由小到 大对数据节点进行排序，形成节点Hash链，将节点Hash链中所有数据节点的物理地址与Hash 值的映射记录以顺序表形式存储到HDFS集群的名字节点上，所述映射记录顺序表又称Hash 链元数据表，当HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中；

步骤(2)：数据存储：将待写入文件的每个数据块按照数据块标号，采用与所述步骤(1) 数据节点散列相同的哈希函数进行一致性散列，得到数据块Hash值；对于每一个数据块，首 先根据其数据块Hash值，从Hash链元数据表中查找首个节点Hash值大于或等于该数据块 Hash值的数据节点，所查找的数据节点即为该数据块所对应的存储节点，然后将当前数据块 内容存储到所对应的存储节点上，最后将数据块及其存储节点的信息写入名字节点；

步骤(3b)：数据迁移，包括：

步骤(3b-1)：当部署HDFS的集群中有新数据节点加入时，首先计算出新数据节点的 Hash值，并依据所得Hash值，通过二分插入排序算法在Hash链元数据表中插入新数据节点 的记录，然后将Hash链中新数据节点的后继节点上Hash值小于或等于新节点Hash值的数 据块迁移到新节点上，最后在名字节点上对新数据节点及其后继节点的信息进行更新；

步骤(3b-2)：当部署HDFS的集群中出现失效节点时，首先从名字节点中读取该失效节 点的信息，计算该失效节点的Hash值，并通过二分查找算法在Hash链元数据表中找到失效 节点的记录，然后将失效节点的数据块从其冗余节点上恢复到失效节点的首个非失效后继节 点上，最后从Hash链元数据表中删除失效节点记录，从名字节点中删除失效节点信息，并更 新恢复节点信息。

所述步骤(1)包括：

步骤(1-1)：计算数据节点Hash值：选取一致性Hash函数，对部署HDFS系统的集群 的各数据节点，将其物理地址以ASCII码字符串形式作为关键字进行一致性散列，得到各数 据节点的Hash值；

步骤(1-2)：构造节点Hash链：对于部署HDFS系统的集群，将集群中所有数据节点均 按照步骤(1-1)所述方法计算节点Hash值，并根据所述节点Hash值由小到大对数据节点进 行排序，形成节点Hash链；

步骤(1-3)：存储Hash链元数据表：将节点Hash链中所有数据节点的物理地址和Hash 值的映射记录，以顺序表形式存储于HDFS系统的名字节点上，形成Hash链元数据表，当 HDFS启动时，所述Hash链元数据表将自动加载到名字节点的内存中。

所述步骤(2)包括：

将待写入文件所对应的每一个数据块，按照以下步骤进行数据存储，直至所有的数据块 均被存储到HDFS系统的数据节点中：

步骤(2-1)：计算数据块Hash值：选取与所述步骤(1-1)相同的一致性Hash函数，以 当前数据块的块标号为关键字进行一致性散列，得到当前数据块的Hash值；所述数据块标号 是指数据块的唯一性标识号；

步骤(2-2)：查找数据块的存储节点：以当前数据块Hash值为查找关键字，通过二分查 找算法，在Hash链元数据表中查找第一个节点Hash值大于或等于该数据块Hash值的数据 节点，所得数据节点即为当前数据块所对应的存储节点；

步骤(2-3)：存储数据块：将当前数据块内容存储到步骤(2-2)查找所得的存储节点上；

步骤(2-4)：将数据块及其存储节点信息写入名字节点。

所述步骤(3a)包括：

当客户向HDFS系统提出读取文件请求时，按以下步骤完成查询：

步骤(3a-1)：从名字节点中查找该文件所对应的数据块；

步骤(3a-2)：对每一个数据块分别按照步骤(2-1)所述方法计算数据块Hash值；

步骤(3a-3)：按照步骤(2-2)所述方法查找当前数据块所对应的存储节点；

步骤(3a-4)：将当前数据块内容从其所对应的存储节点上读出。

所述步骤(3b-1)包括如下步骤：

步骤(3b-1-1)：对新加入的数据节点在名字节点进行注册，加入HDFS集群中；

步骤(3b-1-2)：按照步骤(1-1)所述方法计算新数据节点的Hash值；

步骤(3b-1-3)：采用二分插入排序算法，在Hash链元数据表中插入新数据节点的物理 地址与Hash值的映射记录；

步骤(3b-1-4)：在Hash链中找到新数据节点的后继节点，将所述后继结点中数据块Hash 值小于或等于新数据节点Hash值的数据块全部迁移到新数据节点上；

步骤(3b-1-5)：在名字节点上对新数据节点及其后继节点的信息进行更新。

所述步骤(3b-2)包括如下步骤：

步骤(3b-2-1)：从名字节点中读取失效节点的物理地址、失效节点上各数据块标号及其 冗余节点位置；

步骤(3b-2-2)：按照步骤(1-1)所述方法计算失效节点的Hash值；

步骤(3b-2-3)：根据失效节点的Hash值，通过二分查找算法，在Hash链元数据表中找 到该失效节点，记录其第一个未失效后继节点，作为该失效节点的恢复节点；

步骤(3b-2-4)：对存储于失效数据节点上的所有数据块，将其存储在冗余节点的副本拷 贝到步骤(3b-2-3)所述的恢复节点上；

步骤(3b-2-5)：从Hash链元数据表中删除该失效节点的记录；

步骤(3b-2-6)：从名字节点中删除失效节点信息，并更新恢复节点信息。

如图4所示，数据节点Hash链结构，以五个数据节点A～E为例，图中数据节点旁边方 框中字符表示该数据节点的Hash值，方框下方字符表示该数据节点的物理地址，箭头表示后 继关系。

如图5所示，节点Hash链元数据表，图中HA(Node_j)表示数据节点Node_j的物理地址， Hash(Node_j)表示数据节点Node_j的Hash值，其中，1≤j≤n,n为数据节点数量；且对于节点Node_k(1≤k<n),Hash(Node_k)＜Hash(Node_k+1).

如图6所示，数据节点Hash链构造过程，包括如下步骤：

步骤(101)：读取各数据节点的物理地址；

步骤(102)：计算各数据节点Hash值；

步骤(103)：将数据节点按其Hash值从小到大的顺序排序；

步骤(104)：将数据节点的物理地址与其节点Hash值的映射记录依次写入Hash链元数 据表。

如图7所示，HDFS数据块存储过程，包括如下步骤：

步骤(201)：判断所有数据块是否已经存储，如果是就结束；如果否就进入步骤(202)；

步骤(202)：读取一个未存储的数据块；

步骤(203)：计算当前数据块Hash值；

步骤(204)：利用二分查找算法在节点Hash链中查找当前数据块所对应的存储节点；

步骤(205)：将数据块写入此存储节点；

步骤(206)：将数据块及其所对应的存储节点信息写入名字节点。

如图8所示，节点添加时数据迁移的步骤如下：

步骤(301)：对新加入的节点在名字节点进行注册；

步骤(302)：计算新加入数据节点的Hash值；

步骤(303)：二分遍历节点Hash链元数据，找到新节点在Hash链中的插入位置；

步骤(304)：将新节点的物理地址与Hash值的映射记录插入Hash链元数据表中；

步骤(305)：将新节点的后继节点中数据块Hash值小于或等于新节点Hash值的数据块 全部迁移到新节点上；

步骤(306)：在名字节点上对新数据节点及其后继节点的信息进行更新。

如图9所示，节点失效时数据迁移的步骤如下：

步骤(401)：从名字节点中读取失效节点信息；

步骤(402)：计算失效节点的Hash值；

步骤(403)：二分查找节点Hash链，确定失效节点在节点Hash链的位置；

步骤(404)：记录该失效节点的第一个未失效后继节点信息；

步骤(405)：将失效节点的数据块内容从其冗余节点恢复到失效节点的第一个未失效后 继节点上；

步骤(406)：从节点Hash链元数据表中删除失效节点记录；

步骤(407)：从名字节点中删除失效节点信息，并更新恢复节点信息。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限 制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付 出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。