DNSの負荷分散とキャッシュの有効性に関する予備的検討 東京電機大学服部敦藤本衡
発表の流れ 研究背景 目的 DNS キャッシュとロードバランス DNS query データ計測 キャッシュミス率のシミュレーション まとめと今後の課題 2
研究背景 Web ページの表示時間 UX に大きな影響がある ネットワーク環境の向上 2000 年以前は8 秒 現在では2 秒以内 名前解決に要する時間が相対的に大きくなる インターネットにおける DNS トラフィック増加 3
DNS キャッシュ 名前解決で得た情報をキャッシュ リソースレコードの情報を TTL の期間保持 キャッシュによる高速化 反復 再帰問い合わせを行わずに名前解決 キャッシュヒット率が UX の向上に繋がる 4
キャッシュミスした名前解決 ルート DNS サーバ 結果をキャッシュ www.example.jp の IP アドレスは? jp の DNS サーバ キャッシュサーバ クライアント PC example.jp の DNS サーバ 5
キャッシュヒットした名前解決 ルート DNS サーバ キャッシュ有 www.example.jp の IP アドレスは? jp の DNS サーバ キャッシュサーバ クライアント PC example.jp の DNS サーバ 6
TTL とヒット率に関する研究 Jung, et.al. (2002) MIT, KAIST で DNS query データの計測 キャッシュヒット率と遅延の評価 TTL がヒット率に大きく影響するのは 1000[s] 未満 Jung, et.al. (2003) キャッシュヒットを再生過程を使ってモデル化 7
DNS における負荷分散 複数のサーバに要求を分散して転送 負荷による処理遅延を防ぐ 障害発生時のシステムダウンを回避 8
キャッシュサーバの負荷分散 結果をキャッシュ キャッシュサーバ www.example.jp の IP アドレスは? キャッシュサーバ ロードバランサ クライアント PC キャッシュサーバ 9
キャッシュサーバの負荷分散 キャッシュサーバ キャッシュ有 www.example.jp の IP アドレスは? キャッシュサーバ ロードバランサ クライアント PC キャッシュサーバ 10
キャッシュと負荷分散 ロードバランスによるキャッシュ効率 複数のキャッシュサーバに負荷分散するとキャッシュ効率が低下する キャッシュ効率を考えた負荷分散 キャッシュヒット率を向上できる 11
研究目的 DNS query データの計測 クエリの到着時間間隔の経験分布 名前解決に要する時間の経験分布 負荷分散のシミュレーション 負荷分散なし ラウンドロビン ランダム キャッシュミス率の比較 キャッシュ効率を考えた負荷分散へ 12
発表の流れ 研究背景 目的 DNS キャッシュとロードバランス DNS query データ計測 キャッシュミス率のシミュレーション まとめと今後の課題 13
経験分布算出に必要なデータ 名前解決対象のドメイン名 名前解決要求の到着時刻 名前解決に対する応答送信時刻 キャッシュヒットの有無 14
経験分布算出に必要なデータ クライアントキャッシュサーバ権威サーバ権威サーバ キャッシュヒットした名前解決 キャッシュで解決 クエリ到着時刻 応答送信時刻 クエリ到着時刻 反復問い合わせ キャッシュミスした名前解決 反復問い合わせ 応答送信時刻 15
logging 機能の設定 カテゴリ client クライアントの要求処理のログを出力 queries 問い合わせログの出力 resolver 名前解決 リゾルバからの再帰的な問い合わせ処理のログを出力 デバッグレベル 10 16
ログメッセージ キャッシュヒットした名前解決 クライアントキャッシュサーバ権威サーバ権威サーバ client UDP request キャッシュで解決 client endrequest クエリ到着時刻 queries www.example.jp IN A 応答送信時刻 反復問い合わせ キャッシュミスした名前解決 resolver query resolver response 17
計測対象 東京電機大学の DNS キャッシュサーバ BIND9.8.2 18
計測対象の構成 プライベートネットワーク キャッシュサーバ 負荷分散 再帰問い合わせ キャッシュサーバ ロードバランサ rsync 反復問い合わせ キャッシュサーバ 19 syslog ログ収集ホスト
シミュレーションに使用するデータ 期間 :2013 年 9 月 18 日 ~2013 年 10 月 18 日 総クエリ数 :16,520,247 クエリタイプ別 クエリタイプ クエリ数 A 10,775,220 AAAA 3,613,683 PTR 1,274,047 MX 340,420 ANY 183,185 SRV 138,889 TXT 106,277 20 クエリタイプ クエリ数 SOA 65,416 DLV 11,853 NS 8,918 DS 1,217 CNAME 489 DNSKEY 423 RRSIG 104
経験分布を算出したドメイン名 A レコードの問い合わせトップ 10 ドメイン名 クエリ数 TTL www.google.com 754,192 300 time.apple.com 277,953 7200 e3191.dscc.akamaiedge.net 234,623 20 us-courier.push-apple.com.akadns.net 168,075 60 6to4.ipv6.microsoft.com 128,090 3600 www.bluecoat.com 114,727 7200 ipv6.msftncsi.com 109,936 1000 www.msftncsi.com 90,235 20 twitter.com 89,234 30 api.twitter.com 82,532 30 21
到着間隔分布 ( 累積分布 ) www.google.com 22
到着間隔分布 ( 累積分布 ) e3191.dscc.akamaiedge.net 23
到着間隔分布 ( 累積分布 ) us-courier.push-apple.com.akadns.net 24
到着間隔分布 ( 累積分布 ) www.bluecoat.com 25
到着間隔分布 ( 累積分布 ) www.msftncsi.com 26
到着間隔分布 ( 累積分布 ) twitter.com 27
到着間隔分布 ( 累積分布 ) api.twitter.com 28
応答時間分布の算出 キャッシュヒット時の応答時間 名前解決に要する時間がほぼ0であった 最大で0.001 秒程度 キャッシュミス時の応答時間を集計 29
キャッシュミス時の応答時間分布 www.google.com ( 累積分布 ) 30
キャッシュミス時の応答時間分布 e3191.dscc.akamaiedge.net ( 累積分布 ) 31
キャッシュミス時の応答時間分布 us-courier.push-apple.com.akadns.net ( 累積分布 ) 32
キャッシュミス時の応答時間分布 www.bluecoat.com ( 累積分布 ) 33
キャッシュミス時の応答時間分布 www.msftncsi.com ( 累積分布 ) 34
キャッシュミス時の応答時間分布 twitter.com ( 累積分布 ) 35
キャッシュミス時の応答時間分布 api.twitter.com ( 累積分布 ) 36
発表の流れ 研究背景 目的 DNS キャッシュとロードバランス DNS query データ計測 キャッシュミス率のシミュレーション まとめと今後の課題 37
シミュレーションの概要 パラメータ 到着時間間隔分布 応答時間分布 TTL キャッシュサーバ数 タイムスケール キャッシュミス率をシミュレーション 38
シミュレーションの設定 名前解決要求の到着間隔 到着間隔分布に従うランダムな間隔で到着 ロードバランサの振る舞い ラウンドロビン ランダムポリシーで割り振り キャッシュミスした場合 応答時間分布に基づく乱数を発生させ 要求処理状態へ 処理中の同一ドメインへの要求はミスとする 39
シミュレーションの設定 要求処理が完了後にキャッシュ保持状態 TTLのカウントダウンを開始 TTLが0になったらキャッシュを消去 キャッシュヒットした場合の処理時間は0 単一のドメイン名からの要求 シミュレーションの試行回数 1 試行で名前解決要求を10000 個発生 10000 試行の結果から平均 信頼区間を算出 40
シミュレーション 1 各ポリシーのキャッシュミス率を比較 TTL:30~30000 キャッシュサーバ数 :5 タイムスケール :1 41
TTL を変化させたキャッシュミス率 www.google.com 42
シミュレーション 2 サーバ数を変化させキャッシュミス率を比較 TTL:1~100,000 キャッシュサーバ数 :2~10 タイムスケール :1 43
サーバ数を変化させたミス率 www.google.com ランダム 44
サーバ数を変化させたミス率 www.google.com ラウンドロビン ランダムより著しく悪化している 45
時間帯別の到着間隔 時間帯別で到着間隔は変化するはず 人のいる時間帯 ( 日中 ) は要求が多い 人のいない時間 ( 深夜 ) は要求が少ない キャッシュミス率も異なるのでは? 46
時間帯毎のクエリ数 www.google.com 47
時間帯毎のクエリ数 e3191.dscc.akamaiedge.net 48
時間帯毎のクエリ数 us-courier.push-apple.com.akadns.net 49
時間帯毎のクエリ数 www.bluecoat.com 50
時間帯毎のクエリ数 www.msftncsi.com 51
時間帯毎のクエリ数 twitter.com 52
時間帯毎のクエリ数 api.twitter.com 53
時間帯毎のクエリ 深夜から早朝にかけてクエリのピーク 予想とは違った時間帯にピークが来ている 機械的なクエリ 日中にクエリのピーク 機械的でないクエリ 54
時間帯別で到着間隔の算出 各ドメイン名の到着間隔を時間帯別に集計 00:00:00~05:59:59 06:00:00~11:59:59 12:00:00~17:59:59 18:00:00~23:59:59 55
時間帯別の到着間隔分布 www.google.com 56
時間帯別の到着間隔分布 e3191.dscc.akamaiedge.net 57
時間帯別の到着間隔分布 us-courier.push-apple.com.akadns.net 58
時間帯別の到着間隔分布 www.bluecoat.com 59
時間帯別の到着間隔分布 www.msftncsi.com 60
時間帯別の到着間隔分布 twitter.com 61
時間帯別の到着間隔分布 api.twitter.com 62
シミュレーション 3( 時間帯別 ) 時間帯毎のキャッシュミス率を比較 TTL:Aレコードに設定されている値 キャッシュサーバ数 :5 タイムスケール :1~10000 63
時間帯別のキャッシュミス率 www.google.com 負荷分散なし 64
時間帯別のキャッシュミス率 www.google.com ランダム 65
時間帯別のキャッシュミス率 www.google.com ラウンドロビン 66
時間帯別のキャッシュミス率 twitter.com 負荷分散なし 67
時間帯別のキャッシュミス率 twitter.com ランダム 68
時間帯別のキャッシュミス率 twitter.com ラウンドロビン 69
シミュレーション 4( 時間帯別 ) TTL を変化させキャッシュミス率を比較 TTL: A レコードに設定されている 0.1, 1, 10, 100, 1000 キャッシュサーバ数 :5 タイムスケール :1 70
TTL を変化させたキャッシュミス率 www.google.com 0 時 ~6 時 71
TTL を変化させたキャッシュミス率 www.google.com 6 時 ~12 時 72
TTL を変化させたキャッシュミス率 www.google.com 12 時 ~18 時 73
TTL を変化させたキャッシュミス率 www.google.com 18 時 ~24 時 74
TTL を変化させたキャッシュミス率 e3191.dscc.akamaiedge.net 0 時 ~6 時 75
TTL を変化させたキャッシュミス率 e3191.dscc.akamaiedge.net 6 時 ~12 時 76
TTL を変化させたキャッシュミス率 e3191.dscc.akamaiedge.net 12 時 ~18 時 77
TTL を変化させたキャッシュミス率 e3191.dscc.akamaiedge.net 18 時 ~24 時 78
TTL を変化させたキャッシュミス率 us-courier.push-apple.com.akadns.net 0 時 ~6 時 79
TTL を変化させたキャッシュミス率 us-courier.push-apple.com.akadns.net 6 時 ~12 時 80
TTL を変化させたキャッシュミス率 us-courier.push-apple.com.akadns.net 12 時 ~18 時 81
TTL を変化させたキャッシュミス率 us-courier.push-apple.com.akadns.net 18 時 ~24 時 82
TTL を変化させたキャッシュミス率 www.bluecoat.com 0 時 ~6 時 83
TTL を変化させたキャッシュミス率 www.bluecoat.com 6 時 ~12 時 84
TTL を変化させたキャッシュミス率 www.bluecoat.com 12 時 ~18 時 85
TTL を変化させたキャッシュミス率 www.bluecoat.com 18 時 ~24 時 86
TTL を変化させたキャッシュミス率 www.msftncsi.com 0 時 ~6 時 87
TTL を変化させたキャッシュミス率 www.msftncsi.com 6 時 ~12 時 88
TTL を変化させたキャッシュミス率 www.msftncsi.com 12 時 ~18 時 89
TTL を変化させたキャッシュミス率 www.msftncsi.com 18 時 ~24 時 90
TTL を変化させたキャッシュミス率 twitter.com 0 時 ~6 時 91
TTL を変化させたキャッシュミス率 twitter.com 6 時 ~12 時 92
TTL を変化させたキャッシュミス率 twitter.com 12 時 ~18 時 93
TTL を変化させたキャッシュミス率 twitter.com 18 時 ~24 時 94
TTL を変化させたキャッシュミス率 api.twitter.com 0 時 ~6 時 95
TTL を変化させたキャッシュミス率 api.twitter.com 6 時 ~12 時 96
TTL を変化させたキャッシュミス率 api.twitter.com 12 時 ~18 時 97
TTL を変化させたキャッシュミス率 api.twitter.com 18 時 ~24 時 98
シミュレーション 5( 時間帯別 ) キャッシュサーバ数によるキャッシュミス率 TTL:1~100000 キャッシュサーバ数 :2~10 タイムスケール :1 99
サーバ数を変化させたミス率 www.google.com 0 時 ~6 時 ランダム 100
サーバ数を変化させたミス率 www.google.com 0 時 ~6 時 ラウンドロビン 101
サーバ数を変化させたミス率 www.google.com 6 時 ~12 時 ランダム 102
サーバ数を変化させたミス率 www.google.com 6 時 ~12 時 ラウンドロビン 103
サーバ数を変化させたミス率 www.google.com 12 時 ~18 時 ランダム 104
サーバ数を変化させたミス率 www.google.com 12 時 ~18 時 ラウンドロビン 105
サーバ数を変化させたミス率 www.google.com 18 時 ~24 時 ランダム 106
サーバ数を変化させたミス率 www.google.com 0 時 ~6 時 ラウンドロビン 107
実測のミス率と比較 www.google.com 時間帯 実測値 シミュレーション 0-6 0.0161395 0.1578095 6-12 0.0147337 0.2152604 12-18 0.0148195 0.4218725 18-24 0.0154831 0.2599871 total 0.0154676 0.2286550 108
実測のミス率と比較 twitter.com 時間帯 実測値 シミュレーション 0-6 0.666927 0.999998 6-12 0.353979 0.999991 12-18 0.164821 0.999967 18-24 0.400568 0.999994 total 0.354693 0.999990 109
実測のミス率と比較 計測したデータを見てみると キャッシュミス数が明らかに少ない TTL が 0 になっているのにキャッシュで応答 110
発表の流れ 研究背景 目的 DNS キャッシュとロードバランス DNS query データ計測 キャッシュミス率のシミュレーション まとめと今後の課題 111
まとめ キャッシュ効率を考えた負荷分散 キャッシュミス率の比較 負荷分散なし ランダム ラウンドロビン キャッシュミス率が悪化するケース TTLが短い場合 キャッシュサーバ数を増した場合 クエリ数が少ない時間帯 112
今後の課題 キャッシュサーバごとの負荷について 複数ドメインの問い合わせに対応 実測のキャッシュミス率が明らかに低い ログを見ると TTL が 0 でもキャッシュで応答 キャッシュ効率を考えた負荷分散 113