(57)【要約】【課題】レプリカを物理的に異なる形式でストレージノードに格納した場合に、レプリカ間の論理的な同一性の確認を可能とするシステム、方法、プログラムを提供する。【解決手段】結合則を満たしかつ加算に関して可換で、減算が定義可能な演算から構成される誤り検出符号を計算する計算手段（１）と、複数のデータについて計算された誤り検出符号合算する合算手段（２）と、を備え、前記ストレージにおけるデータの更新時、元の前記データのうち、更新対象の部分データに対して前記計算手段で計算した誤り検出符号又は誤り検出訂正符号と、それ以外のデータに関して既に計算されている誤り検出符号又は誤り検出訂正符号とを前記合算手段で合算し、更新後の全体のデータの誤り検出符号又は誤り検出訂正符号を求める。【選択図】図３
2013050836.tif 000002
【特許請求の範囲】
【請求項１】
データ格納部を備えたストレージと、
結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出符号を計算する計算手段と、
複数の前記誤り検出符号を合算する合算手段と、
を備え、
前記データ格納部に格納されたデータの変更時、前記計算手段は、変更対象の部分データに対して前記誤り検出符号を計算し、
前記合算手段は、前記計算手段で計算された前記部分データの前記誤り検出符号と、変更前のデータの誤り検出符号であって既に計算又は合算され前記データ格納部に格納されている誤り検出符号とを合算し、前記合算した値を、前記変更後のデータの誤り検出符号として、前記データ格納部に格納する、ことを特徴とするストレージシステム。
【請求項２】
前記データの変更は、データの追加、挿入、削除、更新を含む、ことを特徴とする請求項１記載のストレージシステム。
【請求項３】
前記誤り検出符号の計算対象のデータから、物理的な構造に依存する情報を除く正規化手段を備え、
前記計算手段は、前記誤り検出符号の計算対象のデータから前記正規化手段で物理的な構造に依存する情報が除かれた状態のデータの誤り検出符号を計算する、こと特徴とする請求項１又は２記載のストレージシステム。
【請求項４】
ストレージノードを複数備え、データを１つの前記ストレージノードに格納する場合、前記データのコピーであるレプリカを物理的に異なる形式で他の１つ又は複数の前記ストレージノードに格納するストレージシステムであって、
前記ストレージノードが、請求項１乃至３のいずれか１項に記載のストレージシステムを備えている、こと特徴とするストレージシステム。
【請求項５】
ストレージノードを複数備え、データを１つの前記ストレージノードに格納する場合、前記データのコピーであるレプリカを物理的に異なる形式で他の１つ又は複数の前記ストレージノードに格納するストレージシステムであって、
前記ストレージノードが、
データの格納時、前記データに対して誤り検出符号を計算し、データ格納部に格納する誤り検出符号付加手段と、
データ読み出し時、読み出した前記データの誤り検出符号を計算し、前記データに対応する誤り検出符号を前記データ格納部から読み出して前記計算した誤り検出符号と照合することで前記データにおける破損の有無を確認する誤り検出符号確認手段と、
を備え、前記誤り検出符号付加手段は、請求項１又は２記載の前記計算手段と前記合算手段とを少なくとも備え、
さらに、１つ又は複数の前記ストレージノードに対して、
データの構造を変換するデータ構造変換手段と、
前記ストレージノードへのデータの格納時に、前記データの誤り検出符号を付加する誤り検出符号付加手段と、
前記ストレージノードからのデータの読み出し時に、データの誤りの有無を検出する誤り検出符号確認手段と、
前記ストレージノードとの間でデータの送受信を行うデータアクセス手段と、
を備えたデータ変換装置を備え、
前記データ変換装置は、
データの書き込み時、前記ストレージノードのデータ格納部に一旦格納されたデータを、前記データ構造変換手段で前記データと論理的には同一ではあるが物理的に異なる形式に変換し、前記データの誤り検出符号とともに前記ストレージノードのデータ格納部に格納し、
データの読み出し時、前記ストレージノードの前記データ格納部から読み出したデータの誤り検出符号を確認した結果、前記誤り検出符号が一致した場合には、読み出し要求元である前記クライアントのアプリケーションに送信し、
前記誤り検出符号の確認の結果、前記誤り検出符号が不一致の場合には、前記データ構造変換手段にて、他のストレージノードに格納されるレプリカからデータ構造を変換したデータと、前記データの誤り検出符号とを、前記ストレージノードの前記データ格納部に格納した上で、前記データを前記アプリケーションに送信する、ことを特徴とするストレージシステム。
【請求項６】
前記データ格納部は、キー欄のキー値に対応した複数の欄の値の組み合わせを１行のエントリとして、複数行を備えたテーブルを備え、
前記テーブルは、行単位で書き込みが行われ、前記テーブルを行ストア（Ｒｏｗ−ｓｔｏｒｅ）形式で記憶し、
前記テーブルのデータの前記誤り検出符号は、前記テーブルを構成する各行の誤り検出符号の総和として求まり、
前記行の追加、挿入では、前記合算手段は、元のテーブルデータに関して保持されている誤り検出符号に、前記計算手段で計算した前記行の誤り検出符号を加算して、前記データ格納部に格納し、
前記行の削除では、前記合算手段は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記行の誤り検出符号を減算し、
旧行を新行で置き換える更新では、前記合算手段は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記旧行の誤り検出符号を減算し、前記計算手段で計算した前記新行の誤り検出符号を加算する、ことを特徴とする請求項４又は５記載のストレージシステム。
【請求項７】
前記誤り検出符号を、行単位、複数行の行グループ単位、テーブル全体の少なくともいずれかに対して１つ備えている、ことを特徴とする請求項６記載のストレージシステム。
【請求項８】
前記計算手段は、前記誤り検出符号の代わりに、結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出訂正符号を計算し、前記合算手段は、誤り検出訂正符号を合算する、ことを特徴とする請求項１乃至７のいずれか１項に記載のストレージシステム。
【請求項９】
結合則を満たしかつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出符号を計算する計算工程と、
複数の前記誤り検出符号を合算する合算工程と、
を含み、
データの変更時、変更対象の部分データに対して前記計算構成で誤り検出符号を計算し、
前記合算工程において、前記部分データの誤り検出符号と、変更前の全体のデータに関して既に計算され、データ格納部に格納されている誤り検出符号と、を合算し、前記合算した値を、前記更新後の全体のデータの誤り検出符号として前記データ格納部に格納する、ことを特徴とするデータ・インテグリティのチェック方法。
【請求項１０】
データ格納部を有するストレージと、
結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出符号を計算する計算手段と、
複数の誤り検出符号を合算する合算手段と、
を備え、
前記データ格納部に格納されたデータの変更時、前記計算手段が変更対象の部分データに対して誤り検出符号を計算し、
前記合算手段が、前記部分データの誤り検出符号と、変更前の全体のデータに関して既に計算され前記データ格納部に格納されている誤り検出符号と、を合算し、前記合算した値を、前記更新後の全体のデータの誤り検出符号として前記データ格納部に格納するコンピュータに、前記計算手段と前記合算手段の処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステム技術に関し、特にデータ・インテグリティのチェックに好適な構成、方法、プログラムに関する。
【背景技術】
【０００２】
データ・インテグリティ（データ完全性：データに誤りや欠けがないこと）のチェックの一例として例えば非特許文献１が参照される。図１に、非特許文献１に開示されたＨＤＦＳ（Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）のアーキテクチャを示す（図１は非特許文献１から引用した図である）。図１に示すように、この分散ファイルシステムは、ファイルシステムのネームスペースの管理及びクライアントからのファイルアクセスの調整等を行うマスタサーバをなす一つのネームノード（Ｎａｍｅｎｏｄｅ）と、ディスク等のローカルストレージを備えファイルの断片（ブロック）を格納する複数のデータノード（Ｄａｔａｎｏｄｅ）から構成される。ネームノードは、ファイルシステムのネームスペースの操作（オープン、クローズ、ファイル、ディレクトリのリネーム等）、データノードへのブロックのマッピング等を行う。データノードは、ファイルシステムのクライアントからのライト・リード要求に対する処理を行い、またネームノードからの指示に基づき、ブロック生成、削除、複製（Ｒｅｐｌｉｃａｔｉｏｎ）を行う。
【０００３】
ＨＤＦＳでは、ファイルを格納する際に、該ファイルを固定サイズ（サイズは、ファイル毎に設定可能である）のブロック（ｂｌｏｃｋ）に分割し（ファイルの最後のブロックは他のブロックより当然小さくなる）、ファイルのブロックは耐障害性（ｆａｕｌｔ  ｔｏｌｅｒａｎｃｅ）のために複製される。複製は、物理的に異なるデータノードに格納される。アプリケーションはファイルのレプリカ数を指定可能である。
【０００４】
また、ブロック毎にチェックサム（ｃｈｅｃｋｓｕｍ）等の誤り検出符号（ｅｒｒｏｒ  ｄｅｔｅｃｔｉｏｎ  ｃｏｄｅ）が作成され、当該ブロックとは別の領域に保存される。クライアントによるファイルアクセスの際には、ファイルを構成するブロックと、当該ブロックに対応する誤り検出符号をデータノード（チェックサムファイル）より取得し、当該ブロックの誤り検出符号を再度計算し、取得した誤り検出符号とが一致するか比較することで、データ・インテグリティのチェックを行う。この際、ブロックの破損が検出されている場合には、クライアントは、例えば他のデータノードから該当ブロックを再取得し、ネームノードは、破損分のレプリカの再作成を行う。
【０００５】
可用性（ａｖａｉｌａｂｉｌｉｔｙ：システムが連続して動作できる能力）やアクセス性能の向上のため、ファイル又はブロックのレプリカを作成する方式の分散ストレージシステムでは、一般に、データのレプリカは物理的に同一形式で作成し、ファイル又はブロック毎の誤り検出符号を別途保持しておき、データのアクセス時に、あるいは定期的に等、必要なタイミングで、レプリカデータのインテグリティのチェックを行い、レプリカの完全性の確認を行う。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】HDFS Architecture Guide, [online] [平成23年6月24日検索]  インターネット＜URL:http://hadoop.apache.org/hdfs/docs/current/hdfs_design.html#Data+Replication＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本願出願時点で、本発明の共同発明者による先願（特願２０１１−０５０１５１号:本願出願時未公開）を除いて、レプリカを物理的に異なる形式で作成する構成とした分散ストレージシステムは提案されていず、当然ながら、そのようなシステム向けのデータ・インテグリティのチェック方法も、本願出願時には存在しない。
【０００８】
したがって、本発明の目的は、論理的に同一内容のデータをレプリカ間で物理的に異なる形式でストレージに格納した場合でも、レプリカ間の論理的な同一性の確認を可能とするシステム、方法、プログラムを提供することにある。
【０００９】
本発明の他の目的は、データの更新、追加、削除時において誤り検出符号の再計算の演算量の縮減を可能とするシステム、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明によれば、データを格納するデータ格納部と、結合則を満たしかつ加算に関して可換で、減算が定義可能な演算から構成される誤り検出符号を計算する計算手段と、複数のデータについて計算された誤り検出符号を合算する合算手段と、を備え、前記ストレージにおけるデータの更新時、元の前記データのうち、更新対象の部分データに対して前記計算手段で計算した誤り検出符号と、それ以外のデータに関して既に計算されている誤り検出符号とを前記合算手段で合算し、前記合算した値を、前記更新後の全体のデータの誤り検出符号とするストレージシステムが提供される。
【発明の効果】
【００１１】
本発明によれば、論理的に同一内容のデータをレプリカ間で物理的に異なる形式でストレージに格納した場合でもレプリカ間の論理的な同一性の確認を可能としている。またデータの更新、追加、削除時において、誤り検出符号の再計算の演算量の縮減を可能としている。
【図面の簡単な説明】
【００１２】
【図１】非特許文献１に開示されたＨＤＦＳ  Ａｒｃｈｉｔｅｃｔｕｒｅの図である。
【図２】キー・バリュー・ストア（Ｋｅｙ−Ｖａｌｕｅ  Ｓｔｏｒｅ）型テーブル・データの格納形式を説明する図である。
【図３】本発明の第１の実施形態の構成を示す図である。
【図４】本発明の第１の実施形態の動作を説明する流れ図である。
【図５】本発明の第２の実施形態の構成を示す図である。
【図６】本発明の第２の実施形態の動作を説明する流れ図である。
【図７】本発明の第３の実施形態の構成を示す図である。
【図８】Ｒｏｗ−ｓｔｏｒｅ  Ｃｏｌｕｍｎ−ｓｔｏｒｅとテーブルの誤り検出符号の関係を説明する図である。
【図９】データ・インテグリティチェックの階層型管理形態を説明する図である。
【発明を実施するための形態】
【００１３】
まず、本発明の原理を説明し、つづいて、実施形態について説明する。本発明によれば、論理的には同一の内容であるデータのレプリカを、例えばレプリカ間で物理的に異なる形式で保持するストレージ・システムにおいて、データ・インテグリティのチェックに好適な手法が提供される。本発明によれば、可用性の向上やアクセス帯域の向上（例えば複数のノードからデータの読み出しを可能とすること）を目的として複数のレプリカを保持する分散ストレージシステムにおいて、データを利用するアプリケーション（アプリケーションソフトウェア（プログラム））のアクセス特性等に応じて、物理的に互いに異なる形式で保持するレプリカに対してレプリカ間の論理的な同一性の確認を可能とする手法が提供される。
【００１４】
以下では、論理的に同一内容のデータのレプリカとして、物理的に互いに異なる形式のレプリカを少なくとも二つ作成する分散ストレージシステムの一例として、キー・バリュー・ストア（Ｋｅｙ−Ｖａｌｕｅ  Ｓｔｏｒｅ：ＫＶＳ）のテーブル形式で、データを格納するストレージ・システムへ、本発明を適用した場合について説明する。キー・バリュー・ストアは、キー（Ｋｅｙ）とデータ（ｖａｌｕｅ：値）をセットとして書き込み、キーを指定して値を読み出す構成のデータベースである。
【００１５】
特に制限されないが、分散ストレージシステムの上位で動作するアプリケーション（例えばストレージサーバに対するクライアント上で動作する）として、大量の事象を分散ストレージに追記し、非同期にその事象を統計的に分析するアプリケーションを想定する。この場合、ストレージに対する書き込みは、事象単位（例えば、ある顧客のステータス情報（位置、時刻、イベント内容（例えば、店を利用した、コマーシャル（ＣＭ）を見た、購入した、クーポン使った等））、すなわち、書き込みトランザクションは、レコード（１行）単位で行われる。
【００１６】
これに対して、例えば統計的な分析（例えば、ある店舗を利用した人数等）は、複数又は全体の事象の特定の項目、すなわち、すなわち複数又は全てのレコードの中の特定のフィールド（列）へのアクセスとなる。このようなアプリケーションを含むシステムにおいて、データノード（ストレージノード）では、テーブルデータを、行（Ｒｏｗ）方向でメモリあるいはストレージ上に保存しているものとする（図２のＲｏｗ−ｓｔｏｒｅ）。なお、図２には、テーブルのデータ保持構造の例として、Ｒｏｗ−ｓｔｏｒｅ型、及び、Ｃｏｌｕｍｎ  Ｓｔｏｒｅ型が模式的に示されている。図２の（Ａ）のテーブルは、Ｋｅｙカラムと、３つのＶａｌｕｅカラムを備え、各行（各レコード）は、Ｋｅｙと３つのＶａｌｕｅのセットからなる。
【００１７】
テーブルへの書き込みに関しては、行（Ｒｏｗ）単位での連続アクセスとなる。すなわち、Ｋｅｙと、該Ｋｅｙに対応する３つの値フィールドｖａｌｕｅ１、ｖａｌｕｅ２、ｖａｌｕｅ３を１行とし、順次、書き込みが行われる。
【００１８】
分析用のアプリケーションによる読み出しに関しては、列（Ｃｏｌｕｍｎ）単位、すなわち、複数行に渡るストライドアクセスとなる。このため、Ｒｏｗ−ｓｔｏｒｅ型のストーレッジの場合、アクセス効率が悪くなる。例えば、図２のテーブルにおいて、ある特定の列（例えば図２（Ａ）のテーブルのフィールド“Ｖａｌｕｅ１”の列）のデータを分析するために、複数行に亘ってデータを処理する場合、Ｒｏｗ−Ｓｔｏｒｅ型（図２（Ｃ）参照）では、各行単位で読み出しを行い、読み出した行の中から該当列（例えばフィールドＶａｌｕｅ１）のデータを抽出する処理を、複数行に亘って行う必要がある。このため、大量のデータの分析においてスループットの低下、処理時間が増大する。
【００１９】
これに対して、Ｃｏｌｕｍｎ−Ｓｔｏｒｅ型（図２（Ｂ））の場合、列単位での読み出しが行われることになり、例えばフィールド“Ｖａｌｕｅ１”の列単位での値の読み出しが行われる。このため、Ｒｏｗ−Ｓｔｏｒｅ型と比べて、アクセス効率は格段に向上する。なお、図２（Ｄ）の行形式分割（Ｒｏｗ−Ｓｔｏｒｅ）は、行形式で、テーブルデータを分割して分散配置するものである。分散ＫＶＳ方式の場合、例えばテーブルの識別子とレプリカの識別子等をキー（Ｋｅｙ）情報として、コンシステント・ハッシング方式により、当該データの配置ノードが特定されるが、本発明の主題と直接関係しないため、説明は省略する。
【００２０】
データの書き込みから、分析用のデータの読み出しまでの非同期性を利用して、データの書き込み後、事前（読み出しが行われる前）に読み出しのためにデータを列方向で保持する変換処理を施しておく（例えばＣｏｌｕｍｎ−ｓｔｏｒｅ形式のデータ構造に変換しておく）ことで、分析用のアプリケーションによる列単位での読み出しにおいて、アクセス性能の向上が期待できる。
【００２１】
ストレージにおけるデータ生成時（書き込み時）と、データ利用時（読み出し時）、さらに、データ利用時における用途に応じて、データがアクセスされる領域、及び、アクセスパターン(例えばデータをアクセスするコマンドの種別、及びその時系列パターン等)は異なることが一般的である。そのような状況において、ストレージの容量、データ構造変換のオーバーヘッド等が許容できる場合には、用途に応じたデータ構造に、事前に変換した上でストレージに格納しておくことで、当該用途に対応したアプリケーションによるデータ読み出しにおけるアクセス性能の向上が期待できる。
【００２２】
分散ストレージシステムでは、前述したように、可用性やアクセス帯域の向上を目的として、データの複製（レプリカ）を１つ以上のデータノードで保持する。レプリカを、用途に応じてオリジナルデータとは異なる形式のデータ構造で保持しておくことで、ストレージ容量のデメリットを解消することができる。すなわち、複製先のデータノードでオリジナルデータと同一のデータ構造のレプリカとともに、アプリケーション用途向けのデータ構造に事前に変換したデータも保持する構成とした場合、必要なストレージ容量が増大する。一方、複製先のデータノードにおいて、レプリカとして、アプリケーションの用途向けの形式（データ構造）に変換したデータのみ保持することで、ストレージ容量の増大という問題は回避される。
【００２３】
なお、前記した先願（特願２０１１−０５０１５１）には、分散ストレージシステムにおいて、耐障害性やアクセス性能向上のためにレプリカに関して、物理的に同一形式でレプリカを作成するのではなく、論理的には同一であるが、アプリケーションの用途、アクセス特性等に応じて、物理的に異なる形式（例えばローストア型（Ｒｏｗ  Ｓｔｏｒｅ）、カラムストア型（Ｃｏｌｕｍｎ  Ｓｔｏｒｅ））でレプリカを保持する構成が提案されている。
【００２４】
しかしながら、アプリケーションのアクセス特性等に応じて例えばレプリカ毎に物理的に異なる形式でそれぞれに対応するデータノード（ストレージノード）に格納した場合に、レプリカ間で論理的な同一性を確認することができない。例えば非特許文献１において、レプリカ間のデータ・インテグリティのチェックは、物理的な保存形式であるブロック等のデータの保存単位で行っている。したがって、論理的には同一であるが、物理的な形式としては異なるという状況下でのデータ・インテグリティのチェックは、非特許文献１等には想定されていない。
【００２５】
本発明の好ましい形態の１つによれば、結合則を満たし、且つ加算に関して可換であり、減算が定義可能な演算で誤り検出（訂正）符号（ｅｒｒｏｒ  ｄｅｔｅｃｔｉｏｎ  （ａｎｄ  ｃｏｒｒｅｃｔｉｏｎ）  ｃｏｄｅ）を計算する計算手段（１）と、誤り検出（訂正）符号を合算する合算手段（２）と、を備えている。計算手段（１）は、例えばアプリケーションからのデータアクセス単位でデータの誤り検出（訂正）符号を計算する。
【００２６】
合算手段（２）は、データの追加、削除等、データの変更時に、変更前の元のデータの誤り検出（訂正）符号と、変更されたデータ（部分データ）の誤り検出（訂正）符号と、を合算し、この合算値を、変更後の全体のデータの誤り検出（訂正）符号の値とする。
【００２７】
本発明の好ましい形態の１つによれば、変更データの誤り検出（訂正）符号の計算の前に、対象データの正規化を行うようにしてもよい。
【００２８】
本発明の好ましい形態によれば、アプリケーションのアクセス特性に応じてレプリカ毎に、物理的に異なる形式でデータノードに格納した場合にも、レプリカ間の論理的な同一性を確認することができる。
【００２９】
本発明の好ましい形態の１つによれば、誤り検出（訂正）符号の計算をアプリケーションのデータアクセス単位で行い、部分データの誤り検出（訂正）符号からデータ全体の誤り検出（訂正）符号の合算として加減算のみを用いている。
【００３０】
このため、データの更新、追加、削除の時にも、データの誤り検出符号の再計算は、多数のデータや全体に波及することなく、局所的な部分データの再計算で対応できる（計算負荷の増大を抑制する）。
【００３１】
なお、チェックサム等の誤り検出符号の代わりに、誤り訂正（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ）を行ってもよい（ＥＣＣ（Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  Ｃｏｄｉｎｇ）符号を用いる）。このため、上記のとおり、「誤り検出（訂正）符号」（ｅｒｒｏｒ  ｄｅｔｅｃｔｉｏｎ  （ａｎｄ  ｃｏｒｒｅｃｔｉｏｎ）  ｃｏｄｅ）と表記している。誤り検出符号では、誤りの位置は検出できないが、訂正符号を用いた場合、ある範囲のエラーなら、その場で修正することが可能となる。
【００３２】
＜実施形態１＞
次に、本発明の実施形態について説明する。図３は、本発明に係るストレージシステムの第１の実施の形態の構成を示す図である。図３を参照すると、第１の実施の形態は、
変更データを入力し、ストレージ３に対して、更新データを反映させる変更データ入力手段４と、
データの誤り検出符号を計算する誤り検出符号計算手段１と、
複数の誤り検出符号の合算を行う誤り検出符号合算手段２と、
データと該データに対応する誤り検出符号とを格納するストレージ３と、
を含む。
【００３３】
誤り検出符号計算手段１は、以下に示すように、結合則を満たし、且つ、加算に関して可換であり、減算が定義可能であるという演算にしたがって計算される誤り検出符号を計算する。
【００３４】
結合則：ａ・（ｂ・ｃ）＝（ａ・ｂ）・ｃ
可換：  ａ・ｂ＝ｂ・ａ
【００３５】
例えばデータＡ、Ｂ、Ｃの誤り検出符号をそれぞれａ、ｂ、ｃとする。誤り検出符号が結合則を満たすことから、データＡに、データＢとデータＣを加えたデータを加える操作を行って得られるデータの誤り検出符号は、ａ＋（ｂ＋ｃ）で与えられるが、これは、データＡにデータＢを加えたデータに、データＣを加えた場合の誤り検出符号（ａ＋ｂ）＋ｃに等しいことを意味する。また加算に関して可換は、例えばデータＡにデータＢを加えたデータの誤り検出符号ａ＋ｂは、データＢにデータＡを加えたデータの誤り検出符号ｂ＋ａと等しい。また、減算が定義可能であることから、データＡにからデータＢを削除したデータの誤り検出符号はａ−ｂで与えられる。
【００３６】
結合則を満たし、且つ、加算に関して可換で減算が定義可能な演算から計算される誤り検出符号として、例えばチェックサムやパリティ符号等が用いられる。よく知られれているように、チェックサムは、データブロックのワード列の個々のワードの総和の例えば下位１ワードをそのまま符号値とする。パリティ符号は、例えばワード単位に１ビットを付加し、パリティビットを含め１の数を例えば偶数個（又は奇数個）とし、１の数が奇数個（偶数個）のものは誤りとして検出される。
【００３７】
誤り検出符号合算手段２は、データの変更（例えば、追加／挿入、削除、更新等）に対して、誤り検出符号計算手段１で計算された誤り検出符号に対して、変更前の元のデータの誤り検出符号（既に計算済み）との合算（加減算）を行い、元のデータに当該データの変更を反映した全体のデータの誤り検出符号を算出する。誤り検出符号合算手段２において、変更対象のデータの誤り検出符号と計算済みの元のデータの誤り検出符号の合算（加減算）で全体のデータの誤り検出符号が算出可能であるのは、結合則を満たし、且つ、加算に関して可換で、減算が定義可能な誤り検出符号固有の性質による。
【００３８】
図４は、図３の第１の実施の形態の全体の動作を説明する流れ図である。図３及び図４を参照して、第１の実施の形態の全体の動作について詳細に説明する。
【００３９】
データの管理単位（例えばテーブル等）に対して、変更データ入力手段４は、部分データ（例えば行等）の変更（追加、挿入、削除、更新等）を行う。
【００４０】
誤り検出符号計算手段１は、変更データ入力手段４から変更対象データを受け取り、当該変更対象データの誤り検出符号を、結合則を満たし、且つ、加算に関して可換で減算が定義可能な演算から構成される誤り検出符号で計算する（ステップＳ１１）。
【００４１】
誤り検出符号合算手段２は、ストレージ３からデータの管理単位全体の誤り検出符号を読み出す（ステップＳ１２）。
【００４２】
誤り検出符号合算手段２は、前記読み出したデータの管理単位全体の誤り検出符号と、部分データ（例えば行等）の誤り検出符号の合算（変更の内容に応じて、加減算等の組み合わせ）を行う（ステップＳ１３）。
【００４３】
誤り検出符号合算手段２は、誤り検出符号の合算結果を、変更後のデータの管理単位全体の誤り検出符号としてストレージ３に格納する（ステップＳ１４）。
【００４４】
変更データ入力手段４は、ストレージ３においてデータの管理単位に対して、部分データの変更を適用する（ステップＳ１５）。なお、ステップＳ１４、Ｓ１５は、一貫性の都合上、アトミックに処理する必要がある。
【００４５】
第１の実施の形態の作用効果について説明する。
【００４６】
第１の実施の形態では、結合則を満たし、且つ、加算に関して可換であり、減算が定義可能な演算で導出される誤り検出符号を利用し、データの更新単位の誤り検出符号と、更新単位以外の元のデータの管理単位全体の誤り検出符号との合算を、新たなデータの管理単位全体の誤り検出符号としている。この結果、アプリケーションの用途、特性等に対応させて互いに物理的に異なる形式の複数のレプリカを複数のストレージにそれぞれ格納した場合でも、これら複数のレプリカ間の論理的な同一性を確認することができる。すなわち、レプリカ間で、データの管理単位全体の誤り検出符号が一致すれば、これらレプリカ間でデータのインテグリティが保たれており、逆に、相違すれば、レプリカ間でデータのインテグリティは保証されない。
【００４７】
第１の実施形態によれば、データを部分的に変更する場合に、誤り検出符号の再計算が多数のデータや全体に波及せずに、変更対象の部分の局所的な誤り検出符号の再計算で済ませることができる。データ全体の誤り検出符号は合算で求めることができ、計算量を特段に低減している。
【００４８】
＜実施形態２＞
次に、本発明の第２の実施形態を説明する。図５は、第２の実施形態の構成を示す図である。図６は、第２の実施形態の動作を説明する流れ図である。図５、図６において、図３、図４と同一の要素、ステップには、同一も参照符号が付されている。以下では、前記第１の実施形態との相違にについて説明し、同一部分の説明は省略する。第２の実施形態は、前記第１の実施形態の構成において、変更データ入力手段４と誤り検出符号計算手段１の間に、変更データ正規化手段５が追加されている。
【００４９】
変更データ正規化手段５は、変更対象データの誤り検出符号の計算の前に、対象データの正規化を行う（図６のステップＳ１０）。ここで、データの正規化とは、データの形式を指示するメタデータ等を除く。
【００５０】
本実施の形態では、レプリカの物理的な構造に依存する情報（データの形式を指示するメタデータ等）を予め除外した上で、誤り検出符号の計算を行う。このため、適用可能なデータ構造、アプリケーション等が広がる。
【００５１】
なお、結合則を満たし、且つ加算に関して可換で、減算が定義可能な演算から構成される誤り検出符号の計算の具体的な例として、チェックサムや、パリティ計算等が挙げられる。
【００５２】
＜実施形態３＞
以下、発明の理解を助けるために、アプリケーションのアクセス特性に応じてレプリカ毎に物理的に異なる形式で保持するタイプの分散ストレージシステムに本発明を適用した場合の概要を第３の実施形態として説明する。
【００５３】
特に制限されないが、第３の実施の形態では、データ格納時に、レプリカを、オリジナルデータと物理的に同一の型式で一旦作成し、非同期に、データ構造の変換を行い、レプリカ作成時と異なる形式に変換する。非同期に別のデータ構造に変換する制御形態としては、例えばオリジナルデータと物理的に同一の型式のレプリカ格納のタイミングから所定の期間経過（タイムアウト発生）、あるいは、システム管理者のコマンド入力等のトリガー条件を格納しておき、当該トリガー発生時に、データ構造の変換を行うようにしてもよい。
【００５４】
図７に示すように、第３の実施の形態は、クライアント１０と、データ変換装置２０、ストレージノード（データノード）３０を含む。図７では、簡単のため、クライアント１０と、データ変換装置２０、ストレージノード（データノード）３０について、各１個が図示されているが、ストレージノード（データノード）３０は複数備えており、クライアント１０も１つ又は複数存在する。なお、データ変換装置２０は、複数のストレージノード３０、複数のクライアント１０に対して１つ備えた構成とされる。
【００５５】
ストレージノード３０は、データを格納するデータ格納部３４と、クライアント１０又はデータ変換装置２０からのデータアクセスリクエストを受け、データ格納部３４に適切なサイズ（ブロック）で入出力を行うブロックアクセス手段３１と、データ格納部３４へのデータの格納時に誤り検出符号を付加する誤り検出符号付加手段３２と、データ格納部３４からのデータ読み出し時にデータの誤りの有無を検出する誤り検出符号確認手段３３とを含む。
【００５６】
クライアント１０は、コンピュータ上で動作するアプリケーション１１（アプリケーションプログラム）と、ストレージノード３０へのアクセスインタフェース（Ｉ／Ｆ）を提供するストレージアクセスインタフェース（Ｉ／Ｆ）１２、ストレージノード３０との間でデータの送受信を行うデータアクセス手段１３を含む。
【００５７】
データ変換装置２０は、データの構造を変換するデータ構造変換手段２１と、ストレージノード３０へのアクセスインタフェース（Ｉ／Ｆ）を提供するストレージアクセスインタフェース（Ｉ／Ｆ）２２と、データの格納時に当該データの誤り検出符号を付加する誤り検出符号付加手段２３と、データの読み出し時に、データの誤りの有無を検出する誤り検出符号確認手段２４、ストレージノード３０との間でデータの送受信を行うデータアクセス手段２５を含む。
【００５８】
これらの手段は、それぞれつぎのように動作する。なお、特に制限されないが、以下では、キー・バリュー型ストア（Ｋｅｙ−Ｖａｌｕｅ  Ｓｔｏｒｅ：ＫＶＳ）での動作を想定する。すなわち、キー（アクセスキー）とデータ（Ｖａｌｕｅ）がセットとしてテーブル（データベース）に格納される。
【００５９】
＜クライアントからのリード＞
クライアント１０上で動作するアプリケーション１１がストレージノード３０に格納されているデータを読み出す場合、ストレージアクセスＩ／Ｆ１２を用いて、該当データの物理的な格納形式と、データのアクセス・キーとそのアクセスの特性を示す識別子等に基づき、該当データの該当格納形式のレプリカが格納されているストレージノードを特定する。なお、該当データを保持するストレージノード（データノード）の特定方法は、データとストレージノードの対応関係を、サーバ（不図示）で保持するメタサーバ方式と、データのアクセス・キーに基づいて、コンシステントハッシング等の計算によって、ストレージノードを求める方式等がある。コンシステントハッシングでは、ハッシュ関数にデータのアクセス・キーを入力し、ハッシュ関数の出力から、当該データを格納しているストレージノードの位置情報を得る。
【００６０】
クライアント１０は、ストレージノード３０に対してデータアクセスのリクエストを発行する。
【００６１】
クライアント１０からデータアクセスリクエストを受信したストレージノード３０のブロックアクセス手段３１は、該当データをデータ格納部３４から読み出し、誤り検出符号確認手段３３にて、当該データの誤り検出符号を計算する。また、当該データの格納時等に事前に計算しておいた当該データに対応する誤り検出符号を、データ格納部３４から読み出し、新たに計算した誤り検出符号と照合する（一致／不一致をチェックする）ことで、該当データにおける破損等の有無を確認する。
【００６２】
ストレージノード３０の誤り検出符号確認手段３３による誤り検出符号の確認の結果、該当データに破損が無い場合には（データ格納部３４から読み出した当該データの誤り検出符号と、新たに計算した誤り検出符号とが一致した場合）、ブロックデータアクセス手段３１は、当該読み出しデータを、クライアント１０のデータアクセス手段１３を介してアプリケーション１１に送信する。
【００６３】
ストレージノード３０の誤り検出符号確認手段３３による誤り検出符号確認の結果、該当データに破損が見つかった場合には（データ格納部３４から読み出した当該データの誤り検出符号と、新たに計算した誤り検出符号とが不一致の場合）、データ変換装置２０のデータアクセス手段２５は、別のデータ構造で保存されている別のストレージノードのデータ格納部３４に格納されているレプリカから、データを復元し、ストレージノード３０のデータ格納部３４に再度格納した上で、該当データを、クライアント１０のデータアクセス手段１３を介してアプリケーション１１に送信する。
【００６４】
＜クライアントからのライト＞
クライアント１０上で動作するアプリケーション１１がストレージノードにデータを格納する場合、クライアント１０のストレージアクセスＩ／Ｆ１２を用いて該当データを格納するストレージノード３０を複数決定する。クライアント１０のデータアクセス手段１３は、決定した複数のストレージノード群に対して、データ格納リクエスト（書き込み要求）を発行する。
【００６５】
クライアント１０からのデータ格納リクエストを受信したストレージノード群の各ノードのデータアクセス手段３１は、書き込みデータを受け取り、当該書き込みデータに対して誤り検出符号付加手段３２を用いて、誤り検出符号を計算し、当該書き込みデータと誤り検出符号とを合わせてデータ格納部３４に格納する。これによって、複数のストレージノードにデータの複製（レプリカ）がそれぞれ格納される。
【００６６】
クライアント１０による書き込み対象のオリジナルデータとレプリカを合わせて３つの同一内容のデータ（レプリカＡ、Ｂ、Ｃとする）があった場合、レプリカＡはオリジナルデータそのままとし（データ構造の変換無し）、レプリカＢはデータ変換装置２０により形式１、レプリカＣは、データ変換装置２０により形式２に変換する。
【００６７】
データ変換装置２０は、クライアント１０によるストレージノード３０のデータ格納部３４へのデータ格納とは、非同期に、ストレージノード３０に格納されたデータを、論理的には同一ではあるが、物理的に異なる形式１、２に変換し、再度、複製先のストレージノード３０にそれぞれ格納する。具体的には、データ構造変換手段２１は、図示されない制御手段からの指示、あるいは予め定められたイベント発生（タイムアウト発生）等を契機として、データアクセス手段２５を用いて、ストレージノード３０から、指示されたデータを読み出し、指示されたデータ構造にデータ構造変換手段２１において変換し、変換したデータ構造を、データアクセス手段２５から、ストレージノード３０に格納する。クライアント１０からのライトの場合と異なり、データ変換装置２０では、この格納データに対するレプリカは作成しない（レプリカデータのレプリカは作成しない）。すなわち、変換後のレプリカのデータ構造が例えば形式１の場合、物理的に異なる形式２のレプリカも作成されるためである。なお、データ構造を変換する前のレプリカの１つ（オリジナルデータそのままのレプリカＡ）は必要に応じて削除してもよい。
【００６８】
なお、クライアント１０のアプリケーション１１からのオリジナルデータの変更（更新）要求に対応して、複数のストレージノード３０の各々において、ブロックアクセス手段３１はデータ格納部３４に格納されているレプリカデータの変更（更新）を行う。その際、複数のストレージノード３０の各々の誤り検出符号付加手段３２は、前記第１、第２の実施形態と同様、変更データの誤り検出符号を計算し、元のデータの誤り検出符号と合算することで、変更後のレプリカデータの誤り検出符号を導出し、データ格納部３４に格納する。
【００６９】
なお、データ変換装置２０において、データ構造の変換内容によっては、ストレージノード３０から読み出した複数のデータから新たに複数のデータを書き出す場合もある。その際に、誤り検出符号の確認と付加を行う必要があり、その方法に関して以下に説明する。図２に示したように、複数の列と行からなるＫＶＳ（キー・バリュー型データストア）テーブルのデータに関して、データの追加時に、行単位でデータが追加、あるいは更新され、アプリケーションによる分析時に、特定の列に関してまとめてアクセスがあるような事例を説明する。この時、書き込みデータに関しては、Ｒｏｗ−ｓｔｏｒｅ形式、読み出しに関してはＣｏｌｕｍｎ−ｓｔｏｒｅ形式が適しているため、ストレージノード３０のデータ格納部３４にＲｏｗ−ｓｔｏｒｅ形式で書きこまれたデータを、データ変換装置２０が、Ｃｏｌｕｍｎ−ｓｔｏｒｅ形式に変換する。
【００７０】
データのアクセス単位は、アプリケーションの特性上、Ｒｏｗ−ｓｔｏｒｅ形式では行単位、Ｃｏｌｕｍｎ−ｓｔｏｒｅ形式では列単位とする。
【００７１】
Ｒｏｗ−ｓｔｏｒｅ形式、Ｃｏｌｕｍｎ−ｓｔｏｒｅ形式の両形式の論理的な同一性を確認するためには、それぞれの形式のデータ全体として、同一の値を持つような、誤り検出（訂正）符号の計算が必要である。
【００７２】
また、データの追加・更新は、テーブル単位ではなく、行単位（Ｒｏｗ−ｓｔｏｒｅ形式）や列単位（Ｃｏｌｕｍｎ−ｓｔｏｒｅ形式）で行われる。このため、行又は列単位でのデータ変更があった場合に、テーブル全体の再計算を必要としない誤り検出（訂正）符号の計算が必要となる。
【００７３】
本実施形態によれば、上記のような要請に対して、「結合則を満たし且つ加算に関して可換で、減算が定義可能な演算から構成される誤り検出符号の計算」を利用し、データの追加／挿入、削除、更新に関して以下に説明するように、誤り検出符号のアルゴリズムを定義する。
【００７４】
図８は、図２のＫｅｙ−Ｖａｌｕｅ方式のテーブルデータのインテグリティ・チェックの原理を説明する図である。
【００７５】
Ｒｏｗ−Ｓｔｏｒｅ形式のテーブルデータ全体の誤り検出符号（チェックサム）ｔａｂ＿ｃｈｋｓｍ＿ｒｏｗは、ｎ列の各行の誤り検出符号ｒｏｗ＿ｃｈｋｓｍ［ｉ］の総和で与えられる。
【００７６】
tab_chksm_row＝Σ_(i=1)^n row_chksm[i]            ・・・(1)
【００７７】
なお、総和記号
2013050836.tif 000003
を本明細書では、Σ_(i=1)^nとテキスト表記で表し、_(ｉ=1）は、総和記号Σの右下の添え字ｉの下限が１であることを表し、＾nは、総和記号Σの添え字ｉの上限がｎであることを表している。
【００７８】
Ｃｏｌｕｍｎ−Ｓｔｏｒｅ形式のテーブル全体の誤り検出符号（チェックサム）ｔａｂ＿ｃｈｋｓｍ＿ｃｏｌは、ｍ列の各々の誤り検出符号ｃｏｌ＿ｃｈｋｓｍ［ｊ］の総和で与えられる。
【００７９】
tab_chksm_co ＝ Σ_(ｊ=1)^m col_chksm[j]            ・・・(2)
【００８０】
図８では、第１列がＫｅｙ、第２、第３、第４列がＶａｌｕｅ１、Ｖａｌｕｅ２、Ｖａｌｕｅ３である（同様に、第ｍ列はＶａｌｕｅｍ）。テーブル全体の誤り検出符号（チェックサム）ｔａｂ＿ｃｈｋｓｍは、第１列のＫｅｙの誤り検出符号（チェックサム）ｋ＿ｃｈｋｓｍ（第１列のｎ個（行）のＫｅｙのチェックサムからなる）と、残りのｊ＝２〜ｍの（ｍ−１）列のＶａｌｕｅの誤り検出符号（チェックサム）ｖ＿ｃｈｋｓｍ（各列、ｎ個のＶａｌｕｅからなる）の総和で与えられる。
【００８１】
tab_chksm ＝ Σ_(i=1)^1 (Σ_(j=1)^n k_chksm[j]) + Σ_(i=2)^n (Σ_(j=1)^m v_chksm[i,j])              ・・・(3)
【００８２】
Ｒｏｗ＿ｓｔｏｒｅ形式でのテーブルデータ全体の誤り検出符号ｔａｂ＿ｃｈｋｓｍ＿ｒｏｗ、Ｃｏｌｕｍｎ−Ｓｔｏｒｅ形式の形式でのテーブルデータ全体の誤り検出符号ｔａｂ＿ｃｈｋｓｍ＿ｃｏｌが等しければ、これらのデータのインテグリティは保たれていることが分かる。すなわち、同一のデータの誤り検出符号（チェックサム）に関して次式（４）が成り立つ。
【００８３】
tab_chksm_row = tab_chksm_col ＝ tab_chksm            ・・・(4)
【００８４】
Ｋｅｙ−Ｖａｌｕｅ方式のテーブルデータについて、Ｒｏｗ＿ｓｔｏｒｅ形式に変換されたデータ構造から求めた誤り検出符号と、Ｃｏｌｕｍｎ−Ｓｔｏｒｅ形式に変換されたデータ構造から求めた誤り検出符号とが一致すれば、これらは論理形式が同一のデータに対応していることがわかる。
【００８５】
以下では、図２、図８等のテーブルにおいて、部分データの変更等によるテーブルデータのインテグリティのチェックについて説明する。
【００８６】
＜Ｒｏｗ−ｓｔｏｒｅ形式の場合＞
【００８７】
＜行の追加／挿入（結合可能で可換のため）＞
テーブルに一行追加、あるいは挿入された場合、追加又は挿入された行の誤り検出符号をｒｏｗ＿ｃｈｋｓｍとし、元のｎ行の誤り検出符号をΣ＿（ｉ＝１）＾ｎ  ｒｏｗ＿ｃｈｋｓｍ［ｉ］とすると、テーブル全体の誤り検出符号は次式（５）で与えられる。
【００８８】
Σ_(i=1)^n row_chksm[i]  + row_chksm               ・・・(5)
【００８９】
＜行の削除（減算可能のため）＞
ｎ行のテーブルから一行が削除された場合、削除された行（一行）の誤り検出符号をｒｏｗ＿ｃｈｋｓｍとし、元のｎ行の誤り検出符号をΣ＿（ｉ＝１）＾ｎ    ｒｏｗ＿ｃｈｋｓｍ［ｉ］とすると、テーブル全体の誤り検出符号は次式（６）で与えられる。
【００９０】
Σ_(i=1)^n row_chksm[i] - row_chksm                 ・・・(6)
【００９１】
＜行の更新（削除、挿入可能のため）＞
更新前の行（一行）の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｏｌｄ］、
更新後の行（一行）の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｎｅｗ］、
元のｎ行の誤り検出符号をΣ＿（ｉ＝１）＾ｎ  ｒｏｗ＿ｃｈｋｓｍ［ｉ］
とすると、更新後のテーブル全体の誤り検出符号は次式（７）で与えられる。
【００９２】
Σ_(i=1)^n row_chksm[i] - row_chksm[old] + row_chksm[new]  ・・・(7)
【００９３】
＜Ｃｏｌｕｍｎ−ｓｔｏｒｅ：追加／挿入（結合可能で可換のため）＞
元のｍ列の誤り検出符号をΣ＿（ｊ＝１）＾ｍ  ｃｏｌ＿ｃｈｋｓｍ［ｊ］
とし、
追加行の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｎｅｗ］
とすると、テーブル全体（ｎ行ｍ列）の誤り検出符号は次式（８）で与えられる。
【００９４】
Σ_(j=1)^m col_chksm[j] + row_chksm(new)      ・・・(8)
【００９５】
式（８）において、Σ＿（ｊ＝１）＾ｍ  ｃｏｌ＿ｃｈｋｓｍ［ｊ］は、次式（９）のように、第１列のｋｅｙ（１列ｎ行）の誤り検出符号ｋ＿ｃｈｋｓｍ［ｉ］と第２〜ｍ列のｖａｌｕｅ（（ｍ−１）列×ｎ行）の誤り検出符号ｖ＿ｃｈｋｓｍ［ｉ，ｊ］とに展開される。
【００９６】
Σ_(j=1)^m col_chksm[j] = 
Σ_(j=1)^1 (Σ_(i=1)^n (k_chksm[i])) +Σ_(j=2)^m (Σ_(i=1)^n (v_chksm[i,j])
=Σ_(i=1)^m (k_chksm[i]) + Σ_(j=2)^m (Σ_(i=1)^n (v_chksm[i,j])      ・・・(9)
【００９７】
これに、追加行の誤り検出符号（ｋｅｙの誤り検出符号ｋ＿ｃｈｋｓｍ［ｎｅｗ］と（ｍ−１）列のｖａｌｕｅの誤り検出符号ｖ＿ｃｈｋｓｍ［ｎｅｗ，  ｊ］の和）
row_chksm［new］ = k_chksm[new] +Σ_(j=2)^m v_chksm[new, j]       ・・・(10)
を加えると、式（８）は次式（１１）と表せる。
【００９８】
Σ_(i=1)^m k_chksm[i] + Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j]) 
+ k_chksm[new] +Σ_(j=2)^m v_chksm[new, j]
=Σ_(i=1)^ n k_chksm[i] + k_chksm[new] 
+ Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j] + v_chksm[new, j])   ・・・(11)
【００９９】
＜削除（減算可能のため）＞
元のｍ列の誤り検出符号をΣ＿（ｊ＝１）＾ｍ  ｃｏｌ＿ｃｈｋｓｍ［ｊ］とし、
削除行の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｏｌｄ］
とすると、テーブルデータ全体の誤り検出符号は、次式（１２）で与えられる。すなわち、Σの部分は列毎の誤り検出符号ｃｏｌ＿ｃｈｋｓｍ［ｉ］をｎ列（全列）足しあわせて全体の誤り検出符号としたものから、新たに削除行の誤り検出符号ｒｏｗ＿ｃｈｋｓｍ［ｏｌｄ］を減ずる。
【０１００】
Σ_(j=1)^m col_chksm[j] - row_chksm［old］    ・・・(12)
【０１０１】
ここで、Σ＿（ｊ＝１）＾ｍ  ｃｏｌ＿ｃｈｋｓｍ［ｊ］は、次式（１３）のように第１列のｋｅｙ（１列ｎ行）の誤り検出符号ｋ＿ｃｈｋｓｍ［ｉ］と第２〜ｍ列のｖａｌｕｅ（（ｍ−１）列ｎ行）の誤り検出符号ｖ＿ｃｈｋｓｍ［ｉ，ｊ］とに展開される。
【０１０２】
Σ_(j=1)^m col_chksm [i]
= Σ_(j=1)^1 (Σ_(i=1)^n k_chksm [i]) + Σ_(j=2)^m (Σ_(i=1)^n v_chksm［i, j］)
= Σ_(i=1)^n k_chksm [i] + Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j])      ・・・(13)
【０１０３】
式（１３）から、
row_chksm[old] = k_chksm[old] +Σ_(j=2)^m v_chksm[old, j]       ・・・(14)
を減じると、式（１５）が導かれる。
【０１０４】
Σ_(i=1)^n k_chksm[i] +Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j]) 
- (k_chksm[old] +Σ_(j=2)^m v_chksm[old, j])
=Σ_(i=1)^n k_chksm [i] - k_chksm[old] 
+Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j] - v_chksm[old, j])    ・・・(15)
【０１０５】
＜更新（削除して挿入）＞
更新前の行（一行）の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｏｌｄ］、
更新後の行（一行）の誤り検出符号をｒｏｗ＿ｃｈｋｓｍ［ｎｅｗ］、
元のテーブルｎ行ｍ列の誤り検出符号をΣ＿（ｉ＝１）＾ｍ  ｃｏｌ＿ｃｈｋｓｍ［ｉ］とすると、更新後のテーブル全体の誤り検出符号は、次式（１６）で与えられる。
【０１０６】
Σ_(j=1)^m col_chksm[j] - row_chksm［old］ + row_chksm[new]     ・・・(16)
【０１０７】
上式（１１）、（１５）から、式（１６）は、以下の（１７）となる。
Σ_(i=1)^n k_chksm [i] - k_chksm[old] + k_chksm[new) 
+Σ_(j=2)^m (Σ_(i=1)^n v_chksm[i, j] - v_chksm[old, j]+ v_chksm[new, j])    ・・・(17)
【０１０８】
上記各操作に対して、誤り検出符号（チェックサム）を行又は列単位よりも更に細分化した要素単位で導出したが、これは、「結合則を満たし且つ加算に関して可換で、減算が定義可能な演算から構成される誤り検出符号の計算」を利用し、データの追加／挿入、削除、更新に関して、データ全体の誤り検出符号が計算できることを、具体例に即して、実証するためである。
【０１０９】
＜実施形態４＞
本発明によれば、データの誤り検出／訂正符号を複数階層で取るようなストレージシステム／ネットワークシステムにも適用できる。図９は、第４の実施形態における誤り検出符号（Ｐ）の管理形態を説明する図である。
【０１１０】
図９に示すように、テーブルデータに関して、
行毎に誤り検出符号（Ｐ）、
複数行からなる行グループごと誤り検出符号（Ｇ  Ｐ）、
テーブル全体に対して誤り検出符号（ＴＢＬ  Ｐ）
を備えた構成としてもよい。行、行グループ、テーブル全体等階層化された、データ・インテグリティのチェックが可能である。
【０１１１】
また、テーブル全体の誤り検出符号（ＴＢＬ  Ｐ）を、行グループの誤り検出符号（Ｇ  Ｐ）ともに、各ストレージノードに持たせた場合、インテグリティ・チェックの多くの計算をストレージノードでローカルに行うことができる。一方、テーブル全体の誤り検出符号（ＴＢＬ  Ｐ）を、図示されない管理サーバ等に持たせた場合、データの更新、追加削除時にテーブル全体の誤り検出符号の更新等の管理を簡易化することができる。
【０１１２】
上記各実施形態のシステムは、分散ストレージシステム（メタサーバ方式、分散ＫＶＳ方式等）に適用して好適とされるが、任意のストレージシステムに適用可能であることは勿論である。
【０１１３】
なお、上記非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【０１１４】
上記実施形態の一部又は全ては、以下の付記のようにも記載され得るが、以下に限られない。
【０１１５】
(付記１)
データ格納部を備えたストレージと、
結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出符号を計算する計算手段と、
複数の前記誤り検出符号を合算する合算手段と、
を備え、
前記データ格納部に格納されたデータの変更時、前記計算手段は、変更対象の部分データに対して前記誤り検出符号を計算し、
前記合算手段は、前記計算手段で計算された前記部分データの前記誤り検出符号と、変更前のデータの誤り検出符号であって既に計算又は合算され前記データ格納部に格納されている誤り検出符号とを合算し、前記合算した値を、前記変更後のデータの誤り検出符号として、前記データ格納部に格納する、ことを特徴とするストレージシステム。
【０１１６】
(付記２)
前記データの変更は、データの追加、挿入、削除、更新を含む、ことを特徴とする付記１記載のストレージシステム。
【０１１７】
(付記３)
前記誤り検出符号の計算対象のデータから、物理的な構造に依存する情報を除く正規化手段を備え、
前記計算手段は、前記誤り検出符号の計算対象のデータから前記正規化手段で物理的な構造に依存する情報が除かれた状態のデータの誤り検出符号を計算する、こと特徴とする付記１又は２記載のストレージシステム。
【０１１８】
(付記４)
ストレージノードを複数備え、データを１つの前記ストレージノードに格納する場合、前記データのコピーであるレプリカを物理的に異なる形式で他の１つ又は複数の前記ストレージノードに格納するストレージシステム（分散ストレージシステム）であって、
前記ストレージノードが、付記１乃至３のいずれか一に記載のストレージシステムを備えている、こと特徴とするストレージシステム。
【０１１９】
(付記５)
ストレージノードを複数備え、データを１つの前記ストレージノードに格納する場合、前記データのコピーであるレプリカを物理的に異なる形式で他の１つ又は複数の前記ストレージノードに格納するストレージシステム（分散ストレージシステム）であって、
前記ストレージノードは、
データの格納時、前記データに対して誤り検出符号を計算し、データ格納部に格納する誤り検出符号付加手段と、
データ読み出し時、読み出した前記データの誤り検出符号を計算し、前記データに対応する誤り検出符号を前記データ格納部から読み出して前記計算した誤り検出符号と照合することで前記データにおける破損の有無を確認する誤り検出符号確認手段と、
を備え、前記誤り検出符号付加手段は、付記１又は２記載の前記計算手段と前記合算手段とを少なくとも備え、
さらに、１つ又は複数の前記ストレージノードに対して、
データの構造を変換するデータ構造変換手段と、
前記ストレージノードへのデータの格納時に、前記データの誤り検出符号を付加する誤り検出符号付加手段と、
前記ストレージノードからのデータの読み出し時に、データの誤りの有無を検出する誤り検出符号確認手段と、
前記ストレージノードとの間でデータの送受信を行うデータアクセス手段と、
を備えたデータ変換装置を備え、
前記データ変換装置は、
データの書き込み時、前記ストレージノードのデータ格納部に一旦格納されたデータを、前記データ構造変換手段で前記データと論理的には同一ではあるが物理的に異なる形式に変換し、前記データの誤り検出符号とともに前記ストレージノードのデータ格納部に格納し、
データの読み出し時、前記ストレージノードの前記データ格納部から読み出したデータの誤り検出符号を確認した結果、前記誤り検出符号が一致した場合には、読み出し要求元である前記クライアントのアプリケーションに送信し、
前記誤り検出符号の確認の結果、前記誤り検出符号が不一致の場合には、前記データ構造変換手段にて、他のストレージノードに格納されるレプリカからデータ構造を変換したデータと、前記データの誤り検出符号とを、前記ストレージノードの前記データ格納部に格納した上で、前記データを前記アプリケーションに送信する、ことを特徴とするストレージシステム。
【０１２０】
(付記６)
前記データ格納部は、キー欄のキー値に対応した複数の欄の値の組み合わせを１行のエントリとして、複数行を備えたテーブルを備え、
前記テーブルは、行単位で書き込みが行われ、前記テーブルを行ストア（Ｒｏｗ−ｓｔｏｒｅ）形式で記憶し、
前記テーブルのデータの前記誤り検出符号は、前記テーブルを構成する各行の誤り検出符号の総和として求まり、
前記行の追加、挿入では、前記合算手段は、元のテーブルデータに関して保持されている誤り検出符号に、前記計算手段で計算した前記行の誤り検出符号を加算して、前記データ格納部に格納し、
前記行の削除では、前記合算手段は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記行の誤り検出符号を減算し、
旧行を新行で置き換える更新では、前記合算手段は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記旧行の誤り検出符号を減算し、前記計算手段で計算した前記新行の誤り検出符号を加算する、ことを特徴とする付記４又は５記載のストレージシステム。
【０１２１】
(付記７)
前記誤り検出符号を、行単位、複数行の行グループ単位、テーブル全体の少なくともいずれかに対して１つ備えている、付記６記載のストレージシステム。
【０１２２】
(付記８)
前記計算手段は、前記誤り検出符号の代わりに、結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算が適用される誤り検出訂正符号を計算し、前記合算手段は、誤り検出訂正符号を合算する、ことを特徴とする付記１乃至７のいずれか一に記載のストレージシステム。
【０１２３】
(付記９)
結合則を満たしかつ加算に関して可換で、減算が定義可能な演算が適用される誤り検出符号を計算する計算工程と、
複数の誤り検出符号を合算する合算工程と、
を含み、
データの変更時、変更対象の部分データに対して前記計算工程で誤り検出符号を計算し、
前記合算工程は、前記部分データの誤り検出符号と、変更前の全体のデータに関して既に計算され、データ格納部に格納されている誤り検出符号とを合算し、前記合算した値を、前記更新後の全体のデータの誤り検出符号として前記データ格納部に格納する、ことを特徴とするデータ・インテグリティのチェック方法。
【０１２４】
(付記１０)
前記データの変更は、データの追加、挿入、削除、更新を含む、ことを特徴とする付記９記載のデータ・インテグリティのチェック方法。
【０１２５】
(付記１１)
前記誤り検出符号の計算対象のデータから、物理的な構造に依存する情報を除くこと特徴とする付記９又は１０記載のデータ・インテグリティのチェック方法。
【０１２６】
(付記１２)
ストレージノードを複数備え、データをストレージノードに格納する場合、他の１又は複数のストレージノードに前記データのコピーであるレプリカを格納する分散ストレージシステムにおいて、
前記ストレージノードは、データの格納時、前記データに対して誤り検出符号を付加し、データ格納部に格納し、
前記誤り検出符号の付加は、付記９又は１０の計算工程と合算工程を有し、
クライアントからの読み出しアクセス時、前記ストレージノードの前記データ格納部から読み出したデータの誤り検出符号を確認した結果、前記誤り検出符号が一致した場合には、読み出し要求元である前記クライアントのアプリケーションに送信し、
前記誤り検出符号の確認の結果、前記誤り検出符号が不一致の場合には、前記データ構造変換手段にて、他のストレージノードに格納されるレプリカからデータ構造を変換したデータと、前記データの誤り検出符号とを前記データ格納部に格納した上で、前記データを前記アプリケーションに送信する、ことを特徴とする、こと特徴とするデータ・インテグリティのチェック方法。
【０１２７】
(付記１３)
前記データ格納部は、キー欄のキー値に対応した複数の欄の値の組み合わせを１行のエントリとして、複数行を備えたテーブルを備え、
前記テーブルは、行単位で書き込みが行われ、前記テーブルを行ストア（Ｒｏｗ−ｓｔｏｒｅ）形式で記憶し、
前記テーブルのデータの前記誤り検出符号は、前記テーブルを構成する各行の誤り検出符号の総和として求まり、
前記行の追加、挿入では、前記合算工程は、元のテーブルデータに関して保持されている誤り検出符号に、前記計算工程で計算した前記行の誤り検出符号を加算して、前記データ格納部に格納し、
前記行の削除では、前記合算工程は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記行の誤り検出符号を減算し、
旧行を新行で置き換える更新では、前記合算手段は、前記元のテーブルデータに関して保持されている誤り検出符号から、前記旧行の誤り検出符号を減算し、前記計算工程で計算した前記新行の誤り検出符号を加算する、ことを特徴とする付記１１記載のデータ・インテグリティのチェック方法。
【０１２８】
(付記１４)
前記誤り検出符号を、行単位、複数行の行グループ単位、テーブル全体に対して１つ備えている、付記１２記載のデータ・インテグリティのチェック方法。
【０１２９】
(付記１５)
データ格納部を有するストレージと、
結合則を満たし、かつ加算に関して可換で、減算が定義可能な演算を適用して計算される誤り検出符号を計算する計算手段と、
複数の誤り検出符号を合算する合算手段と、
を備え、
前記データ格納部に格納されたデータの変更時、前記計算手段が変更対象の部分データに対して誤り検出符号を計算し、
前記合算手段は、前記部分データの誤り検出符号と、変更前の全体のデータに関して既に計算され前記データ格納部に格納されている誤り検出符号と、を合算し、前記合算した値を、前記更新後の全体のデータの誤り検出符号として前記データ格納部に格納するコンピュータに、前記計算手段と前記合算手段の処理を実行させるプログラム。
【０１３０】
(付記１６)
前記データの変更は、データの追加、挿入、削除、更新を含む、ことを特徴とする付記１５記載のプログラム。
【０１３１】
(付記１７)
前記誤り検出符号の計算対象のデータから、物理的な構造に依存する情報を除く正規化処理を備え、
前記計算処理は、前記誤り検出符号の計算対象のデータから前記正規化処理で物理的な構造に依存する情報が除かれた状態のデータの誤り検出符号を計算する、こと特徴とする付記１５又は１６記載のプログラム。
【符号の説明】
【０１３２】
１  誤り検出符号計算手段
２  誤り検出符号合算手段
３  ストレージ
４  変更データ入力手段
５  変更データ正規化手段
１０  クライアント
１１  アプリケーション
１２  ストレージアクセスインタフェース（I/F）
１３  データアクセス手段
２０  データ変換装置
２１  データ構造変換手段
２２  ストレージアクセスインタフェース（I/F）
２３  誤り検出符号付加手段
２４  誤り検出符号確認手段
２５  データアクセス手段
３０  ストレージノード
３１  ブロックアクセス手段
３２  誤り検出符号付加手段
３３  誤り検出符号確認手段
３４  データ格納部
【図１】
2013050836.tif 000004
【図２】
2013050836.tif 000005
【図３】
2013050836.tif 000006
【図４】
2013050836.tif 000007
【図５】
2013050836.tif 000008
【図６】
2013050836.tif 000009
【図７】
2013050836.tif 000010
【図８】
2013050836.tif 000011
【図９】
2013050836.tif 000012