Michael Hicks, Scott Nettles, "Dynamic Software Updating", ACM TOPLS 2003(1)
いかにしてシステムをとめることなくアップデートするかと言う研究。
そういったシステムでは、以下の四つの評価基準が満たされてる必要がある。
- 柔軟さ
システムのどの部分もアップデートできるようにしたい
- 堅牢性(ロバストネス)
アップデートによってクラッシュやエラーが起きないようにしたい
- 使いやすさ
- オーバーヘッドの小ささ
本稿での実現方法
動的パッチというアイデアに基づいて、動的にアップデートする。
コードとデータのアップデート
このようなmain.popというコード(この論文では、Cとほぼ同じPopcorn*1という言語が使われているため、拡張子はpopとなっている。)があるとする。これを、新しいバージョンmain.pop(2)にアップデートしたい。
static int num = 0;
typedef struct {
int a; int b;
} t;
int f(t T){
num++;
return T.a + T.b;
}
このとき、普通の静的なパッチとは違い、動的パッチでは動作中のプログラムの状態を新しいバージョンに教えてあげないといけない。そのための関数をstate transformerと呼ぶ。すると、main.pop(2)のためのstate transformer Sは、
new version main.pop(2):static int num = 0;
typedef struct {
int a; int b;
} t;
int f(t T){
num++;
return T.a * T.b;
}
見てのとおり、ただnumという変数が移されると言うだけの関数。もちろん、state transformerには、もっと複雑なことも書くことが出来る。例えば、有向グラフを表すgraphという型があって、graph型の表現方法を変更するようなアップデートを行いたい場合、graph型のフィールドから値を取り出して、新しいgraph型へ移行する事も出来る。しかし、ポインタ型で実際のアドレスを見ている場合などは、制限がある。
state transformer Svoid S(){
main.pop(2) :: num = main.pop::num;
}
スタブ関数
パッチは、全てのプログラムにあてるわけではなく、アップデートしたい部分にのみあてるため、関数やデータの型を変更するようなアップデートの場合、プログラムのほかの部分からの参照と型が食い違ってしまう。例えば、先ほどのmain.popを以下のようなmain.pop(3)にアップデートしたいとする。
ここで、関数fの引数が変わっている。こういった場合、通常は関数fを呼び出している箇所にもパッチを当てればよいのだが、呼び出し側を変更できない場合もある。例えば、大きなアップデートをいくつかの小さなアップデートに分割する場合などである(ここの部分良くわからず。。）。こういった場合に対処するために、スタブ関数と言うものを使えるようにする。スタブ関数とは、アップデートする前の関数と同じ型の引数を受け取り、アップデート後の関数fとの間に介入して正しい処理を行うような関数である。main.pop(3)の場合だと、state transformerとスタブ関数は以下の様にすればよいだろう。
new version main.pop(3):static int num = 0;
typedef struct {
int a; int b;
} t;
int f(t T, int x){
num++;
return T.a + T.b + x;
}
ここでstub_fと言うのが、スタブ関数である。アップデートしない他のモジュールの関数fの呼び出しは、stub_fを呼び出すことになる。
state transformer Svoid S(){
main.pop(3)::num = main.pop::num;
}int stub_f(t T){
return f(T, 0);
}
型定義の変更
先ほどから見てきているmain.popのtという構造体を以下のようなmain.pop(4)にアップデートしたいとする。
どのようにしてパッチに表現すればよいだろうか？単純な方法としては、古い型と新しい型を別のものとして扱えるようにする、と言うものがある。この方法での、パッチは以下のようになる。
new version main.pop(4):static int num = 0;
typedef struct {
int a; int b; int c;
} t;
int f(t T) {
num++;
return T.a * T.b * T.c;
}
(このコードは、元の論文に載っていたのだけど、stub_fの中のT2で、cの値を0にしちゃうと、fの返り値が常に0になっちゃうから良くない様な。。。まあ説明したいことには、プログラムの意味は関係ないから無視すればいいんだろうけど)
state transformer Svoid S() {
main.pop(4)::num = main.pop::num;
}
int stub_f(Old::t T) {
t T2 = new t(T.a, T.b, 0);
return f(T2);
}
ここで、アップデート前の型tはOld::tとして扱うことが出来る。
制限
これまで紹介したパッチには、いくつかの制限がある。特にstate transformerに根本的な制限がある。それは、スタック上のデータを扱う手段が無いということ。そして、プログラマがstate transformerでそれまであったデータを手で扱わないといけないと言うことは、時として煩わしいということである。これらについて考えてみよう。
- state transformationの表現力について
state transformation関数では、新しい状態はアップデートする前の状態から得ることが出来るという仮定に基づいている。しかし、新しいデータ構造に、現在のプログラムでは得ることの出来ない情報が含まれている可能性もあるのである。例えば、データ構造が生成されたときのタイムスタンプを組み込みたいとしても、その情報はアップデートする際には得ることが出来ないのである。こういった状態遷移の理論的な限界に関しては、Bloom and Day 1993が詳しい。
この問題は、問題のあるコードやデータ構造を、情報の欠如を扱えるように修正することで解決される。
他の研究では、この問題に対して、古いコードと新しいコードを混ぜることを許すことで対処している。どちらのバージョンのコードを用いるかと言うことは、自動的に決定される。しかし、この方法では、一般的な動作の正当性を示す事が出来ない。
- スタックのtransformation
state transformation関数Sは、ヒープや静的なデータ領域を含めて、グローバルな状態は扱えるが、スタックは扱うことが出来ない。
スタックを直接扱うことが出来ないことで、以下の二つが可能になる。
- 古いコードやデータが、新しいコードと一緒に動作することが出来る。これによって、動作中のコードのリターンアドレスを新しいコードに対応するように書き換える必要が無くなるという利点がある反面、正しくなかったり予測できない動作をする場合があると言う欠点もある。複数のバージョンを正しく扱えるようにする方法の一つが、スタブ関数である。
- 実装が簡単になる。
この論文では、実装の簡単のためスタックを扱えわないことにした。これによって、スタックが空の時にのみアップデートが出来る。
- 既存のデータのtransformation
これまで紹介したパッチは、プログラマ主導のものであった。しかし、これではプログラマに余分な負荷をかけてしまう。そこで、システム主導のパッチというアプローチもある。これは、ある型のデータは一つしか存在できないと言うことをシステムで強制するのである。このようにすると、プログラマは、古い型がどのようにして新しくアップデートされるのかを示すために、型変換関数(type conversion functions)を定義する。この方法を使った例は以下のようになる。
new version main.pop(4_2):static int num = 0;
struct t {
int a; int b; int c;
}
int f(t T) {
num++;
return T.a * T.b * T.c;
}
システムは必要に応じて、convert_t関数をデータを変換するために使う。このように、プログラマはどのようにしてデータが変換されるかということだけを考えればよく、いつ変換されるかと言うことを考えなくてすむようになる。
state transformer Svoid S() {
main.pop(4)::num = main.pop::num;
}
Old::t convert_t(t T) {
t T2 = new t(T.a, T.b, 0);
return T2;
}
このシステム主導のパッチには、二つの欠点がある。
実装が煩雑になるということである。つまり、データは型付けされている必要があるため、データを見つけ変換する手段が必要となるのである。加えて、変換中に起こるようなエラーの扱いが難しい。さらに、自動的にデータを変換するこの方法は、あるアプリケーションにおいては柔軟性が無い。
本論文では、プログラマ主導のパッチを採用する。柔軟性があり、実装が簡単であるからである。
まとめると、動的パッチの定義は、(f, S, stub set)と表す。ここで、fは新しいコード、Sはヒープと静的データ領域に対するstate transformer関数、stub setは関数から対応するスタブへの写像の集合、をそれぞれ表している。
んー、ずいぶん長くなっちゃったな。と言うわけで、二回に分けます。
この後は、実装方法とパッチをどうやって得るかと言う話になっていきます。
