DNSの負荷分散とキャッシュの有効性に関する予備的検討

(1)

DNSの負荷分散とキャッシュの

有効性に関する予備的検討

東京電機大学服部敦藤本衡

(2)

発表の流れ

• 研究背景・目的 – DNSキャッシュとロードバランス • DNS query データ計測 • キャッシュミス率のシミュレーション • まとめと今後の課題 2

(3)

研究背景

• Webページの表示時間 – UXに大きな影響がある • ネットワーク環境の向上 – 2000年以前は8秒 → 現在では2秒以内 – 名前解決に要する時間が相対的に大きくなる • インターネットにおけるDNSトラフィック増加 3

(4)

DNSキャッシュ

• 名前解決で得た情報をキャッシュ – リソースレコードの情報をTTLの期間保持 • キャッシュによる高速化 – 反復・再帰問い合わせを行わずに名前解決 • キャッシュヒット率がUXの向上に繋がる 4

(5)

キャッシュミスした名前解決

5 クライアントPC キャッシュサーバルートDNSサーバ jpのDNSサーバ example.jpの DNSサーバ www.example.jp のIPアドレスは？結果をキャッシュ

(6)

キャッシュヒットした名前解決

6 クライアントPC キャッシュサーバルートDNSサーバ jpのDNSサーバ example.jpの DNSサーバ www.example.jp のIPアドレスは？キャッシュ有

(7)

TTLとヒット率に関する研究

• Jung, et.al. (2002)

– MIT, KAISTでDNS queryデータの計測 – キャッシュヒット率と遅延の評価

– TTLがヒット率に大きく影響するのは1000[s]未満

• Jung, et.al. (2003)

– キャッシュヒットを再生過程を使ってモデル化

(8)

DNSにおける負荷分散

• 複数のサーバに要求を分散して転送 • 負荷による処理遅延を防ぐ

• 障害発生時のシステムダウンを回避

(9)

キャッシュサーバの負荷分散

9 クライアントPC ロードバランサキャッシュサーバキャッシュサーバキャッシュサーバ www.example.jp のIPアドレスは？結果をキャッシュ

(10)

キャッシュサーバの負荷分散

10 クライアントPC ロードバランサキャッシュサーバキャッシュサーバキャッシュサーバ www.example.jp のIPアドレスは？キャッシュ有

(11)

キャッシュと負荷分散

• ロードバランスによるキャッシュ効率 – 複数のキャッシュサーバに負荷分散するとキャッシュ効率が低下する • キャッシュ効率を考えた負荷分散 – キャッシュヒット率を向上できる 11

(12)

研究目的

• DNS queryデータの計測 – クエリの到着時間間隔の経験分布 – 名前解決に要する時間の経験分布 • 負荷分散のシミュレーション – 負荷分散なし・ラウンドロビン・ランダム • キャッシュミス率の比較 • キャッシュ効率を考えた負荷分散へ 12

(13)

発表の流れ

(14)

経験分布算出に必要なデータ

• 名前解決対象のドメイン名 • 名前解決要求の到着時刻 • 名前解決に対する応答送信時刻 • キャッシュヒットの有無 14

(15)

経験分布算出に必要なデータ

15 クエリ到着時刻応答送信時刻クライアントキャッシュサーバ権威サーバ権威サーバキャッシュヒットした名前解決キャッシュミスした名前解決キャッシュで解決応答送信時刻反復問い合わせ反復問い合わせクエリ到着時刻

(16)

logging機能の設定

• カテゴリ – client • クライアントの要求処理のログを出力 – queries • 問い合わせログの出力 – resolver • 名前解決、リゾルバからの再帰的な問い合わせ処理のログを出力 • デバッグレベル10 16

(17)

ログメッセージ

17 クエリ到着時刻応答送信時刻クライアントキャッシュサーバ権威サーバ権威サーバキャッシュヒットした名前解決キャッシュミスした名前解決反復問い合わせキャッシュで解決

client UDP request

client endrequest

resolver query resolver response queries www.example.jp IN A

(18)

計測対象

• 東京電機大学のDNSキャッシュサーバ • BIND9.8.2

(19)

計測対象の構成

19 キャッシュサーバキャッシュサーバキャッシュサーバロードバランサログ収集ホスト再帰問い合わせ負荷分散反復問い合わせ syslog プライベートネットワーク rsync

(20)

シミュレーションに使用するデータ

