はてな流大規模データ処理

アジェンダ 大規模なデータ OS のキャッシュ MySQLの運用 大規模データアプリケーションの開発

大規模なデータ

大規模データ はてなブックマーク mysql> select count(*) from relword; +----------+ | 51780147 | 1 row in set (0.00 sec)

はてなブックマークのデータ規模 レコ―ド数 データサイズ 1,073万エントリー 3,134万ブックマーク 4,743万タグ エントリー 2.5GB ブックマーク 4GB タグ 3.4GB HTML 100GB超

大規模データへのクエリ mysql> select url from entry use index(hoge) where eid = 9615899; ... 200秒待っても結果が返って来ない

大規模データの難しい所 メモリ内で計算できない

メモリとディスクの速度差 メモリはディスクの100倍以上高速 メモリ 7 .5 GB/sec ディスク 58MB/sec % sudo /sbin/hdparm -tT /dev/sda /dev/sda: Timing cached reads: 15012 MB in 1.99 seconds = 7525.03 MB/sec Timing buffered disk reads: 176 MB in 3.02 seconds = 58.37 MB/sec

スケーリングの要所 CPU 負荷のスケーリングは簡単 I/O 負荷のスケーリングは難しい 同じ構成のサーバーを増やす、LB で分散 Web, APサ―バ, クローラー I/O 負荷のスケーリングは難しい 大規模データ データベース

大規模データを扱うコツ いかにしてメモリで済ませるか データ量の増加に強いアルゴリズム、データ構造 圧縮、情報検索技術 局所性を活かした分散 例: 線形探索 → 二分探索 O (n) → O (log n) 圧縮、情報検索技術

大規模データを前に知っておくべき事 OS のキャッシュ層 分散を考慮した RDBMS の運用 アルゴリズムとデータ構造

OS のキャッシュ

メモリとディスク メモリとディスクの速度は 150倍 メモリを使ってディスクアクセスを減らす

OS のキャッシュ Linux のページキャッシュの特性

Linux (x86) のページング機構 仮想メモリ機構の基盤 論理的なリニアアドレスを物理的な物理アドレスへ変換 0xbffff444 (MMU) 物理アドレス 0x00002123

Linux (x86) のページ フラットメモリモデル ページ = 仮想メモリの最小単位 4kb の構造体 ページキャッシュ = カーネルバッファに残った page構造体

Linux のページキャッシュとディスク ディスクの内容をメモリに読み込む 作成したページは破棄せずに残す = ページキャッシュ ページが作成される 作成したページは破棄せずに残す = ページキャッシュ 例外を除きすべての I/O に透過的に作用する ディスクのキャッシュを担う箇所 ... VFS

VFS vfs ext2 ext3 ext4 xfs tmpfs デバイスドライバ

VFSの役割 (1) ファイルシステム実装の抽象化 (2) パフォーマンス ページキャッシュ

VFS データ構造関係図 superblock inode (1) inode番号 inode inode dentry file * inode dentry file 1 1 1 1 1 1 address_space 1 (2) offset * page page page

Linux はページ単位でディスクをキャッシュ ファイルの一部をキャッシュできる address_space → page(s) は Radix Tree 検索コストはファイルの大きさにほとんど依存しない

キャッシュの単位 ページ = 仮想メモリの最小単位 ページキャッシュ ≠ ファイルキャッシュ ページキャッシュ = カーネルバッファに残った page構造体

メモリが空いていればキャッシュ 制限なし sar –r で確認 % sar -r 1 10000 Linux 2.6.11-co-0.6.4 (colinux) 05/28/07 19:50:32 kbmemfree kbmemused %memused kbbuffers kbcached kbswpfree kbswpused %swpused kbswpcad 19:50:33 5800 1005888 99.43 28244 694088 262132 4 0.00 0 19:50:34 5800 1005888 99.43 28244 694088 262132 4 0.00 0 19:50:35 5800 1005888 99.43 28244 694088 262132 4 0.00 0 19:50:36 5800 1005888 99.43 28244 694088 262132 4 0.00 0

