2008-08-12

待ち行列に入門した

先週, 会社をさぼって システム性能評価と待ち行列理論 という講義を受けてきた. 待ち行列理論の入門講義で, 大学の学部でやるレベルの話らしい. 私は学部でも学部以外でも勉強したことがない話題だったので, とても興味深く聞いた.

受講後はすっかり盛り上り, 待ち行列で性能評価するぜ! という気分になったのだが, 実際は難しい. 性能評価一般の難しさはさておくとして, 待ち行列理論そのものがけっこう複雑. 数学が苦手な身には辛い. 理論の常として, 待ち行列の理論もまず解析対象の特性に様々な制限や前提を設けた上でモデルをたてる. そのモデルがうまく解析できたら, 少しずつ制限をとりはずしていく. 現実を扱えるモデルに至る道程は険しそうだ. 高価なツールを使えばそんな洗練されたモデルも扱えるのかもしれないけれど, もうちょっと庶民に優しい路線であってほしい.

解析に挫ける一方, 理論の成果が明らかにする様々な知見には面白いものも多かった. 性能の挙動は非線形で, 直感的でないこと. 性能の上限に近づくほど設計の違いが顕著に現れること. 性能上の問題を事前に明らかにできる可能性と, その意義. 脳味噌の性能不足でこうした知見を生かせないのは悲しい. 解析的に解けなくても, せめて数値的には解けないものか. 近似だって何もないよりはいいはずだ. たぶん.

というわけで, ちょっとコードを書いてみた. 若者ぶるには github を使えと指導をうけたため, コードは github へ. disque と命名. (名前つけるような規模じゃないけどね...)

disque in action

disque のコード自体はどうでもいいベタなものだけれど, 動かしてみると色々面白かった. いくつか紹介.

まず, 一番素朴な待ち行列網から. こんなグラフが...:

こんなコードになる.

engine = Engine.new
e = engine.new_emitter(ExponentialDistro.new(100))
r = engine.new_receiver
q = engine.new_queue
s = engine.new_server(NormalDistro.new(100, 50))

e.connect_to(q)
q.connect_to(s)
s.connect_to(r)

engine.resolution =    1*1000
engine.duration   = 5*60*1000
engine.run

Disque::write_csv(STDOUT, engine.samplers, :nwait)

Emitter はある間隔でリクエスト(Queue の要素)を発行する. ここでは指数分布(exponential distribution)をとる平均 100ms 間隔での リクエストを発行している. Server は Queue にたまったリクエストをとりだして処理し, 結果を Receiver に引き渡す. 処理には所定の時間がかかる. ここでは処理時間を平均 100ms, 分散 50 の正規分布としている.

disque エンジンはこの条件で 5*60*1000ms = 5 分間相当のシミュレーションを行い, Queue の要素数(=待ち行列の長さ!) などを 1000ms 間隔で記録する. もちろんほんとに 5 分かかるわけではない. 計算はすぐおわる.

実行結果のチャートはこんなかんじ:

横軸が時間で, 縦軸がキューの待ち時間(秒). 1 リクエストあたり 100ms しかかからないサーバを相手に, ある瞬間は 70 秒も待っている. これはサーバの処理性能とリクエストの到着率(どちらも毎秒 10 リクエスト)が拮抗しているためだ. それにしても折れ線の挙動が妙に生々しいなあ...

ためしにサーバをちょっと速く(80ms)してみる:

ピークが 18 秒まで減った. でも結構遅い. 分散が大きすぎるのかも... という風に色々わかる.

ところで, 確率分布であっさり正規分布を使えるのは数値計算のいいところ. 初歩の(=私が先週習った)解析は, 分布が指数分布であることに依存してるからね.

レジ待ち対決

待ち行列で有名なのは, スーパーのレジや銀行の ATM に並ぶとき, 全体で一列に並ぶのとレジ毎でバラバラに並ぶのとではどちらが早いかという分析の結果だろう. 左が一列ならび, 右がバラバラ並びね:

disque で書くとこうなる:

nemitters = 4

# 一列並び
fq = engine.new_queue("fork") # キューは 1 個
fr = engine.new_receiver
nemitters.times do |i|
  fe = engine.new_emitter(ExponentialDistro.new(100))
  fs = engine.new_server(NormalDistro.new(100, 50))
  fe.connect_to(fq)
  fq.connect_to(fs)
  fs.connect_to(fr)
end

# バラバラ並び
cr = engine.new_receiver
nemitters.times do |i|
  ce = engine.new_emitter(ExponentialDistro.new(100))
  cs = engine.new_server(NormalDistro.new(100, 50))
  cq = engine.new_queue("cs#{i}")  # キューは n 個
  ce.connect_to(cq)
  cq.connect_to(cs)
  cs.connect_to(cr)
