SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

イベントレポート

「実現したいことを計算機の問題に置き換えることが『技術力』」、伊藤CTOが“はてな流”大規模データ処理の極意を語る

関西オープンソースカンファレンス2008セッションレポート


  • X ポスト
  • このエントリーをはてなブックマークに追加

MySQLの運用

 はてなブックマークでは、MySQLを一般的なマスター/スレーブ構成で運用している。つまり、参照系はスレーブにアクセスし、更新はマスターにアクセスするという構成だ。

 このとき更新は1か所で行うため、負荷分散が難しい。Webアプリでは99%が参照クエリなので問題になることは少ないが、マスター負荷を分散する必要が出てくれば、データベースを分割して凌ぐのが現状のセオリーだ。ただし、運用が複雑になり、故障確率も上がるので、できるだけメモリ増設で対応し、データベース分割は「最後の切り札」にした方がよいと伊藤氏は言う。

 データベースの分割を前提とした際のはてなブックマークの運用で特徴的なことは、SQL文でJOINを使わないこと。「RDB屋さんには叱られるだろうが」と前置きしつつ、最近の大規模Webアプリでは、ほとんどがMySQLを「高速なソート機能つきキーバリューストレージ」として使っているという。

 例えば、あるユーザーがブックマークしたURLを5件取ってくるSQLを考える場合、一般的には次のようにINNER JOINしている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回発行する方法をはてなでは採用している。

JOINを排除しwhere~inを利用したSQL発行(※発表資料より)
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」を使用しているという。

  1. バッチ処理でデータを抽出する
  2. 用途に応じたデータ構造でインデックスサーバーを作成する
  3. アプリケーションからRPCでクエリする

 特に、この11月にベータテストが開始された「新しいはてなブックマーク」での新規実装例が多い。いかにその問題解決に適したデータ構造とアルゴリズムを利用するかがポイントになるという。

例1:はてなキーワードリンク

 「はてなキーワード」のリンクでは、昔は巨大な正規表現を使っていたが、現在ではキーワードリンク用のトライ木(Trie)を作って、Common Prefix Searchをしているという。また、キーワードリンクのような機能を高速に実装できる例として、アルゴリズムにエイホ・コラシック(Aho-Corasick)法や、MeCab(オープンソースの形態素解析エンジン)で使われているDouble-Array Trieを使うことも可能だ。バッチ処理で抽出したデータから作ったトライ木をメモリに載せておいて、ダイアリーのエントリーからキーワード辞書に含まれる単語を最小の計算で探し出すことができる。

例2:はてなブックマークのテキスト分類器

 はてなブックマークのカテゴリー分類は、Complement Naive Bayesというアルゴリズムが使われている。多くのスパムフィルタで利用されているベイジアンフィルタ(Bayesian Filter)と同じもので、文書に含まれる単語の出現確率を数えて、この単語が出てくるとSPAM(またはカテゴリー)に分類される確率は何%、別の単語だと何%という数字を持ち続ける。このときリアルタイムでデータベースを更新するのは無理なので、サーバーに保持して検索している。

次のページ
大規模データアプリケーションの開発 その2

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
イベントレポート連載記事一覧

もっと読む

この記事の著者

CodeZine編集部(コードジンヘンシュウブ)

CodeZineは、株式会社翔泳社が運営するソフトウェア開発者向けのWebメディアです。「デベロッパーの成長と課題解決に貢献するメディア」をコンセプトに、現場で役立つ最新情報を日々お届けします。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/3315 2012/07/09 14:52

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング