ETNET 2013

サービス指向ルータ向け
問合せ処理用ハードウェア
の検討
松谷宏紀
（慶應義塾大学）
1
サービス指向ルータ（SoR）
• インターネットの普及、クラウド・仮想化技術の発展
– 豊かな情報サービスに対する需要
• サービス指向ルータ
[H. Nishi, 2012]
– 情報を蓄積・解釈可能なインターネットルータ
– データベースを内蔵
– ルータを通過するパケットの情報を DB に蓄積
– クライアントからの問合せに応答
クライアントマシン
SoR から吸い上げた情報
を使ってデータマイニング
問合せ（SQL）
2
SoR におけるデータベース処理
• SoR の制御用プロセッサ上で RDBMS が動作
• 転送したパケット情報を DB に登録
• DB を利用するクライアントが、SoR に対して問合
せ処理を要求
– 昨日の www.hoge.jp へのアクセス回数を知りたい
– 未使用 IP アドレスに対してパケットを送信してきた
ノードの IP アドレスを特定したい
クライアントマシン
SoR から吸い上げた情報
を使ってデータマイニング
3
SoR 向け問合せ処理用 HW の検討
• はじめに
• プロセッサによる SQL 問合せ処理性能
– データベースの定義、登録および問合せ処理
– 登録および問合せ処理時間、スループット
• ハードウェア SQL キャッシュ
– 設計方針
– 結果キャッシュ
– バッファキャッシュ
• 予備評価
– 性能およびハードウェア量に関する考察
• まとめと今後の課題
4
SoR DB：データベースの定義
列名
ts
saddr
型
時間
整数
説明
INSERT 時のタイムスタンプ
SRC IPv4 アドレス
daddr
proto
sport
dport
整数
整数
整数
DST IPv4 アドレス
プロトコル番号（例：TCP、UDP）
SRC ポート
整数
文字列
DST ポート
ペイロード（例：HTTP の GET 要求）
data
• 応用例
– 昨日の www.hoge.jp へのアクセス回数を知りたい
– www.hoge.jp でよく参照されるページを知りたい
– 未使用 IP アドレスに対してパケットを送信してきた
ノードの IP アドレスを特定したい
5
SoR DB：登録および問合せ処理内容
• 登録 (1)、集合演算 (2～3)、取り出し (4～9)
OP
処理内容（SQL 文）
1
2
3
4
INSERT
SELECT
SELECT
SELECT
5
6
7
SELECT ts FROM sor WHERE proto=6
SELECT ts, saddr, daddr, proto, sport, dport FROM sor
8
9
INTO sor
COUNT(*)
COUNT(*)
ts FROM
VALUES（ランダムデータ）
FROM sor
FROM sor WHERE proto=6
sor
SELECT ts, saddr, daddr, proto, sport, dport FROM sor
WHERE proto=6
SELECT * FROM sor
SELECT * FROM sor WHERE proto=6
※本来は、SoR 用 DB の実用的ベンチマークの開発が望まれる
問合せ処理性能：予備評価の環境
• フルシステムシミュレータ Gem5
[N.Binkert, 2011]
– シミュレータ上で Linux および RDBMS を実行
– RDBMS には、In-Memory 動作の SQLite 使用
アーキテクチャ
動作周波数
L1キャッシュ
L2 キャッシュ
ゲスト OS
コンパイラ
RDBMS
ハイエンド環境
X86-64
2.66 GHz
32kB / 32kB
256kB /core
Linux 2.6.22.9
GCC 4.4.4 (-O2)
SQLite 3.7.15.2
（In-Memory 動作）
組込み環境
ARMv7
0.8 GHz
32kB / 32kB
512kB /core
Linux 2.6.38.8
GCC 4.6.2 (-O2)
SQLite 3.7.15.2
（In-Memory 動作）
7
SoR DB：問合せ処理時間 [msec]
• DB 中のレコード数 n = 36,000 のとき
OP2
OP3
ハイエンド環境
1.442
43.669
組込み環境
2.962
127.141
OP4
OP5
OP6
58.224
46.704
152.494
179.947
137.069
513.986
OP7
OP8
OP9
59.201
181.615
64.033
178.302
615.747
192.199
75.923
56.136
243.419
195.377
8
平均 x
標準偏差 σ
SoR DB：問合せ処理時間
• DB 中のレコード数 n = 10～100,000
シミュレーション結果
（ハイエンド）
シミュレーション結果
（組込み）
9
SoR DB：問合せ処理時間
• DB 中のレコード数 n = 10～100,000
シミュレーション結果
（ハイエンド）
近い性能を有する
実機
10
SoR DB：問合せ処理スループット
• DB 中のレコード数 n = 36,000 のとき
– 待ち行列理論（M/G/1）を用いて解析
– 到着はポアソン過程、サービス時間は一般分布
シミュレーション結果
（ハイエンド）
シミュレーション結果
（組込み）
11
SoR 向け問合せ処理用 HW の検討
• はじめに
• プロセッサによる SQL 問合せ処理性能
– データベースの定義、登録および問合せ処理
– 登録および問合せ処理時間、スループット
• ハードウェア SQL キャッシュ
– 設計方針
– 結果キャッシュ
– バッファキャッシュ
• 予備評価
– 性能およびハードウェア量に関する考察
• まとめと今後の課題
12
問合せ HW：設計方針（1/2）
• SoR の制御用プロセッサ上で、RDBMS が
In-Memory 動作（ディスクアクセスはしない）
• DB を利用するクライアントが、SoR に対して問合
せ処理を要求
• HW SQL キャッシュはプロセッサの前段に置く
– HIT : プロセッサを介さずに問合せ結果を返信
– MISS : 通常通りプロセッサが問合せを処理
クライアントマシン
SoR から吸い上げた情報
を使ってデータマイニング
13
問合せ HW：設計方針（2/2）
1. 重い処理は（できる限り）クライアント側で
2. 分割可能な問合せ処理は、クライアント側が問
合せを複数回行うことで実現
– WHERE 句の和集合は、複数問合せに分割可能
3. SoR 側で多量のデータを永続的に保持するので
はなく、永続的なデータ保持にはクライアント側
のストレージを使用
クライアントマシン
SoR から吸い上げた情報
を使ってデータマイニング
14
問合せ HW：問合せのカテゴリ分け
• 問合せ処理の柔軟性と高速化の間にはトレード
オフの関係
• Class-0
– SQL-92 でサポートされている全問合せ機能
• Class-1
– 提案ハードウェアが応答可能な問合せ
– SELECT 句、WHERE 句などに制限
• Class-2
– キャッシュヒットしやすい問合せ（推奨問合せ）
• Class-3
– 局所性の高い問合せ例（のちの予備評価で使用）
15
問合せ HW：問合せのカテゴリ分け
• 問合せ
– SELECT 句を用いた選択リスト
– FROM 句を用いた表参照リスト
– WHERE 句を用いた探索条件
• Class-0
– SQL-92 でサポートされている全問合せ機能
SELECT句
WHERE句
指定可能な列（ts, saddr, daddr, proto, sport, dport,
data）の任意の組合せ
任意の集合関数
論理演算子（AND、OR）、比較演算子、IN 句、
BETWEEN 句、LIKE 句を用いたすべての組合せ
16
問合せ HW：問合せのカテゴリ分け
• Class-1
– 提案ハードウェアが応答可能な問合せ
– WHERE 句は等号探索のみ（dont care も可能）
SELECT句
WHERE句
指定可能な列（ts, saddr, daddr, proto, sport, dport,
data）の任意の組合せ、
もしくは、集合関数 COUNT(*)
以下の６条件を AND で結合した探索条件のみ
ts BETWEEN INT32 AND INT32
※time_t構造体
saddr = INT32
※IPv4アドレス
daddr = INT32
proto = INT8
※プロトコル番号
sport = INT16
※TCP/UDPポート
dport = INT16
17
問合せ HW：問合せのカテゴリ分け
• Class-1問合せのためのデータ構造
– SELECT 句に1Byte、WHERE 句に 21Byte
※WHERE 句のフィールドにおいて全ビット1は
dont care扱い
18
問合せ HW：問合せのカテゴリ分け
• Class-1問合せのためのデータ構造
– SELECT 句に1Byte、WHERE 句に 21Byte
※WHERE 句のフィールドにおいて全ビット1は
dont care扱い
19
問合せ HW：問合せのカテゴリ分け
• Class-1問合せのためのデータ構造
– SELECT 句に1Byte、WHERE 句に 21Byte
※WHERE 句のフィールドにおいて全ビット1は
dont care扱い
20
問合せ HW：問合せのカテゴリ分け
• Class-2
– キャッシュヒットしやすい問合せ（推奨問合せ）
– タイムスタンプ ts の指定を１０分単位、かつ、最近に
限定
SELECT句
WHERE句
集合関数 COUNT(*)
以下の条件を含む Class-1 WHERE 句
ts BETWEEN INT32 AND（INT32 +10分）
※直近1日、10分単位の指定に限定→144通り
SELECT句
指定可能な列（ts, saddr, daddr, proto, sport, dport,
data）の任意の組合せ
WHERE句
以下の条件を含む Class-1 WHERE 句
ts BETWEEN INT32 AND（INT32 +10分）
※直近1時間、10分単位の指定に限定→6通り
21
問合せ HW：問合せのカテゴリ分け
• Class-3
– 局所性の高い問合せ例（のちの予備評価で使用）
SELECT句
以下の4 種類のいずれか
COUNT(*)
ts, saddr, daddr, proto, sport, dport
data
*
WHERE句
以下の４条件を AND で結合した探索条件のみ
ts BETWEEN INT32 AND INT32
※直近1時間、10分単位の指定に限定→6通り
daddr = INT32
※少数のホストに限定→16通り
proto = INT8
※TCPに限定→1通り
dport = INT16
22
問合せ HW：結果キャッシュ
• キャッシュに入れる条件
– Class-2 に合致する集合関数 COUNT(*) の結果
– ts が10分単位、かつ、直近1日以内
• キャッシュサイズ：256 エントリ
– ハッシュ値の下位 8bit をインデックスとして使用
• 各エントリ
– ハッシュ値
– タイムスタンプ
– 前回の問合せ結果
問合せ HW：結果キャッシュ
• ハッシュ値（MurmurHash 等を使用）
– クライアント側が計算し、問合せに添付
– Update フラグ：キャッシュを無視したい場合は1
24
問合せ HW：結果キャッシュ
• 結果キャッシュの陳腐化
– 結果キャッシュの値が古くなっている可能性
• SoR 側での対処は高コスト
– SoR DB 側でレプリカ（キャッシュ）を追跡し
– SoR DB への変更の度にキャッシュを更新
• 対策：クライアント側で判断
– SoR からの問合せ応答のタイムスタンプ
– 陳腐化していると判断したら Update フラグを1
①問合せ
②キャッシュによる応答
③再問合せ Update=1 Cache
④キャッシュの更新＋応答
クライアント
RDBMS
SoR（DB+Cache）
25
問合せ HW：バッファキャッシュ
• キャッシュに入れる条件
– Class-2 に合致する表の取り出し処理の結果
– ts が10分単位、かつ、直近1時間（６スロット）
• キャッシュサイズ：１スロット当たり 6,000 エントリ
– 秒間１０エントリを登録すると仮定した場合１０分間分
• 各エントリ
– ヘッダ 17Byte
– ペイロード 111Byte
問合せ HW：バッファキャッシュ
• 表の取り出し操作
– SELECT 句で指定されたフィールドを返す
– バッファキャッシュには全フィールドがキャッシュ
• 問合せ結果のフィルタリング
– クライアントには指定されたフィールドのみ返す
– ストライドアクセス（不要フィールドを読み飛ばす）
SELECT 句で指定されたフィールド（例：dport）
SoR 向け問合せ処理用 HW の検討
• はじめに
• プロセッサによる SQL 問合せ処理性能
– データベースの定義、登録および問合せ処理
– 登録および問合せ処理時間、スループット
• ハードウェア SQL キャッシュ
– 設計方針
– 結果キャッシュ
– バッファキャッシュ
• 予備評価
– 性能およびハードウェア量に関する考察
• まとめと今後の課題
28
予備評価：評価項目
• ヒット率 vs. スループットの解析
– ヒット率が 10%、50%、70%、80%、90% のとき
– 待ち行列理論（M/G/1）を用いて解析
• シミュレータを用いたスループット評価
– SoR 向け HW キャッシュのシミュレーション
– 局所的問合せ（Class-3）が 25%、50%、75% のとき
• ハードウェア量の考察
– FPGA への実装を想定
– 結果キャッシュ、バッファキャッシュのメモリ量
29
予備評価：ヒット率 vs. スループット
• ヒット率が 10%、50%、70%、80%、90% のとき
• 待ち行列理論（M/G/1）を用いて解析
シミュレーション結果
（ハイエンド）
シミュレーション結果
（組込み）
30
予備評価：キャッシュシミュレーション
• SoR 向け HW キャッシュシミュレーション
– 局所的問合せ（Class-3）が 25%、50%、75% のとき
局所性（Class-3）25%：SW比 1.52～1.94倍向上
局所性（Class-3）50%：SW比
2.25～2.78倍向上
シミュレーション結果
シミュレーション結果
（ハイエンド）
（組込み）
局所性（Class-3）75%：SW比
4.22～5.12倍向上
31
予備評価：ハードウェア量
• バッファキャッシュのメモリ量
– スロット数は６（１時間分のレコードを保持）
– １スロットは 6,000 エントリ（１０分間分）
– １エントリは、ヘッダ 17Byte、データ 111Byte
– 合計 4,500kByte
• Xilinx Virtex-6
– 最大 38,304kbit の BlockRAM
– バッファおよび結果キャッシュを実装可能
• Virtex-6 FPGA ML605 ボード
– BlockRAM のサイズが足りなかったが、キャッシュサイ
ズを減らした縮小版は実装できた
32
まとめと今後の課題
• SoR 向け問合せ処理 HW の検討
– 複雑な処理はすべてクライアントで行う
– SoR 側ストレージは一次記憶として使う
• ハードウェア SQL キャッシュ
– 結果キャッシュ（直近１日の問合せ結果をキャッシュ）
– バッファキャッシュ（直近１時間のレコードをキャッシュ）
• 予備評価
– 局所性（Class-3）25%： SW 比で 1.52～1.94倍向上
– 局所性（Class-3）50%： SW 比で 2.25～2.78倍向上
– 局所性（Class-3）75%： SW 比で 4.22～5.12倍向上
• 今後の課題：今回検討した HW を実装評価
33

Download Report