平码五不中公式规律
  • / 22
  • 下载费用:30 金币  

文件系统、数据重复排除方法以及用于文件系统的程序.pdf

关 键 ?#21097;?/dt>
文件系统 数据 重复 排除 方法 以及 用于 程序
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201480081653.5

申请日:

2014.09.11

公开号:

CN106663052A

公开日:

2017.05.10

当前法律状态:

实审

有效性:

审中

法?#19978;?#24773;: 著录事项变更IPC(主分类):G06F 12/00变更事项:申请人变更前:株式会社东芝变更后:株式会社东芝变更事项:地址变更前:日本东京都变更后:日本东京都变更事项:申请人变更前:东芝解决方案株式会社变更后:东芝数?#32440;?#20915;方案株式会社|||实质审查的生效IPC(主分类):G06F 12/00申请日:20140911|||公开
IPC分类号: G06F12/00; G06F3/06 主分类号: G06F12/00
申请人: 株式会社东芝; 东芝解决方案株式会社
发明人: 泽田祥一
地址: 日本东京都
优?#28909;ǎ?/td>
专利代理机构: 永新专利商标代理有限公司 72002 代理人: 徐殿军
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201480081653.5

授权公告号:

||||||

法律状态公告日:

2019.01.04|||2017.06.06|||2017.05.10

法律状态类型:

著录事项变更|||实质审查的生效|||公开

摘要

根据实施方式,文件系统具备散列值计算部、访问控制器以及重复排除控制器。所述散列值计算部计算构成应储存于存储器的文件的至少一个数据块的散列值。所述访问控制器在所述至少一个数据块包括第一数据块、且所述第一数据块的第一高速缓存值已被计算出的情况下,将所述第一散列值用作识别符,向根据所述第一散列值决定的所述存储器的第一位置储存所述第一数据块。所述重复排除控制器在所述第一位置已经储存有有效的数据块的情况下,抑制所述第一数据块向所述第一位置储存的情况。

权利要求书

1.一种文件系统,具备:
散列值计算部,计算构成应储存于存储器的文件的至少一个数据块的散列值;
访问控制器,在所述至少一个数据块包括第一数据块、且所述第一数据块的第一高速
缓存值已被计算出的情况下,该访问控制器将所述第一散列值用作识别符,向根据所述第
一散列值决定的所述存储器的第一位置储存所述第一数据块;以及
重复排除控制器,在所述第一位置已经储存有有效的第二数据块的情况下,抑制所述
第一数据块向所述第一位置储存。
2.根据权利要求1上述的文件系统,其中,
所述访问控制器将所述文件分割成包括所述第一数据块的多个数据块,
所述散列值计算部计算所述多个数据块各自的散列值,
所述重复排除控制器基于是否在根据所述多个数据块各自的计算出的散列值而决定
的所述存储器的位置储存有有效的数据块,判断是否需要进行所述多个数据块各自的重复
排除,
所述访问控制器在判断为不需要进行所述第一数据块的重复排除的情况下,向所述第
一位置储存所述第一数据块。
3.根据权利要求2上述的文件系统,其中,
上述文件系统还具备文件管理部,该文件管理部使用与所述文件建立了对应的i节点
来管理所述文件的所述多个数据块各自所储存的所述存储器的位置,
所述访问控制器在需要进行所述文件的读出的情况下,根据与所述文件建立了对应的
所述i节点而指定所述文件的所述多个数据块各自所储存的所述存储器的位置,由此从所
述存储器读取所述多个数据块。
4.根据权利要求3上述的文件系统,其中,
与所述文件建立了对应的i节点包括记录所述多个数据块各自的计算出的散列值的数
据块表。
5.根据权利要求3上述的文件系统,其中,
所述散列值计算部在从所述第一位置读出所述第一数据块的情况下,计算该读出的第
一数据块的散列值,
所述访问控制器在判断为不需要进行所述第一数据块的所述重复排除的情况下,将包
括所述第一散列值的所述第一数据块的元数据与所述第一数据块的组储存于所述第一位
置,在从所述第一位置读出所述第一数据块,并且计算出该读出的第一数据块的散列值的
情况下,将所述计算出的散列值与所述第一数据块的所述元数据所包括的所述第一散列值
进行比较,由此检测所述第一数据块的读出中的错误。
6.根据权利要求2所述的文件系统,其中,
所述访问控制器在需要将所述第二数据块储存于所述第一位置的情况下,将包括重复
计数的所述第二数据块的元数据与所述第二数据块的组储存于所述第一位置,所述重复计
数用于表示具有与所述第二数据块的散列值相同的散列值的数据块的数,
所述重复排除控制器在判断为需要进行所述第一数据块的所述重复排除的情况下,使
储存于所述第一位置的所述第二数据块的所述元数据中的所述重复计数增加1。
7.根据权利要求6所述的文件系统,其中,
所述文件系统还具备生成储存于所述存储器的各个数据块的拷贝的拷贝控制器,
所述拷贝控制器根据所述第二数据块的所述元数据中的所述重复计数而决定所述第
二数据块的拷贝的数。
8.根据权利要求2所述的文件系统,其中,
所述访问控制器在判断为不需要进行所述第一数据块的所述重复排除的情况下,将包
括重复计数的所述第一数据块的元数据与所述第一数据块的组储存于所述第一位置,该重
复计数用于表示具有与所述第一数据块的散列值相同的散列值的数据块的数。
9.根据权利要求1所述的文件系统,其中,
所述存储器是对象存储器,
所述对象存储器的所述第一位置根据包括所述第一数据块的元数据与所述第一数据
块的组的第一对象的对象识别符而决定,
所述访问控制器将所述第一数据块的所述第一散列值用作所述第一对象的对象识别
符,向根据所述第一对象的所述对象识别符决定的所述对象存储器的所述第一位置储存所
述第一对象。
10.根据权利要求1所述的文件系统,其中,
所述存储器是块存储器,
所述块存储器的指定所述第一位置的第一地址使用所述第一数据块的所述第一散列
值的规定的一部分表示,
所述访问控制器将所述第一数据块的元数据与所述第一数据块的组储存于根据所述
第一地址而指定的所述块存储器的所述第一位置。
11.一种数据重复排除方法,应用于文件系统中,其中,
所述数据重复排除方法包括以下步骤:
计算构成应储存于存储器的文件的至少一个数据块的散列值;
在所述至少一个数据块包括第一数据块、且所述第一数据块的第一高速缓存值已被计
算出的情况下,将所述第一散列值用作识别符,向根据所述第一散列值决定的所述存储器
的第一位置储存所述第一数据块;以及
在所述第一位置已经储存有有效的第二数据块的情况下,抑制所述第一数据块向所述
第一位置储存。
12.一种用于文件系统的程序,用于使计算机执行以下内容:
计算构成应储存于存储器的文件的至少一个数据块的散列值;
在所述至少一个数据块包括第一数据块、且所述第一数据块的第一高速缓存值已被计
算出的情况下,将所述第一散列值用作识别符,向根据所述第一散列值决定的所述存储器
的第一位置储存所述第一数据块;以及
在所述第一位置已经储存有有效的第二数据块的情况下,抑制所述第一数据块向所述
第一位置储存。

