yaotti's diary

Software is Eating the World

KOF(関西オープンフォーラム)へ

event

土曜日だけ行ってきた．
KOF2008：関西オープンソース2008

会場は大阪南港ATCというところで，かなり寂れていた．テナントが3分の1くらいしか入ってない．綺麗な建物なのにもったいない．
立地を考えると仕方ないのか．


はてなの伊藤さんとGoogleの及川さんの，2つの講演を見てきました．
メモが長いので感想を先に書くと．

  • 理論と実践(経験)両方が必要，ということを聞けてよかった
  • 常に「どうあるべき」か考えるべきだ
  • 歴史に学べることはたくさんありそうだ

といったところ．


以下講演のメモ．

はてな流大規模データ処理(伊藤直也さん:id:naoya)

  • 難しいところ
    • 物理メモリ内で全てを計算できない

メモリとディスクの速度差が100倍以上あるので，ディスクアクセスがあると極端に遅くなる

      • 7.5GB/secと58MB/sec
    • 開発段階ではメモリに収まるが，実際のサービスでは収まりきらない
    • CPU負荷のスケーリング(増設するだけ)は簡単，I/O負荷のスケーリング(メモリに収めるため工夫する)は難しい
  • 大規模データを扱うコツ
    • いかにメモリで済ませるか
    • データ量の増加に強いアルゴリズム，データ構造を使用する
  • 大規模データを前に知っておくべきこと
    • linuxのページキャッシュの特性
      • linux(x86)のページング機構
      • リニアアドレス→ページング→物理アドレス
    • ディスクの内容をメモリに読み込む(ぺーじガ作成)
    • このページは破棄されない←ページキャッシュ
    • linuxはメモリが空いていればキャッシュ
  • sarコマンド
    • iowait
      • メモリ4GBだと18%
      • 8GBだと0.8%
  • CPUだけが仕事をしているのが理想的
    • キャッシュしきれない規模
    • I/O分散では局所性を考慮
    • 自前インデックス
  • リクエストパターンで「島」に分割
    • 通常リクエスト→最近のものが多い，キャッシュが有効
    • botやfeed→レスポンスが少し遅くてもok，キャシュが効きにくい
    • 画像API→負荷が大きい

などに分割する．

  • knowhow
    • OS起動後すぐにサーバを投入すると落ちる→キャッシュがない．
      • catでとりあえずメモリに載せるとか
  • 分散を考慮したMySQL
    • データ量<物理メモリを維持
    • インデックスが重要．B-tree
      • 計算量のオーダーはデータ量が増えるほど効いてくる．

Amazon.co.jp： 実践ハイパフォーマンスMySQL: ジェレミ・D. ザウドニ, デレク・J. ベリング, Jeremy D. Zawodny, Derek J. Balling, 林 秀幸: 本

  • ロードバランサ(lvs)をapp serverとDB slaveの間に
    • 参照はスレーブ
    • 更新はマスタ
    • マスタはスケールしないが，web appは参照が9割以上なので大丈夫
    • マスタに関してはテーブル分割で凌ぐ
  • パーティショニングを前提に(キャッシュのため)
    • RDBだがjoinを使わない．(大規模では多い)
      • where ... in ...にてJOINを排除．
      • 2回クエリを投げることになるが，大規模ではこのほうが速い
  • 大規模データのアプリケーション開発
    • RDBMSでは限界→バッチ処理でデータを抽出する
    • インデックスサーバ,rpcでアクセス
    • 定期的にdumpしたデータからデータ構造を構築
      • 用途に適したデータ構造に
    • TRIE
    • Aho-Corasick
    • Double array TRIE
  • はてブのテキスト分類器
    • Complement Naive Bayes
  • 転置インデックスのソート
    • 文書はID順
    • 差分を取ってδ符号で圧縮
    • そのままだと辞書の単語数*文書数なので計算コストが大きすぎる
    • →CosineSimilarityのアルゴリズム
    • 行列がスパース(疎)であること(出てこない，0の単語が多い→その計算を速くする)
    • top kが取得できればよい，足切りする
  • 一台で処理しきれないバッチ処理をどうするか→MapReduceで分散処理(Hadoop)
  • 理論と実践
    • やりたいこと→計算機の問題，の道筋を発見するのが一番難しい(ex. キーワードでリンクしたい→CommonPrefixSearchを使える，と繋げるのが難しい)
  • まとめ
    • TB, PBになるとまた違った方法になるだろう
    • ディスクでなくメモリをいかに使うか
    • アルゴリズムとデータ構造によって運用コストを下げられる
  • 質疑応答

Q:RDBMSそのものをハックするのは?
A:まだその段階には至っていない．PB，TBになるとそうなるかもしれない
Q:最初のアプリケーションでは負荷分散はわからないのではないか?
A:アプリケーションを作っていく中で考えていく．


Google Chrome 完全技術解説(及川卓也さん:id:takoratta)

  • なぜブラウザを作ったのか
    • もしGoogleが今の時代を考え，0から作るとどうなるか
    • どうあるべきかを定義する
  • Rediscover the web
  • Do not reinvent the wheel
    • 先人の知恵を活用する
  • Web Appとローカルアプリケーションを同様に扱えるように

(クエリからダイレクトに情報のあるページへ飛ぶべき，ということを目指してるんだな)

  • chromeの内部構造
    • WebKit(Apple, js engineとグラフィックライブラリは除く)
    • SGL(グラフィック)
    • V8(js engine)
  • 昔のコンピュータ：1つおかしなアプリケーションを動かすとOS全体が不安定に．
  • 今のブラウザも同じようなもの→chromeは現在のオペレーティングシステムの発想を応用
  • プロセスは2種類：ブラウザプロセス，レンダラプロセス
    • 同じサイトなら複数タブを1プロセスにすることも
  • beta channel&dev channel(every week)