MySQLの運用
はてなブックマークでは、MySQLを一般的なマスター/スレーブ構成で運用している。つまり、参照系はスレーブにアクセスし、更新はマスターにアクセスするという構成だ。
このとき更新は1か所で行うため、負荷分散が難しい。Webアプリでは99%が参照クエリなので問題になることは少ないが、マスター負荷を分散する必要が出てくれば、データベースを分割して凌ぐのが現状のセオリーだ。ただし、運用が複雑になり、故障確率も上がるので、できるだけメモリ増設で対応し、データベース分割は「最後の切り札」にした方がよいと伊藤氏は言う。
データベースの分割を前提とした際のはてなブックマークの運用で特徴的なことは、SQL文でJOINを使わないこと。「RDB屋さんには叱られるだろうが」と前置きしつつ、最近の大規模Webアプリでは、ほとんどがMySQLを「高速なソート機能つきキーバリューストレージ」として使っているという。
例えば、あるユーザーがブックマークしたURLを5件取ってくるSQLを考える場合、一般的には次のようにINNER JOIN
しているSQLになる。
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 | +-------------------------------------------------------------------+
ここで、bookmarkテーブルとentryテーブルを分割するとJOIN
が使えないので、where~in
を利用してSQLを2回発行する方法をはてなでは採用している。
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)
JOIN
した方が速そうだが、スケーラビリティを考慮すると、分割した方が速いという。また、はてなでは独自のORマッパ(DBIx::MoCo)の中でこれを実現することで、コードも読みやすくしているという。
大規模データアプリケーションの開発 その1
RDBで限界になったときには、独自の大規模データ検索アプリケーションを作成する。データの用途が決まっている場合、それに特化したデータ構造を持たせれば高速に検索できる。
独自の検索アプリケーションは、次のような構成になっている。はてなブックマークでは、Facebookが開発したフレームワーク「Thrift」を使用しているという。
- バッチ処理でデータを抽出する
- 用途に応じたデータ構造でインデックスサーバーを作成する
- アプリケーションからRPCでクエリする
特に、この11月にベータテストが開始された「新しいはてなブックマーク」での新規実装例が多い。いかにその問題解決に適したデータ構造とアルゴリズムを利用するかがポイントになるという。
例1:はてなキーワードリンク
「はてなキーワード」のリンクでは、昔は巨大な正規表現を使っていたが、現在ではキーワードリンク用のトライ木(Trie)を作って、Common Prefix Searchをしているという。また、キーワードリンクのような機能を高速に実装できる例として、アルゴリズムにエイホ・コラシック(Aho-Corasick)法や、MeCab(オープンソースの形態素解析エンジン)で使われているDouble-Array Trieを使うことも可能だ。バッチ処理で抽出したデータから作ったトライ木をメモリに載せておいて、ダイアリーのエントリーからキーワード辞書に含まれる単語を最小の計算で探し出すことができる。
例2:はてなブックマークのテキスト分類器
はてなブックマークのカテゴリー分類は、Complement Naive Bayesというアルゴリズムが使われている。多くのスパムフィルタで利用されているベイジアンフィルタ(Bayesian Filter)と同じもので、文書に含まれる単語の出現確率を数えて、この単語が出てくるとSPAM(またはカテゴリー)に分類される確率は何%、別の単語だと何%という数字を持ち続ける。このときリアルタイムでデータベースを更新するのは無理なので、サーバーに保持して検索している。