说明书

文件系统、数据重复排除方法以及用于文件系统的程序

技术领域

本发明的实施方式涉及文件系统、数据重复排除方法、以及用于文件系统的程序。

背景技术

近年来,要储存于存储装置的数据的量一直增大。因此,要求有效地利用存储装置
的有限的存储容量的技术。作为这样的技术之一,重复排除技术引起关注。根据重复排除技
术,防止相同内容的数据重复储存于存储装置。

重复排除技术一般来说按照执行重复排除的主体的不同而大体分为两种。第一重
复排除技术应用于文件系统,第二重复排除技术应用于存储装置。第一重复排除技术作为
内容一致的文件的全体或一部分记录于存储装置的相同位置的方法而公知。另一方面,第
二重复排除技术作为将内容一致的块并为一体而储存于存储装置内,从不同的访问路径参
照相同的块的方法而公知。

在线技术文献

专利文献

专利文献1:日本特开2009-251725号公报

专利文献2:日本特开2012-93827号公报

发明内容

根据第一重复排除技术,由于重复排除由文件系统执行,因此存储装置不需要用
于进行重复排除的特别功能。另一方面,根据第二重复排除技术,由于重复排除由存储装置
(更详细地说是存储装置的控制器)执行,因此文件系统不需要用于进行重复排除的特别功
能。

但是,在第一重复排除技术中,在文件系统中会产生用于重复排除的开销(日文:
オーバヘッド)。另一方面,在第二重复排除技术中,在存储装置中会产生用于重复排除的开
销。并且,在第二重复排除技术中,为了通过存储装置进行重复的判断而利用文件系统将全
部的数据转送至存储装置,因此数据转送量不会减少。

本发明要解决的课题在于提供能够减少与重复排除相伴的开销与数据转送量的
文件系统、数据重复排除方法、以及用于文件系统的程序。

根据实施方式,文件系统具备散列值计算部、访问控制器以及重复排除控制器。所
述散列值计算部计算构成要储存于存储器的文件的至少一个数据块的散列值。所述访问控
制器在所述至少一个数据块包括第一数据块、并且所述第一数据块的第一高速缓存值已被
计算出的情况下,将所述第一散列值用作识别符,向根据所述第一散列值决定的所述存储
器的第一位置储存所述第一数据块。所述重复排除控制器在所述第一位置已经储存有有效
的第二数据块的情况下,抑制所述第一数据块向所述第一位置储存。

附图说明

图1是示出一个实施方式所涉及的计算机系统的典型结构的框图。

图2是用于对图1所示的文件系统的主要功能的概要进行说明的图。

图3是示出在该实施方式的构成文件的多个块的管理中使用的i节点的构造的例
子的图。

图4是示出该实施方式中应用的块的对象的数据构造例的图。

图5是示出该实施方式中应用的类型为目录的两个i节点的例子的图。

图6是示出该实施方式中应用的文件写入处理的典型顺序的流程图。

图7是示出该实施方式中应用的文件读出处理的典型顺序的流程图。

图8是示出该实施方式中应用的文件删除处理的典型顺序的流程图。

具体实施方式

以下,参照附图说明各种实施方式。

图1是示出一个实施方式所涉及的计算机系统的典型结构的框图。图1所示的计算
机系统包括主计算机(以下,称作主机)10以及存储装置20。在本实施方式中,主机10以及存
储装置20经由网络30而连接。

主机10具备文件系统11以及对象控制器12。在本实施方式中,文件系统11以及对
象控制器12具有包括CPU101、存储器102以及?#38236;?#30828;盘驱动器(HDD)103的共用的硬件结构。
但是,文件系统11以及对象控制器12?#37096;?#20197;分别具有包括CPU、存储器以及?#38236;豀DD的固有
的硬件结构。

CPU101例如分时执行文件系统程序以及对象控制程序,由此作为文件系统11以及
对象控制器12各自的主控制器而发挥功能。文件系统程序以及对象控制程序预先储存于本
地HDD103。在本实施方式中,根据在主机10起动时由CPU101执行的初始程序的装入程序
(IPL),上述的两程序的至少一部分装载于存储器102,由该CPU101使用。在图1中被省略,不
过IPL预先储存于闪存这样的?#19988;资?#24615;存储器。

存储装置20具?#22797;?#20648;器21以及存储器控制器22。在本实施方式中,存储器21由HDD
阵列、例如使用多个HDD构成的RAID(Redundant Arrays of Inexpensive Disks或者
Redundant Arrays of Independent Disks)阵列构成。需要说明的是,存储器21?#37096;?#20197;使
用多个闪存构成的闪存阵列(换句话说,与HDD阵列相比访问速度更高速的闪存阵列)。此
外,存储器21?#37096;?#20197;是由低速存储器(例如,HDD阵列)以及高速存储器(例如,闪存阵列)构
成的层级化存储器。另外,闪存阵列?#37096;?#20197;由与HDD具有互换性的多个固态硬盘(SSD)构成。
此外,存储器21不必一定具有阵列构造。

