[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ

Architecture これは読むべき アルゴリズム インフラ システム設計 Comments

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ
タイトル
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ
著者
伊藤 直也 (著), 田中 慎司 (著)
出版社
技術評論社
Amazonで購入する

大規模サービスの運営、大変だということは分かっていても、じゃあ実際にどういうふうに大変なのか。実際に体験してみないとこの大変さはわからないと思います。

でも、実際に大規模サービスの開発・運営に携わることになったら！？

本書は、はてなで実際に運用されているサービスを元に、大規模サービス技術のノウハウを解説しています。実際にはてなのインターンシップで講義資料として使われているものがベースになっているので、分かりやすくかつ、実用的です。

Web サービスはいつユーザ数が爆発するかわからないという面白さがある一方、きちんとサービスのノウハウがないとシステムダウンにすぐに繋がってしまうという怖さがあります。

すべてのWeb サービス開発エンジニアにおすすめです。本書で本質的な知識を得て、準備万端にしておくと良いと思います。

本書の目次

  1. 大規模Webサービスの開発オリエンテーション - 全体像を把握する
    1. 本書の源 - 本書で説明すること、しないこと
    2. 大規模なサービスと小規模なサービス
    3. 成長し続けるサービスと、大規模化の壁
    4. サービス開発の現場
  2. 大規模データ処理入門 - メモリとディスク、Webアプリケーションと負荷
    1. はてなブックマークのデータ規模 - データが大きいと処理に時間がかかる
    2. 大規模データ処理の難所 - メモリとディスク
    3. スケーリングの要所
    4. 大規模データを扱うための基礎知識
  3. OSのキャッシュと分散 - 大きなデータを効率良く扱うしくみ
    1. OSのキャッシュ機構
    2. I/O負荷の軽減策
    3. 局所性を活かす分散
  4. DBのスケールアウト戦略 - 分散を考慮したMySQLの運用
    1. インデックスを正しく運用する - 分散を考慮したMySQL運用の大前提
    2. MySQLの分散 - スケーリング前提のシステム設計
    3. MySQLのスケールアウトとパーティショニング
  5. 大規模データ処理[実践]入門 - アプリケーション開発の勘所
    1. 用途特化型インデクシング - 大規模データを捌く
    2. 理論と実践の両側から取り組む
  6. [課題]圧縮プログラミング - データサイズ、I/O高速化との関係を意識する
    1. [課題]整数データをコンパクトに持つ
    2. VB Codeと速度感覚
    3. 課題の詳細と回答例
  7. アルゴリズムの実用化 - 身近な例で見る理論・研究の実戦投入
    1. アルゴリズムと評価
    2. はてなダイアリーのキーワードリンク
    3. はてなブックマークの記事カテゴライズ
  8. [課題]はてなキーワードリンクの実装 - 応用への道筋を知る
    1. [課題]はてなキーワードリンクを作る
    2. 回答例と考え方
  9. 全文検索技術に挑戦 - 大規模データ処理のノウハウ満載
    1. 全文検索技術の応用範囲
    2. 検索システムのアーキテクチャ
    3. 検索エンジンの内部構造
  10. [課題]全文検索エンジンの作成 - 基本部分、作り込み、速度と精度の追求
    1. [課題]はてなブックマーク全文検索を作る
    2. 回答例と考え方
  11. 大規模データ処理を支えるサーバ/インフラ入門 - Webサービスのバックエンド
    1. エンタープライズ vs. Webサービス
    2. クラウド vs. 自前インフラ
  12. スケーラビリティの確保に必要な考え方 - 規模の増大とシステムの拡張
    1. レイヤとスケーラビリティ
    2. 負荷の把握、チューニング
  13. 冗長性の確保、システムの安定化 - ほぼ100%の稼働率を実現するしくみ
    1. 冗長性の確保
    2. システムの安定化
    3. システムの安定化対策
  14. 効率向上作戦 - ハードウェアのリソースの使用率を上げる
    1. 仮想化技術
    2. ハードウェアと効率向上 - 低コストを実現する要素技術
  15. Webサービスとネットワーク - ネットワークで見えてくるサービスの成長
    1. ネットワークの分岐点
    2. さらなる上限へ
  16. いまどきのWebサービス構築に求められる実践技術 - 大規模サービスに対応するために
    1. ジョブキューシステム - TheSchwartz, Gearman
    2. ストレージの選択 - RDBMSかkey-valueストアか
    3. キャッシュシステム - Squid、Varnish
    4. 計算クラスタ - Hadoop

おぼえがき

小規模サービスと大規模サービスの違い

スケーラビリティの確保と負荷分散

大量のアクセスがあるサービスでは、サーバ1台では処理しきれない負荷を同処理するかが一番の問題です。ここ10年のトレンドとしてはいわゆる「スケールアウト」がこの問題に対する戦略の基礎になります。

大量のアクセスのある大規模サービスでは、スケーラビリティの確保と負荷分散が重要な問題になります。

ハードウェアが安くなってきた最近では、高価なハードウェアを購入するよりもコストを削減できます。ただその代わりに考えないといけないことも増えます。

複数のハードウェアを効率良く使うための負荷分散のしくみや、データの同期の問題、ネットワークのレイテンシ（遅延時間）をどうするか。

冗長性

スケールアウトでサーバを複数台用意すると、サーバの故障率は高くなります。どこかのサーバが1台故障したからといって、サービスが停止してしまうことは避けなければなりません。

省力運用

サーバ台数が増えてくると、それぞれのサーバの状況を把握することが困難になってきます。セキュリティ設定、ソフトウェアのバージョンなど、管理しなければならないことも増えてきます。

監視用ソフトウェアを使って自動化を行ったとしても実際に確認するのは人間の役目になります。いかに手間を掛けずに健康状態を維持するか。

開発方法の統制

大規模サービスになると、当然そのサービスに携わる人は増えてきます。効率化を図るための標準化や標準ツールの策定、教育やマネージメントなどの必要性が出てきます。

大規模データの処理

大規模Webアプリケーションを運用するにあたっての苦労の多くは、この大規模データの扱いに集約されます。

データが小さいうちは、とくに工夫をしなくてもすべてメモリで処理できますし、複雑なアルゴリズムを使うよりもナイーブなアルゴリズムのほうがオーバーヘッドがないため早い、なんてこともままあって、I/O負荷などはまず問題となりません。しかし、サービスがある程度以上の規模になるとデータは増加します。このデータ量が分水域を超えたところで問題が顕在化します。そしてその対策は、応急処置ではなかなかに難しい。ここが大規模サービスの難所です。

ミニマムスタートと、変化を見込んだ管理と設計

サービスが小規模の時には、あれこれ考えて早過ぎる最適化を行うのはよくありません。かといって、何も考えずにシステムを設計するのもまたよくありません。

サービス設計時にある程度のキャパシティ管理とデータが莫大に増加してしまわないような設計を行った上で、ミニマムスタートをきる。それがサービスを開始するときのコツです。

大規模データ処理の難所

大規模データ処理の難しいポイントは、メモリ内で計算ができないことです。

コンピュータはメモリとディスクとで、105〜106倍以上の探索速度の差があります。また、メモリとディスクの転送速度では、メモリが約7.5GB/秒ほど出るのに対して、ディスクは58MB/秒ほどしかでません。

SSD(Solid State Drive) などの記憶装置が出てきたことで探索速度の差は縮まってきていますが、転送速度の差は埋めることがまだ出来ていない状況です。

単一ホストの負荷

「負荷分散」と言う言葉から思い浮かべるのは、多くの場合、複数のホストに処理を担当させる文字通りの「分散」です。しかし、そもそも1台で処理できるはずの負荷をサーバ10数台で分散するのは本末転倒です。単一のサーバの性能を十分に引き出すことができてはじめて、複数サーバでの負荷分散が意味をなします。

ボトルネック見極め作業の基本的な流れ

推測するな、計測せよ

  • ロードアベレージを見る
  • CPU、I/Oのいずれがボトルネックかを探る
  • CPUの場合、ディスクやメモリはボトルネックになっていないかを確認。プログラムのバグも確認する
  • I/Oの場合、スワップが発生していないかを確認。メモリの使い方が適切か、足りているかを確認する

大規模データを扱う勘所

プログラミングの3つの勘所

  1. いかにメモリで済ませるか
  2. データ量の増加に強いアルゴリズムを使う
  3. データ圧縮や検索技術を駆使する

3つの基礎知識

  1. OSのキャッシュ
  2. 分散を考慮したRDBMSの運用
  3. アルゴリズムとデータ構造

OSのキャッシュのしくみ

参考

キャッシュを前提に I/O を軽減するというのが、I/O 対策の基本です。扱うデータ規模に対して十分な物理メモリを用意しておくことで、データがすべてキャッシュにのるので I/O が軽減できます。

また、データを圧縮することによって、そのままではキャッシュに全部のらなかったものがのるようになって、効率化ができるようになります。

分散のポイント

CPU が追いついていないときにサーバを増やす分には単純に増やせばよいですが、ディスクアクセスによる負荷を軽減する場合は単純に増やすことはできません。

OS のキャッシュによって I/O を軽減する目的でサーバを増設する場合には、アクセスパターンを考慮して十分にデータがキャッシュにのるようにサーバを増やす必要があります。つまり、単純に同じサーバを増やすというのでは効果がないことがあります。

特に、データベースがボトルネックになっているときには、データ量が多いテーブルをメモリが潤沢なサーバに移すなどのアクセスパターンによってサーバを分散させるようにする必要があります。

局所性を考慮した分散

いかにしてデータをキャッシュにのせた状態で処理するかを考えて、分散を行う必要があります。例えば、データベースの分散の手法には様々ありますが、主なものには次のものがあります。

テーブル単位での分割

1台のサーバのメモリ上にのるように、テーブル単位でサーバを分割する方法。アプリケーション側の変更も必要になる

データの途中で分割

テーブル単位で分割ではなくデータの途中から別のサーバに分割する方法。たとえば、イニシャルがA〜M、N〜Zでサーバを分ける。これも、アプリケーション側の変更が必要になる

リクエストパターンによって分割する

最近のデータ、過去のデータなどといった感じでリクエストのパターンによってデータを分割し、サーバを分散する方法。API からのリクエスト、検索エンジンからのリクエストなどで分けたりもする

テーブルを分散させるときには、アプリケーション側で JOIN を極力使わないようにする必要があります。多くの RDBMS では別サーバにあるテーブルどうしを JOIN することができません。

サーバ再起動時には一度データをリードする

MySQLなどのDBサーバを運用するにあたって、大規模なデータを扱う場合にはここに注意が必要です。たとえば、メンテナンスなどでサーバを再起動した場合、それまでにメモリにキャッシュされていたページキャッシュは、すべてフラッシュされてしまいます。(中略）。一度必要なデータ全体に読み込みをかけてから、プロダクション環境に戻すといった工夫が必要になります。

Bツリーインデックスはハードディスクのアクセスと相性がいい

参考

Bツリーはそのデータ構造上、ページキャッシュと相性がいいです。なので、データベースでインデックスを貼る際にはBツリーインデックスを使うことが多いです。また、Bツリーをさらに最適化したものに、B+ツリーというものもあります。

MySQLのインデックスの癖

複数のカラムがインデックス利用の対象になった場合です。(中略)。MySQLは1回のクエリでインデックスを1つしか使わない、という癖を持っているのが原因です。

実践ハイパフォーマンスMySQL 第2版
  • 『実践ハイパフォーマンスMySQL 第2版』
  • 著者: Baron Schwartz (著), Peter Zaitsev (著), Vadim Tkachenko (著), Jeremy D. Zawodny (著), Arjen Lentz (著), Derek J. Balling (著), 伊藤 直也 (監訳) (翻訳), 田中 慎司 (監訳) (翻訳), 吉川 英興 (監訳) (翻訳), 株式会社クイープ (翻訳)
  • 出版社: オライリージャパン

インデックスが効くかどうかは、explain コマンドを使うと確認できます。

更新系のデータベースでもスケールしやすい kye-value ストア

RDBMS を使っていると、参照系のクエリに関しては、キャッシュに注意すればサーバを増設するだけなのでスケールしやすいです。しかし、更新系のクエリとなるとサーバの増設はとたんに難しくなります。

そこで、そもそも RDBMS を使わないという選択肢をとることも考えられます。単に値を書きこんで取り出すだけで、RDBMS の統計処理やソートなどが不要なのであれば、key-value ストアを使用するという方法を考えるといいです。

単に値を保存して取り出すだけで、RDBが持つ複雑な統計処理や汎用的なソート処理が必要ないなら、key-valueストアはオーバーヘッドも少なく圧倒的に速いし、スケールしやすいんです。

圧縮アルゴリズム

アルゴリズムのオーダー表記

右に行くほど計算量が多くなります。

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) ... O(nk) < O(2n)

はてなで使っている（使っていたいた）マッチングアルゴリズムやデータ構造

検索システムの6つのステージ

全文検索システムを作る上で、大まかに作業を分けると、6つのステージに分解できます。

クロール

検索する対象のドキュメントを見つける

格納

ドキュメントを保存・格納する

インデクシング

ドキュメントからインデックスを構築する

検索

インデックスを元にクエリを含むドキュメントを検索する

スコアリング/ランキング

検索結果をどのような順番で表示するかを決める

結果表示

結果を表示する

Introduction to Information Retrieval

仮想化のデメリット

はてなでの経験則だそうですが、だいたい、

  • CPUで2〜3%
  • メモリの性能も1割くらい
  • ネットワークの性能は半分くらい
  • I/O性能が5%くらい

落ちるようです。

SSDの寿命

SSDを扱う上で一番気になるのは、いつどのように壊れるのか、ということです。HDDが時間と共に消耗して壊れるのは周知の事実なのですが、SSDも時間とともに消耗して壊れる、と考えるのが自然です。

フラッシュメモリも書き込みの消耗で壊れてしまうようです。新しいメディアを使うときは、それがどのように壊れるのかをきちんと確認して、監視する仕組みを整えておくことが必要です。

ネットワークの限界

1つのサブネットは500ホストくらいが限界のようです。サブネット内にホストがたくさんあると、ブロードキャストパケットの受信だけでも結構 CPU を食うようです。

ジョブキュー、ストレージ、キャッシュシステム、計算クラスタ

いまどきのWebサービスに求められる実践技術

  • ジョブキューシステム – TheSchwartz, Gearman
  • ストレージ – RDBMS, key-valueストア
  • キャッシュシステム – Squid, Varnish
  • 計算クラスタ – Hadoop

ストレージ選択のフローチャート

本書より

flowchart.png

関連記事