Time Machineは過去をどのように記憶しているのか？

Time MachineとTime Capsuleによるバックアップ環境は、面倒な手順なしで、今までにない絶大な安心感を与えてくれる。

• バックアップ対象を詳細に選別する必要もなく、起動ディスク丸ごと、つまりマシン環境そのまんまが保存できる。
• そして、過去のバックアップ時点の状態はルールに従って*1残され、任意の過去のマシン環境にいつでも戻すことができる。（もちろん、任意のファイルやフォルダだけを復元することも可能）
• しかも、ディスク容量をそれほど浪費する訳でもなく、おそらく変化した差分のみがバックアップされている様子。なのに、Finderでバックアップファイルに直接アクセスすることも出来て、見た目は起動ディスク以下の一般的なファイルやフォルダが並んでいるだけ。

これまでもバックアップにはいろいろな方法を試してみたが、Time Machineと比較すると、以下のような悩みを抱えていた。

• 起動ディスクのクローンを作ることは出来たが、それはバックアップする度に上書きされる点のバックアップで、過去の履歴は上書きされてしまう。
• 複数のイメージディスクとして過去を残し続けようとすると、膨大なディスク容量とバックアップ時間が必要になってしまう。とても1時間ごとのバックアップなんて対応できない。
• .Macからも「バックアップ」という名前のまんまのソフトウェアが提供されている。ホームフォルダレベルの毎日の差分バックアップまでなら使えるが、やはり、システム全体を1時間ごとにバックアップなんて使い方は無理。また、差分ファイルは、途中1箇所でもバックアップファイルが壊れてしまうと、それ以降のバックアップは失われてしまう不安があった。
• SubversionやGitなどのバージョン管理ソフトは、特定のファイルやフォルダの変化を追跡することには向いているが、起動ディスク全体のような巨大な履歴を管理することは多分、出来ない。（試したことないけど）

Time Machineは、一体どんな方法でバックアップしているのだろう？

バックアップファイルの保存方法

スパースバンドル

• Time Machineのバックアップ先であるTime Capsuleの中には、バックアップ対象のマシンがディスクイメージとして保存されている。
  • Time Capsule >> コンピュータ名_MACアドレス.sparsebundle

• そして、上記ディスクイメージをマウントすると、以下のようなフォルダ構成で毎時のバックアップが続けられていた。
  • Backup of コンピュータ名 >> Backups.backupdb >> コンピュータ名 >> 年-月-日-時分秒 >> ディスクボリューム名
  • 例："Backup of zariMacBook/Backups.backupdb/zariMacBook/2009-03-20-061517/Macintosh HD"
  • 年-月-日-時分秒はバックアップした時の日時になる。

• OSX 10.4までのスパースイメージとスパースバンドルの違いや利点などは、以下のページでとても分かり易く説明されていた。
  • スパースバンドル・ディスクイメージを発見する

• つまり、スパースイメージは一つの巨大なファイルになってしまうが、スパースバンドルはそのフォルダの中に8Mバイトに分割されたファイルがいくつも保存されている。
• ディスク内容が更新された時、スパースバンドルでは更新されたファイルを含む8Mバイトのファイルだけが更新される。
• 例えば、100GBのスパースイメージだったらその中の1ファイルを変更しただけでも100GBのディスクイメージ全体を書き換えることになってしまうが、スパースバンドルなら変更があったファイルを含む8MBの領域だけを書き換えれば良いことになる。
• だから、Time Machineのように巨大なディスクイメージを扱うにはとても効率的なのだ。
• マシンごとに独立したスパースバンドルが作成されるので、一つのTime Capsuleに複数のマシン環境をバックアップすることも出来る。

ハードリンク

• 年-月-日-時分秒のフォルダ以下には、起動ディスクなどのボリュームが丸ごと保存されている。
• それが、バックアップを繰り返した回数分保存されているのだから、普通に考えれば膨大なディスク容量が必要になるはず。（ボリュームの容量×バックアップ回数）
• ところが実際には、バックアップ先のTime Capsuleではボリュームの容量＋アルファ程度しか消費されていない。（例：100GBの起動ディスク＋数GB）
• 一体、何が起こっているのか？実は、UNIX的にはTime Machineのバックアップファイルはハードリンクになっているらしい。
• しかし、ハードリンクと聞いてもピンと来ない。ハードリンクとは何者で、なぜ、ディスク容量を消費しないのだろうか？

