(57)【特許請求の範囲】
【請求項１】
同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置であって、
前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割手段と、
前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得手段と、
前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶手段と、
前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶手段と、
前記第１及び前記第２の記憶手段にそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期手段とを備え、
前記ファイル同期手段は、
前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定部と、
前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを削除することによって、前記第２の記憶手段が記憶した前記同期先ファイルを前記第１の記憶手段が記憶した前記同期元ファイルに同期させるファイル同期部とを備えたことを特徴とするファイル同期装置。
【請求項２】
前記ブロック仮想分割手段、前記特徴データ取得手段及び前記ファイル同期手段は、それぞれ、アプリケーション及びファイルシステムのいずれかのプログラムに実装されることを特徴とする請求項１に記載のファイル同期装置。
【請求項３】
同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置が、
前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割ステップと、
前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得ステップと、
前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶ステップと、
前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶ステップと、
前記第１及び前記第２の記憶ステップにおいてそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期ステップとを実行し、
前記ファイル同期ステップは、
前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定ステップと、
前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを削除することによって、前記第２の記憶ステップで記憶した前記同期先ファイルを前記第１の記憶ステップで記憶した前記同期元ファイルに同期させるステップとを含むことを特徴とするファイル同期方法。
【請求項４】
同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置としてコンピュータを機能させるためのファイル同期プログラムであって、
前記コンピュータを、
前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割手段と、
前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得手段と、
前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶手段と、
前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶手段と、
前記第１及び前記第２の記憶手段にそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期手段として機能させ、
前記ファイル同期手段は、
前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定部と、
前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを削除することによって、前記第２の記憶手段が記憶した前記同期先ファイルを前記第１の記憶手段が記憶した前記同期元ファイルに同期させるファイル同期部とを備えたことを特徴とするファイル同期プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば２つの記憶領域にそれぞれ記憶された映像、音声等のコンテンツデータのファイルを同期させるファイル同期装置、ファイル同期方法及びファイル同期プログラムに関する。
【背景技術】
【０００２】
互いに異なる記憶領域に記憶されたファイルを同期させる（同一の内容とする）形態としては、例えば図１２に示すようなものがある。
【０００３】
図１２（ａ）は、ファイルを同期させる形態を概念的に示したものであり、記憶領域Ａと記憶領域Ｂとが通信路Ｃによって接続され、記憶領域Ａ及びＢにはそれぞれファイルＦＡ及びＦＢが記憶されている。図１２（ｂ）〜（ｄ）は、それぞれ、ファイルを同期させる形態を具体的に示したものである。すなわち、図１２（ｂ）に示したものは、ＩＰネットワークＣによって互いに接続されたノードＡ及びＢがそれぞれ蓄積装置Ａ及びＢを備え、蓄積装置Ａ及びＢはそれぞれファイルＦＡ及びＦＢを記憶している。また、図１２（ｃ）に示したものは、バスＣによって互いに接続された半導体メモリＡと蓄積装置ＢとがそれぞれファイルＦＡ及びＦＢを記憶している。また、図１２（ｄ）に示したものは、同一の蓄積装置内の記憶領域Ａ及びＢにそれぞれファイルＦＡ及びＦＢを記憶している。
【０００４】
図１２に示した各形態において、ファイルＦＢをＦＡに同期させる場合、ファイルＦＡをＦＢに上書きするのが最も簡単かつ万能な方法であるが、ファイルＦＡとＦＢの差分が少なく、かつ、通信路Ｃの伝送容量が小さい場合は、従来、両ファイルを比較して互いに異なる箇所を予め特定する手法がとられている。
【０００５】
例えば、ＯＳ（Operating System）の一つであるＵＮＩＸ（登録商標）では、ファイルＦＡ及びＦＢの全ての情報から両ファイルの差分を示すパッチと呼ばれる差分ファイルを生成する手法が用いられている。
【０００６】
また、ファイルＦＡ及びＦＢのそれぞれを構成する全てのデータ列を比較するのではなく、それぞれのデータ列のダイジェスト値（要約値）を算出し、このダイジェスト値によって両ファイルが同一か否かを判定する手法が知られている。
【０００７】
また、ファイル記録時にファイルを割当ユニットという単位に分離し、その割当ユニット毎にＮＤＳ（ネイティブ・データ署名）と呼ばれる一意に特定できる識別子を付与し、ファイルが更新された箇所に対応するＮＤＳのみを更新することにより、ファイルそのものを比較しないでファイルの更新部分を高速に特定することができるものが提案されている（例えば、特許文献１参照）。
【０００８】
また、ファイルのデータ列を直接比較しないで、ファイルのプロファイルを作成しプロファイル同士で比較することによって高速に両ファイルを比較できるものが提案されている（例えば、特許文献２参照）。
【０００９】
また、ダウンロード元のファイルとダウンロードしたファイルとを比較する際の比較方法として、ダウンロードしたファイルが正しくダウンロードされているかを高速に判定するために、ファイルの更新情報のみを比較するものが提案されている（例えば、特許文献３参照）。
【００１０】
また、２つのファイル間の差分を求めて両者を同期させるｒｓｙｎｃというアルゴリズムが知られている（例えば、非特許文献１参照）。このｒｓｙｎｃアルゴリズムについて図１３を用いて説明する。
【００１１】
図１３に示すように、装置α及びβにそれぞれファイルＡ及びＢが記憶されているものとする。まず、装置β側においてファイルＢの実データをブロックサイズＳのブロックに分割する。次に、ｗｅａｋチェックサム（３２ビットローリングチェックサム）と、ｓｔｒｏｎｇチェックサム（１２８ビットハッシュ関数）とを用いて、分割したブロック毎にチェックサムを計算する。そして、通信回線を介し、チェックサムのデータを装置αに送る。
【００１２】
装置αにおいて、まず、ファイルＢのｗｅａｋチェックサム全てについて１６ビットハッシュ値を計算し、そのハッシュ値でソートしたエントリーハッシュテーブルを作成する。次に、ファイルＡの最初のＳバイトブロックのｗｅａｋチェックサムと、その１６ビットハッシュ値とを計算する（ステップＳ１）。このハッシュ値と同じハッシュ値となるブロック（以下「一致ブロックｈ」という。）をハッシュテーブルから検索する。一致ブロックｈが見つからなければ、１バイトずつずらして見つかるまで検索する。
【００１３】
一致ブロックｈが１つ以上見つかった場合は、その中からｗｅａｋチェックサムが一致するブロック（以下「一致ブロックｗ」という。）を検索する（ステップＳ２）。一致ブロックｗが見つからなかった場合は、ステップＳ１の処理に戻る。
【００１４】
一致ブロックｗが１つ以上見つかった場合は、その中から一致ブロックｗがｓｔｒｏｎｇチェックサムで一致するかを確認し（ステップＳ３）、一致すれば同一ブロックと判定し、一致しなければステップＳ１の処理に戻る。そして、ｓｔｒｏｎｇチェックサムで同一ブロックと判定されたブロックを除いた部分を差分データとし、差分データを装置βに送ってファイルＢに上書きし、ファイルＢをファイルＡに同期させる。
【００１５】
以上のように、ｒｓｙｎｃアルゴリズムでは、ファイルをブロックに分割し、ブロック毎にチェックサムを比較することにより、特に通信速度の遅い通信回線（例えばダイヤルアップ回線）で結ばれた装置間においては、通信回線に流すデータの量を少なくすることにより、高速にファイルを同期することができるようになっている。
【特許文献１】特表２００２−５０１２５８号公報
【特許文献２】特開平１０−２４０６０２号公報
【特許文献３】特開２００５−１６４６４０号公報
【非特許文献１】「Ｔｈｅ  ｒｓｙｎｃ  ａｌｇｏｒｉｔｈｍ」、［ｏｎｌｉｎｅ］、［平成２０年２月１日検索］、インターネット〈ＵＲＬ：ｈｔｔｐ：／／ｒｓｙｎｃ．ｓａｍｂａ．ｏｒｇ／ｔｅｃｈ＿ｒｅｐｏｒｔ／〉
【発明の開示】
【発明が解決しようとする課題】
【００１６】
サイズの大きなファイルを高速に同期させるためには、相違箇所を高速に発見し、相違箇所のみを転送するのが有効である。しかしながら、従来の手法には以下に示すような課題があった。
【００１７】
まず、パッチと呼ばれる差分ファイルを用いる手法は、ファイルＦＡ及びＦＢの全ての情報から両ファイルの相違箇所を特定するものであり、例えば図１２（ｂ）に示すような形態においてはＩＰネットワークを介してファイルＦＡとＦＢとを比較することとなるので、ファイルの読み込み、ファイルの転送を伴うため、差分ファイルを短時間で生成できないという課題があった。
【００１８】
次に、ダイジェスト値によって両ファイルが同一であるか否かを判定する手法では、ファイル全体において相違箇所があるか否かを確認することはできるが、相違箇所がある場合にファイルのどの箇所が相違しているのかを特定することができないという課題があった。
【００１９】
次に、特許文献１に示されたものは、識別子ＮＤＳは割当ユニットの内容に基づいて生成されるものではないので、例えば図１２（ｂ）に示すような互いに異なるノード上で作製された２つのファイルの内容を比較することができず、２つのファイルの相違箇所を特定することができないという課題があった。
【００２０】
また、特許文献１に示されたものは、ファイルシステム上でファイルを作成・更新するときにＮＤＳを作成・更新するものなので、２つのファイルがそれぞれ記憶される記憶領域が共にＮＤＳを生成することができるファイルシステム上になければならないという課題があった。
【００２１】
次に、特許文献２に示されたものは、ファイルのダウンロードが途中で失敗したときのことを考慮しているため、２つのファイルの相違箇所の構成要素だけでなく、相違箇所がある構成要素からファイルの末尾を含む構成要素までのファイルデータを全部ダウンロードし直す構成となっているので、相違箇所がファイルの先頭に近いところにある場合は、ほとんど全てのファイルデータをダウンロードし直さなければならないという課題があった。
【００２２】
次に、特許文献３に示されたものは、ダウンロードしたファイルが正しくダウンロードされているかを高速に判定するため、ファイルの更新情報のみを比較する構成となっているので、ファイルに１箇所でも相違箇所があれば全てのファイルデータをダウンロードし直さなければならないという課題があった。
【００２３】
次に、非特許文献１に示されたものでは、異なると判定された箇所に対しては、ブロックデータを１バイトずつずらしながらチェックサムが一致する箇所を探す構成なので、ファイルサイズが大きくなるに従って一致箇所を探索する時間が増加するという課題があった。また、非特許文献１のパッチを利用する方法と同様に、ファイル全体を読むための時間がかかるという課題もあった。
【００２４】
以上のように、ファイル同期における従来のファイルの比較方法では、２つのファイルの相違箇所を短時間で検出することができず、その結果、２つのファイルの同期に時間がかかるという課題があった。
【００２５】
本発明は、このような事情に鑑みてなされたものであり、従来よりも高速にファイルを同期させることができるファイル同期装置、ファイル同期方法及びファイル同期プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２６】
本発明のファイル同期装置は、同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置であって、前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割手段と、前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得手段と、前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶手段と、前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶手段と、前記第１及び前記第２の記憶手段にそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期手段とを備え、前記ファイル同期手段は、前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定部と、前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを削除することによって、前記第２の記憶手段が記憶した前記同期先ファイルを前記第１の記憶手段が記憶した前記同期元ファイルに同期させるファイル同期部とを備えた構成を有している。
【００２７】
この構成により、本発明のファイル同期装置は、ファイル記憶時にファイル記憶と並行して記憶された同期元ファイル特徴データと同期先ファイル特徴データとの比較によって、同期元ファイルと同期先ファイルとの相違箇所を特定し、相違ブロックデータに基づいて同期先ファイルを同期元ファイルに同期させるので、従来よりも高速にファイルを同期させることができる。
【００２９】
この構成により、本発明のファイル同期装置は、第１のノードと第２のノードとが通信回線を介して接続されている場合でも、相違箇所指示データ及び相違ブロックデータに基づいて同期先ファイルを同期元ファイルに同期させるので、同期元ファイルと同期先ファイルとの相違箇所が相対的に少ない場合、例えば１時間番組のコンテンツファイルに対し２〜３分程度の変更を行う場合において、従来よりも高速にファイルを同期させることができる。
【００３０】
また、この構成により、本発明のファイル同期装置は、第２のノードが第１のノードよりもデータ処理能力が低い場合や、第２のノードに負荷が集中しやすい場合等においても、第２のノードに負担をかけることなく特徴データの比較ができるため、相違箇所の特定を短時間で行うことができる。
【００３２】
この構成により、本発明のファイル同期装置は、第１のノードと第２のノードとが通信回線を介して接続されている場合でも、相違箇所指示データ及び相違ブロックデータに基づいて同期先ファイルを同期元ファイルに同期させるので、同期元ファイルと同期先ファイルの相違箇所が相対的に少ない場合は、従来よりも高速にファイルを同期させることができる。
【００３３】
また、この構成により、本発明のファイル同期装置は、第１のノードが第２のノードよりもデータ処理能力が低い場合や、第１のノードに負荷が集中しやすい場合等においても、第１のノードに負担をかけることなく特徴データの比較ができるため、相違箇所の特定ファイルの同期を短時間で行うことができる。
【００３４】
なお、前記ブロック仮想分割手段、前記特徴データ取得手段及び前記ファイル同期手段は、それぞれ、アプリケーション及びファイルシステムのいずれかのプログラムに実装されるのが好ましい。
【００３５】
本発明のファイル同期方法は、同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置が、前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割ステップと、前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得ステップと、前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶ステップと、前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶ステップと、前記第１及び前記第２の記憶ステップにおいてそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期ステップとを実行し、前記ファイル同期ステップは、前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定ステップと、前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記削除対象ブロックのデータを削除することによって、前記第２の記憶ステップで記憶した前記同期先ファイルを前記第１の記憶ステップで記憶した前記同期元ファイルに同期させるステップとを含む構成を有している。
【００３６】
この構成により、本発明のファイル同期方法は、同期元ファイル特徴データと同期先ファイル特徴データとの比較によって、同期元ファイルと同期先ファイルとの相違箇所を特定し、相違ブロックデータに基づいて同期先ファイルを同期元ファイルに同期させるので、従来よりも高速にファイルを同期させることができる。
【００３７】
本発明のファイル同期プログラムは、同期させる対象として同期元ファイル及び少なくとも１つの同期先ファイルが設定され、前記同期先ファイルを前記同期元ファイルに同期させるファイル同期装置としてコンピュータを機能させるためのファイル同期プログラムであって、前記コンピュータを、前記同期元ファイル及び前記同期先ファイルの各実データをそれぞれ予め定められたサイズのブロックデータに仮想分割するブロック仮想分割手段と、前記同期元ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期元ファイルのダイジェスト値と前記同期先ファイルに係る前記ブロックデータの特徴を前記ブロックデータ毎に示す同期先ファイルのダイジェスト値とを計算する特徴データ取得手段と、前記同期元ファイルと前記同期元ファイルのダイジェスト値のデータとを記憶する第１の記憶手段と、前記同期先ファイルと前記同期先ファイルのダイジェスト値のデータとを記憶する第２の記憶手段と、前記第１及び前記第２の記憶手段にそれぞれ記憶した前記同期元ファイルのダイジェスト値のデータ及び前記同期先ファイルのダイジェスト値のデータに基づいて前記ブロックデータ単位でのデータの挿入及びデータの削除を伴うファイルの同期を行うファイル同期手段として機能させ、前記ファイル同期手段は、前記同期元ファイルのダイジェスト値のデータと前記同期先ファイルのダイジェスト値のデータとを比較して前記同期元ファイルと前記同期先ファイルとの相違箇所を特定する相違箇所特定部と、前記ブロックデータ単位でのデータの挿入を伴うファイルの同期において挿入対象ブロックの挿入位置情報及び前記挿入対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを挿入するとともに、前記ブロックデータ単位でのデータの削除を伴うファイルの同期において削除対象ブロックの削除位置情報及び前記削除対象ブロックの個数情報により前記相違箇所に該当するブロックのデータを削除することによって、前記第２の記憶手段が記憶した前記同期先ファイルを前記第１の記憶手段が記憶した前記同期元ファイルに同期させるファイル同期部とを備えた構成を有している。
【００３８】
この構成により、本発明のファイル同期プログラムは、同期元ファイル特徴データと同期先ファイル特徴データとの比較によって、同期元ファイルと同期先ファイルとの相違箇所を特定し、相違ブロックデータに基づいて同期先ファイルを同期元ファイルに同期させるので、同期元ファイルと同期先ファイルの相違箇所が相対的に少ない場合は、従来よりも高速にファイルを同期させることができる。
【発明の効果】
【００３９】
本発明は、従来よりも高速にファイルを同期させることができるという効果を有するファイル同期装置、ファイル同期方法及びファイル同期プログラムを提供することができるものである。
【発明を実施するための最良の形態】
【００４０】
以下、本発明の実施の形態について図面に基づいて説明する。なお、本発明のファイル同期装置を、２つのノードにそれぞれ１つずつ記憶されたファイルを同期するものに適用した例を挙げて説明する。
【００４１】
図１は、本発明に係るファイル同期装置の一実施の形態における構成の概要を示すブロック図である。図１に示すように、本実施の形態におけるファイル同期装置１０は、ＩＰネットワーク１１を介して接続されたノード１００とノード２００とを備えている。ここで、ノード１００はファイルを同期させる際の同期元ノードとし、ノード２００は同期先ノードとする。なお、以下の記載において、インターフェース部をＩＦ部、アプリケーション部をアプリ部と略記する。また、ノード１００は、本発明に係る第１のノードを構成する。また、ノード２００は、本発明に係る第２のノードを構成するものであり、本実施の形態では１つで説明するが、ノード２００を複数設けてもよい。
【００４２】
ノード１００は、ユーザＩＦ部１０１と、ファイル編集アプリ部１１０と、ファイル同期アプリ部１２０と、ＯＳ（Operating System）部１３０と、蓄積装置１０２と、ネットワークＩＦ部１０３とを備えている。
【００４３】
ノード２００は、ファイル同期アプリ部２１０と、ＯＳ部２２０と、蓄積装置２０１と、ネットワークＩＦ部２０２とを備えている。
【００４４】
ノード１００の蓄積装置１０２は、同期元ファイルＦＡと、後述するダイジェストデータＤＡとを記憶している。また、ノード２００の蓄積装置２０１は、同期先ファイルＦＢと、後述するダイジェストデータＤＢとを記憶している。なお、蓄積装置１０２及び蓄積装置２０１は、それぞれ、本発明に係る第１及び第２の記憶手段を構成する。また、ダイジェストデータＤＡ及びＤＢは、それぞれ、本発明に係る同期元ファイル特徴データ及び同期先ファイル特徴データに対応する。
【００４５】
図１において、ノード１００及び２００は、例えばコンピュータで構成される。また、ユーザＩＦ部１０１は、例えばマウスやキーボート等の入出力装置や、インターフェース回路等で構成される。また、ファイル編集アプリ部１１０、ファイル同期アプリ部１２０及び２１０、ＯＳ部１３０及び２２０は、それぞれ、例えばコンピュータを動作させるためのプログラムで構成される。また、蓄積装置１０２及び２０１は、例えばＨＤＤ（Hard Disk Drive）で構成される。また、ネットワークＩＦ部１０３及び２０２は、それぞれ、例えばネットワークインターフェスカードで構成される。
【００４６】
次に、図２に基づいて、ノード１００におけるファイル編集アプリ部１１０の詳細な構成について説明する。図２は、ファイル編集アプリ部１１０の詳細な構成を示すブロック図である。
【００４７】
図２に示すように、ファイル編集アプリ部１１０は、ファイルを編集するファイル編集部１１１と、編集したファイルをブロックに分割するブロック分割部１１２と、ダイジェストデータＤＡを処理するダイジェストデータ処理部１１３とを備えている。また、ＯＳ部１３０は、ファイルの入出力を制御するファイル入出力部１３１を備えている。
【００４８】
ファイル編集部１１１は、ユーザＩＦ部１０１の指示に従って、例えば映像、音声、テキスト、静止画等のコンテンツデータのファイルを編集するようになっている。
【００４９】
ブロック分割部１１２は、ファイル編集部１１１が編集したファイルを蓄積装置１０２に記録する際に、予め定められたファイルサイズのブロックに仮想分割し、仮想分割したブロック毎にダイジェスト値（要約値）を計算するようになっている。なお、ブロック分割部１１２は、本発明に係るブロック仮想分割手段及び特徴データ取得手段を構成する。
【００５０】
具体的には、ブロック分割部１１２は、ファイルを記録する際に、図３に示すようにファイルの実データを１つ以上のブロックに仮想分割し、ファイルの記録と並行して、ブロック毎にダイジェスト値を計算するようになっている。ここで、仮想分割とは、実際に１つのファイルの実データを別の複数のファイルの実データに分割することではなく、ダイジェスト値を計算するためのブロックの範囲を設定することをいう。また、ダイジェスト値とは、例えばチェックサム、ＣＲＣ（Cyclic Redundancy Check：巡回冗長検査）、ハッシュ関数等の手法を用いて各ブロックのデータの特徴を表した固定長の数値をいう。なお、説明の都合上、ブロック分割部１１２は、分割したブロックにブロック番号を付与するものとする。例えば、ファイルの先頭に属するブロックはブロック番号０とし、それ以降順に１ずつ加えた値とする。
【００５１】
ブロック分割部１１２が生成する各ブロックのブロックサイズは、固定長でも可変長でもよい。ブロック分割部１１２は、ブロックサイズを固定長とする場合は図３（ａ）に示すように、ブロック番号（０、１、２、・・・、Ｎ−１）と、各ブロックのダイジェスト値（Ｄ０、Ｄ１、Ｄ２、・・・、ＤＮ−１）との対応関係を示すデータをダイジェストデータＤＡとして記録するようになっている。また、ブロック分割部１１２は、ブロックサイズを可変長とする場合は図３（ｂ）に示すように、ブロック番号（０、１、２、・・・、Ｎ−１）と、各ブロックのサイズ（Ｌ０、Ｌ１、Ｌ２、・・・、ＬＮ−１）と、各ブロックのダイジェスト値（Ｄ０、Ｄ１、Ｄ２、・・・、ＤＮ−１）との対応関係を示すデータをダイジェストデータＤＡとして記録するようになっている。このダイジェストデータＤＡは、ファイルが新規作成されるときのみでなく、ファイルが更新されるときにも、その更新内容に合わせて作成されるものである。
【００５２】
なお、図３（ａ）及び（ｂ）には、ダイジェストデータＤＡの記載例としてテキストフォーマットで記載する例を示したが、本発明はこれに限定されるものではなく、ブロック番号とブロックサイズやダイジェスト値とが対応づけられたデータであれば、どのようなフォーマットで記載してもよい。また、ダイジェスト値は固定長なので、ブロックサイズを固定長とする場合やブロックサイズが可変でもブロックサイズを固定長で表現する場合は、指定するブロック番号のダイジェスト値はダイジェストデータ内の位置情報（先頭から何バイト目に記録されているかを示す情報）からだけでも得られるため、ダイジェストデータにブロック番号の情報は必須ではなく省略してもよい。
【００５３】
また、本実施の形態では、アプリケーションでダイジェストデータを作成する構成としているので、ダイジェストデータを１つのファイルとして記録し、アプリケーションでファイルの実データとダイジェストデータとを関連付けるものとしている。なお、全てのファイルに対してダイジェストデータの作成は必須ではないが、高速に比較を行う必要のあるファイルを生成する場合はダイジェストデータを作成するのが好ましい。
【００５４】
また、アプリケーションに代えてファイルシステムでダイジェストデータを作成する構成とすることもできる。ファイルシステムでダイジェストデータを作成する場合は、ファイルシステム内でダイジェストデータを記録する領域を確保し、ファイルシステムがファイルの実データとダイジェストデータとを関連付けるようにする。ファイルシステムがダイジェストデータを作成する構成とすれば、アプリケーションはダイジェストデータの作成について関わることなく、全てのファイルに自動的にダイジェストデータが付与される。ただし、そのダイジェストデータをアプリケーションで取得できるように、ＡＰＩ（Application Program Interface）を用意する必要がある。ファイルシステムでダイジェストデータを生成する場合は、ブロックのサイズを固定長にし、そのブロックのサイズとファイルシステムのブロックサイズ（クラスタサイズ）とを同じにすれば実装を簡略化できて好ましい。
【００５５】
図２に戻り、構成の説明を続ける。ダイジェストデータ処理部１１３は、蓄積装置１０２から読み出したファイルＦＡのダイジェストデータＤＡを処理するようになっている。
【００５６】
ファイル入出力部１３１は、ユーザＩＦ部１０１の指示に従って、蓄積装置１０２に対して編集ファイルの書き込み及び読み出しを行うようになっている。また、ファイル入出力部１３１は、ファイルの実データＦＡとダイジェストデータＤＡとを管理するようになっている。ここで、ファイルの実データＦＡ及びダイジェストデータＤＡは、読み書き時間の短縮化を図るため、それぞれ別個に管理し、できる限り連続領域に記録される構成とするのが好ましい。
【００５７】
次に、ダイジェストデータの作成が必要なアプリケーションやファイルシステムにおいて、ファイルを保存するときの動作について図４を用いて説明する。
【００５８】
まず、ファイルの書き込み指示を行い（ステップＳ１１）、ファイルの実データを予め定められたサイズのブロックデータに仮想分割する（ステップＳ１２）。続いて、全ブロックのダイジェスト値を計算し（ステップＳ１３）、ファイルとダイジェストデータとを所定の蓄積装置に書き込む（ステップＳ１４、Ｓ１５）。
【００５９】
次に、本実施の形態におけるファイル同期装置１０のファイル編集アプリ部１１０に係る動作について図２及び図５に基づいて説明する。図５は、編集対象のファイルに対し編集して保存するときの動作の概要を示すフローチャートである。
【００６０】
まず、ユーザがユーザＩＦ部１０１を介し、アプリケーションであるファイル編集アプリ部１１０を立ち上げ（ステップＳ２１）、編集対象のファイルを開く動作を行う。ここで、該当するファイルが蓄積装置１０２に存在するか否かを判断し（ステップＳ２２）、該当ファイルが存在する場合は蓄積装置１０２からファイルを読み込み（ステップＳ２３）、ファイルの読み込みと同時にそのファイルに対応するダイジェストデータも読み込む（ステップＳ２４）。
【００６１】
一方、ステップＳ２２において、該当ファイルが存在しない場合はファイル及びダイジェストデータを新規にオープンする（ステップＳ２５、２６）。
【００６２】
その後、ファイル編集部１１１はファイルを編集し（ステップＳ２７）、ブロック分割部１１２は、ファイルを書き込むとき予め定められたサイズのブロックデータにファイルを分割し（ステップＳ２８）、全ブロックを対象としてブロック毎にダイジェスト値を計算し（ステップＳ２９）、ファイルの書き込み（ステップＳ３０）とダイジェストデータの書き込み（ステップＳ３１）とを実行する。
【００６３】
次に、図６に基づいて、ノード１００におけるファイル同期アプリ部１２０及び２１０に係る構成の詳細について説明する。図６は、ファイル同期アプリ部１２０及び２１０に係る詳細な構成を示すブロック図である。なお、図６において、例えば同期対象のファイルが存在しないというようなエラー時の処理経路については図示を省略した。
【００６４】
図６に示すように、ファイルの同期元であるノード１００において、ファイル同期アプリ部１２０は、ブロックデータ処理部１２１と、ダイジェストデータ処理部１２２とを備えている。なお、ファイル同期アプリ部１２０は、本発明に係るファイル同期手段及び相違箇所特定部を構成する。
【００６５】
また、前述の図２における説明と一部重複するが、ＯＳ部１３０は、ファイル入出力部１３１と、通信部１３２とを備えている。ファイル入出力部１３１には蓄積装置１０２が接続され、通信部１３２にはネットワークＩＦ部１０３が接続されている。蓄積装置１０２は、同期元のファイルであるファイルＦＡと、そのダイジェストデータＤＡとを記憶している。なお、ネットワークＩＦ部１０３は、本発明に係る第１の送信手段及び第１の受信手段を構成する。
【００６６】
一方、ファイルの同期先であるノード２００において、ファイル同期アプリ部２１０は、ファイル再構成部２１１と、ダイジェストデータ処理部２１２とを備えている。なお、ファイル同期アプリ部２１０は、本発明に係るファイル同期手段及びファイル同期部を構成する。
【００６７】
また、ＯＳ部２２０は、ファイル入出力部２２１と、通信部２２２とを備えている。ファイル入出力部２２１には蓄積装置２０１が接続され、通信部２２２にはネットワークＩＦ部２０２が接続されている。なお、ネットワークＩＦ部２０２は、本発明に係る第２の送信手段及び第２の受信手段を構成する。
【００６８】
蓄積装置２０１は、同期先のファイルであるファイルＦＢと、そのダイジェストデータＤＢとを記憶している。
【００６９】
ノード１００のファイル同期アプリ部１２０において、ブロックデータ処理部１２１は、ユーザＩＦ部１０１がファイルＦＡとＦＢとを同期させる指示をしたとき、ファイルＦＡとＦＢとの比較をダイジェストデータ処理部１２２に指示するようになっている。また、ブロックデータ処理部１２１は、ファイルＦＡとＦＢとが異なるとき、ダイジェストデータ処理部１２２から受け取った相違箇所に相当する相違ブロックのデータに当該ブロックサイズ及びブロック番号を示すデータを付与し、通信部１３２、ネットワークＩＦ部１０３及びＩＰネットワーク１１を介してノード２００に送信するようになっている。
【００７０】
ダイジェストデータ処理部１２２は、ブロックデータ処理部１２１がファイルＦＡとＦＢとを比較するよう指示したとき、それらのダイジェストデータＤＡとＤＢとを比較するようになっている。この比較によって、ファイルＦＡとＦＢとが仮想分割されたブロック同士で比較されることとなる。ここで、ダイジェストデータ処理部１２２は、ダイジェストデータＤＡを蓄積装置１０２からファイル入出力部１３１を介して取得し、ダイジェストデータＤＢをノード２００からＩＰネットワーク１１、ネットワークＩＦ部１０３及び通信部１３２を介して取得するようになっている。
【００７１】
なお、動作説明で述べるように、ファイルの同期には、ブロックデータの置換のみによる同期（図９）、ブロックデータの挿入を伴う同期（図１０）、ブロックデータの削除を伴う同期（図１１）があり、ダイジェストデータ処理部１２２は、これらの同期形態に応じた動作を行うようになっている。例えば、ブロックデータの置換のみによるファイルの同期においては、ダイジェストデータ処理部１２２は、ダイジェストデータＤＡとＤＢとを比較する際に、ブロックサイズ又はブロックのダイジェスト値が相違する全てのブロック番号の情報を含む相違ブロック番号リストを作成し、これをブロックデータ処理部１２１に渡すようになっている。
【００７２】
通信部１３２は、ＩＰネットワーク１１に接続されたネットワークＩＦ部１０３を介し、ノード２００と通信するようになっている。
【００７３】
ノード２００において、通信部２２２は、ＩＰネットワーク１１に接続されたネットワークＩＦ部２０２を介し、ノード１００と通信するようになっている。
【００７４】
ファイル再構成部２１１は、前述のダイジェストデータ処理部１２２と同様に、ファイルの同期形態に応じた動作を行うようになっている。例えば、ブロックデータの置換のみによるファイルの同期においては、ファイル再構成部２１１は、ファイルＦＡとＦＢとの相違箇所に相当する相違ブロックデータと、当該相違ブロックのブロックサイズ及びブロック番号を示すデータとに基づき、ファイルＦＢの該当箇所のデータを書き換えるようになっている。
【００７５】
ダイジェストデータ処理部２１２は、ノード１００から受信した、全ての相違ブロックデータについてダイジェスト値を計算し、ダイジェストデータＤＢにおけるブロックサイズを示すデータ及びダイジェスト値を更新し、更新したダイジェストデータＤＢを蓄積装置２０１にファイル入出力部２２１を介して記憶するようになっている。
【００７６】
次に、ダイジェストデータ処理部１２２で行うファイルＦＡとＦＢとのブロック同士の比較について説明する。
【００７７】
ダイジェストデータ処理部１２２は、ブロックサイズ及びダイジェスト値の情報でブロック同士を比較し、ブロックサイズとダイジェスト値とが同じであればその２つのブロック内のデータ列は一致していると判断するものである。つまり、ダイジェストデータ処理部１２２は、ブロック内のデータ列同士で比較するものではない。
【００７８】
したがって、例えば、ブロックデータの置換のみによるファイルの同期において、ダイジェストデータ処理部１２２は、ファイル全体において相違箇所を特定するには、ブロック番号０から最終番号までのブロックを順にダイジェスト値の情報で比較をし、ダイジェスト値が相違するブロック番号のみをリストアップすればよい。すなわち、ダイジェストデータ処理部１２２は、２つのファイルのダイジェストデータＤＡとＤＢとを比較することによって、その２つのファイルの相違ブロックのブロック番号情報を取得し、相違箇所を特定することができる。
【００７９】
ダイジェスト値としては、入力データサイズの大きさに関係なく固定長の値であることが望ましい。固定長でない場合は、ダイジェスト値の長さも別途個別に管理する必要がある。また、異なる入力データ列に対し同じ出力値となる確率が低くなるように、ダイジェスト値は、与えられたビット数で表現できる全ての値の出現確率が均一であることが望ましい。
【００８０】
例えば、１ブロックあたりのダイジェスト値の出力サイズをＴ、２つのファイルで実際に異なるブロックの数をｎとすると、ｎ箇所ある異なるブロックのうち１箇所でも同一ブロックであると判断してしまう確率は１−（１−２−Ｔ）ｎである。この確率が例えば約０．５になるのは、Ｔ＝８のときでｎ＝１７７、Ｔ＝１６のときでｎ＝４５４２６である。比較するデータのブロック数にもよるが、Ｔは最低でも３２ビットであることが好ましい。その一方で、Ｔの長さに比例して、ダイジェストデータ列の読み出しや比較処理に時間がかかるため、Ｔは長すぎてもよくない。また、ダイジェスト値を計算するときの処理が軽いことが求められる。ダイジェスト値の計算アルゴリズムの例としては、チェックサム、ＣＲＣ、ハッシュ関数（例：ＭＤ４、ＭＤ５、ＳＨＡ１）などがあるが、上記の条件を満たしていれば、ここで挙げた例に限らず、どのようなアルゴリズムを使用してもよい。
【００８１】
また、ブロックサイズは、大きすぎても小さすぎてもよくない。大きすぎると、相違箇所数が少なくても差分データ量が不必要に大きくなる。逆に、小さすぎると、ダイジェストデータのサイズが大きくなり、またダイジェスト値の読み込み、書き込み、転送、比較のいずれの処理においても時間がかかる。したがって、使用環境に応じて最適なブロックサイズを予め求めておくのが好ましい。
【００８２】
一例として、ブロックサイズを４キロバイトの固定長とし、１つのブロックのダイジェスト値の長さを３２ビット（４バイト）とすると、ダイジェストデータの大きさはファイルの大きさのおよそ１０００分の１となるので、ダイジェストデータの読み出し時間、比較時間及び転送時間は、ファイルの実データを用いる場合に比べて無視できるほど短くなる。
【００８３】
次に、本実施の形態におけるファイル同期装置１０のファイル同期に係る動作について説明する。ここでは、ユーザがノード２００側にあるファイルＦＢをノード１００側にあるファイルＦＡに同期させる指示をしたときの例を挙げ、図６〜図８に基づいて説明する。図７は、動作の概要を示すフローチャートであり、図８は、動作の詳細を示すフローチャートである。
【００８４】
最初に、図６及び図７に基づいてファイル同期に係る動作の概要を説明する。
【００８５】
まず、ユーザによるファイル同期の指示があると（ステップＳ４１）、ノード１００側のファイル同期アプリ部１２０は、ファイルＦＡのダイジェストデータＤＡを蓄積装置２０１から読み込み（ステップＳ４２）、ノード２００側のファイル同期アプリ部２１０にファイルＦＢのダイジェストデータＤＢをノード１００側に転送するよう指示する。この指示に従い、ノード２００側のファイル同期アプリ部２１０は、ダイジェストデータＤＢを読み込み（ステップＳ５１）、それをノード１００側に送信する（ステップＳ５２）。
【００８６】
ノード１００側のファイル同期アプリ部１２０は、このダイジェストデータＤＢを受信し（ステップＳ４３）、先に読み込んだダイジェストデータＤＡと受信したダイジェストデータＤＢとを比較して相違ブロックを特定し（ステップＳ４４）、ブロックデータの置換のみによるファイルの同期においては、ブロックサイズ又はダイジェスト値が異なるブロック番号をリストアップする。リストアップされたブロック番号に対応するブロックデータをファイルＦＡから読み出し、それぞれのブロックデータにブロック番号及びブロックサイズを示すデータを付与して、ノード２００側に送信する（ステップＳ４５）。ノード２００側のファイル同期アプリ部２１０は、このデータを受信し（ステップＳ５３）、受信したブロックデータをブロック番号に対応するファイルＦＢの該当箇所に上書きして更新する（ステップＳ５４）。同時に、そのブロックのダイジェスト値を計算し、ダイジェストデータＤＢを更新する（ステップＳ５５）。
【００８７】
次に、図６及び図８に基づいてファイル同期に係る動作の詳細を説明する。図８は、図７に記載した動作を具体化した一例を示すものである。
【００８８】
ユーザが、ノード１００上でファイル同期アプリ部１２０に対し、ユーザＩＦ部１０１を介してファイルＦＢをＦＡに同期させる指示があると（ステップＳ６１）、ブロックデータ処理部１２１は、ファイル入出力部１３１に対しファイルＦＡが存在するか確認し（ステップＳ６２）、存在しなければ処理を終了し、存在していればブロックデータ処理部１２１はダイジェストデータ処理部１２２にファイルＦＡとＦＢとの比較を指示する。
【００８９】
ダイジェストデータ処理部１２２は、ファイルＦＡとＦＢとの比較を、ファイルＦＡとＦＢの実データではなくダイジェストデータＤＡとＤＢとで比較するため、ダイジェストデータＤＡの読み込みをファイル入出力部１３１に指示し、ノード２００にあるダイジェストデータＤＢの転送を通信部１３２に指示する（ステップＳ６３）。この転送指示信号は、ネットワークＩＦ部１０３及びＩＰネットワーク１１を介してノード２００に送られる。
【００９０】
ノード２００において、ファイル同期アプリ部２１０のダイジェストデータ処理部２１２は、ファイル入出力部２２１に対しファイルＦＢが蓄積装置２０１に存在するか確認させる（ステップＳ８１）。なお、ファイルＦＢの存在確認に代えてダイジェストデータＤＢの存在確認としてもよい。
【００９１】
ダイジェストデータ処理部２１２は、ファイルＦＢが存在していればファイル入出力部２２１を経由してダイジェストデータＤＢを読み込み（ステップＳ８２）、読み込んだダイジェストデータＤＢを通信部２２２経由でノード１００に送信する（ステップＳ８３）。ステップＳ８１においてファイルＦＢが存在しなければ、ダイジェストデータ処理部２１２は、ノード１００にエラー通知信号によってエラー発生の通知する（ステップＳ８４）。
【００９２】
ノード１００のダイジェストデータ処理部１２２は、ノード２００からダイジェストデータＤＢ又はエラー通知信号を受信し（ステップＳ６４）、エラー通知の有無を確認する（ステップＳ６５）。エラー通知があった場合は、ファイルＦＡをノード２００に送信する（ステップＳ６６）。この場合、ノード２００において、ファイルＦＡを受信し（ステップＳ８５）、受信したファイルＦＡをファイルＦＢとして蓄積装置２０１に書き込み（ステップＳ８６）、ファイルＦＢのダイジェストデータＤＢを生成した後、ダイジェストデータＤＢを蓄積装置２０１に書き込み（ステップＳ８７）、処理を終了する。
【００９３】
一方、エラー通知がなかった場合、すなわちダイジェストデータＤＢを受信した場合、ダイジェストデータ処理部１２２は、ダイジェストデータＤＡとＤＢとを比較し、ブロックサイズ又はブロックのダイジェスト値が相違する全てのブロック番号の情報を含む相違ブロック番号リストを作成し（ステップＳ６７）、これをブロックデータ処理部１２１に渡す。
【００９４】
ブロックデータ処理部１２１は、相違ブロックが存在するかを確認し（ステップＳ６８）、相違ブロックが存在する場合は、相違ブロック番号リストから相違ブロック番号情報を取得して、ファイル入出力部１３１を介してファイルＦＡの相違ブロック番号に対応するアドレスを読み出し（ステップＳ６９）、相違ブロックデータにブロックサイズ及びブロック番号を示すデータを付与して、通信部１３２を介してノード２００に送信する（ステップＳ７０）。通信部１３２は、１つのブロックデータを送信したらブロック番号リストから転送したブロックデータに係るブロックの番号データを消去することで、未送信ブロックデータを管理する（ステップＳ７１）。
【００９５】
全ての相違ブロックデータの送信を完了すると、通信部１３２は送信完了通知を通信部２２２に送信して処理を終了する（ステップＳ７２）。ステップＳ６７において、相違ブロックが存在しない場合は、通信部１３２は送信完了通知だけを通信部２２２に送信して処理を終了する。
【００９６】
ノード２００においてファイル再構成部２１１は、ノード１００から相違ブロックデータ又は送信完了通知を受信し（ステップＳ８８）、送信完了通知の受信の有無を確認する（ステップＳ８９）。送信完了通知を受信していない場合、ファイル再構成部２１１は、ファイル入出力部２２１を介して相違ブロック番号に対応するファイルＦＢのアドレスに、受信した相違ブロックデータを上書きし（ステップＳ９０）、ファイルＦＢを更新する。同時に、ファイル再構成部２１１は、ダイジェストデータ処理部２１２にも受信した相違ブロックデータを渡す。なお、ステップＳ８７においてファイルＦＢを更新するとき、ノード１００から転送された相違ブロックのブロックサイズとそのブロック番号に対応するファイルＦＢのブロックサイズとが全て同じ場合は、単に相違ブロックデータをファイルＦＢに上書きすればよいので、ブロックサイズが互いに異なる場合よりも高速にファイルを同期することができる。
【００９７】
ダイジェストデータ処理部２１２は、受信した全ての相違ブロックデータについてダイジェスト値を計算し（ステップＳ９１）、ダイジェストデータＤＢにおける相違ブロックのブロックサイズを示すデータとブロックのダイジェスト値とを更新し、ファイル入出力部２２１を介して蓄積装置２０１に記録することにより、ダイジェストデータＤＢを更新する（ステップＳ９２）。
【００９８】
次に、図６及び図９〜図１１に基づいて、ＩＰネットワーク１１上におけるデータ通信の具体例を示す。
【００９９】
まず、図９に基づき、ブロックデータの置換のみによりファイルの同期を行う際の一例を説明する。説明を簡単にするため、同期対象のファイルＦＡ及びＦＢは共にブロックサイズ＝Ｌの４ブロックで構成され、同期前のダイジェストデータＤＡ及びＤＢが含むダイジェスト値は、それぞれ、ブロック番号（０、１、２、３）に対して（Ｄ０、Ｄ４、Ｄ２、Ｄ５）及び（Ｄ０、Ｄ１、Ｄ２、Ｄ３）とする。
【０１００】
図９において、ノード１００がノード２００にファイルＦＢのダイジェストデータＤＢを要求すると、ノード２００の蓄積装置２０１（図６参照）にはファイルＦＢは存在するので、ノード２００は、ダイジェストデータＤＢをノード１００に送信する。
【０１０１】
ノード１００側では、ダイジェストデータＤＡとＤＢとを比較すると、ブロック番号１及び３のダイジェスト値がノード２００におけるものと相違していることが分かる。ノード１００は、相違ブロックリストにブロック番号１及び３を示す情報を登録し、ブロック番号１及び３の相違ブロックデータをノード２００に順次送信する。このとき、相違ブロックデータには、ブロック番号及びブロックサイズを示すデータが相違ブロックデータ毎に付与される。
【０１０２】
ノード２００は、ブロックデータを正しく受信するとその旨を、そうでなければ正しく受信できなかった旨を、ブロックデータ毎にノード１００に通知する。ノード１００は、全ての相違ブロックの転送を完了したら、送信終了通知をノード２００に送信する。その結果、ノード２００において、ファイルＦＢのブロック番号１及び３のブロックデータ、ダイジェスト値が新たな値に置換され、ファイルＦＢがファイルＦＡに同期することとなる。
【０１０３】
次に、図１０に基づき、ブロックデータの挿入を伴うファイルの同期を行う際の一例を説明する。説明を簡単にするため、同期元のファイルＦＡはブロックサイズ＝Ｌの４ブロック、同期先のファイルＦＢはブロックサイズ＝Ｌの３ブロックで構成されるものとする。また、同期前おいて、ダイジェストデータＤＡが含むダイジェスト値はブロック番号（０、１、２、３）に対して（Ｄ０、Ｄ３、Ｄ１、Ｄ２）、ダイジェストデータＤＢが含むダイジェスト値はブロック番号（０、１、２）に対して（Ｄ０、Ｄ１、Ｄ２）とする。
【０１０４】
図１０において、ノード１００がノード２００にファイルＦＢのダイジェストデータＤＢを要求すると、ノード２００の蓄積装置２０１（図６参照）にはファイルＦＢは存在するので、ノード２００は、ダイジェストデータＤＢをノード１００に送信する。
【０１０５】
ノード１００側では、ダイジェストデータＤＡとＤＢとの比較により、ファイルＦＢにおけるブロック番号０のブロックデータとブロック番号１のブロックデータとの間に１ブロック分のデータが挿入されたものがファイルＦＡであることが分かる。
【０１０６】
ノード１００は、相違ブロックリストにブロック番号１を示す情報と、ファイルＦＡにおけるブロック番号１のブロックデータがブロック番号０とブロック番号２との間に挿入されたものであることを示す情報とを登録する。その後、ファイルＦＢのブロック番号０のブロックデータとブロック番号１のブロックデータとの間に１ブロック分のブロックデータを挿入する指示信号をノード２００に送信する。ノード２００は、この指示信号を正常に受信した場合、その旨を示す信号をノード１００に返す。
【０１０７】
ノード１００は、ブロック番号１の相違ブロックデータをノード２００に送信する。このとき、相違ブロックデータには、ブロック番号及びブロックサイズを示すデータと、挿入されるブロック番号１のブロックの位置データとが付与される。ノード２００は、これらのデータを正常に受信した場合、その旨を示す信号をノード１００に返す。ノード１００は、これらのデータの転送を完了したら、送信終了通知をノード２００に送信する。その結果、ノード２００において、ファイルＦＢのブロック番号０のブロックデータとブロック番号１のブロックデータとの間に新たなブロックデータとそのダイジェスト値とが挿入され、ファイルＦＢがファイルＦＡに同期することとなる。
【０１０８】
次に、図１１に基づき、ブロックデータの削除を伴うファイルの同期を行う際の一例を説明する。説明を簡単にするため、同期元のファイルＦＡはブロックサイズ＝Ｌの３ブロック、同期先のファイルＦＢはブロックサイズ＝Ｌの４ブロックで構成されるものとする。また、同期前おいて、ダイジェストデータＤＡが含むダイジェスト値はブロック番号（０、１、２）に対して（Ｄ０、Ｄ２、Ｄ３）、ダイジェストデータＤＢが含むダイジェスト値はブロック番号（０、１、２、３）に対して（Ｄ０、Ｄ１、Ｄ２、Ｄ３）とする。
【０１０９】
図１１において、ノード１００がノード２００にファイルＦＢのダイジェストデータＤＢを要求すると、ノード２００の蓄積装置２０１（図６参照）にはファイルＦＢは存在するので、ノード２００は、ダイジェストデータＤＢをノード１００に送信する。
【０１１０】
ノード１００側では、ダイジェストデータＤＡとＤＢとの比較により、ファイルＦＢにおけるブロック番号０のブロックデータとブロック番号１のブロックデータとの間で１ブロック分のデータが削除されたものがファイルＦＡであることが分かる。
【０１１１】
ノード１００は、ファイルＦＡが、ファイルＦＢにおけるブロック番号１のブロックが削除されたものであることを示す情報を相違ブロックリストに登録する。その後、ファイルＦＢのブロック番号０のブロックデータとブロック番号２のブロックデータとの間の１ブロックを削除する指示信号をノード２００に送信する。ノード２００は、この指示信号を正常に受信した場合、ファイルＦＢのブロック番号０のブロックデータとブロック番号２のブロックデータとの間の１ブロックデータを削除すると共に、その旨を示す信号をノード１００に返す。
【０１１２】
ノード１００は、この信号を受信完了したら、送信終了通知をノード２００に送信する。その結果、ノード２００において、ファイルＦＢのブロック番号０のブロックデータとブロック番号２のブロックデータとの間のブロックデータ及びそのダイジェスト値とが削除され、ファイルＦＢがファイルＦＡに同期することとなる。
【０１１３】
なお、図９〜図１１を用いた説明では、説明を簡単にするため、１箇所におけるブロックデータの置換、挿入及び削除について個別に説明したが、複数箇所の変更を伴う同期であっても、前述したブロックデータの置換、挿入及び削除を組み合わせることにより実現することができる。また、ブロックデータの挿入及び削除を含む場合における相違ブロックを特定する方法として、例えば、文書比較の問題を解くアルゴリズムとしての、最長共通部分（LCS: Longest Common Subsequence）を求める手法や、最小エディト距離（SED: Shortest Edit Distance）を求める手法を用いることができる。さらに、これらの検索効率を改善する手法として、文献「EUGENE W. MYERS, "An O(ND) Difference Algorithm and Its variations", Algorithmixa, 1 (1986),pp.251-266」に記載された文書比較機能アルゴリズムを用いることができる。ただし、相違ブロックの特定に時間がかかると、ファイルを高速に同期させるという目的に合わないため、予めタイムアウトを設定しておき、相違ブロックの特定時間がそのタイムアウトを越えた場合はその時点で相違ブロック特定処理を中断し、同一ブロックと判定されなかった全てのブロックを相違ブロックとみなすなどの対処が必要である。
【０１１４】
また、前述の実施の形態では、アプリケーションであるファイル同期アプリ部１２０及び２１０がダイジェストデータの作成を行う例を挙げて説明したが、ファイルシステム（例えばＯＳ部１３０及び２２０）にダイジェストデータの作成を行わせる場合は、アプリケーション側にダイジェストデータの読み出し機能及び通信の機能を残し、その他の機能をファイルシステム側に持たせ、ファイルシステムがダイジェストデータを例えばメタデータとして扱う構成とすればよい。
【０１１５】
例えば、図６において、ノード２００のファイル再構成部２１１がファイルＦＡの相違ブロックアドレス及び相違ブロックデータをダイジェストデータ処理部２１２にも渡しているが、ファイルシステムがダイジェストデータを作成する場合は、相違ブロックアドレス及び相違ブロックデータをダイジェストデータ処理部２１２に送る必要はなくなる。同様に、図８における相違ブロックデータのダイジェスト値の計算（ステップＳ８８）のステップと、ダイジェストデータＤＢの更新（ステップＳ８９）のステップはファイルシステムが行うので不要となる。
【０１１６】
ファイルシステムがダイジェストデータの作成を行う構成では、本発明に係るブロック仮想分割手段、相違箇所特定部及びファイル同期部が、ファイルシステムのプログラムに実装されることとなる。
【０１１７】
以上のように、本実施の形態におけるファイル同期装置１０によれば、ダイジェストデータＤＡとダイジェストデータＤＢとの比較によってファイルＦＡとファイルＦＢとの相違箇所を特定するダイジェストデータ処理部１２２と、相違ブロックデータに基づき、蓄積装置２０１が記憶したファイルＦＢを蓄積装置１０２が記憶したファイルＦＡに同期させるファイル再構成部２１１とを備える構成としたので、特に大きなサイズのファイル、例えば映像、音声等のコンテンツデータのようなファイルに対し、従来よりも高速にファイルを同期させることができる。
【０１１８】
また、本実施の形態におけるファイル同期装置１０によれば、ユーザの指示により、２つのファイルを、相違箇所のデータ量にほぼ比例した時間で同期させることが可能となる。したがって、相違箇所がファイルサイズに比べて非常に少ない２つのファイルであれば、ファイル全体を上書きする方法と比べて高速に同期させることが可能となる。特に、その２つのファイルが別々のホストに記録されており、さらにそれらのホストを結ぶ通信路の転送速度が遅い場合、又はファイルの読み書きの速度が遅い場合には、さらに有効な方法である。
【０１１９】
また、本実施の形態におけるファイル同期装置１０によれば、相違箇所が全くない２つのファイルを対象とする場合でも次のような効果が得られる。すなわち、本実施の形態におけるファイル同期装置１０により、相違箇所が全くない２つのファイルに対してファイルを同期させようとする操作を行うと、相違箇所を示すデータは空になるため、２つのファイルが同一であることを高速に確認することができる。したがって、本実施の形態におけるファイル同期装置１０は、相違箇所がファイルサイズに比べて非常に少ない２つのファイルに対する同期の指示を２回連続して行えば、２つのファイルを高速に同期させてから、２つのファイルが本当に同じ内容になったかを高速に確認することができる。
【０１２０】
なお、前述の実施の形態において、ノード１００が相違箇所特定部としてのファイル同期アプリ部１２０を備え（図６参照）、ファイル同期アプリ部１２０がダイジェストデータＤＡとＤＢとを比較する構成を例に挙げて説明したが、本発明はこれに限定されるものではなく、例えば、相違箇所特定部をノード１００及び２００の少なくとも一方が備える構成、又は、ノード１００及び２００とは別の装置が備える構成等でもよい。
【０１２１】
例えば、ノード２００が相違箇所特定部を備え、この相違箇所特定部がＩＰネットワーク１１を介してユーザＩＦ部１０１からの同期指示の信号を受信した場合、ノード１００からダイジェストデータＤＡを受信し、受信したダイジェストデータＤＡと、蓄積装置２０１から読み出したダイジェストデータＤＢとを比較する構成とすることもできる。この構成によれば、ノード１００がノード２００よりもデータ処理能力が低い場合や、ノード１００に負荷が集中しやすい場合（例えばノード１００がサーバである場合）等においても、ファイルの比較を短時間で行うことができるという効果が得られる。
【０１２２】
また、例えば、ノード１００及び２００とは別に、相違箇所特定部を備えた専用の装置を設ける構成とすることにより、ノード１００及び２００のデータ処理能力や負荷状態に関わらず、ファイルの比較を短時間で行うことができるという効果が得られる。
【０１２３】
また、前述の実施の形態において、本発明に係るファイル同期部を構成するファイル同期アプリ部２１０を、同期先のファイルが記録された側のノード２００に設ける構成を例に挙げて説明したが、本発明はこれに限定されるものではない。例えば、本発明に係るファイル同期部を、同期元のファイルが記憶されたノード１００に設けてネットワークＩＦ部１０３及び２０２を介してファイルＦＢをファイルＦＡに同期させる構成としてもよい。また、本発明に係るファイル同期部を、ノード１００及び２００とは別の装置が備える構成としてもよい。
【０１２４】
また、前述の実施の形態において、ユーザＩＦ部１０１が同期元のノードであるノード１００に対して同期指示を行ってファイルを同期させる構成、すなわち、ノード１００が相違ブロックデータをノード２００にアップロードして同期させる構成を例に挙げて説明したが、本発明はこれに限定されるものではない。例えば、ユーザＩＦ部１０１が同期先のノードであるノード２００に対して同期指示を行ってファイルを同期させる構成、すなわち、ノード２００が相違ブロックデータをノード１００からダウンロードして同期させる構成とすることもできる。
【産業上の利用可能性】
【０１２５】
以上のように、本発明に係るファイル同期装置、ファイル同期方法及びファイル同期プログラムは、従来よりも高速にファイルを同期させることができるという効果を有し、例えば２つの記憶領域にそれぞれ記憶された映像、音声等のコンテンツデータのようなサイズの大きいファイルを同期させるファイル同期装置、ファイル同期方法及びファイル同期プログラム等として有用である。
【図面の簡単な説明】
【０１２６】
【図１】本発明の一実施の形態におけるファイル同期装置の構成の概要を示すブロック図
【図２】本発明の一実施の形態におけるファイル同期装置のファイル編集アプリ部に係る構成を示すブロック図
【図３】本発明の一実施の形態におけるファイル同期装置のブロック分割部が行うブロック分割例を示す図  （ａ）ブロックサイズを固定長とした場合のブロック分割例を示す図  （ｂ）ブロックサイズを可変長とした場合のブロック分割例を示す図
【図４】本発明の一実施の形態におけるファイル同期装置のファイル保存に係る動作の概要を示すフローチャート
【図５】本発明の一実施の形態におけるファイル同期装置のファイル編集アプリ部に係る動作を示すフローチャート
【図６】本発明の一実施の形態におけるファイル同期装置のファイル同期アプリ部に係る構成を示すブロック図
【図７】本発明の一実施の形態におけるファイル同期装置のファイル同期アプリ部に係る動作の概要を示すフローチャート
【図８】本発明の一実施の形態におけるファイル同期装置のファイル同期アプリ部に係る動作において、図７に記載した動作を具体化した一例を示すフローチャート
【図９】本発明の一実施の形態におけるファイル同期装置のＩＰネットワーク上におけるデータ通信の説明図であって、ブロックデータの置換によりファイルの同期を行う際の一例を示す図
【図１０】本発明の一実施の形態におけるファイル同期装置のＩＰネットワーク上におけるデータ通信の説明図であって、ブロックデータの挿入によりファイルの同期を行う際の一例を示す図
【図１１】本発明の一実施の形態におけるファイル同期装置のＩＰネットワーク上におけるデータ通信の説明図であって、ブロックデータの削除によりファイルの同期を行う際の一例を示す図
【図１２】互いに異なる記憶領域に記憶されたファイルを同期させる形態を示す図
【図１３】従来のｒｓｙｎｃアルゴリズムに関する説明図
【符号の説明】
【０１２７】
１０  ファイル同期装置
１１  ＩＰネットワーク
１００  ノード（第１のノード）
１０１  ユーザＩＦ部
１０２  蓄積装置（第１の記憶手段）
１０３  ネットワークＩＦ部（第１の受信手段、第１の送信手段）
１１０  ファイル編集アプリ部
１１１  ファイル編集部
１１２  ブロック分割部（ブロック仮想分割手段、特徴データ取得手段）
１１３  ダイジェストデータ処理部
１２０  ファイル同期アプリ部（ファイル同期手段、相違箇所特定部）
１２１  ブロックデータ処理部
１２２  ダイジェストデータ処理部
１３０  ＯＳ部
１３１  ファイル入出力部
１３２  通信部
２００  ノード（第２のノード）
２０１  蓄積装置（第２の記憶手段）
２０２  ネットワークＩＦ部（第２の受信手段、第２の送信手段）
２１０  ファイル同期アプリ部（ファイル同期手段、ファイル同期部）
２１１  ファイル再構成部
２１２  ダイジェストデータ処理部
２２０  ＯＳ部
２２１  ファイル入出力部
２２２  通信部
【図１】
0005237661.tif 000002
【図２】
0005237661.tif 000003
【図３】
0005237661.tif 000004
【図４】
0005237661.tif 000005
【図５】
0005237661.tif 000006
【図６】
0005237661.tif 000007
【図７】
0005237661.tif 000008
【図８】
0005237661.tif 000009
【図９】
0005237661.tif 000010
【図１０】
0005237661.tif 000011
【図１１】
0005237661.tif 000012
【図１２】
0005237661.tif 000013
【図１３】
0005237661.tif 000014