データ分割プログラム
【課題】データ重複排除を実施しつつ、データ圧縮効率を高めることのできるデータ分割手法を提供する。
【解決手段】本発明に係るデータ分割プログラムは、データを分割する位置を判定する際に、データの終端により近い位置を優先して保存しておき、その位置でデータを分割する。
【解決手段】本発明に係るデータ分割プログラムは、データを分割する位置を判定する際に、データの終端により近い位置を優先して保存しておき、その位置でデータを分割する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを分割するプログラムに関するものである。
【背景技術】
【０００２】
コンピュータにデータを格納する際に、重複部分を排除してデータサイズを小さくする処理を施す場合がある。具体的には、データをブロックに分割し、バイト列が同一であるブロックを削除する。
【０００３】
データに重複排除処理を施す例として、データをバックアップする処理が挙げられる。バックアップデータは継続的に蓄積する必要があるため、サイズが大きくなりやすく、したがって重複しているデータを削除するニーズがあるからである。その他、今後はストレージ装置そのものにも重複排除技術が適用される可能性がある。
【０００４】
バックアップデータに対して重複排除処理を実施する場合、まずバックアップするファイルをブロックに分割し、ブロックのハッシュ値をキーとして、適当な手法で圧縮したブロックをバックアップメディアに退避する。また、バックアップデータを取り出すことを容易にするため、各ブロックのハッシュ値をバックアップデータとは別の記憶装置に保持しておく場合もある。
【０００５】
重複排除処理の効果を高めるためには、データを分割して生成した各ブロック同士ができる限り同一となるようにすることが望ましい。そのため、重複排除処理を実施する際には、データをどの位置で分割するかという課題がともなう。
【０００６】
下記特許文献１では、バイト列を先頭から末尾に向かって順次スキャンし、所定長のバイト列のハッシュ値が、あらかじめ定めておいた規定の数値パターンになった時点でバイト列を分割する。予備的な分割条件として、ハッシュ値が規定数値パターンに部分的に一致した場合にも、バイト列を分割することとしている。
【０００７】
下記特許文献２では、バイト列の中に分割枠を設けておき、分割枠内の各分割位置候補の特徴値を求め、各特徴値を比較することにより、分割位置を決定している。
【０００８】
下記特許文献３では、分割位置候補のオフセット、ハッシュ値、その他の特徴値を評価することにより、分割位置を決定している。
【０００９】
下記特許文献４では、バイト列を何らかの方法で分割し、分割したバイト列内に、先に記憶装置へ書き込んだバイト列が含まれるか否かを、ハッシュ値によって判定している。これにより、記憶装置に書込済のバイト列については重複書込しないようにしている。
【００１０】
下記非特許文献１では、データを遠隔コンピュータに複製する技術が記載されている。全データを一括して遠隔複製することは難しいため、対象データを適当な大きさに分割する必要がある。重複しているブロックは複製しなくともよいため、分割位置を適切に定めることにより、複製効率を向上させることができる。同文献では、データを固定長で分割するのではなく、可変長で分割し、重複するブロックを探している。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】US 6,810,398 B2，2004，System and method for unorchestrated determination of data sequence using sticky byte factoring to determine breakpoints in digital sequences
【特許文献２】US 7,504,969 B2，2009，Location-based stream segmentation for data deduplication
【特許文献３】US 2006/0047855 A1，2006，Efficient Chunking Algorithm
【特許文献４】US 6,704,730 B1，2004，Hash file system and method for use in a commonality factoring system
【非特許文献】
【００１２】
【非特許文献１】Andrew Tridgell，Efficient Algorithms for Sorting and Synchronization，Chapter 3 : The rsync algorithm，1999，学位論文，URL：http://samba.org/~tridge/phd_thesis.pdf（２０１１年１月１１日取得）
【発明の概要】
【発明が解決しようとする課題】
【００１３】
重複排除処理の効果を高めるためには、データをブロックに分割する際のブロックサイズをできる限り小さくしたほうがよいと考えられる。サイズが小さいブロックほど、他のブロックと一致する確率が高まるからである。
【００１４】
一方で、データを圧縮する際には、圧縮前のデータサイズが大きいほど、圧縮効率がよいとされる。したがって、上述したバックアップの例のように、データをブロック毎に圧縮して保存する場合には、各ブロックサイズができる限り大きいほうがよいということになる。このことは、重複排除の効率を高めるために必要となる上記要件と相反している。
【００１５】
重複排除とデータ圧縮は、ともに余分なデータを除去する目的があるので、総合的にデータサイズを小さくすることができる手法を優先すべきであると考えられる。特に上述したバックアップの例のように、重複排除とデータ圧縮を双方とも実施する場合には、上記のような相反する要求のバランスをとりつつ、総合的な効果としてデータサイズを小さくすることが肝要である。
【００１６】
また、大容量のデータをバックアップする際には、バックアップ処理の効率も考慮する必要がある。分割ブロックのサイズを小さくすると、重複排除処理の効果は高まる反面、ブロックをバックアップメディアに格納する書込処理の回数が増えるため、結果としてバックアップ処理の時間が増大してしまう。
【００１７】
以上のような理由から、データ重複排除とデータ圧縮のバランスをとることのできるデータ分割手法が望まれる。この点、上記特許文献１〜４および非特許文献１では、重複排除処理のみに着目しており、したがって分割ブロックサイズを大きくするという観点は記載されていない。以下、個別に説明する。
【００１８】
非特許文献１では、あるブロックと重複するブロックを高速に探す方法を記載しているが、その前提として、重複するブロックが多くなるようにデータを分割することについては、明確には開示していない。
【００１９】
特許文献１では、分割条件を複数設け、第１分割条件に該当する分割候補が見つけられなければ、予備的な第２分割条件に該当する位置でデータを分割している。しかし、第１分割条件および第２分割条件ともに、分割ブロックのサイズが大きくなるように明示的に構成されているわけではない。したがって、原則として重複排除処理の効率が高くなるように分割位置を定めるように動作すると思われる。
【００２０】
特許文献２〜３でも、特許文献１と同様に分割ブロックのサイズが大きくなるとは限らない。また、複数の分割位置候補を比較するため、処理負荷が高く、処理効率が求められる用途には向かないと考えられる。
【００２１】
特許文献４では、バイト列が書込済であるか否かを確認するために記憶装置から書込済データを読み取る必要があるので、記憶装置にアクセスする時間が長くなり、処理効率が高くないと考えられる。
【００２２】
本発明は、上記のような課題を解決するためになされたものであり、データ重複排除を実施しつつ、データ圧縮効率を高めることのできるデータ分割手法を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明に係るデータ分割プログラムは、データを分割する位置を判定する際に、データの終端により近い位置を優先して保存しておき、その位置でデータを分割する。
【発明の効果】
【００２４】
本発明に係るデータ分割プログラムでは、データ重複排除を実施するためのデータ分割を実施する過程で、データの終端により近い位置が優先的に用いられるので、データ圧縮の効果を高める方向に処理を振り向けつつ、データ重複排除を実施することができる。これにより、データ重複排除とデータ圧縮のバランスをとり、データサイズを小さくする効果を総合的に最適化することができる。また、これにより、バックアップ処理の時間を総合的に短縮することができる。
【図面の簡単な説明】
【００２５】
【図１】実施形態１に係るデータ分割装置１００の機能ブロック図である。
【図２】データ分割装置１００がデータを分割する処理を記述したプログラムである。
【図３】データ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。
【図４】実施形態２に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。
【図５】実施形態３に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。
【図６】実施形態４においてデータ分割部１３０とデータ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。
【発明を実施するための形態】
【００２６】
＜実施の形態１＞
図１は、本発明の実施形態１に係るデータ分割装置１００の機能ブロック図である。データ分割装置１００は、データを分割する処理を実施する装置であり、データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０を備える。
【００２７】
データ読取部１１０は、ファイルサーバ２００などのデータソースから、分割対象となるデータを読み取る。分割条件判定部１２０は、データ読取部１１０が読み取ったデータを順次取得し、データを分割する条件に該当するか否かを判定する。データ分割部１３０は、分割条件判定部１２０が判定した条件に該当する位置で、データをブロックに分割する。データ格納部１４０は、データ分割部１３０がデータ分割によって生成したデータブロックのハッシュ値を計算し、バックアップ装置４００に格納する。また、データブロックとハッシュ値を対応付けてブロックＤＢ３００に格納する。
【００２８】
ブロックＤＢ３００は、データ分割部１３０が元のデータを分割して生成したデータブロックを記憶するデータベースである。ブロックＤＢ３００は、ハードディスクなどの記憶装置を用いて構成することができる。バックアップ装置４００は、データ格納部１４０が生成したハッシュ値を記憶する記憶装置である。
【００２９】
データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０は、個別の機能部として構成することもできるし、一体的に構成することもできる。
【００３０】
データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０は、これらの機能を実現する回路デバイスなどのハードウェアとして構成することもできるし、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などの演算装置とその動作を規定するプログラムによって構成することもできる。以下では主にプログラムによってこれら機能部を構成した例を説明する。
【００３１】
図２は、データ分割装置１００がデータを分割する処理を記述したプログラムである。説明の便宜上、ステップ番号を併記した。以下、図２の各ステップについて説明する。
【００３２】
（図２：ステップ２００）
データ分割装置１００は、データ読取部１１０が読み取ったデータ全てに対して、以下のステップ２１０〜２２３を実施する。データ全てに対して処理を終えていない場合は、「ｓｔａｒｔ」マーカを目印にして本ステップに戻り、同様の処理を繰り返す。データ読取部１１０が読み取ったデータは、変数blockStartが示すメモリアドレスから、変数blockEndが示すメモリアドレスの１つ手前のアドレスまでに、バイト列として格納されているものとする。
【００３３】
（図２：ステップ２１０）
分割条件判定部１２０は、blockEnd <= blockStartが成り立てば処理を終了する。blockStart変数は、以下のステップにおいて逐次更新される。本ステップは、分割対象であるバイト列の長さが０となったことを確認し、処理を終了すべきか否かを判断するためのものである。
【００３４】
（図２：ステップ２１１）
分割条件判定部１２０は、blockEnd <= blockStart + blockMinが成り立つか否かを判断する。成り立つ場合、データ格納部１４０は、blockStartとblockEnd間のブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じブロックのハッシュ値を計算し、バックアップ装置４００に格納する。データ格納部１４０が実施する上記処理は、関数bdb内に記述されている。同関数の詳細は、後述の図３で改めて説明する。
【００３５】
（図２：ステップ２１１：補足）
blockMinは、分割後ブロックの最小サイズである。したがって本ステップは、分割対象となるバイト列が最小サイズ以下になっているか否かを判定していることになる。対象バイト列が最小サイズ以下であれば、処理がデータの終端近くまで進んでおり、残りバイト列は僅かであることになるので、以下のステップを実施する意義はあまりない。そこで、残りバイト列についてはそのままブロックＤＢ３００に格納することとした。
【００３６】
（図２：ステップ２１２）
分割条件判定部１２０は、変数cP1と変数cP2を０で初期化する。変数cP1は、データを分割する条件である第１分割条件に該当するデータアドレスを保持するための変数である。変数cP2は、データを分割する条件である第２分割条件に該当するデータアドレスを保持するための変数である。
【００３７】
（図２：ステップ２１３）
分割条件判定部１２０は、分割位置を探す際に使用するアドレス変数cPを初期化する。最初の位置は、最小ブロックサイズに相当する位置よりも１バイト先のアドレスとする。以下、各機能部は、ファイルサーバ２００から取得したデータを１バイトずつ順次読み取りながら、以下の処理を実施する。
【００３８】
（図２：ステップ２１４）
分割条件判定部１２０は、cP < blockEndが満たされる間、すなわち、アドレス変数cPが分割対象データの最後に到達するまで、ステップ２１５〜２２３の処理を繰り返す。
【００３９】
（図２：ステップ２１５）
分割条件判定部１２０は、分割条件に該当するか否かを判定するために用いる特徴値hashを求める。特徴値hashを求める処理は、関数crcに記述されている。関数crcの処理内容としては、任意の公知技術を用いることができる。
【００４０】
（図２：ステップ２１５：補足）
関数crcの処理内容として、例えば指定されたアドレスから所定長手前のバイト列について巡回冗長検査値やハッシュ値を求め、その値を特徴値hashとして用いることが考えられる。
【００４１】
（図２：ステップ２１６）
分割条件判定部１２０は、特徴値hashが第１分割条件を満たすか否かを検査する。第１分割条件は、関数pattern1に記述されている。特徴値hashが第１分割条件を満たす場合は、変数cP1に現在のデータアドレスcPをセットし、ステップ２１９に進む。第１分割条件を満たさない場合は、ステップ２１７へ進む。
【００４２】
（図２：ステップ２１６：補足）
第１分割条件としては、例えば特徴値hashの部分ビットパターンが特定のビットパターンと一致するか否か、などが考えられる。その他、特徴値hashをある特定の値で割った余りが規定値に一致するか否か、などが考えられる。以下で説明する第２分割条件および第３分割条件も同様である。
【００４３】
（図２：ステップ２１７）
分割条件判定部１２０は、特徴値hashが第２分割条件を満たすか否かを検査する。第２分割条件は、関数pattern2に記述されている。第２分割条件は、ステップ２１６における第１分割条件とは異なる条件とする。特徴値hashが第２分割条件を満たす場合は、変数cP2に現在のデータアドレスcPをセットし、ステップ２１９に進む。第２分割条件を満たさない場合は、ステップ２１８へ進む。
【００４４】
（図２：ステップ２１８）
分割条件判定部１２０は、特徴値hashが第３分割条件を満たすか否かを検査する。第３分割条件は、関数pattern3に記述されている。第３分割条件は、ステップ２１６における第１分割条件およびステップ２１７における第２分割条件とは異なる条件とする。特徴値hashが第３分割条件を満たす場合は、変数cP2に現在のデータアドレスcPをセットする。
【００４５】
（図２：ステップ２１９）
データ分割部１３０は、変数cP1がセットされている（0でない）か否かを検査する。変数cP1がセットされていれば、ステップ２１６で第１分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP1の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP1として、ステップ２１０に戻る。変数cP1がセットされていない場合はステップ２２０に進む。
【００４６】
（図２：ステップ２２０）
データ分割部１３０は、アドレスcP（分割条件を判定している現アドレス）が、分割後ブロックの最大サイズに相当する位置（blockStart + blockMax）に達しているか否かを検査する。最大サイズに相当する位置に達していればステップ２２１に進み、達していなければステップ２２３にスキップする。
【００４７】
（図２：ステップ２２１）
データ分割部１３０は、変数cP2がセットされている（0でない）か否かを検査する。変数cP2がセットされていれば、ステップ２１７における第２分割条件またはステップ２１８における第３分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP2の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP2として、ステップ２１０に戻る。変数cP2がセットされていない場合はステップ２２２に進む。
【００４８】
（図２：ステップ２２２）
データ分割部１３０は、アドレスblockStartとアドレスcPの間でデータをデータブロック（ステップ２２０の条件により、分割ブロックの最大サイズとなっている）に分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cPとして、ステップ２１０に戻る。
【００４９】
（図２：ステップ２２３）
データ分割部１３０は、アドレスcPを１バイト前（データの終端に向かう方向）に進め、ステップ２１５に戻る。
【００５０】
（図２：ステップ２２５）
データ分割部１３０は、アドレスblockStartとアドレスblockEndの間の残ったデータをデータブロックとして取り出す。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。本ステップは、分割後ブロックの最大サイズに相当する位置まで第１分割条件に該当する位置がみつからなかった場合の処理である。
【００５１】
図３は、データ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。以下、図３の各ステップについて説明する。
【００５２】
（図３：ステップＳ３０１）
データ格納部１４０は、ブロックＤＢ３００に格納する対象となっているデータブロックのハッシュ値を計算する。衝突する確率が低いハッシュ関数を用いることが望ましい。例えば、SHA-1、SHA-256などのハッシュ関数を用いることができる。
【００５３】
（図３：ステップＳ３０２）
データ格納部１４０は、ステップＳ３０１でデータ格納部１４０が求めたハッシュ値をキーにして、同じ内容のデータブロックが既にブロックＤＢ３００へ登録されているか否かを検索する。
【００５４】
（図３：ステップＳ３０３）
ステップＳ３０２でキーが見つかった場合は、データ格納部１４０はハッシュ値をバックアップ装置４００に出力し、本処理フローを終了する。
【００５５】
（図３：ステップＳ３０４）
ステップＳ３０２でキーが見つからなかった場合は、データ格納部１４０はハッシュ値をバックアップ装置４００に出力し、ハッシュ値をキーにしてデータブロックをブロックＤＢ３００に格納する。ブロックＤＢ３００に格納するデータブロックは、適当なアルゴリズムを用いて圧縮することが望ましい。
【００５６】
（図３：ステップＳ３０３〜Ｓ３０４：補足）
これらステップにおいてハッシュ値をキーにしているのは、ステップＳ３０４でブロックＤＢ３００にデータブロックを格納する際に、データブロックを圧縮する場合があるからである。データブロックを圧縮してからブロックＤＢ３００に格納する場合、既にブロックＤＢ３００に格納されているデータブロックと新たなデータブロックが同一であるか否かは、圧縮を解かない限り分からないため、処理負担が重くなる。そこで、ハッシュ値が一致するか否かによって簡易的に同一判定できるようにしているのである。
【００５７】
＜実施の形態１：まとめ＞
以上のように、本実施形態１に係るデータ分割装置１００は、第２分割条件に該当するデータ位置のうち、データの終端にできる限り近い分割位置を優先してデータを分割するように構成されている。これにより、重複排除処理のためのデータ分割を実施しつつ、分割後のデータブロックサイズができる限り大きくなるように処理方針を方向付けていることになるので、結果としてデータ重複排除とデータ圧縮をバランスよく両立させることができる。
【００５８】
具体的には、第１分割条件に該当する分割位置が見つからない場合には、第２分割条件に該当するできるだけ終端に近い分割位置を変数cP2に保存しておき、ステップ２２１でblockStartからcP2までのデータブロックをブロックＤＢ３００に書き込む。この処理手順により、最後に残ったcP2の値は、できる限りデータ終端に近い位置となる。
【００５９】
また、データブロックが第１分割条件と第２分割条件いずれにも該当しない場合には、ステップ２２２で分割後ブロックの最大サイズblockMaxのデータブロックをブロックＤＢ３００に格納するようにしている。これにより、重複排除に適していないデータブロックはデータ圧縮を優先してできる限り大きなサイズのデータブロックを格納することになるので、重複排除効果を発揮できないとしても、データ圧縮効果でこれを補い、総合的にデータサイズを小さくすることができる。
【００６０】
＜実施の形態２＞
本発明の実施形態２では、実施形態１と同様にできる限りデータ終端に近い位置でデータを分割する手法を説明する。本実施形態２では、分割するデータを終端から先頭に向かって順次読み取り、分割条件に合致した時点でデータを分割する。データ分割装置１００の構成は実施形態１と同様であるため、以下では差異点を中心に説明する。
【００６１】
図４は、本実施形態２に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。説明の便宜上、ステップ番号を併記した。以下、図４の各ステップについて説明する。
【００６２】
（図４：ステップ４００〜４１２）
これらのステップは、図２のステップ２００〜２１２と同様である。
【００６３】
（図４：ステップ４１３）
分割条件判定部１２０は、blockStart + blockMax <= blockEndが成立する場合は、分割位置を探す際に使用するアドレス変数cPを、分割後ブロックの最大サイズに相当する位置に初期化する。
【００６４】
（図４：ステップ４１４）
分割条件判定部１２０は、ステップ４１３の条件式が成立しない場合は、変数cPをデータブロックの末尾位置に初期化する。
【００６５】
（図４：ステップ４１３〜４１４：補足）
これらのステップでは、条件判定する位置cPを、データブロックのできるだけ後方の位置に初期設定していることになる。
【００６６】
（図４：ステップ４１５）
分割条件判定部１２０は、cP >= blockStart + blockMinが満たされる間、すなわちアドレスcPがデータブロックの末尾から最小ブロックサイズに相当する位置に達するまで、ステップ４１６からステップ４２１までの処理を繰り返す。
【００６７】
（図４：ステップ４１６〜４１７）
これらのステップは、図２のステップ２１５〜２１６と同様である。
【００６８】
（図４：ステップ４１８〜４１９）
これらのステップは、図２のステップ２１７〜２１８と同様である。ただし、分割条件判定部１２０は、第２分割条件pattern2と第３分割条件pattern3を判定する前に、アドレスcP2がセットされているか否か（値が０）を判定する。これは、本実施形態２ではデータブロックの末尾から先頭に向かってデータを読み取っていくため、最初に見つかったcP2の値が最もデータブロック末尾に近いからである。すなわち、できる限りデータブロックの末尾に近い位置でデータ分割するという観点では、cP2が既に見つかっていればその値を更新する必要はなく、cP2が空である場合に限り値をセットする必要があるからである。
【００６９】
（図４：ステップ４２０）
本ステップは、図２のステップ２１９と同様である。
【００７０】
（図４：ステップ４２１）
データ分割部１３０は、アドレスcPを１バイト後ろ（データの先頭に向かう方向）に進め、ステップ４１６に戻る。
【００７１】
（図４：ステップ４２３）
本ステップに到達した時点で変数cP2がセットされている場合、ステップ４１５〜４２１のループ内では、第１判定条件に合致する位置が見つからず、第２判定条件に合致する位置のみが見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP2の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP2として、ステップ４１０に戻る。
【００７２】
（図４：ステップ４２４）
ステップ４２３で変数cP2がセットされていない場合、ステップ４１５〜４２１のループ内では、第１判定条件と第２分割条件いずれも合致する位置が見つからなかったことになるので、分割後ブロックの最小サイズでデータブロックを分割する。データ分割部１３０は、アドレスblockStartとアドレスblockStart + blockMinの間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、アドレスblockStartをblockMinだけインクリメントして、ステップ４１０に戻る。
【００７３】
＜実施の形態２：まとめ＞
以上のように、本実施形態２に係るデータ分割装置１００は、データの終端から先頭に向かって順次データを読み取り、第２分割条件に該当するできるだけ終端に近い分割位置を変数cP2に保存しておく。ステップ４２３では、blockStartからcP2までのデータブロックをブロックＤＢ３００に書き込む。この処理手順により、最後に残ったcP2の値は、できる限りデータ終端に近い位置となる。
【００７４】
また、データブロックが第１分割条件と第２分割条件いずれにも該当しない場合には、ステップ４２４で分割後ブロックの最小サイズblockMinのデータブロックをブロックＤＢ３００に格納するようにしている。これにより、重複排除に適していないデータブロックでも、少なくとも最小サイズblockMinのデータブロックを格納することになるので、最低限のデータ圧縮効果を発揮することができる。
【００７５】
なお、ステップ４２４において、最大サイズblockMaxのデータブロックをブロックＤＢ３００に格納するようにしてもよい。これは、図２のステップ２２２と同様の処理を採用したものといえる。
【００７６】
＜実施の形態３＞
実施形態１〜２では、第１分割条件と第２分割条件のみを用いているが、より多くの分割条件を判定するようにすることもできる。本発明の実施形態３では、第１分割条件、第２分割条件、第３分割条件のいずれかに該当する位置でデータを分割する。データ分割装置１００の構成は実施形態１と同様であるため、以下では差異点を中心に説明する。
【００７７】
図５は、本実施形態３に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。ここでは、実施形態１の図２で説明したプログラムに加えて、第３分割条件に合致する位置でデータ分割する処理を新たに設けた例を示すが、実施形態２の図４で説明したプログラムに加えて第３判定条件を設けることもできる。以下、図２で説明したプログラムと異なる部分を中心に説明する。
【００７８】
（図５：ステップ５１２）
分割条件判定部１２０は、変数cP1、変数cP2、変数cP3を０で初期化する。変数cP3は、データを分割する条件である第３分割条件に該当するデータアドレスを保持するための変数である。
【００７９】
（図５：ステップ５１８）
分割条件判定部１２０は、特徴値hashが第３分割条件を満たす場合は、変数cP3に現在のデータアドレスcPをセットする。実施形態１〜２では、第３分割条件に合致する場合は変数cP2にデータアドレスcPを格納しているため、第１分割条件と第２分割条件のうちいずれかを採用していた。本実施形態３では、この選択肢に加えて新たに第３分割条件を設けた点が異なる。
【００８０】
（図５：ステップ５２２）
データ分割部１３０は、変数cP3がセットされている（0でない）か否かを検査する。変数cP3がセットされていれば、ステップ５１８における第３分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP3の間でデータをデータブロックに分割する。データ格納部１４０は、データブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP3として、ステップ５１０に戻る。変数cP3がセットされていない場合はステップ５２３に進む。
【００８１】
＜実施の形態３：まとめ＞
以上のように、本実施形態３に係るデータ分割装置１００は、第１分割条件、第２分割条件、第３分割条件の順に分割条件を判定し、いずれかに該当した位置でデータを分割する。これにより、実施形態１〜２よりも細かな分割条件を設定することができる。
【００８２】
＜実施の形態４＞
本発明の実施形態４では、データブロックのハッシュ値に加えてデータブロックの固有識別番号をブロックＤＢ３００とバックアップ装置４００に格納する動作例を説明する。これにより、ハッシュ値が衝突した場合でもブロックＤＢ３００やバックアップ装置４００に格納しているデータを破壊しないようにすることを図る。その他の構成は実施形態１〜３と同様であるため、以下では差異点を中心に説明する。
【００８３】
図６は、本実施形態４においてデータ分割部１３０とデータ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。以下、図６の各ステップについて説明する。
【００８４】
（図６：ステップＳ６０１）
本ステップは、図３のステップＳ３０１と同様である。
【００８５】
（図６：ステップＳ６０２）
データ格納部１４０は、データブロックを固有に識別する固有識別番号を、０で初期化する。
【００８６】
（図６：ステップＳ６０３）
データ格納部１４０は、ステップＳ６０１でデータ格納部１４０が求めたハッシュ値とデータブロックの固有識別番号をキーにして、同じ内容のデータブロックが既にブロックＤＢ３００へ登録されているか否かを検索する。
【００８７】
（図６：ステップＳ６０４）
ステップＳ６０３でキーが見つかった場合は、データ格納部１４０は対応するデータブロックをブロックＤＢ３００から取り出し、処理対象になっているデータブロックと同一内容であるか否か比較する。同一であればハッシュ値と固有識別番号をバックアップ装置４００に出力し、本処理フローを終了する。同一でなければ固有識別番号を１つインクリメントしてステップＳ６０３に戻る。
【００８８】
（図６：ステップＳ６０５）
ステップＳ６０３でキーが見つからなかった場合は、データ格納部１４０はハッシュ値と固有識別番号をバックアップ装置４００に出力し、データ格納部１４０はハッシュ値と固有識別番号をキーにしてデータブロックをブロックＤＢ３００に格納する。ブロックＤＢ３００に格納するデータブロックは、適当なアルゴリズムを用いて圧縮することが望ましい。
【００８９】
＜実施の形態４：まとめ＞
以上のように、本実施形態４に係るデータ分割装置１００は、ハッシュ値が衝突する場合であっても、固有識別番号によってデータブロックを一意に識別することができる。これにより、ハッシュ値が衝突した場合でもブロックＤＢ３００やバックアップ装置４００に格納しているデータを破壊しないようにすることができる。
【００９０】
＜実施の形態５＞
以上の実施形態１〜４において、データ分割装置１００は、データ読取部１１０がファイルサーバ２００からデータを読み取った時点で、そのデータが圧縮または暗号化されているか否かを判断し、圧縮または暗号化されている場合は図２〜図６で説明した処理を省略してそのデータをそのままブロックＤＢ３００に格納するようにしてもよい。圧縮または暗号化されているデータに対してさらに重複排除処理やデータ圧縮処理をしても、大きな効果は見込めないと考えられるからである。
【００９１】
図２〜図６で説明した処理を省略する場合は、データ全体を１つのデータブロックとして取り扱い、ハッシュ値はデータ全体に対して計算することになる。
【符号の説明】
【００９２】
１００：データ分割装置、１１０：データ読取部、１２０：分割条件判定部、１３０：データ分割部、１４０：データ格納部、２００：ファイルサーバ、３００：ブロックＤＢ、４００：バックアップ装置。
【技術分野】
【０００１】
本発明は、データを分割するプログラムに関するものである。
【背景技術】
【０００２】
コンピュータにデータを格納する際に、重複部分を排除してデータサイズを小さくする処理を施す場合がある。具体的には、データをブロックに分割し、バイト列が同一であるブロックを削除する。
【０００３】
データに重複排除処理を施す例として、データをバックアップする処理が挙げられる。バックアップデータは継続的に蓄積する必要があるため、サイズが大きくなりやすく、したがって重複しているデータを削除するニーズがあるからである。その他、今後はストレージ装置そのものにも重複排除技術が適用される可能性がある。
【０００４】
バックアップデータに対して重複排除処理を実施する場合、まずバックアップするファイルをブロックに分割し、ブロックのハッシュ値をキーとして、適当な手法で圧縮したブロックをバックアップメディアに退避する。また、バックアップデータを取り出すことを容易にするため、各ブロックのハッシュ値をバックアップデータとは別の記憶装置に保持しておく場合もある。
【０００５】
重複排除処理の効果を高めるためには、データを分割して生成した各ブロック同士ができる限り同一となるようにすることが望ましい。そのため、重複排除処理を実施する際には、データをどの位置で分割するかという課題がともなう。
【０００６】
下記特許文献１では、バイト列を先頭から末尾に向かって順次スキャンし、所定長のバイト列のハッシュ値が、あらかじめ定めておいた規定の数値パターンになった時点でバイト列を分割する。予備的な分割条件として、ハッシュ値が規定数値パターンに部分的に一致した場合にも、バイト列を分割することとしている。
【０００７】
下記特許文献２では、バイト列の中に分割枠を設けておき、分割枠内の各分割位置候補の特徴値を求め、各特徴値を比較することにより、分割位置を決定している。
【０００８】
下記特許文献３では、分割位置候補のオフセット、ハッシュ値、その他の特徴値を評価することにより、分割位置を決定している。
【０００９】
下記特許文献４では、バイト列を何らかの方法で分割し、分割したバイト列内に、先に記憶装置へ書き込んだバイト列が含まれるか否かを、ハッシュ値によって判定している。これにより、記憶装置に書込済のバイト列については重複書込しないようにしている。
【００１０】
下記非特許文献１では、データを遠隔コンピュータに複製する技術が記載されている。全データを一括して遠隔複製することは難しいため、対象データを適当な大きさに分割する必要がある。重複しているブロックは複製しなくともよいため、分割位置を適切に定めることにより、複製効率を向上させることができる。同文献では、データを固定長で分割するのではなく、可変長で分割し、重複するブロックを探している。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】US 6,810,398 B2，2004，System and method for unorchestrated determination of data sequence using sticky byte factoring to determine breakpoints in digital sequences
【特許文献２】US 7,504,969 B2，2009，Location-based stream segmentation for data deduplication
【特許文献３】US 2006/0047855 A1，2006，Efficient Chunking Algorithm
【特許文献４】US 6,704,730 B1，2004，Hash file system and method for use in a commonality factoring system
【非特許文献】
【００１２】
【非特許文献１】Andrew Tridgell，Efficient Algorithms for Sorting and Synchronization，Chapter 3 : The rsync algorithm，1999，学位論文，URL：http://samba.org/~tridge/phd_thesis.pdf（２０１１年１月１１日取得）
【発明の概要】
【発明が解決しようとする課題】
【００１３】
重複排除処理の効果を高めるためには、データをブロックに分割する際のブロックサイズをできる限り小さくしたほうがよいと考えられる。サイズが小さいブロックほど、他のブロックと一致する確率が高まるからである。
【００１４】
一方で、データを圧縮する際には、圧縮前のデータサイズが大きいほど、圧縮効率がよいとされる。したがって、上述したバックアップの例のように、データをブロック毎に圧縮して保存する場合には、各ブロックサイズができる限り大きいほうがよいということになる。このことは、重複排除の効率を高めるために必要となる上記要件と相反している。
【００１５】
重複排除とデータ圧縮は、ともに余分なデータを除去する目的があるので、総合的にデータサイズを小さくすることができる手法を優先すべきであると考えられる。特に上述したバックアップの例のように、重複排除とデータ圧縮を双方とも実施する場合には、上記のような相反する要求のバランスをとりつつ、総合的な効果としてデータサイズを小さくすることが肝要である。
【００１６】
また、大容量のデータをバックアップする際には、バックアップ処理の効率も考慮する必要がある。分割ブロックのサイズを小さくすると、重複排除処理の効果は高まる反面、ブロックをバックアップメディアに格納する書込処理の回数が増えるため、結果としてバックアップ処理の時間が増大してしまう。
【００１７】
以上のような理由から、データ重複排除とデータ圧縮のバランスをとることのできるデータ分割手法が望まれる。この点、上記特許文献１〜４および非特許文献１では、重複排除処理のみに着目しており、したがって分割ブロックサイズを大きくするという観点は記載されていない。以下、個別に説明する。
【００１８】
非特許文献１では、あるブロックと重複するブロックを高速に探す方法を記載しているが、その前提として、重複するブロックが多くなるようにデータを分割することについては、明確には開示していない。
【００１９】
特許文献１では、分割条件を複数設け、第１分割条件に該当する分割候補が見つけられなければ、予備的な第２分割条件に該当する位置でデータを分割している。しかし、第１分割条件および第２分割条件ともに、分割ブロックのサイズが大きくなるように明示的に構成されているわけではない。したがって、原則として重複排除処理の効率が高くなるように分割位置を定めるように動作すると思われる。
【００２０】
特許文献２〜３でも、特許文献１と同様に分割ブロックのサイズが大きくなるとは限らない。また、複数の分割位置候補を比較するため、処理負荷が高く、処理効率が求められる用途には向かないと考えられる。
【００２１】
特許文献４では、バイト列が書込済であるか否かを確認するために記憶装置から書込済データを読み取る必要があるので、記憶装置にアクセスする時間が長くなり、処理効率が高くないと考えられる。
【００２２】
本発明は、上記のような課題を解決するためになされたものであり、データ重複排除を実施しつつ、データ圧縮効率を高めることのできるデータ分割手法を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明に係るデータ分割プログラムは、データを分割する位置を判定する際に、データの終端により近い位置を優先して保存しておき、その位置でデータを分割する。
【発明の効果】
【００２４】
本発明に係るデータ分割プログラムでは、データ重複排除を実施するためのデータ分割を実施する過程で、データの終端により近い位置が優先的に用いられるので、データ圧縮の効果を高める方向に処理を振り向けつつ、データ重複排除を実施することができる。これにより、データ重複排除とデータ圧縮のバランスをとり、データサイズを小さくする効果を総合的に最適化することができる。また、これにより、バックアップ処理の時間を総合的に短縮することができる。
【図面の簡単な説明】
【００２５】
【図１】実施形態１に係るデータ分割装置１００の機能ブロック図である。
【図２】データ分割装置１００がデータを分割する処理を記述したプログラムである。
【図３】データ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。
【図４】実施形態２に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。
【図５】実施形態３に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。
【図６】実施形態４においてデータ分割部１３０とデータ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。
【発明を実施するための形態】
【００２６】
＜実施の形態１＞
図１は、本発明の実施形態１に係るデータ分割装置１００の機能ブロック図である。データ分割装置１００は、データを分割する処理を実施する装置であり、データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０を備える。
【００２７】
データ読取部１１０は、ファイルサーバ２００などのデータソースから、分割対象となるデータを読み取る。分割条件判定部１２０は、データ読取部１１０が読み取ったデータを順次取得し、データを分割する条件に該当するか否かを判定する。データ分割部１３０は、分割条件判定部１２０が判定した条件に該当する位置で、データをブロックに分割する。データ格納部１４０は、データ分割部１３０がデータ分割によって生成したデータブロックのハッシュ値を計算し、バックアップ装置４００に格納する。また、データブロックとハッシュ値を対応付けてブロックＤＢ３００に格納する。
【００２８】
ブロックＤＢ３００は、データ分割部１３０が元のデータを分割して生成したデータブロックを記憶するデータベースである。ブロックＤＢ３００は、ハードディスクなどの記憶装置を用いて構成することができる。バックアップ装置４００は、データ格納部１４０が生成したハッシュ値を記憶する記憶装置である。
【００２９】
データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０は、個別の機能部として構成することもできるし、一体的に構成することもできる。
【００３０】
データ読取部１１０、分割条件判定部１２０、データ分割部１３０、データ格納部１４０は、これらの機能を実現する回路デバイスなどのハードウェアとして構成することもできるし、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などの演算装置とその動作を規定するプログラムによって構成することもできる。以下では主にプログラムによってこれら機能部を構成した例を説明する。
【００３１】
図２は、データ分割装置１００がデータを分割する処理を記述したプログラムである。説明の便宜上、ステップ番号を併記した。以下、図２の各ステップについて説明する。
【００３２】
（図２：ステップ２００）
データ分割装置１００は、データ読取部１１０が読み取ったデータ全てに対して、以下のステップ２１０〜２２３を実施する。データ全てに対して処理を終えていない場合は、「ｓｔａｒｔ」マーカを目印にして本ステップに戻り、同様の処理を繰り返す。データ読取部１１０が読み取ったデータは、変数blockStartが示すメモリアドレスから、変数blockEndが示すメモリアドレスの１つ手前のアドレスまでに、バイト列として格納されているものとする。
【００３３】
（図２：ステップ２１０）
分割条件判定部１２０は、blockEnd <= blockStartが成り立てば処理を終了する。blockStart変数は、以下のステップにおいて逐次更新される。本ステップは、分割対象であるバイト列の長さが０となったことを確認し、処理を終了すべきか否かを判断するためのものである。
【００３４】
（図２：ステップ２１１）
分割条件判定部１２０は、blockEnd <= blockStart + blockMinが成り立つか否かを判断する。成り立つ場合、データ格納部１４０は、blockStartとblockEnd間のブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じブロックのハッシュ値を計算し、バックアップ装置４００に格納する。データ格納部１４０が実施する上記処理は、関数bdb内に記述されている。同関数の詳細は、後述の図３で改めて説明する。
【００３５】
（図２：ステップ２１１：補足）
blockMinは、分割後ブロックの最小サイズである。したがって本ステップは、分割対象となるバイト列が最小サイズ以下になっているか否かを判定していることになる。対象バイト列が最小サイズ以下であれば、処理がデータの終端近くまで進んでおり、残りバイト列は僅かであることになるので、以下のステップを実施する意義はあまりない。そこで、残りバイト列についてはそのままブロックＤＢ３００に格納することとした。
【００３６】
（図２：ステップ２１２）
分割条件判定部１２０は、変数cP1と変数cP2を０で初期化する。変数cP1は、データを分割する条件である第１分割条件に該当するデータアドレスを保持するための変数である。変数cP2は、データを分割する条件である第２分割条件に該当するデータアドレスを保持するための変数である。
【００３７】
（図２：ステップ２１３）
分割条件判定部１２０は、分割位置を探す際に使用するアドレス変数cPを初期化する。最初の位置は、最小ブロックサイズに相当する位置よりも１バイト先のアドレスとする。以下、各機能部は、ファイルサーバ２００から取得したデータを１バイトずつ順次読み取りながら、以下の処理を実施する。
【００３８】
（図２：ステップ２１４）
分割条件判定部１２０は、cP < blockEndが満たされる間、すなわち、アドレス変数cPが分割対象データの最後に到達するまで、ステップ２１５〜２２３の処理を繰り返す。
【００３９】
（図２：ステップ２１５）
分割条件判定部１２０は、分割条件に該当するか否かを判定するために用いる特徴値hashを求める。特徴値hashを求める処理は、関数crcに記述されている。関数crcの処理内容としては、任意の公知技術を用いることができる。
【００４０】
（図２：ステップ２１５：補足）
関数crcの処理内容として、例えば指定されたアドレスから所定長手前のバイト列について巡回冗長検査値やハッシュ値を求め、その値を特徴値hashとして用いることが考えられる。
【００４１】
（図２：ステップ２１６）
分割条件判定部１２０は、特徴値hashが第１分割条件を満たすか否かを検査する。第１分割条件は、関数pattern1に記述されている。特徴値hashが第１分割条件を満たす場合は、変数cP1に現在のデータアドレスcPをセットし、ステップ２１９に進む。第１分割条件を満たさない場合は、ステップ２１７へ進む。
【００４２】
（図２：ステップ２１６：補足）
第１分割条件としては、例えば特徴値hashの部分ビットパターンが特定のビットパターンと一致するか否か、などが考えられる。その他、特徴値hashをある特定の値で割った余りが規定値に一致するか否か、などが考えられる。以下で説明する第２分割条件および第３分割条件も同様である。
【００４３】
（図２：ステップ２１７）
分割条件判定部１２０は、特徴値hashが第２分割条件を満たすか否かを検査する。第２分割条件は、関数pattern2に記述されている。第２分割条件は、ステップ２１６における第１分割条件とは異なる条件とする。特徴値hashが第２分割条件を満たす場合は、変数cP2に現在のデータアドレスcPをセットし、ステップ２１９に進む。第２分割条件を満たさない場合は、ステップ２１８へ進む。
【００４４】
（図２：ステップ２１８）
分割条件判定部１２０は、特徴値hashが第３分割条件を満たすか否かを検査する。第３分割条件は、関数pattern3に記述されている。第３分割条件は、ステップ２１６における第１分割条件およびステップ２１７における第２分割条件とは異なる条件とする。特徴値hashが第３分割条件を満たす場合は、変数cP2に現在のデータアドレスcPをセットする。
【００４５】
（図２：ステップ２１９）
データ分割部１３０は、変数cP1がセットされている（0でない）か否かを検査する。変数cP1がセットされていれば、ステップ２１６で第１分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP1の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP1として、ステップ２１０に戻る。変数cP1がセットされていない場合はステップ２２０に進む。
【００４６】
（図２：ステップ２２０）
データ分割部１３０は、アドレスcP（分割条件を判定している現アドレス）が、分割後ブロックの最大サイズに相当する位置（blockStart + blockMax）に達しているか否かを検査する。最大サイズに相当する位置に達していればステップ２２１に進み、達していなければステップ２２３にスキップする。
【００４７】
（図２：ステップ２２１）
データ分割部１３０は、変数cP2がセットされている（0でない）か否かを検査する。変数cP2がセットされていれば、ステップ２１７における第２分割条件またはステップ２１８における第３分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP2の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP2として、ステップ２１０に戻る。変数cP2がセットされていない場合はステップ２２２に進む。
【００４８】
（図２：ステップ２２２）
データ分割部１３０は、アドレスblockStartとアドレスcPの間でデータをデータブロック（ステップ２２０の条件により、分割ブロックの最大サイズとなっている）に分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cPとして、ステップ２１０に戻る。
【００４９】
（図２：ステップ２２３）
データ分割部１３０は、アドレスcPを１バイト前（データの終端に向かう方向）に進め、ステップ２１５に戻る。
【００５０】
（図２：ステップ２２５）
データ分割部１３０は、アドレスblockStartとアドレスblockEndの間の残ったデータをデータブロックとして取り出す。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。本ステップは、分割後ブロックの最大サイズに相当する位置まで第１分割条件に該当する位置がみつからなかった場合の処理である。
【００５１】
図３は、データ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。以下、図３の各ステップについて説明する。
【００５２】
（図３：ステップＳ３０１）
データ格納部１４０は、ブロックＤＢ３００に格納する対象となっているデータブロックのハッシュ値を計算する。衝突する確率が低いハッシュ関数を用いることが望ましい。例えば、SHA-1、SHA-256などのハッシュ関数を用いることができる。
【００５３】
（図３：ステップＳ３０２）
データ格納部１４０は、ステップＳ３０１でデータ格納部１４０が求めたハッシュ値をキーにして、同じ内容のデータブロックが既にブロックＤＢ３００へ登録されているか否かを検索する。
【００５４】
（図３：ステップＳ３０３）
ステップＳ３０２でキーが見つかった場合は、データ格納部１４０はハッシュ値をバックアップ装置４００に出力し、本処理フローを終了する。
【００５５】
（図３：ステップＳ３０４）
ステップＳ３０２でキーが見つからなかった場合は、データ格納部１４０はハッシュ値をバックアップ装置４００に出力し、ハッシュ値をキーにしてデータブロックをブロックＤＢ３００に格納する。ブロックＤＢ３００に格納するデータブロックは、適当なアルゴリズムを用いて圧縮することが望ましい。
【００５６】
（図３：ステップＳ３０３〜Ｓ３０４：補足）
これらステップにおいてハッシュ値をキーにしているのは、ステップＳ３０４でブロックＤＢ３００にデータブロックを格納する際に、データブロックを圧縮する場合があるからである。データブロックを圧縮してからブロックＤＢ３００に格納する場合、既にブロックＤＢ３００に格納されているデータブロックと新たなデータブロックが同一であるか否かは、圧縮を解かない限り分からないため、処理負担が重くなる。そこで、ハッシュ値が一致するか否かによって簡易的に同一判定できるようにしているのである。
【００５７】
＜実施の形態１：まとめ＞
以上のように、本実施形態１に係るデータ分割装置１００は、第２分割条件に該当するデータ位置のうち、データの終端にできる限り近い分割位置を優先してデータを分割するように構成されている。これにより、重複排除処理のためのデータ分割を実施しつつ、分割後のデータブロックサイズができる限り大きくなるように処理方針を方向付けていることになるので、結果としてデータ重複排除とデータ圧縮をバランスよく両立させることができる。
【００５８】
具体的には、第１分割条件に該当する分割位置が見つからない場合には、第２分割条件に該当するできるだけ終端に近い分割位置を変数cP2に保存しておき、ステップ２２１でblockStartからcP2までのデータブロックをブロックＤＢ３００に書き込む。この処理手順により、最後に残ったcP2の値は、できる限りデータ終端に近い位置となる。
【００５９】
また、データブロックが第１分割条件と第２分割条件いずれにも該当しない場合には、ステップ２２２で分割後ブロックの最大サイズblockMaxのデータブロックをブロックＤＢ３００に格納するようにしている。これにより、重複排除に適していないデータブロックはデータ圧縮を優先してできる限り大きなサイズのデータブロックを格納することになるので、重複排除効果を発揮できないとしても、データ圧縮効果でこれを補い、総合的にデータサイズを小さくすることができる。
【００６０】
＜実施の形態２＞
本発明の実施形態２では、実施形態１と同様にできる限りデータ終端に近い位置でデータを分割する手法を説明する。本実施形態２では、分割するデータを終端から先頭に向かって順次読み取り、分割条件に合致した時点でデータを分割する。データ分割装置１００の構成は実施形態１と同様であるため、以下では差異点を中心に説明する。
【００６１】
図４は、本実施形態２に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。説明の便宜上、ステップ番号を併記した。以下、図４の各ステップについて説明する。
【００６２】
（図４：ステップ４００〜４１２）
これらのステップは、図２のステップ２００〜２１２と同様である。
【００６３】
（図４：ステップ４１３）
分割条件判定部１２０は、blockStart + blockMax <= blockEndが成立する場合は、分割位置を探す際に使用するアドレス変数cPを、分割後ブロックの最大サイズに相当する位置に初期化する。
【００６４】
（図４：ステップ４１４）
分割条件判定部１２０は、ステップ４１３の条件式が成立しない場合は、変数cPをデータブロックの末尾位置に初期化する。
【００６５】
（図４：ステップ４１３〜４１４：補足）
これらのステップでは、条件判定する位置cPを、データブロックのできるだけ後方の位置に初期設定していることになる。
【００６６】
（図４：ステップ４１５）
分割条件判定部１２０は、cP >= blockStart + blockMinが満たされる間、すなわちアドレスcPがデータブロックの末尾から最小ブロックサイズに相当する位置に達するまで、ステップ４１６からステップ４２１までの処理を繰り返す。
【００６７】
（図４：ステップ４１６〜４１７）
これらのステップは、図２のステップ２１５〜２１６と同様である。
【００６８】
（図４：ステップ４１８〜４１９）
これらのステップは、図２のステップ２１７〜２１８と同様である。ただし、分割条件判定部１２０は、第２分割条件pattern2と第３分割条件pattern3を判定する前に、アドレスcP2がセットされているか否か（値が０）を判定する。これは、本実施形態２ではデータブロックの末尾から先頭に向かってデータを読み取っていくため、最初に見つかったcP2の値が最もデータブロック末尾に近いからである。すなわち、できる限りデータブロックの末尾に近い位置でデータ分割するという観点では、cP2が既に見つかっていればその値を更新する必要はなく、cP2が空である場合に限り値をセットする必要があるからである。
【００６９】
（図４：ステップ４２０）
本ステップは、図２のステップ２１９と同様である。
【００７０】
（図４：ステップ４２１）
データ分割部１３０は、アドレスcPを１バイト後ろ（データの先頭に向かう方向）に進め、ステップ４１６に戻る。
【００７１】
（図４：ステップ４２３）
本ステップに到達した時点で変数cP2がセットされている場合、ステップ４１５〜４２１のループ内では、第１判定条件に合致する位置が見つからず、第２判定条件に合致する位置のみが見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP2の間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP2として、ステップ４１０に戻る。
【００７２】
（図４：ステップ４２４）
ステップ４２３で変数cP2がセットされていない場合、ステップ４１５〜４２１のループ内では、第１判定条件と第２分割条件いずれも合致する位置が見つからなかったことになるので、分割後ブロックの最小サイズでデータブロックを分割する。データ分割部１３０は、アドレスblockStartとアドレスblockStart + blockMinの間でデータをデータブロックに分割する。データ格納部１４０は、そのデータブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、アドレスblockStartをblockMinだけインクリメントして、ステップ４１０に戻る。
【００７３】
＜実施の形態２：まとめ＞
以上のように、本実施形態２に係るデータ分割装置１００は、データの終端から先頭に向かって順次データを読み取り、第２分割条件に該当するできるだけ終端に近い分割位置を変数cP2に保存しておく。ステップ４２３では、blockStartからcP2までのデータブロックをブロックＤＢ３００に書き込む。この処理手順により、最後に残ったcP2の値は、できる限りデータ終端に近い位置となる。
【００７４】
また、データブロックが第１分割条件と第２分割条件いずれにも該当しない場合には、ステップ４２４で分割後ブロックの最小サイズblockMinのデータブロックをブロックＤＢ３００に格納するようにしている。これにより、重複排除に適していないデータブロックでも、少なくとも最小サイズblockMinのデータブロックを格納することになるので、最低限のデータ圧縮効果を発揮することができる。
【００７５】
なお、ステップ４２４において、最大サイズblockMaxのデータブロックをブロックＤＢ３００に格納するようにしてもよい。これは、図２のステップ２２２と同様の処理を採用したものといえる。
【００７６】
＜実施の形態３＞
実施形態１〜２では、第１分割条件と第２分割条件のみを用いているが、より多くの分割条件を判定するようにすることもできる。本発明の実施形態３では、第１分割条件、第２分割条件、第３分割条件のいずれかに該当する位置でデータを分割する。データ分割装置１００の構成は実施形態１と同様であるため、以下では差異点を中心に説明する。
【００７７】
図５は、本実施形態３に係るデータ分割装置１００がデータを分割する処理を記述したプログラムである。ここでは、実施形態１の図２で説明したプログラムに加えて、第３分割条件に合致する位置でデータ分割する処理を新たに設けた例を示すが、実施形態２の図４で説明したプログラムに加えて第３判定条件を設けることもできる。以下、図２で説明したプログラムと異なる部分を中心に説明する。
【００７８】
（図５：ステップ５１２）
分割条件判定部１２０は、変数cP1、変数cP2、変数cP3を０で初期化する。変数cP3は、データを分割する条件である第３分割条件に該当するデータアドレスを保持するための変数である。
【００７９】
（図５：ステップ５１８）
分割条件判定部１２０は、特徴値hashが第３分割条件を満たす場合は、変数cP3に現在のデータアドレスcPをセットする。実施形態１〜２では、第３分割条件に合致する場合は変数cP2にデータアドレスcPを格納しているため、第１分割条件と第２分割条件のうちいずれかを採用していた。本実施形態３では、この選択肢に加えて新たに第３分割条件を設けた点が異なる。
【００８０】
（図５：ステップ５２２）
データ分割部１３０は、変数cP3がセットされている（0でない）か否かを検査する。変数cP3がセットされていれば、ステップ５１８における第３分割条件を満たす位置が見つかっていることになる。データ分割部１３０は、アドレスblockStartとアドレスcP3の間でデータをデータブロックに分割する。データ格納部１４０は、データブロックをブロックＤＢ３００に書き込む。データ格納部１４０は、同じデータブロックのハッシュ値を計算し、バックアップ装置４００に書き込む。データ分割部１３０は、blockStart = cP3として、ステップ５１０に戻る。変数cP3がセットされていない場合はステップ５２３に進む。
【００８１】
＜実施の形態３：まとめ＞
以上のように、本実施形態３に係るデータ分割装置１００は、第１分割条件、第２分割条件、第３分割条件の順に分割条件を判定し、いずれかに該当した位置でデータを分割する。これにより、実施形態１〜２よりも細かな分割条件を設定することができる。
【００８２】
＜実施の形態４＞
本発明の実施形態４では、データブロックのハッシュ値に加えてデータブロックの固有識別番号をブロックＤＢ３００とバックアップ装置４００に格納する動作例を説明する。これにより、ハッシュ値が衝突した場合でもブロックＤＢ３００やバックアップ装置４００に格納しているデータを破壊しないようにすることを図る。その他の構成は実施形態１〜３と同様であるため、以下では差異点を中心に説明する。
【００８３】
図６は、本実施形態４においてデータ分割部１３０とデータ格納部１４０が実施する関数bdbの詳細処理フローを示す図である。以下、図６の各ステップについて説明する。
【００８４】
（図６：ステップＳ６０１）
本ステップは、図３のステップＳ３０１と同様である。
【００８５】
（図６：ステップＳ６０２）
データ格納部１４０は、データブロックを固有に識別する固有識別番号を、０で初期化する。
【００８６】
（図６：ステップＳ６０３）
データ格納部１４０は、ステップＳ６０１でデータ格納部１４０が求めたハッシュ値とデータブロックの固有識別番号をキーにして、同じ内容のデータブロックが既にブロックＤＢ３００へ登録されているか否かを検索する。
【００８７】
（図６：ステップＳ６０４）
ステップＳ６０３でキーが見つかった場合は、データ格納部１４０は対応するデータブロックをブロックＤＢ３００から取り出し、処理対象になっているデータブロックと同一内容であるか否か比較する。同一であればハッシュ値と固有識別番号をバックアップ装置４００に出力し、本処理フローを終了する。同一でなければ固有識別番号を１つインクリメントしてステップＳ６０３に戻る。
【００８８】
（図６：ステップＳ６０５）
ステップＳ６０３でキーが見つからなかった場合は、データ格納部１４０はハッシュ値と固有識別番号をバックアップ装置４００に出力し、データ格納部１４０はハッシュ値と固有識別番号をキーにしてデータブロックをブロックＤＢ３００に格納する。ブロックＤＢ３００に格納するデータブロックは、適当なアルゴリズムを用いて圧縮することが望ましい。
【００８９】
＜実施の形態４：まとめ＞
以上のように、本実施形態４に係るデータ分割装置１００は、ハッシュ値が衝突する場合であっても、固有識別番号によってデータブロックを一意に識別することができる。これにより、ハッシュ値が衝突した場合でもブロックＤＢ３００やバックアップ装置４００に格納しているデータを破壊しないようにすることができる。
【００９０】
＜実施の形態５＞
以上の実施形態１〜４において、データ分割装置１００は、データ読取部１１０がファイルサーバ２００からデータを読み取った時点で、そのデータが圧縮または暗号化されているか否かを判断し、圧縮または暗号化されている場合は図２〜図６で説明した処理を省略してそのデータをそのままブロックＤＢ３００に格納するようにしてもよい。圧縮または暗号化されているデータに対してさらに重複排除処理やデータ圧縮処理をしても、大きな効果は見込めないと考えられるからである。
【００９１】
図２〜図６で説明した処理を省略する場合は、データ全体を１つのデータブロックとして取り扱い、ハッシュ値はデータ全体に対して計算することになる。
【符号の説明】
【００９２】
１００：データ分割装置、１１０：データ読取部、１２０：分割条件判定部、１３０：データ分割部、１４０：データ格納部、２００：ファイルサーバ、３００：ブロックＤＢ、４００：バックアップ装置。
【特許請求の範囲】
【請求項１】
データを分割する処理をコンピュータに実行させるプログラムであって、
前記コンピュータに、
前記データを所定の読取単位毎に順次読み取る読取ステップ、
前記読取ステップで読み取ったデータが、データを分割する条件に該当するか否かを判定してそのデータ位置を取得する判定ステップ、
前記データが前記条件に該当する位置で前記データを分割する分割ステップ、
を実行させ、
前記判定ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが、データを分割する条件である第１分割条件に該当するか否かを判定する第１判定ステップ、
前記読取ステップで読み取ったデータが前記第１分割条件に該当しない場合は、前記読取ステップで読み取ったデータが、データを分割する条件である第２分割条件に該当するか否かをさらに判定する第２判定ステップ、
を実行させ、
前記第２判定ステップは、
前記データの終端により近い位置を前記判定ステップの結果として優先的に用いるように構成されている
ことを特徴とするデータ分割プログラム。
【請求項２】
前記分割ステップで分割した後のデータの上限サイズをあらかじめ規定するステップを前記コンピュータに実行させ、
前記読取ステップでは、前記コンピュータに、
前記データを先頭から終端に向かって順次読み取らせ、
前記データ分割ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しなかった場合は、前記上限サイズで前記分割ステップを実行させる
ことを特徴とする請求項１記載のデータ分割プログラム。
【請求項３】
前記分割ステップで分割した後のデータの下限サイズをあらかじめ規定するステップを前記コンピュータに実行させ、
前記読取ステップでは、前記コンピュータに、
前記データを終端から先頭に向かって順次読み取らせ、
前記データ分割ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しなかった場合は、前記下限サイズで前記分割ステップを実行させる
ことを特徴とする請求項１記載のデータ分割プログラム。
【請求項４】
前記判定ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しない場合は、前記読取ステップで読み取ったデータが、データを分割する条件である第３分割条件に該当するか否かをさらに判定する第３判定ステップを実行させ、
前記分割ステップでは、前記コンピュータに、
前記第１分割条件、前記第２分割条件、または前記第３分割条件のいずれかに該当した位置で前記データを分割させ、
前記第３判定ステップは、
前記データの終端により近い位置を前記判定ステップの結果として優先的に用いるように構成されている
ことを特徴とする請求項１から３のいずれか１項記載のデータ分割プログラム。
【請求項５】
前記分割ステップで分割したデータをそのデータのハッシュ値と対応付けて記憶装置に格納する格納ステップを前記コンピュータに実行させる
ことを特徴とする請求項１から４のいずれか１項記載のデータ分割プログラム。
【請求項６】
前記格納ステップでは、前記コンピュータに、
前記分割ステップで分割した前記データを固有に識別する番号を前記ハッシュ値と対応付けて前記記憶装置に格納させる
ことを特徴とする請求項５記載のデータ分割プログラム。
【請求項７】
前記データが圧縮済みまたは暗号化されているか否かを判断するステップ、
前記データが圧縮済みまたは暗号化されている場合は、前記読取ステップ、前記判定ステップ、前記分割ステップ、および前記格納ステップを省略し、前記データをそのハッシュ値と対応付けて記憶装置に格納する処理のみを実行するステップ、
を前記コンピュータに実行させる
ことを特徴とする請求項５または６記載のデータ分割プログラム。
【請求項８】
前記格納ステップでは、前記コンピュータに、
前記データまたは前記分割ステップで分割した前記データを圧縮して記憶装置に格納させる
ことを特徴とする請求項５から７のいずれか１項記載のデータ分割プログラム。
【請求項９】
データを分割する装置であって、
前記データを所定の読取単位毎に順次読み取る読取部と、
前記読取部が読み取ったデータが、データを分割する条件に該当するか否かを判定する分割条件判定部と、
前記データが前記条件に該当する位置で前記データを分割する分割部と、
を備え、
前記分割条件判定部は、
前記読取部が読み取ったデータが、データを分割する条件である第１分割条件に該当するか否かを判定し、
前記読取部が読み取ったデータが前記第１分割条件に該当しない場合は、前記読取部が読み取ったデータが、データを分割する条件である第２分割条件に該当するか否かをさらに判定し、
前記分割条件判定部は、
前記データが第２分割条件に該当するか否かを判定する際に、前記データの終端により近い位置を優先的に用いる
ことを特徴とするデータ分割装置。
【請求項１】
データを分割する処理をコンピュータに実行させるプログラムであって、
前記コンピュータに、
前記データを所定の読取単位毎に順次読み取る読取ステップ、
前記読取ステップで読み取ったデータが、データを分割する条件に該当するか否かを判定してそのデータ位置を取得する判定ステップ、
前記データが前記条件に該当する位置で前記データを分割する分割ステップ、
を実行させ、
前記判定ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが、データを分割する条件である第１分割条件に該当するか否かを判定する第１判定ステップ、
前記読取ステップで読み取ったデータが前記第１分割条件に該当しない場合は、前記読取ステップで読み取ったデータが、データを分割する条件である第２分割条件に該当するか否かをさらに判定する第２判定ステップ、
を実行させ、
前記第２判定ステップは、
前記データの終端により近い位置を前記判定ステップの結果として優先的に用いるように構成されている
ことを特徴とするデータ分割プログラム。
【請求項２】
前記分割ステップで分割した後のデータの上限サイズをあらかじめ規定するステップを前記コンピュータに実行させ、
前記読取ステップでは、前記コンピュータに、
前記データを先頭から終端に向かって順次読み取らせ、
前記データ分割ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しなかった場合は、前記上限サイズで前記分割ステップを実行させる
ことを特徴とする請求項１記載のデータ分割プログラム。
【請求項３】
前記分割ステップで分割した後のデータの下限サイズをあらかじめ規定するステップを前記コンピュータに実行させ、
前記読取ステップでは、前記コンピュータに、
前記データを終端から先頭に向かって順次読み取らせ、
前記データ分割ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しなかった場合は、前記下限サイズで前記分割ステップを実行させる
ことを特徴とする請求項１記載のデータ分割プログラム。
【請求項４】
前記判定ステップでは、前記コンピュータに、
前記読取ステップで読み取ったデータが前記第１分割条件および前記第２分割条件のいずれにも該当しない場合は、前記読取ステップで読み取ったデータが、データを分割する条件である第３分割条件に該当するか否かをさらに判定する第３判定ステップを実行させ、
前記分割ステップでは、前記コンピュータに、
前記第１分割条件、前記第２分割条件、または前記第３分割条件のいずれかに該当した位置で前記データを分割させ、
前記第３判定ステップは、
前記データの終端により近い位置を前記判定ステップの結果として優先的に用いるように構成されている
ことを特徴とする請求項１から３のいずれか１項記載のデータ分割プログラム。
【請求項５】
前記分割ステップで分割したデータをそのデータのハッシュ値と対応付けて記憶装置に格納する格納ステップを前記コンピュータに実行させる
ことを特徴とする請求項１から４のいずれか１項記載のデータ分割プログラム。
【請求項６】
前記格納ステップでは、前記コンピュータに、
前記分割ステップで分割した前記データを固有に識別する番号を前記ハッシュ値と対応付けて前記記憶装置に格納させる
ことを特徴とする請求項５記載のデータ分割プログラム。
【請求項７】
前記データが圧縮済みまたは暗号化されているか否かを判断するステップ、
前記データが圧縮済みまたは暗号化されている場合は、前記読取ステップ、前記判定ステップ、前記分割ステップ、および前記格納ステップを省略し、前記データをそのハッシュ値と対応付けて記憶装置に格納する処理のみを実行するステップ、
を前記コンピュータに実行させる
ことを特徴とする請求項５または６記載のデータ分割プログラム。
【請求項８】
前記格納ステップでは、前記コンピュータに、
前記データまたは前記分割ステップで分割した前記データを圧縮して記憶装置に格納させる
ことを特徴とする請求項５から７のいずれか１項記載のデータ分割プログラム。
【請求項９】
データを分割する装置であって、
前記データを所定の読取単位毎に順次読み取る読取部と、
前記読取部が読み取ったデータが、データを分割する条件に該当するか否かを判定する分割条件判定部と、
前記データが前記条件に該当する位置で前記データを分割する分割部と、
を備え、
前記分割条件判定部は、
前記読取部が読み取ったデータが、データを分割する条件である第１分割条件に該当するか否かを判定し、
前記読取部が読み取ったデータが前記第１分割条件に該当しない場合は、前記読取部が読み取ったデータが、データを分割する条件である第２分割条件に該当するか否かをさらに判定し、
前記分割条件判定部は、
前記データが第２分割条件に該当するか否かを判定する際に、前記データの終端により近い位置を優先的に用いる
ことを特徴とするデータ分割装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１６４１３０（Ｐ２０１２−１６４１３０Ａ）
【公開日】平成２４年８月３０日（２０１２．８．３０）
【国際特許分類】
【出願番号】特願２０１１−２３９６０（Ｐ２０１１−２３９６０）
【出願日】平成２３年２月７日（２０１１．２．７）
【出願人】（０００２３３０５５）株式会社日立ソリューションズ (1,610)
【Ｆターム（参考）】
【公開日】平成２４年８月３０日（２０１２．８．３０）
【国際特許分類】
【出願日】平成２３年２月７日（２０１１．２．７）
【出願人】（０００２３３０５５）株式会社日立ソリューションズ (1,610)
【Ｆターム（参考）】
[ Back to top ]