👜

修正ハノイの塔アルゴリズム　もうひとつのバックアップレベルの決め方

2021/03/21に公開

toh

backup

dump

tech

はじめに

ファイルシステムのバックアップを取るとき、定期的にフルバックアップを取ります。
そして、フルバックアップから次のフルバックアップまでの期間は、更新・新規作成されたファイルをバックアップする、という方法が採られます。

では、日々のバックアップ対象とするファイルは、どのように選択するのでしょうか。
現在多く行われている方法は、フルバックアップ以降全ての更新ファイルを取得し続ける差分バックアップ、直前のバックアップ以降に更新されたファイルのみを取得する増分バックアップの、いずれかです。^[1]

そして、現在ではあまり使われていませんが、差分バックアップ、増分バックアップの間を取ったような方法として、修正ハノイの塔アルゴリズム(Modified Tower of Hanoi algorithm)があります。
本稿では、修正ハノイの塔アルゴリズムがどんなのであったのか、それを発掘してみます。

修正ハノイの塔アルゴリズム

修正ハノイの塔アルゴリズムを簡単に説明すると、増分バックアップの変形です。
修正ハノイの塔アルゴリズムは、バックアップ周期の中で、1日分のバックアップと2日分の増分バックアップを交互に繰り返します。

修正ハノイの塔アルゴリズムの動作

修正ハノイの塔アルゴリズムを、ダンプレベルで表記すると以下のようになります。これは1週間周期の場合です。

日	月	火	水	木	金	土
0	3	2	5	4	7	6

修正ハノイの塔アルゴリズムでは、このダンプレベルのシーケンスによって、増分を取得するのでしょうか。

月曜日は、ダンプレベルが3なので、フルバックアップ後からバックアップ時点まで、1日分の増分を取得します。

火曜日は、月曜日のダンプレベルが3、火曜日のダンプレベルが2なので、2よりもレベルが小さい最後のバックアップである、フルバックアップ以降の、月曜と火曜の2日感の増分を取得します。

水曜日はダンプレベル5なので、4より小さいダンプレベルのバックアップのうち、最新のものである、火曜日(ダンプレベル2)のバックアップ以降の、1日分の増分を取得します。

木曜日は、ダンプレベル4なので、それよりもダンプレベルが小さい最新のバックアップである、火曜日以降、2日分の増分が取られます。

金曜日は、ダンプレベルが7なので、それよりもレベルが小さい最新のバックアップである木曜日(レベル4)以降の、1日分の増分を取得します。

土曜日は、ダンプレベルが6なので、それよりもレベルが小さい最新のバックアップである木曜日(レベル4)以降の、2日分の増分を取得します。

この流れを図示すると、以下のようになります。横軸はファイルの作成・更新時点、縦軸はバックアップ実行時点です。1日の終りにバックアップを取る想定をします。

一週間周期の修正ハノイの塔アルゴリズムによるバックアップ取得

修正ハノイの塔アルゴリズムはどこで紹介されていたか

修正ハノイの塔アルゴリズムは、動作を説明されると納得できます。ですが、とても直感的とは言いがたいです。では、このダンプレベルの並びはどこで紹介されていたのでしょうか。

ダンプレベル決定における修正ハノイの塔アルゴリズムは、BSD系maanの、dump(8)に記述卯があります。該当部分を引用します。

 +o   After a level 0,	dumps of active	file systems (file systems
     with files that change, depending on your partition layout some
     file systems may	contain	only data that does not	change)	are
     taken on	a daily	basis, using a modified	Tower of Hanoi algo-
     rithm, with this	sequence of dump levels:

       3 2 5 4 7 6 9 8 9 9 ...

また、少なくとも2000年前後のドキュメントや書籍で、修正ハノイの塔アルゴリズムの名前を覧ることができます。2000年のLinux: dump and restore mini-HOWTO や、2001年発行の書籍であるUNIXバックアップ＆リカバリにも記述がありました。

修正ハノイの塔アルゴリズムの名前の由来

バックアップテープのローテーショ鳴子リズムに、ハノイの塔アルゴリズムとよばれるものがあります。これは、n本のテープで、2のn-1乗の日数のリストアを可能とする、テープ交代順の決定アルゴリズムです。

ですが、UNIXバックアップ＆リカバリには、パズルのハノイの塔の円盤の数に由来する数列、という記述があります。
修正ハノイの塔アルゴリズムに関する原典が見つからなかったのであくまでも推測ですが、グレイコードによる3枚ハノイの塔の解法に由来した数列を紹介します。

ハミング距離1の数値エンコードのひとつであるグレイコードは、遷移がハノイの塔の解法と一致している、という特徴があります。最上位ビットを一番大きい(一番下の)円盤、最下位ビットを一番小さい(一番上の)円盤に対応させると、数値が0(初期状態)から1ずつ増加していくときにグレイコードにエンコードします。
このとき、グレイコード側で変化したビットが、そのターンで動かすべき円盤に対応します。
最小手数をとる場合、円盤の移動先は、ビットの状態とターン数から求めることができます。

