(57)【要約】【課題】ハッシュ値の衝突が発生した場合に、処理負荷が過大となることを防止しながらデータが同一であるか否かを検知することが可能な情報処理装置を提供すること。【解決手段】この装置１００Ａは、データを含む書込要求が受け付けられた場合、第１のハッシュ関数に基づいて第１のハッシュ値を取得するとともに第２のハッシュ関数に基づいて第２のハッシュ値を取得する。装置は、取得された第１のハッシュ値及び第２のハッシュ値が対応付けて記憶装置１１０Ａに記憶されていない場合、データと第１のハッシュ値と第２のハッシュ値と参照回数情報とを対応付けて記憶装置に記憶させる。一方、装置は、取得された第１のハッシュ値及び第２のハッシュ値が対応付けて記憶装置に記憶されている場合、第１のハッシュ値及び第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。【選択図】図２０
2010146308.tif 000002
【特許請求の範囲】
【請求項１】
データを含む書込要求を受け付ける書込要求受付手段と、
前記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、前記書込要求に含まれるデータと、前記取得された第１のハッシュ値と、前記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える情報処理装置。
【請求項２】
請求項１に記載の情報処理装置であって、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と、前記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて前記記憶装置に記憶されている場合、以降において前記ハッシュ値取得処理手段が前記第１のハッシュ値を取得するために用いるハッシュ関数を、前記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を備える情報処理装置。
【請求項３】
請求項１又は請求項２に記載の情報処理装置であって、
前記第１のハッシュ関数は、基本となるハッシュ関数である第１の基本ハッシュ関数に、前記入力されたデータと、予め定められた第１の付加データと、からなるデータを入力することにより、当該第１の基本ハッシュ関数から出力されたハッシュ値を出力するように構成され、
前記第２のハッシュ関数は、基本となるハッシュ関数である第２の基本ハッシュ関数に、前記入力されたデータと、予め定められ且つ前記第１の付加データと異なる第２の付加データと、からなるデータを入力することにより、当該第２の基本ハッシュ関数から出力されたハッシュ値を出力するように構成された情報処理装置。
【請求項４】
請求項１乃至請求項３のいずれか一項に記載の情報処理装置であって、
前記記憶処理手段は、前記書込要求に含まれるデータを前記記憶装置に記憶させる際、当該記憶装置内の複数のセル領域のそれぞれに、当該データを記憶させるように構成された情報処理装置。
【請求項５】
請求項４に記載の情報処理装置であって、
前記ハッシュ値取得処理手段は、前記書込要求が受け付けられた場合、少なくとも３つの互いに異なるハッシュ関数のそれぞれに当該書込要求に含まれるデータを入力することによりハッシュ値を取得する処理を行うように構成され、
前記記憶処理手段は、前記書込要求に含まれるデータを前記記憶装置に記憶させる際、前記複数のセル領域のそれぞれに、前記データと、前記取得されたハッシュ値のうちの少なくとも２つのハッシュ値と、を対応付けて記憶させることにより、当該複数のセル領域の任意の１つである第１のセル領域に当該データと対応付けて記憶されている１つのハッシュ値が、当該第１のセル領域以外の第２のセル領域に当該データと対応付けて記憶され、且つ、当該第１のセル領域に当該データと対応付けて記憶されている他の１つのハッシュ値が、当該第１のセル領域及び当該第２のセル領域以外の第３のセル領域に当該データと対応付けて記憶されるように構成された情報処理装置。
【請求項６】
請求項４又は請求項５に記載の情報処理装置であって、
前記記憶装置内のセル領域の数が予め設定された数よりも少ない場合において、前記記憶装置に新たに記憶可能なデータ量が所定の閾値量よりも多い場合、前記記憶処理手段が前記データを記憶させるセル領域の数を増加させる処理を行うセル領域生成処理手段を備える情報処理装置。
【請求項７】
請求項５又は請求項６に記載の情報処理装置であって、
前記取得されたハッシュ値のうちの１つである第１のハッシュ値と同一の第１のハッシュ値と、前記取得されたハッシュ値のうちの他の１つである第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて前記記憶装置内の前記第１のセル領域に記憶されている場合、前記記憶処理手段が前記データを記憶させるセル領域から当該第１のセル領域を消去する処理を行うセル領域消滅処理手段を備える情報処理装置。
【請求項８】
請求項１乃至請求項７のいずれか一項に記載の情報処理装置であって、
前記書込要求に含まれるデータは、ファイルとして取り扱われる一連のデータを所定のデータサイズ毎に分割したデータブロックとしてのセグメントである情報処理装置。
【請求項９】
記憶装置を備えるとともに、
データを含む書込要求を受け付ける書込要求受付手段と、
前記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて前記記憶装置に記憶されていない場合、前記書込要求に含まれるデータと、前記取得された第１のハッシュ値と、前記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える情報処理システム。
【請求項１０】
請求項９に記載の情報処理システムであって、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と、前記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて前記記憶装置に記憶されている場合、以降において前記ハッシュ値取得処理手段が前記第１のハッシュ値を取得するために用いるハッシュ関数を、前記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を備える情報処理システム。
【請求項１１】
データを含む書込要求を受け付ける書込要求受付工程と、
前記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理工程と、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、前記書込要求に含まれるデータと、前記取得された第１のハッシュ値と、前記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理工程と、
を含む情報処理方法。
【請求項１２】
請求項１１に記載の情報処理方法であって、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と、前記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて前記記憶装置に記憶されている場合、以降において前記ハッシュ値取得処理手段が前記第１のハッシュ値を取得するために用いるハッシュ関数を、前記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理工程を含む情報処理方法。
【請求項１３】
情報処理装置に、
データを含む書込要求を受け付ける書込要求受付手段と、
前記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて前記記憶装置に記憶されていない場合、前記書込要求に含まれるデータと、前記取得された第１のハッシュ値と、前記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、前記取得された第１のハッシュ値と同一の第１のハッシュ値と前記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を実現させるためのプログラム。
【請求項１４】
請求項１３に記載のプログラムであって、
前記情報処理装置に、更に、
前記取得された第１のハッシュ値と同一の第１のハッシュ値と、前記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて前記記憶装置に記憶されている場合、以降において前記ハッシュ値取得処理手段が前記第１のハッシュ値を取得するために用いるハッシュ関数を、前記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを記憶装置に記憶させる情報処理装置に関する。
【背景技術】
【０００２】
データを含む書込要求を受け付けるとともに、受け付けた書込要求に含まれるデータを記憶装置に記憶させる情報処理装置が知られている。
【０００３】
この種の情報処理装置の一つとして特許文献１に記載の情報処理装置は、データを記憶装置に記憶させる際、そのデータをハッシュ関数に入力することにより、ハッシュ値を取得する。そして、情報処理装置は、取得されたハッシュ値と同一のハッシュ値が記憶装置に記憶されていない場合、データと、ハッシュ値と、当該データが参照されている回数を表す参照回数情報と、を対応付けて記憶装置に記憶させる。
【０００４】
一方、取得されたハッシュ値と同一のハッシュ値が記憶装置に記憶されている場合、情報処理装置は、そのハッシュ値と対応付けて記憶装置に記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
この情報処理装置によれば、同一のデータが重複して記憶装置に記憶されることを回避することができるので、記憶装置に記憶されるデータ量を減少させることができる。
【０００５】
【特許文献１】特開２００７−２３４０２６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、ハッシュ関数は、異なるデータが入力されても、同一のハッシュ値を出力する（ハッシュ値の衝突が発生する）場合がある。従って、上記情報処理装置においては、ハッシュ値の衝突が発生した場合に、２つの異なるデータが誤って同一のデータとして認識され、一方のデータを消失してしまう場合が生じるという問題があった。
【０００７】
また、仮に、ハッシュ値が同一である２つのデータの少なくとも一部を直接比較することによりデータが同一であるか否かを検知するように上記情報処理装置を構成した場合には、情報処理装置の処理負荷が過大となってしまうという問題があった。
【０００８】
このため、本発明の目的は、上述した課題である「ハッシュ値の衝突が発生した場合に、処理負荷が過大となることなくデータが同一であるか否かを検知することができないこと」を解決することが可能な情報処理装置を提供することにある。
【課題を解決するための手段】
【０００９】
かかる目的を達成するため本発明の一形態である情報処理装置は、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える。
【００１０】
また、本発明の他の形態である情報処理システムは、
記憶装置を備えるとともに、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて上記記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える。
【００１１】
また、本発明の他の形態である情報処理方法は、
データを含む書込要求を受け付ける書込要求受付工程と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理工程と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理工程と、
を含む。
【００１２】
また、本発明の他の形態であるプログラムは、
情報処理装置に、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて上記記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を実現させるためのプログラムである。
【発明の効果】
【００１３】
本発明は、以上のように構成されることにより、ハッシュ値の衝突が発生した場合に、処理負荷が過大となることを防止しながらデータが同一であるか否かを検知することができる。
【発明を実施するための最良の形態】
【００１４】
本発明の一形態である情報処理装置は、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える。
【００１５】
これによれば、第１のハッシュ値及び第２のハッシュ値のいずれか一方の衝突が発生した場合であっても、他方を比較することによりデータが同一であるか否かを検知することができる。即ち、ハッシュ値の衝突が発生した場合に、処理負荷が過大となることを防止しながらデータが同一であるか否かを検知することができる。これにより、２つの異なるデータを誤って同一のデータとして認識することを回避しながら、同一のデータが重複して記憶装置に記憶されることを回避することができる。この結果、記憶装置に記憶されるデータ量を減少させることができる。
【００１６】
この場合、上記情報処理装置は、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と、上記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて上記記憶装置に記憶されている場合、以降において上記ハッシュ値取得処理手段が上記第１のハッシュ値を取得するために用いるハッシュ関数を、上記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を備えることが好適である。即ち、ハッシュ関数変更処理手段により、ハッシュ値の衝突が発生したハッシュ関数を他のハッシュ関数に置換することができる。
【００１７】
これによれば、第１のハッシュ値及び第２のハッシュ値のいずれか一方の衝突が発生する状態が継続することを回避することができる。従って、第１のハッシュ値及び第２のハッシュ値のいずれか一方を比較するだけで、そのデータと同一のデータが記憶されているか否かを検知することができる。即ち、情報処理装置の処理量を低減することができる。
【００１８】
また、ハッシュ値の衝突が発生した場合、ハッシュ値の衝突が発生する基となったデータを、予め定められた規則に従って空き領域に記憶させ、且つ、データの読み出し時にその規則に従って当該データを読み出すように、情報処理装置が構成されている場合であっても、そのデータを読み出すために要する時間が過大となることを防止することができる。
【００１９】
この場合、
上記第１のハッシュ関数は、基本となるハッシュ関数である第１の基本ハッシュ関数に、上記入力されたデータと、予め定められた第１の付加データと、からなるデータを入力することにより、当該第１の基本ハッシュ関数から出力されたハッシュ値を出力するように構成され、
上記第２のハッシュ関数は、基本となるハッシュ関数である第２の基本ハッシュ関数に、上記入力されたデータと、予め定められ且つ上記第１の付加データと異なる第２の付加データと、からなるデータを入力することにより、当該第２の基本ハッシュ関数から出力されたハッシュ値を出力するように構成されることが好適である。
【００２０】
この場合、上記第１の基本ハッシュ関数と、上記第２の基本ハッシュ関数と、は、同一の基本ハッシュ関数であることが好適である。
これによれば、基本ハッシュ関数を１つ用意するだけで、容易に複数のハッシュ関数を用意することができる。
【００２１】
また、上記情報処理装置の他の態様において、上記第１の基本ハッシュ関数と、上記第２の基本ハッシュ関数と、は、異なる基本ハッシュ関数であることが好適である。
これによれば、あるデータに対して、第１のハッシュ値及び第２のハッシュ値の両方においてハッシュ値の衝突が発生する可能性を低減することができる。
【００２２】
この場合、
上記記憶処理手段は、上記書込要求に含まれるデータを上記記憶装置に記憶させる際、当該記憶装置内の複数のセル領域のそれぞれに、当該データを記憶させるように構成されることが好適である。
【００２３】
これによれば、１つのセル領域に記憶されているデータが消失した場合であっても、他のセル領域に記憶されているデータを取得することができる。即ち、記憶装置に記憶されているデータの冗長性を確保することができる。
【００２４】
この場合、
上記ハッシュ値取得処理手段は、上記書込要求が受け付けられた場合、少なくとも３つの互いに異なるハッシュ関数のそれぞれに当該書込要求に含まれるデータを入力することによりハッシュ値を取得する処理を行うように構成され、
上記記憶処理手段は、上記書込要求に含まれるデータを上記記憶装置に記憶させる際、上記複数のセル領域のそれぞれに、上記データと、上記取得されたハッシュ値のうちの少なくとも２つのハッシュ値と、を対応付けて記憶させることにより、当該複数のセル領域の任意の１つである第１のセル領域に当該データと対応付けて記憶されている１つのハッシュ値が、当該第１のセル領域以外の第２のセル領域に当該データと対応付けて記憶され、且つ、当該第１のセル領域に当該データと対応付けて記憶されている他の１つのハッシュ値が、当該第１のセル領域及び当該第２のセル領域以外の第３のセル領域に当該データと対応付けて記憶されるように構成されることが好適である。
【００２５】
これによれば、１つのハッシュ値の衝突が発生した場合であっても、複数のセル領域に共通して記憶されているハッシュ値であり且つ衝突が発生していないハッシュ値を２つ以上確保することができる。この結果、例えば、ハッシュ値の衝突が発生した場合に、そのハッシュ値を、他のハッシュ関数に基づくハッシュ値に更新するように、情報処理装置が構成されている場合において、ハッシュ値の更新処理中に書込要求が受け付けられたときであっても、上述した効果を奏することができる。
【００２６】
この場合、上記情報処理装置は、
上記記憶装置内のセル領域の数が予め設定された数よりも少ない場合において、上記記憶装置に新たに記憶可能なデータ量が所定の閾値量よりも多い場合、上記記憶処理手段が上記データを記憶させるセル領域の数を増加させる処理を行うセル領域生成処理手段を備えることが好適である。
【００２７】
これによれば、記憶装置に新たに記憶可能なデータ量が閾値量よりも多い場合には、予め設定された数までセル領域の数を増加させることができる。
【００２８】
この場合、上記情報処理装置は、
上記取得されたハッシュ値のうちの１つである第１のハッシュ値と同一の第１のハッシュ値と、上記取得されたハッシュ値のうちの他の１つである第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて上記記憶装置内の上記第１のセル領域に記憶されている場合、上記記憶処理手段が上記データを記憶させるセル領域から当該第１のセル領域を消去する処理を行うセル領域消滅処理手段を備えることが好適である。
【００２９】
この場合、
上記書込要求に含まれるデータは、ファイルとして取り扱われる一連のデータを所定のデータサイズ毎に分割したデータブロックとしてのセグメントであることが好適である。
【００３０】
これによれば、ファイルの一部のみが重複している場合に、その重複している部分が記憶装置に重複して記憶されることを防止することができる。この結果、記憶装置に記憶されるデータ量をより一層減少させることができる。
【００３１】
また、本発明の他の形態である情報処理システムは、
記憶装置を備えるとともに、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて上記記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を備える。
【００３２】
この場合、上記情報処理システムは、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と、上記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて上記記憶装置に記憶されている場合、以降において上記ハッシュ値取得処理手段が上記第１のハッシュ値を取得するために用いるハッシュ関数を、上記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を備えることが好適である。
【００３３】
また、本発明の他の形態である情報処理方法は、
データを含む書込要求を受け付ける書込要求受付工程と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理工程と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理工程と、
を含む。
【００３４】
この場合、上記情報処理方法は、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と、上記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて上記記憶装置に記憶されている場合、以降において上記ハッシュ値取得処理手段が上記第１のハッシュ値を取得するために用いるハッシュ関数を、上記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理工程を含むことが好適である。
【００３５】
また、本発明の他の形態であるプログラムは、
情報処理装置に、
データを含む書込要求を受け付ける書込要求受付手段と、
上記書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行うハッシュ値取得処理手段と、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて上記記憶装置に記憶されていない場合、上記書込要求に含まれるデータと、上記取得された第１のハッシュ値と、上記取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置に新たに記憶させ、一方、上記取得された第１のハッシュ値と同一の第１のハッシュ値と上記取得された第２のハッシュ値と同一の第２のハッシュ値とが対応付けて当該記憶装置に記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する記憶処理手段と、
を実現させるためのプログラムである。
【００３６】
この場合、上記プログラムは、
上記情報処理装置に、更に、
上記取得された第１のハッシュ値と同一の第１のハッシュ値と、上記取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて上記記憶装置に記憶されている場合、以降において上記ハッシュ値取得処理手段が上記第１のハッシュ値を取得するために用いるハッシュ関数を、上記第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行うハッシュ関数変更処理手段を実現させるためのプログラムであることが好適である。
【００３７】
上述した構成を有する、情報処理システム、情報処理方法、又は、プログラム、の発明であっても、上記情報処理装置と同様の作用を有するために、上述した本発明の目的を達成することができる。
【００３８】
以下、本発明に係る、情報処理装置、情報処理システム、情報処理方法、及び、プログラム、の実施形態について図１〜図２０を参照しながら説明する。
【００３９】
＜実施形態＞
図１に示したように、実施形態に係る情報処理システム１は、情報処理装置１００と、外部記憶装置（記憶装置）１１０と、を含む。
【００４０】
情報処理装置１００は、図示しない中央処理装置（ＣＰＵ；Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、及び、内部記憶装置（メモリ及びハードディスク駆動装置（ＨＤＤ））を備える。情報処理装置１００は、内部記憶装置に記憶されているプログラム（例えば、オペレーティングシステム）をＣＰＵが実行することにより、後述する機能を実現するように構成されている。
【００４１】
外部記憶装置１１０は、情報を記憶（保持）するための記憶媒体を備える。外部記憶装置１１０は、情報処理装置１００からの書込指示に応じて、情報を記憶媒体に記憶させる。また、外部記憶装置１１０は、情報処理装置１００からの読出指示に応じて、記憶媒体に記憶されている情報を情報処理装置１００へ伝達する。
【００４２】
図２は、上記のように構成された情報処理システム１の機能を表すブロック図である。この機能は、情報処理装置１００のＣＰＵが内部記憶装置に記憶されているプログラム等を実行することにより、実現される。
【００４３】
この情報処理装置１００の機能は、ファイルシステム制御部１１と、書込要求受付部（書込要求受付手段）１２と、ハッシュ値取得処理部（ハッシュ値取得処理手段）１３と、記憶処理部（記憶処理手段）１４と、ハッシュ関数変更処理部（ハッシュ関数変更処理手段、ハッシュ関数変更処理工程）１５と、セル領域消滅処理部（セル領域消滅処理手段）１６と、セル領域生成処理部（セル領域生成処理手段）１７と、読出要求受付部（読出要求受付手段）１８と、を含む。
【００４４】
ファイルシステム制御部１１は、情報処理装置１００が実行するプログラム（例えば、アプリケーションプログラム等）が、外部記憶装置１１０に記憶されているデータをファイルとして取り扱う（例えば、ファイルを読み出す、又は、ファイルを書き出す）ための機能を提供する。
【００４５】
ファイルシステム制御部１１は、図３に示したファイルシステム情報Ｄ３０を内部記憶装置に記憶させている。ファイルシステム情報Ｄ３０は、ファイル管理情報Ｄ３１と、ハッシュ関数情報Ｄ３２と、セル領域情報Ｄ３３と、を含む。
【００４６】
ファイル管理情報Ｄ３１は、ファイルのメタ情報を含む。メタ情報は、各ファイルのファイルシステムにおける位置（パス）、アクセス制御権、作成日、及び、更新日等を表す情報を含む。また、ファイル管理情報Ｄ３１は、ファイルとセグメントとを対応付けるための情報を含む。ここで、セグメントは、ファイルとして取り扱われる一連のデータ（ファイルを構成するデータ）を所定のデータサイズ毎に分割したデータブロックである。
【００４７】
本例では、ファイル管理情報Ｄ３１は、図４に示したファイルメタ情報テーブル、図５に示したノード関係テーブル、図６に示したファイル構成セグメントテーブル、及び、図７に示したセグメントハッシュ管理テーブル、を含む。
【００４８】
ファイルメタ情報テーブルは、図４に示したように、ノード（ｉ−ｎｏｄｅ）番号と、先頭セグメント番号と、ディレクトリフラグと、ファイル名と、作成日と、からなる情報を複数含む。なお、ファイルメタ情報テーブルは、更新日、及び、アクセス権等の他の情報を含んでいてもよい。
【００４９】
ノード番号は、ファイルを管理するためのファイルシステムにてファイルを識別するための情報である。ファイルシステムは、階層構造（本例では、木（ツリー）構造）を有している。即ち、ファイルシステムは、ファイルと、ディレクトリと、を有し、ディレクトリは、ファイル及び／又はディレクトリを格納するための特殊ファイルである。以下、本明細書においては、ファイルｆａがディレクトリｄａに格納されている場合、「ｄａ／ｆａ」と表す。また、この場合、ディレクトリｄａを「親」と呼び、ファイルｆａを「子」と呼ぶ。
【００５０】
本例では、ファイルメタ情報テーブルに、ノード番号として「０」、「１」、「５０」、及び、「３００」のそれぞれを有する情報を含んでいる状態とする。なお、ノード番号「０」により識別されるファイルは、ファイルシステムにおける最上階層に位置する（全てのファイルの親となる）ファイル（即ち、ルートファイル）である。
【００５１】
ディレクトリフラグは、そのファイルが特殊ファイルとしてのディレクトリであるか否かを表す情報である。ディレクトリフラグは、「１」である場合にそのファイルがディレクトリであることを表し、「０」である場合にそのファイルが通常の（即ち、データを表す）ファイルであることを表す。
【００５２】
先頭セグメント番号は、ファイル内の先頭に位置するセグメントを識別するためのセグメント番号である。セグメント番号は、セグメントを識別するための情報である。
なお、本例では、ディレクトリは、セグメントを有しない。従って、ディレクトリに対する先頭セグメント番号は、「０」に設定されている。ディレクトリがデータを有する場合には、「０」以外のセグメント番号が設定されてもよい。
【００５３】
ファイル名は、ノード番号により識別されるファイル（又は、ディレクトリ）の名称を表す情報である。情報処理装置１００が実行するプログラム（例えば、アプリケーションプログラム等）がファイルシステムにアクセスする（即ち、ファイルを読み出す、又は、ファイルを書き込む）場合には、ファイル名によりアクセスの対象となるファイルが特定される。
【００５４】
ノード関係テーブルは、図５に示したように、ノード番号と、そのノード番号により識別されるファイルを格納するファイルを識別するための親ノード番号と、からなる情報を複数含む。即ち、ノード関係テーブルは、ファイルの階層構造（親子関係）を表す情報である。ルートファイルを格納するファイルは存在しないため、ルートファイルのノード番号と対応付けられた親ノード番号は「０」に設定される。
【００５５】
本例では、ルートファイルの直下の階層には、ノード番号「１」により識別されるファイルが存在している。ノード番号により階層構造を表すと、「０／１」と表すことができ、ファイル名により階層構造を表すと、「／ｈｏｍｅ」と表すことができる。
【００５６】
ファイル構成セグメントテーブルは、図６に示したように、ノード番号と、セグメント番号と、そのノード番号により識別されるファイルにおいてそのセグメント番号により識別されるセグメントに後続するセグメントを識別するためのセグメント番号である後続セグメント番号と、からなる情報を複数含む。
【００５７】
本例では、ノード番号「３００」により識別されるファイルは、６個のセグメントにより構成される。即ち、このファイルは、セグメント番号「１０１」〜「１０６」により識別されるセグメントがこの順に並んだデータからなる。
【００５８】
セグメントハッシュ管理テーブルは、図７に示したように、セグメント番号と、第１のハッシュ値と、第２のハッシュ値と、第３のハッシュ値と、からなる情報を複数含む。第１のハッシュ値〜第３のハッシュ値のそれぞれは、後述するハッシュ関数を用いて算出された値である。
【００５９】
ハッシュ関数情報Ｄ３２は、複数のハッシュ関数のそれぞれを表す情報を含む。各ハッシュ関数は、入力されたデータを変換することにより、そのデータよりもデータサイズが小さいハッシュ値を出力する関数である。各ハッシュ関数は、入力されるデータと出力されるハッシュ値とをｎ対１（ｎは、１を含む整数）に対応させるように構成されている。
【００６０】
本例では、ハッシュ関数ＨＡ（「ｈａｓｈＡ」）は、基本となるハッシュ関数である基本ハッシュ関数（第１の基本ハッシュ関数）に、入力されたデータと、予め定められた第１の付加データと、からなるデータを入力することにより、その基本ハッシュ関数から出力されたハッシュ値を出力するように構成される。
【００６１】
同様に、ハッシュ関数ＨＢ（「ｈａｓｈＢ」）は、基本ハッシュ関数（第２の基本ハッシュ関数）に、入力されたデータと、予め定められ且つ第１の付加データと異なる第２の付加データと、からなるデータを入力することにより、その基本ハッシュ関数から出力されたハッシュ値を出力するように構成される。
【００６２】
なお、第１の基本ハッシュ関数と第２の基本ハッシュ関数とは、異なる基本ハッシュ関数であってもよい。この場合、あるデータに対して、第１のハッシュ値及び第２のハッシュ値の両方においてハッシュ値の衝突が発生する可能性を低減することができる。
【００６３】
また、ハッシュ関数ＨＣ（「ｈａｓｈＣ」）は、第１の付加データ及び第２の付加データのいずれとも異なる第３の付加データを第２の付加データに代えて用いる点においてのみハッシュ関数ＨＢと相違している。同様に、ハッシュ関数ＨＤ（「ｈａｓｈＤ」）は、第１の付加データ、第２の付加データ及び第３の付加データのいずれとも異なる第４の付加データを第３の付加データに代えて用いる点においてのみハッシュ関数ＨＣと相違している。
【００６４】
このように、情報処理装置１００は、付加データを変更することにより、複数のハッシュ関数を構成する。これによれば、容易に複数のハッシュ関数を用意することができる。
【００６５】
なお、ハッシュ関数ＨＡ〜ＨＤは、互いに異なるアルゴリズムに基づいて構成されていてもよい。
【００６６】
セル領域情報Ｄ３３は、図８に示したように、領域特定情報Ｄ８１と、ハッシュ関数特定情報Ｄ８２と、各セル領域に対応付けられたセグメント管理テーブルＤ８３と、を含む。
本例では、セル領域情報Ｄ３３は、第１のセル領域〜第３のセル領域からなる３つのセル領域を特定するための情報を含む。
【００６７】
領域特定情報Ｄ８１は、各セル領域に対応付けられた、外部記憶装置１１０を特定するための情報と、外部記憶装置１１０内の記憶領域（記憶位置（アドレス）の範囲）を特定するための情報と、を含む。
【００６８】
ハッシュ関数特定情報Ｄ８２は、各セル領域に対応付けられた、ハッシュ関数を特定するための情報を含む。本例では、ハッシュ関数特定情報Ｄ８２は、図９に示したハッシュ関数テーブルを含む。
【００６９】
ハッシュ関数テーブルは、ハッシュ関数を特定するための情報と、不使用フラグと、そのハッシュ関数を使用するセル領域を特定するための情報と、からなる情報を複数含む。不使用フラグは、ハッシュ関数の使用を禁止するか否かを表す情報である。不使用フラグに値が設定されていることは、ハッシュ関数の使用が禁止されていることを表す。一方、不使用フラグに値が設定されていないことは、ハッシュ関数の使用が許可されていることを表す。
【００７０】
本例では、情報処理装置１００は、セグメント管理テーブルＤ８３を、各セル領域の先頭の領域に記憶する。セグメント管理テーブルＤ８３は、セル領域が新たに設定された場合に作成される。
第１のセル領域に対応付けられたセグメント管理テーブルＤ８３は、図１０に示したように、第１のハッシュ値と、第２のハッシュ値と、参照回数情報と、アドレスと、からなる情報を複数含む。セグメント管理テーブルＤ８３内の各情報は、第１のハッシュ値と、第２のハッシュ値と、セグメントハッシュ管理テーブルと、ハッシュ関数テーブルと、を介して、セグメント番号と対応付けられている。
【００７１】
第１のハッシュ値は、セグメントを、ハッシュ関数テーブルにてセル領域と対応付けられた第１のハッシュ関数に入力することにより出力されたハッシュ値である。同様に、第２のハッシュ値は、セグメントを、ハッシュ関数テーブルにてセル領域と対応付けられた第２のハッシュ関数に入力することにより出力されたハッシュ値である。
【００７２】
参照回数情報は、セグメント（データ）が参照されている回数を表す情報である。また、アドレスは、セグメントが記憶されている記憶位置を表す情報である。
【００７３】
同様に、第２のセル領域に対応付けられたセグメント管理テーブルＤ８３は、第２のハッシュ値と、第３のハッシュ値と、参照回数情報と、アドレスと、からなる情報を複数含む。第３のハッシュ値は、セグメントを、ハッシュ関数テーブルにてセル領域と対応付けられた第３のハッシュ関数に入力することにより出力されたハッシュ値である。同様に、第３のセル領域に対応付けられたセグメント管理テーブルＤ８３は、第３のハッシュ値と、第１のハッシュ値と、参照回数情報と、アドレスと、からなる情報を複数含む。
【００７４】
ファイルシステム制御部１１は、情報処理装置１００が実行するプログラム（例えば、アプリケーションプログラム等）からのファイル書込要求又はファイル読出要求を受け付ける。ファイル書込要求は、ファイルを構成するデータと、そのファイルのパスと、を含む。ファイル読出要求は、ファイルシステムにおけるファイル名（パスを含むファイル名）を含む。
【００７５】
ファイルシステム制御部１１は、ファイル書込要求を受け付けると、受け付けたファイル書込要求に含まれるファイルを構成するデータを分割することによりセグメントを生成する。ファイルシステム制御部１１は、生成したセグメントを含む書込要求を書込要求受付部１２へ出力する。
【００７６】
また、ファイルシステム制御部１１は、ファイル読出要求を受け付けると、受け付けたファイル読出要求に含まれるファイル名と、図４〜図７に示したテーブルと、に基づいて、そのファイル名により特定されるファイルを構成するセグメントと対応付けられたハッシュ値（本例では、第１のハッシュ値〜第３のハッシュ値）を取得する。そして、ファイルシステム制御部１１は、取得したハッシュ値を含む読出要求を読出要求受付部１８へ出力する。
【００７７】
書込要求受付部１２は、ファイルシステム制御部１１により出力された書込要求を受け付ける。
ハッシュ値取得処理部１３は、書込要求受付部１２により書込要求が受け付けられた場合、ハッシュ関数テーブルを参照することにより、いずれかのセル領域に対して使用することが設定されているハッシュ関数のそれぞれに、当該書込要求に含まれるデータを入力することによりハッシュ値を取得する処理を行う。
【００７８】
例えば、図９に示したように、第１のセル領域（「ｃｅｌｌ１」）に対してハッシュ関数ＨＡ（「ｈａｓｈＡ」）及びハッシュ関数ＨＢ（「ｈａｓｈＢ」）を使用し、第２のセル領域（「ｃｅｌｌ２」）に対してハッシュ関数ＨＢ（「ｈａｓｈＢ」）及びハッシュ関数ＨＣ（「ｈａｓｈＣ」）を使用し、第３のセル領域（「ｃｅｌｌ３」）に対してハッシュ関数ＨＣ（「ｈａｓｈＣ」）及びハッシュ関数ＨＡ（「ｈａｓｈＡ」）を使用する。
【００７９】
従って、ハッシュ値取得処理部１３は、ハッシュ関数ＨＡ（第１のハッシュ関数）に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得し、且つ、ハッシュ関数ＨＢ（第２のハッシュ関数）に当該データを入力することにより第２のハッシュ値を取得し、且つ、ハッシュ関数ＨＣ（第３のハッシュ関数）に当該データを入力することにより第３のハッシュ値を取得する処理を行う。
【００８０】
即ち、ハッシュ値取得処理部１３は、３つの互いに異なるハッシュ関数ＨＡ〜ＨＣのそれぞれに書込要求に含まれるデータを入力することにより、３つのハッシュ値を取得する処理を行う。
【００８１】
記憶処理部１４は、書込要求受付部１２により書込要求が受け付けられた場合、セル領域情報Ｄ３３にて設定されている複数のセル領域のそれぞれに、受け付けられた書込要求に含まれるデータを記憶させる。
【００８２】
このとき、記憶処理部１４は、ハッシュ値取得処理部１３により取得された第１のハッシュ値と同一の第１のハッシュ値と、ハッシュ値取得処理部１３により取得された第２のハッシュ値と同一の第２のハッシュ値と、が対応付けて第１のセル領域に記憶されているか否かを判定する。
【００８３】
記憶処理部１４は、記憶されていないと判定した場合、書込要求に含まれるセグメントと、ハッシュ値取得処理部１３により取得された第１のハッシュ値と、ハッシュ値取得処理部１３により取得された第２のハッシュ値と、当該セグメントが参照されている回数としての所定の初期値（本例では、「１」）を表す参照回数情報と、を対応付けて第１のセル領域に新たに記憶させる。
【００８４】
一方、記憶処理部１４は、記憶されていると判定した場合、上記第１のハッシュ値及び上記第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
【００８５】
同様に、記憶処理部１４は、ハッシュ値取得処理部１３により取得された第２のハッシュ値と同一の第２のハッシュ値と、ハッシュ値取得処理部１３により取得された第３のハッシュ値と同一の第３のハッシュ値と、が対応付けて第２のセル領域に記憶されているか否かを判定する。
【００８６】
そして、記憶処理部１４は、記憶されていないと判定した場合、セグメントと、第２のハッシュ値と、第３のハッシュ値と、初期値を表す参照回数情報と、を対応付けて第２のセル領域に新たに記憶させ、一方、記憶されていると判定した場合、第２のハッシュ値及び第３のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
【００８７】
同様に、記憶処理部１４は、ハッシュ値取得処理部１３により取得された第３のハッシュ値と同一の第３のハッシュ値と、ハッシュ値取得処理部１３により取得された第１のハッシュ値と同一の第１のハッシュ値と、が対応付けて第３のセル領域に記憶されているか否かを判定する。
【００８８】
そして、記憶処理部１４は、記憶されていないと判定した場合、セグメントと、第３のハッシュ値と、第１のハッシュ値と、初期値を表す参照回数情報と、を対応付けて第３のセル領域に新たに記憶させ、一方、記憶されていると判定した場合、第３のハッシュ値及び第１のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
【００８９】
なお、記憶処理部１４は、取得されたハッシュ値と同一のハッシュ値が記憶されているか否かを判定する際に、記憶されているハッシュ値を１つずつ順に取り出し、取り出したハッシュ値と取得されたハッシュ値とを比較することにより上記判定を行う。また、記憶処理部１４は、取得されたハッシュ値と同一のハッシュ値が記憶されているか否かを判定する際に、二分探索法等の方法を用いてもよい。
【００９０】
ハッシュ関数変更処理部１５は、各セル領域に対して、ハッシュ値取得処理部１３により取得されたハッシュ値のうちのそのセル領域に対して使用するハッシュ関数に基づくハッシュ値の一方と同一のハッシュ値と、他方と異なるハッシュ値と、が対応付けてそのセル領域に記憶されている場合、以降において、ハッシュ値取得処理部１３が当該他方のハッシュ値を取得するために用いるハッシュ関数を他のハッシュ関数に変更する処理を行う。
【００９１】
即ち、例えば、ハッシュ関数変更処理部１５は、ハッシュ値取得処理部１３により取得された第１のハッシュ値と同一の第１のハッシュ値と、ハッシュ値取得処理部１３により取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて第１のセル領域に記憶されている場合、以降において、ハッシュ値取得処理部１３が第１のハッシュ値を取得するために用いるハッシュ関数を、第１のハッシュ関数から当該第１のハッシュ関数と異なる第４のハッシュ関数に変更する処理を行う。
【００９２】
なお、本実施形態の変形例において、ハッシュ関数変更処理部１５は、入力されるデータと出力されるハッシュ値とをｎ対１（ｎは、１を含む整数）に対応させることが可能なデータの範囲が第１のハッシュ関数よりも広いハッシュ関数を第４のハッシュ関数として選択するように構成されていてもよい。
これによれば、ハッシュ関数を変更することにより、以降においてハッシュ値の衝突が発生する可能性をより一層低減することができる。
【００９３】
具体的には、ハッシュ関数変更処理部１５は、ハッシュ関数テーブルにて、第１のハッシュ関数として設定されていたハッシュ関数ＨＡと対応付けられた不使用フラグに真を表す所定の値を設定する。
【００９４】
セル領域消滅処理部１６は、各セル領域に対して、ハッシュ値取得処理部１３により取得されたハッシュ値のうちのそのセル領域に対して使用するハッシュ関数に基づくハッシュ値の一方と同一のハッシュ値と、他方と異なるハッシュ値と、が対応付けてそのセル領域に記憶されている場合、記憶処理部１４がセグメントを記憶させるセル領域から当該セル領域を消去する処理を行う。
【００９５】
従って、例えば、セル領域消滅処理部１６は、ハッシュ値取得処理部１３により取得された第１のハッシュ値と同一の第１のハッシュ値と、ハッシュ値取得処理部１３により取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて第１のセル領域に記憶されている場合、記憶処理部１４がセグメントを記憶させるセル領域から当該第１のセル領域を消去する処理を行う。
【００９６】
また、セル領域生成処理部１７は、外部記憶装置１１０内のセル領域の数が予め設定された数（本例では、３つ）よりも少ない場合において、外部記憶装置１１０に新たに記憶可能なデータ量が所定の閾値量よりも多い場合、記憶処理部１４がセグメントを記憶させるセル領域の数を増加させる処理を行う。
【００９７】
ハッシュ関数変更処理部１５は、セル領域生成処理部１７によりセル領域が新たに追加された場合、そのセル領域に対して使用するハッシュ関数として、ハッシュ関数テーブルにて、値が設定されていない不使用フラグと対応付けられたハッシュ関数（例えば、第４のハッシュ関数）を設定する。
【００９８】
読出要求受付部１８は、ファイルシステム制御部１１により出力された読出要求を受け付ける。読出要求受付部１８は、受け付けた読出要求に含まれるハッシュ値と、図１０に示したセグメント管理テーブルと、に基づいて、各セル領域に記憶されているセグメントを読み出す。そして、読出要求受付部１８は、読み出したセグメントをファイルシステム制御部１１へ出力する。
【００９９】
ファイルシステム制御部１１は、読出要求受付部１８により出力されたセグメントからファイルを生成し、生成したファイルを、ファイル読出要求を出力したプログラムに対して出力する。
【０１００】
次に、上述した情報処理システム１の作動について具体的に述べる。
先ず、ファイルシステムを管理するための情報処理システム１の作動について、図１１を参照しながら説明する。
【０１０１】
外部記憶装置１１０の記憶領域には、セル領域が形成される。情報処理システム１は、セル領域の数が不足している場合にはセル領域を増加（生成）させ、一方、ハッシュ値の衝突が発生した場合にはセル領域を減少（消滅）させる。即ち、外部記憶装置１１０に新たに記憶可能なデータ量が所定の閾値量よりも多い場合、且つ、未使用フラグに値が設定されていない予備のハッシュ関数が存在している場合、外部記憶装置１１０の記憶領域は、セル領域を用いて自律的に管理される。
【０１０２】
先ず、情報処理装置１００は、ユーザからの指示に基づくファイルシステム作成要求を受け付ける（ステップ１１０５）。ファイルシステム作成要求は、アクティブな（使用する）セル領域の最大数を表す情報と、１つのセル領域に対して使用するハッシュ関数の数を表す情報と、を含む。本例では、使用するセル領域の最大数が３つであり、１つのセル領域に対して使用するハッシュ関数の数が２つである場合を想定する。
【０１０３】
次いで、情報処理装置１００は、ファイルシステムの初期化を行う（ステップ１１１０）。具体的には、情報処理システム１は、外部記憶装置１１０の記憶領域に記憶されているデータを消去し、内部記憶装置に記憶されているファイルシステム情報Ｄ３０を予め設定された初期値に設定する。
【０１０４】
そして、情報処理装置１００は、ステップ１１１５にて、１つのセル領域を設定（生成）する処理を行うため、図１２のステップ１２０５へ進む。
次いで、情報処理装置１００は、既に設定されているセル領域が存在するか否かを判定する。
【０１０５】
この状態においては、セル領域は１つも設定されていないので、情報処理装置１００は、「Ｎｏ」と判定してステップ１２１０に進む。そして、情報処理装置１００は、図９に示したハッシュ関数テーブルを参照しながら、値が設定されていない不使用フラグと対応付けられたハッシュ関数を２つ（ここでは、ハッシュ関数ＨＡ及びハッシュ関数ＨＢ）選択する。更に、情報処理装置１００は、セル領域として割り当てる記憶領域を特定する（ステップ１２１０）。
【０１０６】
更に、情報処理装置１００は、特定した記憶領域の先頭の領域にセグメント管理テーブルを作成する（記憶させる）（ステップ１２１５）。
【０１０７】
次に、情報処理装置１００は、ステップ１１２０へ進み、設定されたセル領域の数が上記最大数（本例では、３つ）以下であるか否かを判定する。この状態においては、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１１２５に進み、セル領域を生成するためのリソースが十分であるか否かを判定する。
【０１０８】
情報処理装置１００は、外部記憶装置１１０に新たに記憶可能なデータ量が所定の閾値量よりも多く、且つ、不使用フラグに値が設定されておらず、現在使用されていないハッシュ関数（値が設定されていない不使用フラグと対応付けられたハッシュ関数）が存在する場合には、リソースが十分であると判定する。
【０１０９】
情報処理装置１００は、ステップ１１２５にて「Ｙｅｓ」と判定した場合、ステップ１１３０に進み、ステップ１１１５と同様に、１つのセル領域を生成する処理を行うため、図１２のステップ１２０５へ進む。
【０１１０】
次いで、情報処理装置１００は、既に設定されているセル領域が存在するか否かを判定する。この状態においては、セル領域は１つ設定されているので、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１２２０に進む。
【０１１１】
情報処理装置１００は、図９に示したハッシュ関数テーブルを参照しながら、値が設定されていない不使用フラグと対応付けられたハッシュ関数を１つ（ここでは、ハッシュ関数ＨＣ）選択する。更に、情報処理装置１００は、セル領域として割り当てる記憶領域を特定する。
【０１１２】
次いで、情報処理装置１００は、廃棄されたセル領域が存在するか否かを判定する（ステップ１２２５）。廃棄されたセル領域は、後述するように、ハッシュ値の衝突が発生したことにより消滅させられたセル領域である。
【０１１３】
この状態においては、廃棄されたセル領域が存在しないので、情報処理装置１００は、「Ｎｏ」と判定してステップ１２３０に進み、既に設定されているセル領域の中から任意のセル領域を選択し、選択したセル領域に基づいて新たなセル領域を生成する処理を行う。
【０１１４】
具体的には、情報処理装置１００は、図１３に概念的に示したように、既に設定されているセル領域（ここでは、第１のセル領域）に記憶されているデータ（セグメント）及びセグメント管理テーブルを、新たに生成したセル領域（第２のセル領域）に記憶させる。
【０１１５】
更に、情報処理装置１００は、図９に示したハッシュ関数テーブルの情報を変更することにより、第１のセル領域に対して使用するハッシュ関数の一方（ここでは、ハッシュ関数ＨＢ）を第２のセル領域に承継させる。加えて、情報処理装置１００は、図９に示したハッシュ関数テーブルの情報を変更することにより、上記ステップ１２２０にて選択したハッシュ関数（ハッシュ関数ＨＣ）を第２のセル領域に対して使用するハッシュ関数として設定する。
【０１１６】
次いで、情報処理装置１００は、ステップ１２３５にて、上記ステップ１２２０にて選択したハッシュ関数（ハッシュ関数ＨＣ）に、第２のセル領域に記憶されている各セグメントを入力することにより出力されたハッシュ値により、第２のセル領域に記憶されているセグメント管理テーブル内の対応するハッシュ値（第３のハッシュ値）を置換する。
【０１１７】
そして、情報処理装置１００は、ステップ１１３５に進み、ハッシュ値の衝突が発生したか否かを判定する。ハッシュ値の衝突の詳細については後述する。
この状態においては、ハッシュ値の衝突は発生していないので、情報処理装置１００は、「Ｎｏ」と判定して、ステップ１１２０へ戻る。
【０１１８】
そして、情報処理装置１００がステップ１１２０〜ステップ１１３５の処理を繰り返し実行することにより、第２のセル領域と同様に第３のセル領域が生成される。これにより、外部記憶装置１１０には、図１４に概念的に示したように、第１のセル領域〜第３のセル領域が形成される。
【０１１９】
なお、情報処理装置１００は、複数のセル領域から任意の１対のセル領域を取り出した場合において、取り出したセル領域のうちの一方のセル領域に対して使用するハッシュ関数の一部が他方のセル領域に対して使用するハッシュ関数の一部と同一であり、且つ、一方のセル領域に対して使用するハッシュ関数の他部が他方のセル領域に対して使用するハッシュ関数の他部と異なるように、各セル領域に対してハッシュ関数を割り当てる。
【０１２０】
換言すると、情報処理装置１００は、上記書込要求に含まれるデータを記憶装置に記憶させる際、上記複数のセル領域のそれぞれに、当該データと、取得されたハッシュ値のうちの少なくとも２つのハッシュ値と、を対応付けて記憶させる。このとき、情報処理装置１００は、複数のセル領域の任意の１つである第１のセル領域に当該データと対応付けて記憶されている１つのハッシュ値が、当該第１のセル領域以外の第２のセル領域に当該データと対応付けて記憶され、且つ、当該第１のセル領域に当該データと対応付けて記憶されている他の１つのハッシュ値が、当該第１のセル領域及び当該第２のセル領域以外の第３のセル領域に当該データと対応付けて記憶されるように、データ及びハッシュ値を各セル領域に記憶させる。
【０１２１】
従って、本例では、第１のセル領域に対して使用するハッシュ関数として、ハッシュ関数ＨＡ及びハッシュ関数ＨＢが設定され、且つ、第２のセル領域に対して使用するハッシュ関数として、ハッシュ関数ＨＢ及びハッシュ関数ＨＣが設定され、且つ、第３のセル領域に対して使用するハッシュ関数として、ハッシュ関数ＨＣ及びハッシュ関数ＨＡが設定される。即ち、ハッシュ関数テーブルは、図９に示したように、情報が設定される。
【０１２２】
次に、ハッシュ値の衝突が発生した場合について説明する。
この場合、情報処理装置１００がステップ１１３５に進んだとき、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１１４０に進み、発生した衝突に係るハッシュ値を取得する基となったハッシュ関数を使用するセル領域を消滅させる。
【０１２３】
具体的には、情報処理装置１００は、セル領域情報Ｄ３３内の上記セル領域を特定するための情報に、当該セル領域を廃棄する旨を表す情報を設定する。これにより、情報処理装置１００は、以降において、このセル領域を廃棄されたセル領域として取り扱う。
【０１２４】
更に、情報処理装置１００は、図９に示したハッシュ関数テーブル内の、発生した衝突に係るハッシュ値を取得する基となったハッシュ関数と対応付けられた不使用フラグに、真を表す値を設定する。これにより、情報処理装置１００は、以降において、このハッシュ関数を使用しない。
【０１２５】
次に、廃棄されたセル領域が存在している場合において、情報処理装置１００がセル領域の生成を行う場合について説明する。
この場合、情報処理装置１００がステップ１２２５に進んだとき、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１２４０に進み、廃棄されたセル領域の中から任意のセル領域を選択し、選択したセル領域に基づいて新たなセル領域を生成する処理を行う。
【０１２６】
具体的には、情報処理装置１００は、廃棄されたセル領域に記憶されているデータ（セグメント）及びセグメント管理テーブルを、新たに生成したセル領域に記憶させる。
【０１２７】
更に、情報処理装置１００は、図９に示したハッシュ関数テーブルの情報を変更することにより、廃棄されたセル領域に対して使用するハッシュ関数の一方を新たに生成したセル領域に承継させる。加えて、情報処理装置１００は、図９に示したハッシュ関数テーブルの情報を変更することにより、上記ステップ１２２０にて選択したハッシュ関数を新たに生成したセル領域に対して使用するハッシュ関数として設定する。
【０１２８】
次いで、情報処理装置１００は、ステップ１２３５にて、上記ステップ１２２０にて選択したハッシュ関数に、新たに生成したセル領域に記憶されている各セグメントを入力することにより出力されたハッシュ値により、新たに生成したセル領域に記憶されているセグメント管理テーブル内の対応するハッシュ値を置換する。
これにより、セル領域を生成するための情報処理装置１００の処理負荷を軽減することができる。
なお、情報処理装置１００は、ハッシュ値の置換後に、活動している正常セルとのデータ同期を行うように構成されることが好適である。
【０１２９】
また、情報処理装置１００は、複数のセル領域のそれぞれに対して、同一のハッシュ関数に基づくハッシュ値を算出する場合、１つのセル領域に対して算出したハッシュ値を他のセル領域に対して設定するように構成されていてもよい。
【０１３０】
例えば、図１５に示したように、第１のセル領域に対して、ハッシュ関数ＨＤを用いて第１のハッシュ値を取得するとともに、第３のセル領域に対して、ハッシュ関数ＨＤを用いて第１のハッシュ値を取得する場合を想定する。
【０１３１】
この場合、情報処理装置１００は、第１のセル領域に記憶されているセグメントのうちの先頭側の半分に対して、第１のハッシュ値を取得し、取得した第１のハッシュ値を第１のセル領域に対して設定する。そして、情報処理装置１００は、取得した第１のハッシュ値を第３のセル領域に対しても設定する。
【０１３２】
一方、情報処理装置１００は、第３のセル領域に記憶されているセグメントのうちの末尾側の半分に対して、第１のハッシュ値を取得し、取得した第１のハッシュ値を第３のセル領域に対して設定する。そして、情報処理装置１００は、取得した第１のハッシュ値を第１のセル領域に対しても設定する。
【０１３３】
これによれば、情報処理装置１００が、第１のセル領域に記憶されているセグメントのすべてに対して、第１のハッシュ値を取得し、且つ、第３のセル領域に記憶されているセグメントのすべてに対して、第１のハッシュ値を取得するように構成されている場合と比較して、ハッシュ値を取得するための情報処理装置１００の処理負荷を軽減することができる。
【０１３４】
次に、ファイルを構成するデータを外部記憶装置１１０に記憶させるための情報処理システム１の作動について、図１６を参照しながら説明する。
【０１３５】
先ず、情報処理装置１００は、ファイル書込要求を受け付ける（ステップ１６０５、書込要求受付工程）。そして、情報処理装置１００は、ファイル書込要求に含まれるファイルを構成するデータを分割することによりセグメントを生成する。次いで、情報処理装置１００は、図９に示したハッシュ関数テーブルを参照することにより、いずれかのセル領域に対して使用することが設定されているハッシュ関数のそれぞれに、生成したセグメントを入力することによりハッシュ値を取得する処理を行う（ステップ１６１０、ハッシュ値取得処理工程）。
【０１３６】
本例では、図１７に示したように、情報処理装置１００は、ファイルを６個のセグメントＳ１〜Ｓ６に分割し、ハッシュ関数ＨＡ、ハッシュ関数ＨＢ及びハッシュ関数ＨＣの３つを用いてそれぞれのハッシュ値（第１のハッシュ値〜第３のハッシュ値）ＨＡ１〜ＨＣ６を取得する。
【０１３７】
次いで、情報処理装置１００は、ファイル書込要求に含まれるパスと、ファイルメタ情報テーブルと、ノード関係テーブルと、に基づいて、そのパスに対応するノード番号及び先頭セグメント番号を取得する。更に、情報処理装置１００は、取得したノード番号及び先頭セグメント番号と、ファイル構成セグメントテーブルと、に基づいて上記ファイルを構成するすべてのセグメント番号を取得する。そして、情報処理装置１００は、取得したセグメント番号と、セグメントハッシュ管理テーブルと、に基づいてそのセグメント番号により特定されるセグメント（既に外部記憶装置１１０に記憶されているセグメント）のハッシュ値を取得する。
【０１３８】
そして、情報処理装置１００は、各セル領域に対して、図１０に示したセグメント管理テーブルにて、取得したハッシュ値のうちのそのセル領域に対して使用するハッシュ関数に基づく２つのハッシュ値と同一の２つのハッシュ値と対応付けられた参照回数情報を、その参照回数情報が表す参照回数を１だけ減少させるように、変更する（ステップ１６１５）。
【０１３９】
次いで、情報処理装置１００は、図１０に示したセグメント管理テーブルにて、１以下の参照回数を表す参照回数情報と対応付けられたセグメントを、各セル領域から消去する（ステップ１６２０）。
【０１４０】
そして、情報処理装置１００は、セル領域毎に独立して記憶処理を実行する（ステップ１６２５、記憶処理工程）。ここでは、第１のセル領域に対する記憶処理について説明するが、他のセル領域に対する記憶処理も同様に行われる。
【０１４１】
情報処理装置１００は、第１のセル領域に対して記憶処理を実行するため、ステップ１８０５に進む。情報処理装置１００は、上記ステップ１６１０にて取得されたハッシュ値のうちの、そのセル領域に対して設定されている２つのハッシュ関数に基づくハッシュ値（即ち、第１のハッシュ値及び第２のハッシュ値）と同一の２つのハッシュ値が対応付けて記憶されているか否かを判定する。
【０１４２】
即ち、情報処理装置１００は、上記ステップ１６１０にて取得されたハッシュ値のうちの第１のハッシュ値と同一の第１のハッシュ値と、上記ステップ１６１０にて取得されたハッシュ値のうちの第２のハッシュ値と同一の第２のハッシュ値と、が対応付けて第１のセル領域に記憶されているか否かを判定する。
【０１４３】
いま、上記ステップ１６１０にて取得された第１のハッシュ値と同一の第１のハッシュ値と、上記ステップ１６１０にて取得された第２のハッシュ値と同一の第２のハッシュ値と、が対応付けられて第１のセル領域に記憶されている場合を想定して説明を続ける。
【０１４４】
この場合、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１８１０に進み、図１０に示したセグメント管理テーブルにて上記２つのハッシュ値と対応付けられた参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
【０１４５】
また、上記ステップ１６１０にて取得された第１のハッシュ値と異なる第１のハッシュ値のみが第１のセル領域に記憶され、且つ、上記ステップ１６１０にて取得された第２のハッシュ値と異なる第２のハッシュ値のみが第１のセル領域に記憶されている場合を想定して説明を続ける。
【０１４６】
この場合、情報処理装置１００は、ステップ１８０５にて「Ｎｏ」と判定し、ステップ１８１５に進む。そして、情報処理装置１００は、上記ステップ１６１０にて取得された第１のハッシュ値と異なる第１のハッシュ値のみが第１のセル領域に記憶され、且つ、上記ステップ１６１０にて取得された第２のハッシュ値と異なる第２のハッシュ値のみが第１のセル領域に記憶されているか否かを判定する。
【０１４７】
上記仮定に従えば、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１８２０に進み、上記ステップ１６１０にて生成されたセグメントと、上記ステップ１６１０にて取得された第１のハッシュ値と、上記ステップ１６１０にて取得された第２のハッシュ値と、初期値を表す参照回数情報と、を対応付けて第１のセル領域に新たに記憶させる。具体的には、情報処理装置１００は、セグメントが記憶される位置を表すアドレスと、２つのハッシュ値と、参照回数情報と、からなる情報を図１０に示したセグメント管理テーブルに追加する。
【０１４８】
また、上記ステップ１６１０にて取得された第１のハッシュ値と同一の第１のハッシュ値と、上記ステップ１６１０にて取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けられて第１のセル領域に記憶されている場合を想定して説明を続ける。
【０１４９】
この場合、情報処理装置１００は、ステップ１８１５にて「Ｎｏ」と判定してステップ１８２５に進み、第１のハッシュ値の衝突が発生したことを検知する。これにより、情報処理装置１００が図１１のステップ１１３５に進んだとき、情報処理装置１００は、「Ｙｅｓ」と判定してステップ１１４０に進み、第１のセル領域を消滅させるとともに、ハッシュ関数ＨＡと対応付けられた不使用フラグに真を表す値を設定する。
【０１５０】
次に、外部記憶装置１１０に記憶されているセグメントからなるファイルを読み出すための情報処理システム１の作動について、図１９を参照しながら説明する。
【０１５１】
先ず、情報処理装置１００は、ファイル読出要求を受け付ける（ステップ１９０５）。そして、情報処理装置１００は、ファイル読出要求に含まれるパスと、ファイルメタ情報テーブルと、ノード関係テーブルと、に基づいて、そのパスに対応するノード番号及び先頭セグメント番号を取得する。
【０１５２】
更に、情報処理装置１００は、取得したノード番号及び先頭セグメント番号と、ファイル構成セグメントテーブルと、に基づいて上記ファイルを構成するすべてのセグメント番号を取得する。そして、情報処理装置１００は、取得したセグメント番号と、セグメントハッシュ管理テーブルと、に基づいてそのセグメント番号により特定されるセグメント（既に外部記憶装置１１０に記憶されているセグメント）のハッシュ値を取得する。
【０１５３】
そして、情報処理装置１００は、図１０に示したセグメント管理テーブルにて、取得したハッシュ値のうちの２つと同一のハッシュ値と対応付けられたアドレスにて記憶されているセグメントを取得する（ステップ１９１０）。
【０１５４】
次いで、情報処理装置１００は、取得したセグメントと、ファイル構成セグメントテーブルと、に基づいてファイルを生成し、生成したファイルを、ファイル読出要求を出力したプログラムに対して出力する（ステップ１９１５）。
【０１５５】
以上、説明したように、本発明による情報処理システムの実施形態によれば、第１のハッシュ値及び第２のハッシュ値のいずれか一方の衝突が発生した場合であっても、他方を比較することによりデータ（セグメント）が同一であるか否かを検知することができる。即ち、ハッシュ値の衝突が発生した場合に、処理負荷が過大となることを防止しながらデータが同一であるか否かを検知することができる。これにより、２つの異なるデータを誤って同一のデータとして認識することを回避しながら、同一のデータが重複して外部記憶装置１１０（記憶装置）に記憶されることを回避することができる。この結果、記憶装置に記憶されるデータ量を減少させることができる。
【０１５６】
更に、上記実施形態において、情報処理装置１００は、取得された第１のハッシュ値と同一の第１のハッシュ値と、取得された第２のハッシュ値と異なる第２のハッシュ値と、が対応付けて記憶装置（第１のセル領域）に記憶されている場合、以降において、第１のハッシュ値を取得するために用いるハッシュ関数を、第１のハッシュ関数（ハッシュ関数ＨＡ）から当該第１のハッシュ関数と異なる第４のハッシュ関数（ハッシュ関数ＨＤ）に変更する処理を行う。
【０１５７】
これによれば、あるデータを含む書込要求を受け付けた場合に、第１のハッシュ値及び第２のハッシュ値のいずれか一方の衝突が発生する状態が継続することを回避することができる。従って、第１のハッシュ値及び第２のハッシュ値のいずれか一方を比較するだけで、そのデータと同一のデータが記憶されているか否かを検知することができる。即ち、情報処理装置１００の処理量を低減することができる。
【０１５８】
また、ハッシュ値の衝突が発生した場合、ハッシュ値の衝突が発生する基となったデータを、予め定められた規則に従って空き領域に記憶させ、且つ、データの読み出し時にその規則に従って当該データを読み出すように、情報処理装置が構成されている場合であっても、そのデータを読み出すために要する時間が過大となることを防止することができる。
【０１５９】
また、上記実施形態において、情報処理装置１００は、書込要求に含まれるデータを外部記憶装置１１０（記憶装置）に記憶させる際、外部記憶装置１１０内の複数のセル領域のそれぞれに、当該データを記憶させる。
【０１６０】
これによれば、１つのセル領域に記憶されているデータが消失した場合であっても、他のセル領域に記憶されているデータを取得することができる。即ち、外部記憶装置１１０に記憶されているデータの冗長性を確保することができる。
【０１６１】
また、上記実施形態によれば、１つのハッシュ値の衝突が発生した場合であっても、複数のセル領域に共通して記憶されているハッシュ値であり且つ衝突が発生していないハッシュ値を２つ以上確保することができる。この結果、例えば、ハッシュ値の衝突が発生した場合に、そのハッシュ値を、他のハッシュ関数に基づくハッシュ値に更新するように、情報処理装置が構成されている場合において、ハッシュ値の更新処理中に書込要求が受け付けられたときであっても、上述した効果を奏することができる。
【０１６２】
更に、上記実施形態において、情報処理装置１００は、外部記憶装置１１０（記憶装置）内のセル領域の数が予め設定された数よりも少ない場合において、外部記憶装置１１０に新たに記憶可能なデータ量が閾値量よりも多い場合、データを記憶させるセル領域の数を増加させる処理を行う。
【０１６３】
これによれば、外部記憶装置１１０に新たに記憶可能なデータ量が閾値量よりも多い場合には、予め設定された数までセル領域の数を増加させることができる。
【０１６４】
また、上記実施形態において、書込要求に含まれるデータは、ファイルを構成するデータを所定のデータサイズ毎に分割したデータブロックとしてのセグメントである。
これによれば、ファイルの一部のみが重複している場合に、その重複している部分が外部記憶装置１１０（記憶装置）に重複して記憶されることを防止することができる。この結果、外部記憶装置１１０に記憶されるデータ量をより一層減少させることができる。
【０１６５】
なお、本発明は上記実施形態に限定されることはなく、本発明の範囲内において種々の変形例を採用することができる。例えば、上記実施形態においては、情報処理システム１は、互いに独立した２つの装置として、情報処理装置１００と外部記憶装置１１０とを備えていたが、情報処理装置１００及び外部記憶装置１１０を含む１つの装置を備えていてもよい。また、情報処理装置１００の内部記憶装置に記憶されている情報は、外部記憶装置１１０に記憶されていてもよい。
【０１６６】
また、上記実施形態において、情報処理システム１は、１つの外部記憶装置１１０を備えていたが、複数の外部記憶装置１１０を備えていてもよい。加えて、上記実施形態においては、使用するセル領域の最大数は、３つであったが、１つ又は２つであってもよく、４つ以上であってもよい。同様に、１つのセル領域に対して使用するハッシュ関数の数も、３つ以上であってもよい。
【０１６７】
また、上記実施形態の変形例において、図２０に示したように、情報処理装置１００Ａの機能は、書込要求受付部１２Ａと、ハッシュ値取得処理部１３Ａと、記憶処理部１４Ａと、を含んでいてもよい。
【０１６８】
書込要求受付部１２Ａは、データを含む書込要求を受け付ける。
ハッシュ値取得処理部１３Ａは、書込要求受付部１２Ａにより書込要求が受け付けられた場合、第１のハッシュ関数に当該書込要求に含まれるデータを入力することにより第１のハッシュ値を取得するとともに第２のハッシュ関数に当該データを入力することにより第２のハッシュ値を取得する処理を行う。
【０１６９】
記憶処理部１４Ａは、ハッシュ値取得処理部１３Ａにより取得された第１のハッシュ値と同一の第１のハッシュ値と、ハッシュ値取得処理部１３Ａにより取得された第２のハッシュ値と同一の第２のハッシュ値と、が対応付けて記憶装置１１０Ａに記憶されていない場合、書込要求に含まれるデータと、取得された第１のハッシュ値と、取得された第２のハッシュ値と、当該データが参照されている回数としての所定の初期値を表す参照回数情報と、を対応付けて当該記憶装置１１０Ａに新たに記憶させる。
【０１７０】
一方、記憶処理部１４Ａは、ハッシュ値取得処理部１３Ａにより取得された第１のハッシュ値と同一の第１のハッシュ値と、ハッシュ値取得処理部１３Ａにより取得された第２のハッシュ値と同一の第２のハッシュ値と、が対応付けて当該記憶装置１１０Ａに記憶されている場合、当該第１のハッシュ値及び当該第２のハッシュ値と対応付けて記憶されている参照回数情報を、その参照回数情報が表す回数が１だけ増加するように変更する。
【０１７１】
この変形例によれば、上記実施形態と同様に、第１のハッシュ値及び第２のハッシュ値のいずれか一方の衝突が発生した場合であっても、他方を比較することによりデータが同一であるか否かを検知することができる。即ち、ハッシュ値の衝突が発生した場合に、処理負荷が過大となることを防止しながらデータが同一であるか否かを検知することができる。これにより、２つの異なるデータを誤って同一のデータとして認識することを回避しながら、同一のデータが重複して記憶装置に記憶されることを回避することができる。この結果、記憶装置に記憶されるデータ量を減少させることができる。
【０１７２】
なお、上記実施形態の他の変形例として、上述した実施形態及び変形例の任意の組み合わせが採用されてもよい。
【産業上の利用可能性】
【０１７３】
本発明は、データを記憶する記憶装置を複数備えるストレージシステム等に適用可能である。
【図面の簡単な説明】
【０１７４】
【図１】本発明の実施形態に係る情報処理システムの概略構成を表す図である。
【図２】図１に示した情報処理システムの機能の概略を表すブロック図である。
【図３】図１に示した情報処理装置が記憶しているファイルシステム情報である。
【図４】図１に示した情報処理装置が記憶しているファイルメタ情報テーブルである。
【図５】図１に示した情報処理装置が記憶しているノード関係テーブルである。
【図６】図１に示した情報処理装置が記憶しているファイル構成セグメントテーブルである。
【図７】図１に示した情報処理装置が記憶しているセグメントハッシュ管理テーブルである。
【図８】図１に示した情報処理装置が記憶しているセル領域情報である。
【図９】図１に示した情報処理装置が記憶しているハッシュ関数テーブルである。
【図１０】図１に示した情報処理装置が記憶しているセグメント管理テーブルである。
【図１１】図１に示した情報処理装置が、ファイルシステムを管理するために実行するプログラムを示したフローチャートである。
【図１２】図１に示した情報処理装置が、セル領域を生成するために実行するプログラムを示したフローチャートである。
【図１３】第１のセル領域に基づいて第２のセル領域が生成される際に、セル領域間で継承される情報を概念的に示した説明図である。
【図１４】生成されたセル領域を概念的に示した説明図である。
【図１５】第１のセル領域及び第３のセル領域のそれぞれに対して、ハッシュ関数ＨＤに基づく第１のハッシュ値を算出する場合における情報処理装置の作動を概念的に示した説明図である。
【図１６】図１に示した情報処理装置が、ファイル書込要求に応じてファイルを書き込むために実行するプログラムを示したフローチャートである。
【図１７】ファイルを構成するセグメントと、セグメント毎に取得されたハッシュ値と、を概念的に示した説明図である。
【図１８】図１に示した情報処理装置が、セグメントを記憶装置に記憶させるために実行するプログラムを示したフローチャートである。
【図１９】図１に示した情報処理装置が、ファイル読出要求に応じてファイルを読み出すために実行するプログラムを示したフローチャートである。
【図２０】本発明の実施形態の変形例に係る情報処理システムの機能の概略を表すブロック図である。
【符号の説明】
【０１７５】
１      情報処理システム
１１    ファイルシステム制御部
１２    書込要求受付部
１２Ａ  書込要求受付部
１３    ハッシュ値取得処理部
１３Ａ  ハッシュ値取得処理部
１４    記憶処理部
１４Ａ  記憶処理部
１５    ハッシュ関数変更処理部
１６    セル領域消滅処理部
１７    セル領域生成処理部
１８    読出要求受付部
１００  情報処理装置
１００Ａ  情報処理装置
１１０    外部記憶装置
１１０Ａ  記憶装置
【図１】
2010146308.tif 000003
【図２】
2010146308.tif 000004
【図３】
2010146308.tif 000005
【図４】
2010146308.tif 000006
【図５】
2010146308.tif 000007
【図６】
2010146308.tif 000008
【図７】
2010146308.tif 000009
【図８】
2010146308.tif 000010
【図９】
2010146308.tif 000011
【図１０】
2010146308.tif 000012
【図１１】
2010146308.tif 000013
【図１２】
2010146308.tif 000014
【図１３】
2010146308.tif 000015
【図１４】
2010146308.tif 000016
【図１５】
2010146308.tif 000017
【図１６】
2010146308.tif 000018
【図１７】
2010146308.tif 000019
【図１８】
2010146308.tif 000020
【図１９】
2010146308.tif 000021
【図２０】
2010146308.tif 000022