存储器控制器22接受来自主机10(更详细地说是主机10的对象控制器12)的访问
要求而访问存储器21。存储器控制器22还在存储器21的区域中将被称作block的块作为单
位而进行管理。存储器控制器22?#26500;?#29702;各块的逻辑地址(逻辑块地址)与分配至该逻辑块地
址的物理地?#20998;?#38388;的对应。

接下来,参照图2对图1所示的文件系统11的主要功能进行说明。图2是用于对文件
系统11的主要功能的概要进行说明的图。在本实施方式中,存储装置20的存储器21从文件
系统11作为对象存储器210而被识别。对象存储器210是一种逻辑性的存储器,使用于将数
据(例如,文件的数据)作为对象而储存于单位。在本实施方式中,对象的大小(数据长度)是
可变长度。但是,对象的大小?#37096;?#20197;是固定长度。

图2以要求从主机10上动作的应用程序向文件系统11将文件F储存于对象存储器
210的情况作为前提。在该情况下,文件系统11的主控制器(换句话说,CPU101)将文件F如图
2中箭头A1所示那样分割成多个数据块、例如四个数据块(以下,简称为块)B1、B2、B3以及
B4。在本实施方式中,块B1~B4的大小是固定长度。但是如后所述,块的大小?#37096;?#20197;是可变
长度。

接着,CPU101例如使用SHA-256这样的公知的散列函数HF,如图2中箭头A2所示那
样计算块B1、B2、B3以及至B4各自的散列值H1、H2、H3以及H4。在散列函数HF是SHA-256的情
况下,分别构成散列值H1、H2、H3以及H4的比特数是256。在图2的例子中,散列值H1、H2、H3以
及H4分别是1234、3456、1234以及5628。换句话说,散列值H1以及H3相同。

在此,假设与散列值H1以及H3对应的块B1以及B3的内容不同。在该情况下,若如本
实施方式那样取足够大的构成散列值的比特数,则能够尽可能使块B1以及B3的散列值相同
这种所谓的散列值的冲突的可能性接近零。换句话说,与产生存储装置20的?#25910;?#25110;该存储
装置20内的数据乱码的可能性比较,散列值的冲突的可能性可小到能?#32531;?#30053;。因此,CPU101
在如上所述散列值H1以及H3相同的情况下,判断为块B1以及B3的内容相同,数据重复。

CPU101根据重复判?#31995;?#32467;果,将散列值H1(=H3)、H2以及H4分别用作识别符(ID),
将与H1、H2以及H4各自的ID对应的块B1、B2以及B4如图2中箭头A3(更详细地说是箭头A31、
A32以及A34)所示那样储存于对象存储器210。这样,在块的储存中使用对象存储器的技术
被称作对象存储技术。在对象存储技术中,上述的ID以及块分别作为对象ID以及对象而被
处理。该对象也被称作与块对应的对象、块的对象或者数据对象。本实施方式的特征在于,
CPU101将块的散列值用作指示该块的对象的对象ID。

而且,在上述的块储存中,CPU101为了继续重复排除而将与相同ID(对象ID)对应
的块作为相同对象进行处理。换句话说,CPU101抑制将相同内容的块B1以及B3重复地储存
于对象存储器210。在图2的例子中,块向对象存储器210进行的储存从文件F的最前的块B1
开始。在该情况下,CPU101抑制将块B3向对象存储器210储存。由此,排除对象存储器210内
的块B1以及B3的重复。

接下来,对本实施方式中应用的管理构成文件的块的结构继续说明。在本实施方
式中,各文件按照Linux(注册商标)的虚拟文件系统(VFS)的形式使用i节点进行管理。

图3示出在本实施方式中使用于构成文件Fp的m个块Bq(q=0,1,…,m-1)的管理的
i节点iNp的构造的例子。为了简化说明,各个块Bq的大小是恒定的,例如是4千?#32440;?KB)。i
节点iNp也作为一个对象(换句话说,i节点iNp的对象)进行管理。在图3中,i节点iNp包括数
据块表310。i节点iNp还包括表示文件Fp的属性的属性信息320。文件Fp的属性信息320也被
称作文件Fp的元数据。文件Fp的属性包括该文件Fp的大小、向该文件Fp访问的权限、以及时
间戳。时间戳包括文件Fp最后被访问的时间、文件Fp最后更改的时间、以及做成文件Fp的时
间。

数据块表310使用于记录表示块Bq的位置的信息(以下,称作块位置信息)。在以往
技术中,作为块位置信息而使用块Bq的地址。与此相对,在本实施方式中,作为块位置信息
而使用块Bq的散列值Hq。

因此,在本实施方式中,对于块Bq,将该块Bq的散列值Hq逻辑性地储存于作为对象
ID而唯一确定的对象存储器210的位置。换句话说,在本实施方式中,块Bq的散列值Hq被用
作该块Bq的对象OBq的对象ID。由此,块Bq的对象OBq逻辑性地储存于通过该对象OBq的对象
ID(=该块Bq的散列值Hq)唯一确定的位置。

而且,在本实施方式中,存储器21的物理存储区域的至少一部分(以下,称作物理
卷)以恒定大小的小区域为单位而向由主机10识别的逻辑卷?#25104;洹?#22240;此,存储器控制器22使
用地址管理表来管理逻辑卷内的小区域的逻辑地址(例如,逻辑块地址)与物理卷内的小区
域的物理地?#20998;?#38388;的对应。

另外,在本实施方式中,对象OBq在对象存储器210中的位置向逻辑卷内的小区域
列?#25104;洹?#22914;上所述,该位置由对象OBq的对象ID指示。因此,对象控制器12使用对象管理表来
管理对象OBq的对象ID与逻辑卷内的小区域列的最前小区域的逻辑块地址LBAq之间的对
应。对象管理表例如储存于主机10的?#38236;豀DD103。构成逻辑块地址LBAq的比特数是64。

文件系统11经由对象控制器12如下执行块Bq的对象OBq的读出(或者写入)。首先,
文件系统11将块Bq的散列值Hq用作指示该块Bq的对象OBq的对象ID,向对象控制器12要求
该对象OBq的读出(或者写入)。根据该要求,对象控制器12从根据散列值Hq(对象ID)唯一确
定的对象存储器210的位置(或者位置)逻辑性地读(或者写入)对象OBq。

