「はてな流大規模データ処理」を見てきた

(2008-11-11 21:06:05追記)
naoya さんが資料を公開してくださいました。
KOF 2008 の発表資料 - naoyaのはてなダイアリー
(追記おわり)

(2008-11-19 19:25:24追記2)
Codegineにレポートがあがりました。
「実現したいことを計算機の問題に置き換えることが『技術力』」、伊藤CTOが"はてな流"大規模データ処理の極意を語る:CodeZine
(追記おわり)

KOF2008:関西オープンソース2008というイベントに来ています。 はてなのnaoyaさんの講演があったので、講演メモを公開。

#ボクがメモした内容であって、100%言ったとおりに書いてあるわけじゃないので、参考としてご覧ください。

(続き)


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

アジェンダ

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

データの例

  • はてなブックマークのデータ量:五千万件くらいのデータ量
  • このデータに対して何百万人がアクセスしてくる状況でどういう作りにするか
  • レコード数
  • 1073万エントリー
  • 3134万エントリー
  • 4143万タグ
  • データサイズ
  • エントリー2.5GB
  • 何の工夫もなく普通にアクセスすると...200秒待っても結果が帰ってこない

大規模データの難しいところ

開発サーバで開発者が作っている時は快適に動いていても、多数の人間がアクセスすると予想もしなかったところ(SQL文)が刺さる

  • 大規模データの難しいところ
    • メモリ内で処理しきれない
      • メモリはディスクの100倍高速
      • SSDがあっても、精々HDDの数倍程度。
      • メモリ内で処理しきれるかどうかの差はでかい。

スケーリングの要所

  • CPU負荷のスケーリングは簡単
  • IO負荷のスケーリングは難しい
    • 大規模データ
    • データベース

重いサイトに対して「サーバ増やせばいい」って簡単に言うけど、増やしてすむのは幸運な例。

大規模データを扱うコツ

  • いかにメモリですませるか

OSのキャッシュ

  • Linuxのページキャッシュの特性 (略)

メモリを増やすことでI/O負荷軽減

  • 4GB→8GBでI/Oウェイトを減らすことが出来た
  • I/Oウェイトが減ることで、CPU負荷はあがる(それまで本来の仕事が出来ていなかったから)
  • 理想的なのはCPU負荷だけが高い状態。これならサーバを増やせばよい。

キャッシュを前提にしたI/O軽減策

  • データ規模<物理メモリなら全てキャッシュできる
  • 経済的コストとのバランスを考慮
    • 現在なら、8GB-16GBがコモディティ
    • 今のサーバだと、メモリスロットが8枚。
    • 2GBのメモリが一番コストパフォーマンスがいいので、2x8=16GBくらいになる。

単純に台数を増やすと...

  • キャッシュできない割合は変わらないから、あまり意味がない。
  • 局所性を考えるのが大切
  • アクセスパターンを考慮して分散することで、キャッシュできないエリアがなくなる

具体的には

  • RDBMSのテーブル単位での分割
  • 検索のインデックスを辞書の途中で分割
    • 昔はてなダイアリーで、特定の名前の島だけ重いとか、有名サイトの人と同じ名前のエリアだけ落ちるとかいうことがあった。
  • 島で分割
    • 通常のユーザーさんのデータは最近のデータにアクセスが集中する(キャッシュが利きやすい)
    • ボットは古いデータも絨毯爆撃してくる(遅くても許される)
    • 画像APIなど(○○users、とかの。アクセスが多すぎるので別の島に。)

ページキャッシュを考慮した運用

  • OS起動後すぐにサーバを投入しない
    • キャッシュが利いていないので負荷があがってしまって落ちる。
  • 性能評価も、キャッシュが最適化された後で行う
  • データ規模にあわせて搭載メモリを調整する

mysqlの話

  • OSのキャッシュを活かす
  • データ量<メモリを維持する
  • インデックスを貼る
    • インデックスがないと計算量はO(n)
    • あると、O(logn)
  • MySQLのインデックスの癖:実践ハイパフォーマンスMySQL
  • MySQLの分散
    • マスタ・スレーブ構成
    • ロードバランサ:サーバー/インフラを支える技術
    • 更新はマスターへ、参照はスレーブへ
      • RubyならRailsのActiveRecordなど、O/Rマッパーが持っている機能を使える
    • 問題:マスターが分散できない
      • でも、たいていのWEBアプリは参照が99%なので、あまり困らない。
  • パーティショニングを前提にした設計
    • JOINを使わない
    • 実は、DBは「高度なソート機能付きストレージ」として使われている^^;
    • つかわなくても、O/Rマッパーが結構吸収してくれる。
  • パーティショニングのトレードオフ
    • 局所性がまして効率が高くなる
    • 故障確率が上がる
      • 1台分のデータを二台にわけるわけに行かない。或程度重複させるから3台とかになってしまう。
      • 5000円のメモリですむのならその方がいい。