• あるファイルを保存するという行為が、実際のOSの中でどのように管理されているかというと、単純には以下のような領域に分けて考えられる。
  • そのファイルのデータ本体（例：テキストなど）......[1]
  • そのファイルのインデックス情報（例：作成・更新・アクセス日時、サイズ、ファイルタイプ、権限、データ本体へのポインタ、リンク数など）......[2]
  • インデックス情報は、iノード番号と呼ばれるユニークな整数値によって管理されている。
  • フォルダとは、その直下に含まれるiノード番号とファイル名を保存したファイルの一種である。......[3]
  • ファイル名がインデックス情報ではなく、フォルダ情報としてiノード番号とセットで管理されているところが意外な感じ。

• 上記の仕組みを利用して、いろいろな操作をしてみると、以下のような更新が発生する。
  • ファイルが新規作成されると、[1][2][3]すべての領域が更新される。
  • ファイルを編集した場合は、[1][2]の領域が更新される。
  • ファイルをtouchした場合は、[2]の領域が更新される。
  • ファイルを移動した場合は、[3]の領域が更新される。

• そして上記仕組みを応用すると、もし[3]の領域に同じiノード番号を持った情報を追記すると、全く同じ[1]データ本体と[2]インデックス情報を参照するファイルがもう一つ出来てしまうのである。
• これがハードリンクである。言い換えれば、すべてのファイルはiノード番号が示す[1]データ本体と[2]インデックス情報へのハードリンクであると言える。
• 新規作成したファイルと、そのあと作成したハードリンクは完全に同等で、差はない。区別することはできない。
• ところで、[2]インデックス領域ではハードリンクのリンク数も管理している。
• ファイルを削除するという行為は、[3]の領域から対象情報を削除することと、[2]インデックス領域のリンク数を1減少させることと言える。
• そして、リンク数が0になった時、初めて、そのファイルのインデックス情報は[2]の領域から削除されることになる。（リンク数が0にならない限り、ファイルは存在し続けるのだ。）

ハードリンク、というよりはUNIXのファイルシステムは、非常に興味深く巧妙な仕組みだ！（メモリ管理の方法に似ているかも）

• Time Machineはこの仕組みを利用して、バックアップをすべてハードリンクとして保存している。
• ハードリンクの追加によって消費される容量は、[3]の領域のiノード番号とファイル名のみの必要最小限で済んでしまうのだ。

起動ディスク全体を1時間ごとにバックアップしても、無駄に保存領域を浪費しない秘密はここにあった！

• 参考ページ：
  • ln - ハードリンクまたはシンボリックリンクの作成 - 会津大学UNIXウィキ
  • [psl] UNIXの基礎の基礎
  • ＵＮＩＸのファイル・システム
  • 第7回　ファイル・システム（前編）：ITpro

HFS+における疑似ハードリンク

Time Machineはハードリンクを活用していると書いておきながら、実はOSXのHFS+というファイルシステムは、UNIXのハードリンクを同じ仕組み（iノードによる管理）では実現できないことが判明した。それではどのようにハードリンクの仕組みを実現しているのだろう？

• HFS+環境でハードリンクを作成すると、/（ルート）から辿ることの出来ない隠しフォルダに本体ファイルを移動する。
• そのあと、リンク元、リンク先の両方にハードリンクファイル（クリエーター: hfs+、ファイルタイプ: hlnk）を作成する。
• ハードリンクファイルは、隠しフォルダの本体ファイルを指し示すエイリアスやシンボリックリンクのように振る舞う。
• 上記仕組みは、カーネル内部のHFS Plusレイヤーで解釈される kernel-level symbolic link という仕組みで処理される。
• その実態は、OSX 10.5からはまるでUNIXのハードリンクのようにラップされているが、OSX 10.4でアクセスしてみると...
  • ハードディスクのルートには .HFS+ Private Directory Data? という隠しフォルダが見えて、その中に本体ファイルが存在する。
  • 多くのフォルダがエイリアス（ハードリンクファイル）となって、隠しフォルダの本体ファイルへリンクしているのが確認できる。*2

• 参考ページ：
  • Undocumented Mac OS X：第8回　HFS、HFS Plusの基本的概念【中編】 (3/3) - ITmedia エンタープライズ
  • Leopard解体新書--第4回：Behind the Time Machine - Leopard解体新書 - page3 - ZDNet Japan
  • AppleInsider: Mac OS X Leopard に向かって: Time Machine [Page 3] - silvervine の定点観測所

バックアップ除外項目

• Time Machineはバックアップする価値のないファイルは除外してくれる。その設定は以下のファイルに書いてある。
  • /System/Library/CoreServices/backupd.bundle/Contents/Resources/StdExclusions.plist
  • 上記ファイルをダブルクリックすると、Property List Editorが起動して、以下のように見えた。（開発環境がインストールされていれば）

