http://www.parfiles.net


パリティ・ボリューム・セット 仕様書 1.0 [2001/10/14]

スティファン・ウェルスによる、最初の構想はトバイス・リーパーによる、 更なる提案とフォーマットの改良はキロイ・バロア、ウィレム・モンスウィ、そしてカール・ボーゲルによる

概要

以下の説明文はパリティ・ボリューム・セットと呼ばれるファイル形式について記述します。
パリティ・ボリューム・セットは与えられた数のファイルに対して RAID 風のパリティ・レコードを提供します。 このパリティ・レコードによって、セット内の消失したファイルを復元することができます。

例：
10個のデータ・ファイルがあるとします。

データ・ファイル

Foobar.d01
Foobar.d02
Foobar.d03
Foobar.d04
Foobar.d05
Foobar.d06
Foobar.d07
Foobar.d08
Foobar.d09
Foobar.d10


この仕様を使うプログラムで、これらのパリティ・ボリュームを計算することができます。

パリティ・ボリューム

Foobar.p01
Foobar.p02
Foobar.p03


パリティ・ボリュームはデータ・ファイルのデータのリード・ソロモン符号のチェックサムを含みます。 そのため、あるファイルが消失したり破損したならば、 残りのデータ・ファイルとパリティ・ボリュームからそれを再構築することができます。 どのパリティ・ボリュームによってでもこのセットのどのファイルでも再構築することができます。 ただ単に失われたファイルと同じ数のパリティ・ボリュームが必要なだけです。
例えば、上記の例で言うならば、Foobar.d03 が失われたとします。 そうすると、残りのデータ・ファイルとパリティ・ボリューム 1個を使って Foobar.d03 を復元することができます。 どのパリティ・ボリューム ( p01 / p02 / p03 ) かは関係ありません、どれでもいいのです・・・。
ファイルが 2個失われた場合は、パリティ・ボリュームが 2個必要です。 どのパリティ・ボリュームとかその組み合わせ ( p01 + p02 / p01 + p03 / p02 + p03 ) も関係ありません、 ただ単にその中の 2個必要なだけです。 ( それらは異ならなければいけません： Foobar.p01 をコピーして Foobar.p02 と名前を付け替えて、 それを Foobar.p01 と共に復元に使おうとしても、うまくいきません・・・ )

一般的な解説

パリティ・ボリューム・セットは二つの部分から構成されます。 最初のは .PAR ファイル (索引ファイル) です。
それはファイルに関する情報を含み、 ボリューム・セット内に「保存」されます：
・どのファイルがセット内に格納されれるか
・そのチェックサム ( MD5 )
・そのサイズ
・そのファイル名
・セットへの一般的なコメント

二番目のはパリティ・ボリューム・ファイルです。 それらは .P00、.P01、.P02・・・.PXX (訳注 1) と名付けられます。 ( .P99 の後は、.Q00・・・となります )

それらが含むのは：
・PAR ファイルと同じ情報 (コメント以外) と
・格納されたファイルの計算されたパリティ・データ

PAR ファイル仕様

( データは「インテル順序」で格納される )

開始位置：型 (サイズ)データ
0x00008バイト 識別文字
"PAR"\0