あえて大量データにアクセスしたい場面

  • 全文検索
  • 類似文書検索
  • etc
  • どうする?:
    • RDBMSはつかわない^^;
      • RDBSだと、特定のカラムでのソートしかできない
    • データを定期的にdumpしておいて、自前でインデックスを作る
    • Thriftが便利。
  • 具体例
    • はてなキーワードの検索
    • はてなブックマークのテキスト分類
    • 全文検索エンジン「いい感じ」の文書を上位に、高速に。
  • テキスト走査と転置インデックス
    • Grep:O(n)
    • Pros
    • Cons
    • 辞書はアルファベット順
    • 文書はID(整数)順
      • 圧縮が出来る
      • 昔の圧縮は、ディスクの節約のための技術だったけど、今使っているのは、いかにディスクI/Oを減らすかのための技術
      • CPU負荷は増えるけど、CPUは高速なので大丈夫

検索

  • ベクトル空間モデル:だいたい最近の検索システムはこれを使っている。
  • 「無限次元のデータ」とかになるので、内積の計算量が洒落にならない。
  • でも、ほとんどのデータは0なので、0の多い計算をするアルゴリズムがある。スパース。
  • 全文検索の問題
    • 辞書でキーワードを作ると、新しく出てきた芸能人とかがヒットしなくなる
    • N-Gram(数文字単位でキーワードとする)と、計算量が増える
    • 部分文字列検索が必要になる

大規模なバッチ処理

  • 一台で処理しきれない。例)httpdのログ
  • 複数サーバーで並列分散処理
    • MapReduce:Googleのシステム

理論と実践から

  • バッドノウハウ:教科書には載っていない
  • 多くの問題は古典的な理論に帰着する
  • 一番難しいのは、「やりたいこと」を古典的な問題に置き換えることが最大の問題

まとめ

  • GB単位のデータ処理
    • TB,PBになるとまた違う世界になるかも。
    • メモリ重要
    • 分散を意識した運用

QA

  • Q:DBMSに手を入れようとは思わなかったの?
  • A:考えないではなかったけど、今のところやっていない
  • Q:実際のデータって始まってみないと分からないけど、どうするの?
  • A:たいていの場合、ユーザーは急に増えないので、やりながら考えていけば大丈夫。はてなブックマークのリニューアルのような場面では、知識を持った人がレビューする必要がある。

追記 2008-11-10 19:56:18

 しまった。あとで感想を書こうと思っていたらブクマがつき始めている...あたふた。

正直ちゃんとメモしきれなかったところがあります。統計処理の手法の名前とか。
以前お話を聞いた時には、伸び続けるサービスに対して根性で何とかしてきた、実経験に裏打ちされたノウハウみたいな話が多かったのですが、今回、とてもアカデミックになったと感じました。きっと、プリファードインフラストラクチャーさんとの提携も影響しているのだと思います。

たぶんそれは、とりあえず作ってみたWEBサービスにユーザーがどんどん集まるのにあわせて成長してきたはてなやnaoyaさんが、そういう勢いだけじゃなくて、たくさんのユーザーがつかうサービスとしてふさわしい安定性とか、そういうものを実現するために一歩成長した証なんじゃないのかな、と。

あんまり最近ぱっとしなかった(失礼!)はてなさんですが、もしかしてさなぎみたいに繭にこもって次の成長の準備をされていたのかもしれません。
これから羽化する新生はてなに期待しています。

| | トラックバック(1)
カテゴリ:

トラックバック(1)

このブログ記事を参照しているブログ一覧: 「はてな流大規模データ処理」を見てきた

このブログ記事に対するトラックバックURL: http://mogya.com/mt/mt-tb.cgi/654

» 計算量+ソート-でつながるブログリング(blogring.org)~のトラックバック

計算量+ソートに関するブログをまとめています。 続きを読む

このブログ記事について

このページは、 もぎゃが 2008年11月 8日 10:43に書いたブログ記事です。

ひとつ前のブログ記事は「 WebTeko2に行ってきた。 」です。

次のブログ記事は「 メイドめーるを公開 」です。

最近のコンテンツは インデックスページ で見られます。過去に書かれたものは アーカイブのページ で見られます。

Powered by
Movable Type