• 期間：2013年9月18日～2013年10月18日 • 総クエリ数：16,520,247 • クエリタイプ別 20 クエリタイプクエリ数 A 10,775,220 AAAA 3,613,683 PTR 1,274,047 MX 340,420 ANY 183,185 SRV 138,889 TXT 106,277 クエリタイプクエリ数 SOA 65,416 DLV 11,853 NS 8,918 DS 1,217 CNAME 489 DNSKEY 423 RRSIG 104

(21)

経験分布を算出したドメイン名

• Aレコードの問い合わせトップ10 21 ドメイン名クエリ数 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

(22)

到着間隔分布（累積分布）

• www.google.com

(23)

到着間隔分布（累積分布）

• e3191.dscc.akamaiedge.net

(24)

到着間隔分布（累積分布）

• us-courier.push-apple.com.akadns.net

(25)

到着間隔分布（累積分布）

• www.bluecoat.com

(26)

到着間隔分布（累積分布）

• www.msftncsi.com

(27)

到着間隔分布（累積分布）

• twitter.com

(28)

到着間隔分布（累積分布）

• api.twitter.com

(29)

応答時間分布の算出

• キャッシュヒット時の応答時間 – 名前解決に要する時間がほぼ0であった – 最大で0.001秒程度 • キャッシュミス時の応答時間を集計 29

(30)

キャッシュミス時の応答時間分布

• www.google.com

30

(31)

キャッシュミス時の応答時間分布

• e3191.dscc.akamaiedge.net

31

(32)

キャッシュミス時の応答時間分布

• us-courier.push-apple.com.akadns.net

32

(33)

キャッシュミス時の応答時間分布

• www.bluecoat.com

33

(34)

キャッシュミス時の応答時間分布

34

(35)

キャッシュミス時の応答時間分布

• twitter.com

35

(36)

キャッシュミス時の応答時間分布

• api.twitter.com

36

(37)

発表の流れ

(38)

シミュレーションの概要

• パラメータ – 到着時間間隔分布 – 応答時間分布 – TTL – キャッシュサーバ数 – タイムスケール • キャッシュミス率をシミュレーション 38

(39)

シミュレーションの設定

• 名前解決要求の到着間隔 – 到着間隔分布に従うランダムな間隔で到着 • ロードバランサの振る舞い – ラウンドロビン・ランダムポリシーで割り振り • キャッシュミスした場合 – 応答時間分布に基づく乱数を発生させ、要求処理状態へ – 処理中の同一ドメインへの要求はミスとする 39

(40)

シミュレーションの設定

• 要求処理が完了後にキャッシュ保持状態 – TTLのカウントダウンを開始 – TTLが0になったらキャッシュを消去 • キャッシュヒットした場合の処理時間は0 • 単一のドメイン名からの要求 • シミュレーションの試行回数 – 1試行で名前解決要求を10000個発生 – 10000試行の結果から平均・信頼区間を算出 40

(41)

シミュレーション１

• 各ポリシーのキャッシュミス率を比較 – TTL：30～30000 – キャッシュサーバ数：5 – タイムスケール：1 41

(42)

TTLを変化させたキャッシュミス率

42

(43)

シミュレーション２

• サーバ数を変化させキャッシュミス率を比較 – TTL：1～100,000 – キャッシュサーバ数：2～10 – タイムスケール：1 43

(44)

サーバ数を変化させたミス率

44

(45)

サーバ数を変化させたミス率

45

• www.google.com ラウンドロビン

ランダムより著しく悪化している

(46)

時間帯別の到着間隔

• 時間帯別で到着間隔は変化するはず – 人のいる時間帯（日中）は要求が多い – 人のいない時間（深夜）は要求が少ない • キャッシュミス率も異なるのでは？ 46

(47)

時間帯毎のクエリ数

• www.google.com

(48)

時間帯毎のクエリ数

48

(49)

時間帯毎のクエリ数

49

(50)

時間帯毎のクエリ数

50

(51)

時間帯毎のクエリ数

(52)

時間帯毎のクエリ数

• twitter.com

(53)

時間帯毎のクエリ数

• api.twitter.com

(54)

時間帯毎のクエリ

• 深夜から早朝にかけてクエリのピーク – 予想とは違った時間帯にピークが来ている – 機械的なクエリ • 日中にクエリのピーク – 機械的でないクエリ 54

(55)

時間帯別で到着間隔の算出

• 各ドメイン名の到着間隔を時間帯別に集計 – 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

(56)

時間帯別の到着間隔分布

56

(57)

時間帯別の到着間隔分布

57

(58)

時間帯別の到着間隔分布

58

(59)

時間帯別の到着間隔分布

59

(60)

時間帯別の到着間隔分布

(61)

時間帯別の到着間隔分布

