CN101853269B

CN101853269B - 分布数据更新的一致性处理方法

Info

Publication number: CN101853269B
Application number: CN2010101635511A
Authority: CN
Inventors: 彭宇行; 刘锋; 周航军; 张伟; 褚瑞; 李东升; 张一鸣; 陈振邦; 王意洁; 徐传福; 车永刚; 王勇献
Original assignee: National University of Defense Technology
Current assignee: National University of Defense Technology
Priority date: 2010-04-29
Filing date: 2010-04-29
Publication date: 2012-01-11
Anticipated expiration: 2030-04-29
Also published as: CN101853269A

Abstract

分布数据更新的一致性处理方法，针对多副本文件存储中数据更新一致性问题，增加了一个文件的“等待写”状态。更新首先按照副本号顺序进行，将各文件副本从“写打开”或“读/写打开”状态更改为“等待写”状态，当两次接收到“等待写”的更改通知时，所有副本均被设置为“等待写”状态。然后再次按副本号顺序传递“正在写”通知，由各副本所在节点独立完成数据更新，并在更新完成后将对应副本的状态恢复至初始状态。由此，当任一副本进行更新时，其它副本处于“等待写”状态或者更新状态或者更新完毕状态。对处于前两种状态的副本访问时访问被拒绝；对处于后一种状态的副本访问时，将获得更新后的数据。因此本方法能保证数据更新时各文件副本数据访问的一致性。

Description

分布数据更新的一致性处理方法

技术领域

本发明涉及一种分布式文件系统中多副本分布存储的一致性处理方法。

背景技术

文件系统是计算机系统的重要组成部分，负责对文件进行组织和管理。它为程序员提供文件访问接口，包括文件创建、文件打开/关闭、读写指针位移、数据读写等。以UNIX为例，其主要文件操作如下：

创建新文件：filedes＝create(name，mode)

打开文件：filedes＝open(name，mode)

读写指针位移：pos＝lseek(filedes，offset，whence)

读数据：count＝read(filedes，buffer，n)

写数据：count＝write(filedes，buffer，n)

关闭文件：status＝close(filedes)

其中，name表示文件名；mode表示文件存储或打开方式，如“只读”、“只写”、“读写”等；offset表示位移量；whence表示绝对、相对位移；buffer表示缓冲区；n表示读写的字节数。

上述文件接口隐含地提供了访问的透明性操作，即用户程序按照文件名称进行访问，可以不用了解文件数据具体的物理存放位置。

分布文件系统允许用户将数据存放在可控网络的任意计算机上，用相同的操作访问本地和远程文件。其透明性操作也同样包括用户程序只按照文件名称进行访问，不用了解文件数据是放在本地还是放在远程计算机上，也不用了解文件数据具体在计算机上的物理存放位置。

由于分布文件系统能够将异地的存储资源利用起来，因此扩大了存储空间，也使得可以采用诸如多副本存储等技术来增强存储的可靠性、提高访问效率。多副本存储的含义是将同一块数据存储于多个计算机上，这样能带来两个好处：其一，在一个数据损坏时，用户可以服务另一副本，提高可靠性；其二，可以用多个计算机分担数据服务负载，提高服务性能。然而，多个副本的存在，必然造成对多个副本同时进行数据修改时会产生不一致文件副本。

因此，多副本存储与版本一致性存在矛盾，即某一用户改变文件的操作会影响其它用户对该文件的访问。解决多副本一致性的技术比较多，但大多数分布文件系统都遵循现代UNIX标准。针对一致性问题，UNIX文件系统提供了单个拷贝更新语义，即当多个用户同时更新或访问文件时，允许在副本上执行读操作，但写操作必须在同一源文件上执行。为保证源文件与副本文件的一致性，源文件更新后，需要将更新操作发送给副本，在进行副本更新。但是，由于副本更新与源文件更新之间存在延迟，因此，如果某读操作发生在源文件更新后且副本文件更新前的时间段内，则会出现所读内容与源文件最新内容不一致的现象。

发明内容

本发明的技术解决问题是：克服现有技术的不足，提供了一种实时性和一致性好的分布数据更新的一致性处理方法。

本发明的技术解决方案是：分布数据更新的一致性处理方法，步骤如下：

(1)将源文件及其所有副本按照FileCopy1、FileCopy2、...、FileCopyN的方式进行编号，其中N为文件及其副本的总数，FileCopy1为源文件编号；

(2)从正待更新的文件副本FileCopyK开始，按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)的顺序依次传递“等待写”的通知；当文件副本处于“等待写”状态时，禁止任何对该文件副本访问的其它操作；

