2024年6月12日发(作者：呼浩歌)
(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(21)申请号 CN2.4
(22)申请日 2013.03.29
(71)申请人 株式会社东芝;东芝解决方案株式会社
地址 日本东京都
(72)发明人 山崎修二
(74)专利代理机构 永新专利商标代理有限公司
代理人 王成坤
(51)
G06F12/00
权利要求说明书 说明书 幅图
(10)申请公布号 CN 104246722 A
(43)申请公布日 2014.12.24
(54)发明名称
用于基于哈希表排除数据重复的存
储系统,存储控制器及方法
(57)摘要
根据实施方式，存储控制器具备分
割部、重复管理部以及重复判定部。所述
分割部将由来自主计算机的写入请求所指
定的数据分割成多个大块。所述重复管理
部在第1大块被写入到存储装置的情况
下，将所述第1大块的第1哈希值与所述
第1大块建立对应，并优先地登记到哈希
表的第1表中。所述哈希表包含具有比所
述第1表多的条目的第2表。所述重复判
定部，在计算出第2大块的第2哈希值的
情况下，首先从所述第1表中搜索与所述
第2哈希值一致的第3哈希值。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种存储系统，具备：
存储装置；
存储控制器，控制对所述存储装置的访问；以及
哈希表，包含具有第1数目的条目的第1表及具有比所述第1数目大
所述存储控制器具备：
分割部，将由来自主计算机的写入请求所指定的数据分割成多个大块；
哈希生成部，基于所述多个大块的各自的数据，计算所述多个大块的
访问控制器，对所述存储装置写入大块；
重复管理部，在所述存储装置被写入第1大块的情况下，将所述第1
重复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
大块的第1哈希值与所述第1大块建立对应并优先地登记到所述哈希表的
所述第1表；以及
各自的具有第1长度的哈希值；
的第2数目的条目的第2表，
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希
值的处理，由此判定具有与所述第2大块相同内容的第3大块是否保
所述存储装置， 存于
在判定为所述第3大块保存于所述存储装置的情况下，所述重复管理
2.如权利要求1所述的存储系统，其中，
所述第1表包括多个第1页，该多个第1页是指，用于基于多个哈希
所述多个第1页分别具有第3数目的条目，
所述多个第1页的总条目数与所述第1数目相等，
所述第2表包括与所述多个组索引分别建立了对应的多个第2页，
所述多个第2页分别具有大于所述第3数目的第4数目的条目，
所述多个第2页的总条目数与所述第2数目相等，
所述重复判定部，基于所述第2大块的所述第2哈希值，确定该第2
哈希值属于的组，优先地选择与所述所确定的组的组索引建立了对应的所
述第1页，从所述所选择的第1页中搜索所述第3哈希值，在无法从
所选择的第1页中搜索所述第3哈希值并且至少所述所选择的
述第3数目的条目全部被使用的情况下，选择与所述所
建立了对应的所述第2页，从所述所选择的第2
值将分别具有所述第1长度的该多个哈希值分类为多个组并登记的、分别
与指示所述多个组的多个组索引建立了对应的多个第1页，
部抑制所述第2大块写入所述存储装置。
所述
第1页的所
确定的组的组索引
页中搜索所述第3哈希值，
所述重复管理部，在判定为所述第3大块未保存于所述存储装置的情
3.如权利要求2所述的存储系统，其中，
所述哈希生成部，基于具有所述第1长度的哈希值，计算具有比所述
所述重复判定部，在从所述哈希表中搜索所述第3哈希值的情况下，
4.如权利要求2所述的存储系统，其中，
所述存储控制器还具备易失性的存储器，
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述多个第1页分别包含管理信息，该管理信息包含该第1页内使用
着的条目的数目、与该第1页所属的组的组索引建立了对应的所述第2页
内使用着的条目的数目，
装置，
将基于所述第2哈希值计算的具有所述第2长度的第4哈希值作为对于应
当搜索所述第3哈希值的组进行指定的组索引而使用。
第1长度短的第2长度并且被用作所述组索引的哈希值，
况下，在所述第1页及所述第2页中的、最后被选择的页中登记所述第1
哈希值。
所述重复判定部，在选择了所述第1页的情况下，将该被选择的第1
页载入到所述存储器，从所述被载入的第1页中搜索所述第3哈希值，在
无法从所述被载入的第1页中搜索所述第3哈希值并且由所述被载入
页中包含的所述管理信息所示的所述第2页内使用着的条目的
的情况下，选择所述第2页，将该被选择的第2页载入
所述被载入的第2页
的第1
数目不为零
到所述存储器，从
搜索所述第3哈希值。
5.一种存储控制器，控制对存储装置的访问，在该存储控制器中，具
分割部，将由来自主计算机的写入请求所指定的数据分割成多个大块；
哈希生成部，基于所述多个大块的各自的数据，计算所述多个大块的
访问控制器，对所述存储装置写入大块；
重复管理部，在所述存储装置被写入第1大块的情况下，将所述第1
重复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
大块的第1哈希值与所述第1大块建立对应，并优先地登记到包含第1表
及第2表的哈希表中的所述第1表；以及
各自的具有第1长度的哈希值；
备：
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希
值的处理，由此判定具有与所述第2大块相同内容的第3大块是否保
存于
所述存储装置，
所述重复管理部，在判定为所述第3大块保存于所述存储装置的情况
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述第1表具有第1数目的条目，
所述第2表具有大于所述第1数目的第2数目的条目。
6.一种方法，应用于控制对存储装置的访问的存储控制器，并且用于
将由来自主计算机的写入请求所指定的数据分割成多个大块，
基于所述多个大块的各自的数据，计算所述多个大块的各自的具有第1
在所述存储装置被写入第1大块的情况下，将所述第1大块的第1哈
在计算出第2大块的第2哈希值的情况下，使从所述第1表的搜索优
先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希值的处理，
希值与所述第1大块建立对应，并优先地登记到包含第1表及第2表的哈
希表中的所述第1表，
长度的哈希值，
基于哈希表排除数据的重复，
装置，
下，抑制所述第2大块被写入到所述存储装置，
基于所述搜索的结果来判定具有与所述第2大块相同内容的第3大块
在判定为所述第3大块保存于所述存储装置的情况下，抑制所述第2
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述第1表具有第1数目的条目，
所述第2表具有大于所述第1数目的第2数目的条目。
是否保存于所述存储装置，
大块被写入所述存储装置，
装置，
说 明 书
技术领域
本发明的实施方式涉及用于基于哈希表排除数据重复的存储系
储控制器及方法。
背景技术
近年，为了保存在信息处理系统中处理的大规模的数据（大量数
存储装置的大容量化正在进展。大量数据一般包含较多的重复
为此，在存储装置中保存有大量数据的情况下，该存储装置
一部分被较多的重复的数据所占据。这意味着，存储装
被浪费地使用。因此，为了有效地使用存储装置的受限
需要从应当保存于该存储装置的数据中排除重复的数
以下，对现有技术中应用的排除重复的数据的方法的例子进行叙
储控制器在对存储装置写入数据的情况下，判定与该应当写入
相同的数据是否已被写入到该存储装置。为了进行该判定，存
器将应当写入的数据（文件）分割成被称为大块（chunk）的
的块。
存储控制器针对每个大块、用哈希函数计算哈希值。存储控制器
希值的计算中所用的大块写入存储装置时，将该哈希值与该大
对应并登记到哈希表中。
因此，存储控制器在计算出应当新写入存储装置的第1大块的哈
判定与该哈希值相同的哈希值是否登记于哈希表中。若进一
存储控制器基于相同的哈希值是否登记于哈希表中，
希值时，
在将哈
块建立
述。存
的数据
储控制
据），
的数据。
统、存
的记忆区域的
置的记忆容量
的记忆容量，
据。
固定长的数据
步具体地叙述，
判定与第1大块重复
的数据是否已写入到存储装置。存储控制器仅在
据未被写入的情况下，将该第1大块写入存储装
与第1大块重复的数
置。由此，从存储装置排除
重复的数据。
在写入到存储装置的大块的数目增多时，与这些大块建立对应并
表中登记的哈希值的数目也增多。因此，现有技术为了登记多
值，应用使用具有相同数目条目的多个表并构成为多级的哈希
现有技术文献（专利文献）
专利文献1：日本特开平3-282966号公报
专利文献2：日本特表2012-505440号公报
发明内容
发明要解决的课题
如上所述，在哈希表被用于登记多个哈希值的情况下，保存该哈
需的记忆容量也变大。将这种哈希表整体保存于存储控制器具
储器是困难的。因此，哈希表一般保存于如保存大量数据所用
量的存储装置、或者存储控制器具有的硬盘驱动器（HDD）那
地存储装置。另一方面，现有技术应用利用具有相同数目条目
表并构成为多级的哈希表。
因此，存储控制器为了比较哈希值而对这种结构的哈希表进行搜
况下，在该存储控制器与存储装置之间将产生很多的输入输出
处理。这样，在伴随着用于排除数据重复的哈希值的比较而
在哈希
个哈希
表。
希表所
有的存
的大容
样的本
的多个
索的情
（I/O）
产生很多I/O
处理时，存储装置的写入性能（写入速度）低下。
本发明要解决的课题在于，提供能够使得用于排除数据重复的哈
索高速化的存储系统、存储控制器及方法。
用于解决课题的手段
希表搜
根据实施方式，存储系统具备存储装置、存储控制器以及哈希表。
储控制器控制对所述存储装置的访问。所述哈希表包含具有第
的条目的第1表及具有比所述第1数目大的第2数目的条目的
存储控制器具备分割部、哈希生成部、访问控制器、重
重复判定部。所述分割部将由来自主计算机的写入请求
分割成多个大块。所述哈希生成部基于所述多个大块的
计算所述多个大块的各自的具有第1长度的哈希值。所
附图说明
图1是表示实施方式涉及的计算机系统的典型的硬件结构的框
所述存
1数目
第2表。所述
复管理部以及
所指定的数据
各自的数据，
述访问控制器对所述存储装置写入大块。在所述存储装置被写入第1
大块的情况下，所述重复管理部将所述第1大块的第1哈希值与所述
第1大块建立对应并优先地登记到所述哈希表的所述第1表。所述重
复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3
哈希值的处理，由此判定具有与所述第2大块相同内容的第3大块是
否保存于所述存储装置。所述重复管理部，在判定为所述第3大块保
存于所述存储装置的情况下，抑制所述第2大块被写入所述存储装
置。
图。
图2是以图1所示的存储控制器的典型的功能结构为主进行表示
图3是表示通过来自主计算机的写入请求所指定的文件的数据与
关系的例子的图。
图4是表示图2所示的哈希表的数据结构例的图。
图5是表示图4所示的哈希表所包含的第1级的表具有的叶页的
构例的图。
图6是表示图5所示的管理信息的格式的例子的图。
图7是表示图5所示的其他的管理信息的格式的例子的图。
图8是表示图2所示的元表（Meta Table）的数据结构例的图。
图9是表示图2所示的大块表的数据结构例的图。
图10是表示对同实施方式中的数据写入处理的典型的步骤进行
用的流程图的一部分的图。
图11是表示对同数据写入处理的典型的步骤进行说明所用的流
其他的一部分的图。
图12是表示对同数据写入处理的典型的步骤进行说明所用的流
剩余部分的图。
图13是表示对同实施方式中的哈希值搜索处理的典型的步骤进
的框图。
大块的
数据结
说明所
程图的
程图的
行说明
所用的流程图的一部分的图。
图14是表示对同哈希值搜索处理的典型的步骤进行说明所用的
的剩余部分的图。
图15是表示由从主计算机依次发送的三个文件写入请求所指定
文件与通过该三个文件被每隔恒定的尺寸来划分而取得的大
子的图。
图16是表示哈希表中包含的第1级的表的内容的变化的例子的
图17是表示元表的内容的变化的例子的图。
图18是表示大块表的内容的变化的例子的图。
具体实施方式
以下，参照附图对实施的方式进行说明。
图1是表示实施方式涉及的计算机系统的典型的硬件结构的框
机系统包括存储系统10及主计算机（以下，称为主机
统10经由网络30与主机20连接。
主机20是服务器、或者客户端个人计算机（客户端PC）这样的
算机。在主机20内，用于对存储系统10内的数据进行访问的
按照该应用程序，主机20将存储系统10（更详细而
后述的HDD/SSD阵列11）作为外部记忆装置并
30例如是存储区域网络（SAN）、因特网
流程图
的三个
块的关系的例
图。
图。所述计算
的装置）20。存储系
物理计
应用程序动作。
言，存储系统10的
经由网络30来利用。网络
（Internet）或者内部网
（intranet）。因特网或者内部网例如由以太网
主机20也可以经由光纤通道（FC）、
线、串行SCSI（SAS）总线、或者
那样的主机接口总线与存储系统10
（登记商标）来构成。此外，
小型计算机系统接口（SCSI）总
串行高级技术附件（SATA）总线
连接。
存储系统10包括HDD/SSD阵列11及存储控制器12。在本实施
HDD/SSD阵列11及存储控制器12构成存储装置。HDD/SSD
例如多个硬盘驱动器及多个固态硬盘（SSD）所构成的
存储控制器12经由存储接口总线13来控制对HDD/SSD阵列11
存储控制器12经由网络30与主机20连接。存储控制器12
理通过指定逻辑地址而进行的读出请求或写入请求。存
通过地址转换功能将所指定的逻辑地址转换为物理地
映射了该逻辑地址的HDD/SSD阵列11内的物
况为例更详细地叙述，存储控制器12将
址所指定的数据（大块）的大块编
12将大块编号转换为物理地址，
大块的HDD/SSD阵列11
访问HDD/SSD阵列
存储控制器12包括CPU121、存储器122及硬盘驱动器（HDD）
CPU121按照存储器122内的后述的控制程序区域122a中所保
方式中，
阵列11是用
RAID（Redundant Arrays of Inexpensive Disks或Redundant Arrays of
Independent Disks）阵列。HDD/SSD阵列11经由存储接口总线13与
存储控制器12（更详细而言，存储控制器12的未图示的存储接口）
连接。在本实施方式中，存储接口总线13是FC（光纤通道）。然而，
存储接口总线13也可以是SCSI总线、SAS总线、或者SATA总线那
样的、FC以外的接口总线。
的访问。
从主机20受
储控制器12
址，该物理地址表示
理区域。若以数据读出的情
逻辑地址转换为分配给以该逻辑地
号。关于大块，后述。存储控制器
该物理地址表示保存有该大块编号所示的
内的物理区域。存储控制器12基于该物理地址
11。
123。
存的控制程序
的程序编码，在存储控制器12中执行被请求的处理。
多个DRAM所构成的易失性存储器。HDD123
控制程序及各种表。此外，也能够使用搭
代替HDD123。
存储器122例如是用
是本地存储装置，用于保存
载了多个闪存器的存储装置
在本实施方式中，存储控制器12包括于包含HDD/SSD阵列11
装置。然而，存储控制器12也可以独立于存储装置而被包括。
下，存储控制器12也可以内置于主机20。另外，存储控制器
言，存储控制器12的功能）也可以用主机20具有的操
能的一部分来实现。
另外，存储控制器12也可以包括于在主机20的插件槽中安装并
的卡片。另外，也可以是，存储控制器12的一部分内置于主
另外，也可以应用例如用多个HDD而构成的RAID阵列、或用
SSD而构成的RAID阵列，来代替HDD/SSD阵列11。另外，
具有RAID结构的仅仅多个存储驱动的集合（驱动阵
HDD/SSD阵列11（即RAID阵列）。
图2是以图1所示的存储控制器12的典型的功能结构为主进行
框图。存储控制器12包括分割部200、重复管理部201、重复
哈希生成部203及访问控制器204。关于分割部200、
复判定部202、哈希生成部203及访问控制器204
功能要素200至204是通过由图1所示的存储控
制程序而实现的软件模块。然而，功能要
部也可以通过硬件模块来实现。
的存储
此情况
12（更详细而
作系统（OS）的功
被使用
机20，该存储控制器12的剩余部分包括于所述卡片。
多个
也可以应用不
列），来代替
表示的
判定部202、
重复管理部201、重
的功能，后述。这些
制器12的CPU121执行控
素200至204的一部分或全
存储器122包含控制程序区域122a、表区域122b及工作区域
序区域122a用于保存由CPU121执行的控制程序的至
序如前所述那样、预先保存于HDD123，该控制
制器12的起动时从该HDD123载入到控
表区域122b用于对保存于HDD123的各种表的至少一部分进行
工作区域122c用于保存CPU121执行控制程序时所利用的临
HDD123（即，本地存储装置）除了保存上述的控制程序以外，
后述的哈希表205、元表206及大块表207。即HDD123包含
程序、哈希表205、元表206及大块表207的记忆区域。
图3表示通过来自主机20的写入请求所指定的文件的数据与大
系的例子。分割部200将图3所示的文件分割成固定长、例如
比特）的数据的块。将该每4K比特的数据的块称为大
对每个大块管理重复的有无。在图3的例子中，
此情况下，文件F被分割成N个大块＃
块＃0至＃N-1赋予唯一的识别编号
块编号以8比特表示。
接着，对在HDD123中保存的哈希表205的概要进行说明。哈希
用于对被赋予了大块编号的每个大块登记哈希信息。哈希信息
含基于对应的大块而计算出的32比特的哈希值与该大块的8
号的对。即，哈希表205用于登记哈希信息，该哈希信
希值与该大块的大块编号建立关联的哈希信息。
哈希表205用于由重复判定部202来判定具有与应当写入
122c。控制程
少一部分。该控制程
程序的至少一部分在存储控
制程序区域122a。
保存。
时性的数据。
还保存
分别保存控制
块的关
4千比特（4K
块。重复管理部201
文件F的尺寸为4NK比特。
0至＃N-1。重复管理部201对大
即大块编号。在本实施方式中，大
表205
例如包
比特的大块编
息是指，将大块的哈
HDD/SSD阵
列11的大块相同内容的大块是否已被写入到该
理部201基于该重复判定部202的判定的
块被重复写入到HDD/SSD阵列11。
HDD/SSD阵列11。重复管
结果，排除具有相同内容的多个大
由此，数据的重复排除能够实现。
在此，对本实施方式中应用的数据的重复排除的概要进行说明。
设想从主机20向存储系统10的存储控制器12请求包含大块
入。另外，设大块A的哈希值为H（A）。重复判定部
值H（A）与登记到哈希表205的哈希值依次比
复判定部202判定HDD/SSD阵列11中
大块（以下，称为代表大块A）。
如果哈希表205中登记有与哈希值H（A）一致的哈希值（即，
H（A）），则重复判定部202判定为HDD/SSD阵列11中保存
大块A。即，重复判定部202判定为大块A重复。另一方面，
希表205中未登记有哈希值H（A），则重复判定部202判定
重复。
在判定为大块A不重复的情况下，访问控制器204在由写入请
定的HDD/SSD阵列11的地址中写入大块A。更详细而言，
204将大块A写入到由被分配到来自主机20的写入请求
地址的物理地址所示的HDD/SSD阵列11的物理区域。
理部201将哈希信息登记到哈希表205，该哈希信息包
大块A的大块编号的对。
另一方面，在判定为大块A重复的情况下，重复管理部201抑
控制器204将大块A写入HDD/SSD阵列11。此情况下，重
对由来自主机20的写入请求所指定的逻辑地址分配物
首先，
A的文件的写
202将大块A的哈希
较。基于该比较的结果，重
保存有具有与大块A相同内容的
哈希值
有代表
如果哈
为大块A不
求所指
访问控制器
所指定的逻辑
此时，重复管
含哈希值H（A）与
制访问
复管理部201
理地址，该物理地址是指已在HDD/SSD阵列11中写入代表大块A
的物理地址（即映射）。
图4表示图2所示的哈希表205的数据结构例。哈希表205用多
成为多级。在图4的例子中，哈希表205用7个表TBL_1、
TBL_3、TBL_4、TBL_5、TBL_6及TBL_7构成。即哈希表
构的表。在此，表TBL_h（h＝1，2，3，4、5，6，7）
中的第h级的表。
表TBL_1至TBL_7任一个都包含“kmax＋1”个页（以下，称为
在此，表TBL_h的第k个（k＝0，1，…，kmax）叶页如LP_k
那样标记。叶页LP_k（h）与后述的组G_k（组编号k或组索
对应。叶页LP_k（h）用于登记哈希信息，该哈希信息
G_k的哈希值（更详细而言，后述的第一阶段哈 希值
个表构
TBL_2、
205为7段结
是哈希表205
叶页）。
（h）
引k）建立了
是指，包含属于组
（first stage hash value））与用于确定在该哈希值的计算中所用的
大块编号的对的哈希信息。
表TBL_1至TBL_7的叶页LP_k（1）至LP_k（7）的尺寸不同，
在登记哈希信息中所用的条目的数目也不同。在此，设表
大块的
因此，
TBL_1、
LP_k（1）、
及
TBL_2、TBL_3、TBL_4、TBL_5、TBL_6及TBL_7的叶页
LP_k（2）、LP_k（3）、LP_k（4）、LP_k（5）、LP_k（6）
LP_k（7）的尺寸（条目数）分别为SIZE_1（EN_1）、SIZE_2（EN_2）、
SIZE_1＜SIZE_2＜SIZE_3＜SIZE_4＜SIZE_5＜SIZE_6＜
SIZE_7
SIZE_3（EN_3）、SIZE_4（EN_4）、SIZE_5（EN_5）、SIZE_6（EN_6）
及SIZE_7（EN_7）。此情况下，在这些尺寸（条目数）之间，存在
如下的关系：
EN_1＜EN_2＜EN_3＜EN_4＜EN_5＜EN_6＜EN_7。
即，在本实施方式中，构成哈希表205的7个表TBL_1、TBL_2、
TBL_4、TBL_5、TBL_6及TBL_7具有的叶页LP_k（1）、
LP_k（3）、LP_k（4）、LP_k（5）、LP_k（6）及LP_k（7）
（条目数）中，表TBL_1（即第1级的表TBL_1）的尺寸最
表TBL_2、TBL_3、TBL_4、TBL_5、TBL_6及TBL_7
表TBL_1的各叶页LP_k（1）具有例如96条目。表TBL_2的
LP_k（2）具有例如192条目（即，叶页LP_k（1）的尺寸的
表TBL_3的各叶页LP_k（3）具有例如384条目（即，
的尺寸的2倍的条目）。表TBL_4的各叶页LP_k（4）
条目（叶页LP_k（3）的尺寸的2倍的条目）。表TBL_5
LP_k（5）具有例如1536条目（即，叶页LP_k（4）的尺
目）。表TBL_6的各叶页LP_k（6）具有例如3，072
LP_k（5）的尺寸的2倍的条目）。表TBL_7的各叶
如6，144条目（即，叶页LP_k（6）的尺寸的2
在本实施方式中，哈希表205为了对该哈希表205的访问的高速
从HDD123载入到存储器122的表区域122b中使用。但是，
122的表区域122b的容量的制约，并不是哈希表205整
储器122，而是仅仅从哈希表205选择出的1个叶页被
表区域122b。
在本实施方式中，用32比特的哈希值作为大块（4K比特的大块） 的哈希
化而被
各叶页
的顺序，叶页的尺寸（条目数）变大。
TBL_3、
LP_k（2）、
的尺寸
小。以下，按
2倍的条目）。
叶页LP_k（2）
具有例如768
的各叶页
寸的2倍的条
条目（即，叶页
页LP_k（7）具有例
倍的条目）。
因为存储器
体被载入到存
载入到存储器122的
值。哈希生成部203在计算该32比特的哈希值时，应用例如
256”的第1哈希函数。将该32比特的哈希值称为第一
在此，设在HDD/SSD阵列11中保存的全部大块的第一阶段哈
大块编号的对不被分类就被分散登记到表TBL_1至TBL_7
在表TBL_1～TBL_7中保存的第一阶段哈希值与大
得庞大。为此，从表TBL_h（h＝1，2，3，4、5，
前述的哈希值H（A）一致的哈希值需要很多时
因此，在本实施方式中，重复管理部201基于第一阶段哈希值，
登记到表TBL_1～TBL_7中的该第一阶段哈希值（即，32比
的集合分类为“kmax＋1”个组G_0至G_kmax。组G_0
编号0至kmax建立对应。表TBL_1～TBL_7的
为了重复管理部201进行的上述的分类，哈希生成部203基于第
哈希值生成用于确定该第一阶段哈希值所属的组的作为组编
下，称为组索引）。在本实施方式中，该组索引中使用
哈希值算出的3比特的哈希值。将该3比特的哈希值称
（second stage hash value）。该第二阶段哈希值（即
第2哈希函数。关于该第2哈希函数，后述。
重复管理部201例如将与第二阶段哈希值（组索引）0（＝
被称为“SHA-
阶段哈希值。
希值与
中。此情况下，
块编号的对的数目变
6，7）中搜索例如与
间。
将应当
特的哈希值）
至G_kmax分别与组
各自的“kmax＋1”个叶页与组G_0至G_kmax（即组编号0至kmax）
建立了对应。例如，表TBL_h的叶页LP_0（h）至LP_kmax（h）与
组G_0至G_kmax建立了对应。在此，kmax”例如为16，777，216
（16进制表现时为0xFFFFFF）。0xFFFFFF中的“0x”表示附有该“0x”
的FFFFFF为16进制表现。
一阶段
号的索引（以
基于第一阶段
为第二阶段哈希值
组索引）的计算中用
0x000000）对
应的第一阶段哈希值的集合作为具有组编号0的组G_0
复管理部201将与第二阶段哈希值1（0x000001）
值的集合作为具有组编号1的组G_1来管理，
（0x000002）对应的第一阶段哈希值的集合作
来管理。同样地，重复管理部201将与第
对应的第一阶段哈希值的集合作为
管理。即重复管理部201将与第二
合作为具有组编号k的组
来管理。同样地，重
对应的第一阶段哈希
将与第二阶段哈希值2
为具有组编号2的组G_2
二阶段哈希值kmax（0xFFFFFF）
具有组编号kmax的组G_kmax来
阶段哈希值k对应的第一阶段哈希值的集
G_k来管理。
这样，在本实施方式中，重复管理部201用第二阶段哈希值（即 组索
“kmax引），将对应的第一阶段索引值的集合分类为16，777，216个（即
＋1”个）组。由此，与第一阶段索引值的集合未被组化的情况
将哈希表205中的搜索范围减小为16，777，216分之
在此，对第2哈希函数进行说明。如前所述，第2哈希函数用于
索引的第二阶段哈希值的计算。在本实施方式中，该第2哈希
函数。该除法函数用规定的质数作为除数。具体而言，
用比以3比特表现的最大的数值（16，777，216）小并
在应用了上述的第2哈希函数的情况下，第二阶段哈希值的总数
组索引的总数）为16，777，213（0xFFFFFC）。此情况下，
值“kmax-2”（＝16，777，214）、“kmax-1”（＝16，777，
（＝16，777，216）不存在。然而，在本实施方式中，
重复管理部201也管理分别与第二阶段哈希值
相比较，能够
一。
作为组
函数使用除法
该除数例如使
且最接近该最大的数值的质数（16，777，213）。第二阶段哈希值是
基于除法函数（第2哈希函数），以质数16，777，213除第一阶段哈
希值而取得的余数。除法函数的除数使用这种质数，由此能够将分别
属于组G_0至G_kmax的第一阶段哈希值的集合随机化。
（即，
第二阶段哈希
215）及kmax
为了简化管理，
“kmax-2”、“kmax-1”及
kmax对应的组G_（kmax-2）、G_（kmax-1）
（kmax-2）、G_（kmax-1）及G_kmax未必
及G_kmax。此外，组G_
是必要的。
接着，举例对表TBL_1至TBL_7的各叶页的数据结构进行说明。
示在图4所示的哈希表205中包含的表TBL_1（即第1级的表
的第k个叶页LP_k（1）的数据结构例。叶页LP_k（1）
立了对应。
叶页LP_k（1）包括8个扇区ST_0至ST_7。扇区如周知那样，
硬盘驱动器（HDD）或者固态硬盘（SSD）那样的存储驱动进
时的最小单位。在本实施方式中，1扇区的尺寸为512比特。
ST_7分别包含登记哈希信息时所用的12个条目。因此，
如前所述那样、具有96（8×12＝96）个条目。哈希
40比特。哈希信息包含32比特的哈希值（第一阶
的大块编号的对。扇区ST_0至ST_7进一步包
MI1_7。管理信息MI1_0至MI1_7的各自的尺
理信息MI1_i（i＝0，1，…，i（1）max），
从叶页LP_k（1）具有的扇区的数目中减
表TBL_2至TBL_7具有的第k个叶页LP_k（2）至LP_k（7）
结构也与图5所示的叶页LP_k（1）的数据结构同样。但是，
至LP_k（7）具有的扇区的数目如依据前述的条目数
例如，叶页LP_k（2）、LP_k（3）及LP_k（4）分别具有16扇
的差异所知那样，是不同的。
图5表
TBL_1）具有
与组G_k建
是对如
行访问
扇区ST_0至
叶页LP_k（1）
信息的尺寸例如为
段哈希值）与8比特
含管理信息MI1_0至
寸例如为32比特。关于管
后述。此外，i（1）max是
去1而获得的数，为7。
的数据
叶页LP_k（2）
区
（2）
页
条目）、
（192条目）、32扇区（384条目）及64扇区（768条目）。即，i
max、i（3）max及i（4）max分别为15、31及63。另外，叶
LP_k（5）、LP_k（6）及LP_k（7）分别具有128扇区（1，536
256扇区（3，072条目）及512扇区（6，144条目）。即，i
（6）max及i（7）max分别为128、256及512。
接着，对向如上所述的数据结构的哈希表205登记哈希信息（即
205的更新）的概要进行说明。如前所述，哈希表205包括表
TBL_7。表TBL_1具有基于3比特的第二阶段哈希值
0xFFFFFF（即组索引）而分类的“kmax＋1”个（即16，
叶页LP_0（1）至LP_kmax（1）。
例如在具有第二阶段哈希值0x000000的第1大块被写入到
列11的情况下，重复管理部201在通过该第二阶段哈希
指定的第1级的表TBL_1的叶页LP_0（1）中登记第1
希信息包含第1大块的第一阶段哈希值与该第1
地，例如在具有第二阶段哈希值0x000001
HDD/SSD阵列11的情况下，重复管理部201
0x000001指定的第1级的表TBL_1的叶页
信息。该第2哈希信息包含第2大块的第
编号的对。
第1级的表TBL_1的叶页LP_k（1）（k＝0，1，…，kmax）具
条目（EN_1＝96）。为此，例如在具有第二阶段哈希值0x000000
个大块已被写入到HDD/SSD阵列11的情况下，叶页LP_0（1）
在该状态下，例如无法将上述的第1哈希信息登记到叶页LP_0
中。即，需要增设的叶页。
因此，在本实施方式中，哈希表205进一步包括提供增设的叶页
（5）max、i
哈希表
TBL_1至
0x000000至
777，216个）
HDD/SSD阵
值0x000000
哈希信息。该第1哈
大块的大块编号的对。同样
的第2大块被写入到
在通过该第二阶段哈希值
LP_1（1）中登记第2哈希
一阶段哈希值与该第2大块的大块
有96
的96
充满。
（1）
LP_k
当在第（2）的第2级的表TBL_2。第2级的表TBL_2的叶页LP_k（2）
1级的表TBL_1中叶页LP_k（1）达到充满的情况下使用。 根据该情况，
可以说，表TBL_1（即第1级的表TBL_1）是哈希表
205中的基本的表。
另外，在第1级的表TBL_1的叶页LP_0（1）达到充满的状态
上所述那样，设第1大块（即，具有第二阶段哈希值0x000000
大块）被写入到HDD/SSD阵列11。此情况下，重复管理部
的表TBL_2的叶页LP_0（2）中登记第1哈希信息。第
TBL_2的叶页LP_k（2）（k＝0，1，…，kmax）具有192
＝192）。因此，例如叶页LP_0（2）的192条目也达到
无法在该叶页LP_0（2）中登记新的哈希信息。
因此，哈希表205进一步包括提供增设的叶页LP_k（3）的第3
TBL_3。叶页LP_k（3）当在第2级的表TBL_2中叶页LP_k
满的情况下使用。第3级的表TBL_3的叶页LP_k（3）
（EN_3＝384）。同样地，哈希表205还包括提供增设
第4级的表TBL_4。叶页LP_k（4）当在第3级
（3）达到充满的情况下使用。第4级的表
具有768条目（EN_4＝768）。
同样地，哈希表205还包括提供增设的叶页LP_k（5）的第5级
TBL_5。第5级的表TBL_5的叶页LP_k（5）具有1，536条目
下，如
的第1
201在第2级
2级的表
条目（EN_2
充满的情况下，
级的表
（2）达到充
具有384条目
的叶页LP_k（4）的
的表TBL_3中叶页LP_k
TBL_4的叶页LP_k（4）
的表
（EN_5＝1，536）。同样地，哈希表205还包括提供增设的叶页LP_k
（6）的第6级的表TBL_6、提供增设的叶页LP_k（7）的第7级的
表TBL_7。第6级的表TBL_6的叶页LP_k（6）具有3，072条目（EN_6
＝3，072），第7级的表TBL_7的叶页LP_k（7）具有6，144条目
（EN_6＝6，144）。即，哈希表205针对每个第二阶段哈希值（即组
索引）具有12，192个条目。
在此，对如上所述的哈希表205的结构的意义进行说明。在哈希
中所登记的哈希值的量随着在HDD/SSD阵列11中保存的数
数）变多而增大。在这种状况下，哈希表205所需的记
法在存储器122中保存的大小（例如，超过数
表205如本实施方式那样、保存于HDD123
外，哈希表205也可以保存于HDD/SSD
在哈希表205所需的记忆容量变大时，存储控制器12（更详细
存储控制器12的重复判定部202）为了搜索哈希值，需要重
205的全部条目的一部分读入到存储器122的动作。为
12与存储装置之间，产生较多的输入输出（I/O）
表205
据的量（大块
忆容量一般成为也无
GB的大小）。为此，哈希
（即，本地存储装置）。此
阵列11。
而言，
复将该哈希表
此，在存储控制器
处理。
另外，在一般的存储系统中，以最初分配到逻辑卷的记忆容量（例
小的单位的记忆容量）开始运用。逻辑卷是指，由主机识别为
存储驱动的记忆区域。逻辑卷中，例如每隔4K（千）比特适
HDD/SSD阵列11的记忆区域（物理区域）。这种存储系统具
始后的状况使逻辑卷的记忆容量灵活地增加的功能。本
存储系统10也是同样的。
在这种具有记忆容量增设功能并且具有重复排除功能的存储系
在运用开始时，准备与分配了最小单位的记忆容量的逻辑卷对
准的大小RS的哈希表。并且，在分配给逻辑卷的记忆容量增
位的M倍（M是比1大的整数）的情况下，哈希表也
RS的M倍。
在本实施方式中，能够对逻辑卷分配的记忆容量的最小的单位是
（T）比特。设该6T比特的数据如前所述那样、被分割成4K
当分配
如，最
逻辑的
有根据运用开
实施方式中的
统中，
应的基
加到最小的单
增加到基准的大小
6太拉
比特的大块。
重复管理部201基于各大块的32比特的哈希值（第一阶段哈希
排除具有相同内容的多个大块（即重复的大块）被保存于
列11的情况。此情况下，哈希表205中登记的大块的数
重复后的大块的数目）以一定的可能性不超过16，777，
所周知的。
16，777，216如前所述那样、是在第一阶段哈希值的集合被按
段哈希值来分类的情况下获得的组G_0至G_kmax（组索引）
是与各组G_k（k＝0，1，…，kmax）建立了对应的表
（1）具有的条目的数目（EN_1）。因此，表TBL_1
的逻辑卷的数据的重复排除。即，在逻辑卷的记
情况下，具有16，777，216×96条目的表TBL_1
在此，逻辑卷的记忆容量从例如6T比特增加到12T比特或24T
情况下，仅仅表TBL_1，条目数不足。此情况下，需要将哈希
的大小扩展为基准的大小RS的2倍或4倍。同样地，逻辑卷
例如6T比特增加到516T比特的情况下，需要将哈希
基准的大小RS的86倍。
若是现有技术，则为了进行该扩展，具有基准大小RS的85个
第86的表被追加至具有基准大小R的第1表（即构成运用开
的第1表）。可知，第2至第86的表任一个都具有与第
目数相同数目的条目。第1表用作多级结构的哈希表的
第86的表分别用作多级结构的哈希表的第2级
此情况下，存储控制器为了从第1至第86的表中搜索哈希值， 需要将
第2至
比特的
表205
的大小为上述的基准的大小RS。
第二阶
值），
HDD/SSD阵
目（即，排除
216×96是众
的总数。96
TBL_1的叶页LP_k
能够应用于6T比特
忆容量为6T比特的
的记忆容量从
表205的大小扩展为
始时的哈希表
1表具有的条
第1级的表。第2至
至第86级的表。
该第1至第86的表依次读入到存储器。因此，在现有技术中，
希表，即使使存储器具有用于保存16，777，216×96条目的表
也需要86次I/O处理。
与之相对，在本实施方式中，第1级的表TB_1中被追加第2级
TBL_2至第7级的表TBL_7。第2级的表TBL_2、第3级的表
及第4级的表TBL_4分别具有第1级的表TB_1所具有的条
4倍及8倍的条目。另外，第4级的表TBL_4、第5级
级的表TBL_6分别具有第1级的表TB_1所具有
32倍及64倍的条目。
此情况下，哈希表205的总条目数成为第1级的表TB_1的条目
127倍，充分地超过了支持516T比特的记忆容量的逻辑卷所需
目数（即，第1级的表TB_1的总条目数的86倍）。在应用这
的哈希表205的本实施方式中，存储控制器12在从第1级的
7级的表TBL_7中搜索哈希值的情况下，至多进行7
因此，根据本实施方式，与现有技术相比较，能够大幅削减伴随
值搜索的表访问所需的I/O处理的次数。由此，根据本实施方
而且，在本实施方式中，存储控制器12无需为了搜索哈希值而
级的表TB_1至第7级的表TBL_7的各自的整体读入到存储器
即，存储控制器12仅仅只将包含第1级的表TB_1至第7级的
TBL_7并且与第二阶段哈希值（更详细而言，以第二阶段哈希值
关于哈
区域，
的表
TBL_3
目数的2倍、
的表TBL_5及第6
的条目数的16倍、
数的
的总条
种结构
表TB_1至第
次的I/O处理就结束。
着哈希
式，能够实现哈希值搜索的高速化，能够提高与重复排除有关的处理
能力，进一步能够提高存储系统10的写入性能（写入速度）。
将第1
122。
表
确定的
组）建立了对应的叶页读入到存储器122即可。
并且，在本实施方式中，最大的尺寸的叶页是第7级的TBL_7
LP_k（7）。该叶页LP_k（7）具有6，144个条目。因此，在
方式中，存储控制器12通过上述的I/O处理，最大将具有6，
叶页从存储装置（更详细而言，HDD123）读入到存储
储器122）即可。换言之，存储器122关于哈希
144条目的表区域即可。
因此，根据本实施方式，与现有技术相比，能够大幅减小哈希值
范围。由此，根据本实施方式，能够实现哈希值搜索的进一步
化，能够进一步提高存储系统10的写入性能。
图6表示图5所示的管理信息MI1_0的格式的例子。管理信息
如前所述，被登记于表TBL_1具有的叶页LP_k（1）的开头
管理信息MI1_0包含8个字段F0至F7。字段F0至
2比特。
管理信息MI1_0的字段F0用于设定使用条目计数CNT。使用条
CNT表示在登记管理信息MI1_0（即，包含字段F0的管理信
扇区ST_0中在哈希信息的登记时所使用的条目的数目。
管理信息MI1_0的字段F1至F7用于设定使用条目计数CNT1
用条目计数CNT1至CNT7表示在表TBL_1至TBL_7
LP_k（7）中在哈希信息的登记时所使用的条目
图7表示图5所示的管理信息MI1_i（i＝1，2，…，7）的格式
管理信息MI1_i如前所述那样、被登记到表TBL_1具有的
的叶页
本实施
144个条目的
器（更详细而言，存
表205、仅具有用于保存6，
搜索的
的高速
MI1_0
的扇区ST_0。
F7的各自的长度为
目计数
息MI1_0）的
至CNT7。使
的叶页LP_k（1）至
的数目。
的例子。
叶页LP_k（1）
的扇区ST_i（即，除了扇区ST_0外的扇区）。管理
信息MI1_i包含字段F0。字段F0的长度为2比特。
管理信息MI1_i的字段F0与管理信息MI1_0同样地，在设定使
计数CNT时使用。该使用条目计数CNT表示在登记管理信息
ST_i中在哈希信息的登记时所使用的条目的数目。图7
MI1_i的格式也被应用于在表TBL_2至TBL_7具有
LP_k（7）的全部扇区中登记的管理信息。
图8表示图2所示的元表206的数据结构例。元表206用于对大
管理，该大块是指，被写入到通过按每4K（千）比特划分逻
各区域（4K比特区域）的大块。元表206具有与对逻
区域（更详细而言，在4K比特区域中保存的大
立了对应的条目的集合。
元表206的各条目用于对在与该条目建立了对应的逻辑地址表
区域中保存的大块的大块编号进行登记。即元表206是
4K比特区域的大块而将该4K比特区域的逻辑地
大块编号建立了对应的表。因此，重复管理部
来确定在以目的的逻辑地址所指定的区域
图9表示图2所示的大块表207的数据结构例。大块表207具有
编号建立了对应的条目的集合。大块表207的各条目用于对具
立了对应的大块编号的大块所涉及的大块信息进行登
理地址及参照计数RCNT。
大块表207的各条目具有物理地址字段及参照计数字段。物理地
用于登记物理地址，该物理地址是指，对具有与具有该物理地
用条目
MI1_i的扇区
所示的管理信息
的叶页LP_k（2）至
块进行
辑卷而获得的
辑卷的各个4K比特
块）进行指示的逻辑地址建
示的4K比特
为了表示写入于各
址与分配给该大块的
201能够通过参照元表206
中保存着的大块。
与大块
有与该条目建
记。大块信息包含物
址字段
址字段
的条目（以下，称为对应条目）建立了对应的大块编号的大块
位置进行指示的物理地址。大块的物理位置是指，实际保存有
的HDD/SSD阵列11的记忆区域的位置。
参照计数字段用于登记参照计数RCNT。参照计数RCNT表示以
条目建立了对应的大块编号所确定的大块（以下，称为对应大
几个逻辑地址（4K比特区域）建立了对应。
例如，在参照计数RCNT为“1”的情况下，该参照计数RCNT表
的物理
该大块
与对应
块）与
示对应大块不会成为重复排除的对象而被写入到HDD/SSD阵
换言之，参照计数RCNT表示对应大块仅被写入到逻辑卷内
辑地址所指示的4K比特区域。与之相对，在参照计数RCN
的情况下，该参照计数RCN表示：通过重复排除，虽然在
阵列11中作为实体写入有1个大块，但是该大块与两个逻辑
立了对应。换言之，表示从主机20对逻辑卷内的两个逻辑地
示的4K比特区域写入了具有相同内容的大块。
列11。
的1个逻
为例如“2”
HDD/SSD
地址建
址所指
接着，参照图10至图12对本实施方式的动作进行说明。图10
用于对由存储系统10的存储控制器12从主机20接收到数据
况下执行的数据写入处理的典型的步骤进行说明所用
图。图11是表示用于对同数据写入处理的典型
其他的一部分的图，图12是表示用于对
说明的流程图的剩余部分的图。
这里，设从主机20经由网络30对存储系统10发送了对文件的
行指定的数据写入请求（即，文件写入请求）。并且，设存储
10的存储控制器12接收到来自主机20的文件写入请求。
是表示
写入请求的情
的流程图的一部分的
的步骤进行说明的流程图的
同数据写入处理的典型的步骤进行
写入进
系统
于是，存储控制器12的分割部200例如按每4K比特对以文件
求所指定的文件（即文件数据）进行划分。由此，分割部200
件分割成具有4K比特尺寸的多个大块（步骤S1）。即
指定的文件取得构成该文件的多个大块。此外，
寸为4K比特的情况下，分割部200取得该文件
大块的尺寸无需为固定长。即大块的尺寸
重复管理部201将所取得的大块的数设定为变量N（步骤S2）。
将所取得的N个大块标记为大块C_1至C_N。哈希生成部203
为例如“SHA-256”的第1哈希函数计算大块C_1至C_N的哈
阶段哈希值）H1（C_1）至H1（C_N）（步骤S3）。第
H1（C_1）至H1（C_N）分别以32比特表示。
接着，哈希生成部203用第2哈希函数计算第一阶段哈希值H1
至H1（C_N）的哈希值（即第二阶段哈希值）H2（C_1）至
写入请
将所指定的文
重复管理部201从所
在所指定的文件的尺
本身作为1个大块。在此，
也可以是可变长。
在此，
用被称
希值（即第一
一阶段哈希值
（C_1）
H2（C_N）（步骤S4）。如前所述，第2哈希函数是用质数16，
213作为除数的除法函数。即哈希生成部203将通过以质数16，777，
213除第一阶段哈希值H1（C_1）至H1（C_N）而取得的余数决定
777，
为第二阶段哈希值H2（C_1）至H2（C_N）。
接着，重复管理部201将在指定通过步骤S1取得的N个大块中
大块时所用的变量n设定为初始值1（步骤S5）。然后，重复
201从通过步骤S1取得的N个大块C_1至C_N中选择第n
（步骤S6）。
接着，重复判定部202执行哈希值搜索处理，该哈希值搜索处理
哈希表205搜索与通过重复管理部201所选择的大块C_n的第
哈希值H1（C_n）一致的第一阶段哈希值（步骤S7）。在该哈
的一个
管理部
个大块C_n
用于从
一阶段
希值搜
索处理中，重复判定部202依次比较通过步骤S4计算出的大
二阶段哈希值H2（C_n）和属于建立有对应的组并且被
205的第一阶段哈希值。通过该比较，重复判定部202
值H1（C_n）一致的第一阶段哈希值。该哈希值
重复判定部202基于哈希值搜索处理的结果，判定与所选择的大
的第一阶段哈希值H1（C_n）一致的第一阶段哈希值是否存
205（步骤S8）。重复管理部201基于该重复判定部202
进入到步骤S9或步骤S16。
如果与所选择的大块C_n的第一阶段哈希值H1（C_n）一致的
段哈希值不存在（步骤S8的否），则重复管理部201判定为具
块C_n相同内容的大块未保存于HDD/SSD阵列11。此情况下，
理部201进入到步骤S9。
块C_n的第
登记于哈希表
搜索与第一阶段哈希
搜索处理的详细后述。
块C_n
在于哈希表
的判定的结果，
第一阶
有与大
重复管
在步骤S9中，重复管理部201对大块C_n赋予大块编号CNC_n。
施方式中，赋予时序的大块编号。通过步骤S9对大块C_n赋
CNC_n通过对已赋予其他大块的最新的大块编号加1
HDD123中保存最新的大块编号（或接着应当赋
大块编号从HDD123载入到存储器122的
此外，通过从开头条目起依次参照大块表207的条目，重复管理
也能够取得最新的大块编号。另外，重复管理部201也可以使
当赋予的大块编号建立对应的大块表207的条目进行
重复管理部201能够基于该下一条目指针，决
块编号CNC_n。
在本实
予的大块编号
而获得。为此，例如
予的大块编号）。该最新的
工作区域122c来使用。
部201
用对与接着应
指示的下一条目指针。
定对于大块C_n赋予的大
在对大块C_n赋予大块编号CNC_n时，访问控制器204将该大
写入到HDD/SSD阵列11内的空的记忆区域（步骤S10）。接
部201在与大块C_n的第二阶段哈希值H2（C-n）建立
表205内的叶页LP_k（h）中登记大块C_n的哈希信息
该哈希信息HIC_n包含大块C_n的第一阶段哈
C_n的大块编号的对。
LP_k（h）如后所述那样、表示通过哈希值搜索处理（步骤S7）
索到哈希值的叶页。在此，LP_k（h）中的k表示用作组索引
希值H2（C-n）。另外，LP_k（h）中的h表示叶页LP_k
第h级的表TBL_h。即，表示LP_k（h）是在第h级的
k个叶页。
关于步骤S11的详细，以下进行说明。首先，设最后搜索到哈希
页LP_k（h）的扇区及该扇区的条目分别是该叶页LP_k（h）
ST_i及该第i个扇区ST_i的第j个条目。此情况下，
页LP_k（h）的第i个扇区ST_i内的第j＋1个
信息HIC_n。
另外，重复管理部201使在扇区ST_i中包含的管理信息中的使
计数CNT仅增加1。并且，重复管理部201使在叶页LP_k（1）
的扇区ST_0中包含的管理信息MI1_0中的使用条目计数
1。该管理信息MI1_0如后所述那样、不仅保存于叶页
扇区ST_0，也保存于工作区域122c。
在本实施方式中，在工作区域122c中保存的管理信息MI1_0中
条目计数CNTh增加。在该工作区域122c保存的管理信息
的使用
用条目
的开头
值的叶
最后搜
块C_n
着，重复管理
了对应的哈希
HIC_n（步骤S11）。
希值H1（C-n）及该大块
的第二阶段哈
（h）包含于
表TBL_h包含的第
的第i个扇区
重复判定部202对叶
条目登记大块C_n的哈希
CNTh仅增加
LP_k（1）的开头的
MI1_0在适当
的时机被在HDD123中保存的叶页LP_k（1）的开头的
管理信息MI1_0例如覆盖。适当的时机是指，例如存储
扇区ST_0的
系统10不忙碌的情况或者存储系统10的电源被切断前的时机。
另外，设第i个扇区ST_i的第j个条目是该第i个扇区的最终条
此，i＝11）。此情况下，重复判定部202在叶页LP_k（h）的
1”个扇区ST_（i＋1）内的开头条目中登记大块C_n的哈希信
另外，重复管理部201使在扇区ST_（i＋1）中包含的管理信息
用条目计数CNT仅增加1。并且，重复管理部201使管理信
的使用条目计数CNTh仅增加1。
接着，设最后搜索到哈希值的叶页LP_k（h）内的条目是该叶页
（h）的最终的条目（更详细而言，叶页LP_k（h）的最终的扇
最终的条目）。即，设叶页LP_k（h）的全部条目被使用，该
内没有空条目。此情况下，重复管理部201与上述的
“h+1”级的表TBL_（h+1）中包含的第k个叶页
ST_0（更详细而言，叶页LP_k（h+1）的
的条目）登记大块C_n的哈希信息HIC_n。
另外，重复管理部201使叶页LP_k（h+1）的开头的扇区ST_0
的管理信息中的使用条目计数CNT仅增加1。并且，重复管
理信息MI1_0中的使用条目计数CNT（h+1）仅增加1。
另外，重复管理部201执行步骤S11后进入到步骤S12。在步骤
重复管理部201取得对所选择的大块C_n的逻辑卷内的位置
目（在
第“i＋
息HIC_n。
中的使
息MI1_0中
LP_k
区内的
叶页LP_k（h）
说明不同地、对在第
LP_k（h+1）的开头的扇区
开头的扇区ST_0内的开头
中包含
理部201使管
S12中，
进行表示的逻
辑地址。该逻辑地址通过对由来自主机20的文件写入
（文件的开头地址）加4K（即，4，096）×（n-1）
中重复管理部201进一步在与所取得的逻辑地址
目中登记对所选择的大块C_n赋予的大块
请求指定的逻辑地址
而取得。在步骤S12
建立了对应的元表206的条
编号CNC_n。
重复管理部201执行步骤S12后进入到步骤S13。在步骤S13中，
重复管理部201选择与对所选择的大块C_n赋予的大块编号
了对应的大块表207的条目。在步骤S13中，重复管理
条目中登记所选择的大块C_n所涉及的大块信息
CIC_n包含写入了所选择的大块C_n的HDD/SSD
重复管理部201执行步骤S13后进入到步骤S14。在步骤S14中，
理部201使变量n增加1。并且，重复管理部201判定增加后
超过通过步骤S2所设定的大块数N（步骤S15）。如果
n未超过大块数N（步骤S15的否），则重复管理部201
自主机20的文件写入请求所指定的文件中包含的下一
返回到步骤S6。与之相对，如果增加后的变
S15的是），则重复管理部201判定为结
入请求而指定的文件中包含的全部
至图12的流程图表示的数据写入处
接着，对重复判定部202在步骤S8中判定为与所选择的大块C_n
阶段哈希值H1（C_n）一致的第一阶段哈希值存在的情况的动
说明。这样，在步骤S8的判定为“是”的情况下，重复管理部
有与所选择的大块C_n相同内容的大块已经保存于
在此，将已经保存于HDD/SSD阵列11并且具有
首先，
CNC_n建立
部201还在所选择的
CIC_n。该大块信息
阵列11内的记忆区域的物理地址及参照计数RCN。参照计数RCN
的值为“1”。
重复管
的变量n是否
增加后的变量
为了对在由来
大块的写入进行处理，
量n超过了大块数N（步骤
束了在通过来自主机20的文件写
大块的写入。此情况下，以图10
理结束。
的第一
作进行
201判定为具
HDD/SSD阵列11。
与大块C_n相同内
容的大块标记为大块C_x。
在步骤S8的判定为”是”的情况下，为了排除具有相同内容的多
重复并且被保存于HDD/SSD阵列11的情况，重复管理部201
S16。在步骤S16中，重复管理部201抑制访问控制器204
块C_n写入到HDD/SSD阵列11的动作。
接着，重复管理部201将大块C_x的大块编号作为所选择的大块
大块编号CNC_n，并登记到元表206中（步骤S17）。由此，
206中，相同的大块编号被登记到元表206内的至少两个条目。
理部201为了确定应当登记该大块编号的元表206的条目，通
同样的方法取得对所选择的大块C_n的逻辑卷内的位
址。
个大块
进入到步骤
将所选择的大
C_n的
元表
重复管
过与步骤S12
置进行表示的逻辑地
重复管理部201执行步骤S17后进入到步骤S18。在步骤S18中，
重复管理部201参照在与所选择的大块C_n的大块编号（即，
首先，
大块C_x的大块编号）建立了对应的大块表207的条目中登
块信息CI_Cn。在步骤S18中，重复管理部201还使所参照的
息中的参照计数RCNT增加1。由此，增加后的参照计数
虽然在HDD/SSD阵列11中作为实体写入1个大块，但是具
内容的RCNT个大块被写入到逻辑卷内的RCNT个4K比特区
记着的大
大块信
RCNT表示：
有相同
域。
重复管理部201执行步骤S18后进入到步骤S19。在步骤S19中，
重复管理部201取得对写有大块C_x（即，具有与所选择的大
内容的大块C_x）的HDD/SSD阵列11的记忆区域进行
址。该物理地址包含于通过步骤S18参照的大块信息。
中，重复管理部201进一步将所取得的物理地址分配至所
首先，
块C_n相同
指示的物理地
在步骤S19
选择的大块
C_n的逻辑地址。具体而言，重复管理部201在未图示的
登记对所选择的大块C_n的逻辑地址与所取得的物理
的地址转换信息（即，映射信息）。重复管理部
进入到步骤S14。以后的动作与重复管理部201
的情况相同。
地址转换表中
地址的对应进行表示
201执行步骤S19后
从步骤S13进入到步骤S14
此外，步骤S19未必是必要的。例如，重复管理部201能够如以
那样、不用地址转换表就将由主机20所指定的逻辑地址转换
重复管理部201首先基于由主机20所指定的逻辑地址
取得在与该逻辑地址建立了对应的条目中登记的
复管理部201基于所取得的大块编号参照大块表
建立了对应的条目中登记的物理地址。
接着，参照图13及图14对本实施方式中的哈希值搜索处理（步
的详细进行说明。图13是表示用于对哈希值搜索处理的典型
明的流程图的一部分的图。图13是表示用于对同哈希
步骤进行说明的流程图的剩余部分的图。
首先，重复判定部202将变量h设定为初始值1（步骤S21）。变
示哈希表205内的第h级的表TBL_h。在步骤S21中，重复
将变量k设定为所选择的大块C_n的第二阶段哈希值
表示包含于表TBL_h并且与所选择的大块C_n的
（C_n）建立了对应的第k个叶页LP_k（h）。在
接着，重复判定部202从哈希表205中选择第h级的表TBL_h
下所述
为物理地址。
参照元表206，由此
大块编号。接着，重
207，由此取得在与该大块
骤S7）
的步骤进行说
值搜索处理的典型的
量h表
判定部202还
H2（C_n）。变量k
第二阶段哈希值H2
步骤S21中，重复判定部202进一步将变量i及j任一个都设定为初
始值0。变量i表示在基于变量h及k而确定的叶页LP_k（h）中包
含的第i个扇区ST_i。变量j表示扇区ST_i内的第j个条目。
（步骤S22）。
在变量h为1的本实施方式中，选择第1级的表TBL_1
着，重复判定部202选择包含于所选择的表TBL_h
C_n的第二阶段哈希值H2（C_n）＝k建立了对
（步骤S23）。在此，因为h为1，所以选
LP_k（1）作为叶页LP_k（h）。在步骤S23
作为表TBL_h。接
并且与所选择的大块
应的第k个叶页LP_k（h）
择表TBL_1的第k个叶页
中，重复判定部202从
读出的叶页LP_k（h）保存
部202将所选择的叶页
HDD123读出所选择的叶页LP_k（h），将该
于存储器122的表区域122b。即重复判定
LP_k（h）载入于存储器122的表区域122b。
接着，重复判定部202选择所选择的（所载入的）叶页LP_k（h）
叶页LP_k（1））的第i个扇区ST_i（步骤S24）。在此，作
ST_i，选择开头（第0个）扇区ST_0。
重复判定部202选择了叶页LP_k（1）（即，存储器122的表区
122b中所保存的叶页LP_k（1））的开头的扇区ST_0时，将该扇
ST_0中包含的管理信息MI1_0也保存于例如存储器122的工作区
122c。由此，重复判定部202仅参照管理信息MI1_0中的使用条
CNT2至CNT7，就能够取得表TBL_2至TBL_7的叶页LP_k
（7）内分别使用着的条目的数目。即，重复判定部202
HDD123读出叶页LP_k（2）至LP_k（7）前取得该叶页
LP_k（7）内分别使用着的条目的数目。另外，重复判
管理信息MI1_0中的使用条目计数CNT1，来取
的条目的数目。
因此，重复判定部202能够基于叶页LP_k（1）至LP_k（7）内
用着的条目的数目（即，管理信息MI1_0中的使用条目计数
CNT7），确定使用着的条目的数目为零的叶页。在此，设使
CNT1至CNT4非零，并设使用条目计数CNT5至CNT7
（在此，
为第i个扇区
域
区
域
目计数
（2）至LP_k
能够在从
LP_k（2）至
定部202也能够基于
得叶页LP_k（1）内使用着
分别使
CNT1至
用条目计数
为零。此情况
下，重复判定部202能够决定为充其量将叶页LP_k（1）
至LP_k（4）作为对象进行哈希值搜索即可。将与该叶页有关的最大
的搜索范围标记为hmax。在该例中，hmax为4，表示将叶页LP_k
（1）作为开头的四个叶页为最大的搜索范围。
同样地，重复判定部202能够基于管理信息MI1_0中的使用条
CNTh（h＝1，2，…，7）确定在叶页LP_k（h）中使用着的
例如，叶页LP_k（1）（h＝1）的各扇区的条目的数目
条目计数CNT1（h＝1）为例如16的情况下，重
定为在叶页LP_k（1）中使用着的扇区的数目为
202能够决定为充其量将叶页LP_k（1）
进行哈希值搜索即可。将与该扇区
目计数
扇区的数目。
是12。因此，使用
复判定部202能够确
2。此情况下，重复判定部
内的扇区ST_0及ST_1作为对象
有关的最大的搜索范围标记为
是通过从在叶页LP_k（1）中使用
imax（h，CNT1）。imax（h，CNT1）
着的扇区的数目减去1而获得的值。
重复判定部202执行步骤S24后进入到步骤S25。在步骤S25中，
定部202从所选择的扇区ST_i的第j个条目中读出第一阶段
（C_x）。接着，重复判定部202对所读出的第一阶段哈希
和通过步骤S1计算出的大块C_n的第一阶段哈希值
（步骤S26）。然后，重复判定部202判定第一
第一阶段哈希值H1（C_n）是否相等（步
如果步骤S27的判定为“是”，则重复判定部202取得包含于扇区
的第j个条目并且与第一阶段哈希值H1（C_x）成对的大块编号
S28）。在步骤S27中，重复判定部202将所取得的大块编号
选择的大块C_n相同内容的大块C_x的大块编号，暂
122的工作区域122c。由此，哈希值搜索处理
定部202进入步骤S8。暂时保存于工作区
重复判
哈希值H1
值H1（C_x）
H1（C_n）进行比较
阶段哈希值H1（C_x）与
骤S27）。
ST_i
（步骤
作为具有与所
时保存于例如存储器
（步骤S7）结束，重复判
域122c的大块C_x的大块
编号在步骤S17中使用。
另一方面，如果步骤S27的判定为“否”，则重复判定部202为了
当与第一阶段哈希值H1（C_n）进行比较的下一第一阶段哈希
入到步骤S29。在步骤S29中，重复判定部202使变量j仅增
重复判定部202判定增加后的变量j是否超过变量j的
如果步骤S30的判定为“否”，则重复判定部202进入到步骤S31。
S31中，重复判定部202判定变量j是否超过jmax（CNT）。
是通过使在叶页LP_k（h）的扇区ST_i中包含的管理
条目计数CNT减1而获得的值（即，“CNT-1”）。
示叶页LP_k（h）的扇区ST_i中的条目涉及的
如果变量j超过jmax（CNT）（即“CNT-1”）（步骤S31的是），
判定部202判定为应当与第一阶段哈希值H1（C_n）进行比较
第一阶段哈希值不存在于哈希表205，因此第一阶段哈希值
哈希表205中登记着的全部第一阶段哈希值不一致。此
202使哈希值搜索处理结束。与之相对，如果变
（步骤S31的否），则重复判定部202为了从
ST_i内的下一条目中读出第一阶段哈希值而
另一方面，如果步骤S30的判定为“是”，则重复判定部202使变
加1（步骤S32）。然后，重复判定部202判定增加后的变量i
过变量i的最大值imax（h）（步骤S33）。变量i的最大值imax
在变量h为例如1时为7（8-1＝7），在变量h为例如2时为15
1）。
取得应
值而进
加1。接着，
最大值jmax（步骤S30）。在本实施方式中，变量j的最大值jmax为
11。
在步骤
jmax（CNT）
信息MIh_i中的使用
即，jmax（CNT）表
最大的搜索范围。
则重复
的新的
H1（C_n）与
情况下，重复判定部
量j未超过jmax（CNT）
叶页LP_k（h）的扇区
返回到步骤S25。
量i增
是否超
（h）
（16-
如果步骤S33的判定为“否”，则重复判定部202进入到步骤S34。
S34中，重复判定部202判定变量i是否超过imax（h，CNTh）。
（h，CNTh）是如前所述那样、通过从在叶页LP_k（h）中使用
区的数目减去1而获得的值。
如果变量i超过imax（h，CNTh）（步骤S34的是），则重复判定
判定为应当与第一阶段哈希值H1（C_n）进行比较的新的第一
希值在哈希表205中不存在，因此第一阶段哈希值H1（C_n）
表205中登记着的全部第一阶段哈希值不一致。此情况下，重
使哈希值搜索处理结束。与之相对，如果变量i超过imax
部202
阶段哈
与哈希
在步骤
imax
着的扇
复判定部202
（h，CNTh）（步骤S34的否），则重复判定部202为了选择叶页
（h）（在此，LP_k（1））的下一扇区而返回到步骤S24。 LP_k
另一方面，如果步骤S33的判定为“是”，则重复判定部202使变
增加1（步骤S35）。然后，重复判定部202判定增加后的变量
超过hmax（步骤S36）。hmax如前所述那样、基于叶页LP_k
的开头的扇区ST_0中包含的管理信息MI1_0中的使用条目计
CNT7而决定。
如果步骤S36的判定为“否”，则重复判定部202为了从哈希表
一表及该下一表内的下一叶页而返回到步骤S22。与之
的判定为“是”，则重复判定部202判定为应当与
进行比较的新的第一阶段哈希值在哈希表
段哈希值H1（C_n）与哈希表205中登记
一致。此情况下，重复判定部202使哈希
接着，参照图15至图18，对通过主机20请求的文件写入的例
量h仅
h是否
（1）
数CNT1至
205中选择下
相对，如果步骤S36
第一阶段哈希值H1（C_n）
205中不存在，因此第一阶
着的全部第一阶段哈希值不
值搜索处理结束。
子进行
说明。图15表示由从主机20依次发送的三个文件写入请求所
F0至F2与通过该文件F0至F2被每隔4K比特划分而取
系的例子。图16表示哈希表205中包含的例如第1级
的变化的例子。图17表示元表206的内容的变化
大块表207的内容的变化的例子。
首先，设存储系统10的运用的开始后，从主机20对存储系统
制器12请求将图15（A）所示的16K比特的文件F0写
逻辑地址La0开始的区域。此情况下，存储控制器12
F0分割成四个大块Ca0、Ca1、Ca2及Ca3。应
Ca3的逻辑地址La1、La2及La3分别是La0
12K。大块Ca0、Ca1、Ca2及Ca3分别具有
生成部203计算大块Ca0、Ca1、Ca2及
H（A）、H（B）、H（C）及H（D）。
在此，设具有与大块Ca0、Ca1、Ca2及Ca3相同内容的其他的
存在。此情况下，访问控制器204将大块Ca0、Ca1、Ca2及
重复管理部201将第一阶段哈希值H（A）、H（B）、H（C）及
与大块编号0、1、2及3的各个对例如如图16（A）所示那
TBL_1。此外，在图16（A）中省略，但这些对被登记
H（B）、H（C）、H（D）各自的第二阶段哈希
TBL_1的叶页。
另外，重复管理部201如图17（A）所示那样、在与逻辑地址
指定的文件
得的大块的关
的表TBL_1的内容
的例子。图18表示
10的存储控
入逻辑卷的从
的分割部200将文件
当写入大块Ca1、Ca2及
＋4K、La0＋8K、La0＋
数据A、B、C及D。哈希
Ca3的哈希值（第一阶段哈希值）
大块不
Ca3写入HDD/SSD阵列11的空区域、例如以物理地址Pa0、Pa1、
Pa2及Pa3指定的物理区域。另外，重复管理部201对大块Ca0、Ca1、
Ca2及Ca3赋予例如大块编号0、1、2及3。
H（D）
样、登记到表
到与哈希值H（A）、
值建立了对应的表
La0、La1、
La2及La3分别建立了对应的元表206的条目中登记大块
Ca2及Ca3的大块编号0、1、2及3。另外，重复管理部
（A）所示那样、在与大块Ca0、Ca1、Ca2及Ca3的大块
及3分别建立了对应的大块表207的条目中登记写入有
Ca2及Ca3的物理区域的物理地址Pa0、Pa1、Pa2
管理部201在大块表207中，对与物理地址Pa0、
别成对的参照计数RCNT任一个都设定1。
Ca0、Ca1、
201如图18
编号0、1、2
大块Ca0、Ca1、
及Pa3。另外，重复
Pa1、Pa2及Pa3分
接着，设从主机20对存储控制器12请求将图15（B）所示的12K
文件F1写入逻辑卷的从逻辑地址Lb0开始的区域。此情况下，
制器12的分割部200将文件F1分割为三个大块Cb0、Cb1及
入大块Cb1及Cb2的逻辑地址Lb1及Lb2分别是Lb0
大块Cb0、Cb1及Cb2分别具有数据X、Y及A。
大块Cb0、Cb1及Cb2的哈希值（第一阶段哈希
（A）。
在此，具有与大块Cb0及Cb1相同内容的其他的大块不存在，
与大块Cb2相同内容（A）的大块Ca0存在。此情况下，访问
大块Cb0及Cb1写入HDD/SSD阵列11的空区域、例
及Pb1指定的物理区域。另一方面，关于大块
的重复，重复管理部201抑制访问控制器
块Cb2。另外，重复管理部201对
编号3的大块编号4及5。另
比特的
存储控
Cb2。应当写
＋4K及Lb0＋8K。
哈希生成部203计算
值）H（X）、H（Y）及H
但具有
控制器204将
如通过物理地址Pb0
Cb2，为了排除与大块Ca0
204向HDD/SSD阵列11写入该大
大块Cb0及Cb1赋予后续于最新的大块
外，对具有与
大块Ca0相同内容（A）的大块Cb2的大块编号使用该
号0。
大块Ca0的大块编
重复管理部201例如如图16（B）所示那样、将第一阶段哈希值
及H（Y）与大块编号4及5的各自的对登记到表TBL_1。
H（X）
另外，重复管
理部201如图17（B）所示那样、在与逻辑地址Lb0、
了对应的元表206的条目中登记大块Cb0、Cb1
0。
Lb1及Lb2分别建立
及Cb2的大块编号4、5及
另外，重复管理部201如图18（B）所示那样、在与大块Cb0
块编号4及5分别建立了对应的大块表207的条目中登记
Cb0及Cb1的物理区域的物理地址Pb0及Pb1。另外，
块表207中，对与物理地址Pb0及Pb1分别成对
都设定1。另外，重复管理部201将与具有
的大块Ca0的大块编号0建立了对应的大
RCNT从如图18（A）所示的1更新为如
接着，设从主机20对存储控制器12请求将如图15（C）所示的
特的文件F2写入逻辑卷的从逻辑地址Lc0开始的区域。此情
制器12的分割部200将文件F2分割为三个大块Cc0、
入大块Cc1及Cc2的逻辑地址Lc1及Lc2分别是
8K。大块Cc0、Cc1及Cc2分别具有数据E、F及
接收大块Cc0、Cc1及Cc2的哈希值（第一阶段
及H（A）。
在此，具有与大块Cc0及Cc1相同内容的其他的大块不存在，
与大块Cc2相同内容（A）的大块Ca0存在。此情况下，访问
大块Cc0及Cc1写入HDD/SSD阵列11的空区域、例
及Pc1指定的物理区域。另一方面，关于大块
的重复，重复管理部201抑制访问控制器
块Cc2。另外，重复管理部201对
编号6的大块编号7及8。另
大块Cc2的大块编号中，使
及Cb1的大
写入有大块
重复管理部201在大
的参照计数RCNT任一个
与大块Cb2相同内容（A）
块表207的条目的参照计数
图18（B）所示的2。
12K比
况下，存储控
Cc1及Cc2。应当写
Lc0＋4K及Lc0＋
A。哈希生成部203
哈希值）H（E）、H（F）
但具有
控制器204将
如通过物理地址Pc0
Cc2，为了排除与大块Ca0
204对HDD/SSD阵列11写入该大
大块Cc0及Cc1赋予后续于最新的大块
外，在具有与大块Ca0相同内容（A）的
用该大块Ca0
的大块编号0。
重复管理部201例如如图16（C）所示那样、将第一阶段哈希值
及H（Y）与大块编号6及7的各自的对登记到表TBL_1。另
部201如图17（C）所示那样、在与逻辑地址Lc0、Lc1
建立了对应的元表206的条目中登记大块Cc0、Cc1及
7及0。
另外，重复管理部201如图18（C）所示那样、在与大块Cc0及
大块编号6及7分别建立了对应的大块表207的条目中登记写
及Cc1的物理区域的物理地址Pc0及Pc1。另外，重复
207中，对与物理地址Pc0及Pc1分别成对的参
定1。另外，重复管理部201将与具有与大
块Ca0的大块编号0建立了对应的大块表
RCNT从图18（B）所示的2更新为图18
在此，设从主机20对存储控制器12请求文件F1的删除。此情
重复管理部201如图17（D）所示那样、使与逻辑地址b0、
建立了对应的元表206的三个条目的内容无效化。在图
示无效条目，对相应的条目附以斜线。为了进行
206的各条目的特定的位用作表示该条目的内容是
重复管理部201将与逻辑地址b0、b1及b2分别建立了对应的元
的三个条目内的各自的有效位任一个都设定为表示该条目的
态（例如“0”）。另外，重复管理部201将与构成被删除
大块Cb0、Cb1及Cb2的大块编号4、5及0分别建立了
207的条目内的参照计数RCNT从图18（C）所示的1、
H（E）
外，重复管理
及Lc2分别
Cc2的大块编号6、
Cc1的
入了大块Cc0
管理部201在大块表
照计数RCNT任一个都设
块Cc2相同内容（A）的大
207的条目内的参照计数
（C）所示的3。
况下，
b1及b2分别
17（D）中，为了表
这种无效化，元表
否有效的有效位。
表206
内容无效的状
的文件F1的
对应的大块表
1及3更新为
图18（D）所示的0、0及2。
在本实施方式中，在这种状态下新的大块被写入到HDD/SSD阵
的情况下，对该新的大块赋予通道编号8。此时，被赋予了通
的有效的大块不存在。因此，在本实施方式中，相应于
12的等待时间或者来自主机20的指示，进行碎片消除处
根据以上说明的至少1个实施方式，能够提供能够使得用于排除
复的哈希表搜索高速化的存储系统、存储控制器及方法。
对本发明的几个实施方式进行了说明，但这些实施方式作为例子
无意限定发明的范围。这些新的实施方式能够以其他各种方
脱离发明的主旨的范围内，能够进行各种省略、置换、
施方式及其变形包含于发明的范围及主旨，并且包含于
记载的发明及其等同的范围。
列11
道编号4及5
存储控制器
理（碎片整理处理；defragmentation）。即，在HDD/SSD阵列11中
保存的有效的大块按照例如每个文件、在该HDD/SSD阵列11的物
理地址连续的区域被进行再配置。此时，对有效的全部大块重新赋予
连续的通道编号。与之相应，哈希表205、元表206及大块表207也
得以更新。
数据重
来提示，
式实施，在不
变更。这些实
与权利要求书
2024年6月12日发(作者：呼浩歌)
(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(21)申请号 CN2.4
(22)申请日 2013.03.29
(71)申请人 株式会社东芝;东芝解决方案株式会社
地址 日本东京都
(72)发明人 山崎修二
(74)专利代理机构 永新专利商标代理有限公司
代理人 王成坤
(51)
G06F12/00
权利要求说明书 说明书 幅图
(10)申请公布号 CN 104246722 A
(43)申请公布日 2014.12.24
(54)发明名称
用于基于哈希表排除数据重复的存
储系统,存储控制器及方法
(57)摘要
根据实施方式，存储控制器具备分
割部、重复管理部以及重复判定部。所述
分割部将由来自主计算机的写入请求所指
定的数据分割成多个大块。所述重复管理
部在第1大块被写入到存储装置的情况
下，将所述第1大块的第1哈希值与所述
第1大块建立对应，并优先地登记到哈希
表的第1表中。所述哈希表包含具有比所
述第1表多的条目的第2表。所述重复判
定部，在计算出第2大块的第2哈希值的
情况下，首先从所述第1表中搜索与所述
第2哈希值一致的第3哈希值。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种存储系统，具备：
存储装置；
存储控制器，控制对所述存储装置的访问；以及
哈希表，包含具有第1数目的条目的第1表及具有比所述第1数目大
所述存储控制器具备：
分割部，将由来自主计算机的写入请求所指定的数据分割成多个大块；
哈希生成部，基于所述多个大块的各自的数据，计算所述多个大块的
访问控制器，对所述存储装置写入大块；
重复管理部，在所述存储装置被写入第1大块的情况下，将所述第1
重复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
大块的第1哈希值与所述第1大块建立对应并优先地登记到所述哈希表的
所述第1表；以及
各自的具有第1长度的哈希值；
的第2数目的条目的第2表，
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希
值的处理，由此判定具有与所述第2大块相同内容的第3大块是否保
所述存储装置， 存于
在判定为所述第3大块保存于所述存储装置的情况下，所述重复管理
2.如权利要求1所述的存储系统，其中，
所述第1表包括多个第1页，该多个第1页是指，用于基于多个哈希
所述多个第1页分别具有第3数目的条目，
所述多个第1页的总条目数与所述第1数目相等，
所述第2表包括与所述多个组索引分别建立了对应的多个第2页，
所述多个第2页分别具有大于所述第3数目的第4数目的条目，
所述多个第2页的总条目数与所述第2数目相等，
所述重复判定部，基于所述第2大块的所述第2哈希值，确定该第2
哈希值属于的组，优先地选择与所述所确定的组的组索引建立了对应的所
述第1页，从所述所选择的第1页中搜索所述第3哈希值，在无法从
所选择的第1页中搜索所述第3哈希值并且至少所述所选择的
述第3数目的条目全部被使用的情况下，选择与所述所
建立了对应的所述第2页，从所述所选择的第2
值将分别具有所述第1长度的该多个哈希值分类为多个组并登记的、分别
与指示所述多个组的多个组索引建立了对应的多个第1页，
部抑制所述第2大块写入所述存储装置。
所述
第1页的所
确定的组的组索引
页中搜索所述第3哈希值，
所述重复管理部，在判定为所述第3大块未保存于所述存储装置的情
3.如权利要求2所述的存储系统，其中，
所述哈希生成部，基于具有所述第1长度的哈希值，计算具有比所述
所述重复判定部，在从所述哈希表中搜索所述第3哈希值的情况下，
4.如权利要求2所述的存储系统，其中，
所述存储控制器还具备易失性的存储器，
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述多个第1页分别包含管理信息，该管理信息包含该第1页内使用
着的条目的数目、与该第1页所属的组的组索引建立了对应的所述第2页
内使用着的条目的数目，
装置，
将基于所述第2哈希值计算的具有所述第2长度的第4哈希值作为对于应
当搜索所述第3哈希值的组进行指定的组索引而使用。
第1长度短的第2长度并且被用作所述组索引的哈希值，
况下，在所述第1页及所述第2页中的、最后被选择的页中登记所述第1
哈希值。
所述重复判定部，在选择了所述第1页的情况下，将该被选择的第1
页载入到所述存储器，从所述被载入的第1页中搜索所述第3哈希值，在
无法从所述被载入的第1页中搜索所述第3哈希值并且由所述被载入
页中包含的所述管理信息所示的所述第2页内使用着的条目的
的情况下，选择所述第2页，将该被选择的第2页载入
所述被载入的第2页
的第1
数目不为零
到所述存储器，从
搜索所述第3哈希值。
5.一种存储控制器，控制对存储装置的访问，在该存储控制器中，具
分割部，将由来自主计算机的写入请求所指定的数据分割成多个大块；
哈希生成部，基于所述多个大块的各自的数据，计算所述多个大块的
访问控制器，对所述存储装置写入大块；
重复管理部，在所述存储装置被写入第1大块的情况下，将所述第1
重复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
大块的第1哈希值与所述第1大块建立对应，并优先地登记到包含第1表
及第2表的哈希表中的所述第1表；以及
各自的具有第1长度的哈希值；
备：
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希
值的处理，由此判定具有与所述第2大块相同内容的第3大块是否保
存于
所述存储装置，
所述重复管理部，在判定为所述第3大块保存于所述存储装置的情况
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述第1表具有第1数目的条目，
所述第2表具有大于所述第1数目的第2数目的条目。
6.一种方法，应用于控制对存储装置的访问的存储控制器，并且用于
将由来自主计算机的写入请求所指定的数据分割成多个大块，
基于所述多个大块的各自的数据，计算所述多个大块的各自的具有第1
在所述存储装置被写入第1大块的情况下，将所述第1大块的第1哈
在计算出第2大块的第2哈希值的情况下，使从所述第1表的搜索优
先来执行从所述哈希表搜索与所述第2哈希值一致的第3哈希值的处理，
希值与所述第1大块建立对应，并优先地登记到包含第1表及第2表的哈
希表中的所述第1表，
长度的哈希值，
基于哈希表排除数据的重复，
装置，
下，抑制所述第2大块被写入到所述存储装置，
基于所述搜索的结果来判定具有与所述第2大块相同内容的第3大块
在判定为所述第3大块保存于所述存储装置的情况下，抑制所述第2
所述哈希表保存于所述存储装置、或所述存储控制器具有的本地存储
所述第1表具有第1数目的条目，
所述第2表具有大于所述第1数目的第2数目的条目。
是否保存于所述存储装置，
大块被写入所述存储装置，
装置，
说 明 书
技术领域
本发明的实施方式涉及用于基于哈希表排除数据重复的存储系
储控制器及方法。
背景技术
近年，为了保存在信息处理系统中处理的大规模的数据（大量数
存储装置的大容量化正在进展。大量数据一般包含较多的重复
为此，在存储装置中保存有大量数据的情况下，该存储装置
一部分被较多的重复的数据所占据。这意味着，存储装
被浪费地使用。因此，为了有效地使用存储装置的受限
需要从应当保存于该存储装置的数据中排除重复的数
以下，对现有技术中应用的排除重复的数据的方法的例子进行叙
储控制器在对存储装置写入数据的情况下，判定与该应当写入
相同的数据是否已被写入到该存储装置。为了进行该判定，存
器将应当写入的数据（文件）分割成被称为大块（chunk）的
的块。
存储控制器针对每个大块、用哈希函数计算哈希值。存储控制器
希值的计算中所用的大块写入存储装置时，将该哈希值与该大
对应并登记到哈希表中。
因此，存储控制器在计算出应当新写入存储装置的第1大块的哈
判定与该哈希值相同的哈希值是否登记于哈希表中。若进一
存储控制器基于相同的哈希值是否登记于哈希表中，
希值时，
在将哈
块建立
述。存
的数据
储控制
据），
的数据。
统、存
的记忆区域的
置的记忆容量
的记忆容量，
据。
固定长的数据
步具体地叙述，
判定与第1大块重复
的数据是否已写入到存储装置。存储控制器仅在
据未被写入的情况下，将该第1大块写入存储装
与第1大块重复的数
置。由此，从存储装置排除
重复的数据。
在写入到存储装置的大块的数目增多时，与这些大块建立对应并
表中登记的哈希值的数目也增多。因此，现有技术为了登记多
值，应用使用具有相同数目条目的多个表并构成为多级的哈希
现有技术文献（专利文献）
专利文献1：日本特开平3-282966号公报
专利文献2：日本特表2012-505440号公报
发明内容
发明要解决的课题
如上所述，在哈希表被用于登记多个哈希值的情况下，保存该哈
需的记忆容量也变大。将这种哈希表整体保存于存储控制器具
储器是困难的。因此，哈希表一般保存于如保存大量数据所用
量的存储装置、或者存储控制器具有的硬盘驱动器（HDD）那
地存储装置。另一方面，现有技术应用利用具有相同数目条目
表并构成为多级的哈希表。
因此，存储控制器为了比较哈希值而对这种结构的哈希表进行搜
况下，在该存储控制器与存储装置之间将产生很多的输入输出
处理。这样，在伴随着用于排除数据重复的哈希值的比较而
在哈希
个哈希
表。
希表所
有的存
的大容
样的本
的多个
索的情
（I/O）
产生很多I/O
处理时，存储装置的写入性能（写入速度）低下。
本发明要解决的课题在于，提供能够使得用于排除数据重复的哈
索高速化的存储系统、存储控制器及方法。
用于解决课题的手段
希表搜
根据实施方式，存储系统具备存储装置、存储控制器以及哈希表。
储控制器控制对所述存储装置的访问。所述哈希表包含具有第
的条目的第1表及具有比所述第1数目大的第2数目的条目的
存储控制器具备分割部、哈希生成部、访问控制器、重
重复判定部。所述分割部将由来自主计算机的写入请求
分割成多个大块。所述哈希生成部基于所述多个大块的
计算所述多个大块的各自的具有第1长度的哈希值。所
附图说明
图1是表示实施方式涉及的计算机系统的典型的硬件结构的框
所述存
1数目
第2表。所述
复管理部以及
所指定的数据
各自的数据，
述访问控制器对所述存储装置写入大块。在所述存储装置被写入第1
大块的情况下，所述重复管理部将所述第1大块的第1哈希值与所述
第1大块建立对应并优先地登记到所述哈希表的所述第1表。所述重
复判定部，在计算出第2大块的第2哈希值的情况下，使从所述第1
表的搜索优先来执行从所述哈希表搜索与所述第2哈希值一致的第3
哈希值的处理，由此判定具有与所述第2大块相同内容的第3大块是
否保存于所述存储装置。所述重复管理部，在判定为所述第3大块保
存于所述存储装置的情况下，抑制所述第2大块被写入所述存储装
置。
图。
图2是以图1所示的存储控制器的典型的功能结构为主进行表示
图3是表示通过来自主计算机的写入请求所指定的文件的数据与
关系的例子的图。
图4是表示图2所示的哈希表的数据结构例的图。
图5是表示图4所示的哈希表所包含的第1级的表具有的叶页的
构例的图。
图6是表示图5所示的管理信息的格式的例子的图。
图7是表示图5所示的其他的管理信息的格式的例子的图。
图8是表示图2所示的元表（Meta Table）的数据结构例的图。
图9是表示图2所示的大块表的数据结构例的图。
图10是表示对同实施方式中的数据写入处理的典型的步骤进行
用的流程图的一部分的图。
图11是表示对同数据写入处理的典型的步骤进行说明所用的流
其他的一部分的图。
图12是表示对同数据写入处理的典型的步骤进行说明所用的流
剩余部分的图。
图13是表示对同实施方式中的哈希值搜索处理的典型的步骤进
的框图。
大块的
数据结
说明所
程图的
程图的
行说明
所用的流程图的一部分的图。
图14是表示对同哈希值搜索处理的典型的步骤进行说明所用的
的剩余部分的图。
图15是表示由从主计算机依次发送的三个文件写入请求所指定
文件与通过该三个文件被每隔恒定的尺寸来划分而取得的大
子的图。
图16是表示哈希表中包含的第1级的表的内容的变化的例子的
图17是表示元表的内容的变化的例子的图。
图18是表示大块表的内容的变化的例子的图。
具体实施方式
以下，参照附图对实施的方式进行说明。
图1是表示实施方式涉及的计算机系统的典型的硬件结构的框
机系统包括存储系统10及主计算机（以下，称为主机
统10经由网络30与主机20连接。
主机20是服务器、或者客户端个人计算机（客户端PC）这样的
算机。在主机20内，用于对存储系统10内的数据进行访问的
按照该应用程序，主机20将存储系统10（更详细而
后述的HDD/SSD阵列11）作为外部记忆装置并
30例如是存储区域网络（SAN）、因特网
流程图
的三个
块的关系的例
图。
图。所述计算
的装置）20。存储系
物理计
应用程序动作。
言，存储系统10的
经由网络30来利用。网络
（Internet）或者内部网
（intranet）。因特网或者内部网例如由以太网
主机20也可以经由光纤通道（FC）、
线、串行SCSI（SAS）总线、或者
那样的主机接口总线与存储系统10
（登记商标）来构成。此外，
小型计算机系统接口（SCSI）总
串行高级技术附件（SATA）总线
连接。
存储系统10包括HDD/SSD阵列11及存储控制器12。在本实施
HDD/SSD阵列11及存储控制器12构成存储装置。HDD/SSD
例如多个硬盘驱动器及多个固态硬盘（SSD）所构成的
存储控制器12经由存储接口总线13来控制对HDD/SSD阵列11
存储控制器12经由网络30与主机20连接。存储控制器12
理通过指定逻辑地址而进行的读出请求或写入请求。存
通过地址转换功能将所指定的逻辑地址转换为物理地
映射了该逻辑地址的HDD/SSD阵列11内的物
况为例更详细地叙述，存储控制器12将
址所指定的数据（大块）的大块编
12将大块编号转换为物理地址，
大块的HDD/SSD阵列11
访问HDD/SSD阵列
存储控制器12包括CPU121、存储器122及硬盘驱动器（HDD）
CPU121按照存储器122内的后述的控制程序区域122a中所保
方式中，
阵列11是用
RAID（Redundant Arrays of Inexpensive Disks或Redundant Arrays of
Independent Disks）阵列。HDD/SSD阵列11经由存储接口总线13与
存储控制器12（更详细而言，存储控制器12的未图示的存储接口）
连接。在本实施方式中，存储接口总线13是FC（光纤通道）。然而，
存储接口总线13也可以是SCSI总线、SAS总线、或者SATA总线那
样的、FC以外的接口总线。
的访问。
从主机20受
储控制器12
址，该物理地址表示
理区域。若以数据读出的情
逻辑地址转换为分配给以该逻辑地
号。关于大块，后述。存储控制器
该物理地址表示保存有该大块编号所示的
内的物理区域。存储控制器12基于该物理地址
11。
123。
存的控制程序
的程序编码，在存储控制器12中执行被请求的处理。
多个DRAM所构成的易失性存储器。HDD123
控制程序及各种表。此外，也能够使用搭
代替HDD123。
存储器122例如是用
是本地存储装置，用于保存
载了多个闪存器的存储装置
在本实施方式中，存储控制器12包括于包含HDD/SSD阵列11
装置。然而，存储控制器12也可以独立于存储装置而被包括。
下，存储控制器12也可以内置于主机20。另外，存储控制器
言，存储控制器12的功能）也可以用主机20具有的操
能的一部分来实现。
另外，存储控制器12也可以包括于在主机20的插件槽中安装并
的卡片。另外，也可以是，存储控制器12的一部分内置于主
另外，也可以应用例如用多个HDD而构成的RAID阵列、或用
SSD而构成的RAID阵列，来代替HDD/SSD阵列11。另外，
具有RAID结构的仅仅多个存储驱动的集合（驱动阵
HDD/SSD阵列11（即RAID阵列）。
图2是以图1所示的存储控制器12的典型的功能结构为主进行
框图。存储控制器12包括分割部200、重复管理部201、重复
哈希生成部203及访问控制器204。关于分割部200、
复判定部202、哈希生成部203及访问控制器204
功能要素200至204是通过由图1所示的存储控
制程序而实现的软件模块。然而，功能要
部也可以通过硬件模块来实现。
的存储
此情况
12（更详细而
作系统（OS）的功
被使用
机20，该存储控制器12的剩余部分包括于所述卡片。
多个
也可以应用不
列），来代替
表示的
判定部202、
重复管理部201、重
的功能，后述。这些
制器12的CPU121执行控
素200至204的一部分或全
存储器122包含控制程序区域122a、表区域122b及工作区域
序区域122a用于保存由CPU121执行的控制程序的至
序如前所述那样、预先保存于HDD123，该控制
制器12的起动时从该HDD123载入到控
表区域122b用于对保存于HDD123的各种表的至少一部分进行
工作区域122c用于保存CPU121执行控制程序时所利用的临
HDD123（即，本地存储装置）除了保存上述的控制程序以外，
后述的哈希表205、元表206及大块表207。即HDD123包含
程序、哈希表205、元表206及大块表207的记忆区域。
图3表示通过来自主机20的写入请求所指定的文件的数据与大
系的例子。分割部200将图3所示的文件分割成固定长、例如
比特）的数据的块。将该每4K比特的数据的块称为大
对每个大块管理重复的有无。在图3的例子中，
此情况下，文件F被分割成N个大块＃
块＃0至＃N-1赋予唯一的识别编号
块编号以8比特表示。
接着，对在HDD123中保存的哈希表205的概要进行说明。哈希
用于对被赋予了大块编号的每个大块登记哈希信息。哈希信息
含基于对应的大块而计算出的32比特的哈希值与该大块的8
号的对。即，哈希表205用于登记哈希信息，该哈希信
希值与该大块的大块编号建立关联的哈希信息。
哈希表205用于由重复判定部202来判定具有与应当写入
122c。控制程
少一部分。该控制程
程序的至少一部分在存储控
制程序区域122a。
保存。
时性的数据。
还保存
分别保存控制
块的关
4千比特（4K
块。重复管理部201
文件F的尺寸为4NK比特。
0至＃N-1。重复管理部201对大
即大块编号。在本实施方式中，大
表205
例如包
比特的大块编
息是指，将大块的哈
HDD/SSD阵
列11的大块相同内容的大块是否已被写入到该
理部201基于该重复判定部202的判定的
块被重复写入到HDD/SSD阵列11。
HDD/SSD阵列11。重复管
结果，排除具有相同内容的多个大
由此，数据的重复排除能够实现。
在此，对本实施方式中应用的数据的重复排除的概要进行说明。
设想从主机20向存储系统10的存储控制器12请求包含大块
入。另外，设大块A的哈希值为H（A）。重复判定部
值H（A）与登记到哈希表205的哈希值依次比
复判定部202判定HDD/SSD阵列11中
大块（以下，称为代表大块A）。
如果哈希表205中登记有与哈希值H（A）一致的哈希值（即，
H（A）），则重复判定部202判定为HDD/SSD阵列11中保存
大块A。即，重复判定部202判定为大块A重复。另一方面，
希表205中未登记有哈希值H（A），则重复判定部202判定
重复。
在判定为大块A不重复的情况下，访问控制器204在由写入请
定的HDD/SSD阵列11的地址中写入大块A。更详细而言，
204将大块A写入到由被分配到来自主机20的写入请求
地址的物理地址所示的HDD/SSD阵列11的物理区域。
理部201将哈希信息登记到哈希表205，该哈希信息包
大块A的大块编号的对。
另一方面，在判定为大块A重复的情况下，重复管理部201抑
控制器204将大块A写入HDD/SSD阵列11。此情况下，重
对由来自主机20的写入请求所指定的逻辑地址分配物
首先，
A的文件的写
202将大块A的哈希
较。基于该比较的结果，重
保存有具有与大块A相同内容的
哈希值
有代表
如果哈
为大块A不
求所指
访问控制器
所指定的逻辑
此时，重复管
含哈希值H（A）与
制访问
复管理部201
理地址，该物理地址是指已在HDD/SSD阵列11中写入代表大块A
的物理地址（即映射）。
图4表示图2所示的哈希表205的数据结构例。哈希表205用多
成为多级。在图4的例子中，哈希表205用7个表TBL_1、
TBL_3、TBL_4、TBL_5、TBL_6及TBL_7构成。即哈希表
构的表。在此，表TBL_h（h＝1，2，3，4、5，6，7）
中的第h级的表。
表TBL_1至TBL_7任一个都包含“kmax＋1”个页（以下，称为
在此，表TBL_h的第k个（k＝0，1，…，kmax）叶页如LP_k
那样标记。叶页LP_k（h）与后述的组G_k（组编号k或组索
对应。叶页LP_k（h）用于登记哈希信息，该哈希信息
G_k的哈希值（更详细而言，后述的第一阶段哈 希值
个表构
TBL_2、
205为7段结
是哈希表205
叶页）。
（h）
引k）建立了
是指，包含属于组
（first stage hash value））与用于确定在该哈希值的计算中所用的
大块编号的对的哈希信息。
表TBL_1至TBL_7的叶页LP_k（1）至LP_k（7）的尺寸不同，
在登记哈希信息中所用的条目的数目也不同。在此，设表
大块的
因此，
TBL_1、
LP_k（1）、
及
TBL_2、TBL_3、TBL_4、TBL_5、TBL_6及TBL_7的叶页
LP_k（2）、LP_k（3）、LP_k（4）、LP_k（5）、LP_k（6）
LP_k（7）的尺寸（条目数）分别为SIZE_1（EN_1）、SIZE_2（EN_2）、
SIZE_1＜SIZE_2＜SIZE_3＜SIZE_4＜SIZE_5＜SIZE_6＜
SIZE_7
SIZE_3（EN_3）、SIZE_4（EN_4）、SIZE_5（EN_5）、SIZE_6（EN_6）
及SIZE_7（EN_7）。此情况下，在这些尺寸（条目数）之间，存在
如下的关系：
EN_1＜EN_2＜EN_3＜EN_4＜EN_5＜EN_6＜EN_7。
即，在本实施方式中，构成哈希表205的7个表TBL_1、TBL_2、
TBL_4、TBL_5、TBL_6及TBL_7具有的叶页LP_k（1）、
LP_k（3）、LP_k（4）、LP_k（5）、LP_k（6）及LP_k（7）
（条目数）中，表TBL_1（即第1级的表TBL_1）的尺寸最
表TBL_2、TBL_3、TBL_4、TBL_5、TBL_6及TBL_7
表TBL_1的各叶页LP_k（1）具有例如96条目。表TBL_2的
LP_k（2）具有例如192条目（即，叶页LP_k（1）的尺寸的
表TBL_3的各叶页LP_k（3）具有例如384条目（即，
的尺寸的2倍的条目）。表TBL_4的各叶页LP_k（4）
条目（叶页LP_k（3）的尺寸的2倍的条目）。表TBL_5
LP_k（5）具有例如1536条目（即，叶页LP_k（4）的尺
目）。表TBL_6的各叶页LP_k（6）具有例如3，072
LP_k（5）的尺寸的2倍的条目）。表TBL_7的各叶
如6，144条目（即，叶页LP_k（6）的尺寸的2
在本实施方式中，哈希表205为了对该哈希表205的访问的高速
从HDD123载入到存储器122的表区域122b中使用。但是，
122的表区域122b的容量的制约，并不是哈希表205整
储器122，而是仅仅从哈希表205选择出的1个叶页被
表区域122b。
在本实施方式中，用32比特的哈希值作为大块（4K比特的大块） 的哈希
化而被
各叶页
的顺序，叶页的尺寸（条目数）变大。
TBL_3、
LP_k（2）、
的尺寸
小。以下，按
2倍的条目）。
叶页LP_k（2）
具有例如768
的各叶页
寸的2倍的条
条目（即，叶页
页LP_k（7）具有例
倍的条目）。
因为存储器
体被载入到存
载入到存储器122的
值。哈希生成部203在计算该32比特的哈希值时，应用例如
256”的第1哈希函数。将该32比特的哈希值称为第一
在此，设在HDD/SSD阵列11中保存的全部大块的第一阶段哈
大块编号的对不被分类就被分散登记到表TBL_1至TBL_7
在表TBL_1～TBL_7中保存的第一阶段哈希值与大
得庞大。为此，从表TBL_h（h＝1，2，3，4、5，
前述的哈希值H（A）一致的哈希值需要很多时
因此，在本实施方式中，重复管理部201基于第一阶段哈希值，
登记到表TBL_1～TBL_7中的该第一阶段哈希值（即，32比
的集合分类为“kmax＋1”个组G_0至G_kmax。组G_0
编号0至kmax建立对应。表TBL_1～TBL_7的
为了重复管理部201进行的上述的分类，哈希生成部203基于第
哈希值生成用于确定该第一阶段哈希值所属的组的作为组编
下，称为组索引）。在本实施方式中，该组索引中使用
哈希值算出的3比特的哈希值。将该3比特的哈希值称
（second stage hash value）。该第二阶段哈希值（即
第2哈希函数。关于该第2哈希函数，后述。
重复管理部201例如将与第二阶段哈希值（组索引）0（＝
被称为“SHA-
阶段哈希值。
希值与
中。此情况下，
块编号的对的数目变
6，7）中搜索例如与
间。
将应当
特的哈希值）
至G_kmax分别与组
各自的“kmax＋1”个叶页与组G_0至G_kmax（即组编号0至kmax）
建立了对应。例如，表TBL_h的叶页LP_0（h）至LP_kmax（h）与
组G_0至G_kmax建立了对应。在此，kmax”例如为16，777，216
（16进制表现时为0xFFFFFF）。0xFFFFFF中的“0x”表示附有该“0x”
的FFFFFF为16进制表现。
一阶段
号的索引（以
基于第一阶段
为第二阶段哈希值
组索引）的计算中用
0x000000）对
应的第一阶段哈希值的集合作为具有组编号0的组G_0
复管理部201将与第二阶段哈希值1（0x000001）
值的集合作为具有组编号1的组G_1来管理，
（0x000002）对应的第一阶段哈希值的集合作
来管理。同样地，重复管理部201将与第
对应的第一阶段哈希值的集合作为
管理。即重复管理部201将与第二
合作为具有组编号k的组
来管理。同样地，重
对应的第一阶段哈希
将与第二阶段哈希值2
为具有组编号2的组G_2
二阶段哈希值kmax（0xFFFFFF）
具有组编号kmax的组G_kmax来
阶段哈希值k对应的第一阶段哈希值的集
G_k来管理。
这样，在本实施方式中，重复管理部201用第二阶段哈希值（即 组索
“kmax引），将对应的第一阶段索引值的集合分类为16，777，216个（即
＋1”个）组。由此，与第一阶段索引值的集合未被组化的情况
将哈希表205中的搜索范围减小为16，777，216分之
在此，对第2哈希函数进行说明。如前所述，第2哈希函数用于
索引的第二阶段哈希值的计算。在本实施方式中，该第2哈希
函数。该除法函数用规定的质数作为除数。具体而言，
用比以3比特表现的最大的数值（16，777，216）小并
在应用了上述的第2哈希函数的情况下，第二阶段哈希值的总数
组索引的总数）为16，777，213（0xFFFFFC）。此情况下，
值“kmax-2”（＝16，777，214）、“kmax-1”（＝16，777，
（＝16，777，216）不存在。然而，在本实施方式中，
重复管理部201也管理分别与第二阶段哈希值
相比较，能够
一。
作为组
函数使用除法
该除数例如使
且最接近该最大的数值的质数（16，777，213）。第二阶段哈希值是
基于除法函数（第2哈希函数），以质数16，777，213除第一阶段哈
希值而取得的余数。除法函数的除数使用这种质数，由此能够将分别
属于组G_0至G_kmax的第一阶段哈希值的集合随机化。
（即，
第二阶段哈希
215）及kmax
为了简化管理，
“kmax-2”、“kmax-1”及
kmax对应的组G_（kmax-2）、G_（kmax-1）
（kmax-2）、G_（kmax-1）及G_kmax未必
及G_kmax。此外，组G_
是必要的。
接着，举例对表TBL_1至TBL_7的各叶页的数据结构进行说明。
示在图4所示的哈希表205中包含的表TBL_1（即第1级的表
的第k个叶页LP_k（1）的数据结构例。叶页LP_k（1）
立了对应。
叶页LP_k（1）包括8个扇区ST_0至ST_7。扇区如周知那样，
硬盘驱动器（HDD）或者固态硬盘（SSD）那样的存储驱动进
时的最小单位。在本实施方式中，1扇区的尺寸为512比特。
ST_7分别包含登记哈希信息时所用的12个条目。因此，
如前所述那样、具有96（8×12＝96）个条目。哈希
40比特。哈希信息包含32比特的哈希值（第一阶
的大块编号的对。扇区ST_0至ST_7进一步包
MI1_7。管理信息MI1_0至MI1_7的各自的尺
理信息MI1_i（i＝0，1，…，i（1）max），
从叶页LP_k（1）具有的扇区的数目中减
表TBL_2至TBL_7具有的第k个叶页LP_k（2）至LP_k（7）
结构也与图5所示的叶页LP_k（1）的数据结构同样。但是，
至LP_k（7）具有的扇区的数目如依据前述的条目数
例如，叶页LP_k（2）、LP_k（3）及LP_k（4）分别具有16扇
的差异所知那样，是不同的。
图5表
TBL_1）具有
与组G_k建
是对如
行访问
扇区ST_0至
叶页LP_k（1）
信息的尺寸例如为
段哈希值）与8比特
含管理信息MI1_0至
寸例如为32比特。关于管
后述。此外，i（1）max是
去1而获得的数，为7。
的数据
叶页LP_k（2）
区
（2）
页
条目）、
（192条目）、32扇区（384条目）及64扇区（768条目）。即，i
max、i（3）max及i（4）max分别为15、31及63。另外，叶
LP_k（5）、LP_k（6）及LP_k（7）分别具有128扇区（1，536
256扇区（3，072条目）及512扇区（6，144条目）。即，i
（6）max及i（7）max分别为128、256及512。
接着，对向如上所述的数据结构的哈希表205登记哈希信息（即
205的更新）的概要进行说明。如前所述，哈希表205包括表
TBL_7。表TBL_1具有基于3比特的第二阶段哈希值
0xFFFFFF（即组索引）而分类的“kmax＋1”个（即16，
叶页LP_0（1）至LP_kmax（1）。
例如在具有第二阶段哈希值0x000000的第1大块被写入到
列11的情况下，重复管理部201在通过该第二阶段哈希
指定的第1级的表TBL_1的叶页LP_0（1）中登记第1
希信息包含第1大块的第一阶段哈希值与该第1
地，例如在具有第二阶段哈希值0x000001
HDD/SSD阵列11的情况下，重复管理部201
0x000001指定的第1级的表TBL_1的叶页
信息。该第2哈希信息包含第2大块的第
编号的对。
第1级的表TBL_1的叶页LP_k（1）（k＝0，1，…，kmax）具
条目（EN_1＝96）。为此，例如在具有第二阶段哈希值0x000000
个大块已被写入到HDD/SSD阵列11的情况下，叶页LP_0（1）
在该状态下，例如无法将上述的第1哈希信息登记到叶页LP_0
中。即，需要增设的叶页。
因此，在本实施方式中，哈希表205进一步包括提供增设的叶页
（5）max、i
哈希表
TBL_1至
0x000000至
777，216个）
HDD/SSD阵
值0x000000
哈希信息。该第1哈
大块的大块编号的对。同样
的第2大块被写入到
在通过该第二阶段哈希值
LP_1（1）中登记第2哈希
一阶段哈希值与该第2大块的大块
有96
的96
充满。
（1）
LP_k
当在第（2）的第2级的表TBL_2。第2级的表TBL_2的叶页LP_k（2）
1级的表TBL_1中叶页LP_k（1）达到充满的情况下使用。 根据该情况，
可以说，表TBL_1（即第1级的表TBL_1）是哈希表
205中的基本的表。
另外，在第1级的表TBL_1的叶页LP_0（1）达到充满的状态
上所述那样，设第1大块（即，具有第二阶段哈希值0x000000
大块）被写入到HDD/SSD阵列11。此情况下，重复管理部
的表TBL_2的叶页LP_0（2）中登记第1哈希信息。第
TBL_2的叶页LP_k（2）（k＝0，1，…，kmax）具有192
＝192）。因此，例如叶页LP_0（2）的192条目也达到
无法在该叶页LP_0（2）中登记新的哈希信息。
因此，哈希表205进一步包括提供增设的叶页LP_k（3）的第3
TBL_3。叶页LP_k（3）当在第2级的表TBL_2中叶页LP_k
满的情况下使用。第3级的表TBL_3的叶页LP_k（3）
（EN_3＝384）。同样地，哈希表205还包括提供增设
第4级的表TBL_4。叶页LP_k（4）当在第3级
（3）达到充满的情况下使用。第4级的表
具有768条目（EN_4＝768）。
同样地，哈希表205还包括提供增设的叶页LP_k（5）的第5级
TBL_5。第5级的表TBL_5的叶页LP_k（5）具有1，536条目
下，如
的第1
201在第2级
2级的表
条目（EN_2
充满的情况下，
级的表
（2）达到充
具有384条目
的叶页LP_k（4）的
的表TBL_3中叶页LP_k
TBL_4的叶页LP_k（4）
的表
（EN_5＝1，536）。同样地，哈希表205还包括提供增设的叶页LP_k
（6）的第6级的表TBL_6、提供增设的叶页LP_k（7）的第7级的
表TBL_7。第6级的表TBL_6的叶页LP_k（6）具有3，072条目（EN_6
＝3，072），第7级的表TBL_7的叶页LP_k（7）具有6，144条目
（EN_6＝6，144）。即，哈希表205针对每个第二阶段哈希值（即组
索引）具有12，192个条目。
在此，对如上所述的哈希表205的结构的意义进行说明。在哈希
中所登记的哈希值的量随着在HDD/SSD阵列11中保存的数
数）变多而增大。在这种状况下，哈希表205所需的记
法在存储器122中保存的大小（例如，超过数
表205如本实施方式那样、保存于HDD123
外，哈希表205也可以保存于HDD/SSD
在哈希表205所需的记忆容量变大时，存储控制器12（更详细
存储控制器12的重复判定部202）为了搜索哈希值，需要重
205的全部条目的一部分读入到存储器122的动作。为
12与存储装置之间，产生较多的输入输出（I/O）
表205
据的量（大块
忆容量一般成为也无
GB的大小）。为此，哈希
（即，本地存储装置）。此
阵列11。
而言，
复将该哈希表
此，在存储控制器
处理。
另外，在一般的存储系统中，以最初分配到逻辑卷的记忆容量（例
小的单位的记忆容量）开始运用。逻辑卷是指，由主机识别为
存储驱动的记忆区域。逻辑卷中，例如每隔4K（千）比特适
HDD/SSD阵列11的记忆区域（物理区域）。这种存储系统具
始后的状况使逻辑卷的记忆容量灵活地增加的功能。本
存储系统10也是同样的。
在这种具有记忆容量增设功能并且具有重复排除功能的存储系
在运用开始时，准备与分配了最小单位的记忆容量的逻辑卷对
准的大小RS的哈希表。并且，在分配给逻辑卷的记忆容量增
位的M倍（M是比1大的整数）的情况下，哈希表也
RS的M倍。
在本实施方式中，能够对逻辑卷分配的记忆容量的最小的单位是
（T）比特。设该6T比特的数据如前所述那样、被分割成4K
当分配
如，最
逻辑的
有根据运用开
实施方式中的
统中，
应的基
加到最小的单
增加到基准的大小
6太拉
比特的大块。
重复管理部201基于各大块的32比特的哈希值（第一阶段哈希
排除具有相同内容的多个大块（即重复的大块）被保存于
列11的情况。此情况下，哈希表205中登记的大块的数
重复后的大块的数目）以一定的可能性不超过16，777，
所周知的。
16，777，216如前所述那样、是在第一阶段哈希值的集合被按
段哈希值来分类的情况下获得的组G_0至G_kmax（组索引）
是与各组G_k（k＝0，1，…，kmax）建立了对应的表
（1）具有的条目的数目（EN_1）。因此，表TBL_1
的逻辑卷的数据的重复排除。即，在逻辑卷的记
情况下，具有16，777，216×96条目的表TBL_1
在此，逻辑卷的记忆容量从例如6T比特增加到12T比特或24T
情况下，仅仅表TBL_1，条目数不足。此情况下，需要将哈希
的大小扩展为基准的大小RS的2倍或4倍。同样地，逻辑卷
例如6T比特增加到516T比特的情况下，需要将哈希
基准的大小RS的86倍。
若是现有技术，则为了进行该扩展，具有基准大小RS的85个
第86的表被追加至具有基准大小R的第1表（即构成运用开
的第1表）。可知，第2至第86的表任一个都具有与第
目数相同数目的条目。第1表用作多级结构的哈希表的
第86的表分别用作多级结构的哈希表的第2级
此情况下，存储控制器为了从第1至第86的表中搜索哈希值， 需要将
第2至
比特的
表205
的大小为上述的基准的大小RS。
第二阶
值），
HDD/SSD阵
目（即，排除
216×96是众
的总数。96
TBL_1的叶页LP_k
能够应用于6T比特
忆容量为6T比特的
的记忆容量从
表205的大小扩展为
始时的哈希表
1表具有的条
第1级的表。第2至
至第86级的表。
该第1至第86的表依次读入到存储器。因此，在现有技术中，
希表，即使使存储器具有用于保存16，777，216×96条目的表
也需要86次I/O处理。
与之相对，在本实施方式中，第1级的表TB_1中被追加第2级
TBL_2至第7级的表TBL_7。第2级的表TBL_2、第3级的表
及第4级的表TBL_4分别具有第1级的表TB_1所具有的条
4倍及8倍的条目。另外，第4级的表TBL_4、第5级
级的表TBL_6分别具有第1级的表TB_1所具有
32倍及64倍的条目。
此情况下，哈希表205的总条目数成为第1级的表TB_1的条目
127倍，充分地超过了支持516T比特的记忆容量的逻辑卷所需
目数（即，第1级的表TB_1的总条目数的86倍）。在应用这
的哈希表205的本实施方式中，存储控制器12在从第1级的
7级的表TBL_7中搜索哈希值的情况下，至多进行7
因此，根据本实施方式，与现有技术相比较，能够大幅削减伴随
值搜索的表访问所需的I/O处理的次数。由此，根据本实施方
而且，在本实施方式中，存储控制器12无需为了搜索哈希值而
级的表TB_1至第7级的表TBL_7的各自的整体读入到存储器
即，存储控制器12仅仅只将包含第1级的表TB_1至第7级的
TBL_7并且与第二阶段哈希值（更详细而言，以第二阶段哈希值
关于哈
区域，
的表
TBL_3
目数的2倍、
的表TBL_5及第6
的条目数的16倍、
数的
的总条
种结构
表TB_1至第
次的I/O处理就结束。
着哈希
式，能够实现哈希值搜索的高速化，能够提高与重复排除有关的处理
能力，进一步能够提高存储系统10的写入性能（写入速度）。
将第1
122。
表
确定的
组）建立了对应的叶页读入到存储器122即可。
并且，在本实施方式中，最大的尺寸的叶页是第7级的TBL_7
LP_k（7）。该叶页LP_k（7）具有6，144个条目。因此，在
方式中，存储控制器12通过上述的I/O处理，最大将具有6，
叶页从存储装置（更详细而言，HDD123）读入到存储
储器122）即可。换言之，存储器122关于哈希
144条目的表区域即可。
因此，根据本实施方式，与现有技术相比，能够大幅减小哈希值
范围。由此，根据本实施方式，能够实现哈希值搜索的进一步
化，能够进一步提高存储系统10的写入性能。
图6表示图5所示的管理信息MI1_0的格式的例子。管理信息
如前所述，被登记于表TBL_1具有的叶页LP_k（1）的开头
管理信息MI1_0包含8个字段F0至F7。字段F0至
2比特。
管理信息MI1_0的字段F0用于设定使用条目计数CNT。使用条
CNT表示在登记管理信息MI1_0（即，包含字段F0的管理信
扇区ST_0中在哈希信息的登记时所使用的条目的数目。
管理信息MI1_0的字段F1至F7用于设定使用条目计数CNT1
用条目计数CNT1至CNT7表示在表TBL_1至TBL_7
LP_k（7）中在哈希信息的登记时所使用的条目
图7表示图5所示的管理信息MI1_i（i＝1，2，…，7）的格式
管理信息MI1_i如前所述那样、被登记到表TBL_1具有的
的叶页
本实施
144个条目的
器（更详细而言，存
表205、仅具有用于保存6，
搜索的
的高速
MI1_0
的扇区ST_0。
F7的各自的长度为
目计数
息MI1_0）的
至CNT7。使
的叶页LP_k（1）至
的数目。
的例子。
叶页LP_k（1）
的扇区ST_i（即，除了扇区ST_0外的扇区）。管理
信息MI1_i包含字段F0。字段F0的长度为2比特。
管理信息MI1_i的字段F0与管理信息MI1_0同样地，在设定使
计数CNT时使用。该使用条目计数CNT表示在登记管理信息
ST_i中在哈希信息的登记时所使用的条目的数目。图7
MI1_i的格式也被应用于在表TBL_2至TBL_7具有
LP_k（7）的全部扇区中登记的管理信息。
图8表示图2所示的元表206的数据结构例。元表206用于对大
管理，该大块是指，被写入到通过按每4K（千）比特划分逻
各区域（4K比特区域）的大块。元表206具有与对逻
区域（更详细而言，在4K比特区域中保存的大
立了对应的条目的集合。
元表206的各条目用于对在与该条目建立了对应的逻辑地址表
区域中保存的大块的大块编号进行登记。即元表206是
4K比特区域的大块而将该4K比特区域的逻辑地
大块编号建立了对应的表。因此，重复管理部
来确定在以目的的逻辑地址所指定的区域
图9表示图2所示的大块表207的数据结构例。大块表207具有
编号建立了对应的条目的集合。大块表207的各条目用于对具
立了对应的大块编号的大块所涉及的大块信息进行登
理地址及参照计数RCNT。
大块表207的各条目具有物理地址字段及参照计数字段。物理地
用于登记物理地址，该物理地址是指，对具有与具有该物理地
用条目
MI1_i的扇区
所示的管理信息
的叶页LP_k（2）至
块进行
辑卷而获得的
辑卷的各个4K比特
块）进行指示的逻辑地址建
示的4K比特
为了表示写入于各
址与分配给该大块的
201能够通过参照元表206
中保存着的大块。
与大块
有与该条目建
记。大块信息包含物
址字段
址字段
的条目（以下，称为对应条目）建立了对应的大块编号的大块
位置进行指示的物理地址。大块的物理位置是指，实际保存有
的HDD/SSD阵列11的记忆区域的位置。
参照计数字段用于登记参照计数RCNT。参照计数RCNT表示以
条目建立了对应的大块编号所确定的大块（以下，称为对应大
几个逻辑地址（4K比特区域）建立了对应。
例如，在参照计数RCNT为“1”的情况下，该参照计数RCNT表
的物理
该大块
与对应
块）与
示对应大块不会成为重复排除的对象而被写入到HDD/SSD阵
换言之，参照计数RCNT表示对应大块仅被写入到逻辑卷内
辑地址所指示的4K比特区域。与之相对，在参照计数RCN
的情况下，该参照计数RCN表示：通过重复排除，虽然在
阵列11中作为实体写入有1个大块，但是该大块与两个逻辑
立了对应。换言之，表示从主机20对逻辑卷内的两个逻辑地
示的4K比特区域写入了具有相同内容的大块。
列11。
的1个逻
为例如“2”
HDD/SSD
地址建
址所指
接着，参照图10至图12对本实施方式的动作进行说明。图10
用于对由存储系统10的存储控制器12从主机20接收到数据
况下执行的数据写入处理的典型的步骤进行说明所用
图。图11是表示用于对同数据写入处理的典型
其他的一部分的图，图12是表示用于对
说明的流程图的剩余部分的图。
这里，设从主机20经由网络30对存储系统10发送了对文件的
行指定的数据写入请求（即，文件写入请求）。并且，设存储
10的存储控制器12接收到来自主机20的文件写入请求。
是表示
写入请求的情
的流程图的一部分的
的步骤进行说明的流程图的
同数据写入处理的典型的步骤进行
写入进
系统
于是，存储控制器12的分割部200例如按每4K比特对以文件
求所指定的文件（即文件数据）进行划分。由此，分割部200
件分割成具有4K比特尺寸的多个大块（步骤S1）。即
指定的文件取得构成该文件的多个大块。此外，
寸为4K比特的情况下，分割部200取得该文件
大块的尺寸无需为固定长。即大块的尺寸
重复管理部201将所取得的大块的数设定为变量N（步骤S2）。
将所取得的N个大块标记为大块C_1至C_N。哈希生成部203
为例如“SHA-256”的第1哈希函数计算大块C_1至C_N的哈
阶段哈希值）H1（C_1）至H1（C_N）（步骤S3）。第
H1（C_1）至H1（C_N）分别以32比特表示。
接着，哈希生成部203用第2哈希函数计算第一阶段哈希值H1
至H1（C_N）的哈希值（即第二阶段哈希值）H2（C_1）至
写入请
将所指定的文
重复管理部201从所
在所指定的文件的尺
本身作为1个大块。在此，
也可以是可变长。
在此，
用被称
希值（即第一
一阶段哈希值
（C_1）
H2（C_N）（步骤S4）。如前所述，第2哈希函数是用质数16，
213作为除数的除法函数。即哈希生成部203将通过以质数16，777，
213除第一阶段哈希值H1（C_1）至H1（C_N）而取得的余数决定
777，
为第二阶段哈希值H2（C_1）至H2（C_N）。
接着，重复管理部201将在指定通过步骤S1取得的N个大块中
大块时所用的变量n设定为初始值1（步骤S5）。然后，重复
201从通过步骤S1取得的N个大块C_1至C_N中选择第n
（步骤S6）。
接着，重复判定部202执行哈希值搜索处理，该哈希值搜索处理
哈希表205搜索与通过重复管理部201所选择的大块C_n的第
哈希值H1（C_n）一致的第一阶段哈希值（步骤S7）。在该哈
的一个
管理部
个大块C_n
用于从
一阶段
希值搜
索处理中，重复判定部202依次比较通过步骤S4计算出的大
二阶段哈希值H2（C_n）和属于建立有对应的组并且被
205的第一阶段哈希值。通过该比较，重复判定部202
值H1（C_n）一致的第一阶段哈希值。该哈希值
重复判定部202基于哈希值搜索处理的结果，判定与所选择的大
的第一阶段哈希值H1（C_n）一致的第一阶段哈希值是否存
205（步骤S8）。重复管理部201基于该重复判定部202
进入到步骤S9或步骤S16。
如果与所选择的大块C_n的第一阶段哈希值H1（C_n）一致的
段哈希值不存在（步骤S8的否），则重复管理部201判定为具
块C_n相同内容的大块未保存于HDD/SSD阵列11。此情况下，
理部201进入到步骤S9。
块C_n的第
登记于哈希表
搜索与第一阶段哈希
搜索处理的详细后述。
块C_n
在于哈希表
的判定的结果，
第一阶
有与大
重复管
在步骤S9中，重复管理部201对大块C_n赋予大块编号CNC_n。
施方式中，赋予时序的大块编号。通过步骤S9对大块C_n赋
CNC_n通过对已赋予其他大块的最新的大块编号加1
HDD123中保存最新的大块编号（或接着应当赋
大块编号从HDD123载入到存储器122的
此外，通过从开头条目起依次参照大块表207的条目，重复管理
也能够取得最新的大块编号。另外，重复管理部201也可以使
当赋予的大块编号建立对应的大块表207的条目进行
重复管理部201能够基于该下一条目指针，决
块编号CNC_n。
在本实
予的大块编号
而获得。为此，例如
予的大块编号）。该最新的
工作区域122c来使用。
部201
用对与接着应
指示的下一条目指针。
定对于大块C_n赋予的大
在对大块C_n赋予大块编号CNC_n时，访问控制器204将该大
写入到HDD/SSD阵列11内的空的记忆区域（步骤S10）。接
部201在与大块C_n的第二阶段哈希值H2（C-n）建立
表205内的叶页LP_k（h）中登记大块C_n的哈希信息
该哈希信息HIC_n包含大块C_n的第一阶段哈
C_n的大块编号的对。
LP_k（h）如后所述那样、表示通过哈希值搜索处理（步骤S7）
索到哈希值的叶页。在此，LP_k（h）中的k表示用作组索引
希值H2（C-n）。另外，LP_k（h）中的h表示叶页LP_k
第h级的表TBL_h。即，表示LP_k（h）是在第h级的
k个叶页。
关于步骤S11的详细，以下进行说明。首先，设最后搜索到哈希
页LP_k（h）的扇区及该扇区的条目分别是该叶页LP_k（h）
ST_i及该第i个扇区ST_i的第j个条目。此情况下，
页LP_k（h）的第i个扇区ST_i内的第j＋1个
信息HIC_n。
另外，重复管理部201使在扇区ST_i中包含的管理信息中的使
计数CNT仅增加1。并且，重复管理部201使在叶页LP_k（1）
的扇区ST_0中包含的管理信息MI1_0中的使用条目计数
1。该管理信息MI1_0如后所述那样、不仅保存于叶页
扇区ST_0，也保存于工作区域122c。
在本实施方式中，在工作区域122c中保存的管理信息MI1_0中
条目计数CNTh增加。在该工作区域122c保存的管理信息
的使用
用条目
的开头
值的叶
最后搜
块C_n
着，重复管理
了对应的哈希
HIC_n（步骤S11）。
希值H1（C-n）及该大块
的第二阶段哈
（h）包含于
表TBL_h包含的第
的第i个扇区
重复判定部202对叶
条目登记大块C_n的哈希
CNTh仅增加
LP_k（1）的开头的
MI1_0在适当
的时机被在HDD123中保存的叶页LP_k（1）的开头的
管理信息MI1_0例如覆盖。适当的时机是指，例如存储
扇区ST_0的
系统10不忙碌的情况或者存储系统10的电源被切断前的时机。
另外，设第i个扇区ST_i的第j个条目是该第i个扇区的最终条
此，i＝11）。此情况下，重复判定部202在叶页LP_k（h）的
1”个扇区ST_（i＋1）内的开头条目中登记大块C_n的哈希信
另外，重复管理部201使在扇区ST_（i＋1）中包含的管理信息
用条目计数CNT仅增加1。并且，重复管理部201使管理信
的使用条目计数CNTh仅增加1。
接着，设最后搜索到哈希值的叶页LP_k（h）内的条目是该叶页
（h）的最终的条目（更详细而言，叶页LP_k（h）的最终的扇
最终的条目）。即，设叶页LP_k（h）的全部条目被使用，该
内没有空条目。此情况下，重复管理部201与上述的
“h+1”级的表TBL_（h+1）中包含的第k个叶页
ST_0（更详细而言，叶页LP_k（h+1）的
的条目）登记大块C_n的哈希信息HIC_n。
另外，重复管理部201使叶页LP_k（h+1）的开头的扇区ST_0
的管理信息中的使用条目计数CNT仅增加1。并且，重复管
理信息MI1_0中的使用条目计数CNT（h+1）仅增加1。
另外，重复管理部201执行步骤S11后进入到步骤S12。在步骤
重复管理部201取得对所选择的大块C_n的逻辑卷内的位置
目（在
第“i＋
息HIC_n。
中的使
息MI1_0中
LP_k
区内的
叶页LP_k（h）
说明不同地、对在第
LP_k（h+1）的开头的扇区
开头的扇区ST_0内的开头
中包含
理部201使管
S12中，
进行表示的逻
辑地址。该逻辑地址通过对由来自主机20的文件写入
（文件的开头地址）加4K（即，4，096）×（n-1）
中重复管理部201进一步在与所取得的逻辑地址
目中登记对所选择的大块C_n赋予的大块
请求指定的逻辑地址
而取得。在步骤S12
建立了对应的元表206的条
编号CNC_n。
重复管理部201执行步骤S12后进入到步骤S13。在步骤S13中，
重复管理部201选择与对所选择的大块C_n赋予的大块编号
了对应的大块表207的条目。在步骤S13中，重复管理
条目中登记所选择的大块C_n所涉及的大块信息
CIC_n包含写入了所选择的大块C_n的HDD/SSD
重复管理部201执行步骤S13后进入到步骤S14。在步骤S14中，
理部201使变量n增加1。并且，重复管理部201判定增加后
超过通过步骤S2所设定的大块数N（步骤S15）。如果
n未超过大块数N（步骤S15的否），则重复管理部201
自主机20的文件写入请求所指定的文件中包含的下一
返回到步骤S6。与之相对，如果增加后的变
S15的是），则重复管理部201判定为结
入请求而指定的文件中包含的全部
至图12的流程图表示的数据写入处
接着，对重复判定部202在步骤S8中判定为与所选择的大块C_n
阶段哈希值H1（C_n）一致的第一阶段哈希值存在的情况的动
说明。这样，在步骤S8的判定为“是”的情况下，重复管理部
有与所选择的大块C_n相同内容的大块已经保存于
在此，将已经保存于HDD/SSD阵列11并且具有
首先，
CNC_n建立
部201还在所选择的
CIC_n。该大块信息
阵列11内的记忆区域的物理地址及参照计数RCN。参照计数RCN
的值为“1”。
重复管
的变量n是否
增加后的变量
为了对在由来
大块的写入进行处理，
量n超过了大块数N（步骤
束了在通过来自主机20的文件写
大块的写入。此情况下，以图10
理结束。
的第一
作进行
201判定为具
HDD/SSD阵列11。
与大块C_n相同内
容的大块标记为大块C_x。
在步骤S8的判定为”是”的情况下，为了排除具有相同内容的多
重复并且被保存于HDD/SSD阵列11的情况，重复管理部201
S16。在步骤S16中，重复管理部201抑制访问控制器204
块C_n写入到HDD/SSD阵列11的动作。
接着，重复管理部201将大块C_x的大块编号作为所选择的大块
大块编号CNC_n，并登记到元表206中（步骤S17）。由此，
206中，相同的大块编号被登记到元表206内的至少两个条目。
理部201为了确定应当登记该大块编号的元表206的条目，通
同样的方法取得对所选择的大块C_n的逻辑卷内的位
址。
个大块
进入到步骤
将所选择的大
C_n的
元表
重复管
过与步骤S12
置进行表示的逻辑地
重复管理部201执行步骤S17后进入到步骤S18。在步骤S18中，
重复管理部201参照在与所选择的大块C_n的大块编号（即，
首先，
大块C_x的大块编号）建立了对应的大块表207的条目中登
块信息CI_Cn。在步骤S18中，重复管理部201还使所参照的
息中的参照计数RCNT增加1。由此，增加后的参照计数
虽然在HDD/SSD阵列11中作为实体写入1个大块，但是具
内容的RCNT个大块被写入到逻辑卷内的RCNT个4K比特区
记着的大
大块信
RCNT表示：
有相同
域。
重复管理部201执行步骤S18后进入到步骤S19。在步骤S19中，
重复管理部201取得对写有大块C_x（即，具有与所选择的大
内容的大块C_x）的HDD/SSD阵列11的记忆区域进行
址。该物理地址包含于通过步骤S18参照的大块信息。
中，重复管理部201进一步将所取得的物理地址分配至所
首先，
块C_n相同
指示的物理地
在步骤S19
选择的大块
C_n的逻辑地址。具体而言，重复管理部201在未图示的
登记对所选择的大块C_n的逻辑地址与所取得的物理
的地址转换信息（即，映射信息）。重复管理部
进入到步骤S14。以后的动作与重复管理部201
的情况相同。
地址转换表中
地址的对应进行表示
201执行步骤S19后
从步骤S13进入到步骤S14
此外，步骤S19未必是必要的。例如，重复管理部201能够如以
那样、不用地址转换表就将由主机20所指定的逻辑地址转换
重复管理部201首先基于由主机20所指定的逻辑地址
取得在与该逻辑地址建立了对应的条目中登记的
复管理部201基于所取得的大块编号参照大块表
建立了对应的条目中登记的物理地址。
接着，参照图13及图14对本实施方式中的哈希值搜索处理（步
的详细进行说明。图13是表示用于对哈希值搜索处理的典型
明的流程图的一部分的图。图13是表示用于对同哈希
步骤进行说明的流程图的剩余部分的图。
首先，重复判定部202将变量h设定为初始值1（步骤S21）。变
示哈希表205内的第h级的表TBL_h。在步骤S21中，重复
将变量k设定为所选择的大块C_n的第二阶段哈希值
表示包含于表TBL_h并且与所选择的大块C_n的
（C_n）建立了对应的第k个叶页LP_k（h）。在
接着，重复判定部202从哈希表205中选择第h级的表TBL_h
下所述
为物理地址。
参照元表206，由此
大块编号。接着，重
207，由此取得在与该大块
骤S7）
的步骤进行说
值搜索处理的典型的
量h表
判定部202还
H2（C_n）。变量k
第二阶段哈希值H2
步骤S21中，重复判定部202进一步将变量i及j任一个都设定为初
始值0。变量i表示在基于变量h及k而确定的叶页LP_k（h）中包
含的第i个扇区ST_i。变量j表示扇区ST_i内的第j个条目。
（步骤S22）。
在变量h为1的本实施方式中，选择第1级的表TBL_1
着，重复判定部202选择包含于所选择的表TBL_h
C_n的第二阶段哈希值H2（C_n）＝k建立了对
（步骤S23）。在此，因为h为1，所以选
LP_k（1）作为叶页LP_k（h）。在步骤S23
作为表TBL_h。接
并且与所选择的大块
应的第k个叶页LP_k（h）
择表TBL_1的第k个叶页
中，重复判定部202从
读出的叶页LP_k（h）保存
部202将所选择的叶页
HDD123读出所选择的叶页LP_k（h），将该
于存储器122的表区域122b。即重复判定
LP_k（h）载入于存储器122的表区域122b。
接着，重复判定部202选择所选择的（所载入的）叶页LP_k（h）
叶页LP_k（1））的第i个扇区ST_i（步骤S24）。在此，作
ST_i，选择开头（第0个）扇区ST_0。
重复判定部202选择了叶页LP_k（1）（即，存储器122的表区
122b中所保存的叶页LP_k（1））的开头的扇区ST_0时，将该扇
ST_0中包含的管理信息MI1_0也保存于例如存储器122的工作区
122c。由此，重复判定部202仅参照管理信息MI1_0中的使用条
CNT2至CNT7，就能够取得表TBL_2至TBL_7的叶页LP_k
（7）内分别使用着的条目的数目。即，重复判定部202
HDD123读出叶页LP_k（2）至LP_k（7）前取得该叶页
LP_k（7）内分别使用着的条目的数目。另外，重复判
管理信息MI1_0中的使用条目计数CNT1，来取
的条目的数目。
因此，重复判定部202能够基于叶页LP_k（1）至LP_k（7）内
用着的条目的数目（即，管理信息MI1_0中的使用条目计数
CNT7），确定使用着的条目的数目为零的叶页。在此，设使
CNT1至CNT4非零，并设使用条目计数CNT5至CNT7
（在此，
为第i个扇区
域
区
域
目计数
（2）至LP_k
能够在从
LP_k（2）至
定部202也能够基于
得叶页LP_k（1）内使用着
分别使
CNT1至
用条目计数
为零。此情况
下，重复判定部202能够决定为充其量将叶页LP_k（1）
至LP_k（4）作为对象进行哈希值搜索即可。将与该叶页有关的最大
的搜索范围标记为hmax。在该例中，hmax为4，表示将叶页LP_k
（1）作为开头的四个叶页为最大的搜索范围。
同样地，重复判定部202能够基于管理信息MI1_0中的使用条
CNTh（h＝1，2，…，7）确定在叶页LP_k（h）中使用着的
例如，叶页LP_k（1）（h＝1）的各扇区的条目的数目
条目计数CNT1（h＝1）为例如16的情况下，重
定为在叶页LP_k（1）中使用着的扇区的数目为
202能够决定为充其量将叶页LP_k（1）
进行哈希值搜索即可。将与该扇区
目计数
扇区的数目。
是12。因此，使用
复判定部202能够确
2。此情况下，重复判定部
内的扇区ST_0及ST_1作为对象
有关的最大的搜索范围标记为
是通过从在叶页LP_k（1）中使用
imax（h，CNT1）。imax（h，CNT1）
着的扇区的数目减去1而获得的值。
重复判定部202执行步骤S24后进入到步骤S25。在步骤S25中，
定部202从所选择的扇区ST_i的第j个条目中读出第一阶段
（C_x）。接着，重复判定部202对所读出的第一阶段哈希
和通过步骤S1计算出的大块C_n的第一阶段哈希值
（步骤S26）。然后，重复判定部202判定第一
第一阶段哈希值H1（C_n）是否相等（步
如果步骤S27的判定为“是”，则重复判定部202取得包含于扇区
的第j个条目并且与第一阶段哈希值H1（C_x）成对的大块编号
S28）。在步骤S27中，重复判定部202将所取得的大块编号
选择的大块C_n相同内容的大块C_x的大块编号，暂
122的工作区域122c。由此，哈希值搜索处理
定部202进入步骤S8。暂时保存于工作区
重复判
哈希值H1
值H1（C_x）
H1（C_n）进行比较
阶段哈希值H1（C_x）与
骤S27）。
ST_i
（步骤
作为具有与所
时保存于例如存储器
（步骤S7）结束，重复判
域122c的大块C_x的大块
编号在步骤S17中使用。
另一方面，如果步骤S27的判定为“否”，则重复判定部202为了
当与第一阶段哈希值H1（C_n）进行比较的下一第一阶段哈希
入到步骤S29。在步骤S29中，重复判定部202使变量j仅增
重复判定部202判定增加后的变量j是否超过变量j的
如果步骤S30的判定为“否”，则重复判定部202进入到步骤S31。
S31中，重复判定部202判定变量j是否超过jmax（CNT）。
是通过使在叶页LP_k（h）的扇区ST_i中包含的管理
条目计数CNT减1而获得的值（即，“CNT-1”）。
示叶页LP_k（h）的扇区ST_i中的条目涉及的
如果变量j超过jmax（CNT）（即“CNT-1”）（步骤S31的是），
判定部202判定为应当与第一阶段哈希值H1（C_n）进行比较
第一阶段哈希值不存在于哈希表205，因此第一阶段哈希值
哈希表205中登记着的全部第一阶段哈希值不一致。此
202使哈希值搜索处理结束。与之相对，如果变
（步骤S31的否），则重复判定部202为了从
ST_i内的下一条目中读出第一阶段哈希值而
另一方面，如果步骤S30的判定为“是”，则重复判定部202使变
加1（步骤S32）。然后，重复判定部202判定增加后的变量i
过变量i的最大值imax（h）（步骤S33）。变量i的最大值imax
在变量h为例如1时为7（8-1＝7），在变量h为例如2时为15
1）。
取得应
值而进
加1。接着，
最大值jmax（步骤S30）。在本实施方式中，变量j的最大值jmax为
11。
在步骤
jmax（CNT）
信息MIh_i中的使用
即，jmax（CNT）表
最大的搜索范围。
则重复
的新的
H1（C_n）与
情况下，重复判定部
量j未超过jmax（CNT）
叶页LP_k（h）的扇区
返回到步骤S25。
量i增
是否超
（h）
（16-
如果步骤S33的判定为“否”，则重复判定部202进入到步骤S34。
S34中，重复判定部202判定变量i是否超过imax（h，CNTh）。
（h，CNTh）是如前所述那样、通过从在叶页LP_k（h）中使用
区的数目减去1而获得的值。
如果变量i超过imax（h，CNTh）（步骤S34的是），则重复判定
判定为应当与第一阶段哈希值H1（C_n）进行比较的新的第一
希值在哈希表205中不存在，因此第一阶段哈希值H1（C_n）
表205中登记着的全部第一阶段哈希值不一致。此情况下，重
使哈希值搜索处理结束。与之相对，如果变量i超过imax
部202
阶段哈
与哈希
在步骤
imax
着的扇
复判定部202
（h，CNTh）（步骤S34的否），则重复判定部202为了选择叶页
（h）（在此，LP_k（1））的下一扇区而返回到步骤S24。 LP_k
另一方面，如果步骤S33的判定为“是”，则重复判定部202使变
增加1（步骤S35）。然后，重复判定部202判定增加后的变量
超过hmax（步骤S36）。hmax如前所述那样、基于叶页LP_k
的开头的扇区ST_0中包含的管理信息MI1_0中的使用条目计
CNT7而决定。
如果步骤S36的判定为“否”，则重复判定部202为了从哈希表
一表及该下一表内的下一叶页而返回到步骤S22。与之
的判定为“是”，则重复判定部202判定为应当与
进行比较的新的第一阶段哈希值在哈希表
段哈希值H1（C_n）与哈希表205中登记
一致。此情况下，重复判定部202使哈希
接着，参照图15至图18，对通过主机20请求的文件写入的例
量h仅
h是否
（1）
数CNT1至
205中选择下
相对，如果步骤S36
第一阶段哈希值H1（C_n）
205中不存在，因此第一阶
着的全部第一阶段哈希值不
值搜索处理结束。
子进行
说明。图15表示由从主机20依次发送的三个文件写入请求所
F0至F2与通过该文件F0至F2被每隔4K比特划分而取
系的例子。图16表示哈希表205中包含的例如第1级
的变化的例子。图17表示元表206的内容的变化
大块表207的内容的变化的例子。
首先，设存储系统10的运用的开始后，从主机20对存储系统
制器12请求将图15（A）所示的16K比特的文件F0写
逻辑地址La0开始的区域。此情况下，存储控制器12
F0分割成四个大块Ca0、Ca1、Ca2及Ca3。应
Ca3的逻辑地址La1、La2及La3分别是La0
12K。大块Ca0、Ca1、Ca2及Ca3分别具有
生成部203计算大块Ca0、Ca1、Ca2及
H（A）、H（B）、H（C）及H（D）。
在此，设具有与大块Ca0、Ca1、Ca2及Ca3相同内容的其他的
存在。此情况下，访问控制器204将大块Ca0、Ca1、Ca2及
重复管理部201将第一阶段哈希值H（A）、H（B）、H（C）及
与大块编号0、1、2及3的各个对例如如图16（A）所示那
TBL_1。此外，在图16（A）中省略，但这些对被登记
H（B）、H（C）、H（D）各自的第二阶段哈希
TBL_1的叶页。
另外，重复管理部201如图17（A）所示那样、在与逻辑地址
指定的文件
得的大块的关
的表TBL_1的内容
的例子。图18表示
10的存储控
入逻辑卷的从
的分割部200将文件
当写入大块Ca1、Ca2及
＋4K、La0＋8K、La0＋
数据A、B、C及D。哈希
Ca3的哈希值（第一阶段哈希值）
大块不
Ca3写入HDD/SSD阵列11的空区域、例如以物理地址Pa0、Pa1、
Pa2及Pa3指定的物理区域。另外，重复管理部201对大块Ca0、Ca1、
Ca2及Ca3赋予例如大块编号0、1、2及3。
H（D）
样、登记到表
到与哈希值H（A）、
值建立了对应的表
La0、La1、
La2及La3分别建立了对应的元表206的条目中登记大块
Ca2及Ca3的大块编号0、1、2及3。另外，重复管理部
（A）所示那样、在与大块Ca0、Ca1、Ca2及Ca3的大块
及3分别建立了对应的大块表207的条目中登记写入有
Ca2及Ca3的物理区域的物理地址Pa0、Pa1、Pa2
管理部201在大块表207中，对与物理地址Pa0、
别成对的参照计数RCNT任一个都设定1。
Ca0、Ca1、
201如图18
编号0、1、2
大块Ca0、Ca1、
及Pa3。另外，重复
Pa1、Pa2及Pa3分
接着，设从主机20对存储控制器12请求将图15（B）所示的12K
文件F1写入逻辑卷的从逻辑地址Lb0开始的区域。此情况下，
制器12的分割部200将文件F1分割为三个大块Cb0、Cb1及
入大块Cb1及Cb2的逻辑地址Lb1及Lb2分别是Lb0
大块Cb0、Cb1及Cb2分别具有数据X、Y及A。
大块Cb0、Cb1及Cb2的哈希值（第一阶段哈希
（A）。
在此，具有与大块Cb0及Cb1相同内容的其他的大块不存在，
与大块Cb2相同内容（A）的大块Ca0存在。此情况下，访问
大块Cb0及Cb1写入HDD/SSD阵列11的空区域、例
及Pb1指定的物理区域。另一方面，关于大块
的重复，重复管理部201抑制访问控制器
块Cb2。另外，重复管理部201对
编号3的大块编号4及5。另
比特的
存储控
Cb2。应当写
＋4K及Lb0＋8K。
哈希生成部203计算
值）H（X）、H（Y）及H
但具有
控制器204将
如通过物理地址Pb0
Cb2，为了排除与大块Ca0
204向HDD/SSD阵列11写入该大
大块Cb0及Cb1赋予后续于最新的大块
外，对具有与
大块Ca0相同内容（A）的大块Cb2的大块编号使用该
号0。
大块Ca0的大块编
重复管理部201例如如图16（B）所示那样、将第一阶段哈希值
及H（Y）与大块编号4及5的各自的对登记到表TBL_1。
H（X）
另外，重复管
理部201如图17（B）所示那样、在与逻辑地址Lb0、
了对应的元表206的条目中登记大块Cb0、Cb1
0。
Lb1及Lb2分别建立
及Cb2的大块编号4、5及
另外，重复管理部201如图18（B）所示那样、在与大块Cb0
块编号4及5分别建立了对应的大块表207的条目中登记
Cb0及Cb1的物理区域的物理地址Pb0及Pb1。另外，
块表207中，对与物理地址Pb0及Pb1分别成对
都设定1。另外，重复管理部201将与具有
的大块Ca0的大块编号0建立了对应的大
RCNT从如图18（A）所示的1更新为如
接着，设从主机20对存储控制器12请求将如图15（C）所示的
特的文件F2写入逻辑卷的从逻辑地址Lc0开始的区域。此情
制器12的分割部200将文件F2分割为三个大块Cc0、
入大块Cc1及Cc2的逻辑地址Lc1及Lc2分别是
8K。大块Cc0、Cc1及Cc2分别具有数据E、F及
接收大块Cc0、Cc1及Cc2的哈希值（第一阶段
及H（A）。
在此，具有与大块Cc0及Cc1相同内容的其他的大块不存在，
与大块Cc2相同内容（A）的大块Ca0存在。此情况下，访问
大块Cc0及Cc1写入HDD/SSD阵列11的空区域、例
及Pc1指定的物理区域。另一方面，关于大块
的重复，重复管理部201抑制访问控制器
块Cc2。另外，重复管理部201对
编号6的大块编号7及8。另
大块Cc2的大块编号中，使
及Cb1的大
写入有大块
重复管理部201在大
的参照计数RCNT任一个
与大块Cb2相同内容（A）
块表207的条目的参照计数
图18（B）所示的2。
12K比
况下，存储控
Cc1及Cc2。应当写
Lc0＋4K及Lc0＋
A。哈希生成部203
哈希值）H（E）、H（F）
但具有
控制器204将
如通过物理地址Pc0
Cc2，为了排除与大块Ca0
204对HDD/SSD阵列11写入该大
大块Cc0及Cc1赋予后续于最新的大块
外，在具有与大块Ca0相同内容（A）的
用该大块Ca0
的大块编号0。
重复管理部201例如如图16（C）所示那样、将第一阶段哈希值
及H（Y）与大块编号6及7的各自的对登记到表TBL_1。另
部201如图17（C）所示那样、在与逻辑地址Lc0、Lc1
建立了对应的元表206的条目中登记大块Cc0、Cc1及
7及0。
另外，重复管理部201如图18（C）所示那样、在与大块Cc0及
大块编号6及7分别建立了对应的大块表207的条目中登记写
及Cc1的物理区域的物理地址Pc0及Pc1。另外，重复
207中，对与物理地址Pc0及Pc1分别成对的参
定1。另外，重复管理部201将与具有与大
块Ca0的大块编号0建立了对应的大块表
RCNT从图18（B）所示的2更新为图18
在此，设从主机20对存储控制器12请求文件F1的删除。此情
重复管理部201如图17（D）所示那样、使与逻辑地址b0、
建立了对应的元表206的三个条目的内容无效化。在图
示无效条目，对相应的条目附以斜线。为了进行
206的各条目的特定的位用作表示该条目的内容是
重复管理部201将与逻辑地址b0、b1及b2分别建立了对应的元
的三个条目内的各自的有效位任一个都设定为表示该条目的
态（例如“0”）。另外，重复管理部201将与构成被删除
大块Cb0、Cb1及Cb2的大块编号4、5及0分别建立了
207的条目内的参照计数RCNT从图18（C）所示的1、
H（E）
外，重复管理
及Lc2分别
Cc2的大块编号6、
Cc1的
入了大块Cc0
管理部201在大块表
照计数RCNT任一个都设
块Cc2相同内容（A）的大
207的条目内的参照计数
（C）所示的3。
况下，
b1及b2分别
17（D）中，为了表
这种无效化，元表
否有效的有效位。
表206
内容无效的状
的文件F1的
对应的大块表
1及3更新为
图18（D）所示的0、0及2。
在本实施方式中，在这种状态下新的大块被写入到HDD/SSD阵
的情况下，对该新的大块赋予通道编号8。此时，被赋予了通
的有效的大块不存在。因此，在本实施方式中，相应于
12的等待时间或者来自主机20的指示，进行碎片消除处
根据以上说明的至少1个实施方式，能够提供能够使得用于排除
复的哈希表搜索高速化的存储系统、存储控制器及方法。
对本发明的几个实施方式进行了说明，但这些实施方式作为例子
无意限定发明的范围。这些新的实施方式能够以其他各种方
脱离发明的主旨的范围内，能够进行各种省略、置换、
施方式及其变形包含于发明的范围及主旨，并且包含于
记载的发明及其等同的范围。
列11
道编号4及5
存储控制器
理（碎片整理处理；defragmentation）。即，在HDD/SSD阵列11中
保存的有效的大块按照例如每个文件、在该HDD/SSD阵列11的物
理地址连续的区域被进行再配置。此时，对有效的全部大块重新赋予
连续的通道编号。与之相应，哈希表205、元表206及大块表207也
得以更新。
数据重
来提示，
式实施，在不
变更。这些实
与权利要求书