メモリを増やすことで I/O 負荷軽減 メモリ 4GB メモリ 8GB 14:10:01 CPU %user %nice %system %iowait %idle 14:20:01 all 8.58 0.00 5.84 16.58 69.00 14:30:01 all 7.41 0.00 5.14 17.81 69.63 14:40:01 all 7.74 0.00 4.97 18.56 68.73 14:50:01 all 7.02 0.00 5.01 16.24 71.72 メモリ 8GB 14:10:01 CPU %user %nice %system %iowait %idle 14:10:01 all 18.16 0.00 11.56 0.80 69.49 14:20:01 all 12.48 0.00 9.47 0.88 77.17 14:30:01 all 14.20 0.00 10.17 0.91 74.72 14:40:01 all 13.25 0.00 9.74 0.75 76.25

透過的に作用する OS起動直後に数GBのファイルを read した結果 18:20:01 kbmemfree kbmemused %memused kbbuffers kbcached kbswpfree kbswpused %swpused kbswpcad 18:30:01 3566992 157272 4.22 11224 50136 2048276 0 0.00 0 18:40:01 3546264 178000 4.78 12752 66548 2048276 0 0.00 0 18:50:01 112628 3611636 96.98 4312 3499144 2048232 44 0.00 44

キャッシュを前提にした I/O 軽減策 データ規模 < 物理メモリなら全てキャッシュできる 経済的コストとのバランスを考慮 現状のコモディティ: 8GB ~ 16GB

キャッシュ仕切れない規模になったら 複数サーバーにスケールさせる ただし単純に増やさない 自前でインデックスを作る CPU 負荷分散では単純に増やす I/O分散では局所性を考慮する 自前でインデックスを作る

単純に台数を増やす場合 キャッシュできない割合は相変わらずそのまま すぐに再度ボトルネックに コピー

局所性を考慮した分散 アクセスパターンを考慮した分散 キャッシュできない箇所がなくなる メモリはディスクの 150倍 アクセスパターンB アクセスパターンA

具体的には RDBMS のテーブル単位での分割 検索のインデクスを辞書の途中で分割する 用途ごとにシステムを「島」に分ける パーティショニング 検索のインデクスを辞書の途中で分割する A ~ E まではサーバ A F ~ I まではサーバB ... 用途ごとにシステムを「島」に分ける

リクエストパターンで「島」に分割 proxy proxy 画像API etc. bot / feed 通常のリクエスト AP DB

ページキャッシュを考慮した運用 OS 起動後すぐにサーバを投入しない 性能評価はキャッシュが最適化された時に 分散は局所性を考慮して データ規模に合わせて搭載メモリを調整する メモリ増設で対応しきれないなら分散

分散を考慮した MySQLの運用

MySQL 運用のポイント OS のキャッシュを活かす インデックスを適切に設定する スケーリングを前提とした設計

OS のキャッシュを活かす 全データサイズに気を配る データ量 < 物理メモリ を維持 メモリが足りない場合は増設 etc.

インデックス重要 インデックス = 索引 B木 O(n) → O(log n)

インデックスの効果 例 : 4,000万件のタグデーブルからの検索 インデックスなし = 線形探索 → O(n) → 最大 4,000 万回の探索 インデックスあり = B木で二分探索 → O(log n) → log24000万 = 最大 25.25 回

インデックスの効果の例 mysql> select url from entry where eid = 9615899; +------------------------------------------------------------------------------+ | url | | http://builder.japan.zdnet.com/member/u87200/blog/2008/08/10/entry_27012867/ | 1 row in set (0.00 sec) mysql> select url from entry use index(hoge) where eid = 9615899; ... 200秒待っても結果が返って来ない

インデックスの作用 where、order by、group by の条件 プライマリキー、UNIQUE 制約 明示的に追加したインデックス 罠 複数のカラムに同時にインデックスを効かせたい場合は複合インデックス select * from entry where url like 'http://d.hatena.nejp/%' order by timestamp

インデックスが効くかどうかの確認 explain mysql> explain select url from entry where eid = 9615899; +-------+------+---------------+------+---------+-------+------+-------------+ | table | type | possible_keys | key | key_len | ref | rows | Extra | | entry | ref | eid | eid | 4 | const | 1 | Using where | 1 row in set (0.04 sec) mysql> explain select url from entry use index(cname) where eid = 9615899; +-------+------+---------------+------+---------+------+---------+-------------+ | table | type | possible_keys | key | key_len | ref | rows | Extra | | entry | ALL | NULL | NULL | NULL | NULL | 9620451 | Using where | 1 row in set (0.01 sec)

