(57)【特許請求の範囲】
【請求項１】
複数の記憶装置に対する記憶対象データの記憶動作を制御する少なくとも１つの第一サーバと、前記複数の記憶装置を構成する複数の第二サーバと、を備えると共に、
記憶対象データを分割した複数のブロックデータを前記複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を備え、
前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶し、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置である前記第二サーバから前記格納位置特定テーブルを前記第一サーバに読み出し、前記第二サーバから前記第一サーバに読み出した前記格納位置特定テーブルに基づいて、さらに新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、
ストレージシステム。
【請求項２】
請求項１に記載のストレージシステムであって、
前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データが前記特定の記憶装置から読み出した前記格納位置特定テーブル内に存在しない場合に、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、
ストレージシステム。
【請求項３】
請求項１又は２に記載のストレージシステムであって、
前記記憶装置特定テーブルを記憶する複数の第三サーバを備え、
前記データ格納制御部は、前記記憶装置特定テーブルを前記複数の第三サーバに分散して記憶する、
ストレージシステム。
【請求項４】
複数の記憶装置を構成する複数の第二サーバに対する記憶対象データの記憶動作を制御する第一サーバに、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させるプログラムであり、
前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶し、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置である前記第二サーバから前記格納位置特定テーブルを前記第一サーバに読み出し、前記第二サーバから前記第一サーバに読み出した前記格納位置特定テーブルに基づいて、さらに新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、
プログラム。
【請求項５】
複数の記憶装置を構成する複数の第二サーバに対する記憶対象データの記憶動作を制御する第一サーバにて、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、
記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶し、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置である前記第二サーバから前記格納位置特定テーブルを前記第一サーバに読み出し、前記第二サーバから前記第一サーバに読み出した前記格納位置特定テーブルに基づいて、さらに新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、
データ格納方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステムにかかり、特に、重複記憶排除機能を有するストレージシステムに関する。
【背景技術】
【０００２】
近年、補助記憶装置のシステムに関する重複排除技術は、研究および商用アプリケーションの双方で大きく注目されてきた。重複排除技術により、データ内の同一ブロックを識別し、同一ブロックについては１つだけコピーを保存することで、必要な記憶容量が大幅に削減される。これまでの研究結果から、重複のかなりの部分がバックアップデータ内にあることがわかっている。大抵の場合、同一システムの後続のバックアップが非常に類似していることから考えても、これは当然である。
【０００３】
様々なストレージシステムにおける重複排除機能は、多くの側面で違いがある。同一のファイルのみを重複排除するシステムもあれば、ファイルを小さなブロックに分割してそのブロックについて重複排除処理を行うものもある。本願は、ブロックレベルでの重複排除に焦点を当てる。その理由は、バックアップのアプリケーションは一般的にバックアップされるファイルシステムからの個別のファイルをｔａｒのような大きなアーカイブに集約するからである。ファイルレベルでの重複排除では、あまり領域削減効果がないと思われる。
【０００４】
ブロックは固定サイズでも多様なサイズでもよく、多様なサイズのブロックは一般的にコンテンツ指定チャンク分割によって作成される。コンテンツ指定の多様なサイズのブロックを使用すると、重複排除の効率が大いに高まることが示されている。
【０００５】
ほとんどのシステムでは同一ブロックを削除するが、中にはブロックが類似していればよく、その違いを効率的に保存するものもある。これは重複排除の効果を高めることができるが、以前のブロックをディスクから読み出す必要があるため、高い書込みスループットを達成するのは難しい。したがって、この論文では同一ブロックの重複排除を中心に扱う。
【０００６】
（記憶装置の重複排除の概略）
一般的に、バックアップストレージシステムは、バックアップアプリケーションが作成した長いデータストリームを受け取る。これらのストリームは通常アーカイルファイブまたは仮想テープ画像である。データストリームはブロックに分割され、各ブロックについて安全なハッシュ値（例えばＳＨＡ−１）が計算される。これらのハッシュ値を、システム内に既に保存されているブロックのハッシュ値と比較する。安全なハッシュ関数にハッシュの衝突が発見されることはまずあり得ないため、同じハッシュ値のブロックは同一であるとみなす（いわゆる「ハッシュ比較」）。したがって、同じハッシュ値のブロックがあった場合はそのブロックが重複していると判断し、保存しない。データストリームを構成するすべてのブロックの識別子を保存し、読み出し時にオリジナルのデータストリームを再構築するのに使用する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】DUBNICKI, C., GRYZ, L., HELDT, L., KACZMARCZYK, M., KILIAN, W.,STRZELCZAK, P., SZCZEPKOWSKI, J., UNGUREANU, C., AND WELNICKI, M. HYDRAstor: aScalable Secondary Storage. In 7th USENIX Conference on File and Storage Technologies(San Francisco, California, USA, February 2009).
【非特許文献２】ZHU, B., LI, K., AND PATTERSON, H. Avoiding the disk bottleneck inthe data domain deduplication file system. In FAST’08: Proceedings of the 6thUSENIX Conference on File and Storage Technologies (Berkeley, CA, USA, 2008),USENIX Association, pp. 1‐14.
【非特許文献３】BIRK, Y. Random raids with selective exploitation of redundancy forhigh performance video servers. 671‐681.
【非特許文献４】UNGUREANU, C., ARANYA, A., GOKHALE, S., RAGO, S.,ATKIN, B., BOHRA, A., DUBNICKI, C., ANDCALKOWSKI, G. Hydrafs: A high-throughput file system for the hydrastorcontentaddressable storage system. In FAST ’10: Proceedings of the 8th USENIXConference on File and Storage Technologies (Berkeley, CA, USA, 2010), USENIXAssociation, pp. 225‐239.
【非特許文献５】DUBNICKI, C., UNGUREANU, C., AND KILIAN, W. FPN: A Distributed HashTable for Commercial Applications. In Proceedings of the Thirteenth InternationalSymposium on High-Performance Distributed Computing (HPDC-13 2004) (Honolulu, Hawaii,June 2004), pp. 120‐128.
【非特許文献６】BEN-OR, M. Another advantage of free choice (extended abstract): Completelyasynchronous agreement protocols. In PODC ’83: Proceedings of the second annualACM symposium on Principles of distributed computing (New York, NY, USA, 1983),ACM, pp. 27‐30.
【非特許文献７】LAMPORT, L. The part-time parliament. ACM Trans. Comput. Syst. 16, 2(1998), 133‐169.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
（ディスクベースの重複排除におけるパフォーマンスの課題）
大規模な重複排除ストレージシステムを実装するためには、パフォーマンスに関するいくつかの重要な課題を解決する必要がある。
【０００９】
大規模なシステムは膨大な数のブロックを保存するため、そのハッシュ値はメインメモリに収まらない。簡易なディスク上のハッシュインデックスを用いると、ランダムな読出しであるインデックスの検索によってパフォーマンスが著しく低下することになる。
【００１０】
すべての入力ブロックを一時的に保存してオフラインで重複排除を行うことで、この問題を解決しているシステムもある。この場合、すべての新規ブロックが事前にわかるため、ハッシュ検索をハッシュの順序に再編成することによって、バッチで効率よく検索を行うことができる。しかし、オフラインで重複排除を行うには、一時的にブロックを保存する大規模かつ高性能な中継領域が必要となる。一方、インライン重複排除システムは、すべての重複ブロックをまとめて書き込まなくてもよいため、一般的な重複率が高いケースでは、より高い書込み性能を提供することができる。
【００１１】
引用文献１に挙げるような多くのシステムでは、「ストリーム局所性観測」（一般的に後続のバックアップ内の重複ブロックは、オリジナルのバックアップと同様の順序通りに現れること）によってこの問題を解決している。バックアップストリームの局所性を保存することで、多くの重複ブロックのハッシュ値を効果的にプリフェッチできる。重複していないブロックは、メモリ内のブルームフィルタ（Bloom filters）を使用するか、またはパフォーマンスを高めるために多少の重複の可能性を犠牲にする「近似重複排除」で妥協することで、効率的に識別することができる。
【００１２】
もう１つの問題は、ストリームの断片化によるストリーミング読出し性能の低下である。重複しているブロックは、新たに書き込まれたブロックとは別の場所に保存されているため、大きな連続する読出しは内部で複数の短い読出しに分割されると思われる。この問題は、正確な重複排除を行うシステムにはつきものである。その理由は、２つのストリームがシステムに保存されており一方が他方のランダムな置換えになっている場合、少なくとも１つのストリームは小さなランダムな読出しをしなければならないからである。実際には、効率的な重複排除を可能にする同じストリーム局所性観測を行うことで、このような最悪のケースが起こらないようにすることができる。しかし、システムが老朽化するにつれて通常は断片化が進むため、不適切なデータ配置によって内部の局所性が悪化することがないよう注意が必要である。
【００１３】
（拡張性のあるグローバルな重複排除）
非特許文献２に挙げるような集中型システムは、システムのサイズに関して拡張性が限られている。独立したシステムをいくつか構成して容量を拡張することはできるが、それらの間では重複排除機能は無効となり、またバックアップを孤立した記憶装置に置くことでメンテナンスの負荷が増大する。
【００１４】
ブロックをそのハッシュ値に基づいてストレージノードに割り当てることによって、拡張性のあるグローバルな規模の重複排除を導入しているシステムもある（非特許文献１）。ここのシステムでは、大きなブロックのインデックスが全てのノードに有効に分割され、各ノードがハッシュ領域の一部を担当する。
【００１５】
このアーキテクチャは、クライアントが単一である設定では拡張性と良好なパフォーマンスを提供するが、複数のクライアンドが同時に読出しまたは書込みを行うとパフォーマンスの問題が発生する恐れがある。
【００１６】
ストリーム局所性の低下
ブロックはすべてのノードに対して均等に分散化されるため、概して全てのノードが、システムサイズのファクタで縮小された入力ストリームの一部を受け取る。大規模なシステムでは、これによってストリームの局所性が著しく低下する。オリジナルのストリームが保持していたストリームの局所性は、各ノード内でもこのファクタによって低下する。
【００１７】
あるストリームの重要な部分を読み出すには、システム内の全ノードの参加が必要である。多数のクライアントが同時に（異なる）ストリームを読み出そうとすると、各ノード上で同じリソースを奪い合うことになる。高いスループットを達成するためには、ストレージノードはクライアント数に比例する読出しキャッシュのサイズが必要である。これは「バッファ爆発問題（buffer explosion problem）」（非特許文献３）として知られている。この問題はストリームの局所性の低下によってさらに悪化し、プリフェッチの効率を低下させる。その結果、非常に大規模なシステムでは、順次的なオリジナルストリームの読出しは、ストレージノード内でランダムな読出しに劣化する。
【００１８】
重複排除の検索でも同じ問題がある。既存のブロックのハッシュ値のプリフェチもランダムな読出しに劣化する。しかし、ハッシュ値はブロックのデータよりもはるかに小さく、適当なサイズのキャッシュに容易に収まるため、重複排除に関する否定的な影響はあまり目立たない。
【００１９】
対称ネットワークのスループット
ブロックはストレージノードに均等に分散化されるため、全てのノードがほぼ同じ数のブロックをクライアントから受け取る。クライアントの数が増加すると、重複していないすべてのブロックの書込みを収容するためにネットワークのスループット要件も増加する。
【００２０】
その結果、高い書込みスループットを提供するためには、対称的な高い２地点間スループットを有するネットワークがシステムに必要となる。後に述べるが、大規模なシステム用にこのようなネットワークを構築することは難しい。
【００２１】
このため、本発明の目的は、上述した課題である、重複排除機能を有するストレージシステムにおける性能の低下を抑制することにある。
【課題を解決するための手段】
【００２２】
本発明の一形態であるストレージシステムは、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を備え、
前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
という構成をとる。
【００２３】
また、本発明の他の形態であるプログラムを記憶した記憶媒体は、
情報処理装置に、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させると共に、
前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
ことを実現させるためのプログラムを記憶した記憶媒体である。
【００２４】
また、本発明の他の形態であるデータ格納方法は、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、
記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
という構成をとる。
【発明の効果】
【００２５】
本発明は、以上のように構成されることにより、重複排除機能を有するストレージシステムにおける性能の向上を図ることができる。
【図面の簡単な説明】
【００２６】
【図１】実施形態１におけるポインタブロック内のブロックアドレスタイプを示す図である。
【図２】実施形態１における、システムのサイズの拡大に伴う負荷が書込み帯域幅に与える影響を示す図である。
【図３】実施形態１における、システムのサイズの拡大に伴う負荷が書込み帯域幅に与える影響を示す図である。
【図４】実施形態２におけるストレージシステムを含むシステム全体の構成を示すブロック図である。
【図５】実施形態２におけるストレージシステムの構成の概略を示すブロック図である。
【図６】実施形態２におけるアクセスノードの構成を示す機能ブロック図である。
【図７】図５に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図８】図５に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図９】図６に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１０】図６に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１１】本発明の付記１におけるストレージシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００２７】
＜実施形態１＞
本願では、グローバルなインライン重複排除機能を持つ拡張可能なストレージシステムのための、新たなアーキテクチャを提案する。このシステムでは、データ記憶装置を重複のインデックスから切り離すことで、システム規模による復元力の低下や全ノード間での均一帯域幅の必要性といった、既存のシステムが持つ欠点が改善される。
【００２８】
本願の実施形態１は、次のように構成されている。まず、システム設計の際に検討する要件と前提を述べる。次に、この要件を満たすアーキテクチャについて説明し、提案するデータ構成上の鍵となる動作を説明する。次に、提案するシステムが要求される特徴をどのように提供するのかを評価し、その設計時に直面するトレードオフの関係を提示する。
【００２９】
［要件と前提］
本願で提案するシステムアーキテクチャについて説明する前に、当該システムが機能する環境に関する要件と前提について概説する。
【００３０】
（ストレージシステムの要件の概要）
ストレージシステムの主な適用対象はバックアップデータである。重複排除を最大限節約するために、ストレージシステムは多数のクライアントシステムのバックアップデータを保存する。このような環境では、大容量、高信頼性、および特有の性能特徴が必要となる。短いバックアップ時間内にバックアップを完了させなければならないため、非常に高い総書込みスループットが必要である。このシステムは、ほぼ書込みを行い、つまりデータの読出しよりも書込みをはるかに頻繁に行うシステムである。読出しは、主にバックアップシステムに障害が発生し再構築を行う時に行われる。通常、システムの再構築にかかる時間は重要であることから、合理的な高い読出しスループットが必要とされる。
【００３１】
上記で説明した理由により、このストレージシステムによって実装される重複排除機能は、次の基準を満たさなければならない。
ブロックレベル
同一ブロック
多様なサイズのブロック：ブロックの境界はコンテンツ指定チャンク分割によって設定
ハッシュによる比較
正確性
インライン
分散型
グローバルな範囲
【００３２】
低コストを維持するため、このシステムは商用の装置で構成され、ペタバイト単位のｒａｗストレージに対応して数百／数千のノードまで拡張可能なものでなければならない。
【００３３】
インタフェース
このシステムは、クライアント装置に対して業界標準バックアップインタフェースを提供する必要がある。Ｄｉｓｋ−ｔｏ−Ｄｉｓｋバックアップの観点において、これは通常ＮＡＳ（Network Attached Storage）またはＶＴＬ（Virtual Tape library）としてエクスポートされるファイルシステムである。
【００３４】
ＮＡＳまたはＶＴＬの導入に関する詳細は本願のテーマとは関連がないため、ここでは、非特許文献１に記載されるものと類似する、より簡潔な「ブロック保存」インタフェースに焦点を当てる。非特許文献４に記載されるように、ファイルシステムは、このブロック保存のトップに構築することができる。
【００３５】
要するに、ブロック保存は多様なサイズのデータのブロックの保存を可能にする。ブロックは不変であり、ブロック保存によって生成されるアドレスを通して検索することができる。同一の内容を持つブロックに同じアドレスを割り当てることで、重複排除が実行される。
【００３６】
特別なポインタブロックは、個々のデータブロックを大きなデータストリームとして構成するために使用される。これらのポインタブロックはポインタが指すブロックのアドレスを含み、指す対象は通常のデータブロックまたはポインタブロックのいずれでもよい。通常ブロックと同様に、ポインタブロックも不変であり、同一のものは重複排除される。データストリームを表すポインタブロックのツリー（通常のデータブロックが葉になる）を構築することができる。このツリーのルートにあるポインタブロックのアドレスで、そのストリーム全体を検索することができる。
【００３７】
（ネットワークモデル）
このストレージシステムは、内部ネットワークをデータソース、つまりクライアントのバックアップ装置に接続することに加えて、必要とされる大容量にまで内部ネットワークを拡大する必要がある。ネットワークは、ストレージシステムのノード間およびデータソースへのリンクにおいて、高いスループットを提供する必要がある。
【００３８】
システムの規模が大きくなるにつれ、すべてのノード間で高い総スループットを実現する大規模ネットワークを構築するのは難しく、また高価になってくる。大規模なデータセンタのネットワークは階層的に構築されており、個々の装置が第１階層のスイッチ（例えば１Ｇビット）で接続され、第１階層のスイッチは、より高速な第２階層のスイッチ（例えば１０Ｇビット）等で接続されている。スイッチ間の接続は、合理的な総スループットを提供するためには高速化する必要があるが、より高速な内部接続を使用すればネットワークのハードウェアのコストが上昇し、また複数の物理的リンクを接合すればケーブル敷設が複雑化する。
【００３９】
当然、小規模なシステムは階層構造にはならず、すべてのノードが同じ第一階層のスイッチに接続され、すべてのノード間で同一の高いスループットが達成される。また、十分なリソースがあれば、総スループットの高い大規模ネットワークを汎用ネットワークハードウェア以外で構築することもできる。
【００４０】
したがって、ストレージシステムは以下の両方に適応可能でなければならない。
スイッチ内スループットが高くスイッチ間の総スループットが低い、階層的ネットワーク。
任意の２つのノード間で全断面（whole cross-section）帯域幅が利用可能な対称ネットワーク。
【００４１】
（クライアントシステムのパフォーマンスの制約）
ストレージシステムに書き込まれる、またはそこから読み出されるデータは、結果的にクライアント装置（バックアップサーバ）を通過しなければならない。各クライアントのバックアップサーバは、データの調達と受信のためのリソースが限られているため、ローカルディスクまたはネットワーク接続のいずれかがボトルネックとなる。
【００４２】
したがって、ストレージシステムは単一のストリームに高いスループットを提供する必要はなく、単一のクライアント装置のリソースは、ストレージシステムの数少ないノードよりも少ない（例えば１２）。しかし、複数のクライアント装置から同時に複数のストリームの読出し／書込みがあった場合には、良好な結合的なパフォーマンスを提供しなければならない。
【００４３】
［アーキテクチャ］
（概要）
本願で提案するストレージシステムは以下の種類のノードで構成される。
アクセスノード：システムへの入口の役割を果たし、またクライアント装置に接続する。
ストレージノード：データブロックを実際に保存する。
インデックスノード：重複の識別と位置特定を担当する。
【００４４】
異なる機能を持つノードは、ハードウェアの条件（例えば消費電力、冷却、使用するデータセンタ領域）により有益であれば、選択的に同じ物理的装置に結合することができる。
【００４５】
上記に定める要件を満たすために、本願では以下の設計目標を備えるストレージシステムを提案する。
【００４６】
局所性保存記憶装置
１つのストリームに属する非重複ブロックのシーケンスは、ストレージノードの小さなサブセット上に近接して保存される。これにより、上記で述べたストリームベースの局所性が保存され、再構築の際に効率的に順次読出しを行うことが可能となる。また、これは重複排除性能にとっても重要であり、重複ブロックのハッシュ値を効率的にプリフェッチすることができる。
【００４７】
このアプローチは、引用文献１に挙げるようなインライングローバル重複排除システムとは対照的である。これまでのシステムは重複インデックスとブロック保存を組み合わせ、ブロックをシステム全体に均等に分散させていた。また、ストリームの局所性をストレージノード内に保存しようとしているが、当初の分割によってその効果が減少している。
【００４８】
グローバルなハッシュベースのインデックス
ブロックが書き込まれるストレージノードは、ブロックのハッシュ値に依存しないので、別のブロックインデックスを維持しなければならない。このインデックスは、ブロックのハッシュ値に基づいて、システム内のすべてのインデックスノードに渡って分割される。ハッシュ領域には、いずれにしても局所性がないため、ここでハッシュ値を求めることは適切であり、それによって良好な拡張性、並列性、および負荷バランスが実現される。
【００４９】
記憶容量のバランス
ストリーム局所性の保存は、ある程度の最大ストリーム長までしか意味をなさない。これは順次的なディスクへのアクセスの効率によって決定される。１つの場所に十分な順次的なブロックが累積されれば、それ以上のブロックはどこかに保存される。したがって、所定のストリームの非重複ブロックが書き込まれるノードは、時間と共に変化する。これは容量のバランスを良好な状態に保つ役割を果たし、あるストレージノードが他のノードよりも早くフルになってしまう事態が避けられる。
【００５０】
非対称ネットワーク性能
データの場所はブロックのハッシュ値によって決定されるわけではないため、本願で提案するシステムでは、データの書込みを行うクライアント装置の近くのストレージノード上にデータを保存することができる。これにより、より高い階層のスイッチを介するデータ転送とそれに関連するネットワークのスループットのボトルネックを避けることによって、非対称ネットワーク内での書込み帯域幅を大きく改善することができる。重複排除のクエリーだけは、ネットワーク内のすべてのノードに一様に送信する必要があるが、これらは非常に小さく、大きな帯域幅を必要としない。上述したシステムを構成する論理的構成要素を以下に記載する。
【００５１】
（フロントエンド）
フロントエンドは、ファイルシステム、ＶＴＬや類似形態のデータをクライアントにエクスポートする。また入力される書込みストリームを多様なサイズのブロックに分割し、重複排除および保存の処理を行うためにそれらを提供する。フロントエンドはアクセスノード上に設けられる。システムのこの部分は、非特許文献１に記載される現在のＨＹＤＲＡｓｔｏｒと同じでもよい。
【００５２】
（ＤＨＴネットワークオーバーレイ）
分散されたコンセンサスを伴う「分散型ハッシュテーブル」を用いて「ネットワークオーバーレイ」層を実装する。ＤＨＴはシステムの拡張性のベースとなるものである。ネットワークオーバーレイは、以下のものを提供する。
オブジェクトの場所の仮想化。障害およびシステム再構築の際、物理的装置に論理オブジェクトを効率的にマッピングすることが可能となる。
障害の検出および耐性
負荷バランス（ＤＨＴのキー領域内でオブジェクトが均等に分散化されていると仮定）
小さなシステム全体の状態（グローバルな状態）の伝播と維持
【００５３】
（スーパーノードを含むＦＰＮ）
本願で使用するＤＨＴは、スーパーノードを備える「固定プレフィックスネットワーク」（ＦｉｘｅｄＰｒｅｆｉｘＮｅｔｗｏｒｋ：ＦＰＮ）（非特許文献５）である。ストレージシステムにおけるＦＰＮの使用については既に非特許文献１に記載されているため、ここでは本システムの内容におけるオーバーレイの機能についてのみ概説する。
【００５４】
オーバーレイネットワークは、キー（ハッシュ値）を、これらのキーに対して責任を持つ一連のノードにマッピングする。これをスーパーノードに編成する。各スーパーノードは一定数の「スーパーノードコンポーネント」から構成される。スーパーノードコンポーネントは物理的ノードに設けられる（この場合はインデックスノードとストレージノード）。１スーパーノード当たりのコンポーネント数、つまり「スーパーノード濃度」（ＳｕｐｅｒｎｏｄｅＣａｒｄｉｎａｌｉｔｙ:ＳＮＣ）は、所定のＦＰＮに対して固定されている。同じスーパーノードのメンバーであるコンポーネントを「ピア」という。
【００５５】
各スーパーノードは、ハッシュキー領域の一部、つまりスーパーノード間で分割されたハッシュ領域を担当する。その際、領域全体がカバーされ、かつスーパーノード間の担当が重複しないような方法を取る。
【００５６】
ノードの障害はスーパーノード内で対処する。所定のスーパーノードのすべてのコンポーネントは互いに継続的に接続を確認することによって、障害を検出し、状態の変化を伝える。あるノードに障害が発生した場合、そのノードに設けられているコンポーネントは、それ以外のピアによって再生される。
【００５７】
非特許文献６又は７に挙げる分散型のコンセンサスアルゴリズムは、すべてのコンポーネントにそのスーパーノードのメンバーシップの一貫した状態を確実に保つよう、使用される。コンセンサスの定足数を維持するためには、各スーパーノードのＳＮＣコンポーネントの半数以上が常に生存していなければならない。これにより、ネットワーク分割が「分離脳」動作を起こすこともない。
【００５８】
またＦＰＮは負荷バランスのレベルも提供する。ＦＰＮは、物理装置間で、利用できるリソースに比例してコンポーネントの分配を試みる。これは、各スーパーノードがほぼ同量の負荷を受ける（１秒当たりの使用容量および要求の両方において）ことを前提としている。また、障害耐性を高めるために、同じ物理的ノード上の「ピアコンポーネント」を同一場所へ配置することも回避する。
【００５９】
障害耐性と「グローバル状態」のブロードキャストを提供するよう拡張されていれば、異なるＤＨＴをＦＰＮの代わりに簡単に実装することができる。本願がスーパーノードを備えるＦＰＮを使用した理由は、ＨＹＤＲＡｓｔｏｒシステムでこの使用に成功しているからである。
【００６０】
（データＦＰＮとインデックスＦＰＮ）
本システムでは、次の２つのＤＨＴを使用する。
・データＦＰＮ
論理的なデータの位置を、その保存を担当するストレージノードにマッピングする。データＦＰＮのコンポーネントはストレージノード上に設けられている。このマッピングはデータ位置の仮想化を提供する。つまり、論理的な位置はシステムの再構築または障害時でも変更されず、データが設けられているストレージノードが変わった場合でも、変更されない。データＦＰＮの詳細は後に説明する。
【００６１】
インデックスＦＰＮ
ブロックのハッシュ値を、そのハッシュ値の変換を維持するインデックスノードに割り当てる。このネットワークのコンポーネントは、インデックスノード上に設置される。詳細は後に説明する。
【００６２】
インデックスノードとストレージノードとで別々のＦＰＮネットワークを用いることにより、これらのタイプのノードを異なるハードウェアに設置することが可能となる。例えば、インデックスノードはより多くのＣＰＵパワー、ＲＡＭ、およびＩＯＰＳを必要とする一方、ストレージノードは大きな記憶容量とディスクおよびネットワークの高いスループットを提供する。
【００６３】
この２つのネットワークのコンポーネントが同じ物理的装置上に設置されたとしても、上記の通り各々が異なるリソースを使用するため、通常は各ネットワーク内で独自に負荷のバランスが取られる。また、この２つのネットワークは異なるスーパーノード濃度（それぞれＳＮＣＩｎｄｅｘとＳＮＣＤａｔａ）を持ち、独立して成長する（ＦＰＮスプリットは互いに同期する必要はない）。
【００６４】
（ブロック保存）
（データ構成の概要）
このシステムに保存されるすべてのユーザデータは、データＦＰＮコンポーネントによってブロックとして保存される。ブロックは冗長符号化されてＳＮＣＤａｔａフラングメントとなる。これにはオリジナルのフラグメントと冗長フラグメントとが含まれる。オリジナルのフラグメントと冗長フラグメントとの割合はユーザがデータに割り当てたクラスによって決定される。ブロックは、書込み時にデータＦＰＮスーパーノードに割り当てられる。割当ポリシの詳細は後に説明する。
【００６５】
ＳｙｎｃｈｒｕｎとＳＣＣ
データＦＰＮスーパーノード内において、保存されたブロックはＳｙｎｃｈｒｕｎにグループ分けされる。同じブロックに属するフラグメントは、そのＳｙｎｃｈｒｕｎの該当するＳｙｎｃｈｒｕｎコンポーネントに入力される。各Ｓｙｎｃｈｒｕｎには、フラグメント番号０からＳＮＣＤａｔａ−１に対応する、ＳＮＣＤａｔａＳｙｎｃｈｒｕｎコンポーネントがある。Ｓｙｎｃｈｒｕｎとは、データ同期動作のための処理の原子単位である。ブロックは、バックグラウンドでのメンテナンス動作中は決してｓｙｎｃｈｒｕｎ境界を越えることはない。
【００６６】
不可欠な数のＳｙｎｃｈｒｕｎコンポーネントは、Ｓｙｎｃｈｒｕｎコンポーネントコンテナ（ＳｙｎｃｈｒｕｎＣｏｍｐｏｎｅｎｔＣｏｎｔａｉｎｅｒ：ＳＣＣ）にグループ分けされ、ＳＣＣはストレージノードのデータディスクに保存される。ＳＣＣは付加のみであり、ＳＣＣ全体が書き込まれた時点で不変となる。後続のバックグラウンド処理でのみＳＣＣを書き換えて修正するができる。
【００６７】
ＳｙｎｃｈｒｕｎコンポーネントのＳＣＣへのグループ分けは、１つのストレージノードが追跡すべき主体数を固定するために行う。ブロックがシステムから削除されるとＳｙｎｃｈｒｕｎのサイズは縮小する。ＳＣＣのサイズは、ほぼ１つのＳｙｎｃｈｒｕｎコンポーネントの当初のサイズ（約６４ＭＢ）に維持される。もし連続するＳｙｎｃｈｒｕｎのサイズが縮小されたら、それらを連結してサイズを維持する。
【００６８】
Ｓｔｒｅａｍｒｕｎ
複数の連続するＳｙｎｃｈｒｕｎは、Ｓｔｒｅａｍｒｕｎにグループ分けされる。このグループ分けは静的であり、Ｓｙｎｃｈｒｕｎが割り当てられた時点で決定される。Ｓｔｒｅａｍｒｕｎとは、良好な局所性を保つために同じスーパーノードに保持すべき同じストリームの一連のブロックに該当し、保存バランスを保つ単位である。
【００６９】
局所性の保持と容量バランスに品質との間にはトレードオフの関係があり、これはＳｔｒｅａｍｒｕｎのサイズによって制御することができる。このトレードオフの関係については、後に詳細に検討する。
【００７０】
（Ｓｙｎｃｈｒｕｎの識別）
各ｓｙｎｃｈｒｕｎは６４ビットの識別子で識別される。ＳｙｎｃｈｒｕｎのＩＤは、Ｓｙｎｃｈｒｕｎが属するスーパーノードを静的に決定する。
【００７１】
ＳｙｎｃｈｒｕｎのＩＤは論理的に次の３つの部分に分けられる。
スーパーノードゾーンのプレフィックス
そのスーパーノード内でのＳｔｒｅａｍｒｕｎのＩＤ
そのＳｔｒｅａｍｒｕｎ内でのシーケンス番号
【００７２】
シーケンス番号のビット数は固定されており、スーパーノードのプレフィックスとして解釈されるビット数は、システムが拡大しＦＰＮゾーンのプレフィックスの長さが長くなるにつれて増加する。詳細については後に説明する。
【００７３】
（ブロック識別とフラグメント検索）
このシステムに保存されるすべてのブロックには、それが書き込まれたＳｙｎｃｈｒｕｎ内のシーケンス番号が割当てられる。このシーケンス番号とＳｙｎｃｈｒｕｎのＩＤの組み合わせによって、システム全体に含まれるブロックを一意的に識別する。
したがって、（ＳｙｎｃｈｒｕｎＩＤ、ＢｌｏｃｋＳｅｑＮｕｍ）のペアを「ユニークブロックアドレス」という。このアドレスは、後にブロックが削除された場合でも再利用されることはない。
【００７４】
（書込みイニシエータ）
所定のスーパーノードに新規ブロックを保存する要求は、常にそのスーパーノードの固定のコンポーネント、つまり「書込みイニシエータ」を経由する。イニシエータは、Ｓｙｎｃｈｒｕｎ内で一意のブロック識別子を割当て、書込み処理と、そのスーパーノードの他のコンポーネントおよびインデックスＦＰＮとの間の調整を担当する。
【００７５】
（ＳＣＣインデックス）
未加工のフラグメントデータとは別に、各ＳＣＣは、そのＳＣＣに属するフラグメントのメタデータを保存する。このメタデータには、例えばブロックのハッシュ値、一意のブロックＩＤ、サイズ、およびＳＣＣ内でのフラグメントのデータの位置等が含まれる。
【００７６】
このメタデータは、データとは別にＳＣＣインデックス内に保存される。したがって、ＳＣＣインデックスは読出しの更新を迅速に行うことができ、フラグメントデータを飛ばし読む必要がない。
【００７７】
ＳＣＣ内でのフラグメントの位置がわかれば、ＳＣＣインデックスから個々のブロックのメタデータを読み出すこともできる。ブロックの削除により、一意のブロックＩＤだけではフラグメントの位置が特定されないため、外部から探す必要がある。
【００７８】
（グローバルブロックインデックス）
「グローバルブロックインデックス」とは、保存されたブロックのハッシュ値を一意のブロック識別子（例えば（ＳｈｎｃｈｒｕｎＩＤ、ＢｌｏｃｋＳｅｑＮｕｍ）のペア）にマッピングする、分散型のハッシュテーブルである。これはインデックスＦＰＮの上部に実装される。
【００７９】
ハッシュテーブルは、ブロックハッシュキーのプレフィックスに基づいて分割される。所定のブロックのハッシュ値の保存を担当するノードは、インデックスＦＰＮコンポーネントが設けられ、そのハッシュ値に対応ずるゾーンを有するノードである。１つのインデックスノード内において、マッピングはディスク上のハッシュテーブルに保存される。
【００８０】
グローバルブロックインデックスは障害耐性を有し、各ゾーンは、スーパーノードのすべてのＳＮＣＩｎｄｅｘコンポーネント上に複製される。
【００８１】
インデックスは、そのサイズによりディスクに保存される。更新はメモリ内に一時的に格納され、バックグラウンドで一括適用される。インデックスは、メモリ内のブルームフィルタを用いて存在しないブロックに関する安価なクエリーをサポートする。存在するブロックに関するクエリーは、１つのランダムなディスク読出しを必要とする。
【００８２】
（ディスク圧縮インデックス）
各ストレージノード内において、グローバルブロックインデックスは「ディスク圧縮インデックス（ＤｉｓｋＣｏｍｐａｃｔｅｄＩｎｄｅｘ：ＤＣＩ）」というディスク上のデータ構造に保存される。ＤＣＩは高いパフォーマンスで非重複ブロックを識別する必要がある。
【００８３】
ＤＣＩは、否定（非重複）クエリー用のメモリ内ブルームフィルタを備えるディスク上のハッシュテーブルと同様に、標準的なディスクの上部に実装することができる。これは非特許文献２に記載されているインデックスと類似する。
【００８４】
この解決策において、すべての更新、つまり変換の入力と削除は、ランダムな書込みを避けるためにメモリ内バッファに入れられる。ディスク上のハッシュテーブル、書込みバッファ、およびブルームフィルタは、バケットに分割され、各バケットはキー領域の一部に相当する。書込みバッファが一杯になると、バックグラウンドスイープによって各バケットが以下の順序で処理される。
ディスク上のハッシュテーブルのバケットを読み出す。
書込みバッファから更新があれば適用する。
バケット用のブルームフィルタ部分を再構築する。
更新したバケットをディスクにフラッシュする。
【００８５】
あるいは、インデックスをフラッシュベースのＳＳＤに保存することもできる。これについては最近研究が行われており、ＲＡＭ消費が削減される効果と、かなりの節電の可能性がある。
【００８６】
ハッシュテーブルのサイズを縮小するために、ＤＣＩはすべてのキー（ブロックのハッシュ値）を明示的に保存する必要はない。ハッシュテーブル内に衝突があった場合、照合する変換はすべて戻される。これらの「候補ブロック」は、適切なＳＣＣインデックスからそのメタデータを読出し、すべてのブロックのハッシュ値が一致するかどうかを確認することによって、検証することができる。さらにキーの数ビットがＤＣＩに追加保存された場合は、候補数は平均して１近くに維持することができる。
【００８７】
（ブロックインデックスの更新）
グローバルブロックインデックスは、ブロックのｓｙｎｃｈｒｕｎへの書込みに成功し、それが「ガーベジコレクション」処理によって削除された後、更新される。グローバルブロックインデックス内の、ブロックのゾーンのホスティングを担当するインデックスノードは、通常、実際にブロックを保存するストレージノードとは異なるため、インデックスの更新を慎重に同期させる必要がある。
【００８８】
新規に書込まれる各ブロックについては、ブロックをデータＦＰＮに書き込む書込みイニシエータによって、ハッシュキーから（ＳｙｎｃｈｒｕｎＩＤ、ＢｌｏｃｋＳｅｑＮｕｍ）への変換が作成される。この変換は適切なブロックインデックスゾーンを備えるインデックスノードに送られ、送信先であるインデックスノードの「変換ログ」保存され、バックグラウンドでＤＣＩに書き込まれる。変換ログ内に変換が維持される限り、インデックスノードは書込みイニシエータに返信する。
【００８９】
変換入力要求を失う可能性があるため、各書込みイニシエータはグローバルブロックインデックスに入力すべき（永続的な）変換のログを維持する。ログからの変換の入力要求は、インデックスノードから成功の返信を受信するまで定期的に再送信される。
【００９０】
インデックスノードは重複する変換の入力要求を受け取ることができる。（ＳｙｎｃｈｒｕｎＩＤ、ＢｌｏｃｋＳｅｑＮｕｍ）はすべての書込みに対して一意であるため、重複入力を安全に削除することができる。重複入力は通常、ＤＣＩの書込みバッファ内にあるうちに検出されるが、ＤＣＩのスイープ時に削除してもよい。
【００９１】
（削除）
変換は、ガーベジコレクションによってのみグローバルブロックインデックスから削除される。最も簡潔な解決策では、グローバルブロックインデックス全体を、ガーベジコレクション終了後に残っているブロックから再構築することができる。また、以下に述べる、より洗練された解決策もある。
【００９２】
ガーベジコレクションの目的において、システムの寿命は「エポック」と言われるフェーズに分割される。システム内でのすべてのブロックの書込みは、あるエポック内で実行される。現在のエポック数はグローバル状態に維持され、ガーベジコレクションの処理が開始されると前進する。エポックは、エポックｎ−１からのすべてのブロックがＧＢＩに追加された後にのみ、ｎ＋１に前進することができる。エポックｎでのガーベジコレクションでは、エポックｎ−２までに保存されたブロックのみ（つまり既に確実にＧＢＩ内にあるブロックのみ）を削除する。
【００９３】
これらのフェーズは、ＧＢＩ変換更新、ブロック削除、およびＧＢＩ変換削除の間での競争を避けるためのものである。ＧＢＩ入力要求（変換ログのエントリ）にはエポック番号が刻印され、古すぎるエポックからの要求は、受信するインデックスノードによって重複として排除される。ガーベジコレクションで、あるブロックを削除すべきと決定されると、その変換に対する削除要求が送信される。この要求には現在のエポックも刻印される。そのブロックが再び保存される場合は、別のｓｙｎｃｈｒｕｎになるため、別の変換となる。
【００９４】
（ハッシュのリース）
変換は、ブロックのｓｙｎｃｈｒｕｎへの保存に成功した場合にのみ、グローバルブロックインデックスに追加される。そのため、複数のクライアントが同時に同じブロックを書き込もうとすると競合が発生し、同じブロックが保存される可能性がある。
【００９５】
競合を避けるために、クライアントは、ブロックを保存に提供する前にグローバルブロックインデックスからそのブロックのハッシュ値を借りる（リースを取得する）。リースの取得は、書込みを行う可能性のある他のクライアントに対して、そのブロックがすでに書き込まれており、オリジナルの書込みを行う者と同期する必要があることを示すものである。そのハッシュ値に対して実際の変換が入力された場合、書込みに失敗した場合、またはリースの期限が切れた場合（例えば書込みを行うオリジナルのアクセスノードが応答を停止した場合）に、リースは返却される。
【００９６】
（変換キャッシュ）
「変換キャッシュ」とは、すでに保存されているブロックに対し効率的に重複排除を行うために使用する、ＳＣＣインデックスのメモリ内キャッシュであり、データストリーム内の重複ブロックの局所性を利用する（通常の重複ブロックは、当初保存されたときと同じ順序で書き込まれる傾向がある）。
【００９７】
変換キャッシュはアクセスノード上に位置する。各アクセスノードは、ブロックが重複しているかどうかを決定する際にローカル変換キャッシュを調査する。キャッシュは、そのホストであるストレージノードからＳＣＣインデックスをダウンロードすることによって追加入力される。キャッシュの容量は限られているため、最近変換が使用されていないＳＣＣインデックスはキャッシュから削除することができる。
【００９８】
変換キャッシュに保存されているＳＣＣインデックスは、その基礎となるＳＣＣが変更された場合には陳腐化する。変換キャッシュの内容は常に使用前にストレージノードで検証されるため、検証に失敗した場合はキャッシュから削除される。
【００９９】
［動作］
次に、上記のデータ構成における一般的な動作について説明する。
【０１００】
（書込みおよび重複排除）
ユーザからの書込みは、まずアクセスノードのフロントエンドで処理される。ここでは、書込みを多様なサイズのブロックに分割し、ブロックのツリーを構築する。各ブロックについて、ＳＨＡ−１ハッシュキーを計算し、これを使用してブロックが唯一のものか、または重複しているのかを決定する。
【０１０１】
（重複ブロック）
ブロックのハッシュキーを、まず変換キャッシュ内で検索する。そこに存在する場合は、候補となるオリジナルのブロックのｓｙｎｃｈｒｕｎとユニークブロックＩＤを検索する。ｓｙｎｃｈｒｕｎＩＤを使用して、要求をストレージノードに送信し、変換キャッシュのエントリが陳腐化していないこと、またブロックが、それに対する重複書込みに十分な耐性を持つことを検証する。この検証に通れば、書込み処理が完了する。
【０１０２】
ブロックが変換キャッシュ内にない場合、または検証に通らない場合は、ブロックのハッシュキーに関するクエリーをグローバルブロックインデックスに送信する。クエリーがＤＨＴを通って適切なインデックスノードに届けられると、グローバルブロックインデックスが読み出され、一連のブロック候補の位置が返信される。
【０１０３】
これらの候補を１つずつ検証する（実際には、平均１つの候補しかない）。各候補について、そのｓｙｎｃｈｒｕｎが置かれているストレージノードに要求を送信する。ユニークブロックＩＤを用いて、フラグメントメタデータの位置を検索し、ＳＣＣインデックスから読み出す。フラグメントメタデータはブロックのハッシュ値を含む。これは新たなブロックのハッシュ値と比較することができる。これらが一致し、ブロックに十分な耐性がある場合は、重複を検索する。そうでない場合は残っている候補のチェックを行う。
【０１０４】
重複ブロックが排除されたら、次の重複排除を高速化するために、オリジナルブロックのＳＣＣインデックスを変換キャッシュへ読み込むことを検討する。
【０１０５】
（ユニークなブロック）
変換キャッシュが利用可能なエントリを含まない場合は、グローバルブロックインデックスを調査する。グローバルブロックインデックス内にブロックがなかった場合は、ブルームフィルタを使用しているおかげで、ディスクにアクセスせず否定回答が返信される可能性が高い。候補が発見されなかった場合、またはすべての候補ブロックが拒否された場合、そのブロックは唯一のものであり、保存される。
【０１０６】
アクセスノードは、書き込まれる各データストリームについて、１つのオープンなＳｙｎｃｈｒｕｎを維持する。新規ブロックはすべてこのｓｙｎｃｈｒｕｎに保存される。ストリームに対してオープンなｓｙｎｃｈｒｕｎがない場合、または以前のｓｙｎｃｈｒｕｎの容量を超えた場合は、新たなｓｙｎｃｈｒｕｎが割り当てられる。
【０１０７】
オープンなｓｙｎｃｈｒｕｎが選択されると、ブロックは冗長符号化されてＳＮＣＤａｔａフラグメントになり、そのフラグメントはオープンなｓｙｎｃｈｒｕｎが置かれているスーパーノードのコンポーネントに送信される。コンポーネントの１つである書込みイニシエータは、書込み処理の同期を担当し、保存するブロックの変換をグローバルブロックインデックスに入力するための要求を送信する。また、ＳＮＣＤａｔａフラグメントの保存の確認を回収し、成功か失敗かをアクセスノードに返信する。
【０１０８】
（Ｓｙｎｃｈｒｕｎの割当て）
新たなＳｙｎｃｈｒｕｎは常に、そのＳｙｎｃｈｒｕｎを担当するスーパーノードの書込みイニシエータによって作成される。書込みイニシエータは、以前に割り当てられていたＳｔｒｅａｍｒｕｎおよびその中のＳｙｎｃｈｒｕｎを知っており、新たに割り当てられたＳｙｎｃｈｒｕｎが一意なＩＤを持つことを保証することができる。
【０１０９】
アクセスノードは、以下の２つの場合にＳｙｎｃｈｒｕｎを割り当てる必要がある。
新たなストリームの、最初の唯一のブロックを書き込む前。
以前のＳｙｎｃｈｒｕｎがフルになった場合。
【０１１０】
アクセスノードが、そのストリームにオープンになっているＳｙｎｃｈｒｕｎを既に所有している場合は、当然、同じＳｔｒｅａｍｒｕｎ内に次のＳｙｎｃｈｒｕｎを割り当てようとする。ＳｔｒｅａｍｒｕｎＩＤはスーパーノードを決定するため、割当要求をデータＦＰＮから適切な書込みイニシエータへ送信することができる。割当てに成功すると、書込みイニシエータは次のＳｙｎｃｈｒｕｎＩＤを割り当て、それをアクセスノードに戻す。そしてアクセスノードは、このＳｙｎｃｈｒｕｎＩＤを持つすべての新たな書込みを提供する。Ｓｔｒｅａｍｒｕｎがフルであるか、またはスーパーノードが不足しているとの理由で割当てに失敗した場合、アクセスノードは新たなＳｔｒｅａｍｒｕｎを割り当てなければならない。
【０１１１】
新たなＳｔｒｅａｍｒｕｎを割り当てるために、アクセスノードはまず、ホストとなる新たなスーパーノードを選択する。スーパーノードを選択するには、データＦＰＮ内のランダムなキーを検索し、そのキーを担当する書込みイニシエータに対して割当要求を送信する。割当てに成功したら、新たなＳｔｒｅａｍｒｕｎの最初のＳｙｎｃｈｒｕｎのＩＤをアクセスノードに返信する。そうでない場合、アクセスノードは別のスーパーノードを選択する。この基本割当ポリシを修正して、後述する非対称ネットワークに対応する特徴を提供することができる。
【０１１２】
通常、各クライアントストリームに対して個別のＳｙｎｃｈｒｕｎが割り当てられる。しかし、オープンなＳｙｎｃｈｒｕｎはストレージノード側にいくつかのリソースを必要とするため、１スーパーノード当たりの同時にオープンになるストリームの最大数には制限がある。同時にあまりにも多くのストリームが書き込まれると、同じＳｙｎｃｈｒｕｎが複数のストリームで使用されることにある。Ｓｙｎｃｈｒｕｎの共有による不都合な点は、同じＳｙｎｃｈｒｕｎに関連性のないデータが混在して、良い効果であるストリームの局所性が損なわれることである。我々は、実際には同時に書き込まれるストリームの数が膨大になるとは想定していないため、このケースに関して最適化する意図はない。
【０１１３】
（重複ブロックの同時書込み）
複数のアクセスノードが同時に同じブロックを書き込もうとした場合、同じブロックの複数のコピーが保存される可能性がある。グローバルブロックインデックスのリースは、このような事態が実際に発生するのを防ぐために使用される。
【０１１４】
リースは常に、新たなブロックが書き込まれる前に取得される。つまり、リースは、グローバルブロックインデックスのクエリーが候補を返信しない場合、またはすべての候補が明らかに拒否された場合に、自動的に取得される。リースには、書き込まれるブロックのハッシュ値と、このブロックを書き込むアクセスノードのアドレスが含まれる。
【０１１５】
グローバルブロックインデックスのクエリー中に、要求するハッシュ値のアクティブなリースが発見されると、他のアクセスノードが同時に同じブロックを書き込んでいるという通知が返信される。その後の書き込みは、オリジナルのアクセスノードに連絡を取り、オリジナルブロックの書込みが終了するまで待つ。
【０１１６】
リースは、そのハッシュ値の変換がＧＢＩに入力された場合、書込み処理に失敗した場合（例えば容量不足）、またはタイムアウトになった場合（例えばアクセスノードの障害）に、開放される。リースは、そのブロックのハッシュ値を担当するインデックスＦＰＮのスーパーノード内の選択されたコンポーネントによってのみ付与される。また、リースは、そのコンポーネントがしばらくの間そのスーパーノード内のクオラムから連絡を受けなかった場合は、付与されない。これにより、インデックスＦＰＮのコンポーネントが失敗した場合またはネットワークから分断された場合に、重複するブロックが同時に書き込まれる可能性が短時間に制限される。
【０１１７】
（読出し）
ブロックは、ポインタブロックにどのタイプのアドレスが保存されているかによって、ハッシュキーまたはユニークブロックＩＤのいずれかに基づいて読み出すことができる（これについては後に詳しく説明する）。ブロックは、十分な数のフラグメントを読み出すことで再構築することができる。実際にデータを読み出すためには、まずＳＣＣ内のフラグメントのオフセットを検索する必要がある。
【０１１８】
ハッシュに基づいて読み出すには、ユニークブロックＩＤを検索するためのステップがさらに必要である。変換キャッシュとグローバルブロックインデックスを調べることによって、重複排除処理と同様に行うことができる。
【０１１９】
アクセスノード上の変換キャッシュは、ＳＣＣオフセットを探すために使用される。キャッシュ内にユニークブロックＩＤがある場合は、関連するエントリに既にデータオフセットが含まれている。このオフセットは陳腐化している可能性があるため、フラグメント読出し要求を処理する際に、ストレージノードで検証する。変換キャッシュ内にフラグメントに関するエントリがなかった場合、フラグメント読出し要求は、そのフラグメントのｓｙｎｃｈｒｕｎを担当するストレージノードに提供される。
【０１２０】
ストレージノードは、変換キャッシュ内で発見されたオフセットを使用してデータを直接読み出すことができる。オフセットがわからない場合または無効である場合は、ＳＣＣインデックスのエントリを読み出さなければならない。これは、一般的にはコンポーネントの内の１つに対してのみ行えばよい。その理由は、同じブロックのフラグメントは、通常すべてのＳＮＣＤａｔａＳＣＣ内で同じオフセットに保存されているからである。
【０１２１】
重複排除と同様に、その後の読出しを高速化させるために、十分な数のフラグメントを含んだＳＣＣのインデックスが変換キャッシュにダウンロードされる。
【０１２２】
ブロックの再構築には、オリジナルのフラグメントのみを読み出せばよい。オリジナルのフラグメントが好ましい理由は、オリジナルのフラグメントからオリジナルのデータを再構築する場合は冗長符号の復号化が必要ないからである。しかし、複数のディスク内でより均等に読出し要求を展開するには、オリジナルではなくいくつか冗長フラグメントを読み出すことが有益である。
【０１２３】
（障害回復）
インデックスとストレージノードの障害は適切なＦＰＮ層によって検出される。障害が発生したノードに設けられているＦＰＮコンポーネントは、別のインデックス／ストレージノードに再形成される（コンセンサスを用いる）。このノードの選択は、１ノード当たりのコンポーネント数のバランスが維持されるように行う。
【０１２４】
コンポーネントの位置が変更されると、そのコンポーネントに関連するすべてのデータ（Ｓｙｎｃｈｒｕｎまたはグローバルブロックインデックスのエントリ）は、以前の位置から移行されるか、またはピアのコンポーネントから再構築される。この再構築処理はバックグラウンドで行われる。
【０１２５】
インデックスＦＰＮでは、グローバルブロックインデックスの変換が複製され、簡単にコピーすることができる。データＦＰＮでは、ＳＣＣは、残りのフラグメントを読み出し、オリジナルブロックを再構築し、不足しているフラグメントを再符号化し、不足しているＳＣＣを新たなコンポーネントの位置に書き込むことで、再構築される。
【０１２６】
負荷バランスを維持するため、回復したコンポーネントは通常、複数のノードに渡って展開される。したがって、データ再構築では、複数のノードに平行して書き込みを行い、高い再生パフォーマンスを生み出して迅速に意図する耐性レベルを回復する。
【０１２７】
（削除と領域の再利用）
ブロックの削除は分散型のガーベジコレクション処理を用いて行う。非特許文献１に記載されているアルゴリズムと同じものを本システムに適用することができる。
【０１２８】
分散型ガーベジコレクション
概説すると、ＳＣＣインデックス内で、各ブロックについて参照カウンタを維持する。ブロックの参照カウンタは、そのブロックを参照するポインタブロックの数である。
【０１２９】
カウンタ値は、周期的なガーベジコレクション処理によってのみ変化する。ガーベジコレクションは段階的に実行され、グローバル状態メカニズムを用いてグローバルに同期される。
【０１３０】
第１段階では、前回のガーベジコレクション以降に書き込まれた新たなポインタブロックをすべて処理し、カウンタのインクリメント要求を、ポインタで指されているブロックが設けられているストレージノードに送信する。すべてのブロックの処理が行われたら、ユニークブロックＩＤによって参照カウンタの更新が保存され、所定のＳＣＣ内のすべてのブロックに対して一括適用される。そして、参照カウンタが０のポインタブロックを識別する。これらのブロックは削除対象であるため、これらのブロックが指しているすべてのブロックに、カウンタのデクリメント要求を送信する。参照カウンタの更新を再び適用し、他にも削除されたポインタブロックがある場合は、新たなデクリメント段階を開始する。
【０１３１】
エポックと言われる複数段階に分割することにより、グローバルブロックインデックスの更新とブロック書込みとの同期が簡潔になる。つまり、ブロックは、書き込まれたのと同じエポック内では削除されることはなく、次のエポックに進むためには、進行中のすべてのグローバルブロックインデックスの更新が完了する必要がある。
【０１３２】
領域の再利用
ガーベジコレクションの処理は、ブロックを死んだものとマークするだけである。つまり、それらの変換がグローバルブロックインデックスから削除され、新たな重複が削除されることはないが、その保存領域はまだ開放されていない。この領域は、バックグラウンドで、一度に１つのＳＣＣについて再利用が行われる。
【０１３３】
領域の再利用はＳｙｎｃｈｒｕｎの平均サイズを縮小させる。ＳＣＣ当たりのメタデータの量が無限に増加するのを防ぐために、連続するＳＣＣを連結してバウンド内の平均ＳＣＣサイズを維持する。
【０１３４】
連続するＳｙｎｃｈｒｕｎを含むＳＣＣのみ連結可能である。同じＳｔｒｅａｍｒｕｎからのＳｙｎｃｈｒｕｎの連結が優先され、異なるＳｔｒｅａｍｒｕｎからのＳｙｎｃｈｒｕｎは、そのＳｔｒｅａｍｒｕｎからのデータを含む他のＳＣＣがない場合は１つのＳＣＣに入力される。
【０１３５】
（システム成長）
システムに新たなストレージノードが追加され容量が増える場合は、良好な負荷バランスを保つためにＦＰＮスーパーノードの数を増やす必要がある。そのためには、ゾーンプレフィックスの長さを長くすればよい。各ＦＰＮコンポーネントは、より長いプレフィックスを備える２つの新たなコンポーネントに分割される。
【０１３６】
グローバルブロックインデックスのエントリは、ハッシュキーに基づいて新たなコンポーネント間で分割される。
【０１３７】
Ｓｙｎｃｈｒｕｎも、この新たなスーパーノード間で分割される。そのためには、ゾーンプレフィックスとして解釈されるＳｙｎｃｈｒｕｎ識別子のビット数を長くし、ＳｔｒｅａｍｒｕｎＩＤの最も重要性が低いビットをゾーンプリフィックスに移動する。例えば、ＩＤ（プレフィックス：ｓｔｒｅａｍｒｕｎ：シーケンスＮｏ）が０１：０：０、０１：１：０、０１：２：０、０１：３：０、０１：４：０、０１：５：０であるＳｙｎｃｈｒｕｎは、分割後は０１０：０：０、０１１：０：０、０１０：１：０、０１１：１：０、０１０：２：０、０１１：２：０と等しい。
【０１３８】
その結果、システムが成長すると、ｓｙｎｃｈｒｕｎはＳｔｒｅａｍｒｕｎの処理単位で、新たなスーパーノード間で等しく分散される。
【０１３９】
分割後に異なるスーパーノードに属するＳｙｎｃｈｒｕｎが１つのＳＣＣと結合すると、そのＳＣＣはバックグラウンド処理で分割されることになる。しかし、これはめったに発生しない。その理由は、Ｓｔｒｅａｍｒｕｎ間の連結の前に、Ｓｔｒｅａｍｒｕｎ内の連結が優先されるからである。
【０１４０】
コンポーネント（およびデータ）は、瞬時的な書込み帯域幅を提供するために、常に新たに追加されたノードに対して再びバランスを取るように設定される。
【０１４１】
（データ構成の説明と評価）
（Ｓｔｒｅａｍｒｕｎのサイズの影響）
Ｓｔｒｅａｍｒｕｎのサイズによって、データのストリームに対して新たなスーパーノードが選択される頻度が決まる。Ｓｔｒｅａｍｒｕｎのサイズの選択に関連してトレードオフの関係がある。負荷バランスを考えると、新たなスーパーノードへのスイッチが頻繁に行われる（例えば各ｓｙｎｃｈｒｕｎの後）方が良い。ただし、次の点を考慮する必要がある。
システム成長後、スーパーノード間でデータが拡散される
ディスクのスピンダウンが回避される。
【０１４２】
各ｓｙｎｃｈｒｕｎの後にスイッチングを行う場合とスーパーノードがフルになった後にのみスイッチングを行う場合との、正しいバランスを探る必要がある。
【０１４３】
（容量のバランス）
スーパーノードのコンポーネントは、システム内の容量のバランスを取るために使用される。コンポーネントは、ストレージノードに対して、そのストレージノードの記憶容量に比例して割り当てられる。すべてのコンポーネントは常に移転するため、各ストレージノードに複数のコンポーネントが存在し、それによってバランスの規模を保っている。
【０１４４】
スーパーノードのコンポーネントのレベルでバランスを取ることによって、すべてのスーパーノードがほぼ同じサイズであれば、使用される容量のバランスが保たれる。Ｓｔｒｅａｍｒｕｎをスーパーノードに対して均等にランダムに割り当てることによって、著しくバランスの取れないサイズのスーパーノードが形成されることが抑制される。入力データと削除方式との間に関連性があれば、スーパーノードのバランスは保たれる。
【０１４５】
ハッシュ値を用いてブロックを分散させるシステムと比較すると、割当ユニットは比較的大きい。我々が提案するシステムではＳｔｒｅａｍｒｕｎ全体が割り当てられており、これは少なくとも３オーダーの規模でブロックよりも大きい。Ｓｔｒｅａｍｒｕｎが大きすぎると、スーパーノードに対するシンプルな均等割当が行われた場合に、システムの最大利用が損なわれると思われる。割当ユニットのサイズの選択によって、ランダムな割り当てによって達成される最大利用にどのような影響が出るのかを評価する実験を行った。Ｓｔｒｅａｍｒｕｎは、満杯のスーパーノードが出てくるまで、ランダムに選択されたスーパーノードに割り当てられる。この実験は、各スーパーノードのサイズが１．５ＴＢの、４８ＴＢのシステムを想定している。
【０１４６】
６４ＭＢのＳｔｒｅａｍｒｕｎでは、スーパーノード間のアンバランスは平均２％である。厳密に均等なランダム割当ポリシでは、容量の９８％に書込みが行われた場合にシステムがフルになると思われる。しかし、当初選択されたスーパーノードの容量が不足した場合に別のスーパーノードへの割り当てを試みることで改善できる。これにより、新規書込みによって使用がほぼ１００％に達することが可能になる一方、データの削除により著しいアンバランスが発生することもほとんどない。
【０１４７】
（冗長性と並列性）
データＦＰＮのスーパーノード濃度により、以下の事項が決定される。
データＦＰＮの冗長性。アクティブなＦＰＮコンポーネントの半分以下しか永久的な故障は許されない。そうでないとコンセンサスのクオラムが失われる。
利用可能なデータ復元クラスの数。冗長符号化は０からＳＮＣＤａｔａ−１までの冗長フラグメントを作成するよう構成することができる。
１つのストリームに割り当てられる並列性の数。
【０１４８】
各ブロックの書込みでは、ＳＮＣＤａｔａフラグメントの書込みが必要であり、ブロックの読出しでは、少なくともそのブロックのオリジナルフラグメントの読出しが必要である。したがって、１つのデータストリームが実際にはＳＮＣＤａｔａのストレージノードに分散化される。この分散化により、ＳＮＣＤａｔａストレージディスクまでのデータアクセスが並列化され、１ストリーム当たりのスループットが改善する。単一のストリームのスループットがさらに高いシステムを構成するために、ＳＮＣＤａｔａを増やすことができる。しかし、ＳＮＣＤａｔａが過剰になると、１つのブロックを読み出すのに多くのディスクにアクセスしなければならないため、ストリームの局所性とランダムな読出し性能が低下する。
【０１４９】
標準的なスーパーノード濃度の値は１２であり、これは、良好なストリームの局所性とランダムな読出し性能を維持しつつ、１つのクライアントのスループットを飽和させるのに十分な並列性を提供する。
【０１５０】
インデックスＦＰＮのスーパーノード濃度はこれより低くてもよい。その理由は、グローバルブロックインデックス変換が冗長符号化されるのではなく、複製されるからである。並列性は、本質的にハッシュベースの負荷分散によって提供されている。そのため、このケースではネットワークの生存可能性と利用可能性のみを検討すればよい。
【０１５１】
（ポインタブロック内のブロックアドレス）
ポインタブロックは、既に保存されている他のブロックを参照するブロックである。ポインタブロックは、個々のデータブロックを、ファイルまたはファイルシステム全体のスナップショットのようなデータ構造に組み込むために使用される。
【０１５２】
システムに保存される各ブロックは、コンテンツ由来のハッシュアドレスまたは位置に依存するユニークブロックアドレスのいずれかによってアクセスすることができる。これらのアドレスはいずれも、原則的にはポインタブロックに保存される。ポインタの種類の選択にはいくつかのトレードオフがある。これを図１に示す。
【０１５３】
アドレスサイズ
ハッシュアドレスは、何らかのメタデータ（例えば復元クラス）と連結したブロックのコンテンツのハッシュ値である。このアドレスは、想定されるサイズのシステムにおいて、ハッシュ衝突の可能性を無視するのに十分な大きさでなければならない。ＳＨＡ−１ハッシュ関数を使用すると仮定すると、ハッシュアドレスは２０バイトである。
【０１５４】
ユニークブロックアドレスは（ＳｙｎｃｈｒｕｎＩｄ、ｂｌｏｃｋｓｅｑｕｅｎｃｅｎｕｍｂｅｒ）のペアで、システム内のブロックを一意に識別する。ＳｙｎｃｈｒｕｎＩＤは体系的に割り当てられるため衝突の可能性がないことから、このアドレスはハッシュ値よりもはるかに小さくすることができる。ブロックを一意に識別するのに必要なビット数は、システムの寿命が続く間にシステムに書き込まれる非重複ブロックの数に依存する。ブロックのサイズがわずか１Ｋで１Ｓｙｎｃｈｒｕｎ当たり２１６ブロックと仮定すると、６４ビットのＳｙｎｃｈｒｕｎ識別子領域は、２４０ペタバイトの非重複データが書き込まれるまで使い果たすことはない。
【０１５５】
読出し性能
ブロックのデータを読み出す前に、ブロックの位置を検索する必要がある。複数のブロックを、当初書き込まれたときと同じ順序で順次読み出す場合、これらの検索のほとんどは、ディスクにアクセスすることなく変換キャッシュで対応する。しかし、変換キャッシュはストリームの最初の数ブロック（ストリームのＳＣＣインデックスがプリフェッチされるまで）の変換を含まない場合があり、またキャッシュはランダムな読出しには全く効果がない。この場合、コストの高いフラグメント位置検索を行う必要がある。
【０１５６】
ポインタブロックがハッシュアドレスの場合、この検索はグローバルブロックインデックスを介して行わなければならず、ディスク捜索が発生する。ユニークブロックアドレスの場合は、ＳｙｎｃｈｒｕｎＩＤがアドレス内に含まれているため、ディスク捜索は必要ない。
【０１５７】
ブロック再配置
Ｓｙｎｃｈｒｕｎからスーパーノードへの静的なマッピングを用いる場合、ブロックを別のＳｙｎｃｈｒｕｎに移動させたほうが良いケースもあり、非対称ネットワークでは負荷バランスを改善するために必要な場合がある。
【０１５８】
ポインタブロック内でハッシュアドレスを使用する場合、ブロックのＳｙｎｃｈｒｕｎは、それを指しているポインタブロックの内容を変えることなく、変更されることがある。一方、ユニークブロックアドレスを使用する場合、再配置されたブロックを指すすべてのポインタブロックを更新しなければならない。ポインタブロックに保存されているアドレスはポインタブロックのハッシュ値の計算に含まれているため、更新した場合は、ブロックツリーのルートまでこれを伝える必要がある。
【０１５９】
ハッシュ検索の要件
ハッシュアドレスによるブロックの読出しは、グローバルブロックインデックスに存在する変換に依存する。これがブロックを読み出す唯一の方法である場合、システムは、ブロック書込み処理が完了する前にＧＢＩの更新に成功したことを保証しなければならない。これにより、ブロック書込み処理のレイテンシが増えるか、またはハッシュリースの持続性が要求される。
【０１６０】
システム回復
システムに、構成上耐えられる以上の障害が発生した場合、読出し不能になるブロックが出てくる可能性がある。重複排除により、読出し不能のブロックを含むすべてのファイルシステムのスナップショットが影響を受ける。
【０１６１】
多くの場合、消失したデータもオリジナルのシステム内に存在し、次のバックアップ時にシステムに書き込まれる。そのブロックは、同じハッシュアドレスで新たなＳｙｎｃｈｒｕｎに再び保存される。
【０１６２】
ポインタブロックに、ユニークブロックアドレスではなくハッシュアドレスが含まれている場合、この新たなブロックは、当初は読出し不能のブロックを指していた古いファイルシステムを読み出す際にも使用されることがある。事実上、失ったブロックを再度書き込むことで、システムは自動的に「回復」すると思われる。
【０１６３】
ヒント（hint）を持つポインタブロック
ポインタブロック内の各ポインタ用のハッシュアドレスとユニークブロックアドレスとを保存することで、ハッシュアドレスの利点（ブロック再配置、システム回復）とユニークブロックアドレスの利点（より良いランダム読出し性能、ハッシュ検索に関する緩やかな要件）とを組み合わせることができる。ハッシュアドレスは信頼性がありポインタブロックのハッシュ値にしか影響を与えない。ユニークブロックアドレスはヒントであり、ヒントが最新のものである場合にグローバルブロックインデックスの更新を回避するために使用される。ヒントは陳腐化することがあり（指されたブロックの位置が変わったか、または読出し不能になった場合）、その場合にヒントはゆっくり（更新される。このアプローチの不都合な点は、ほとんどの記憶容量がポインタブロック用に必要となることである。
【０１６４】
（ユニークなブロックの書込み性能）
上記で説明した通り、バックアップシステムでは読出しよりも書込みの方が多く行われ、このシステムを実現可能にするためには高い書込みスループットが不可欠である。
【０１６５】
本願で提案するアーキテクチャでは、ユニークなデータのすべてのストリームが、当初書き込まれるときにＳＮＣＤａｔａディスクを越えて分散化される。一方、ハッシュベースのブロック分散を行うシステムでは、書込みはすべてのディスクに渡って均等に展開される。したがって、本願が提案するシステムが提供する単一ストリーム書込みスループットは非常に低い。しかし、上記に記載した通り、一般的に１つのクライアントシステムがそのような高いスループットを利用することはできないため、我々はこの制限は重要ではないと認識している。
【０１６６】
負荷バランス
大規模なシステムでは、一般的に複数のストリームが同時に書き込まれる。Ｓｙｎｃｈｒｕｎは、各ストリームに対してランダムにかつ独立して割り当てられる。そのため、同じスーパーノードが複数のＳｙｎｃｈｒｕｎのホストとして選択されることがあり、いくつかのストリームが１つのストレージノードのスループットを共有しなければならないことがある。
【０１６７】
このような負荷のアンバランスは、Ｓｙｎｃｈｒｕｎ割当てアルゴリズムにおいて複数のランダムな選択を使用すれば緩和できる。新たなスーパーノードを選択する場合、ランダムに選択されたｄ個のスーパーノードに対してクエリーを送信し、アクティブに書き込まれたＳｔｒｅａｍｒｕｎの数が最も少ないスーパーノードを選択する。複数のランダムな選択を用いることで、ランダム化された負荷バランスを著しく改善することができることが示される。
【０１６８】
図２及び図３は、システムのサイズの拡大に伴う負荷のアンバランスが書込み帯域幅に与える影響を示している。様々な数のスーパーノードと割当てクエリーに関して、ｎ個のＳｔｒｅａｍｒｕｎのｎ個のスーパーノードへの割り当てをシミュレートした。なお、スーパーノードの数は常にシステムのサイズに比例する。
【０１６９】
図２は１つのスーパーノードに割り当てられるＳｔｒｅａｍｒｕｎの最大数の平均を示している。予想した通り、割当てクエリーを１つ追加しただけで、スーパーノードに含まれるＳｔｒｅａｍｒｕｎの最大数が大きく減少する。しかし、クエリーが多くなっても、複数のアクティブなＳｔｒｅａｍｒｕｎを含むスーパーノードが発見される可能性は高い。Ｓｔｒｅａｍｒｕｎがそのようなスーパーノードに割り当てられたストリームは、そのＳｔｒｅａｍｒｕｎを使い果たして新たなものが割り当てられるまで、書込みスループットが低下したままとなる。
【０１７０】
しかし、図３を参照すると、個々のストリームはいくらか遅延するものの、総合的な書込み帯域幅に対して負荷のアンバランスが与える影響は大きくないことを示している。書込み帯域幅は、少なくとも１つのＳｔｒｅａｍｒｕｎを割り当てられたスーパーノードの数を数えることで計算された（１つのスーパーノードのスループットを飽和させるには１つのストリームで十分であるとの前提に基づく）。非常に大規模なシステムでも、１０のクエリーの場合、達成された帯域幅は最大値の５％以内であった。
【０１７１】
ストリームのソート
ハッシュベースの分散を行うシステムにおいて、異なるストリームに属する書込みは同じストレージコンテナ内で多重化される。同じストリームが一緒に読み出されることはないと思われるため、このような多重化されたコンテナを読み出すのは効率が悪い。その理由は、不要なデータストリームを飛ばす必要があるからである。非特許文献１では、ストリームのソートを用いて、ストリームからのデータを合体して大きなチャンクにすることによって、将来の読出しを改善する。しかし、ストリームのソートは、書込み処理中にインラインで実行した場合はレイテンシが増加する。または、バックグラウンド処理で、すべてのデータをストリームがソートされた順序に書き直す必要がある。
【０１７２】
本願が提案するアーキテクチャでは、ストリーム毎に個別のＳｔｒｅａｍｒｕｎが作成されるため、異なるストリームからのデータをまとめて多重化することはない。
【０１７３】
（読出しスループット）
本願で提案するアーキテクチャの主な目的は、ストリーム局所性の保存性を高めて大規模なシステムにおける.読出しスループットを改善することである。
【０１７４】
（ストリーム局所性の保存）
正確な重複排除処理を行うストレージシステムでは、当然ストリーム局所性が低下する。本願の焦点は、ストレージシステムの内部データ構成に起因する更なる性能の低下であるため、ユニークなデータブロックのストリームに関して局所性がどのように保存されるかを分析することで、重複排除の影響を取り除く。
【０１７５】
まず、入力ストリームをＳｙｎｃｈｒｕｎのサイズに分割して、その各部分を順次ディスク上に置く。１つのＳｙｎｃｈｒｕｎの想定サイズは数メガバイトから数十メガバイトの範囲であるため、入力ストリームの順次読込みは、保存ディスクをほんのわずかしか探さなくてよい。
【０１７６】
削除処理では、Ｓｙｎｃｈｒｕｎｓの中央からブロックを削除することができる。そしてガーベジコレクションによりＳｙｎｃｈｒｕｎのサイズが縮小される。Ｓｙｎｃｈｒｕｎのサイズが順次読出しの性能に多大な影響を与えるほど縮小する前に、上記で説明したように連続するＳｙｎｃｈｒｕｎを連結する。連結により、Ｓｔｒｅａｍｒｕｎのサイズまでデータの局所性を保存する。Ｓｔｒｅａｍｒｕｎのサイズになったデータストリームの部分からあまりに多くのブロックが削除され、Ｓｙｎｃｈｒｕｎの半分しか残らなくなると、連結は、別のＳｔｒｅａｍｒｕｎに属するＳｙｎｃｈｒｕｎを統合し始める。そのため、オリジナルのストリームの局所性の保存に関しては有効性がなくなる。
【０１７７】
システムが成長すると、使用容量のバランスを保つために既存のデータが新たなノードに転送される。しかし、上述したように、Ｓｔｒｅａｍｒｕｎは常に１つのユニットとして一緒に保存される。したがって、新たなストレージノードが追加されてもストリームの局所性は影響を受けない。
【０１７８】
（ハッシュベースのブロック分散との比較）
ハッシュベースのブロック分散および本願で提案するストリーム毎のブロック分散のいずれにおいても、読出しスループットは、書込み時および読出し時の双方でのアクセスパターンに大きく依存する。この２つのアーキテクチャ間のトレードオフをよりわかりやすくするために、いくつかの典型的なシナリオでこれらのシステムがどのように機能するかを分析する。
【０１７９】
単一ストリームの書込み、単一ストリームの読出し
大規模なシステムではまずあり得ないと思われる最もシンプルなシナリオは、当初保存されたときに唯一書き込まれたストリームであった１つのストリームを、順次読み出すものである。この場合、ハッシュベースの分散は非常に効率的であり、すべてのストレージノードの混合スループットを提供する。本願で提案するアーキテクチャのパフォーマンスも十分に良好で、ＳＮＣＤａｔａストレージノードの並列性を有し、単一のクライアントの需要を十分満たすと思われる。
【０１８０】
複数ストリームの書込み、単一ストリームの読出し
同時に複数のストリームが書き込まれ、後にその内の１つしか読み出されない状況は、実際のシステムでは間違いなく極めて一般的である。このような状況は、共有バックアップ時間に複数のシステムのバックアップを平行して行い、その後、その内の１つだけに障害が発生してバックアップから回復させる場合によく発生する。
【０１８１】
この状況は、ハッシュベースの分散を用いるシステムにはあまり好ましくない。すべてのストリームに属するブロックが同じディスク上コンテナに均等に分散されているため、１つのストリームだけを読み出すのに、他のブロックを探索するかまたは飛ばすかのどちらかが必要となる。非特許文献１では、ブロックが書込みバッファに提供されるのを待っているときに、バックグラウンドおよび書込み中はインラインの両方でストリームＩＤにしたがってコンテナ内でブロックをソートすることにより、この問題の解決を図っている。このようなストリームのソートの効果はコンテナのサイズによって制限される。
【０１８２】
本願が提案するアーキテクチャは、異なるデータストリームからの書込みが独自のコンテナにソートされるため、この問題の影響を受けない。このケースでの読出しスループットは、やはりＳＮＣＤａｔａストレージノードの結合スループットである。
【０１８３】
複数ストリームの読出し
複数のバックアップシステムに大規模な障害が発生した後、複数のバックアップが画像を平行して復元させる場合に、複数のストリームを同時に読み出すことがある。しかし高度に断片化された重複排除されたストリームを読み出す際には、１つの外部読出しストリームでもシステムにとっては複数のストリームを読み出すのと同じようなものである。
【０１８４】
ハッシュベースで分散されたシステムでは、すべてのストレージノードが各ストリームの縮小バージョンを効果的に保存している。ストリーム全体を再形成するためには、これらの縮小化された各ストリームを並行して読み出さなければならない。すべてのストレージノードが、システム内の読み出される各ストリームからのアクセスに対応しなければならない。ストレージノードおよびアクセスノードの両方とも、読出しを一時格納するための固定量のメモリを備えているため、同時に読み出すストリームの数が増えればより、小さなディスク読出しサイズを使用しなければならない。小さなサイズのディスク読出しを使用するとスループットが大幅に減少し、最終的には順次的な読出しがランダムなブロック読出しに劣化する。 
【０１８５】
本願で提案するシステムでは、各データストリームはほんのわずかなストレージノード群に対してのみ分散化されているため、同じ問題に直面することはない。しかし、ハッシュベースの分散とは異なり、不完全な負荷バランスの問題がある。小さなストレージノード群から多数のストリームを読み出すことは可能だが、他のストレージノードがアイドル状態になる。いくつかのオリジナルのフラグメントの代わりに冗長フラグメントを読み出す方法を採用すれば、冗長符号化アルゴリズムによりＣＰＵの消費が増加するが、それを犠牲にして負荷バランスを改善することができる。それでも、多数のストリームを同時に読み出す場合は、ハッシュベースのブロック分散を用いるよりも読出し性能は著しく高くなる。
【０１８６】
（グローバルブロックインデックスの更新）
上記で説明したように、グローバルブロックインデックスはハッシュ値をブロックのユニークブロックアドレス（ＳｙｎｃｈｒｕｎＩｄとｓｙｎｃｈｒｕｎ内のシーケンス数）にマッピングする。この決定により、データ位置が変わった場合またはガーベジコレクションが実行された場合でも、グローバルブロックインデックスの変換を変更する必要はなく、ブロックアドレスはそのブロックが削除されるまで有効である。
【０１８７】
別の解決策としては、ＳＣＣＩｄおよびそのＳＣＣ内のブロックのオフセットを維持する方法がある。これにより、（ＳｙｎｃｈｒｕｎＩｄ、ｓｅｑｕｅｎｃｅｎｕｍｂｅｒ）から（ＳＣＣＩｄ、Ｏｆｆｓｅｔ）への変換を行わないことでランダムな読出しの性能が改善される可能性がある。しかし、ＳＣＣ内のフラグメントのオフセット（領域再利用、連結）を変更するバックグラウンド処理の後でＧＢＩ変換を更新する必要があるため、インデックスノードに対する負荷が増大する。
【０１８８】
（非対称ネットワーク対応）
ハッシュベースの分散は、データストリームのブロックをすべてのストレージノードに均等に展開する。そのため、アクセスノードは各ストレージノードへ同じ量のデータを送信する必要がある。データストリームを書き込む帯域幅は、アクセスノードとストレージノードとの間の最も遅いネットワークリンクによって制限される。
【０１８９】
本願で提案するアーキテクチャでは、アクセスノードはスーパーノードおよびデータを保存するストレージノードの選択に関して、より自由度が高い。この特徴は非対象ネットワークにおける書込み性能の改善に役立つ。
【０１９０】
上記で説明したように、本願では、ネットワークがノード群から構成されると仮定している。１つのグループ内のノードは、二地点間のスループットが高い状態で通信を行うことができる。一方、グループ間のリンクでは１ノード当たりのスループットが低下する。
【０１９１】
アクセスノードは、自身のグループ内のストレージノード上にのみＳｔｒｅａｍｒｕｎを割り当てるようにして、書込みにグループ間のリンクを使用しない。Ｓｔｒｅａｍｒｕｎはストレージノードに直接割り当てられるのではなくスーパーノードに割り当てられるため、データＦＰＮキー領域は、データＦＰＮ内のプレフィックスの範囲が１つのグループ群に対応するように分割される。スーパーノードが、あるノード群に割り当てられると、そのコンポーネントはすべてそのグループに属するストレージノード上に保持される。
【０１９２】
Ｓｔｒｅａｍｒｕｎ割当アルゴリズムは、同じグループ内のスーパーノードのみをアクセスノードとみなすように修正される。選択されたスーパーノードがフルの場合のみ、ノード群の制約を受けない通常の割り当てが行われる。
【０１９３】
このグループ特定割当ポリシは、速度の遅いリンクを介した帯域幅集約型データ転送を排除する。グループシステムの容量を使い果たさない限り、ブロックの書込みはアクセスノードと同じグループのストレージノードによってのみ行われる。この場合でもＧＢＩクエリーはすべてのインデックスノードに均等に送信されるが、これらはそれほど帯域幅を消費しない。同様に、重複ブロックを書き込む際に変換キャッシュによって行われるＳＣＣインデックスのプリフェッチは、重複が別のグループに保存されている場合はグループ間帯域幅を使用することができる。しかし、ＳＣＣインデックスはデータのサイズに比べて小さいため、これらはグループ間スループットを超えることはない。障害後のデータ再構築も、スーパーノードのコンポーネントがすべて同じグループ内にあるため、それほど多くのグループ間帯域幅を必要としない。
【０１９４】
しかし、このポリシはいくつかのトレードオフを伴う。容量のバランス保持は１つのノード群内でのみ行われる。いくつかのクライアントが他のクライアントよりも多くのデータを書き込んだ場合、それらのグループ内のフリー領域は他のグループよりも早く使い果たされる。同じグループ内のストレージノードの障害が独立したものでなければ、システムの冗長性が損なわれることがある。その理由は、１つのスーパーノードのすべてのコンポーネントは同じノード群に含まれるからである。
【０１９５】
新たな書込みがグループ間のネットワークのトラフィックを生成することはないが、読出しの効果は重複排除パターンに依存する。例えば、あるアクセスノードが、異なるグループに接続された他のアクセスノードが既に書き込んだデータを書き込んだ場合、そのデータはオリジナルのグループにしか保存されない。２番目のアクセスノードからのデータを読み出すには、オリジナルのグループからすべてのデータを転送しなければならない。その場合、データがすべてのスーパーノードに均等に展開されている場合よりも、読出し性能が悪化する場合がある。
【０１９６】
最悪のケースでは読出しスループットが低下するが、非対称ネットワークの展開は、ネットワークのコストを最も低くすることを考慮するなら意味がある、というのが本願での主張である。その理由は、第１に、１つのネットワークグループ内のアクセスノードを介して同じクライアントのシステムが常にバックアップされる場合、そのシステムにしか存在しないユニークなデータは、そのグループに保存される可能性が高い。このデータを高いスループットで読み出すことができる。第２に、障害が発生したクライアントのシステムを復旧させる場合、通常はいくつかのバックアップ画像のみを読み出す。いくつかのストリームを同時に読み出す場合、グループ間のリンクは、データが他のノード群に保存されていたとしてもボトルネックにならないよう高速でなければならない。最後に、リモートのノード群からデータを読み出すには、同時書込みを伴うグループ間のネットワークスループットを競う必要がない。
【０１９７】
（レイテンシとマローダーに対する復元力）
本願で提案するアーキテクチャは、ハッシュベースの分散よりもブロックの書込みに対してレイテンシが増大する可能性がある。その理由は、グローバルブロックインデックスの問い合わせを行うのに余分なネットワークのホップが必要だからである。また、複数の比較的速度の遅いクライアントに対して、より高い書込みレイテンシを持つ可能性もある。順次的な書込み用の、より大きなバッファを蓄積するには、より長い時間が必要であるが、これは異なるストリームのブロックを混合しないからである。均等にハッシュベースの分散を行うシステムでは、すべてのストリームのブロックを同じ書込みバッファに蓄積して順次ディスクにフラッシュする。
【０１９８】
一方、ハッシュベースの分散システムで必要なインラインでのストリームのソートは書込みレイテンシを大幅に増加させるが、これは本システムでは必要ない。
【０１９９】
また、本願で提案するアーキテクチャはマローダー、つまり障害を宣言されない速さで機能するが他よりは動作の遅いノード、に対する復元力が高い。このアーキテクチャでは、特定のノードにアクセスするストリームのみが、そのノードの遅さまたは障害の影響を受ける。ハッシュベースの分散では、システム全体のパフォーマンスがそのネットワーク内で最も遅いノードによって決定される。
【０２００】
１つのストリームの書込み要求に対応するのは幾つかのストレージノードのみであるため、ストリーム内の未処理データの明白なフラッシュを要求してレイテンシを下げることが可能である。これは、例えば、提供されたすべてのデータが書き込まれるまでそれ以降の処理を阻止することが多い、クライアントからのＮＦＳ同期要求を処理する場合に役立つ。アクセスノードは、明白な優先順位の高いフラッシュを要求することができる。なぜなら、書き込みは、１つのストリームによって一度に１つのＳｙｎｃｈｒｕｎにしか送信されないからである。ハッシュベースの分散システムではすべてのストレージノードに対する要求を送信する必要があるため、これは実現不可能である。
【０２０１】
（Ｓｙｎｃｈｒｕｎからスーパーノードへの静的割当てｖｓ動的割当て）
本願で提示する解決策では、Ｓｙｎｃｈｒｕｎは静的にスーパーノードに割り当てられる。この割当てはＳｙｎｃｈｒｕｎのＩＤのみに基づき、ＳｙｎｃｈｒｕｎのＩＤが変更されなければ変わることはない。
【０２０２】
Ｓｙｎｃｈｒｕｎからスーパーノードへの動的なマッピングを検討することもできる。その場合は、Ｓｙｎｃｈｒｕｎのデータが保存されているストレージノードを検索しなければならず、ＳｙｎｃｈｒｕｎのＩＤによって静的に決定されることはない。このような動的マッピングの利点は、個々のスーパーノードが、システム内の変更に合わせて位置を変えられることである。例えば、非対称ネットワークでは、Ｓｙｎｃｈｒｕｎは、最も頻繁にアクセスしてくるアクセスノードの近くに移動することができる。
【０２０３】
本願では、提案するシステム内に追加のマッピングを行わないことに決定した。その理由は、追加のマッピングを行うためにはＳｙｎｃｈｒｕｎからストレージノードへの検索のために追加のネットワークホップを導入することになり、読出しレイテンシの増加につながるからである。
【０２０４】
（結論）
本願では、効果的な拡張性を持つ高性能なインライン重複排除処理のための新たなアーキテクチャを提案した。このアーキテクチャでは、正確な重複排除処理に使用するＤＨＴベースのグローバルブロックインデックスを、ストリーム認識型の順次的なデータ配置と区別している。
【０２０５】
上述したように、本願が提案するアーキテクチャは、大規模システムにおいて同時に読み出すストリームの数がシステムの規模に伴い増加する場合に、既存の解決策と比べて読出し性能が改善される。このシステムは、データの削除やノードの追加がある場合でもストリームの局所性を保存する一方、ストレージノード間の容量バランスを良好な状態に保つ。また、複数のストリームを同時に書き込む場合に、異なるストリームからのブロックをインターリーブすることがない。
【０２０６】
対称ネットワークでは、ハッシュベースの分散の方が書込みスループットはわずかに高いが、読出し性能にかなりのコストがかかる。本願が提案するアーキテクチャでは、読出し性能はアクセスパターンに大きく依存するものの、同時読出しがある場合でも非対称ネットワークにおける読出し性能が非常に高い。
【０２０７】
ハッシュベースでブロック分散を行う既存のシステムは、負荷バランスやホットスポットの問題がないため、小規模から中規模のシステムではより効果的である。しかし高いマルチストリーム読出しスループットが要求される大規模なシステムでは、本願の提案するアーキテクチャの方が適している。
【０２０８】
＜実施形態２＞
本発明の第２の実施形態を、図４乃至図１０を参照して説明する。図４は、システム全体の構成を示すブロック図である。図５は、ストレージシステムの概略を示すブロック図であり、図６は、構成を示す機能ブロック図である。図７乃至図１０は、ストレージシステムの動作を説明するための説明図である。
【０２０９】
ここで、本実施形態では、ストレージシステムがＨＹＤＲＡｓｔｏｒといったシステムであり、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、１台のコンピュータで構成されていてもよい。
【０２１０】
図４に示すように、本発明におけるストレージシステム１０は、ネットワークＮを介してバックアップ処理を制御するバックアップシステム１１に接続している。そして、バックアップシステム１１は、ネットワークＮを介して接続されたバックアップ対象装置１２に格納されているバックアップ対象データ（記憶対象データ）を取得し、ストレージシステム１０に対して記憶するよう要求する。これにより、ストレージシステム１０は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。
【０２１１】
そして、図５に示すように、本実施形態におけるストレージシステム１０は、複数のサーバコンピュータが接続された構成を採っている。具体的に、ストレージシステム１０は、ストレージシステム１０自体における記憶再生動作を制御するサーバコンピュータであるアクセスノード１０Ａ（第一サーバ）と、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード１０Ｂ（第二サーバ）と、データの格納先を表すインデックスデータを記憶するインデックスノード１０Ｃ（第三サーバ）と、を備えている。なお、アクセスノード１０Ａ、ストレージノード１０Ｂ、インデックスノード１０Ｃの数は、図５に示したものに限定されず、さらに多くの各ノード１０Ａ，１０Ｂ，１０Ｃが接続されて構成されていてもよい。
【０２１２】
さらに、本実施形態におけるストレージシステム１０は、記憶対象データを分割して、複数の記憶装置であるストレージノード１０Ｂに分散して記憶する機能を有する。また、ストレージシステム１０は、記憶対象データ（ブロックデータ）の特徴を表す固有のハッシュ値を用いて、同一内容のデータが既に記憶されているか否かを調べ、既に記憶されているデータについては、かかるデータの格納場所を参照することで重複記憶を排除する、という機能を有する。具体的な記憶処理については、後に詳述する。
【０２１３】
図６に、ストレージシステム１０の構成を示す。この図に示すように、ストレージシステム１０を構成するアクセスノード１０Ａは、記憶対象となるデータの記憶再生を制御するデータ格納制御部２１を備えている。
【０２１４】
なお、上記データ格納制御部２１は、図５に示したアクセスノード１０Ａが備えているＣＰＵ（Central Processing Unit）などの演算装置にプログラムが組み込まれることで構成されている。
【０２１５】
ここで、上記プログラムは、例えば、ＣＤ−ＲＯＭなどの記憶媒体に格納された状態でストレージシステム１０に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム１０に提供されてもよい。
【０２１６】
以下、上記データ格納制御部２１の構成について詳述する。まず、データ格納制御部２１は、バックアップ対象データＡであるストリームデータの入力を受けると、図７に示すように、当該バックアップ対象データＡを、所定容量（例えば、６４ＫＢ）のブロックデータＤに分割する。そして、このブロックデータＤのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値Ｈ（特徴データ）を算出する。例えば、ハッシュ値Ｈは、予め設定されたハッシュ関数を用いて、ブロックデータＤのデータ内容から算出する。
【０２１７】
そして、データ格納制御部２１は、新たに記憶するブロックデータＤが既にストレージノード１０Ｂつまり記憶装置に記憶されていないかといった重複判定を行う。このとき、後述するように、アクセスノード１ＡにＳＣＣインデックスＢ２が近頃読み込まれている場合には、いずれかのＳＣＣインデックスＢ２内にブロックデータＤのハッシュ値が存在するか調べる。そして、いずれのＳＣＣインデックスＢ２内にもブロックデータＤのハッシュ値が存在しない場合には、データ格納制御部２１は、さらにインデックスノード１０Ｃに記憶されているグローバルブロックインデックスＣ１内に、新たに記憶するブロックデータＤのハッシュ値が存在するか調べる。また、アクセスノード１ＡにＳＣＣインデックスＢ２が読み込まれていない場合にも、インデックスノード１０Ｃに記憶されているグローバルブロックインデックスＣ１内に、新たに記憶するブロックデータＤのハッシュ値が存在するか調べる。
【０２１８】
データ格納制御部２１は、インデックスノード１０Ｃに記憶されているグローバルブロックインデックスＣ１内に、新たに記憶するブロックデータＤのハッシュ値が存在しない場合には、ストリームデータのブロックデータを、ストレージノード１０Ｂに新規に保存する。具体的に、データ格納制御部２１にてブロックデータＤをストレージノード１０Ｂに記憶するときの様子を、図７及び図８を参照して説明する。
【０２１９】
データ格納制御部２１は、バックアップ対象データＡであるデータストリームを分割したブロックデータＤ１等を、順次、特定のストレージノード１０Ｂ内に形成されたＳＣＣファイルＢ１に格納する。このとき、使用されている記憶容量が最も少なかったり、オープンとなっているＳＣＣファイルＢ１が存在するなどのストレージノード１０Ｂを、ブロックデータＤ１等を格納する特定のストレージノード１０Ｂとする。但し、ブロックデータＤ１等を格納するストレージノード１０Ｂは、他の方法により決定してもよい。
【０２２０】
そして、データ格納制御部２１は、格納するデータストリーム内で連続する複数のブロックデータＤ１，Ｄ２，Ｄ３等を、ＳＣＣファイルＢ１内に格納する。このとき、データ格納制御部２１は、ＳＣＣファイルＢ１内における各ブロックデータＤ１，Ｄ２，Ｄ３等の格納位置を表す格納位置情報と、格納した各ブロックデータＤ１，Ｄ２，Ｄ３のハッシュ値Ｈとをそれぞれ関連付けて、ＳＣＣインデックスＢ２（格納位置特定テーブル）としてブロックデータＤ１，Ｄ２，Ｄ３を格納したストレージノード１０Ｂ内に格納しておく。また、データ格納制御部２１は、各ブロックデータＤ１，Ｄ２，Ｄ３を格納したストレージノード１０Ｂを特定する識別情報（記憶装置識別情報）であるＩＤ（例えば、特定のＳＣＣファイルＢ１内の特定領域を示すＩＤ（図８参照））と、各ブロックデータＤ１，Ｄ２，Ｄ３のハッシュ値とを関連付けて、グローバルブロックインデックスＣ１（記憶装置特定テーブル）としてインデックスノード１０Ｃに記憶しておく。なお、ここでは、ハッシュ値自体ではなく、ハッシュ値の一部とストレージノード１０Ｂを特定するＩＤとを関連付けて記憶することとする。このとき、データ格納制御部２１は、グローバルブロックインデックスＣ１を、複数存在するインデックスノード１０Ｃに分散して記憶する。なお、ハッシュ値とＩＤとを分散して記憶する方法は任意である。
【０２２１】
以上のように格納することで、バックアップ対象データＡの連続する複数のブロックデータＤ１，Ｄ２，Ｄ３等が、同一のストレージノード１０Ｂに連続して格納されると共に、それらの格納位置を示すデータも連続してＳＣＣインデックスＢ２に格納される。また、ブロックデータＤ１，Ｄ２，Ｄ３等が格納されたストレージノード１０Ｂ（特定のＳＣＣファイルＢ１内の特定領域）がグローバルブロックインデックスＣ１にて管理される。
【０２２２】
なお、上述した各ブロックデータＤ１，Ｄ２，Ｄ３等の記憶処理は、実際には、各ブロックデータＤ１，Ｄ２，Ｄ３等を、複数のストレージノード１０Ｂ群（スーパーノード）を特定のストレージノード１０Ｂとして分散して記憶することにより行う。ここで、ブロックデータをさらに分散して記憶するときの様子を、図７を参照して説明する。
【０２２３】
また、データ格納制御部２１は、上述したように新規に記憶するブロックデータＤを圧縮して、図７に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図７の符号Ｅ１〜Ｅ９に示すように、９つのフラグメントデータ（分割データ４１）に分割する。さらに、データ格納制御部２１は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ４１に追加する。例えば、図７の符号Ｅ１０〜Ｅ１２に示すように、３つのフラグメントデータ（冗長データ４２）を追加する。これにより、９つの分割データ４１と、３つの冗長データとにより構成される１２個のフラグメントデータからなるデータセット４０を生成する。
【０２２４】
そして、データ格納制御部２１は、生成されたデータセットを構成する各フラグメントデータを、スーパーノードであるストレージノード１０Ｂ群に形成された各記憶領域３１に、それぞれ分散して格納する。例えば、図７に示すように、１２個のフラグメントデータＥ１〜Ｅ１２を生成した場合には、１２個の記憶領域３１内にそれぞれ形成したデータ格納ファイルＦ１〜Ｆ１２（データ格納領域）に、各フラグメントデータＥ１〜Ｅ１２を１つずつそれぞれ格納する。
【０２２５】
次に、上述したデータストリームＡとほぼ同一のデータ内容のバックアップ対象データＡ’のデータストリームが、新たな記憶対象データとして入力された場合を図９及び図１０を参照して説明する。まず、バックアップ対象データＡ’のブロックデータＤ１が既にストレージノード１０Ｂつまり記憶装置に記憶されていないかといった重複判定を行う。このとき、アクセスノード１ＡにＳＣＣインデックスＢ２が読み込まれていないか調べ、この場合にはＳＣＣインデックスＢ２が読み込まれていないので、インデックスノード１０Ｃに記憶されているグローバルブロックインデックスＣ１内に、新たに記憶するブロックデータＤ１のハッシュ値（ここでは、ハッシュ値の一部）が存在するか調べる。
【０２２６】
そして、データ格納制御部２１は、インデックスノード１０Ｃに記憶されているグローバルブロックインデックスＣ１内に、新たに記憶するブロックデータＤ１のハッシュ値（ハッシュ値の一部）が存在する場合には、そのハッシュ値（ハッシュ値の一部）に対応付けられたストレージノード１０Ｂ（特定のＳＣＣファイルＢ１の領域）を特定し、そのストレージノード１０Ｂ内のＳＣＣインデックスＢ２を参照する。このＳＣＣインデックスＢ２内に記憶されているハッシュ値と、新たに記憶するブロックデータＤ１のハッシュ値とを比較し、一致する場合には、ＳＣＣインデックスＢ２を参照してＳＣＣファイル内Ｂ１のブロックデータの格納位置を、新たに記憶するブロックデータＤ１として参照する。これにより、新たに記憶するブロックデータＤ１自体を格納することなく、重複記憶を排除することができる。
【０２２７】
これと同時に、データ格納制御部２１は、上述したように参照したストレージノード１０Ｂに記憶されているＳＣＣインデックスＢ２を、アクセスノード１０Ａに読み出す。そして、データ格納制御部２１は、バックアップ対象データＡ’の後続のブロックデータＤ２，Ｄ３については、当該ブロックデータＤ２，Ｄ３のハッシュ値と、アクセスノード１０Ａに読み出されたＳＣＣインデックスＢ２内に記憶されているハッシュ値とを比較し、一致する場合には、ＳＣＣインデックスＢ２を参照してＳＣＣファイル内Ｂ１のブロックデータの格納位置を、新たに記憶するブロックデータＤ２，Ｄ３として参照する。これにより、新たに記憶するブロックデータＤ２，Ｄ３自体を格納することなく重複記憶を排除することができ、さらに、高速に重複判定を行うことができる。
【０２２８】
以上のように、本発明によると、複数のストレージノード１０Ｂを備え、かかるストレージノード間の容量バランスを良好に保つべく分散してデータを記憶できると共に、記憶対象データを分割した連続する所定量のブロックデータを特定のインデックスノード１０Ｂ群（スーパーノード）に局所的に保存できる。このため、重複排除処理を高速化することができる。さらに、データを読み出す処理も高速化することができる。
【０２２９】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム１００（図１１参照）、プログラムを記憶した記憶媒体、データ格納方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。
【０２３０】
（付記１）
記憶対象データを分割した複数のブロックデータを複数の記憶装置１１０に分散して記憶すると共に、記憶装置１１０に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置１１０に格納する場合に、当該記憶装置１１０に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部１０１を備え、
前記データ格納制御部１０１は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置１１０のうち特定の記憶装置１１０に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置１１０内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置１１０を識別する記憶装置識別情報と当該特定の記憶装置１１０に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
ストレージシステム１００。
【０２３１】
（付記２）
付記１に記載のストレージシステムであって、
前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、
ストレージシステム。
【０２３２】
（付記３）
付記２に記載のストレージシステムであって、
前記データ格納制御部は、前記特定の記憶装置から読み出した前記格納位置特定テーブルに基づいて、新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、
ストレージシステム。
【０２３３】
（付記４）
付記３に記載のストレージシステムであって、
前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データが前記特定の記憶装置から読み出した前記格納位置特定テーブル内に存在しない場合に、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、
ストレージシステム。
【０２３４】
（付記５）
付記１に記載のストレージシステムであって、
複数の記憶装置に対する記憶対象データの記憶動作を制御する少なくとも１つの第一サーバと、前記複数の記憶装置を構成する複数の第二サーバと、を備え、
前記データ格納制御部は、前記第二サーバから前記第一サーバに前記格納位置特定テーブルを読み出す、
ストレージシステム。
【０２３５】
（付記６）
付記５に記載のストレージシステムであって、
前記記憶装置特定テーブルを記憶する複数の第三サーバを備え、
前記データ格納制御部は、前記記憶装置特定テーブルを前記複数の第三サーバに分散して記憶する、
ストレージシステム。
【０２３６】
（付記７）
情報処理装置に、
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させると共に、
前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
ことを実現させるためのプログラムを記憶した記憶媒体。
【０２３７】
（付記８）
付記７に記載のプログラムを記憶した記憶媒体であって、
前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、
プログラムを記憶した記憶媒体。
【０２３８】
（付記９）
記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、
記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、
データ格納方法。
【０２３９】
（付記１０）
付記９に記載のデータ格納方法であって、
新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、
データ格納方法。
【図１】
0005500257.tif 000002
【図２】
0005500257.tif 000003
【図３】
0005500257.tif 000004
【図４】
0005500257.tif 000005
【図５】
0005500257.tif 000006
【図６】
0005500257.tif 000007
【図７】
0005500257.tif 000008
【図８】
0005500257.tif 000009
【図９】
0005500257.tif 000010
【図１０】
0005500257.tif 000011
【図１１】
0005500257.tif 000012