2017-01-01
『Web開発者のための大規模サービス技術入門』がめっちゃ良かった
目次
『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キャッシュを使いやすい利点があるため
- → 定数項が速いという例
- オーダー表記は比較するのには便利だが、実装込みで考えた場合それだけが全てではない