多くの構成管理システムと異なり、 Mercurial が基にしている概念は非常に単純なので、 Mercurial のプログラムが実際にどのように動作するのかを理解するのは簡単です。そのような知識は必要無いかもしれませんが、筆者は内情に関する “概念理解” が有用であると考えています。
筆者自身は、内情を理解することで、 Mercurial が安全性と効率に留意して設計されている、という確信を得ることができました。また、構成管理操作を行った際にソフトウェアがどのように機能するのかを、容易に覚えておけるのであれば、構成管理ツールの振る舞 いに驚かされる機会が減る、という点も非常に重要です。
この章では、最初に Mercurial の設計における中核的な概念について説明した上で、実装における興味深い点に関する詳細を幾つか取り上げようと思います。
ファイルの変更を追跡する場合、 Mercurial はファイルの履歴を filelog と呼ばれるメタデータオブジェクト形式で保存します。 filelogに記録される個々の要素は、追跡対象ファイルの、とあるリビジョンを再現するのに十分な情報を保持しています。 filelogは .hg/store/data ディレクトリ配下にファイルとして保存されており、履歴情報と、 Mercurial のリビジョン検索を補助するインデックスの、2種類の情報を保持しています。
サイズが大きかったり変更履歴の多いファイルの場合、 filelog を履歴情報(拡張子 “.d”)とインデックス(拡張子 “.i”)の2つに分離して保存されます。変更履歴がそれほど無い小さなファイルの場合、履歴情報とインデックスは “.i” 拡張子を持つ単一のファイルに保存されます。作業領域ディレクトリ中のファイルと、その変更履歴を追跡するためのリポジトリ中の filelog ファイルの対応を、図 4.1に示します。
追跡対象ファイルの情報をまとめるために、 Mercurial は manifest と呼ばれる構造を使用しています。 manifest に記録される個々の 要素は、当該チェンジセットにおけるファイルの一覧や、各ファイルのリビジョン、幾つかのファイルのメタデータといった、個々の チェンジセットごとのファイルに関する情報を保持しています。
changelog は、チェンジセットのコミット主や、コミット時のログメッセージ、その他チェンジセットに関する幾つかの情報や、 manifest のリビジョンといった、個々のチェンジセットに関する情報を保持しています。
changelog、 manifest ないし filelog における個々のリビジョンは、直接の親リビジョン(マージを行ったリビジョンの場合は、マージ 対象となった2つの親リビジョン)への参照を保持しています。今述べたように、各構造にまたがった関連性をもち、それらは必然的に 階層構造を持っています。
リポジトリ中の全てのチェンジセットに関して、 changelog には厳密に1つのリビジョンが保存されます。 changelog における各リ ビジョンは、 manifest 中のリビジョンへの参照を保持しています。 manifest 中の各リビジョンは、チェンジセットが生成された際の 各ファイルのリビジョンに対応する filelog 中のリビジョンへの参照を保持しています。この関連性を図 4.2に示しま す。
図からもわかるように、 changelog、 manifest および filelog が保持するリビジョン情報間の関係は、必ずしも “1対1” というわけではありません。2つのチェンジセットの間で manifest が変更されていない場合、それらのチェンジセットに対応する changelog 要素は、 manifest 中の同じリビジョンを参照します。2つのチェンジセットの間で Mercurial が追跡するファイルが変 更されていない場合、それらのチェンジセットに対応する manifest 要素は、 filelog 中の同じリビジョンを参照しま す。
changelog、 manifest および filelog は、 revlog と呼ばれる同じ構造により構成されています。
revlog は差分手法という仕組みを使用して、リビジョン情報を効率的に格納しています。差分手法では、ファイルの各リビ ジョンごとに完全な複製を保持する代わりに、旧リビジョンから新リビジョンへの変形に必要な情報を保持します。多 くのファイルでのデータ格納において、差分手法は一般的に完全な複製の場合の数パーセント程度のサイズになりま す。
旧式の構成管理システムでは、テキスト形式のファイルでしか差分手法が適用できないものもあります。それらのシステムにおけるバイ ナリファイルの格納は、完全なスナップショットか、テキスト表現形式への変換によって行われますが、これらは共に不経済な手法です。任 意のバイナリデータを含むファイルであっても、 Mercurial は差分を効率的に扱うことができますので、テキストを特別扱いする必要はあり ません1 。
Mercurial は revlog の末尾にデータを追加するだけで、書き込まれた後からファイルの一部を改変するようなことは行いません。既存 データの改変を必要とする仕組みと比較した場合、この手法は堅牢且つ効率的です。
それに加えて、 Mercurial は複数のファイルにまたがった全ての書き込みを、単一のトランザクションの一部として扱います。トラ ンザクションは不可分なものとして扱われますので、トランザクション全体が成功すれば結果の全てが利用者に見えるようになります が、トランザクションの一部でも失敗した場合には、全ての書き込み操作は取り消されます。一方はデータの読み込みを行い他 方はデータの書き出しを行うような、2つの Mercurial プロセスを同時に実行した場合でも、この不可分保証によ り、読み込みを混乱させるような部分的な書き込みデータを、データ読み込み側のプロセスが読み込むことはありませ ん2 。
Mercurial がファイルへの追加しか行わないことが、トランザクションの不可分性保証の提供を容易にしています。トランザクショ ン保証が容易である程、それが正しく機能していることを確信できる筈です。
初期の構成管理システムが共に陥っていた非効率な復旧問題の落とし穴を、 Mercurial は上手に回避しています。殆どの構成管理シス テムは、 “スナップショット” に対する変更の追加的な連続として、リビジョンの内容を保持していました。この手法の場合、特定のリ ビジョンを再構築するには、最初にスナップショットを読み込み、続いて対象リビジョンとの間の全ての差分データを読み込む必要があ ります。ファイルの履歴が積み重なるほど、差分データを読み込まなければ成らないリビジョンが増加し、特定のリビジョンの再構築に 時間が必要となります。
Mercurial がこの問題の解決に使用している手法は、簡単なものですが効果的です。前回のスナップショット作成時点から、固定された閾値を超えて差分情報が蓄積された際には、差分情報の蓄積ではなく、新たなスナップショット(勿論圧縮は行います)を保存す る、というものです。この手法は、任意のリビジョンにおけるファイルを素早く再構築できます。この手法は非常に有効であるため、他 の幾つかの構成管理システムにも取り込まれています。
図 4.3の概要が示すように、 Mercurial は、 revlog のインデックスファイルにおける各要素に、特定のリビジョンの再構築の際に 読み込みが必要とされる、データファイル中の要素の範囲を格納します。
動画圧縮を熟知しているか、ケーブルないし衛星によるデジタルテレビ配信を視聴したことがあるならば、たいていの動画圧縮形式にお いて各動画フレームが、先行するフレームとの差分で保持されていることをご存知かもしれません。加えてそれらの形式では、圧縮率を 向上させるために “非可逆” 圧縮手法を用いていますので、フレーム間差分の数に応じて視覚的エラーが蓄積されま す。
動画配信の場合、時折の信号異常による “欠落” が有り得ますし、可逆圧縮過程により生じる誤差の蓄積を制限する必要もあるた め、動画圧縮側では定期的に完全なフレーム(“キーフレーム” と呼ばれます)を圧縮形式の中に挿入します。これは動画信号が中断さ れても、次のキーフレームの到着時点からの再開が可能であることを意味します。符号化エラーの蓄積も、個々のキーフレームでクリア されます。
差分ないしスナップショット情報のデータに対して、 revlog 要素は暗号化に用いられるハッシュ値を計算して保持 しています。これにより、リビジョンに関する情報の偽造を困難にすると同時に、不慮の破損の検出が容易になりま す。
ハッシュ値の算出は、単なる破損の検出以上のものをもたらします。ハッシュ値は各リビジョンの識別子として使用されます。 Mercurial のエンドユーザとして目にするチェンジセット識別子のハッシュ値は、 changelog のリビジョンに由来する値で す。 filelog や manifest でもハッシュ値を使用していますが、 Mercurial ではこれらは舞台裏のみで使用されていま す。
特定リビジョンのファイルを再構築する場合や、他のリポジトリからチェンジセットを取り込んだ場合、 Mercurial はハッシュ値が 正しいことを確認します。一貫性に問題があることが検出された場合、警告を発した上で、進行中の全ての処理を停止しま す。
Mercurial が定期的に差し込んでいるスナップショットは、特定リビジョンの再構築の際の効率に加えて、部分的なデー タの破損に対する堅牢性をもたらしてます。ハードウェアエラーやシステムのバグによって、 revlog が部分的に破 損した場合、破損を免れた revlog のデータから、破損した部位の前後共に、一部(あるいは殆どの)リビジョンを 復旧することが可能です。差分のみを保持するモデルを採用する構成管理システムでは、このようなことはできませ ん。
全ての Mercurial の revlog 要素は、通常は親と言われる直前のリビジョンの識別子を保持しています。実際には、各 revlog 要素は1つで はなく2つの親の情報を保持できます。 Mercurial は “空識別子” (null ID)と呼ばれる特別なハッシュ値を使って、 “親不在” を表現 します3 。 このハッシュ値は単純に 0 が連続した文字列です。
revlog の概念図を図 4.4に見ることができます。 filelog や manifest、 changelog の全てが同じ構造を持っており、個々の要素が保 持している、差分やスナップショットといったデータの種別が異なるだけです。
revlog における最初のリビジョン(図における底位置のリビジョン)は、2つの親リビジョン格納領域の両方に空識別子を保持して います。 “通常の” リビジョンでは、第1親の格納領域には親リビジョンの識別子が、第2親の格納領域には空識別子が格納され、親リ ビジョンが1つしかないことを表します。親リビジョンの識別子として同じ識別子を格納するリビジョン同士は、互いにブランチとなり ます。ブランチをマージしたリビジョンは、統合された両方のリビジョンの識別子を親リビジョンの識別子として格納しま す。
Mercurial は、リポジトリで構成管理されているファイルの、特定のリビジョンにおけるスナップショットを作業領域ディレクトリに保 持します。
作業領域ディレクトリは、どのリビジョンのスナップショットを保持しているのかを “知っています”。作業領域ディレクトリを特定 のリビジョンで更新しようとした場合、 Mercurial は (1) 相応しいリビジョンの manifest を参照し、 (2) 当該リビジョンのコミット時 点での管理対象ファイルを特定し、 (3) 作業領域ディレクトリ中のファイルが保持すべき内容を決定します。その上で、当該 チェンジセットのコミット時点と同じ内容を持つように、作業領域ディレクトリ中に各ファイルの複製を再生成しま す。
dirstate 形式には、作業領域ディレクトリがどのチェンジセットで更新されているかとか、作業領域で Mercurial によ り構成管理されているファイルの一覧など、作業領域ディレクトリに関する Mercurial の管理情報が格納されていま す。
個々のリビジョンに関する revlog 要素は、2つの親リビジョン識別子を格納する領域を持っていますので、通常のリビジョン(1 つの親リビジョンだけを参照)も、2つのリビジョンをマージするリビジョンも表現可能ですが、 dirstate 形式も2つの親リビジョン 識別子を格納する領域を持っています。“hg update” コマンドを実行した際には、指定したチェンジセットは “第1親” (first parent)として保持され、第2親は空識別子を保持します。チェンジセットとの“hg merge” を行った際に は、 dirstate 形式が保持する第1親は変化しませんが、第2親は“hg merge” コマンドに指定されたチェンジセッ トに設定されます。“hg parents” コマンドにより、 dirstate 形式が保持する親リビジョンの識別子を表示できま す。
dirstate 形式が親リビジョン情報を保持するのは、何も覚え書きのためだけではありません。 Mercurial は dirstate 形式の持つ親リビ ジョン情報を、コミットの際の新規チェンジセットの親チェンジセットとして使用します。
図 4.5は、1つの親チェンジセットのみを持つ、通常の作業領域ディレクトリを表しています。図における作業領域ディレクトリの親チェンジセットは、リポジトリにおける最新で且つ子を持たないチェンジセットですので、 tip と呼ばれます。
作業領域ディレクトリそのものを、 “コミットしようとしているチェンジセット” と捉えるとわかりやすいでしょう。 Mercurial に対して追加/削除/改名ないし複製を指示したファイルは、既に Mercurial により構成管理されているファイルへの変更と同様に、そのチェンジセットに反映されます。その新たなチェンジセットには、作業領域ディレクトリと同じ親チェンジセットが設定されま す。
コミットが完了したなら、 Mercurial や作業領域ディレクトリの親チェンジセットの情報を更新します。第1親にはコミットにより 新たに生成されたチェンジセットの識別子が設定され、第2親には空識別子が設定されます。コミット後の模式図を、図 4.6に示しま す。 Mercurial はコミットの際に、作業領域ディレクトリ中のファイルには一切触れず、単に dirstate の親チェンジセット情報を書き 換えるだけです。
現時点での tip 以外のチェンジセットでの作業領域ディレクトリの更新は、良くあることです。例えば、先週火曜日時点でのプロジェク トの状態を調べたり、どのチェンジセットがバグを持ち込んだのかを調べる、といった状況です。このような状況での自然な行為は、作 業領域ディレクトリを希望のチェンジセットで更新し、当該チェンジセットをコミットした時点でのファイルの内容を、作業 領域ディレクトリ中のファイルを参照して確認する、というものでしょう。この行為による影響を、図 4.7に示しま す。
作業領域ディレクトリを以前のチェンジセットで更新した場合、何らかの変更を行ってコミットしたなら、 Mercurial はどのように振舞うのでしょうか? Mercurial はこれまでに説明してきた場合と同じように振舞います。作業領域ディレクトリの親チェンジセットが、新規に作成されるチェンジセットの親になります。新規作成されるチェンジセットは子を持たず、よって新たな tip チェンジセット となります。コミットの結果、リポジトリには子を持たないチェンジセットが2つ存在し、これらは head と呼ばれます。この状況を 図 4.8 に示します。
括弧付きで「間違い」と述べたのは、この状況を修復するのに必要なことが、“hg merge” してから“hg commit” すれば良いだけだからです。言い換えるなら、このよ うなケースは全然深刻な状況ではない、ということです。 Mercurial に慣れていない人 はビックリするかもしれませんが…。このような事態を回避する別の方法や、初心者に とって意外に感じるこのような振る舞いを Mercurial がとる理由について、後ほど説明 したいと思います。
“hg merge” コマンド実行の際に、 Mercurial は作業領域ディレクトリの第1親は変更せずに、第2親をマージ対象として指定した チェンジセットに変更します。この様子を図 4.9に示します。
2つのチェンジセットにおいて管理されるファイルをマージするため、 Mercurial は作業領域ディレクトリを変更します。多少簡便化して説明すると、両方のチェンジセットの manifest に含まれる全てのファイルに対して、概ね以下のようにマージ処理が実施されます。
他にも細かい話 — 特にマージに関しては細かい話が沢山あります — がありますが、マージに関連する一般的な振る舞いの種類はこ の程度です。ご覧の様に、殆どの状況が全く自動的に処理されますし、実際のマージでも殆どの場合、衝突解消のための対話的な入力無 しに自動的に完了します。
マージ後のコミットの際に処理される事柄を考える場合は、先にも述べましたが、作業領域ディレクトリを “コミットしようとして いるチェンジセット” と捉えるとわかりやすいでしょう。“hg merge” コマンドが完了した後の作業領域ディレクトリは、親 チェンジセットを2つ持ち、コミットによって生成される新たなチェンジセットは、これらを親チェンジセットとしま す。
Mercurial では繰り返しマージすることが可能ですが、 Mercurial はりビジョンおよび作業領域ディレクトリの両方に対して、一度 に2つの親リビジョンしか追跡できないため、個々のマージの都度コミットする必要があります。複数のチェンジセットの一括マージ は技術的には可能でしょうが、ユーザが混乱したり、ひどく乱雑なマージが行われるであろうことは目に見えていま す。
これまでの節で、 Mercurial が信頼性と性能へ注意深く配慮を払っていることを説明するために、設計における最も重要な側面の幾つ かに焦点を当ててきました。しかし、詳細事項への配慮は、これだけに留まりません。 Mercurial の構成において筆者の個人的な興味 をそそる側面が多数あります。これまでの “big ticket” な側面とは別に、いくつかを選んで詳細を説明しようと思いま すので、これらに興味があれば、良い設計のシステムの考案の際に有用な、より良い発想を得ることができるでしょ う。
Mercurial はスナップショットと差分のそれぞれに対して、圧縮が有効である場合には圧縮形式で保存します。 Mercurial は常にスナッ プショットないし差分の圧縮を試行しますが、非圧縮な状態よりもサイズが小さい場合に限り、圧縮形式での保存を行いま す。
このことは、例えば zip アーカイブや JPEG 画像のように、元々圧縮形式の内容を持つファイルの格納の際に、 Mercurial が “適切な処置 ” を行うこと意味します。これらのファイルは Mercurial による2度目の圧縮の際には、最初のサイズよりも大きくなるのが一般的ですので、 Mercurial は zip や JPEG ファイルをそのまま保存します。
圧縮形式のファイルのリビジョン間の差分は、一般的にはスナップショットよりも大きくなりますので、この場合でも Mercurial は “適切な処置” を行います。ファイルのスナップショットそのものを保存する場合の許容範囲を、差分情報のサイズが超えることが判明 した場合、 Mercurial はスナップショットを保存しますので、繰り返しになりますが、差分のみを保持するモデルよりもディスク容量 が節約できます。
Mercurial はディスクへの履歴保存の際に、性能に対する圧縮率がそこそこ良好でバランスの取れている “収縮” (deflate)圧縮アルゴ リズム(著名な zip アーカイブ形式が同等のものを使用しています)を使用しています。しかし、ネットワーク越しのデータ転送の際 には、 Mercurial は履歴データを圧縮しません。
ネットワーク接続が HTTP 経由の場合、 Mercurial はデータ通信の経路全体を、より良い圧縮率を得られる圧縮アルゴリズム (bzip2 圧縮として広く使用されている Burrows-Wheeler アルゴリズム)で再圧縮します。リビジョン情報個別の圧縮ではな く、bzip2 アルゴリズムと通信経路全体の圧縮という組み合わせにすることで、転送データ量を大幅に低減することができますので、 殆ど全てのネットワーク形態において良好な性能を発揮できます。
(ssh での接続の場合、ssh 自身が圧縮を行うことができるので、 Mercurial は接続経路の再圧縮を行いません 4)
不完全な書き込み内容が利用されることのないように保証する上では、ファイルへの追加書き込みだけが全てではありません。も う一度、図 4.2を見ていただければわかるように、 changelog 中のリビジョン要素は manifest 中のリビジョン要素 を、 manifest 中のリビジョン要素は filelog 中のリビジョン要素を指しています。この階層構造は意図的なものなので す。
データ書き込みの際には、 filelog および manifest への書き込みでトランザクションが開始され、これらへの書き込みが完了するま では changelog への書き込みは行われません。読み込みの際には、 changelog を起点として manifest、 filelog の順序で読み込みを行 います。
changelog への書き込みに先立って、常に filelog および manifest への書き込みが完了しているので、 changelog からの不 完全な manifest への参照を読み込むことも、 manifest からの不完全な filelog への参照を読み込むこともありませ ん。
読み書き手順と不可分性保証により、例え読み込みの最中に書き込みが行われるとしても、 Mercurial は読み込みにおけるリポジトリ の排他を必要としません。この特性は大規模化の際に非常に影響があります。任意の数の Mercurial プロセスが、書き出しプロセスの 有無に関わらず、リポジトリに対して同時読み出しを安全に行うことができます。
読み出しにおける排他不要の特性は、多ユーザシステム上でリポジトリを公開している際に、複製(“hg clone”) や変更の取り込み(“hg pull”)のために、他のユーザに(あなたの)リポジトリへの書き込みを許可する必 要5 が無い ことを意味します。読み出しを行う他のユーザには、読み出し権限のみの公開で済みます(この性質は構成管理システムに共通の特性で はありませんので、一般的なものだとは思わないでください。多くの構成管理システムでは、読み出しユーザであっても、安全な読み出 しのためにはリポジトリを排他する権限が必要であり、そのためには最低でも1つのディレクトリに対する書き込み権限が必要なため、 安全性と管理上で面倒な問題の原因となり得ます。)。
Mercurial が排他を行うのは、一度に1つのプロセスのみがリポジトリに書き込むのを保証場合だけです(排他に適さないと言われる NFS のよう なファイルシステム6 で あっても、安全に排他できる仕組みを用いています)。リポジトリが他のプロセスにより排他されている場合、書き込みを行うプロセス は、リポジトリの排他が解除されるまで暫く待って再度排他を試行しますが、長時間に渡って排他されたままの場合は、時間切れとみな されます。そのため、例えば人知れずシステムが停止したとしても、自動化された日次処理が停止したままになったり、停止しない処理 が次々と積み上がったりすることはありません。
dirstate 形式ファイルからのリビジョン情報の読み出しに際して、 Mercurial はファイルに対する排他を行ったりはせず、書き込みの 際にのみ排他を行います。不完全な書き込みを dirstate 形式ファイルから読み出してしまうことを回避するため、 Mercurial は対象 dirstate 形式ファイルと同じディレクトリに特有の名前でファイルを書き出し、この一時ファイルを dirstateファイルへと不可分な操 作で改名します。そのため、dirstate という「名前の」ファイルは、不完全な書き込みを持たない完全な内容であることが保証されま す。
比較的大量のデータ読み込み処理に対してすら、ディスクヘッドのシークは非常にコストが高くつくため、 Mercurial の性能確保の重 要な点は、ディスクヘッドのシークを極力回避することにあります。
例えば dirstate 形式のようなデータが、単一のファイルに保存される理由がここにあります。 Mercurial により構成管理される ディレクトリごとにdirstate ファイルが存在する場合は、ディレクトリごとにディスクヘッドのシークが発生し得ます。その ようなディスクヘッドのシークを回避するために、 Mercurial は一度に単一のdirstate ファイル全体を読み込みま す7 。
ローカルストレージにおけるリポジトリの複製の際には、 Mercurial は “書き出し時複製” の仕組みも使用します。複製元リポジト リから複製先に個々の revlog ファイルを複製する代わりに、 “ハードリンク” を使用することで、 “2つのファイル名が同一内容のファ イルを参照” することを手早く表明します。一方の revlog ファイルに書き込みを行う際には、 Mercurial は当該ファイルのハードリン クを確認します。当該ファイルが複数のリポジトリから参照されいている場合、 Mercurial は当該リポジトリ用に revlog の新たな複製 を作成します。
何人かの構成管理ツールの開発者により、この方法 — 完全にリポジトリ固有のものとしてファイルを複製する — が ディスク使用量削減にそれほど効果的でないとの指摘を受けています。それは事実ではありますが、ディスク容量の 確保は安価であり、 OS への複製要求を遅延することにより高い性能を得ることができます。別な仕組みを用いる場 合、性能が低下しソフトウェアの複雑さが増しますので、日々の利用における “体感” に非常に影響を及ぼしま す8 。
ファイルの変更の際の Mercurial への通知が必要ないことから、ファイル変更の有無を効率的に判定するために、特別な情報を格納し た dirstate 形式ファイルを使用します。作業領域ディレクトリ中の全てのファイルに対して、 Mercurial はファイルの最終変更日時と その時点でのサイズを dirstate 形式ファイルに格納しています。
“hg add”、“hg remove”、“hg rename” ないし“hg copy” を明示的に使用した場合、 Mercurial はこの情報を更新しますので、 コミット時の振る舞いを特定できます。
Mercurial が作業領域ディレクトリ中のファイルを確認する場合、最初にファイルの変更日時を確認します。変更日時が同一ならば、 ファイルは変更されていない筈です。ファイルサイズが異なっているならば、ファイルは変更されている筈です。変更日時が異なっているの にファイルサイズが同一の場合にのみ、ファイルの内容が異なっているか否かを判定するために Mercurial は実際にファイルの内容を読み込 みます9 。 このように僅かな追加情報を格納することで、 Mercurial が必要とする読み込みデータ量を劇的に減らすことができ、他の構成管理シ ステムと比較して大幅に性能が改善されています。