(3)当文件副本FileCopyK所在节点接收到文件副本FileCopy(K-1)传来的“等待写”的通知后，同样按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)的顺序依次传递“正在写”的通知；当文件副本处于“正在写”状态时，禁止任何对该文件副本访问的其它操作；

(4)当文件副本处于“正在写”状态时，进行数据更新操作；数据更新操作完毕后，将文件副本的状态重新设置回数据更新前的操作状态。

所述的每一个编号为FileCopyK，K＝1、2、...、N的文件所在节点独立执行本节点的处理流程，方法为：当接收到“等待写”通知时，如果本节点所存文件副本处于“写打开”或“读/写打开”状态，则记录文件副本当前状态，并置文件副本状态为“等待写”，同时向下一节点发送“等待写”通知；如果本节点所存文件副本处于“等待写”状态，则置文件副本状态为“正在写”，进行数据更新，同时向下一节点发送“正在写”通知。

本发明与现有技术相比的优点在于：本发明方法克服了现有方法在数据更新时会出现的读数据与最新数据不一致性的现象。现有方法为了避免不同用户对不同副本更新时所造成的“写”不一致性，规定写操作只能在固定的源文件上进行，而读操作可以在所有副本文件上进行。但是，这带来了“读写不一致性”问题，即从副本文件上所读取的内容与源文件上所更新的最新内容不一致。为了避免上述“读写不一致性”，本发明方法在原有的“写打开”、“读/写打开”、“正在写”等文件相关状态的基础上，增加了一个文件“等待写”状态并提出了一个分布式的一致性处理方法。它通过将未更新完的文件设置为“等待写”或“正在写”状态，禁止对其进行“读”操作，并通过将更新完的文件重新设置为“写打开”或“读/写打开”状态，保证了所读取的数据一定是文件更新后的数据。此外，本发明还能够同等看待源文件和副本文件，允许对每一个副本文件进行更新操作，提高了操作的实时性和一致性。

附图说明

图1为本发明方法的流程框图；

图2为本发明实施例中测试系统结构图。

具体实施方式

为解决多副本分布存储更新中的一致性问题，本发明提出了一种称之为DDCW(Distributed Data Consistent Write)的分布数据更新的一致性处理方法。

在传统的文件系统中，文件状态具有“关闭”、“读打开”、“写打开”、“读/写打开”、“正在读”、“正在写”等状态，在文件状态处于“写打开”或“读/写打开”状态下，便可进行文件更新操作。DDCW的基本思想是：文件更新操作中，为避免不同用户同时写一个文件的不同副本带来的不一致性，定义只能从副本号为FileCopy1的文件上，即源文件上，以“写打开”或“读/写打开”方式打开文件；为避免“读”未更新副本带来的所读数据与文件最新数据的不一致性，给文件增加一个“等待写”状态，将对副本FileCopyK的更新操作分解成“分布式为所有文件副本设置‘等待写’状态”、“分布执行所有文件副本的‘写’操作”和“状态恢复”三个步骤：

(1)按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)的顺序将文件副本状态从“写打开”或“读/写打开”更改为“等待写”；在文件副本处于“等待写”状态时，禁止任何对该副本访问的其它操作。

(2)按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)的顺序传递“正在写”通知，每个副本独立地进行文件“写”操作；在文件写操作过程中，禁止任何对该副本访问的其它操作。

(3)每个副本完成数据更新后，独立地将其状态重新设置为“写打开”或“读/写打开”，允许对其进行其它操作。

如图1所示，为本发明方法的流程框图。在执行更新操作前，通过分布式算法将所有文件状态设置为“等待写”，其顺序为：从执行更新操作的副本节点FileCopyK开始，按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)依次传递“等待写”的通知；收到“等待写”通知后，每个节点独立地将文件副本状态从“写打开”或“读/写打开”更改为“等待写”；在文件副本处于“等待写”状态时，禁止任何对该副本访问的其它操作。当存储FileCopyK副本的节点接收到“等待写”的通知时，表明所有副本均被设置为“等待写”状态，此时同样按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)依次传递“正在写”通知；收到“正在写”通知后，每个节点独立地进行文件“写”操作，完成数据更新，并独立地将本节点的副本文件状态重新设置为“写打开”或“读/写打开”；在文件副本处于“正在写”状态时，禁止任何对该副本访问的其它操作。由于数据更新完毕后才将文件状态设置为“写打开”或“读/写打开”，因此保证了此时所访问的数据是更新后的数据，有效避免分布文件系统更新过程中的数据访问不一致现象，亦即保证了各文件副本数据访问的一致性。

本发明方法的主要内容如下：

①存储节点管理

