サービス指向ルータ向け 問合せ処理用ハードウェアの検討 松谷 宏紀　　（慶應義塾大学）

SoR から吸い上げた情報を使ってデータマイニング インターネットの普及、クラウド・仮想化技術の発展 豊かな情報サービスに対する需要 サービス指向ルータ [H. Nishi, 2012] 情報を蓄積・解釈可能なインターネットルータ データベースを内蔵 ルータを通過するパケットの情報を DB に蓄積 クライアントからの問合せに応答 クライアントマシン SoR から吸い上げた情報を使ってデータマイニング 問合せ（SQL）

SoR から吸い上げた情報を使ってデータマイニング SoR の制御用プロセッサ上で RDBMS が動作 転送したパケット情報を DB に登録 DB を利用するクライアントが、SoR に対して問合せ処理を要求 昨日の www.hoge.jp へのアクセス回数を知りたい 未使用 IP アドレスに対してパケットを送信してきたノードの IP アドレスを特定したい クライアントマシン SoR から吸い上げた情報を使ってデータマイニング

SoR 向け問合せ処理用 HW の検討 はじめに プロセッサによる SQL 問合せ処理性能 ハードウェア SQL キャッシュ 予備評価 データベースの定義、登録および問合せ処理 登録および問合せ処理時間、スループット ハードウェア SQL キャッシュ 設計方針 結果キャッシュ バッファキャッシュ 予備評価 性能およびハードウェア量に関する考察 まとめと今後の課題

SoR DB：データベースの定義 応用例 昨日の www.hoge.jp へのアクセス回数を知りたい 列名 型 説明 ts 時間 INSERT 時のタイムスタンプ saddr 整数 SRC IPv4 アドレス daddr DST IPv4 アドレス proto プロトコル番号（例：TCP、UDP） sport SRC ポート dport DST ポート data 文字列 ペイロード（例：HTTP の GET 要求） 応用例 昨日の www.hoge.jp へのアクセス回数を知りたい www.hoge.jp でよく参照されるページを知りたい 未使用 IP アドレスに対してパケットを送信してきた　ノードの IP アドレスを特定したい

SoR DB：登録および問合せ処理内容 登録 (1)、集合演算 (2～3)、取り出し (4～9) OP 処理内容（SQL 文） 1 INSERT INTO sor VALUES（ランダムデータ） 2 SELECT COUNT(*) FROM sor 3 SELECT COUNT(*) FROM sor WHERE proto=6 4 SELECT ts FROM sor 5 SELECT ts FROM sor WHERE proto=6 6 SELECT ts, saddr, daddr, proto, sport, dport FROM sor 7 SELECT ts, saddr, daddr, proto, sport, dport FROM sor 　 　　　　　　　　　　　　　　　 　WHERE proto=6 8 SELECT * FROM sor 9 SELECT * FROM sor WHERE proto=6 ※本来は、SoR 用 DB の実用的ベンチマークの開発が望まれる

問合せ処理性能：予備評価の環境 フルシステムシミュレータ Gem5 [N.Binkert, 2011] シミュレータ上で Linux および RDBMS を実行 RDBMS には、In-Memory 動作の SQLite 使用 ハイエンド環境 組込み環境 アーキテクチャ X86-64 ARMv7 動作周波数 2.66 GHz 0.8 GHz L1キャッシュ 32kB / 32kB L2 キャッシュ 256kB /core 512kB /core ゲスト OS Linux 2.6.22.9 Linux 2.6.38.8 コンパイラ GCC 4.4.4 (-O2) GCC 4.6.2 (-O2) RDBMS SQLite 3.7.15.2 （In-Memory 動作）

SoR DB：問合せ処理時間 [msec] DB 中のレコード数 n = 36,000 のとき ハイエンド環境 組込み環境 OP2 1.442 2.962 OP3 43.669 127.141 OP4 58.224 179.947 OP5 46.704 137.069 OP6 152.494 513.986 OP7 59.201 178.302 OP8 181.615 615.747 OP9 64.033 192.199 平均 x 75.923 243.419 標準偏差 σ 56.136 195.377

SoR DB：問合せ処理時間 DB 中のレコード数 n = 10～100,000 シミュレーション結果（ハイエンド） シミュレーション結果（組込み）

SoR DB：問合せ処理時間 DB 中のレコード数 n = 10～100,000 シミュレーション結果（ハイエンド） 近い性能を有する実機

SoR DB：問合せ処理スループット DB 中のレコード数 n = 36,000 のとき 待ち行列理論（M/G/1）を用いて解析 到着はポアソン過程、サービス時間は一般分布 シミュレーション結果（ハイエンド） シミュレーション結果（組込み）

SoR 向け問合せ処理用 HW の検討 はじめに プロセッサによる SQL 問合せ処理性能 ハードウェア SQL キャッシュ 予備評価 データベースの定義、登録および問合せ処理 登録および問合せ処理時間、スループット ハードウェア SQL キャッシュ 設計方針 結果キャッシュ バッファキャッシュ 予備評価 性能およびハードウェア量に関する考察 まとめと今後の課題

SoR から吸い上げた情報を使ってデータマイニング 問合せ HW：設計方針（1/2） SoR の制御用プロセッサ上で、RDBMS が 　　　In-Memory 動作（ディスクアクセスはしない） DB を利用するクライアントが、SoR に対して問合せ処理を要求 HW SQL キャッシュはプロセッサの前段に置く HIT : プロセッサを介さずに問合せ結果を返信 MISS : 通常通りプロセッサが問合せを処理 クライアントマシン SoR から吸い上げた情報を使ってデータマイニング

SoR から吸い上げた情報を使ってデータマイニング 問合せ HW：設計方針（2/2） 重い処理は（できる限り）クライアント側で 分割可能な問合せ処理は、クライアント側が問合せを複数回行うことで実現 WHERE 句の和集合は、複数問合せに分割可能 SoR 側で多量のデータを永続的に保持するのではなく、永続的なデータ保持にはクライアント側のストレージを使用 クライアントマシン SoR から吸い上げた情報を使ってデータマイニング

問合せ HW：問合せのカテゴリ分け 問合せ処理の柔軟性と高速化の間にはトレードオフの関係 Class-0 Class-1 Class-2 SQL-92 でサポートされている全問合せ機能 Class-1 提案ハードウェアが応答可能な問合せ SELECT 句、WHERE 句などに制限 Class-2 キャッシュヒットしやすい問合せ（推奨問合せ） Class-3 局所性の高い問合せ例（のちの予備評価で使用）

問合せ HW：問合せのカテゴリ分け 問合せ Class-0 SELECT 句を用いた選択リスト FROM 句を用いた表参照リスト WHERE 句を用いた探索条件 Class-0 SQL-92 でサポートされている全問合せ機能 SELECT句 指定可能な列（ts, saddr, daddr, proto, sport, dport, data）の任意の組合せ 任意の集合関数 WHERE句 論理演算子（AND、OR）、比較演算子、IN 句、 BETWEEN 句、LIKE 句を用いたすべての組合せ

問合せ HW：問合せのカテゴリ分け Class-1 提案ハードウェアが応答可能な問合せ WHERE 句は等号探索のみ（dont care も可能） SELECT句 指定可能な列（ts, saddr, daddr, proto, sport, dport, data）の任意の組合せ、 もしくは、集合関数 COUNT(*) WHERE句 以下の６条件を AND で結合した探索条件のみ ts BETWEEN INT32 AND INT32 ※time_t構造体 saddr = INT32 ※IPv4アドレス daddr = INT32 proto = INT8 ※プロトコル番号 sport = INT16 ※TCP/UDPポート dport = INT16

問合せ HW：問合せのカテゴリ分け Class-1問合せのためのデータ構造 SELECT 句に1Byte、WHERE 句に 21Byte 　dont care扱い

問合せ HW：問合せのカテゴリ分け Class-1問合せのためのデータ構造 SELECT 句に1Byte、WHERE 句に 21Byte 　dont care扱い

問合せ HW：問合せのカテゴリ分け Class-1問合せのためのデータ構造 SELECT 句に1Byte、WHERE 句に 21Byte 　dont care扱い

問合せ HW：問合せのカテゴリ分け Class-2 キャッシュヒットしやすい問合せ（推奨問合せ） タイムスタンプ ts の指定を１０分単位、かつ、最近に限定 SELECT句 集合関数 COUNT(*) WHERE句 以下の条件を含む 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通り

問合せ 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

問合せ HW：結果キャッシュ キャッシュに入れる条件 キャッシュサイズ：256 エントリ 各エントリ Class-2 に合致する集合関数 COUNT(*) の結果 ts が10分単位、かつ、直近1日以内 キャッシュサイズ：256 エントリ ハッシュ値の下位 8bit をインデックスとして使用 各エントリ ハッシュ値 タイムスタンプ 前回の問合せ結果

問合せ HW：結果キャッシュ ハッシュ値（MurmurHash 等を使用） クライアント側が計算し、問合せに添付 Update フラグ：キャッシュを無視したい場合は1

問合せ HW：結果キャッシュ 結果キャッシュの陳腐化 SoR 側での対処は高コスト 対策：クライアント側で判断 結果キャッシュの値が古くなっている可能性 SoR 側での対処は高コスト SoR DB 側でレプリカ（キャッシュ）を追跡し SoR DB への変更の度にキャッシュを更新 対策：クライアント側で判断 SoR からの問合せ応答のタイムスタンプ 陳腐化していると判断したら Update フラグを1 ①問合せ ②キャッシュによる応答 ③再問合せ Update=1 ④キャッシュの更新＋応答 Cache RDBMS クライアント SoR（DB+Cache）

問合せ HW：バッファキャッシュ キャッシュに入れる条件 キャッシュサイズ：１スロット当たり 6,000 エントリ 各エントリ Class-2 に合致する表の取り出し処理の結果 ts が10分単位、かつ、直近1時間（６スロット） キャッシュサイズ：１スロット当たり 6,000 エントリ 秒間１０エントリを登録すると仮定した場合１０分間分 各エントリ ヘッダ 17Byte ペイロード 111Byte

SELECT 句で指定されたフィールド（例：dport） 問合せ HW：バッファキャッシュ 表の取り出し操作 SELECT 句で指定されたフィールドを返す バッファキャッシュには全フィールドがキャッシュ 問合せ結果のフィルタリング クライアントには指定されたフィールドのみ返す ストライドアクセス（不要フィールドを読み飛ばす） SELECT 句で指定されたフィールド（例：dport）

SoR 向け問合せ処理用 HW の検討 はじめに プロセッサによる SQL 問合せ処理性能 ハードウェア SQL キャッシュ 予備評価 データベースの定義、登録および問合せ処理 登録および問合せ処理時間、スループット ハードウェア SQL キャッシュ 設計方針 結果キャッシュ バッファキャッシュ 予備評価 性能およびハードウェア量に関する考察 まとめと今後の課題

予備評価：評価項目 ヒット率 vs. スループットの解析 シミュレータを用いたスループット評価 ハードウェア量の考察 ヒット率が 10%、50%、70%、80%、90% のとき 待ち行列理論（M/G/1）を用いて解析 シミュレータを用いたスループット評価 SoR 向け HW キャッシュのシミュレーション 局所的問合せ（Class-3） が 25%、50%、75% のとき ハードウェア量の考察 FPGA への実装を想定 結果キャッシュ、バッファキャッシュのメモリ量

予備評価：ヒット率 vs. スループット ヒット率が 10%、50%、70%、80%、90% のとき 待ち行列理論（M/G/1）を用いて解析 シミュレーション結果（ハイエンド） シミュレーション結果（組込み）

予備評価：キャッシュシミュレーション 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倍向上 シミュレーション結果（ハイエンド） シミュレーション結果（組込み）

予備評価：ハードウェア量 バッファキャッシュのメモリ量 Xilinx Virtex-6 Virtex-6 FPGA ML605 ボード スロット数は６（１時間分のレコードを保持） １スロットは 6,000 エントリ（１０分間分） １エントリは、ヘッダ 17Byte、データ 111Byte 合計 4,500kByte Xilinx Virtex-6 最大 38,304kbit の BlockRAM バッファおよび結果キャッシュを実装可能 Virtex-6 FPGA ML605 ボード BlockRAM のサイズが足りなかったが、キャッシュサイズを減らした縮小版は実装できた

まとめと今後の課題 SoR 向け問合せ処理 HW の検討 ハードウェア SQL キャッシュ 予備評価 複雑な処理はすべてクライアントで行う 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 を実装評価