• Finderから見えないファイル、ライブラリフォルダの中で不要なファイルは、最初からかなり詳細に除外指定*3されており、無駄なバックアップで保存領域を圧迫しないようになっているのだ。
• 上記以外にもバックアップから除外したい項目は、システム環境設定 >> Time Machine >> オプション にパスを追記することで除外してくれる。

変化したファイルを確認する

起動ディスクを丸ごとバックアップしようとすると、そこに含まれるファイルやフォルダの多さに圧倒される。環境にもよるが、その数100万個前後あるんじゃないだろうか。なので、前回のバックアップと比較して、変化しているファイルやフォルダをしらみ潰しにチェックする作業には、Core2Duo 2GHzのCPUでも相当時間がかかりそう。
実際、.Macが提供するBackupアプリケーションは差分を検出するために上記の作業をしていたと思うのだが、バックアップするファイルが増えるほどに差分チェックに時間が掛かっていた。だからBackupによる起動ディスク丸ごとのバックアップというのは負荷が大き過ぎると思う。一度試してみたが、チェック作業中にメモリを異常に消費して、いつまで経ってもバックアップが終わらない状態だったと記憶している。
ところがTime Machineの場合、初回こそ相当な時間がかかってしまう（一晩とか）場合があるが、その後の毎時のバックアップにはそれほどの時間を必要としない...。一体、どのような方法で差分チェックを行っているのだろう？

/dev/fsevents 機構

OSX 10.4以降、/dev/fsevents という機構が搭載されたそうだ。/dev/fsevents 機構は、カーネルを通るあらゆるファイル i/o を追跡して、すべてのファイルの変更を通知してくれるらしい。OSX 10.4で実装されたSpotlightは、この/dev/fsevents 機構の通知を受け取って、検索インデックスを効率よく最新の状態に更新しているようだ。
もし/dev/fsevents 機構が無いと、検索インデックスは定期的に更新する必要があるが、次にインデックスを更新するまでの間のファイルの変更は、検索してもヒットしないことになってしまう...。そして、予約された時間が来ると、猛烈な勢いで検索インデックスの更新作業を実行する。そう、今は昔、OS9時代のシャーロックのようになってしまうのだ...。Spotlight にとって/dev/fsevents 機構は必須なのであった。
さらに /dev/fsevents 機構は OSX 10.5で Time Machine を可能にした。Time Machine は次にどのファイルをバックアップするか、/dev/fsevents 機構から教えてもらっていたのだ。/dev/fsevents 機構がカーネルレベルで漏れなく監視しているファイルの更新情報を利用して、Time Machineの毎時のバックアップは迅速に実行できるようになったのだ。
Time Machineは、/dev/fsevents 機構を直接利用するのではなく、以下のFSEvents APIを通して利用しているのかもしれない。

FSEvent APIの実装とモダンOSの完成

ちょっと余談になってしまうが、ファイル監視の機能はOSX 10.5の開発環境でFSEvent APIとしても公開された。ファイルの変更を監視する機能というのは、一見ありふれたことのように見えるが、実はモダンOSとしての悲願であったらしく、これを実現するためにいくつもの工夫や妥協の絶妙なバランスの上で成り立っているらしい。FSEvent API 実装までの軌跡 = OSX開発の歴史そのものと言っても過言ではなく、この辺の話は、非常に興味深く以下のページに翻訳されている。とっても面白い。

• 参考ページ：
  • Mac関連ﾈﾀをそれはもう凄まじい勢いで翻訳するｽﾚ7（fseventでテキスト検索してスレッド54辺りから。アーカイブされるとリンクをクリックしただけでは読めなくなってしまうかも...。）
  • Mac OS X 10.5 Leopard: the Ars Technica review - Ars Technica（原文）

• 上記ページから読み取ったこと
  • /dev/fsevents 機構はカーネルに存在する。カーネルに存在するコードは、各イベントをクライアントに通知してからできるだけ素早く次に進むのが理想。そうしないと、処理しきれないイベントを捨てるか、デッドロックが発生することになってしまう...。
  • そこで、/dev/fsevents 機構は、SpotlightやTime Machine、FSEvents API等の信頼できるプロセス（クライアント）のみサポートすることになっている。FSEvents APIは、フォルダ監視をするために新しく追加されたAPI。
  • FSEvents APIは、fseventsdデーモンによって /dev/fsevents を読んで、イベント情報を各ボリューム上のログファイル /.fseventsd ディレクトリ内に書き込む。ただし、ログファイルが巨大になりそうなので、ディレクトリレベルでのみ変更を記録する。
  • だから、FSEvents APIはそのディレクトリで何か変更があったことしか通知できない。利用する側では、変更のあったディレクトリを検索して、自分でどのファイルに何が起こったのか確認する必要がある。
  • せっかくすべてのファイル更新情報を網羅できるのに、ディレクトリレベルでしか監視せず、その詳細を自分で調べ直すのは無駄な作業な気がするが、カーネル処理の効率化とファイルを監視するという目的を両立するための現実的な妥協点を探って、このような仕様になったようだ。