より詳しくは

MySQL の分散 マスタ・スレーブ 参照系はスレーブへ、更新はマスタへ ORマッパで制御する アプリケーション サーバー アプリケーション ロードバランサ DBスレーブ DBスレーブ DBスレーブ DBマスタ

マスタ・スレーブの特徴 参照系クエリはスケール マスタはスケールしない サーバーを増やすだけで良い ただし、台数を稼ぐことよりもメモリにフィットさせることが重要 マスタはスケールしない 更新系クエリが増えると厳しい ただし、Web アプリは多くの場合 90％以上が参照クエリ マスタ負荷はテーブル分割で凌ぐのが現状のセオリー

MySQL のスケールアウト戦略 データがメモリに載るサイズ? YES → メモリに載せる NO メモリ増設 メモリ増設が不可能ならパーティショニング

パーティショニング (テーブル分割) テーブルA とテーブルB を別のサーバーに置いて分散する方法

パーティショニング テーブル単位での分割 特定のアルゴリズムでの分割 例1. 頭文字 a-d が A、頭文字 e-h が B ... 例2. ハッシュ関数 A B A B

パーティショニングはなぜ効果的か 局所性

パーティショニングを前提にした設計 JOIN を使わない RDBMS 屋には叱られるがしょうがない

INNER JOIN している SQL entry has many bookmarks mysql> select url from entry INNER JOIN bookmark on entry.eid = bookmark.eid -> where bookmark.uid = 169848 limit 5; +-------------------------------------------------------------------+ | url | | http://blog.bulknews.net/mt/archives/001537.html | | http://www.wrightthisway.com/Articles/000154.html | | http://internet.watch.impress.co.jp/cda/news/2005/02/10/6438.html | | http://headlines.yahoo.co.jp/hl?a=20050210-00000136-kyodo-bus_all | | http://headlines.yahoo.co.jp/hl?a=20050210-00000015-maip-soci |

JOIN を排除 where ... in ... を利用 mysql> select eid from bookmark where uid = 169848 limit 5; +-----+ | eid | | 0 | | 4 | | 5 | | 6 | | 7 | 5 rows in set (0.01 sec) mysql> select url from entry where eid in (0, 4, 5, 6, 7); +-------------------------------------------------------------------+ | url | | http://blog.bulknews.net/mt/archives/001537.html | | http://www.wrightthisway.com/Articles/000154.html | | http://internet.watch.impress.co.jp/cda/news/2005/02/10/6438.html | | http://headlines.yahoo.co.jp/hl?a=20050210-00000136-kyodo-bus_all | 4 rows in set (0.12 sec)

DBIx::MoCo $entry->bookmarks(0, 5) JOIN は使わない where ... in ... を使ってプライマリキーで結合

運用が複雑になるとその分経済的コストがかかる。 パーティショニングのトレードオフ 良い点 負荷が下がる 局所性が増してキャッシュ効果が高くなる 悪い点 運用が複雑になる、故障確率が上がる 運用が複雑になるとその分経済的コストがかかる。 メモリは今時 2GB で 5,000円。 パーティショニングはあくまで切り札。

大規模データ アプリケーションの開発

Q. 敢えて大量データにアクセスしたい 全文検索 はてなのキーワードリンク 類似文書探索 データマイニング ...

A. RDBMS では限界 バッチ処理でデータを抽出 別途インデックスサーバを作りRPCでクエリする

用途特化型のインデクシング データを定期的に dump 構造化データを保持したサーバーをC++で開発、RPC でアクセス 検索用の転置インデックス キーワードリンク用の TRIE ... 構造化データを保持したサーバーをC++で開発、RPC でアクセス Thrift

はてなキーワードによるリンク ある文書が20万強のキーワードのうち何を含むか 昔 ... 巨大な正規表現 現在 ... TRIE で Common Prefix Search Aho-Corasick Double Array TRIE

はてなブックマークのテキスト分類器 Complement Naive Bayes 文書に含まれる単語の出現確率を保持するサーバー

