Mercurial: "Behind the scenes" を読む
Tagged:  •    •  

今回は "4. Behind the scenes" を読みます。

この章で述べられていることは、 Mercurial の設計方針といった事柄ですので、 構成管理を行う上では必ずしも必要の無い話ですが:

  • 内情を知ることで Mercurial への理解が深まる
  • 構成管理ツール選択の際の判断材料
  • 自分で他のプログラムを設計する際の参考

といったメリットがあります。

4.1 Mercurial’s historical record
4.1.1 Tracking the history of a single file

ファイルごとの履歴情報は filelog 形式で保存されます。

4.1.2 Managing tracked files

構成管理対象のファイル一覧は、 manifest 形式で保存されます。

4.1.3 Recording changeset information

各リビジョン毎の情報は changelog 形式で保存されます。

4.1.4 Relationships between revisions

changelog/manifest/filelog の個々の要素は、 以下のように階層構造を形成しています。

changelog/manifest/filelog 階層 (BOS book より引用)

原文には:

2つのチェンジセットの間で manifest が変更されていない場合、 それらのチェンジセットに対応する changelog 要素は、 manifest 中の同じリビジョンを参照します。

とありますが、 manifest が変更されていない、 即ちファイルには一切の変更が発生していないのに changelog 要素が増える、という事態は、 例えば、 衝突やその解消のための変更が無いマージの場合などが該当します。

4.2 Safe, efficient storage

この節では、 changelog、manifest および filelog が採用している revlog と呼ばれる格納形式に関して説明しています。

4.2.1 Efficient storage

revlog 形式では、 差分ベースでの情報保持が基本になります。

4.2.2 Safe operation

revlog 形式への書き込みを 「改変」ではなく「末尾への追加」に限定することで、 複数の revlog ファイルに跨る書き込みを 「トランザクション」化することが容易になっています (DBMS 等で言う隔離レベルは「Read uncommitted」です)。

トランザクション化の実現方法に関しては後述。

4.2.3 Fast retrieval

大量の差分を適用しないと特定のリビジョンを再現できない、 という CVS などでの性能上の問題を、 revlog 形式では、 一定間隔でその時点の完全なスナップショット (O'Sullivan 氏曰く 「ビデオ圧縮形式における"キーフレーム"のようなもの」) を挟み込むことで回避しています。

4.2.4 Identification and strong integrity

revlog 形式では、 保持するデータのハッシュ値を算出することで、 故意(=偽造)か否(=機器障害等)かによらず、 データの改変を検出することができます。

先述した「スナップショットの挟み込み」との併用により、 他の構成管理システムが採用しているデータ形式よりも、 中途データの破損に対する復旧率が高い、 というのが特徴なのだそうです。

4.3 Revision history, branching, and merging

revlog 形式では、 マージに関わる要素は親を2つ持ち、 それ以外は親を1つ持つ、 という話。

4.4 The working directory

作業領域中の各ファイルのリビジョン情報を保持するのは dirstate 形式、 という話。

4.4.1 What happens when you commit

各ファイルのリビジョン情報を保持する dirstate は、 commit 時の親チェンジセット特定にも使用される、 という話。

4.4.2 Creating a new head

tip 以外での hg update 後に、 変更を hg commit した場合、 即ち新しい head が生成されるような場合でも、 Mercurial の挙動は変わらない、 という話。

4.4.3 Merging heads

Mercurial でのチェンジセットのマージでは、 管理単位であるファイル毎に、 概ね以下のような判断が行われます。

どちらも何もしていない:
なにもしない
一方のみが内容を変更:
一方の変更内容で作業領域を更新
一方が削除したファイルを、他方が変更:
削除と変更のどちらを採用するか確認
一方がファイルを削除:
ファイルを削除
一方が変更したファイルを、他方が改名ないし複製:
変更内容を改名先・複製先にも伝播
両方が内容を変更:
外部プログラムを起動して変更内容をマージ

こまめにマージしていれば、 外部プログラムによるマージの必要な所謂「衝突」(conflict)は、 そうそう発生するものでは無いということです。

4.5 Other interesting design features

この節は、 著者の O'Sullivan 氏による 「Mercurial 技術トピックつまみ食い」的な内容です。

4.5.1 Clever compression

Mercurial では、 圧縮後のサイズが元サイズよりも小さくなる場合には圧縮してデータを保存するので、 磁性面に優しい、という話。

ちなみに、 ネットワーク転送の際には、 個別の履歴情報毎ではなく通信ストリームそのものを圧縮するので、 更に圧縮率が高くなるのだとか。

4.5.2 Read/write ordering and atomicity

(1)「書き込み」が基本的に「データの追加」のみであることと、 (2)履歴情報の持つ changelog ⇒ manifest ⇒ filelog という参照関係の逆順 (filelog ⇒ manifest ⇒ changelog)での「書き込み」、 という2点が Mercurial における整合性保持の上での大きな柱になっています。

ちなみに「書き込み」途中での取り消しは、 書き込みに先立って書き込み前のファイルサイズを記録しておき、 取り消しの際にはファイル長を切り詰める、 ということで実現しています(システムコール的にも一発で済みますね)。 ここでも「書き込み」が基本的に 「データの追加」のみであることが生きてきます。

4.5.3 Concurrent access

Mercurial は排他無しでも整合性の取れた読み出しができるので、 参照のみの利用者のために、 リポジトリの書き込み権限(排他用) を公開する危険を冒す必要がなくなります。

4.5.4 Avoiding seeks

(フラグメント化が進んだ場合) 必ずしも「1つのファイル」=「ディスクヘッドのシークを回避」 ではありませんが、 少なくとも多量のファイルを読み込むよりは 「ディスクヘッドのシークを低減」するのは確かですので、 Mercurial の「極力単一ファイルにまとめる」方式は、 ある程度性能向上に寄与するのでしょう。

ちなみに、 ローカルディスク(厳密には同一パーティション) 内でリポジトリを複製する場合、 Mercurial がハードリンクを使用するのは、 ディスク容量削減ではなく (ファイル生成回避による)ディスクヘッドのシークの低減が主眼なのだそうです。 ま、近年は磁性面単価はゴミみたいなものですしね。

4.5.5 Other contents of the dirstate

事前に記録しておいた更新日付・ファイルサイズでの判定を併用することで、 変更の有無の判定でのファイル内容の全比較の必要性を低減できる、 という話。

ただ、所謂 DOS 改行・UNX 改行の変換の問題が絡んでくると、 hg diff は何も出力しないのに、 hg status は 'M'(変更) マーク連発、 といった嫌な事態になることもあるので注意が必要です。


即座に役立つ知識では無いかもしれませんが、 技術屋的にはこういった技術トピックは読んでいて楽しいですね。

「トランザクション」機構の簡便な実現のあたりは、 結構応用性が高そうな気がします。


"Distributed revision control with Mercurial" 関連エントリの一覧は、BOSBook(Bryan O’Sullivan Book)タグで参照できます。