読者です 読者をやめる 読者になる 読者になる

Murakumo - 分散型負荷分散での振り分けの平均化について

EC2

分散型内部DNSサーバ - Murakumo 0.3.8をひっそりとリリースしました。
画期的だと思うんですが、話題のわの字にも上りません。悲しいなぁ…

分散型負荷分散での振り分けの平均化について

Murakumo 0.3.8では振り分けの新しいアルゴリズムとして、fix_by_srcという実装を追加しました。
いままで乱数で振り分けていたので試行回数が少ないと偏りが出ましたが、これによって少しは改善されるのではないかと考えています。

何をやっているのか?

ユースケースとして考えているのは以下のようなサーバ構成です。


以前までのバージョンでは、各AppサーバのRailsの問い合わせに対して、MurakumoノードはランダムにスレーブDBのIPを返していました。
コネクションプーリングをしないようにすれば、「試行回数が十分」ならそこそこ平均的に振り分けられます。

しかしコネクションプーリングをしていて、再接続までの間隔が長い場合、「試行回数が十分」とはいえないので、接続するスレーブDBが結構偏ってしまいます。
そこで接続元のIPアドレスごとに接続先を固定するような実装を追加しました。


たとえばApp×5・DB×2の場合、以下のように接続先が割り振られます。

IPアドレスでソートして、順番に接続先を決めているだけです。

なぜこんなことをしているのか?

1サーバに集約されたロードバランサーならラウンドロビンや最小接続数などですべての接続を適切に割り振ることができるのですが、ノードが各サーバに分散しているため情報を集約・同期することが困難です。
個々のノードでラウンドロビンなどをしてもどこまで意味があるかわかりませんし、DSNサーバなので問い合わせがRailsに限らず、digをたたいただけでもラウンドロビン対象として見なされます。
さらにコネクションを管理しているわけではないので、コネクションの情報を取ろうと思うとそれなりにトリックが必要になります。


…いろいろ考えた末、上記のような実装になりました。

いろいろな問題点

以下の問題があります。

  • 接続先が接続元より多いと、接続先にあまりが出る
  • 接続先が最小公約数じゃないと、端数分が偏る
  • 接続先・接続元が増減するとマッピングががらっと変わる

微妙ですね。
最後についてはコンシステント・ハッシング法を使おうかとも考えたのですが、結局ランダムに頼ってるので試行回数が少ないと偏り、うまくいきませんでした。

fix_by_src/fix_by_src2

実装としてはfix_by_src/fix_by_src2の二種類を用意しました。基本的にはどちらも同じアルゴリズムですが、複数IPアドレスを返す場合に2番目以降のアドレスの順序が異なります。

fix_by_src(無印)では、2番目以降のアドレスは一応ソートして返します。たとえば「1,2,3,4,5」と内部データベースに登録されていた場合に、接続元サーバに紐付くIPアドレスが3だとすると返される順序は「3,4,5,1,2」となります。
fix_by_src2の場合、2番目以降のランダムに返されます。無印の例だと「3,2,4,1,5」と返されたり、[3,5,2,1,4」と返されたり問い合わせによってまちまちです。
これはフェイルオーバー時の挙動を考慮しています。先頭アドレスが死んでいて、クライアント側が次のIPアドレスに接続する場合、順序が固定されていると接続が偏ってしまいます。これをランダムに返しておけば、一つのサーバに偏ることはある程度避けられます*1

その他

正直微妙な実装なのですが他によい手段も思い浮かばず…。分散環境でリアルタイムなデータの同期を実装するアイデアも根性もないので、こんな実装になってしまいました。
まあ、バランシング部分のソースは切り出してあるので、アルゴリズムの追加自体は容易です。
何かよい実装を知っている方がいたら、情報・パッチをお待ちしていますm(_ _)m

*1:複数IPアドレスでソート順を制御する場合はgai.confの修正が必要