『Web開発者のための大規模サービス技術入門』を読んだ。とても勉強になった。

特に興味深く読めたのは次の部分。

• ハードウェアレベルの話（第2回）
• OS（Linux）のキャッシュまわりの話（第3回）
• DBのスケールアウト戦略の話（第4回）
• アルゴリズムの話（第7回）

その中でもアルゴリズムの話が一番収穫があった。 正直苦手意識がある分野だったのでこれまで避けがちだったが、Webアプリケーションを題材にして具体的な事例や効果が合わせて書かれていたので、楽しんで読むことができた。

次のステップとして、以下の文を引用。

大規模なWebアプリケーションを運用開発しようとすると、この理論と実践、その両方をやらなくてはいけない。

この辺をバランス良くやっていくのは、はてなのような会社に求められている技術的要件です。どちらか一方ではダメです。

理論を追求していって論文を書けるくらいの知識を持っていても、いざ実装しようとすると、実装のために必要ないろいろなバッドノウハウが出てきますし、一方でたとえバッドノウハウだけ知ってても、大規模なデータを目の前に出されたときに「どう処理していいかわからない」ということになってしまう。 ですから、両方をバランス良く使えるようにならないといけません。

※ p.115 より引用

本書を読んだ段階ではまだ理論を学んだだけで実践まで到達していないので、ここから何らかの方法で実践につなげて引き出しを増やしていきたい。

復習用読書ログ

以下は、自分の復習用に作った読書ログ。
「これは覚えておきたい」と思ったことを中心にまとめている。

第2回：大規模データ処理入門

• 大規模データの難しい点を端的に言うと「メモリ内で計算できない」こと。メモリ内で計算できれば力技でやっても計算はそこそこ速く返ってくる。
• メモリとディスクの速度差は約10万~100万倍 → メモリの方が圧倒的に速い
• メモリは電気的な部品であるため、探索速度に物理的構造は関係ない
• ディスクはなぜ遅いか
  • 「ヘッドの移動」と「円盤の回転」という2つの物理的な移動が必要になるため
  • さらに、もしデータがディスク上にバラバラに配置されている場合はもっと遅くなる
• ディスクの遅さに対するOSレベルの工夫
  • OSは連続したデータを同じようなところに固める
  • データを取得するときは1byteずつ読み取るのではなく4KBくらいをまとめて読み出す
  • → このようにしてディスクの回転を少なくし、処理速度を上げている
• 転送速度、バスの速度差
  • メモリにしてもディスクにしてもCPUとバスでつながっている。このバスの速度にもかなりの差がある
  • メモリ：7.5GB/sec
  • ディスク：58MB/sec
  • ※ hdparmというLinuxのツール（コマンド）で転送速度を測定できる
• Webアプリケーションの3層構造：Proxyサーバ - APサーバ - DBサーバ
• CPUバウンドなサーバのスケーリングは簡単 → 同じ構成のサーバを増やしてロードバランサで分散する
• I/Oバウンドなサーバのスケーリングは難しい
• 大規模データを扱うための勘所
  • いかにしてメモリで済ませるかを考える
    • ディスクのシーク回数の最小化
    • 局所性を活かした分散
  • データ量の増加に強いアルゴリズム、データ構造を使う
    • 例：線形探索の計算量はO(n)だが、二分探索はO(log n)
  • データ圧縮、情報検索技術を有効活用する

第3回：OSのキャッシュと分散

• OSにはキャッシュ機構がある。Linuxではページキャッシュ等と呼ばれる
• このLinuxのページキャッシュの特性は知っておくべき
• 仮想メモリ機構
  • OSは仮想メモリ機構を持っている
  • 仮想メモリ機構は、論理的なリニアアドレスを物理的な物理アドレスへ変換する働きをする
  • **OSはメモリを直接プロセスに渡さず、カーネルの中でメモリを抽象化して管理する。**これには様々な利点がある。
  • ページ：OSが物理メモリを確保・管理する単位
• プロセスがディスクからデータを読み出す流れ
  • ① OSがディスクから4KBのブロックを読み出す
  • ② 読み出したデータをメモリに置く（プロセスは直接ディスクにアクセスできないため、このステップが必要）
  • ③ OSはメモリの番地をプロセスに教える
  • ④ プロセスがメモリからデータを読み出す
• ページキャッシュ
  • Linuxではディスクにデータを読みにいくと必ず1回メモリに置いて、それが必ずキャッシュされる。したがって、2回目以降のアクセスが高速になる
  • ページ = 仮想メモリの最小単位
• LRU
  • メモリの余裕が1.5GBあって、4GBのファイルを全部読んだらどうなるか
  • LRU（Least Recently Used）：一番古いものを破棄して一番新しいものを残す
  • → LRUの仕組みを使うので、最近読んだところがキャッシュに乗って、昔読んだ古い部分は破棄される