其中,需要将对象OBq(更详细地说是对象OBq的内容)物理性地被从存储装置20的
存储器21读出(或者写入存储器)。因此,为?#31169;?#34892;该物理性的读出(或者写入),对象控制器
12根据块Bq的对象OBq的对象ID(换句话说是块Bq的散列值Hq)而参照对象管理表。由此,对
象控制器12获取与对象OBq的对象ID对应的逻辑块地址LBAq。?#32531;螅?#23545;象控制器12根据所获
取的逻辑块地址LBAq与对象OBq的大小而向存储装置20的存储器控制器22要求该对象OBq
的内容的读出(或者写入)。

存储器控制器22根据来自对象控制器12的要求而基于逻辑块地址LBAq参照地址
管理表。由此,存储器控制器22获取与逻辑块地址LBAq建立了对应的物理地址。?#32531;螅?#23384;储
器控制器22将利用所获取的物理地址与对象OBq的大小表示的该对象OBq的内容从存储器
21内的位置(或者向位置)读出(或者写入)。在以下的说明中,为?#31169;?#34892;简化而省略关于对
象的物理性的读出或者写入的记载。

在本实施方式中,i节点iNp(更详细地说是i节点iNp的对象)的大小是可变长度。
因此,在本实施方式中,能够将构成文件Fp的全部的块Bq(B0乃至Bm-1)的散列值记录于i节
点iNp的数据块表310。换句话说,在图3中,例如块B0、B1、…、Bm-2、Bm-1各自的散列值H0、
H1、…、Hm-2、Hm-1记录于数据块表310。在该情况下,块B0、B1、…、Bm-2、Bm-1直接储存于将
记录于数据块表310的散列值H0、H1、…、Hm-2、Hm-1作为ID而决定的位置。

需要说明的是,i节点iNp的大小?#37096;?#20197;是固定长度。在此,将构成文件Fp的块Bq的
数记作Np,将能够记录于数据块表310的散列值的数记作Nq。首先,若Np≤Nq,则CPU101能够
使用数据块表310直接管理全部的块Bq。与此相对,若Np>Nq,则CPU101只要使用公知的间
接块管理一部分的块Bq即可。在此,使用间接块IBx管理块Bn以及Bn+1的散列值Hn以及Hn+
1。在该情况下,块Bn以及Bn+1的散列值Hn以及Hn+1记录于间接块IBx,在数据块表310中记
录该间接块IBx的散列值Hx。需要说明的是,在以往技术中,块Bn以及Bn+1的地址记录于间
接块IBx,该间接块IBx的地址记录于数据块表310。

如果在即便使用间接块IBx也无法利用i节点iNp的数据块表310管理全部的块Bq
的情况下,CPU101例如只要利用2段间接块或者3段间接块即可。在该情况下,CPU101在2段
间接块或者3段间接块中不记录下一段的间接块的地址,而是记录下一段的间接块的散列
值。

图4示出本实施方式中应用的上述的块Bq的对象OBq的数据构造例。对象OBq储存
于对象存储器210内的数据区域。在本实施方式中,数据区域分配给文件系统11,由该文件
系统11使用。在主机10具有包括文件系统11的多个文件系统的情况下,数据区域?#37096;?#20197;由
该多个文件系统共享。

需要说明的是,?#37096;?#20197;在对象存储器210内准备多个数据区域,例如第一以及第二
数据区域。在此,第一文件系统(或者第一文件系统的集合)利用第一数据区域,第二文件系
统(或者第二文件系统的集合)利用第二数据区域。另外,应储存于第一数据区域的第一对
象的散列值与已储存于第二数据区域的第二对象的散列值相同。在该情况下,即便是相同
的散列值,第一文件系统(或者各第一文件系统)也将第一对象作为不同于第二对象的其他
对象进行处理。换句话说,即便存在第二对象,第一对象也从重复排除的对象中排除。

另一方面,例如,图3所示的i节点iNp也被称作i节点对象,储存于对象存储器210
内的i节点区域。在本实施方式中,i节点区域被分配给文件系统11,由该文件系统11使用。
在主机10具备包括文件系统11的多个文件系统的情况下,?#37096;?#20197;由该多个文件系统使用各
个单独的i节点区域。

对象OBq包括元数据410与实数据420。对象OBq的实数据420是该对象OBq的实体。
在对象OBq如本实施方式那样与文件Fp的块Bq对应的情况下,实数据420与该块Bq的内容一
致。

另一方面,对象OBq的元数据410表示关于该对象OBq的管理信息,包括重复计数
DCNTq。重复计数DCNTq也被称作参照计数,表示与实数据420一致的块Bq的数。换句话说,重
复计数DCNTq表示具有与实数据420(块Bq)的散列值Hq相同的散列值的块的数。元数据410
还包括表示对象OBq所固有的对象ID、实数据420的大小的信息、以及表示实数据420的储存
位置的地址(例如,逻辑块地址)。对象OBq的对象ID中使用与该对象OBq对应的块Bq的散列
值Hq。

i节点一般分成多个类型。作为i节点的代表类型,已知有文件(更详细地说是通常
文件)以及目录。类型为文件的i节点使用于管理文件。图3所示的i节点iNp的类型是文件。
在以下说明中,也将类型为文件的i节点记作文件i节点,将类型为目录的i节点记作目录i
节点。i节点与该i节点的类型无关系,具有该i节点所固有的i节点编号。i节点(换句话说是
i节点对象)的i节点编号被用作该i节点对象的对象ID。

图5示出本实施方式中应用的类型为目录的i节点500的例子。i节点500的大小与i
节点iNp相同地是可变长度。i节点500也作为一个对象(换句话说是i节点500的对象)进行
管理。因此,i节点500也记作i节点对象500。i节点500例如具有i节点编号iNdn,包括目?#32487;?br />目表(以下称作条目表)510以及属性信息520。条目表510使用于记录i节点500所指示的目
录中包括的全部文件的、i节点编号以及文件名的组。在新制作文件的情况下,该文件所对
应的i节点的i节点编号以及该文件的文件名的组通过文件系统11追加至例如i节点500的
条目表510的空条目。