• twitter.com

(62)

時間帯別の到着間隔分布

• api.twitter.com

(63)

シミュレーション3（時間帯別）

• 時間帯毎のキャッシュミス率を比較 – TTL：Aレコードに設定されている値 – キャッシュサーバ数：5 – タイムスケール：1～10000 63

(64)

時間帯別のキャッシュミス率

• www.google.com

64

(65)

時間帯別のキャッシュミス率

• www.google.com

65

(66)

時間帯別のキャッシュミス率

• www.google.com

66

(67)

時間帯別のキャッシュミス率

• twitter.com

67

(68)

時間帯別のキャッシュミス率

• twitter.com

68

(69)

時間帯別のキャッシュミス率

• twitter.com

69

(70)

シミュレーション4（時間帯別）

• TTLを変化させキャッシュミス率を比較 – TTL： Aレコードに設定されている • 0.1, 1, 10, 100, 1000 – キャッシュサーバ数：5 – タイムスケール：1 70

(71)

TTLを変化させたキャッシュミス率

71

(72)

TTLを変化させたキャッシュミス率

72

(73)

TTLを変化させたキャッシュミス率

73

(74)

TTLを変化させたキャッシュミス率

74

(75)

TTLを変化させたキャッシュミス率

75

0時～6時 • e3191.dscc.akamaiedge.net

(76)

TTLを変化させたキャッシュミス率

76

(77)

TTLを変化させたキャッシュミス率

77

(78)

TTLを変化させたキャッシュミス率

78

(79)

TTLを変化させたキャッシュミス率

79

0時～6時

(80)

TTLを変化させたキャッシュミス率

80

6時～12時

(81)

TTLを変化させたキャッシュミス率

81

12時～18時

(82)

TTLを変化させたキャッシュミス率

82

18時～24時

(83)

TTLを変化させたキャッシュミス率

83

0時～6時

(84)

TTLを変化させたキャッシュミス率

84

6時～12時

(85)

TTLを変化させたキャッシュミス率

85

12時～18時

(86)

TTLを変化させたキャッシュミス率

86

18時～24時

(87)

TTLを変化させたキャッシュミス率

87

0時～6時

(88)

TTLを変化させたキャッシュミス率

88

6時～12時

(89)

TTLを変化させたキャッシュミス率

89

12時～18時

(90)

TTLを変化させたキャッシュミス率

90

18時～24時

(91)

TTLを変化させたキャッシュミス率

91

0時～6時

(92)

TTLを変化させたキャッシュミス率

92

6時～12時

(93)

TTLを変化させたキャッシュミス率

93

12時～18時

(94)

TTLを変化させたキャッシュミス率

94

18時～24時

(95)

TTLを変化させたキャッシュミス率

95

0時～6時

(96)

TTLを変化させたキャッシュミス率

96

6時～12時

(97)

TTLを変化させたキャッシュミス率

97

12時～18時

(98)

TTLを変化させたキャッシュミス率

98

18時～24時

(99)

シミュレーション5（時間帯別）

• キャッシュサーバ数によるキャッシュミス率 • TTL：1～100000 • キャッシュサーバ数：2～10 • タイムスケール：1 99

(100)

サーバ数を変化させたミス率

100

• www.google.com 0時～6時

(101)

サーバ数を変化させたミス率

101

(102)

サーバ数を変化させたミス率

102

(103)

サーバ数を変化させたミス率

103

(104)

サーバ数を変化させたミス率

104

(105)

サーバ数を変化させたミス率

105

(106)

サーバ数を変化させたミス率

106

(107)

サーバ数を変化させたミス率

107

(108)

実測のミス率と比較

• www.google.com 108 時間帯実測値シミュレーション 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

(109)

実測のミス率と比較

• twitter.com 109 時間帯実測値シミュレーション 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

(110)

実測のミス率と比較

• 計測したデータを見てみると

– キャッシュミス数が明らかに少ない

– TTLが0になっているのにキャッシュで応答

(111)

発表の流れ

(112)

まとめ

• キャッシュ効率を考えた負荷分散 • キャッシュミス率の比較 – 負荷分散なし・ランダム・ラウンドロビン • キャッシュミス率が悪化するケース – TTLが短い場合 – キャッシュサーバ数を増した場合 – クエリ数が少ない時間帯 112

(113)

今後の課題

• キャッシュサーバごとの負荷について – 複数ドメインの問い合わせに対応 • 実測のキャッシュミス率が明らかに低い – ログを見るとTTLが0でもキャッシュで応答 • キャッシュ効率を考えた負荷分散 113