• I/O軽減策は、OSのキャッシュを前提にI/Oの軽減を図るのが効果的
• I/O対策のポイント
  • ① 扱うデータのサイズに注目する。データ規模に対して物理メモリの方が大きければ全てキャッシュできる
  • ② 経済的コストとのバランスを考慮する。ハードウェア側（メモリ量）で頑張るべきか、ソフトウェア側で頑張るべきか？
• データがキャッシュに乗り切らない規模になったらどうするか？
  • ここで初めて複数サーバにスケールさせるという考え方が浮かんでくる
  • DBサーバを増やしたいときというのは、負荷軽減というよりもキャッシュの容量を増やしたい、あるいは効率を上げたいというときのほうが多い
  • ただし、単純に台数を増やしただけではキャッシュできない割合が変わらないのでほぼ意味がない
• 局所性を考慮して分散する
  • アクセスパターンを考慮して分散させることでキャッシュを最大限利用する
  • はてブの例：人気エントリーのページを表示する場合はDB1へ、個人のブックマークのページを表示する場合はDB2へ、というように振り分ける
• パーティショニング
  • パーティショニング：1つのDBを複数のサーバに分割する手法のこと
  • 局所性を考慮した分散を実現するためには、このパーティショニングがよく使われる
  • テーブル単位での分割や、データの途中での分割など
  • → DBが分割されることで、アプリケーション側で参照先の振り分け処理が必要になる（が、修正コストは小さい）

第4回：DBのスケールアウト戦略

• アプリケーションを書く人が分散されたシステムを前提に書くときに何に気をつける必要があるか
• 分散を考慮したMySQL運用のポイント
  • ① OSのキャッシュを活かす
  • ② インデックスを適切に設定する
  • ③ スケーリングを前提とした設計をする
• OSのキャッシュを活かす
  • 全データサイズに気を配る。データ量 < 物理メモリとなるようにする
  • スキーマ設計がデータサイズに与える影響を考慮する
• インデックス重要
  • アルゴリズム・データ構造において、探索のときには広くツリー（探索木）がよく使われる
  • MySQLのインデックスは、**B+木（ビープラスツリー）**というデータ構造が基本（B+木はB木（ビーツリー）から派生したデータ構造）
  • 探索ロジック：まず根から自分の探している値が格納されていることを確認する → 無ければ子を辿る（どの子を辿るべきかは一意に決まる） → 最終的に木の高さ分の回数しか子を辿らない（そのため、高速な検索ができる）
  • B木の場合、各ノードの大きさを任意に設定できる。ここで、Linuxの1ページのサイズにノードの大きさを合わせることで、ディスクのシーク回数を最小化し、探索速度を高速化できる
  • B+木は、各ノードの中では子へのポインタしか持っていなくて、ポインタ以外のデータとしての実際の値は一番最後の葉（リーフ）にしか持たせない構造になっている
  • → とりあえず、B+木はDBにデータを保存するのにB木よりもさらに最適化されたデータ構造である、という点は抑えておく
  • インデックスの効果例：4000万件のtagテーブルから検索
    • インデックス無し（=線形探索）→ O(n)なので、最大4000万回の探索
    • インデックスあり（=B木で二分探索）→ O(log n)なので、最大25.25回の探索
    • ※ 計算量だけでなく、ディスク構造も最適化されるため、ディスクシーク回数も改善される
  • MySQLにおいて、基本的にインデックスが使われるのはwhere、order by、group byの条件に指定されたカラム
  • MySQLにおいて、インデックスとして作用するのは「明示的に追加したindex」、「プライマリキー」、「UNIQUE制約」
  • MySQLにおいて、複数のカラムに同時にインデックスを効かせたい場合は複合インデックスを使わなければならない
  • インデックスが期待通りに動いているかの確認にはexplainコマンドを使う
• MySQLの分散　スケーリング前提のシステム設計
  • MySQLのレプリケーション機能：マスタに書き込まれた内容をスレーブがポーリングして自身に反映させ、マスタのレプリカとなる。これにより同じ内容のサーバを複数用意することができる
  • 更新クエリはマスタへ、参照クエリはスレーブへ流すようにアプリケーション側で制御する。スレーブに更新クエリを流すと不整合が発生してレプリケーションは停止する。
  • スレーブへの振り分けはアプリケーション側で細かく制御することも可能だが、ロードバランサを使うと簡単に分散できる
  • 参照系はスケールさせやすいが、マスタはどうやって分散（冗長化）させるか？
    • Webアプリケーションの特性として、多くは参照系のクエリになる。そのため、マスタがボトルネックになって困るということは少ない
    • 書き込みが激しいシステムの場合、テーブルを分割する方法がある
    • 書き込みが激しいシステムの場合、そもそもRDBMSを使わないという選択肢もある。KVSの方が用途に合う場面も
  • パーティショニングを前提にした設計
    • MySQLには基本的に異なるサーバにあるテーブルをJOINする機能が無い
    • → JOINクエリは対象となるテーブルが将来にわたってサーバにまたがる分割を行わないことが保証できそうな場合のみしか使わない
    • ※ MySQL5.1系から異なるサーバにあるテーブルをJOINすることは可能（FEDERATED句）
  • パーティショニングのトレードオフ
    • [good] 負荷が下がる
    • [good] 局所性が増してキャッシュ効率が高くなる
    • [bad] 運用が難しい（複雑になる）
    • [bad] 故障率が上がる
    • ※ パーティショニングは切り札