拡張属性

• Time Machineのバックアップフォルダの中をターミナルからlsで覗いてみると、以下のように表示される。

$ cd Backups.backupdb/zari_macbook
$ ls -l
drwxr-xr-x@ 6 bebe  staff  204  3 21 14:23 2009-03-21-142314
drwxr-xr-x@ 6 bebe  staff  204  3 21 14:24 2009-03-21-142455
lrwxr-xr-x  1 bebe  staff   17  3 21 14:24 Latest -> 2009-03-21-142455

• 気になるのは、権限情報の最後の項目「@」のところ。
• 「@」はそのファイルが拡張属性（自由に拡張可能な関連情報）を持っていることを意味し、「-l@」オプションで属性キーを表示できる。（右の数字はバイト数）

$ ls -l@
total 8
drwxr-xr-x@ 6 bebe  staff  204  3 21 14:23 2009-03-21-142314
	com.apple.backup.SnapshotNumber	  2 
	com.apple.backup.SnapshotVersion	  2 
	com.apple.backupd.SnapshotCompletionDate	 17 
	com.apple.backupd.SnapshotStartDate	 17 
	com.apple.backupd.SnapshotState	  2 
	com.apple.backupd.SnapshotType	  2 
drwxr-xr-x@ 6 bebe  staff  204  3 21 14:24 2009-03-21-142455
	com.apple.backup.SnapshotNumber	  2 
	com.apple.backup.SnapshotVersion	  2 
	com.apple.backupd.SnapshotCompletionDate	 17 
	com.apple.backupd.SnapshotStartDate	 17 
	com.apple.backupd.SnapshotState	  2 
	com.apple.backupd.SnapshotType	  2 
lrwxr-xr-x  1 bebe  staff   17  3 21 14:24 Latest -> 2009-03-21-142455

• 拡張属性の中身は、xattrコマンドで確認できた。

$ xattr -l 2009-03-21-142314
com.apple.backup.SnapshotNumber:
0000   31 00                                              1.

com.apple.backup.SnapshotVersion:
0000   31 00                                              1.

com.apple.backupd.SnapshotCompletionDate:
0000   31 32 33 37 36 31 32 39 39 34 35 36 30 38 30 31    1237612994560801
0010   00                                                 .

com.apple.backupd.SnapshotStartDate:
0000   31 32 33 37 36 31 32 39 39 34 33 30 30 32 35 39    1237612994300259
0010   00                                                 .

com.apple.backupd.SnapshotState:
0000   34 00                                              4.

com.apple.backupd.SnapshotType:
0000   31 00                                              1.

• 日時フォルダの中の起動ディスクの拡張属性は、以下のようになっていた。

$ xattr -l Macintosh\ HD
com.apple.backupd.SnapshotVolumeFSEventStoreUUID:
0000   37 37 39 31 34 42 38 33 2D 32 38 31 38 2D 34 34    77914B83-2818-44
0010   34 31 2D 42 44 46 41 2D 32 34 34 32 44 31 33 42    41-BDFA-2442D13B
0020   31 44 43 41 00                                     1DCA.

com.apple.backupd.SnapshotVolumeLastFSEventID:
0000   32 33 35 34 36 00                                  23546.

com.apple.backupd.SnapshotVolumeUUID:
0000   42 41 33 32 33 30 46 32 2D 37 42 46 38 2D 33 35    BA3230F2-7BF8-35
0010   43 45 2D 42 37 32 38 2D 34 37 41 45 35 41 32 36    CE-B728-47AE5A26
0020   39 31 42 44 00                                     91BD.

com.apple.backupd.VolumeIsCaseSensitive:
0000   30 00                                              0.

com.apple.metadata:_kTimeMachineNewestSnapshot:
0000   62 70 6C 69 73 74 30 30 33 42 2D 63 C3 7F 00 00    bplist003B-c....
0010   00 08 00 00 00 00 00 00 01 01 00 00 00 00 00 00    ................
0020   00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................
0030   00 11                                              ..