全文検索エンジン 大量のデータから検索したい 「いい感じ」の文書を上位に 高速に検索したい

RDBMS の限界 特定のカラムで並び替えることしか出来ない 横断的な検索には向いてない

RDBMS → 情報検索 RDB のデータをバッチで取得 転置インデクスを作って検索アルゴズムを使う

テキスト走査と転置インデックス

テキスト走査 O(N) grep Pros Cons 実装が容易 正規表現 大量のドキュメントに向かない 「複数のドキュメントから、一番欲しいドキュメントを検索する」(ranked retrieval) に向かない

転置インデックス Pros 大規模データを高速に検索 Ranked retrieval Cons 設計/実装が大変

転置インデックス 索引語 (term) => docIDs (postings list)

転置インデックスのソート 辞書はアルファベット順 文書はID (整数) 順 辞書から単語を探しやすいように 圧縮や探索など様々なアルゴリズムで有利 差分を取ってδ符合で圧縮

転置インデックスに対する検索 辞書から検索 ヒットした単語の postings list を取得 ソート済み → 二分探索可 → O(log n) ヒットした単語の postings list を取得 docID が検索結果 スコアリング → Cosine Similarity

ベクトル空間モデル ベクトル空間モデル 情報検索技術の基盤 クエリやドキュメントをベクトル化して無限次元のベクトル空間に展開 ベクトル空間内で 「近い」 ベクトルを探す → 類似文書 情報検索技術の基盤 クエリに基づいたドキュメントのスコアリング ドキュメント分類 ドキュメントクラスタリング

ドキュメントのベクトル化 ドキュメントをベクトルとして表現 辞書の単語を成分とする無限次元ベクトル d1

ベクトル空間モデルのイメージ t3 d2 d3 d1 θ φ t1 d5 t2 d4

Cosine similarity 二つのベクトルの類似度 = 2ベクトルが作る cosΘ を求める式に等しい ∵ 相関係数 = cosΘ

Cosine similarity 2ベクトルの内積が最も大きいもの = 最も相関度が高い

例 3つの小説の 3 語の tf ベクトル長で正規化 SaS・PaP = 0.999 SaS・WH = 0.888 "Sense and Sensibility" "Pride and Prejudice" "Wuthering Heights" ベクトル長で正規化 SaS・PaP = 0.999 SaS・WH = 0.888 ∴ SaSに近いのはWHよりPaP

ベクトル空間モデルの内積計算コスト M次元の内積計算を N ドキュメント数 計算コストを下げる手法が必要 M ... 辞書の単語数。万単位

Cosine Similarity のアルゴリズム 現実的な計算時間で計算するには 行列がスパースであることを利用 転置インデックスを利用する top K が取得できれば良い 様々な手法で足切り

圧縮全文索引 転置インデックスの弱点 部分文字列検索 分かち書き方式は検索漏れ N-gram 方式は計算量が増加 Suffix Arrays ただし SA は空間コストが高い → Compressed Suffix Arrays (PFI's Sedue)

大規模なバッチ処理 一台で処理仕切れない 例: httpd のログ 複数サーバーで並列分散処理 → MapReduce Hadoop

理論と実践 理論と実践の両側から "やりたいこと"→ "計算機の問題" の道筋をどう発見するかが鍵 JOIN を使わない etc ... バッドノウハウ 教科書には載っていない ベクトル計算 etc ... 古典的な理論 多くの問題は古典的な理論に帰着する "やりたいこと"→ "計算機の問題" の道筋をどう発見するかが鍵 「キーワードでリンクしたい」 → TRIE で Common Prefix Search

まとめ GB単位のデータ処理 TB、PB はまた違った世界 メモリ重要 分散を意識した運用 アルゴリズムとデータ構造

参考文献 Daniel P. Bovet、Marco Cesati "詳解Linuxカーネル 第3版" オライリー・ジャパン 2007 Jeremy D. Zawodny, Derek J. Balling　"実践ハイパフォーマンスMySQL" オライリー・ジャパン, 2004 Christopher D. Manning、Prabhakar Raghavan、 Hinrich Schutz "Introduction to Information Retrieval" Cambridge University Press, 2008 "たつをの ChangeLog" IIR カテゴリ http://chalow.net/clsearch.cgi?cat=IIR