コメント：
・文字 "PAR" の後に null バイトが 5個続く
0x00088バイト整数 1個 バージョン番号
・バージョン番号は二つの部分で構成される：
下位 4バイト整数 ( ビット 0〜31 ) はバージョンです、$00010000 は v01.00
上位 4バイト整数 ( ビット 32〜63 ) は作成プログラムへの識別子です。 どのプログラムがパリティ・ボリューム・セットを作成したのかを見るために クライアントはそれを使うことができます。 もし、あなたのプログラムが作成元それ自体かどうかを知る必要があるなら、 これは便利かもしれません。 ( それがステータス記録内の所有者ビットを使うことができるかどうかを見るためにとか、 新しいバージョンが出たかどうかを知らしめるためとか・・・)
その値は "プログラム"-"バージョン"-"サブ・バージョン"-"サブ・サブ・バージョン" です。
"プログラム" の値は：
00 - 未定義
01 = Mirror
02 = PAR
例： Mirror 0.2.1 ならプログラム識別子は $01000201 になります。
0x001016バイト コントロール・ハッシュ
・0x0020 から始まって最後までのファイルの残りの MD5 ハッシュです。
・破損したファイルを探知する為に使います。
0x002016バイト セット・ハッシュ
・パリティ・ボリューム・セットのための識別子として使われます。
作り方：
バイト配列 ( 一次元で、サイズ = 使ったファイル数 * 16 ) を作ります。 そして、最初のファイルから始めて、 MD5 ハッシュを (MD5 16k ハッシュではなく) そこに配置します。 パリティ・データに含まれるファイル ( ステータス・ビット 0 = 1 ) だけを使います。 そして、この配列の MD5 ハッシュを計算します。
0x00308バイト整数 1個 ボリューム番号
・パリティ・ボリュームの番号
・PAR ファイルは 0
・.p01 は 1、.p02 は 2、.p03 は 3 などなど
0x00388バイト整数 1個 ファイル数
・パリティ・ボリューム・セットに格納されているファイルの数
( 入力されたデータ・ファイルのみ、パリティ・ボリュームは数えません。)
パリティ・データに格納されないけれど、 MD5 (訳注 2) チェックのためにファイル・リストには含まれるファイルも数えます。 なので、これはファイル・リストに入ってるファイルの数です。
0x00408バイト整数 1個 ファイル・リストの開始位置
・格納されたファイルのリストの開始位置
0x00488バイト整数 1個 ファイル・リストのサイズ
・ファイル・リストのバイト単位のサイズ
0x00508バイト整数 1個 データの開始位置
・データ領域の開始位置
0x00588バイト整数 1個 データのサイズ
・データ領域のバイト単位のサイズ
0x0060・・・ ファイル・リスト
・保存されているファイルのリストがここから始まります。 ・それはファイル・エントリーで構成されます。


ファイル・エントリーは次の形式です。

開始位置：型 (サイズ)データ
0x00008バイト整数 1個 エントリー・サイズ
・ファイル・リストのエントリーのバイト単位のサイズです。
・1番目から数えて、この記録も数えます。
0x00088バイト整数 1個 ステータス領域
・ステータス・フラグや番号のための 64ビット
・今の所、ビット 0 と 1 だけが使われています：
ビット 0 = 0、ファイルはパリティ・ボリューム・セットに保存されていません。
ビット 0 = 1、ファイルはパリティ・ボリューム・セットに保存されています。
ビット 1 = 0、ファイルはまだ検証されていません。
ビット 1 = 1、ファイルは検証されてました。
0x00108バイト整数 1個 サイズ
・格納されてるファイルのバイト単位のサイズ
0x001816バイト MD5 ハッシュ
・ファイル全域の MD5 ハッシュ
0x002816バイト 16k MD5 ハッシュ
・ファイルの先頭 16384バイトの MD5 ハッシュ
・ファイルが 16k よりも小さければ、存在するバイトの分だけが使われます。
0x00382バイト整数 X個 ファイル名
・ユニコードでの拡張子を含む完全なファイル名
( "Foobar.d01" )
・パスは許されません。
・終端の印はありません、 エントリー・サイズからサイズを逆算しなければいけません。 ( 文字数 = ( エントリー・サイズ - 0x38 ) / 2 )


ファイル・リストの後に、データ領域が始まります。
PAR ファイルでは、データ領域にはボリューム・セットのコメントを入れます。 コメントはユニコードで格納されて、制御文字も許されます。