3枚円盤のハノイの塔

最初に3枚の円盤が重ねてある棒がA、テンポラリ用の棒がB、移動先の棒をCとします。
3枚ハノイの塔に対応する3bitのグレイコードの0から7までの遷移と、そのビット反転は、以下のようになります。続く括弧の中の数値は、そのビット列をグレイコードと見なしてデコードした数値です。

ハノイの塔手順	初期状態	1枚目をC	2枚目をB	1枚目をB	3枚目をC	1枚目をA	2枚目をB	1枚目をC(完成)
グレイコード	000 (0)	001 (1)	011 (2)	010 (3)	110 (4)	111 (5)	101 (6)	100 (7)
グレイコードのビット反転	111 (5)	110 (4)	100 (7)	101 (6)	001 (1)	000 (0)	010 (3)	011 (2)

このように、先程のダンプレベルと同じような数列が現れます。この数列を利用していることから、修正ハノイの塔アルゴリズム、という名前になったと思われる……のですが、前述の通り修正ハノイの塔アルゴリズムに関する原典が見つからず、推測の域を出ません。

複数週間のバックアップとダンプレベル1

修正ハノイの塔の1週間周期ローテーションで、ダンプレベル1は出てきません。
ダンプレベル1は、ローテーション期間を複数の州に設定するときに、フルバックアップ以降の全ての差分を取得するときに使用します。

修正ハノイの塔アルゴリズムで2週間ローテーションするときは、以下のようなダンプレベル設定をします。2回目の日曜日に、フルバックアップからの差分を取得し、2週間目は、それ以降の増分を取得します。
4週間(1ヶ月)周期にする場合も、3周目、4周目の日曜日レベル1の差分取得を行います。

2週目の状態へのリストア・ロールバックは、最初の日曜日のフルバックアップ、次の日曜日の差分(レベル1)と、それ以降の増分を適用します。

日	月	火	水	木	金	土	日	月	火	水	木	金	土
0	3	2	5	4	7	6	1	3	2	5	4	7	6

2週間周期の場合を図示すると、以下のようになります。

2週間周期の修正ハノイの塔アルゴリズムによるバックアップ取得

修正ハノイの塔アルゴリズムの利点と欠点

では、修正亜ハノイの塔アルゴリズムには、どのような利点と欠点があるのでしょうか。

先に結論を書いちゃうと、利点も欠点も差分バックアップと増分バックアップの間を取ったものであり、オペレーションが直感的でない、という点が、現在あまり使われていない理由であると考えられます。

利点

1週間でローテーションする場合のリストアは、フルバックアップと、最大で3本の増分を適用すれば、リストア、あるいはロールバックを行うことができます。
また、一度に取得するファイルサイズ、蓄積されるファイルサイズは、フルバックアップ以降全てのの更新ファイルを保存する、差分バックアップよりも小さくなります。
これは、更新日が判っている特定のファイルをリストアする場合は、差分バックアップよりも短時間でファイル取り出しを行うことができる、ということです。

欠点

差分バックアップ、増分バックアップと比較したとき、ダンプレベルの設定、リストアで使用するバックアップファイルの選択が直感的ではありません。
また、差分バックアップよりもバックアップデータの総量は少ないですが、単純な増分バックアップよりは大きくなります。
また、バックアップを1回取得されるファイルと2回取得されるファイルがあることから、いずれかのが破損したときに失われる可能性が残るのは、増分バックアップと同じです。

まとめ

総括すると、修正ハノイの塔アルゴリズムは、利点も欠点も差分バックアップと増分バックアップの間を取ったものであり、オペレーションが直感的でない、という点が、現在あまり使われていない理由であると考えられます。

言い換えれば、バックアップの工数と総バックアップ容量(テープ本数)のトレードオフを取りつつ、手動でリストアオペレーションをしていた頃は、差分バックアップと増分バックアップの中間である修正ハノイの塔アルゴリズムに存在意義がありました。
ですが、バックアップの自動化ソリューションが一般化し、バックアップメディアも低価格になった今では、選択肢に入らなくなってしまった、とも言えます。
、

そういうケチをつけつつも、わたしはチームレベルのLinuxベースファイルサーバでは、バックアップに修正ハノイの塔アルゴリズムを1週間ローテーションで、2ボリューム(2週間分)保存するという方法を採用していました。
これは、慣れればオペレーションが簡単であること、フルリストアよりも特定ファイルの復旧の方が多い環境であったこと、そして、それを手動で行う規模であったこと、というのが理由です。

脚注

初代のフルバックアップと取得した増分から定期的に新しいフルバックアップを作る、永久増分バックアップもありますが、これは増分バックアップのバリエーションです ↩︎