需要说明的是,文件?#37096;?#20197;不是通常的文件而是目录。在该情况下,将类型为目录
的i节点编号与目录名记录于条目表510。另外,i节点(目录i节点)500的大小?#37096;?#20197;是固定
长度。在该情况下,文件系统11(CPU101将应保持于i节点500的条目表510的i节点编号以及
文件名的组的集合分散记录于其他多个对象,?#37096;?#20197;将该其他多个对象的ID(换句话说是
目?#32487;?#30446;的列表)记录于i节点500。

文件系统11在该文件系统11的管理中利用特别的块。该特别的块也被称作超级
块,在生成文件系统11时生成。超级块使用于记录文件系统11的管理信息(以下,称作文件
系统管理信息),例如,储存于对象存储器210内的i节点区域。超级块也作为对象而被管理。
因此,超级块被分配有特别的对象ID。

文件系统管理信息包括i节点列表信息。i节点列表信息包括与预?#28909;?#20445;在对象存
储器210的i节点区域内的每个i节点的储存位置相关的信息(以下,称作i节点管理信息)。i
节点管理信息包括对应的i节点所固有的i节点编号。文件系统11通过参照文件系统管理信
息所包含的的i节点管理信息,由此能够将目标的i节点编号作为ID而指定所具有的i节点。

接下来,说明本实施方式的动作。首先,对于由文件系统11的CPU101执行的文件写
入处理,参照图6以文件Fp的写入为例进行说明。图6是示出本实施方式中应用的文件写入
处理的典型顺序的流程图。在?#23435;?#20102;简化说明,文件Fp的大小是4KB的整数倍。

现在,要求从在主机10内执行的应用程向文件系统11进行文件Fp的写入。于是,文
件系统11的CPU101开始进行文件写入处理。首先,CPU101作为文件访问控制器而发挥功能,
将文件Fp分割成例如具有4KB的大小的多个块Bq(q=0,1,…)(步骤S1)。多个块Bq例如储存
于存储器102。在此,块Bq的数是m。

接着CPU101将变量q以及Q分别初期设定为0以及m(步骤S2)。变量q表示文件Fp中
的块Bq的相对位置。变量Q表示被分割出的块Bq的数。接着,CPU101从?#38236;豀DD103选择由变
量q(=0)表示的块Bq(第一块),将该被选择的块Bq储存至存储器102的工作区域。?#32531;螅?br />CPU101作为散列值计算部而发挥功能,计算储存于存储器102的工作区域的块Bq的内容的
散列值Hq(步骤S3)。于是,CPU101进入步骤S4。

在步骤S4中,CPU101作为文件管理部而发挥功能,如以下所述那样,将计算出的散
列值Hq记录于具有与文件Fp的文件名建立了对应的i节点编号iNpn的i节点iNp的数据块表
310。首先,CPU101根据文件Fp的文件名参照i节点500a的条目表510a。由此,CPU101获取与
文件Fp的文件名对应的i节点编号iNpn。即,CPU101从i节点500a的条目表510a寻找与文件
Fp的文件名对应的i节点编号iNpn。

接着,CPU101将寻?#19994;?#30340;i节点编号iNpn用作ID,由此从对象存储器210的i节点区
域经由对象控制器12而读出具有该i节点编号iNpn的i节点iNp。CPU101将读出的i节点iNp
储存于存储器102的工作区域。?#32531;螅珻PU101向储存于存储器102的工作区域的i节点iNp的
数据块表310记录块Bq的散列值Hq。

接着,CPU101作为重复排除控制器而发挥功能。?#32531;螅珻PU101将块Bq的散列值Hq用
作对象ID,以如下方式确认具有与该对象ID相同的对象ID的对象OBq的存在(步骤S5)。即,
CPU101将块Bq的散列值Hq用作对象ID,经由对象控制器12从根据该散列值Hq唯一确定的对
象存储器210内的位置执行对象的读出。?#32531;螅珻PU101以在上述的位置储存有有效的对象作
为条件,确?#31995;?#30446;标的对象OBq存在。

接着,CPU101?#38405;?#26631;的对象OBq的确?#31995;?#32467;果进?#20449;?#26029;。即,CPU101判断目标的对
象OBq是否存在于上述的位置(步骤S6)。在此,目标的对象OBq不存在于上述的位置(步骤S6
的No)。换句话说,在根据块Bq的散列值Hq唯一确定的位置(第一位置),不存在与该块Bq相
同内容的有效的块。在该情况下,CPU101判断为,由文件系统11利用的对象存储器210内的
数据区域中储存的块均没有块Bq重复,因此不需要进行与块Bq相关的重复排除。

于是,CPU101再次作为文件访问控制器而发挥功能。?#32531;螅珻PU101将块Bq(第一块)
作为以散列值Hq为对象ID而具有的对象OBq,写入到上述的位置(步骤S7)。该写入通过从
CPU101向对象控制器12要求进行对象OBq的写入而由该对象控制器12执行。

对象OBq如图4所示那样包括元数据410与实数据420。元数据410包括与散列值Hq
一致的对象ID。对象OBq的元数据410还包括值为0(初期值)的重复计数DCNTq。实数据420与
块Bq的内容一致。CPU101在执行步骤S7时作为重复排除控制器而发挥功能,进入步骤S8。

另一方面,与上述的例子不同,目标的对象OBq(更详细地说是具有与块Bq相同内
容的块的对象)存在于上述的位置(步骤S6的Yes)。换句话说,在根据块Bq的散列值Hq唯一
确定的位置,已经存在与该块Bq相同内容的有效的块(第二块)。在该情况下,CPU101判断
为,块Bq与存在于上述的位置的有效的块重复,因此需要进行与块Bq相关的重复排除。因
此,CPU101作为重复排除控制器而发挥功能,为?#31169;?#34892;重复排除而跳过步骤S7,在此之后进
入步骤S8。即,CPU101为?#31169;?#34892;重复排除而抑制块Bq作为对象OBq被写入到上述的位置,进
入步骤S8。

在步骤S8中,CPU101使对象OBq的元数据410中的重复计数DCNTq增加1。由此,若是
判断为不存在目标的对象OBq的情况(步骤S6的No),则重复计数DCNTq从初期值0更新为1。
重复计数DCNTq=1表示与对象OBq的实数据420一致的块Bq的数是1。与此相对,若是判断为
目标的对象OBq存在的情况(步骤S6的Yes),由于重复计数DCNTq是1以?#31995;?#25972;数,因此该重
复计数DCNTq更新为2以?#31995;?#20540;。

接着,CPU101作为文件访问控制器而发挥功能,使变量q增加1(步骤S9)。?#32531;螅?br />CPU101判断为增加1后的变量q与变量Q(=m)相等(步骤S10)。如果增加1后的变量q不与变
量Q相等(步骤S10的No),则CPU101判断为残留应处理的块Bq。在该情况下,CPU101返回步骤
S3。?#32531;螅珻PU101与上述情况相同地执行步骤S3~S10或者步骤S3~S6以及S8~S10。需要说
明的是,在步骤S10中,?#37096;?#20197;判断增加1后的变量q是否为变量Q以上、或者是否超过Q-1。

而且,当CPU101反复进行上述的动作Q(=m)?#38382;保?#22686;加1后的变量q变为与变量Q相
等(步骤S10的Yes)。在该情况下,CPU101判断为未残留应处理的块Bq。于是,CPU101进入步
骤S11。

在步骤S11中,CPU101作为文件管理部而发挥功能,向储存于存储器102的工作区
域的i节点iNp记录文件Fp的新的属性信息320。即CPU101将i节点iNp的旧属性信息320更新
为新的属性信息320。

接着,CPU101将包括新的数据块表310以及属性信息320的新的i节点iNp作为以i
节点编号iNpn为ID而具有的对象OiNp,写入到对象存储器210内的i节点区域(步骤S12)。
即,CPU101将旧i节点iNp(旧对象OiNp)更新为新的i节点iNp(新的对象OiNp)。由此,文件写
入处理结束。需要说明的是,步骤S12中的对象OiNp的写入通过从CPU101向对象控制器12要
求对象OiNp的写入而由该对象控制器12执行。

接下来,对于由文件系统11的CPU101执行的文件读出处理,参照图7以文件Fp的读
出为例进行说明。图7是示出本实施方式中应用的文件读出处理的典型顺序的流程图。

现在,要求从应用程序向文件系统11进行文件Fp的读出。于是文件系统11的
CPU101开始进行文件读出处理。首先,CPU101作为文件访问控制器而发挥功能,将与文件Fp
对应的i节点编号iNpn用作ID,将i节点iNp的对象OiNp从对象存储器210读出(步骤S21)。该
读出通过从CPU101向对象控制器12要求对象OiNp的读出而由该对象控制器12执行。

读出的i节点iNp的对象OiNp储存于存储器102的工作区域。与前述的文件写入处
理相同,CPU101根据文件Fp的文件名,参照i节点500a的条目表510a而获取i节点编号iNpn。

接着,CPU101从读出的对象OiNp所包括的i节点iNp的数据块表310中选择未被选
择的块Bq的散列值Hq(步骤S22)。在此,从数据块表310的第q(=0)个条目选择块Bq的散列
值Hq。

接着,CPU101将所选择的散列值Hq用作对象ID,将块Bq的对象OBq从对象存储器
210读出(步骤S23)。即,CPU101读取将所选择的散列值Hq作为对象ID而具有的对象OBq。读
出的对象OBq储存于存储器102的工作区域。

接着,CPU101判断是否选择了在步骤S21中读出的对象OiNp所包括的i节点iNp的
数据块表310中记录的全部的散列值Hq(步骤S24)。若未被选择的散列值Hq存在于i节点iNp
的数据块表310(步骤S24的No),则CPU101返回步骤S22。?#32531;螅珻PU101与前述情况相同地执
行步骤S22~S24。

而且,对于i节点iNp的数据块表310中记录的全部的散列值Hq,反复执行步骤S22
~S24(步骤S24的Yes)。在该情况下,CPU101进入步骤S25。

在步骤S25中,CPU101作为文件管理部而发挥功能,向储存于存储器102的工作区
域的对象OiNp所包括的i节点iNp记录文件Fp的新的属性信息320。即,CPU101将i节点iNp的
旧属性信息320更新为新的属性信息320。

接着,CPU101将包括新的数据块表310以及属性信息320的新的i节点iNp作为以i
节点编号iNpn为ID而具有的对象OiNp,经由对象控制器12向对象存储器210内的i节点区域
写入(步骤S26)。由此,旧i节点iNp(旧对象OiNp)被更新为新的i节点iNp(新的对象OiNp),
文件读出处理结束。

接下来,对于由文件系统11的CPU101执行的文件删除处理,参照图8以文件Fp的删
除为例进行说明。图8是示出本实施方式中应用的文件删除处理的典型顺序的流程图。

现在,要求从应用程序向文件系统11进行文件Fp的删除。于是,文件系统11的
CPU101开始进行文件删除处理。首先,CPU101作为文件访问控制器而发挥功能,将与文件Fp
对应的i节点编号iNpn用作ID,将i节点iNp的对象OiNp从对象存储器210读出(步骤S31)。读
出的i节点iNp的对象OiNp储存于存储器102的工作区域。

接着,CPU101从读出的对象OiNp所包括的i节点iNp的数据块表310选择出未被选
择的块Bq的散列值Hq(步骤S32)。在此,从数据块表310的第q(=0)个条目选择块Bq的散列
值Hq。

接着,CPU101将所选择的散列值Hq用作对象ID,将块Bq的对象OBq的元数据410从
对象存储器210读出(步骤S33)。读出的对象OBq的元数据410储存于存储器102的工作区域。

接着,CPU101作为文件删除控制器而发挥功能,使步骤S33中读出的对象OBq所包
括的元数据410中的重复计数DCNTq减1(步骤S34)。?#32531;螅珻PU101判断减1后的重复计数
DCNTq是否为0(步骤S35)。

若减1后的重复计数DCNTq等于0(步骤S35的Yes),则CPU101判断为,与对象OBq所
包括的实数据420一致的块Bq的数通过这次的文件Fp的删除而变为零。在该情况下,CPU101
从对象存储器210删除对象OBq(步骤S36)。?#32531;螅珻PU101进入步骤S37。

与此相对,若是减1后的重复计数DCNTq不等于0(步骤S35的No),则CPU101判断为,
与对象OBq所包括的实数据420一致的块Bq的数通过这次的文件Fp的删除也未变为零。在该
情况下,CPU101跳过步骤S36而进入步骤S37。

在步骤S37中,CPU101与上述的文件读出处理中的步骤S24相同,判断是否选择了
所读出的对象OiNp所包括的i节点iNp的数据块表310中记录的全部的散列值Hq。若是未被
选择的散列值Hq存在于i节点iNp的数据块表310(步骤S37的No),则CPU101返回步骤S32。然
后,CPU101与前述情况相同地执行步骤S32~S37、或者步骤S32~35以及S37。

而且,对于记录于i节点iNp的数据块表310的全部的散列值Hq,反复执行步骤S32
~S37、或者步骤S32~35以及S3(步骤S37的Yes)。在该情况下,CPU101从对象存储器210删
除对象OiNp(步骤S38)。需要说明的是,步骤S38中的对象OiNp的删除通过从CPU101向对象
控制器12要求该对象OiNp的删除而由该对象控制器12执行。

接着,CPU101将i节点(目录i节点)500a的i节点编号iNdn用作ID,读出该i节点(i
节点对象)500a(S39)。读出的i节点500a储存于存储器102的工作区域。

接着,CPU101从步骤S39中读出的i节点500a的条目表510a删除i节点编号iNpn与
文件Fp的文件名的组(步骤S40)。CPU101将包括删除i节点编号iNpn与文件Fp的文件名的组
后的条目表510a的i节点500a作为以该i节点500a的i节点编号iNdn为ID而具有的对象,向
对象存储器210内的i节点区域写入(步骤S41)。由此,文件删除处理结束。

接下来,简单说明本实施方式中应用的公知的文件制作处理。现在,要求从主机10
上动作的应用程序向文件系统11重新制作文件Fp。在该情况下,文件系统11的CPU101作为
文件管理部而发挥功能,获取未使用的i节点编号。在此,获取i节点编号iNpn。

接着,CPU101在存储器102的工作区域内制作文件i节点iNp,向该文件i节点iNp记
录文件Fp的属性信息。CPU101将i节点编号iNpn用作ID,将记录有文件Fp的属性信息的文件
i节点iNp写入到对象存储器210的i节点区域。

接着,CPU101将i节点(目录i节点)500a的i节点编号iNdn用作ID,读出该i节点(i
节点对象)500a。CPU101向读出的i节点500a的条目表510追加i节点编号iNpn与文件Fp的文
件名的组。CPU101将包括追加了i节点编号iNpn与文件Fp的文件名的组的条目表510a的i节
点500a作为以i节点编号iNdn为ID而具有的对象,向对象存储器210内的i节点区域写入。由
此,文件作成处理结束。

如上所述,在本实施方式中,文件系统11将根据应写入对象存储器210的块的内容
(换句话说是数据)计算出的该块的散列值用作ID(对象ID),决定(或者指定)该块的位置。
因此,文件系统11例如在需要将块Bq向对象存储器210写入的情况下,将该块Bq的散列值Hq
用作ID而访问上述的位置。只要进行该访问,文件系统11就能简单地判断具有与散列值Hq
相同的ID的块是否已经储存于存储装置20。换句话说,在上述的位置储存有有效的块的情
况下,不必一定为?#31169;?#34892;上述的判断而由文件系统11计算该有效的块的散列值,将该计算
出的散列值与块Bq的散列值Hq比较。

这样,根据本实施方式,在文件系统11侧,表示块Bq的位置的信息只是从现有技术
中的地址变为该块Bq的散列值Hq。因此,能够减少用于重复排除的开销。另外,在存储装置
20侧,存储器控制器22只要根据来自文件系统11侧的要求,将块Bq储存于根据该块Bq的散
列值Hq唯一确定的位置即可,不需要进行重复的判断。

然而,在上述实施方式中,分割文件Fp而得到的Q(=m)块(数据块)Bq的大小是固
定长度。Q个的块Bq各自的大小由该块Bq各自的对象OBq的元数据410所包括的大小信息表
示。因此,Q个的块Bq各自?#37096;?#20197;是可变长度。另外,?#37096;?#20197;将文件Fp以包括与已经储存于对
象存储器210的块的内容相同的内容的块的方式分割成多个块。

在此,多个文件均包括内容相同的连续的多个块、例如两个块Ba以及Bb。在这样的
情况下,块Ba以及Bb的对象OBa以及OBb?#37096;?#20197;并为一个对象OBab。换句话说,块Ba以及Bb也
可以并为一个块Bab。

这样,CPU101作为文件管理部而发挥功能,通过将块的大小设为可变长度而能够
提高重复排除?#30465;?#21478;外,通过集中连续的多个块而能够提高访问性能。

在此,CPU101作为文件访问控制器而发挥功能的结果是,例如将在步骤S22或者
S32中选择的散列值Hq作为ID,读出块Bq的对象OBq(步骤S23或者S33)。在该情况下,CPU101
?#37096;?#20197;计算所读出的对象OBq中的实数据420的散列值、换句话说块Bq的散列值,将计算出
的散列值与选择出的散列值H比较。CPU101根据该比?#31995;?#32467;果而检测块Bq的对象OBq的读出
中的错误。换句话说,CPU101在计算出的散列值不与散列值Hq相等的情况下,判断为因块Bq
的对象OBq的读出而产生错误。根据这样的结构,无需增加计算量就能够实现错误检查。

另外,与上述实施方式不同,存储装置20的存储器21是包括访问性能不同的两种
存储器、例如包括高速存储器以及低速存储器的层级化存储器。在该情况下,对象OBq各自
的元数据410?#37096;?#20197;包括向该对象OBq访问的次数(访问计数)。在这样的结构中,CPU101作
为层级化管理部而发挥功能,?#37096;?#20197;将访问计数例如超过阈值的对象储存于高速存储器,
将访问计数为阈值以下的对象储存于低速存储器。由此,能够根据访问计数(换句话说访问
频率)使各对象层级化。

而且,在对象存储系统中,为了提高可靠性与性能,一般将对象OBq拷贝并记录于
多个存储介质、例如构成存储器21的多个HDD盘。在需要进行这样的对象OBq的拷贝的系统
中,?#37096;?#20197;根据该对象OBq的元数据410中的重复计数DCNTq而决定该对象OBq的拷贝的数。
换句话说,?#37096;?#20197;是,CPU101作为拷贝控制器而发挥功能,越是重复计数DCNTq的值大的对
象OBq,越多地生成该对象OBq的拷贝。这样,能够通过增加重复数多的对象的拷贝数而提高
访问性能。

<变形例>

接着,说明上述实施方式的变形例。在上述实施方式中,存储装置20的存储器21从
文件系统11作为对象存储器210而进行识别。换句话说,上述实施方式以文件系统11具有利
用对象存储器的结构的情况作为前提。因此,主机10需要对象控制器12。与此相对,在本变
形例中,存储装置20的存储器21从文件系统11作为块存储器而进行识别。换句话说,本变形
例以具有文件系统11虽利用块存储器但不利用对象存储的结构的情况作为前提。

在这样的结构中,文件系统11的CPU101需要将块Bq向块存储器储存。在该情况下,
CPU101作为文件访问控制器而发挥功能,只要将与块Bq的对象OBq的元数据410相当的元数
据(以下,称作块管理元数据)与块Bq的内容的组(以下,称作元数据·块组)储存于块存储
器即可。块管理元数据与对象OBq的元数据410相同地包括重复计数DCNTq。块管理元数据还
包括表示块Bq的散列值Hq(=对象OBq的对象ID)、元数据·块组整体的大小SZq的信息。

CPU101为了将包括块Bq的内容的元数据·块组写入块存储器而如以下那样决定
表示该元数据·块组的写入目标的地址、例如逻辑块地址LBAq。在本实施方式中,构成散列
值Hq的比特数是256。另一方面,构成逻辑块地址LBAq的比特数是64。换句话说,散列值Hq的
长度比逻辑块地址LBAq的长度更长。因此,CPU101将散列值Hq的预定的64比特的部分、例如
最前的64比特决定为逻辑块地址LBAq。

CPU101根据决定的逻辑块地址LBAq与元数据·块组的大小SZq而对存储装置20的
存储器控制器22要求该元数据·块组的写入。由此,CPU101能够将元数据·块组向始自逻
辑块地址LBAq的大小为SZq的区域(块存储内的区域)书写。在此,存储器控制器22的动作与
上述实施方式相同。

在本变形例中,散列值Hq的一部分用作逻辑块地址LBAq。因此,存在逻辑块地址
LBAq与根据不同于散列值Hq的散列值Hr而决定的逻辑块地址LBAr一致的可能性。

因此,在具有散列值Hr的元数据·块组已经储存于始自逻辑块地址LBAq(=LBAr)
的区域(以下,称作LBAq区域)的情况下,CPU101执行重新计算块Bq的散列值的动作(所谓的
再散列动作)。具体地说,CPU101根据散列值Hq而计算该散列值Hq的散列值Hq′,将该散列值
Hq′用作块Bq的散列值。需要说明的是,CPU101?#37096;?#20197;使散列值Hq与恒定值(例如1)相加,将
该相加结果用作块Bq的散列值。另外,在已经储存于LBAq区域的元数据·块组具有散列值
Hq的情况下,CPU101判断为需要进行重复排除。在该情况下,CPU101使已经储存于LBAq区域
的元数据·块组的块管理元数据中的重复计数DCNTq增加1。

根据本变形例,在文件系统11所利用的存储器不是对象存储器,而是一般的块存
储器的情况下,关于重复排除,能够实现与利用对象存储器的情况同等的功能。

在上述实施方式中,主机10经由网络30而利用存储装置20。但是,?#37096;?#20197;是包括主
机10的多个主机与网络30连接,该多个主机经由网络30而利用存储装置20。另外,?#37096;?#20197;是
包括存储装置20的多个存储装置与网络30连接,主机10或者多个主机利用多个存储装置。
另外,?#37096;?#20197;是主机10(或者多个主机)经由光纤通道(FC)、串行连接SCSI(SAS)或者串行AT
配件(SATA)这样的网络30以外的连接结构而利用存储装置20(多个存储装置)。

另外,在上述实施方式中,存储器21以及存储器控制器22相对于主机10独立设置。
但是,存储器21以及存储器控制器22?#37096;?#20197;内置于主机10。

另外,前述的文件访问控制器、散列值计算部、文件管理部、重复排除控制器、文件
删除控制器、层级化管理部以及拷贝控制器各自(功能要素)?#37096;?#20197;是文件系统11的CPU101
执行存储器控制程序而实现的软件模块。但是,上述的功能要素的至少一个?#37096;?#20197;由硬件
模块实现。

根据以上说明的至少一个实施方式,能够减少与重复排除相伴的开销与数据转送
量。

虽说明了本发明的几个实施方式,但上述的实施方式仅用于例示,并不意图限定
发明的?#27573;А?#36825;些新的实施方式能够以其他各种方式实施,能够在不脱离发明宗旨的?#27573;?br />内进行各?#36136;?#30053;、替换、变更。这些实施方式或其变形包含于发明的?#27573;?#25110;主旨,并且包含
于权利要求书所记载的发明及其等同的?#27573;А?br />

关于本文
本文标题:文件系统、数据重复排除方法以及用于文件系统的程序.pdf
链接地址:http://www.pqiex.tw/p-6091873.html
关于我们 - 网?#26087;?#26126; - 网?#38236;?#22270; - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 排列五走势图两元网 天津十一选五开奖查询 加拿大卑斯快乐8官网 北京赛车走势图表一比分 银河999游戏下载 晓游休闲棋牌 河南体育彩票 全球股票指数软件 湖南幸运赛车开奖直播 北京pk10前五后五算法