对任一存储节点，若其IP地址为IPAddressK，使用相容哈希函数SHA-1计算IPAddressK，求得SHA-1(name)的值(注：SHA-1是Eastlake.D于2001年提出的一个哈希函数，其功能是“将一个任意字符串映射为一个数值”，如SHA-1(198.10.10.1)＝123，它具有如下性质：对任意两个字符串x、y，SHA-1(x)＝SHA-1(y)的概率极小)。如果对每一个存储节点的IP地址都进行SHA-1计算，则这些节点都分别对应一个不同的SHA-1值。

②创建文件

当使用filedes＝create(name，mode)创建文件时，name、mode分别表示文件名和存储方式，用相容哈希函数SHA-1计算name，如SHA-1(file1.dat)，求得SHA-1(name)的值。根据SHA-1(name)，将新创建的文件存储在节点n上，存储节点的分配原则是：

(1)节点的SHA-1值≥SHA-1(name)。

(2)在所有满足分配原则(1)的存储节点中，n的SHA-1值最小。

根据上述分配原则，任意一个用户，无论他是否是文件的创建者，都可以在节点n上访问到名字为name的文件。

③副本管理

将原始文件及其所有副本文件按照其在网络中的位置顺序编号为FileCopyK，K＝1，2，3...N，N为正整数，其中原始文件的编号为FileCopy1。文件副本的标识符通过哈希其“文件名+副本号”产生，如SHA-1(file1.dat+FileCopy2)。根据这种管理方式，文件创建时的源文件哈希值为SHA-1(name+FileCopy1)。

④元数据管理

描述文件的元信息包括：文件名、副本号、状态、副本总数，如“file1.dat、FileCopy2、WriteOpen、4”。

⑤打开文件

当以“写/读写”方式打开文件时，统一从FileCopy1所在节点打开。当文件已处于“写打开”、“读/写打开”或“正在写”状态时，禁止其它用户用“写打开”或“读/写打开”的方式打开该文件。这样，可以避免两个不同用户同时在不同的节点上以“写/读写”方式打开同一文件的不同副本，避免在同一文件的不同副本上出现“写”不一致现象。

⑥将所有文件副本状态从“写打开”或“读/写打开”转变为“等待写”

对副本号为FileCopyK，K＝1，2，3...N-1，的文件所在节点来说，当它收到一个改变状态为“等待写”的通知后：如果本节点所存文件副本状态为“写打开”或“读/写打开”，则将其状态改变为“等待写”，并将“等待写”的通知发送到副本号为FileCopy(K+1)的文件所在节点(当K＝N时，将“等待写”的通知发送到副本号为FileCopy1的文件所在节点)；如果本节点所存文件副本状态已为“等待写”，则表示所有文件副本的状态均为“等待写”，可以进行“写”操作了。

⑦数据更新

对每一个节点来说，当它处于“等待写”状态且收到一个改变状态为“等待写”或“正在写”的通知后：将文件状态改变为“正在写”；通知下一副本所在节点将状态修改为“正在写”；进行“写”操作；写操作完毕后，将文件状态回置到“写打开”或“读/写打开”。

采用软件实现本发明方法是的流程如下：

[1]打开文件：filedes＝open(name，mode)，这里，open为打开文件命令，name为文件名，mode为打开方式，如“读打开”、“写打开”或“读/写打开”，filedes为打开的文件句柄，以后对filedes的操作即为对该文件的操作

(1)如果本节点不为FileCopy1所在节点，则{

通过SHA-1(name+FileCopy1)定位FileCopy1所在节点nodeK；

将文件打开操作转移到节点nodeK上；

退出

}

(2)如果本节点为FileCopy1所在节点且该文件处于“关闭”状态，则{

以mode方式打开该文件；

用SHA-1(name+FileCopy2)定位FileCopy2所在节点；

通知该节点以mode方式打开文件；

退出

}

(3)如果本节点不为FileCopy1且接到其它节点转来的打开文件通知，则{

以mode方式打开该文件；

如果文件副本号对应的数值不等于副本总数值，则{

用SHA-1定位下一副本号的文件所在节点；

通知该节点以mode方式打开文件

}

退出

}

[2]写数据：count＝write(filedes，buffer，n)，这里，write为写命令，filedes为已打开文件的句柄，buffer为缓冲区，n为写字节数，count为写操作返回的实际所写字节数。

(1)如果文件状态为“写打开”或“读/写打开”，则{

记录文件打开的模式；

将文件状态改为“等待写”；

如果本节点文件副本号所对应数值与副本总数值相对，则{

用SHA-1(name+FileCopy1)定位FileCopy1所在节点nodeK；

}

否则{

用SHA-1定位下一副本文件所在节点nodeK

}

通知nodeK将文件状态改为“等待写”；

退出

}