end

結果は...:

埋もれてしまってわかりにくいけど, 青い "fork" という線が一列並びの待ち時間を表す. スパイクもなく, バラバラ並び ("cs") と比べても少い値を維持しているのがわかる. ちゃんと解析の結果と一致している.

負荷分散対決

一列並びの例では, サーバがキューからリクエストをとりだすと仮定していた. ただし現実がいつもそうとは限らない. たとえばロードバランサは一種のキューとして振る舞うけれど, キュー(バランサ自身)からサーバへ リクエストを "プッシュ" する. これはサーバ側からキューを読む元々のモデルと異なる. キューからプッシュするこの方式だと, サーバを完全に効率的には使い切れない. プッシュ先の選び方がまずいとヒマなサーバがでてしまう. ではどんな選び方がいいのか.

先に結論からいくと, 先の講義ではラウンドロビン方式とランダム方式を比較し, ラウンドロビン方式がより効率的であることを解析から示していた. 私はこのへんからおいてけぼりモードだったので, disque で復習(?)しよう:

def connect_to_balancer(engine, b, nemitters, prefix)
  nemitters.times do |i|
    e = engine.new_emitter(ExponentialDistro.new(100))
    q = engine.new_queue("#{prefix}#{i}")
    s = engine.new_server(NormalDistro.new(100, 50))
    r = engine.new_receiver
    e.connect_to(b)
    b.connect_to(q)
    q.connect_to(s)
    s.connect_to(r)
  end
end
...
round = engine.new_balancer(RoundRobinChoice.new)
connect_to_balancer(engine, round, 4, "round")
random = engine.new_balancer(RandomChoice.new)
connect_to_balancer(engine, random, 4, "random")

結果:

たしかにラウンドロビン(紫色)の方が短い待ち時間に留まっている. 解析の結果と同じだ. めでたしめでたし.

...と言いたいところなんだけど, ちょっと条件を変えると雲行きが怪しくなる. 先の例では, サーバ処理時間の分布に正規分布を使っていた. これを指数分布に変更してみる.

    s = engine.new_server(ExponentialDistro.new(100))

すると...:

橙色の線, ランダム方式がラウンドロビン方式の待ち時間を下回ってしまった! なんてこったい. 話が違うじゃん...

二つの差は一つ前のグラフより僅差だ. シミュレーション時間を延ばしたり, 乱数の種を変えたりすれば, また逆転するかもしれない. いずれにせよ, 解析のような絶対正しい答えを出せない数値計算の弱さがはやくも露呈してしまった.

実践にむけて

ひととおり遊び気も済んだところで少し考えごとを.

まずベンチマークのこと. 素朴なベンチマークでは負荷をありったけかけて, このスループットまではいけますという指標をだす. この "ありったけ" の部分は一定間隔でリクエストを発行しがちだけれど, 実際は適当な確率分布(たぶん指数分布でよい)を使って間隔を揺らした方が良さそうだ. そうしないと, 瞬間的に負荷がかかるケースをベンチマークで洗いだせない. ベンチマークでは動いたのに実戦ではボロボロとタイムアウト...なんてのは 想像するだけで冷や汗がでる. また, ベンチマークではクライアント側で接続時間やタイムアウト率も記録に残した方がよい. 危険な兆候がわかるからね. 前に自分が書いたベンチマークは タイムアウト率を記録してなかった気がする...

あとはサーバのタスク構成のこと. 高負荷時に不安定になるサーバは設計がまずいのだが, 具体的に何がまずいのか少しわかった. 負荷を野放しにしているのがまずいんだな. わかりやすいのは認証やメッセージのブロードキャストなど, 計算負荷の高いリクエストが短時間に集中するケース. 素朴に作られたサーバだと, 各セッション(スレッド)がみな一斉に要求を 処理しようとして理不尽な高負荷になる. 資源の奪い合いがおき, 予測できない振舞いに繋がる. 資源が足りないと過負荷の出所とは無関係なジョブも圧迫される. これが高負荷時の安定を損ねている.

負荷を制御するには, 高負荷なリクエストを一旦キューに積み, 資源の様子を見ながら順に処理していけば良いのだろう. "キューの長さ" というわかりやすい形で負荷の状況を監視できるし, 同時に処理するリクエスト数を増減することで資源の占有率を調整できる. 言われて見れば世のサーバはそんな作りになっている気がする. ちゃんと意識してなかった.

プロセスをまたぐ場合は各種 MQ がまさにキューの役割を果たすし, インプロセスでスレッドをまたぐならワーカプールが使える. タスクベースの実装でも, 同じような抽象を用意して積極的に使うべきなのだろう.

というようなことを考えた夏休みの一日でした.