第5回：大規模データ処理[実践]入門

• 統計処理や検索処理といった、本質的に大量のデータにアクセスしたい（しなければならない）場合にどうするか
  • こういったケースでは、RDBMSには限界があることが多い
  • バッチ処理でRDBMSからデータを抽出し、そこから別途インデックスサーバを構築し、そのインデックスサーバにWebアプリケーションからアクセスさせる
  • → はてなではこれを「用途特化型インデクシング」と呼んでいる
• 特定の目的だけに使いたいとき、その目的だけに特化してチューニングしたデータ構造を使うことで、高速な処理を実現する
• Webアプリケーションの世界では理論と実践の両側から攻めていかなければならないことが多い
• 課題が本質的になるにつれ、小手先のテクニックでは通用しなくなってくる。そのときに必要だったのは、新しい技術やノウハウではなく、古典的だけれども本質的な理論だった

第7回：アルゴリズムの実用化

• 対象となるデータが大きくなればなるほど、アルゴリズムやデータ構造の選択が速度に響く
• 線形探索
  • データ中から必要なデータを先頭から順番に見て探す
  • n件に対してn回の探索が必要 → **O(n)**のアルゴリズム
• 二分探索
  • n件に対してlog n回の探索が必要 → **O(log n)**のアルゴリズム
• 最大の探索回数は計算回数の目安となる指標で、計算量と呼ばれる
• 比較すると・・・
  • n = 1000の場合：O(n)は最大1000回、O(log n)は10回
  • n = 100万の場合：O(n)は最大100万回、O(log n)は20回
  • n = 1000万の場合：O(n)は最大1000万回、O(log n)は24回
• なぜアルゴリズムに対する知識が必要なのか
  • 計算機の資源は有限である
  • エンジニアの「共通言語」として
  • アルゴリズムを知っておくことで、新しい問題に対処できる可能性が広がる
• アルゴリズムの評価には、前述のオーダー表記を使うのが一般的である
• オーダー表記は、対象とするアルゴリズムが入力のサイズnのとき、大雑把にこのぐらいの計算量がかかる、というのを示す
• O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) ...
• 大切なのは、オーダー表記そのものではなく、オーダー表記を使って比較されるアルゴリズムのうち、その差がどのくらいになるかといった感覚
• データ構造とアルゴリズムがセットで論じられるのは、アルゴリズムでよく使う操作に合わせてデータ構造を選ぶ必要があるから
• 計算量のオーダー表記では「定数項」を無視する。定数項とは、そのアルゴリズムの実装中、入力サイズには依存しないけど実行しなければならない処理の類
  • 例：関数呼び出し、一時変数の確保、if文など
• 簡単な実装では定数項はそのアルゴリズムの計算量にほとんど影響を与えないが、複雑な実装になると定数項が無視できなくなってくる
• ソートのアルゴリズムは理論的にはO(n log n)が下限で、平均計算量O(n log n)を達成するアルゴリズムは複数存在する。しかし、その中でも一般的にはクイックソートが最速と言われている。
  • なぜか：クイックソートはその特性上、CPUキャッシュを使いやすい利点があるため
  • → 定数項が速いという例
• オーダー表記は比較するのには便利だが、実装込みで考えた場合それだけが全てではない

第11回：大規模データ処理を支えるサーバ・インフラ入門

• エンタープライズとWebサービスは特徴が異なる
  • エンタープライズは信頼性が最重要
  • Webサービスはトラフィックが多く、成長度合いも大きい
• Webサービスのインフラで重視したい3つのポイント
  • ① 低コスト、高効率重要：100%の信頼性は目指さない、などのように割り切る
  • ② 設計重要：スケーラビリティや応答性が求められる
  • ③ 開発スピード重要：サービスに対して機動的にリソースを提供できるようにする

第12回：スケーラビリティの確保に必要な考え方

• APサーバは基本的にスケールが容易
  • なぜか：APサーバは状態を持たないため。リクエストごとに別のサーバに飛んでも問題が発生しない（ことがほとんど）
