第 3 章 持続的接続時間の自動設定 12
3.3 持続的接続時間の設定機構
3.3.1 設定機構の概要
3.2節では，リクエスト待機間隔の分析から最大持続間隔の値を持続的接続時間 に設定すれば，持続期間内の接続を維持し，思考期間に入った接続を切断できる ことを示した．以下，本節ではそのための具体的な手法を説明する．
本設定機構は，3.2節の分析をそのまま実現する．まず，全てのクライアントか らのリクエスト待機間隔を測定し，記録する．次に，その測定結果からリクエス ト待機間隔のヒストグラムを作成する．リクエスト待機間隔の短い方からヒスト グラムを探索し，最大持続間隔を見つける．最後に，この最大持続間隔を元に持 続的接続時間を更新する．
図 3.5に，設定方式全体の擬似コードを示す．関数tune_ka()はリクエスト待 機間隔を測定する度に呼び出される．tune_ka()では，まず (1) 全てのリクエス ト待機間隔を記録用配列arr に記録し（9–12行），(2) リクエスト待機間隔のヒ ストグラムhistを作成する（13–15行）．histは配列であり，リクエスト待機間隔 tを添字に与えると，そのリクエスト待機間隔での頻度を返す．(3)作成したヒス トグラムをもとに，最大持続間隔tmaxを見つけ（16–28行），(4) 持続的接続時間
1: //tune_ka()– リクエスト待機間隔を測定する度に呼び出される 2: procedure tune_ka();
3: //arr: リクエスト待機間隔を記録するための配列 (大きさ N) 4: //index: 配列arrのインデックス(初期値 0)
5: //hist: リクエスト待機間隔のヒストグラム(大きさ T) 6: //KeepAliveTimeout: 持続的接続時間の現在値
7: //tmax: 最大持続間隔 8: begin
9: //リクエスト待機間隔の記録
10: arr[index] :=測定されたリクエスト待機間隔; 11: index :=index+ 1;
12: if index < N then return;
13: //ヒストグラムの作成 14: Creatinghist fromarr; 15: index := 0;
16: //最大持続間隔の計算
17: fort:= 0toT −1 do begin
18: ratio :=hist[t]/j≤thist[j]; // 式(3.1) 19: if t≥KeepAliveTimeout then begin
20: err := (ratio−target)/target; // 式(3.2) 21: tmax :=t+adj ·err;
22: break
23: end;
24: if ratio <target then begin 25: tmax :=t; //最大持続間隔の更新
26: break
27: end
28: end;
29: //KeepAliveTimeoutの更新
30: KeepAliveTimeout:=α·KeepAliveTimeout+ (1−α)·tmax // 式(3.4) 31: end.
図 3.5: 持続的接続時間の設定機構の擬似コード
KeepAliveTimeout を更新する（29–30行）．以上により，持続的接続時間の設定 を実現する．
持続的接続時間の設定は定期的に行うこともできる．これは，ウェブサーバに 対する負荷の変化に応じて，適切な持続的接続時間も変化するからである．
以下，擬似コードの詳細な説明を行う．まず，ヒストグラムで求めた最大持続
間隔が現在設定されている持続的接続時間以下の場合（3.3.2節），最大持続間隔 が現在の持続的接続時間を超える場合（3.3.3節）の2つに分けて説明する．最後 に，3.3.4節で最大持続間隔を元にした持続的接続時間の更新方法を説明する．
3.3.2 最大持続間隔の計算
( 最大持続間隔 ≤ 持続的接続時間 )
最大持続間隔tmax を求める過程を図3.6(a) を用いて説明する．最大持続間隔を 求めるため，ヒストグラムhist をリクエスト待機間隔0 から順に大きい方へ調べ ていく．そして，リクエスト待機間隔の頻度が十分小さくなった地点を最大持続 間隔とする．
直感的には，リクエスト待機間隔tの頻度hist[t]がある閾値を下回ったところを 最大持続間隔とするのが自然である．しかし，その判定法では比較的頻度が小さ いリクエスト待機間隔の山の立上りに閾値を下回った場合，その地点に最大持続 間隔が誤って設定されることがある．
式 (3.1)の比率ratioを用いて判定すると，山の立上りではこの比率が相対的に
大きくなるため，最大持続間隔が誤って設定されるのを避けることができる．
ratio:=hist[t]/
j≤t
hist[j] (3.1)
このratioは，新しく加えたhist[t]がこれまでに調べたリクエスト待機間隔全体に 対してどの程度の割合を占めるかを表している．山の立ち上がりではratioの値は 大きく，開始時では1.0である．ヒストグラムを調べて行くにつれて，このratio の値は小さくなり，最終的には閾値targetを下回る．判定のための閾値 target は
現在は5%としており，比較的良好な結果が得られている．また，targetはワーク
ロードによらない値であるため容易に決めることができる．hist[t]がちょうど最大 持続間隔のあたりであれば，式 (3.1)の分母は持続期間内のリクエスト待機間隔全 体となる．持続期間のリクエスト待機間隔全体に対してどの程度小さくなったら 最大持続間隔と判定するかということに応じて，target を決めればよい．
持続期間内の山
Σ < target
頻度
リクエスト待機間隔 ヒストグラムの走査
hist[t]
hist[t]
hist[j]
hist[t]
思考期間内の山
この地点を最大持続間隔とする．
Σhist[j]
i <= t
i <= t
ならば
(a)tmax ≤KeepAliveTimeout
頻度
hist[t]
前回の時刻のKeepAliveTimeout
接続の切断のため KeepAliveTimeoutを超える リクエスト待機間隔は得られない
実際の最大持続間隔 KeepAliveTimeout を
hist[t] の大きさに応じて移動する．
(b) tmax >KeepAliveTimeout 図 3.6: 最大持続期間の計算
3.3.3 最大持続間隔の計算
( 最大持続間隔 > 持続的接続時間 )
現在すでに設定されている持続的接続時間より最大持続間隔が大きい場合，図3.6 (b) に示す通り，リクエスト待機間隔が持続的接続時間を超える接続は切断される．
よって，持続的接続時間を超えるリクエスト待機間隔の分布が得られず，最大持 続間隔を計算することができない．
本機構ではこれに対処するため，現在設定されている持続的接続時間での比率
ratioと，最大持続間隔かどうかを判定する閾値target とのずれに応じて，最大持
続間隔tmax を予測する．このずれは式(3.2)により計算する（図3.5の20行目）．
err := (ratio−target)/target (3.2) 現在の持続的接続時間に誤差errに比例した値を加えたものを最大持続間隔tmax
とすることで，本当の最大持続間隔に近づける．計算は式 (3.3)により行う．
tmax :=KeepAliveT imeout+adj ·err（adj は定数） (3.3) なお，最大持続間隔を大きく調整し過ぎた場合でも，3.3.2節の最大持続間隔の 計算方式により修正されるため問題はない．この修正と最大持続間隔の予測を繰 り返すことで，本当の最大持続間隔に近づくことが期待される．
3.3.4 持続的接続時間の更新
最後に，これまで計算した最大持続間隔をもとに，持続的接続時間を更新する．
本機構では，リクエストのバーストを考慮した持続的接続時間の更新を行う．イ ンターネット・サーバでは，頻繁にリクエストのバーストが観測されることが報告 されている[41, 32, 81]．一時的なバーストによって，リクエスト待機間隔が大き く変化し，誤ったヒストグラムを作成し，最大持続間隔が誤った値に設定される可 能性がある．そのため本機構では，3.3.3節までの方式で求めた最大持続間隔をた だちに持続的接続時間とするのではなく，過去の持続的接続時間を考慮して持続 的接続時間を更新する．過去の持続的接続時間を含めることで，一時的なバース トにより最大持続間隔が大きく変化しても，その影響を抑えることができる．実 現には指数移動平均法による式 (3.4)を用いる（図 3.5の30行目）．
KeepAliveTimeout :=α·KeepAliveTimeout + (1−α)·tmax (3.4) tmax は図3.5 の擬似コードにより計算した最大持続間隔である．右辺のKeepAlive
Timeout は式 (3.4)で計算した一つ前の時刻の持続的接続時間であり，これを用
いて新しい持続的接続時間を計算する．αは重みであり，現在はα= 0.9としてい る．この指数移動平均法は，文献[18, 47, 14]でも使用されている．
ウェブサーバの起動時には，持続的接続時間は任意の値（例えばデフォルト値）
でよい．その後，式 (3.4)により徐々に適切な持続的接続時間へと近付けていく．