com.apple.metadata:_kTimeMachineOldestSnapshot:
0000   62 70 6C 69 73 74 30 30 33 41 AE E9 63 4E 00 00    bplist003A..cN..
0010   00 08 00 00 00 00 00 00 01 01 00 00 00 00 00 00    ................
0020   00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................
0030   00 11                                              ..

• 何やら、Time Machineのバックアップに関する情報がひっそりと書き込まれていた。
• その情報が意味するところは分からないが、Time Machineの舞台裏ではこれが活躍しているはず。

• 参考ページ：
  • Leopard のファイルシステム拡張属性 - d.hetima
  • Undocumented Mac OS X：第11回　HFS Plus独自の機能【後編】 (2/2) - ITmedia エンタープライズ
  • Undocumented Mac OS X：第7回　HFS、HFS Plusの基本的概念【前編】 (2/4) - ITmedia エンタープライズ

Time Machineのバックアップの方法は、表面的にはユーザーにバックアップ先を選択させて、スイッチを入にするだけという究極のシンプルさ。しかし、その裏では、スパースバンドル、シンボリックリンク、/dev/fsevents ファイル監視機構、自由に拡張可能なファイル属性、といった様々な技術が絶妙に組み合わされて実現されていた。そして最後に、バックアップしたスナップショットがブラックホールに吸い込まれる神秘的なアニメーションで分かり易く表現されることで、芸術的なレベルのアプリケーションに仕上がっていたのだ！

• バックアップから復元する状況というのは、できれば遭遇したくないこと。
• そして、運良くそんな状況にならなければ、Time Machineの利用価値は、あまり感じることはできないかもしれない。
• しかし、一度でもそのような状況になれば、その素晴らしさは実感できる。*4
• Time Machineを利用できる環境ならば、今すぐスイッチを入れるべきなのだ。
• スイッチを切ったままでは、OSX 10.5 Leopardの魅力の半分しか体験できていないのだと思う。

参考ページ

調べているうちに出会った白山貴之さんの記事はどれも奥深く、OSXの深遠な技術の世界に導いてくれます。読み始めると、熟読せずにはいられない相当な面白さです。（自分の知識不足で正確に理解できることは少ないのですが...。）

• Undocumented Mac OS X シリーズ
  • 「Undocumented Mac OS X」最新記事一覧

• the inner universe of Leopard シリーズ
  • 【レポート】秘められた"真の革新"を暴く - the inner universe of Leopard (1) Mac OS X Leopard | パソコン | マイコミジャーナル
  • 【レポート】the inner universe of Leopard - 「rcの引退とlaunchdの強化」 (1) goodby "rc" | パソコン | マイコミジャーナル
  • 【特集】Mac OS X独自のディレクトリサービスOpen DirectoryとdsLocal(前編) -the inner universe of Leopard (1) 「Open Directory」とは何か? | パソコン | マイコミジャーナル
  • 【特集】Mac OS X独自のディレクトリサービスOpen DirectoryとdsLocal(後編) - the inner universe of Leopard (1) DirectoryService APIを用いたプログラミング | パソコン | マイコミジャーナル

一見の価値あり、面白過ぎる！一体、どうしたらこんなにも深い知識を習得できるのだろうか...。

ブックマークコメントへの追記

• > 細部が違うかも。ファイル変更を監視するのはカーネル内部のvfs_fseventsで、これがdev/fseventsを通してユーザランドのfseventdと通信するそうな。TimeMachineの内部解説が載ってたMacPeople捨ててしまったなあ…

• • おっしゃる通り、細部は違っているかもしれません...。調べるほどに新たな疑問が湧いてきて、正確に理解できていないことの方が多いです。是非「TimeMachineの内部解説が載ってたMacPeople」を読んでみたいです。より正確な情報をお持ちの方いらっしゃいましたら、コメント頂けると嬉しいです。

*1:デフォルトでは毎時バックアップを実行して、24時間以内は1時間ごと、1ヵ月以内は1日ごと、それ以上過去は1週間ごと、バックアップ先のハードディスクの容量が許す限り保存され続ける。

*2:Time CapsuleのスパースバンドルにはOSX 10.4環境からアクセスできなかった...。USB接続で外付けハードディスクをTime Machineのバックアップ先にしてみると、その様子が確認できた。

*3:spotlightの検索インデックス、ゴミ箱の中身、仮想メモリのswapfile、キャッシュ、ログ等の一時的なファイルや状況によってシステム側が自動作成するファイル

*4:実際、Time Capsuleを導入してから1年弱で数回、その素晴らしさを実感した。以前だったら、諦めるしかなかったこと。OSX環境をバージョンアップ前に戻すことも問題なくできた。