第参回天下一カウボーイ大会・カウボーイセッション/西川徹さん

検索エンジンの技術
　検索エンジンがどこが面白いのか？エキサイティングか？
　Sedueという検索エンジンソフトウェアが主力
　もともとはハードウェアの研究

　検索エンジンの全体像
　　クロール→インデックス→クエリーをインデックスマッチする→ソートする→出力する

　２つの大きな問題
　　大規模分散検索システムの構築
　　　→時には数万台規模
　　　→インデックスが分散している場合、もっともらしく結果をだす
　　　→分散検索かつリアルタイム検索の実現
　　インデックス手法の改善
　　　→どこにデータをおくのか？

　インデックスとは？
　　→検索するだけならgrepでもできる
　　→インデックスをあらかじめ作っておくことで検索を早くする
　　→究極的には全部インデックスを作る

　インデックスの例
　　→転置ファイル
　　→核キーワードことに、そのキーワードがマッチする番号

　転置ファイル少し詳しく
　　→キーワード
　　→どのポスティングリストをとってくればいいのか
　　→４０年ぐらい使われている

　PostingListのエンコーディング
　　→昇順リストのため、差分をとって可変長でかんりする

　インデックスの更新方法
　　→B+-Treeでキーワードを管理する

　ディスクorメモリ
　　→ディスクは遅いので、いかに効率よく置くかが重要
　　→インデックスはディスクの外周に置く
　　→１０％効率よくなれば　100台単位でマシンを圧縮できる

　インデックス手法比較
　　
　CSAの開発
　　→元文章とインデックスで元文章より小さいものを実現

　SSDか検索エンジンに大して引き起こすイノベーション
　これまでのインデックス手法は
　　→HDDに最適化されていた
　　→ディスクはランダムアクセスが苦手
　　→メモリは、要領を集約できない

　SSDとは
　　→レイテンシが低いのが特徴

　単純に既存の方法を移植すればよいのか？
　　→HDDの数倍程度は早くなる
　　　→もともと、HDDでうまく動くようにつくられている
　　　→SSD向けの対応必要

　SSDに適しているアルゴリズム
　　→ランダムアクセスが多いがそうアクセス量が少ない
　　→かきこみが遅い

　SSD版 Sebueを開発
　Wikipedia 50GB検索で 0.03秒
　10万円のサーバーで実現

　まとめ
　検索エンジンは低レイヤーから高レイヤーまで、さまざまなれイヤーの技術が必要
　新しいインデックス手法の開発

　ゲノム検索、Blog検索などに使われている
　どのような人が向いているか？　
　　→いかにうまく作るか。最後は実装力。

検索エンジンも面白そうだけど、根性足りないんで無理そうだ。ｗ