Googleを支える技術

最終更新:

masurai

- view
管理者のみ編集可
出典: パーソナル百科事典『マスペディア(Masupedia)』


Googleを支える技術 ‾巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)
西田 圭介
技術評論社
売り上げランキング: 22
おすすめ度の平均: 5.0
5 Googleの分散処理をわかりやすく解説

メモ・考えたことなど


  • インデクシングやランキングアルゴリズム自体の技術というよりも、それをいかに膨大なWeb空間検索のために利用するか、といった実践的技術の内容が書かれてる
  • 例えば、DB構造とか分散処理のさせ方とか、どのような機器をどのように並列するかとか、コストや消費電力の観点での解決策も載ってる

キーワード・キーフレーズ


  • Googleにブラウザからアクセスするとアクセス元にもっとも近いGoogleデータセンタに繋がる
  • ランキングのために PageRank、アンカーテキスト、単語情報(位置、前後関係、など)を利用
  • Googleのインデックスには億単位のキー⇒リレーショナルデータベースでは性能的に× もっと原始的で、しかし限界まで効率化されたシステムが必要
  • 文字列は全て数値に置き換える⇒DB内で文字列がそのまま重複して保存されるのを回避
  • 多段階構造のデータ構造(BigTable)
  • クローラ::最もトラブルに遭いやすいシステム。特定サイトにアクセス集中×。応答ない場合等の対処など。DNSがボトルネック⇒内部キャッシュ管理。
  • インデクシング
    • Lexicon::単語文字列とwordId
    • Barrels::docIdとその中に含まれるwordId一覧を持つテーブル。分散のためにはwordIdによってテーブルを分割。特定のwordを検索する際には一つのインデックスに負荷が集中してしまい処理分散にならない(初期Google版。現在はBarrelsに代わりShardを使う)
    • Shard::docIdとその中に含まれるwordId一覧を持つテーブル。Barrelsとの違いは、docIdによってテーブルを分割している点。これによりインデックスあたりのdocIdの数が限られる。特定のwordを検索する際に複数インデックスを並列して検索でき、効率が良い。また、処理するPCの性能によりインデックスあたりのdocIdの数を調整でき、また各インデックスを検索する処理時間の推定も容易などの利点。
    • Links::リンク関係。docIdとdocIdのセット
    • 検索処理の流れ(初期型Google)
 1.検索後をLexicon使いwordIdに変換
 2.wordIdをキーに分散されたShardを調べ、そのwordId含むdocIdリスト得る
 3.各インデックスサーバで担当する範囲内でランキングを行う
 4.全ての情報を統合し、docIdそれぞれについてのランキングを出す

    • 検索処理の流れ(新型Google)
 1.検索後をLexicon使いwordIdに変換
 2.wordIdをキーにBarrelsの転置インデックスを調べ、そのwordId含むdocIdリスト得る
 3.docIdそれぞれについてランキング計算し並べ替え

  • スケールアップ::より優れたハードを使う  スケールアウト::ハードの数を増やす
  • Googleでは普及していて安価なハードを大量に並列化する方法
  • 故障してもいいようにソフトウェアで対処⇒UPSやRAID等は不要(H/Wレベルでの信頼性向上はしない)
  • GFS::GoogleFileSystem。独自の分散ファイルシステム。膨大なデータの通り道。キューとして用いるだけ。更新、修正等できない。ロックもない。
  • BigTable::分散ストレージシステム。データベースのような存在。通常のRDBのように行・列ではなく。列の代わりに行キー、コラムファミリーの二種類。行キーは行特定のために用いる。コラムファミリーは複数列になり得て、複数列のうちのどのデータかを指す際にコラムキーを用いる。コラムキーはいくつでも増やすことができ、行によってコラムキーの数が違ってもよい。各セルにはタイムスタンプの概念があり、過去の情報も持つ。3次元的な構造。(詳しくはp90~参照)

  • 開発体制
    • 仕事は与えられるものではなく、自分でみつけだす
    • 利用できる言語は限られる(C++,Java,Python)各言語ごとにコーディングスタンダードがある。
    • アイデア浮かぶ⇒DB登録⇒社員による投票、コメント
    • デモ&ドキュメント作成を重視
    • TechTalk::社内でいつでもプレゼン開ける。デモ見せてPJアピールや、社外エンジニアの講演など
    • TGIF::Thanks God! it's Friday 自由参加の集会。息抜き、交流。重要な情報交換の場
    • Googleレジュメ::担当案件や経歴、得意分野を公開
    • スニペット::毎週書く週報
    • 日常的に使うOSはUbuntuを独自カスタマイズしたGoobuntu
    • 大規模DBにはBigtable。それ以外はMySQLを多用。

コメント


名前:
コメント:

目次


第1章 Googleの誕生
 1.1 よりよい検索結果を得るために
 1.2 検索エンジンのしくみ
 1.3 クローリング -- 世界中のWebページを収集する
 1.4 インデックス生成 -- 検索用データベースを作り上げる
 1.5 検索サーバ -- 求める情報を即座に見つける
 1.6 まとめ
第2章 Googleの大規模化
 2.1 ネットを調べつくす巨大システム
 2.2 世界に広がる検索クラスタ
 2.3 まとめ
第3章 Googleの分散ストレージ
 3.1 Google File System -- 分散ファイルシステム
 3.2 Bigtable -- 分散ストレージシステム
 3.3 Chubby -- 分散ロックサービス
 3.4 まとめ
第4章 Googleの分散データ処理
 4.1 MapReduce -- 分散処理のための基盤技術
 4.2 Sawzall -- 手軽に分散処理するための専用言語
 4.3 まとめ
第5章 Googleの運用コスト
 5.1 何にいくら必要なのか
 5.2 CPUは何に電気を使うのか
 5.3 PCの消費電力を削減する
 5.4 データセンターの電力配備
 5.5 ハードディスクはいつ壊れるか
 5.6 全米に広がる巨大データセンター
 5.7 まとめ
第6章 Googleの開発体制
 6.1 自主性が重視されたソフトウェア開発
 6.2 既存ソフトウェアも独自にカスタマイズ
 6.3 テストは可能な限り自動化する
 6.4 まとめ


記事メニュー
目安箱バナー