PXX ファイルでは、データ領域にはチェックサム・データを入れます。
チェックサム・データの計算：
n 個のファイルがあって m 個のパリティ・データを作りたいとします。 そうすると、データ領域 D1〜Dn (訳注 3) を作って、 D1 はファイル 1 の最初のバイト、D2 はファイル 2 の最初のバイト、D3 はファイル 3 の最初のバイト・・・ Dn はファイル n の最初のバイトにします。 この領域に対して、m 個のパリティ・チェックサムの領域 C1〜Cm を作ります。 C1 は .p01 の最初のパリティ・バイトとして格納され、 C2 は .p02 の最初のパリティ・バイトとして格納され、 C3 は .p03 の最初のパリティ・バイトとして格納され・・・ Cm は .p0m の最初のパリティ・バイトとして格納されます。
そして、全てのファイルの二番目のバイトを処理して、更にまたと、 最も大きい入力されたファイルの最後に到達するまで続けます。 ファイルにバイトが残ってなければ、計算には 0 を使います。 したがって、パリティ・データのサイズは パリティ・ボリューム・セットに格納されてる最も大きいファイルのサイズになるでしょう。

チェックサムを計算するためには、リード・ソロモン符号アルゴリズムが使われます。 このアルゴリズムのプログラマー向けのいい解説が http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.html にあります。
その「wordsize」は 8ビットなので、バイト単位でだけ計算できます。 ( これによって ファイル + パリティ・ボリュームの数は 256 未満に制限されます。)

注釈：

どうして 16k MD5 ハッシュなのですか？
要求される機能の一つとして、 プログラムはたとえファイル名が変更されてもそのファイルを見つけ出そうとする、 というのがあります。 そうなので、プログラムが名前の変更のためにファイルを見つけることができなくても、 「検索」ボタンを押せば そのファイルを探し出す為にディレクトリー内の全てのファイルの MD5 ハッシュをチェックするかもしれません。 しかし、大きなファイルが大量にあると時間がかかります。 16k MD5 ハッシュを使えば、プログラムは各ファイルの最初の 16k をチェックするだけで済みます。 これはずっと速いでしょう。 もしもファイルを見つければ、確認する為だけに、完全なハッシュを作ることもできます・・・

どうしてステータス・フラグを保存するのですか？
もしかすると PAR ファイルはファイルのコメントとチェックサムを提供する為だけに使われるかもしれません。 そうするとファイルは PXX ボリュームには保存されません。

どうしてステータス・フラグをチェックするのですか？
そうすることで、あなたは関数を作ることができます、 そのようなプログラムは検証されたファイルをスキップします。 こうすることで同じセットの繰り返すチェックは速くなるでしょう。 ( QuickSFV のように )

実装上の注意

ファイル・リスト内に存在するファイルは 常にパリティ・データ内に格納されるわけではありません。 なので、いくつかの ( あるいは全ての ) ファイルは チェックサム管理のためにだけ存在したり、 PAR ファイル内のコメントのためにだけ存在することもありえます。 ( その場合、.SFV や .NFO の機能性だけが必要とされます・・・ )

保存されるファイルはどのような種類やサイズでも可能です。

ヘッダー内には格納されているパリティ・ボリュームに関する情報はありません。 そのため、プログラムは存在するパリティ・ボリュームを探してディレクトリーを探査しなくてはいけません。 それらはセット・ハッシュで識別されます。

ファイル・リスト内のエントリーの順序には明確な規則はありませんが、 ファイル名をアルファベット順 (訳注 4) に並び替えることを推奨します。

著作権

この説明書には著作権がありません。 紹介されてる原理、ファイル形式の仕様とその詳細は 誰でもどのような種類のソフトウェアででも無料で使えます。 ライセンス契約やその他の制限事項は無いでしょう。
あなたが公開、非公開、または共有されたソース、 公共所有、無料、有料、商用ソフトを書こうが、関係なく、 この仕様を使うことができます。
しかし、もしあなたが PAR / PXX ファイル形式を使ってそのフォーマットに変更を加えたいならば、 互換性を維持する為にここで彼らと議論する必要があります。

http://www.parfiles.net




訳注 1：説明ではこうなってますが、実際には .P01 から始まります。
訳注 2：原文では CRC ですが、実際には MD5 が使われるので変更してあります。
訳注 3：原文では D1〜Dm ですが、間違いっぽいので D1〜Dn と訂正してあります。
訳注 4：原文では昇順ですが、こういった方がわかりやすいので変えてます。

仕様書の日本語版は 澤田 豊 によります。 2009年 11月 17日