• DBやファイルサーバは、分散・スケーラビリティの確保が難しい
  • その中でも、writeの分散は難しい
  • readは比較的容易
• どのようにスケールさせていくかを検討するために、まずはサーバの負荷状態を把握する
• 負荷を見る際にはまずロードアベレージから見る
  • ロードアベレージ：プロセスがいつでも動ける状態なのに、実際にCPUが割り当てられていなくて待ち状態にあるプロセス数の平均値
  • CPUがきれいに割り当てられていると、ロードアベレージは0に近くなる
  • CPUコア数以下であれば良い

第13回：冗長性の確保、システムの安定化

• APサーバ
  • APサーバはスケーラビリティの考え方と同様に、台数を並べるのが基本
    • 1,2台停止しても十分処理できるような処理能力を確保する
  • サーバは様々な要因で止まる
    • 人為的ミス
    • 物理的故障
  • ロードバランサによる自動フェイルオーバ、フェイルバックでの対応
    • フェイルオーバ：壊れたサーバを自動で切り離す
    • フェイルバック：正常になったサーバを自動で復帰させる
• DBサーバ
  • DBサーバも台数を並べて1,2台停止しても十分処理できるようにする
  • マルチマスタという手法を使い、マスタの冗長化を行う
    • マルチマスタでは双方向でのレプリケーションを行う（お互いがお互いのスレーブであるという状態になる）
    • MySQLの実装では片側に伝わるまでに遅延がある → ミリ秒単位で見るとデータが一致していない状態が常にある
    • わずかではあるがデータが一致していないタイミングで異常が発生すると同期がズレる → ここは割り切って常に動かすことを優先させている
• ストレージサーバ
  • はてなでは、画像などのメディアファイルを保存するための分散ストレージとして、MogileFSを使っている
  • 分散ファイルシステムを使うことで、スケーラビリティと冗長性の確保が同時に実現できる
• システム安定化
  • システムを安定化させるためにはトレードオフがいくつかある
  • 安定性と資源効率のトレードオフ
  • 安定性と速度のトレードオフ
  • マシンリソースをギリギリまで使うような設定にしない。こういう設定は予期しないデータ量の増加やバグが発生した場合に障害となる。そのため、7割程度までしか使わない、といったような余裕を持った設計にする
• 実際の安定化対策
  • 大枠は以下の2つ
    • ① 適切なバッファの維持
    • ② 不安定要因の除去
  • バッファの維持
    • 限界の7割運用で実現
    • キャパシティの7割を超えたらサーバを追加したりメモリを増やしたりする
  • 不安定要因の除去
    • SQL負荷対策：重いSQLを発行しない。どうしても重くなるSQLは別ホストへ切り出す。など。
    • メモリリークを減らす：アプリケーションエンジニアの基本（常識）としてやってもらう
    • 異常動作時の自律制御：自動DoS判定、自動再起動、自動クエリ除去...

第14回：効率向上化作戦

• 冗長化を進めていくと、サーバが突然ダウンしても大丈夫なようになるが、リソースの使用率は低下する
• はてなでは、以下の方法で効率の向上を図っている
  • 仮想化技術：ホストの集積度を上げることで、サーバのリソース使用率を上げる
  • 自作サーバ：サーバの冗長な仕様を削ぎ落とし、システム全体の低コスト化を図る
• 仮想化技術の目的
  • スケーラビリティ
  • コストパフォーマンス
  • 高可用性
• 仮想化技術の効用
  • IPMIの代替としてのハイパーバイザ
  • ハード差分の吸収（環境の抽象化）
  • 準仮想化を使用
  • リソース消費の制御
• 仮想化サーバの構築ポリシー
  • 仮想化技術の最も基本的な目的はハードウェアの利用効率の向上
  • 空いているリソースに適したゲストOSを追加する（例：CPUリソースが空いていたらAPサーバ、I/Oリソースが空いていたらDBサーバ）
  • リソースの消費傾向が似ていて、かつ負荷の高いマシンの同居は避ける（リソースを食い合ってしまうため）
• 仮想化によって得られたメリット
  • 物理的なリソース制約からの解放
  • ソフトウェアレベルの強力なホスト制御
  • ハードウェア・運用コストの低下
  • コストパフォーマンスの向上
  • 高可用性
• 仮想化の注意点
  • パフォーマンス上のオーバヘッドがある
  • 仮想化技術の実装上の不具合による、不安要素の増加
• ムーアの法則：集積回路上のトランジスタ数は18ヶ月ごとに倍になる
• SSDのアクセス性能
  • はてブでは、DBのスレーブサーバで多く使用されている
  • 良好なランダムアクセス性能。メモリほどではないが十分高速
  • メモリ > SSD > HDD RAID-0 > HDD RAID-1