(2)如果文件状态为“等待写”且收到“等待写”或“正在写”通知，则{

将文件状态改为“正在写”；

如果本节点文件副本号所对应数值与副本总数值相对，则{

用SHA-1(name+FileCopy1)定位FileCopy1所在节点nodeK；

}

否则{

用SHA-1定位下一副本文件所在节点nodeK

}

通知nodeK将文件状态改为“正在写”；

写数据直至写结束；

恢复文件的打开模式；

退出

}

[3]关闭文件：status＝close(filedes)，这里，close为关闭命令，filedes为已打开文件的句柄，status为操作后返回的文件状态。

(1)如果该文件副本号不为FileCopy1，则{

用SHA-1(name+FileCopy1)定位FileCopy1所在节点nodeK；

将文件关闭操作转移到节点nodeK上；

退出

}

(2)如果本节点为FileCopy1所在节点，则{

用SHA-1(name+FileCopy2)定位FileCopy2所在节点；

通知该节点关闭文件；

如果本节点上的文件处于“正在读”或“正在写”状态，则{

等待读完或写完

}

关闭该文件；

退出

}

(3)如果本节点不为FileCopy1且接到其它节点转来的关闭文件通知，则{

如果文件副本号对应的数值不等于副本总数值，则{

通过SHA-1定位下一副本号的文件所在节点nodeK；

通知节点nodeK关闭文件

}

如果本节点上的文件处于“正在读”或“正在写”状态，则{

等待读完或写完

}

关闭该文件；

退出

}

实施例

下面对本发明方法进行测试，测试环境为图2所示的网络环境：由三个管理域组成的广域网；每个管理域由16台服务器组成的局域网构成；域间通过链路损伤仪相连，由链路损伤仪模拟广域网行为。

实验中，将一个10M的文件存储在3个不同域的节点上。以“读/写打开”方式打开。

实验1：启动第一个应用，以“读/写打开”方式打开，结果是“文件被打开”。

实验2：启动第二个应用，同样以“读/写打开”方式打开，结果是“该应用不能打开文件”。

实验3：启动第三个应用，以“只读打开”方式打开，结果是“该应用能够打开文件”。

实验4：在第一个应用中，循环将某个数据写入文件；在第三个应用中，循环从文件中读数据；结果是“第三个应用不能读取数据”。

实验5：停止第一个应用的数据写入；在第三个应用中，继续循环从文件中读数据；结果是“第三个应用能够读取数据”。

实验1、实验2、实验3是对打开文件操作的测试：实验1表明的是正常的打开文件操作；实验2说明了在文件已被写打开后，就不能再对其进行写打开操作了；实验3说明了在文件已被写打开后，还可以对其进行读打开操作。实验4、实验5是对写文件操作的测试：实验4说明了在执行文件写操作过程中，有效屏蔽了对文件的读操作；实验五说明了在写操作完成后，才能执行读操作。上述五个实验中，实验4和实验5是对本发明的测试，它验证了多副本数据更新过程中的读写一致性，即所读数据是更新后的数据；实验1、实验2和实验3虽然不是对本发明的直接测试，但是只有在其能够正确执行的情况下，本发明方法才具有有效执行的基础。

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。

Claims

1.分布数据更新的一致性处理方法，其特征在于步骤如下：

(1)将源文件及其所有副本按照FileCopy1、FileCopy2、...、FileCopyN的方式进行编号，其中N为源文件及其副本的总数，FileCopy1为源文件编号；

(2)通过SHA-1(name+FileCopy1)定位FileCopy1所在节点，从FileCopy1开始按照编号顺序打开所有文件副本，从正待更新的文件副本FileCopyK开始，按照FileCopyK、FileCopy(K+1)、...、FileCopyN、FileCopy1、...、FileCopy(K-1)的顺序依次传递“等待写”的通知；当文件副本处于“等待写”状态时，禁止任何对该文件副本访问的其它操作，其中SHA-1为相容哈希函数，name为文件名，K＝1、2、...、N；

2.根据权利要求1所述的分布数据更新的一致性处理方法，其特征在于：所述的每一个编号为FileCopyK，K＝1、2、...、N的文件所在节点独立执行本节点的处理流程，方法为：当接收到“等待写”通知时，如果本节点所存文件副本处于“写打开”或“读/写打开”状态，则记录文件副本当前状态，并置文件副本状态为“等待写”，同时向下一节点发送“等待写”通知；当接收到“正在写”通知时，如果本节点所存文件副本处于“等待写”状态，则置文件副本状态为“正在写”，进行数据更新，同时向下一节点发送“正在写”通知。