Preliminary Study on DNS Load Balancing and Efficiency of Cache

DNS の負荷分散とキャッシュの有効性に関する予備的
検討
Preliminary Study on DNS Load Balancing and Efficiency
of Cache
服部 敦 1
1
東京電機大学 理工学研究科
藤本 衡 2
2
東京電機大学 理工学部
概要
大規模組織での DNS キャッシュサーバでは、利用者からの DNS クエリをロードバランサ
によって複数のサーバに分配する運用がしばしば見られる。しかし、DNS におけるキャッ
シュヒット率は単位時間あたりのクエリ到着数に比例するため、ロードバランシングによっ
てヒット率が（ロードバランシングを行わない場合に比べて）低下するおそれがある。本
研究では、実際に得られたクエリの到着時刻情報を用い、いくつかのロードバランシング
ポリシーにおけるヒット率の比較を行う。
1
はじめに
DNS プリフェッチ [3] も実装されているが、
処理が重くなるなどの理由により、必ずし
も UX 向上には繋がっていないとも言われ
ている。キャッシュの効果については、DNS
キャッシュヒット率を計測することで生存
時間（TTL）を適切に調整する研究 [4, 5]
が行われている。
また、キャッシュサーバの処理遅延を避
けるため、ネットワーク内にキャッシュサー
バを複数配置し、ロードバランサによって
負荷分散を行う構成もしばしば見られる。
しかし、キャッシュサーバが複数になるこ
とで逆にキャッシュ効率が低下する懸念も
ある。ロードバランシングに関する数理的
な評価の試みもある [6] が、処理待ち時間
の解析が主でありキャッシュヒット率には
注目していない。また、リクエストの到着
間隔を指数分布にするなど、必ずしも実際
のシステムを十分に反映できているとは言
Web ページの表示に要する時間は、ユー
ザエクスペリエンス（UX）を高め顧客を
維持するために重要な指標となっている。
2000 年以前の ISDN/ADSL 時代に 8 秒と
されていた [1] 目安は、ブロードバンドの
普及に伴うユーザの「慣れ」とともに短く
なり、2009 年には 47% の消費者が 2 秒以
内にページ表示が行われることを望んでい
るという調査結果 [2] が示された。このよう
にコンテンツ表示に費やすことが可能な時
間が短くなるにつれ、その前処理として必
要なドメイン名の解決に要する時間は（相
対的に）大きくなる。
DNS を用いたドメイン名解決では、従
来よりリゾルバおよびキャッシュサーバに
おけるキャッシュを用いた高速化が図られ
ている。近年では、クライアント側による
1
メイン名に関する要求を集約してコンテン
ツサーバの負荷を軽減するとともに、キャッ
シュの有効性を高めリゾルバの応答時間を
短縮することが可能となる。
えない。
そこで、本研究ではキャッシュサーバに
到着するドメイン名解決リクエストを計測
し、到着時間間隔およびドメイン名解決に
要する時間の経験分布を導く。そして、ロー
ドバランサを用いないキャッシュサーバと、
ラウンドロビンもしくはランダム振り分け
による負荷分散を用いたキャッシュサーバ
のシミュレーションを行い、キャッシュヒッ
ト率を比較する。
2
2.1
複数キャッシュサーバによる構成
多くのホストを収容する大規模ネットワー
クにおいては、キャッシュサーバへの負荷
も増大するため、負荷分散を検討する必要
がある。また、キャッシュサーバが故障等
で停止する場合を考慮し、予備機を用意す
ることも重要である。
一般的なリゾルバ実装では複数（2 ない
し 3）のキャッシュサーバを設定できる。障
害対応が主目的でありキャッシュサーバの
数が少ない場合は、このようなリゾルバ側
での対応も有効である。しかし、リゾルバ
は指定した順にドメイン名解決要求を送る
ので、この方法は負荷分散という用途には
適していない。
したがって、負荷分散を目的としたより
大規模なキャッシュサーバでは、キャッシュ
サーバの前段にロードバランサを配置し、
リゾルバはロードバランサに要求を送ると
いう構成をとる。ロードバランサからキャッ
シュサーバへの要求転送では、処理速度を
重視して単純なポリシーを採用する場合も
あり、一方で各サーバの負荷状況や要求内
容に応じた複雑なポリシーを採用する場合
もある。
本研究では、n 台のキャッシュサーバ群へ
の要求転送に際してロードバランサが以下
の 2 つのポリシーを用いる場合を想定し、
単一キャッシュサーバ構成との間でキャッ
シュヒット率を比較する。
DNS について
DNS(Domain Name System)[7] は、ド
メイン名と IP アドレスの対応付けを管理
するシステムである。DNS の構成を図 1 に
示す。
図 1: 一般的な DNS の構成
DNS によるドメイン名解決を要求するク
ライアントはリゾルバ（スタブリゾルバ）
と呼ばれる。リゾルバは OS の機能、ある
いはライブラリやソフトウェアとして用意
されており、OS 上で動作するアプリケー
ションソフトウェアの要求に応じてドメイ
ン名解決を行う。コンテンツサーバはリゾ
ルバの要求に対し、自らが管理する情報を
返信する。
一般的なネットワークにおいては、ネッ
トワーク上の各リゾルバから送られる解決
要求を取りまとめ、外部のコンテンツサー
バに転送するキャッシュサーバ（フルサービ
スリゾルバ）を置く。これにより、同一ド
1. ラウンドロビンポリシー: 到着した名
前解決要求を順にサーバ 1、サーバ 2、
. . .、サーバ n へと送り、(n + 1) 番目
の要求は再びサーバ 1 へと送る。
2
• resolver : 名前解決、再帰問い合わせ
の処理
2. ランダムポリシー：要求ごとに区間
[1, n] 上の一様整数乱数 U を生成し、
サーバ U へ要求を転送する。
図 3 は実際に BIND が出力したログの例
である。ドメイン名 www.google.com の A
レコードを要求する問い合わせであり、上
位への反復問い合わせがないままリゾルバ
に結果が送信されているため、キャッシュ
ヒットした問い合わせであることがわかる。
データ計測
3
本研究では、東京電機大学の DNS キャッ
シュサーバ群におけるドメイン名解決要求
を観測し、以降の解析に用いた。
観測対象のキャッシュサーバ群は、ロー
ドバランサによる負荷分散を行っている。
ネットワーク内のリゾルバはロードバラン
サに対してアクセス要求を送信し、ロード
バランサはラウンドロビンポリシーに基づ
いて要求を各キャッシュサーバに転送して
いる。図 2 にキャッシュサーバ群の構成概
要を示す。
client: debug 3: client 133.20.1.1#14866: UDP request
client: debug 5: client 127.0.0.1#14866: using view
’_default’
client: debug 3: client 127.0.0.1#14866: query
queries: info: client 127.0.0.1#14866: query:
www.google.com IN A +
client: debug 10: client 127.0.0.1#14866:
ns_client_attach: ref = 1
client: debug 3: client 127.0.0.1#14866: send
client 127.0.0.1#14866: sendto
client 127.0.0.1#14866: senddone
client 127.0.0.1#14866: next
client 127.0.0.1#14866: ns_client_detach: ref = 0
client 127.0.0.1#14866: endrequest
図 3: BIND ログの例
ログの保存や転送などがキャッシュサー
バ本来の処理に影響を与えないよう、別途
ログ収集用のホストを用意し syslogd を介
してログの受信を行った。収集されたログ
すべてを用いることで、ロードバランサに
到着しているすべての名前解決要求を観測
できたことになる。
このように収集されたログから、以下の
情報を取得した。
図 2: 観測対象サーバ群の構成
3.1
計測方法
• 解決対象ドメイン名
観測対象の DNS キャッシュサーバでは、
DNS のサーバソフトウェア BIND が使用
されているため、BIND の logging 機能を
使用して DNS 名前解決のログを収集した。
logging 機能では、BIND の処理内容に応じ
て出力を取捨選択できるため、本研究では
以下のカテゴリについてデバッグレベル 10
で出力するように設定した。
• 解決要求の受信時刻
• 解決要求に対する応答の送信時刻
• キャッシュヒットの有無
3.2
要求の到着間隔と処理時間
前節で得られた計測データから、特定の
ドメイン名に関する名前解決要求の到着間
隔分布、および応答時間分布の相対頻度が
得られる。ただし、キャッシュミスした場
• client : クライアントの要求処理
• queries : BIND が受信した問い合わ
せ
3
prob.
合には上位への反復問い合わせを必要とす
るため 0.1 秒オーダーでの応答時間を要す
るのに対して、キャッシュヒットした場合
は十分に無視できるほど小さい応答時間と
なる。そこで、以下ではキャッシュヒット
した場合の応答時間は無視している。
図 4 は、ドメイン名 www.google.com に
対する名前解決要求の到着間隔を累積分布
として表したグラフである。
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0.01
0.1
1
prob.
response time[s]
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
図 5: キャッシュミスした要求の応答時間累
積分布
キャッシュサーバ i (i = 1, 2, . . . , n) に
要求を転送する。
1
10
100
1000
3. キャッシュサーバ i では、以下の基準
でキャッシュヒットかミスかを判定す
る。
10000
interarrival time[s]
(a) キャッシュが存在しない場合、キ
ャッシュミスとする。このとき、
同一ドメインの要求処理中でな
ければ、応答時間分布に基づく
乱数を発生させ、要求処理に入
る。要求処理中に到着する同一
ドメインの要求は、同じくキャッ
シュミスとする。
図 4: 要求の到着間隔累積分布
図 5 は、ドメイン名 www.google.com に
対する名前解決要求のうちキャッシュミス
したものに限定して、応答終了までの時間
を累積分布として表したグラフである。計
測データに限れば、すべての要求は 1 秒以
内に応答しており、キャッシュミスした要
求の処理中に同じドメイン名に対する要求
が来ることはほぼ無いと考えてよい。
4
(b) キャッシュが存在する場合は、キ
ャッシュヒットとする。
4. キャッシュサーバ i は要求処理の完了
とともに、キャッシュが存在する状態
へと移行し、TTL のカウントダウン
を開始する。TTL が 0 になった場合、
キャッシュを消去する。
シミュレーションによる解析
3.2 節で得られた到着間隔分布および応
答時間分布に基づき、以下のようなシミュ
レーションを行う。
以下では、名前解決要求を 10000 個発生
させてキャッシュミス率を求めるシミュレー
ションを 1 試行とし、10000 試行の結果か
ら平均および 95%信頼区間を求めた。
1. 名前解決要求が、到着間隔分布に従
うランダムな間隔でロードバランサ
に到着する。
2. ロードバランサはラウンドロビン、も
しくはランダムポリシーにしたがって
4
4.1
到着間隔の影響について
4.2
TTL 値の影響について
次に、到着間隔分布を実測値にしたがう
ものに固定し、キャッシュ生存時間（TTL）
を変化させた時のキャッシュミス率の変動
を求めた。
図 7 は 4.1 節と同じ www.google.com の
要求到着間隔と応答時間の分布を用い、TTL
を 30 から 30000（秒）まで変化させた結果
である。TTL 値が大きくなればキャッシュ
ミス率は無視できるほど小さくなるが、一
方で TTL が 30 の時には特にラウンドロビ
ンポリシーによる負荷分散でキャッシュミ
ス率が極端に悪化していることがわかる。
Twitter などいくつかの主要サービスでは
60 秒程度の TTL を設定していることから、
キャッシュ性能の低下に対しては何らかの
対策を検討する必要があると考えられる。
まず、n = 5 のキャッシュサーバ群におい
て、ラウンドロビンポリシーとランダムポ
リシーでのキャッシュミス率を求め、n = 1
（単一キャッシュサーバ）の場合と比較した。
到着間隔分布の値をスケーリングし、より
短い到着間隔の場合にキャッシュミス率が
どのように変化するかを図 6 に示す。
図 6 はドメイン名 www.google.com に関
する分布を用い、TTL が 300 秒と仮定し
たシミュレーションである。グラフは対数
軸で表現されており、実測値そのままのタ
イムスケール（横軸が 1）においては複数
キャッシュサーバとすることでキャッシュミ
ス率が 4 倍にもなる可能性を示している。
また、ラウンドロビンポリシーに比べると
ランダムポリシーの方が若干キャッシュミ
ス率が低下することがわかる。
また、タイムスケールを短くする（すな
わち単位時間あたりの到着頻度を高める）
ことにより、この差は減少していくことが
わかる。10−3 ではかなり差が小さくなり、
10−4 では信頼区間が重なるため優劣が分か
らない結果となった。計測対象のキャッシュ
サーバが受け入れるリゾルバの概数は 1 万
台のオーダーであると推測されるため、大
手の ISP であれば複数キャッシュサーバを
用いることによるキャッシュミス率の差は
無視できるレベルになると期待される。
図 7: TTL の変化に伴うキャッシュミス率
の変動
5
まとめ
本研究では、負荷分散を目的として複数
の DNS キャッシュサーバとロードバラン
サによる構成をとった場合に、キャッシュ
ヒット率に与える影響をシミュレーション
によって比較した。
その結果、数万加入者規模のサイトにお
いては、キャッシュサーバを複数台にするこ
とでキャッシュヒット率が低下することが
図 6: 到着間隔の時間スケール変化に伴う
キャッシュミス率の変動
5
確認できた。その一方で、数百万台以上の
規模であれば、キャッシュヒット率の差は無
視できるレベルであることが示唆された。
キャッシュヒット率低下を避ける対策と
しては、たとえば解決要求の対象となるド
メイン名からハッシュ値を生成し、ハッシュ
値に基づいて要求を転送する方法が考えら
れる。ただし、ロードバランサでこうした
パケット内の情報に基づくポリシーを実装
するには処理時間など様々な課題があり、
今後の検討課題と言える。
3.2 節で示した要求の到着間隔分布およ
び応答時間分布は、ドメイン名によって明
らかに異なっており、また計測対象となる
ネットワークによっても異なるものと推測
される。今後はそれらを網羅的に表現でき、
十分な精度でキャッシュヒット率の近似値
を与える分布形の提案と、それを用いたモ
デル構築を行うことが求められる。
[4] Jung J., Sit E., and Balakrishnan
H., DNS Performance and the Effectiveness of Caching, IEEE/ACM
Transactions on Networking, 10(5),
pp.589–603, 2002.
[5] Jung J., Berger A. W., and Balakrishnan H., Modeling TTL-based Internet Caches, IEEE Infocom, 2003.
[6] 藤原飛一, 紀一誠, (2-2) 間引きシステ
ム入力待ち行列の解析, 日本オペレー
ションズ・リサーチ学会和文論文誌, 54,
pp.43–57, 2011.
[7] Mockapetris P., Domain Names —
Concepts and Facilities, RFC 1034,
1987.
参考文献
[1] インセプト, 8 秒ルール, IT 用語辞典
e-Words,
http://e-words.jp/w/8E7A792E38
3ABE383BCE383AB.html,
2014/04/30.
[2] Akamai Technologies, Akamai Reveals 2 Seconds as the New Threshold
of Acceptability for eCommerce Web
Page Response Times, press release,
http://www.akamai.com/html/abo
ut/press/releases/2009/press_09
1409.html, 2009/09/14.
[3] DNS Prefetching, The Chromium
Projects,
http://www.chromium.org/develop
ers/design-documents/dns-prefet
ching, 2014/05/01.
6