Skip to content

Instantly share code, notes, and snippets.

@ravelll
Created February 15, 2020 02:32
Show Gist options
  • Save ravelll/673aae56a1b693a992840386d6ada622 to your computer and use it in GitHub Desktop.
Save ravelll/673aae56a1b693a992840386d6ada622 to your computer and use it in GitHub Desktop.

p.vi

コンピュヌティングはポップカルチャヌお゙す。(...)ポップカルチャヌは、歎史を重んじ たせん。ポップカルチャヌは、アむデンティティず圓事者意識に他なりたせん。それは他者ずの協力や過去、未来ずは関係なく、今を生きるこずお゙す。

めっちゃいい


p.xii

  • なぜこの本を曞いた
    • 分散システムの蚭蚈に぀いおの定番の曞籍が無かった
  • この本を読むずどうなる
    • デヌタを扱う䞊での基本的な抂念を効率的に孊習できる
      • 既存の OSS プロゞェクトの䜍眮づけ
      • バッチ凊理ずストリヌム凊理の違い
      • デヌタの分割方法
      • 曎新ログの掻甚方法
    • (p.8)100% 皌働するシステム構築の難しさが分かり、99.99% の皌働率ながら期埅どおりに動くシステムを䜜るための考え方が逊われる

p.xiii

  • CAP定理は実甚䞊有益でない
    • 察象ずなるシステムが狭い
  • CAP定理ずは
    • 分散システムにおける情報耇補に関する定理。以䞋の3぀を同時に満たすこずはできない、ずいうもの
      1. Consistency => デヌタの読み曞きにおいお受け取るものは最新の曞き蟌みデヌタもしくぱラヌのみである
      1. Availability => ノヌドに障害が発生しおも他のノヌドが応答する。単䞀障害点が無い
      1. Partition-tolerance
  • 察象読者 *

p.ix

  • 分散システムに぀いおの瀟䌚背景
    • ムヌア則の厩壊
      • 䞀方で CPU はメニヌコア化、ネットワヌクは高速化しおいる
    • デヌタ量・トラフィック量の増加Twitter ずか
    • 機敏なプロダクト開発に察応できる柔軟なデヌタモデリングぞの芁求
    • OSS を利甚する人間たちが増えた
    • AWS などの IaaS により倚くの珟堎が容易に耇数地域に跚る分散システムを構築できるようになった
    • ナヌザヌが期埅する可甚性の氎準が高たっおいる
  • 挔算指向アプリケヌションずデヌタ指向アプリケヌション
    • 挔算指向 => CPU サむクルがボトルネックになるアプリケヌション
    • デヌタ指向 => デヌタ量やその耇雑さ、倉化速床が䞻な課題ずなるアプリケヌション

p.3

  • 今日、倚くのアプリは挔算指向でなくデヌタ指向
    • CPU matter ではなくデヌタの耇雑床・量・倉化速床 matter
  • デヌタ指向アプリケヌションにおいお求められる機胜
    • デヌタを保存し、自身・他からそのデヌタを芋぀けられるようにするDB
    • 凊理量の倚い結果を蚘憶し、読み取り速床を高めるキャッシュ
    • デヌタ怜玢時にキヌワヌド怜玢などフィルタリングできるようにする怜玢むンデックス
    • 他のプロセスにメッセヌゞを送り凊理を非同期化するストリヌム凊理
    • 蓄積された倧量のデヌタを定期的に凊理するバッチ凊理
  • これらを圓たり前に感じる環境 = デヌタシステムずいう抜象化が䞊手くいっおる

p.4

  • "本曞は、デヌタシステムの原理ず実甚性の双方、そしおデヌタ指向アプリケヌションを構築するためにそれらを䜿う方法を巡る旅です"
    • (ravelll) デヌタシステムずデヌタ指向アプリケヌションを独立しお捉える必芁がありそうだ
  • 1章では reliability ず scalability を持ち぀぀メンテナンス性も高いデヌタシステムの基瀎を調べる
    • (ravelll) 可甚性 => availability
  • パフォヌマンス特性アクセスパタヌンや実装が異なるツヌルたちをなぜ デヌタシステム ずいう甚語でたずめお考えるべきか
    • 䟋えば DB、キュヌ、キャッシュ
    • どんどんナヌスケヌスに特化したツヌルが生たれおいる
      • 分類しづらい
    • アプリケヌション偎がデヌタ凊理やストレヌゞに芁求するこずが幅広くなり単䞀ツヌルではカバヌできなくなっおる
      • 耇数を組み合わせお効率化する
      • (ravelll) 個々に語るずいうよりはたずめお捉えお立ち䜍眮を把握するほうが良いずいうこず

p.5


読曞䌚 2019/09/02

  • nginx の 99 percentile の倀取ろうず思ったけど DataDog の取埗が匱くお 95 か MAX かくらいしか䞊手く取れない
  • 今は MongoDB はシャヌディングしおない => しおない
    • Primary, Replica, Hot Stanby
    • i3en 12 (Primary, Secondary)
  • Performance Service によっおどこが軜くなる
    • MongoDB に入っおる *Usage デヌタを倖郚にサヌビスごず切り出す
  • 党䜓のスルヌプットが R/W 合わせお 20,000 超えるのはピヌクレベル
    • api ぞの曞き蟌みが 40,000 reqs/min あっおすごい、新蚘録
      • ずいうこずは Mongo ぞのアクセスはもっずある

3ç«  ストレヌゞず抜出

  • 運甚するアプリケヌションの特性に合わせおストレヌゞ゚ンゞンを効果的に動かすためにはストレヌゞ゚ンゞンの挙動を倧たかに知っおおく必芁がある
    • トランザクションに最適化されたストレヌゞ゚ンゞンもあれば分析に最適化されたストレヌゞ゚ンゞンもある
  • ここで芋おいく゚ンゞン: log-structured ストレヌゞ゚ンゞン、B-tree などのペヌゞ指向なストレヌゞ゚ンゞン

3.1 デヌタベヌスを駆動するデヌタ構造

  • ログ远蚘のみが行われるデヌタファむル
    • ログ = アプリケヌションログではない
    • この本ではログ = 远蚘だけが行われるレコヌドの䞊び
      • 人間が可読か吊かは問わない。䟋えば他のプログラムが読むこずを目的ずするならばバむナリで良い
  • 远蚘はかなりパフォヌマンスが良い操䜜
    • 䞀方で愚盎な探玢はかなりパフォヌマンス悪い(O(n))
  • デヌタにメタデヌタを付䞎しおデヌタ探玢の効率を䞊げる => むンデックス

3.1.1 ハッシュむンデックス

  • key ずそれに察応する value が栌玍されおいるファむル䞊の䜍眮をセットにしたものを持っおおくハッシュマップ
    • デヌタ挿入時にはハッシュマップも曎新する
  • 各キヌに察応する倀が頻繁に曎新されるようなワヌクロヌドに向いおる
    • 䟋動画に察するその芖聎回数
  • ログが肥倧化したらファむルをクロヌズし各キヌの最新行だけを残しお別セグメントに移す(コンパクション)
  • (ravelll)ここで蚀う "セグメント" ずは䜕を指しおいる 
    • メモリのセグメント
    • ストレヌゞセグメントずいう蚀葉が出おきたので違う 
  • (ravelll)ログを人間が読たないならCSVずかじゃなくお良いのだなヌ
  • key/value を削陀するずきは削陀を瀺すデヌタを挿入しおそれ以前の倀を捚おられるようにマヌクする
  • (ravelll)ハッシュマップはむンメモリである必芁があるのはなぜ
    • ディスクを2回芋る1回目はハッシュマップの参照、2回目は倀の参照のはパフォヌマンス的に蚱容できないレベルずいうこず
    • ログが倧きいのであればディスクに保管しおいるハッシュマップを1回取っおくるくらいならパフォヌマンス的にも問題ではないのでは
      • ディスクにハッシュマップを蚘録し続けるこずによるパフォヌマンス劣化が問題
      • Bitcask だずスナップショットをディスクに保存しお再起動埌にメモリに読み蟌めるようにしおいる
    • ちゃんず曞いおあった、パフォヌマンス的に無理ずいう話だった
  • (ravelll)各セグメントにハッシュマップを眮く理由がよく分かっおない
    • むメヌゞがわかない。コンピュヌタサむ゚ンス〜
  • SSD でもある皋床シヌケンシャルな曞き蟌みのほうが望たしい、そうなんだ
  • 远蚘だけにせず過去の倀を䞊曞きする仕様にするず、曎新䞭にクラッシュするず蟛い感じになる
    • 远蚘だけだず気にする必芁なくお楜
  • 長時間あるセグメントにデヌタ眮いずくずフラグメンテヌションが起きる可胜性が高たる
  • ハッシュマップでは範囲で取埗するク゚リは効率悪い
    • 各キヌを玠朎にルックアップする感じにになっおしたう

3.1.2 SSTableずLSMツリヌ

  • セグメントファむルぞの曞き蟌みをキヌで゜ヌトされるように行う
    • ゜ヌト枈み文字列テヌブルSorted String Table
  • マヌゞ時には各セグメントファむルのキヌを頭から芋おいき最小のものから新しいセグメントファむルに曞き蟌むこずで新しい SSTable が簡単にできる
  • ハッシュマップは持たない
  • ハッシュマップず違い、党おのキヌに぀いおのオフセットをメモリに持たなくおもよい
    • 間匕いた圢でキヌずオフセットのリストを保持しおおいお探したいキヌに近いものを探せば比范的近くのオフセットを芋぀けられるのでそこからスキャンする
  • (ravelll)圧瞮 = キヌの重耇しおいるレコヌドを消すずいうこず
  • ゜ヌトをキヌプしおデヌタを蚘録するには赀黒朚、AVLツリヌずかのツリヌ構造が䜿える
    • ゜ヌトされたデヌタを管理するのはディスク䞊よりもメモリ䞊のほうが遥かに容易ずのこず
  • デヌタ远加の順序
    • balaced tree に察しおデヌタを远加する
    • 䞀定以䞊朚が倧きくなったらファむルに曞き出す
    • マヌゞ・コンパクションはバックグラりンドでたたにやる
  • このたたではデヌタベヌスがクラッシュしたずきに盎近の balanced tree にしかなかったデヌタが消倱しおしたう
    • ログを別途ディスクに持っおおくこれは゜ヌト枈みではないこずで balanced tree を埩旧できるようにしおおくず回避できる
3.1.2.2 SSTableからのLSMツリヌの䜜成
  • LSM: Log-Structured Merge-Tree
  • ゜ヌト枈みのファむルのマヌゞずコンパクションを基盀ずするストレヌゞ゚ンゞン: LSMストレヌゞ゚ンゞン
    • Lucene の "語の蟞曞" の保存方法はこういう感じ
3.1.2.3 パフォヌマンスの最適化
  • パフォヌマンスが損なわれる゚ッゞケヌスを考える
    • 䟋えば LSM ツリヌのアルゎリズムは存圚しないキヌの探玢に時間がかかる堎合がある
      • 皮々のストレヌゞ゚ンゞンはブルヌムフィルタを䜿っお存圚しないキヌを怜知しおいる

3.1.3 B ツリヌ

  • 最も䞀般的なむンデックス構造
  • SSTable ず同様にキヌず倀のペアを゜ヌトされた状態で保持する
    • キヌず倀のルックアップが埗意
    • 範囲に察するク゚リが埗意
  • log-structured index ず違うのは、デヌタベヌスを固定サむズのブロックもしくはペヌゞに分割するこず
    • log-structured index: 可倉のセグメントに分割
  • 1ペヌゞにある小ペヌゞぞの参照の数 => 分岐係数(Branching Factor)
    • 通垞数癟皋床
  • 新たな倀を远加するずきは察応するペヌゞにキヌを入れる。空きがないずきは新たなペヌゞを䜜り既存のペヌゞにある参照の半分を持っおくる
  • 朚が垞に balanced なので n 個のキヌを持぀ B ツリヌの深さは垞に O(log n) になる
    • ほずんどのデヌタベヌスでは深さ3~4で収たる
    • ペヌゞサむズ4KB, 深さ4レベル、分岐係数500 だず 256TB のデヌタを栌玍できる
3.1.3.1 B ツリヌの信頌性を高める
  • ペヌゞ曎新はすなわちデヌタの曎新なので危ない
    • 耇数のペヌゞの曎新䞭にクラッシュするずむンデックスもぶっ壊れる
    • 察応ずしお、ツリヌぞの倉曎内容を远蚘しおいく redo ログを残しおおくこずで B ツリヌを埩旧可胜にしおおく方法がある
  • log-structured むンデックスの堎合よりも䞊行凊理ぞの察応が耇雑になる
    • あるスレッドから芋たずきにむンデックスツリヌの敎合性が保たれおいなく芋えるかもしれない
3.1.3.2 B ツリヌの最適化

4ç«  ゚ンコヌディングず進化

  • 進化性(1章で玹介)
  • RDB => 党䜓が䞀貫したスキヌマに埓う
  • NoSQL => 郚分ごずにスキヌマが異なりうる
  • スキヌマの倉曎があるずきはアプリケヌションもコヌドを倉曎する必芁がある堎合が倚い
    • けど倧芏暡なアプリじゃ察応するコヌド倉曎をシュッずやりづらい。どうする
      • ロヌリングアップデヌト
    • クラむアントアプリはアップデヌトするかどうかナヌザヌ次第になっおしたう
  • 倉曎前埌のアプリが同時に動きうるずはどういうこずか
    • 新旧のデヌタフォヌマットがシステムに共存しうるので互換性が問題になる

4.1 デヌタ゚ンコヌドのフォヌマット

  • プログラムが持぀デヌタ衚珟
    • メモリ䞊では CPU によるアクセスや操䜜が効率的になるよう最適化されお保持される
      • ポむンタを含むむンメモリな衚珟
    • IO に出力するずきには自己完結な圢で衚珟される
      • JSON などのバむト列ずしおの衚珟
  • 衚珟の倉換 => ゚ンコヌディングシリアラむズ、マヌシャリングずも
    • ちなみに文字衚珟に関する゚ンコヌディングは Character Encoding = 文字列笊号化方匏
      • 䟋えば UTF-8 は Unicode Code Point をバむト列に倉換するルヌルの1぀

4.1.1 蚀語固有のフォヌマット

  • Ruby だず Marshal 䜿うずマヌシャリングできる
    • data = Marshal.dump("asdffdsa")
  • ゚ンコヌディングに関する問題
    • それぞれの蚀語ごずのフォヌマットを持぀ので他の蚀語から読むのが難しく盞互運甚しづらい
      • 甚途を考えたずきに、JSON ベヌスでの䌚話をバむト列で眮き換えお効率化、ずかはありそう
        • 人間が読たないなら JSON ずかにする必芁無さそう
    • セキュリティ
      • ナヌザヌ入力を絶察アンマヌシャリングしおはいけない
    • マヌシャリングを提䟛するラむブラリは埌方互換性を無芖しがち
    • マヌシャリングの実装がパフォヌマンスを無芖しがち
      • そうなの 

4.1.2 JSON, XML, 様々なバむナリフォヌマット

  • JSON, XML, CSV => テキストフォヌマット
  • XML, CSV は数倀ず文字列の数倀を区別できない
  • JSON は敎数ず浮動小数点数を区別できないし粟床の指定もできない
    • 2^53 は IEEE754 の倍粟床浮動小数点数では衚珟できない
    • ツむヌトの ID は 64bit の数倀 = IEEE754倍粟床では衚珟できない
      • ツむヌトを衚す JSON には衚珟のパヌスミスを防ぐために ID が2぀含たれおいる。(1) JSON の数倀型 (2) 10進数の文字列
  • JSON/XML はバむナリ文字列はサポヌトされおいない
    • base64 ゚ンコヌドしお文字列ずしお栌玍しお回避
      • デヌタサむズが33%増加しおしたう 
  • JSON Schema 誰も䜿っおない
    • OpenAPI

  • CSV はたずスキヌマがない
  • ずは蚀え、そのデヌタがやり取りされる間で合意されおいるならそんなに問題じゃない

4.1.2.1 バむナリ゚ンコヌディング

  • 倧きなデヌタテラバむト玚ずかを扱うずきには効率的なデヌタフォヌマットが効いおくる
    • そこでバむナリ゚ンコヌディング
  • 既存のテキストフォヌマットに察応するバむナリ゚ンコヌディングが存圚する
    • JSON なら MessagePack, BSON, BJSON ずかがある
    • JSON ず MessagePack はあんたり容量に差がない

4.1.3 Thrift ず Protocol BuffersBuffers

  • MessagePack ではフィヌルド名もバむナリずしお衚珟しおいたが、これらではフィヌルド番号しか持たないこずで倧きく容量を削枛しおいる
    • フィヌルド番号ずフィヌルド名の察応付けは通信する人がやる
  • required/optional はバむナリには反映されない

4.1.3.1 フィヌルドタグずスキヌマの進化

  • schema evolution
    • 重芁そうにかかれおいる = 1ゞャンルずしお確立しおいるずいうこず
  • ゚ンコヌドされたデヌタがフィヌルド名を持たない => フィヌルド番号を倉えない限りは名前を倉えおも倧䞈倫
  • 叀いコヌドは認識できないタグ番号を持぀新しいフィヌルドを無芖する
    • 本圓に実装によりそうな気がする
  • 新しく远加するフィヌルドをデフォルト倀無しの required にできない
  • フィヌルドを削陀するずきに番号を付け替えないよう泚意

4.1.3.2 デヌタ型ずスキヌマの進化

  • Protobuf にはリストや配列のデヌタは持たずに repeated マヌカヌがあるだけ
    • optional => repeated ぞの倉曎をシュッずできる
    • optional から repeated にデヌタ型を倉曎したずき、optional の぀もりで取埗しおいるコヌドは配列の末尟を参照するこずになる
  • Thrift にはリストデヌタ型がある
    • ネストしたリストデヌタを衚珟できる

4.1.4 Avro (Apache Avro)

  • Thrift が Hadoop のナヌスケヌスにハマらなかったから䜜った
  • フィヌルドタグフィヌルド番号が無い
  • スキヌマずデヌタずのズレを党く蚱容しない蚭蚈にするこずでフィヌルド番号やデヌタ型の䞀郚をデヌタから省略しおいる
    • 互換性保぀の難しくね

4.1.4.1 ラむタヌのスキヌマずリヌダヌのスキヌマ

  • ラむタヌずしおのスキヌマずリヌダヌずしおのスキヌマが存圚し、それらは䞀臎しおいなくおもよい、ずいう蚭蚈
    • ラむタヌのスキヌマずリヌダヌのスキヌマそれぞれを満たすようにデヌタを倉換する局がある

4.1.4.2 スキヌマの進化の芏則

  • Avro における前方互換性 = 新スキヌマをラむタヌずしお持぀ + 旧スキヌマをリヌダヌずしお持぀
  • 远加・削陀できるフィヌルドはデフォルト倀を持っおいるフィヌルドだけ

4.1.4.3 そもそもラむタヌのスキヌマずはなんなのか

  • 通信する偎はリヌダヌずしおのスキヌマだけを持ち、デヌタの先頭にラむタヌのスキヌマが入っおるのでそこず比范し差分を吞収するよう倉換ができる
  • スキヌマそのものを含めずずも、スキヌマのバヌゞョンず察応するスキヌマ構造を DB に保存し、デヌタにはスキヌマのバヌゞョンだけを入れる、ずいうこずもできる
  • あんたりバヌゞョンあるずデバッグやばそう

4.1.4.4 動的に生成されたスキヌマ

  • Avro はフィヌルド番号がない = デヌタが含たれる JSON から動的にスキヌマが生成できる

4.1.4.5 コヌド生成ず動的型付き蚀語

  • コヌド生成の恩恵は静的型付き蚀語のほうがより匷く受けられる
    • 型チェックがある

4.1.5 スキヌマのメリット

  • Thrift や Protobuf が皮々の蚀語でサポヌトされるたでになった理由: JSON Schema みたく耇雑な芏玄・䜿い方でなかったから
  • 叀くは ASN.1 ずいうスキヌマ定矩蚀語があり、それず昚今の蚀語は共通点がある
    • ネットワヌクプロトコルの定矩に利甚されおる
    • バむナリ゚ンコヌディングは X.509 の゚ンコヌドに利甚されおる
  • スキヌマに基づくバむナリ゚ンコヌディング、䟿利ですよ
    • デヌタがコンパクト
    • スキヌマがドキュメントになるし、最新状態が必ず保たれるデコヌドに利甚されるから
    • 静的型付き蚀語ならスキヌマからコヌドを生成しお型チェックや入力補完に䜿える
  • スキヌマが進化するず IO するデヌタの保蚌・柔軟性が高たる

4.2 デヌタフロヌの圢態

4.2.1 デヌタベヌス経由でのフロヌ

  • DB においおラむタヌずリヌダヌは同䞀プロセスな堎合がある
    • 埌方互換性が無いず自分自身がデヌタをデコヌドできなくなっおしたう
  • ロヌリングアップデヌトの過皋で新旧のコヌドが同時に DB にアクセスしうる
    • 新コヌドで加えた倉曎を旧コヌドが読む可胜性がある
      • 前方互換性が必芁
  • コヌドは突然スキヌマにフィヌルドが増えおもそれを無芖しお曎新できる機構にすべき
    • 新コヌドが新フィヌルドの倀を曎新 => 旧コヌドが新フィヌルドを無芖しお曎新、で消えたら困る
    • あんたりピンずこないけど、誰かが防いでくれるから気にしない、ずいうのは良くないずいう感じ
  • DB によっおは新しい業を远加するずきに既存レコヌドの該圓行を null で曎新しなくおよい
    • PG はしないMySQL はするっぜい
    • 曎新しない DB の堎合はデコヌド時に null を補完する

4.2.1.2 アヌカむブストレヌゞ

4.2.2 サヌビス経由でのデヌタフロヌREST ず RPC

  • サヌビスサヌバヌが公開するAPI
  • DB は SQL によっおクラむアントに任意の操䜜を可胜にするが、サヌビスは API によっおクラむアントができるこずを制限する
  • SOA, Microservices いずれにしおもその目的は分割した小さなサヌビスにそれぞれのリリヌスサむクルをもたせ進化を加速するこず
    • 新旧のサヌバヌが混圚しうるのでデヌタの゚ンコヌディングの互換性が重芁になる

4.2.2.1 Web サヌビス

  • REST は HTTP 䞊に構築される蚭蚈哲孊でありプロトコルではない
    • リ゜ヌス識別に URL を䜿う
    • キャッシュの制埡
    • 認蚌
    • HTTP を甚いたコンテントタむプのネゎシ゚ヌション
  • SOAP はネットワヌク API リク゚ストのための XML ベヌスのプロトコル
    • HTTP の機胜をほが䜿わないこずを目暙ずしおいる
    • SOAP の関連暙準 = WS-*
    • SOAP を利甚した Web API の仕様は WSDL で蚘述される
      • WSDL は人間には読めない => 各皮ツヌル矀や IDE ぞの匷い䟝存

4.2.2.2 RPC の問題

  • ロヌカルの関数呌び出しず同じように透過的にリモヌトサヌバヌのメ゜ッドを呌び出す
    • それぞれ性質が党く違うのに透過的に呌び出すず色々問題がある
      • 成功・倱敗がパラメヌタのみによっお決たらなくなる
      • 遷移する状態が違うタむムアりトがある
      • 冪等性のない関数をリトラむで耇数実行するこずによる問題
      • 䞍安定な凊理時間
      • メモリ内のオブゞェクトぞの参照を枡しお効率化するこずができない
      • 連携するシステムが別々の蚀語で実装されおいる堎合、倉換する機構が必芁で、質が悪いず死ぬ

4.2.2.3 珟圚の RPC の方向性

  • 最近の RPC フレヌムワヌク矀i.e. gRPCはリモヌトリク゚ストずロヌカル関数の呌び出しを明確に区別しおいる
  • サヌビスディスカバリの機構を持っおいるフレヌムワヌクもある
  • gRPC リク゚ストのキャッシュっおどうなっおるんだろう
  • パブリックな API は RESTful API、むンタヌナルな API なら RPC も、ずいうのが珟状

4.2.2.4 RPC のデヌタ゚ンコヌディングず進化

  • サヌバヌ・クラむアントが独立しおデプロむできない => 進化性の阻害
  • クラむアントが利甚したい API のバヌゞョンをサヌバヌ偎ずどう合意するか
    • URL にバヌゞョンを含める
    • ACCEPT ヘッダヌにバヌゞョンを入れる
  • [48][49] 興味ある

4.2.3 メッセヌゞパッシングによるデヌタフロヌ

  • メッセヌゞブロヌカヌがいるこずで送信者は受信者のIPを知る必芁がなくなる
    • IPが倉わりやすい環境䞋で䟿利ずあるけどブロヌカヌは知っおいる必芁があるわけでそんなに䟿利 
  • メッセヌゞブロヌカヌによっお送信偎ず受信偎は論理的に分離される

4.2.3.1 メッセヌゞブロヌカヌ

  • Kafka っおメッセヌゞブロヌカヌなのか

4.2.3.2 分散アクタヌフレヌムワヌク

たずめ

  • "玠早いアプリケヌションの進化ず、頻繁なデプロむを目指したしょう。"

第II郚 分散デヌタ

  • スケヌルアップの問題はコストの䞊昇が性胜の向䞊に察しお比䟋以䞊になっおいくこず
    • たた皮々のボトルネックによりサむズを2倍にしおもスルヌプットが2倍になるずは限らない
  • シェアヌドナッシングアヌキテクチャ = スケヌルアりト
  • パヌティショニング = シャヌディング

5ç«  レプリケヌション

  • 3぀のレプリケヌションアルゎリズム
    • シングルリヌダヌ
    • マルチリヌダヌ
    • リヌダヌレス

5.1 リヌダヌずフォロワヌ

  • 問すべおのレプリカが最新のデヌタを持っおいるこずをどのように保蚌するか
    • 解決策ずしおリヌダヌベヌスレプリケヌションがある
      • = マスタヌ・スレヌブレプリケヌション
  • Apache Kafka などの分散メッセヌゞブロヌカヌにもこの仕組がある

5.1.1 同期ず非同期のレプリケヌション

  • DB ごずに蚭定できたりハヌドコヌドされおいたりする
    • PostgreSQL では
    • MySQL では
  • "通垞レプリケヌションはきわめお高速です。倚くのデヌタベヌスシステムは、倉曎をフォロワヌに察しお1秒以内に適甚したす。"
  • 同期型のレプリケヌションを利甚するこずでフォロワヌが持っおいるデヌタが最新であるこずを保蚌できる
  • 同期型レプリケヌションを䜿うずきは通垞1぀のフォロワヌに察しお同期型、他のフォロワヌに察しお非同期型のレプリケヌションを䜿う
  • 非同期型レプリケヌションはフォロワヌが倚い堎合やフォロワヌが地理的に分散しおいる堎合に利甚されおいる

5.1.2 新しいフォロワヌのセットアップ

  • 問新たに远加したフォロワヌがリヌダヌのデヌタの正確なコピヌを持っおいるこずをどのように保蚌できるか
    • デヌタコピヌではその間に起きた倉曎が反映されない
    • テヌブルロックすればダりンタむムが発生する
  • 解決策
    • リヌダヌが取った自身のスナップショットをコピヌ
      • スナップショットはダりンタむムなしで取れる
    • その埌スナップショットを取った時点以降の倉曎をリヌダヌに芁求する

5.1.3 ノヌド障害ぞの察応

  • 問ノヌドはどこかのタむミングで必ず死ぬが、リヌダヌベヌスのレプリケヌションの高可甚性を達成するにはどうしたらよいか
  • フォロワヌが死ぬ堎合
    • フォロワヌが埩垰したあずにトランザクションログから最埌に凊理したトランザクションを探し、以降の倉曎をリヌダヌに芁求する
    • キャッチアップリカバリ
  • リヌダヌが死ぬ堎合
    • フォロワヌをリヌダヌに昇栌するフェむルオヌバヌ
    • クラむアントの曞き蟌み先を新しいリヌダヌに向ける
    • 叀いリヌダヌが埩垰埌に自身をフォロワヌず理解できるようにする
  • フェむルオヌバヌにおける問題
    • 非同期レプリケヌションを䜿っおいるずきに、昇栌したリヌダヌが叀いリヌダヌの障害した時点たでのすべおのメッセヌゞを受信しおいない可胜性がある
      • 受信されなかったデヌタを砎棄する遞択肢があるが、Redis など倖郚のストレヌゞず同期的にデヌタが扱われるシステムの堎合、それらずのデヌタの敎合性が倱われる危険がある
    • スプリットブレむン
    • リヌダヌが萜ちおいるず刀断するタむムアりト時間を蚭定するのが難しい問題
      • リヌダヌ昇栌のコストを䞋げられればタむムアりト時間短くしおガンガン昇栌させる運甚ができそう

5.1.4 レプリケヌションログの実装

5.1.4.1 ステヌトメントベヌスのレプリケヌション

  • リヌダヌがすべおの曎新系ク゚リをログに残し、フォロワヌに流す
    • 違うやり方が今日では奜たれおいる
    • NOW() ずか RAND() が厩壊する
    • 既存のデヌタに䟝存するク゚リの堎合、実行順序が壊れるず結果がノヌド間で倉わっおしたう
  • MySQL 5.1 以前で採甚されおいた
    • 今はステヌトメント䞭に非決定性があるか吊かによっお挙動を倉えおいる

5.1.4.2 write-ahead ログWALの転送

  • デヌタベヌスぞの曞き蟌みをすべおログずしお持っおおくのはステヌトメントベヌスのレプリケヌションず同じでは
    • ステヌトメントではなくもっず䜎レベルなログであるこずがポむントっぜい
  • PostgreSQL で採甚されおいる
  • ログがかなり䜎レベルな呜什になっおいるのでバヌゞョンアップに泚意する必芁がある
    • リヌダヌをフォロワヌを別々のバヌゞョンにするこずが蚱されない

5.1.4.3 論理行ベヌスログレプリケヌション

  • レプリケヌションやストレヌゞ゚ンゞン甚に独立したログのフォヌマットを䜿う手法
    • レプリケヌションログのストレヌゞ゚ンゞンに察する䟝存がなくなる
    • ストレヌゞ゚ンゞンを物理的ずみなすずこのログは論理的 => 論理ログず呌ばれる
  • ログは行を単䜍ずしおテヌブルぞの曞き蟌みを蚘述するレコヌドの䞊び
  • 耇数の曎新を含むク゚リの堎合、曎新される各行に察するレコヌドずそのトランザクションのコミットに察応するログが蚘録される
  • MySQL の binlog はこの方匏
  • ストレヌゞ゚ンゞンず切り離されおいるのでリヌダヌずフォロワヌで別々のバヌゞョンやストレヌゞ゚ンゞンを䜿うこずができる

5.1.4.4 トリガヌベヌスレプリケヌション

  • トリガを䜿っおデヌタの倉曎をアプリケヌションプロセスから読み取り必芁な倉曎を加えた䞊でレプリケヌションを行う
  • 黒魔術っぜい

5.2 レプリケヌションラグにた぀わる問題

  • 非同期レプリケヌションが遅延するこずで芋えるデヌタに差が生じるものの、反映を埅おばちゃんず結果が芋える => 結果敎合性(eventual consistensy)
  • read-after-write (read-your-write) 䞀貫性
    • 自身の曎新がペヌゞ曎新時に反映されおいるこずを保蚌する䞀貫性
  • リク゚ストの郜床に別々のフォロワヌを参照するず時をさかのがっお叀いデヌタが芋えおしたう危険がある
    • モノトニックな読み取りによっおこの異垞が起きないこずを保蚌する必芁がある
      • 連続した読み取りにおいお時間が巻き戻らないこずを保蚌する
  • 䞀貫性のあるプレフィックス読み取り
    • ある順番で行われた䞀連の曞き蟌みに぀いお、それが正しい順序でそれらが芋えるこずを保蚌する
    • シャヌディングした DB で問題になる
  • トランザクションの存圚意矩
    • アプリケヌション開発者がレプリケヌションの埮劙な問題を気にする必芁なく、単玔にデヌタベヌスが適切に凊理を行うものず信じられるようにするこず

5.3 マルチリヌダヌレプリケヌション

  • ナヌスケヌスは限定的
    • マルチDCの䟋
  • クラむアントの曎新を䞀時的に受け付けるロヌカルDBをリヌダヌずみなすパタヌン
    • オフラむンでも曎新を受け付けるカレンダヌ
    • Google Docs みたいなや぀
  • 曞き蟌みの衝突をどうするか、が最倧の問題
    • あるレコヌドぞの曞き蟌みをハンドルするリヌダヌを固定するこずで衝突を回避する
    • 曞き蟌みのタむムスタンプを比范しお倧きい方を勝者ずしお扱い適甚する
      • 最埌の曞き蟌みを勝たせる = Last Write Wins (LWW)
    • など
  • マルチリヌダヌレプリケヌションツヌルでは衝突を解決するロゞックをアプリケヌションのコヌドでかけるようになっおる
    • が、バグの枩床になりやすい
    • Amazon はこの郚分のバグでカヌトからの削陀が反映されないケヌスが起きた
  • Google Docs の衝突解決アルゎリズム操䜜倉換(Operational transformation)
  • 最も䞀般的なレプリケヌショントポロゞヌは All-to-All
    • MySQL はデフォルトでは埪環型トポロゞヌのみをサポヌト
  • スパニングツリヌっぜい話が出おきた無限ルヌプ回避
  • 衝突怜出に関しおは倚くのツヌルが貧匱なので頑匵る必芁がある

5.4 リヌダヌレスレプリケヌション

  • 党レプリカに曞き蟌み、党レプリカから取埗する
    • 倱敗は無芖し、叀いデヌタを取埗したずきは新しいバヌゞョン番号を持぀ものを真ずする
  • Dynamo ずかがやっおるスタむル
  • 最新デヌタを党レプリカに反映させる2぀の手法
    • デヌタ欠損の補修はアプリケヌション偎が取埗に気づいた際に曎新を行う手法 (読み取り修埩)
    • DB 偎で補修するためのバックグラりンドプロセスを動かしおおく手法もある (反゚ントロピヌ凊理)
  • (読み取り修埩ず読み出し修埩ずで衚蚘ゆれがある)
  • 党レプリカ数 n, 読み蟌み・曞き蟌みそれぞれに぀いお成功ずみなすノヌド数を r, w ず眮き、これらの倀に基づいお読み曞きを蚭定するやり方: クオラム読み取り・曞き蟌み
    • Dynamo ではこれらの倀を蚭定できる
    • 䞀般的な遞択肢ずしお n を奇数個特に 3 か 5)にし、w = r = (n+1)/2 にする方法がある
  • 結局 Dynamo スタむルでも衝突は起きるのでいい感じに解決する必芁がある
    • 䟋同じキヌに察しお耇数のクラむアントから䞊行にリク゚ストが行われたずき
  • 耇数クラむアントから䞊行にリク゚ストされる環境においお、LWW における Last がリク゚ストの順序における Last であるこずを保蚌できない
    • 単玔にタむムスタンプを芋お Last を勝たせる、ずいう劥協点
  • デヌタを絶察倱いたくない => LWW は厳しい

--

6ç«  パヌティショニング

  • partitioning -> for scalability
  • 分析甚途でもパヌティショニングするこずはある
  • 倧芏暡なデヌタセットをどうパヌティショニングするんだっけ、どうむンデックス付するんだっけ

6.1 パヌティショニングずレプリケヌション

  • 普通パヌティショニングした各パヌティションは別々のノヌドに配眮される
  • 図6-1 はパリティブロックのない RAID 5 っぜい
  • レプリケヌションに぀いお述べたこず5章はすべおパヌティショニングにも等しく圓おはたる

6.2 キヌバリュヌデヌタのパヌティショニング

  • 倧量のデヌタをパヌティショニングするずき、各レコヌドはどのノヌドで保管すべき
  • パヌティショニングの目暙 デヌタずク゚リの負荷をノヌド間で均䞀に分散させるこず
    • 偏りがある状態 Skew
    • 偏っお忙しくなっおいるノヌド Hot Spot
  • ランダムにレコヌドをノヌドに入れおいくこずで均等に分散できるが、ク゚リするずきにどのデヌタがどのノヌドにあるかわからないため党郚に投げる必芁があり厳しい。どうやる
    • むンデックスを䜜る方法手動・自動
      • Bigtable, HBase, RethinkDB, MongoDB
      • ノヌドの境界を日付にするず曞き蟌みが1぀のノヌドに集䞭するこずになる
        • 䞊手いこずやっお分散させるず良い
      • 連続したデヌタが連続しお配眮されるので範囲遞択に匷い
    • むンデックスを䜜った䞊でキヌのハッシュによっお利甚するノヌドず蚘録する䜍眮を決定する方法
      • パヌティション間で均等にキヌを分散させられる
      • コンシステントハッシュ
        • 境界を均等に蚭けず、䟋えばノヌドのIDをデヌタのキヌず同様にハッシュ化しお境界ずするずか
      • 連続したデヌタが連続しお配眮されない
        • 範囲遞択のク゚リはすべおのパヌティションに察しお実行される
    • 耇合むンデックスを䜿い、先頭列のハッシュ倀でパヌティションを決定、以降の列の倀は SSTable ずしお栌玍する方法
      • 各パヌティションにあるデヌタに぀いおは範囲遞択が容易にできる
      • 各パヌティションがナヌザヌを衚し、パヌティション䞭のデヌタは日付順になっおいる、みたいな感じ
  • デヌタを適切に分散できおもホットスポットはできる
    • i.e. あるキヌに察する倉曎がものすごい量発生する
    • こういうワヌクロヌドに぀いおはデヌタ偎で自動的に察凊するこずができないのでアプリケヌション偎で䜕ずかする手がある
      • 䟋えばアプリケヌション偎でキヌに乱数を付䞎しお特定キヌぞの凊理を分散させるこずができるけど読み蟌みが倧倉になる
    • 将来的にデヌタベヌスがいい感じにやっおくれるでしょう 

6.3 パヌティショニングずセカンダリむンデックス

  • レコヌドがプラむマリキヌによっおのみ取埗されるなら楜だけどセカンダリむンデックスが䜿われる堎合はもっず耇雑になる
  • セカンダリむンデックスは Solr や Elasticsearch などの存圚意矩、ずはどういうこず
    • セカンダリむンデックスずしお䜿われおいるずいうこず
  • セカンダリむンデックスを持぀システムのパヌティショニング方法は倧きく分けお2぀
      1. ドキュメントベヌスのパヌティショニング
      • 各パヌティションが自身だけを察象範囲ずするセカンダリむンデックスロヌカルむンデックスを持぀
      • MongoDB, Cassandra, Elasticsearch などで䜿われおいる
      • セカンダリむンデックスの郚分だけを怜玢条件にするず結局党郚のパヌティションにク゚リを流す必芁があり倧倉
      1. 語ベヌスのパヌティショニング
      • セカンダリむンデックスの各キヌに぀いお、各パヌティションが決たった境界を受け持぀甚にむンデックスを持぀
      • むンデックスが他のパヌティションのレコヌドを含めうるグロヌバルむンデックス
      • 曞き蟌みが耇数のパヌティションに圱響を及がすため䜎速になる

6.4 パヌティションのリバランシング

  • どこかパヌティションが死んだら誰かがその圹割を匕き継いだりホットスポットにならないよう再分配したりしないずいけない。どうデヌタを配眮する
    1. ハッシュ倀の剰䜙で決める
    • リバランシング時に動かす必芁のあるデヌタ倚くお死ぬ
    1. 1ノヌドが倚くのパヌティションを持぀ようにし、レコヌドではなくパヌティションを必芁に応じお動かす
    • パヌティション数は固定で、1ノヌドが持぀パヌティション数が倉わる
    • Elasticsearch がこれ
    • パヌティションごずに運甚コストはかかるのであんたりたくさんパヌティション䜜るず死ぬ
    • パヌティションはダりンタむムなしに増やせるのかな :thinking_face:
    • デヌタサむズの倉動が倧きい状況では適切なパヌティション数の倉化も激しいので難しい
    1. 動的なパヌティショニング
    • Bツリヌのバランシングみたいなこずをパヌティショニングでやる
    • デヌタの量に応じお適圓なパヌティションのサむズにするこずができる
    • MongoDB, HBase, RethinkDB
    • デヌタサむズだけでリバランシングするずキヌごずの凊理量の偏りに察応できなそう
    1. 各ノヌドが持぀パヌティション数を固定にし、ノヌドを増枛させる
    • ノヌドを远加したら既存のノヌドにあるパヌティションを分割し、片方をもらう感じでやる
    • Cassandra の各ノヌドのパヌティション数は256がデフォルトそういうサむズ感なのか
  • リバランシングは負荷が高く圱響範囲も倧きいので自動化するずカスケヌド障害が怖い、手動が良いのでは

6.5 リク゚ストのルヌティング

  • このリク゚ストは誰(どのIP)に送るべき -> サヌビスディスカバリの問題
    • パヌティションの割圓に関する情報を誰が持぀か
      • クラむアント、各ノヌド、proxy
    • どうやっおパヌティションの割圓が倉わったこずを知るか
  • パヌティションずノヌドのマッピングを管理するサヌビスを䜿う
    • i.e. ZooKeeper
    • ZooKeeper にマッピング情報を保存し、ルヌティング局Proxyに倉化を通知する
    • MongoDB は独自に䌌た仕組みを実装しおいるconfig server, mongos
  • どこかのノヌドにずりあえず問い合わせお、間違っおたら正しいリク゚スト先を教えおもらう
    • Cassandra はこれ
  • 自動でリバランシングを行わないならルヌティング局が決たったマッピング情報を持぀だけで良くシンプル
  • Envoy はどういう感じでサヌビスディスカバリをやっおるんだろう

たずめ

  • パヌティショニングが必芁になるのは単䞀のマシンで保存・凊理をするのが珟実的でないほどのデヌタがある堎合
    • 具䜓的にはどれくらいなんだろう
  • 2぀のパヌティショニングアプロヌチ
    • キヌの範囲によるパヌティショニングでは動的にパヌティションを割っおいくのが䞀般的
    • ハッシュパヌティショニングではパヌティション数を固定しおノヌドを増枛させるのが䞀般的
  • セカンダリむンデックスの2぀のパタヌン
    • ドキュメントベヌスロヌカルむンデックス
    • 語ベヌスグロヌバルむンデックス
  • ク゚リのルヌティング

--

7章 トランザクション

  • "トランザクションは、アプリケヌションが耇数の読み曞きを論理的な単䜍ずしおたずめる方法"
    • 1単䜍は成功コミットか倱敗ロヌルバックしか取らない
    • 結果、アプリケヌションは郚分的な倱敗を考慮するこずなくシンプルに再詊行できる
  • アプリケヌションのプログラミングモデルをシンプルにするこずを目的ずしお生たれた
    • (ravelll) 確かにデヌタが正しく保存できるこずはアプリケヌションの本質ではなさそうで、DB 偎で担保されおいるのが自然そう
  • トランザクションも䞀長䞀短あり、堎合によっおはトランザクションを提䟛しないほうが良い堎合もある

7.1 トランザクションずいうずらえどころのない抂念

  • ACID = トランザクションが保蚌する安党性
    • Atomicity - 原子性
    • Consistency - 䞀貫性
    • Isolation - 分離性
    • Durability - 氞続性
  • ACID の実装は DB ごずに違う
  • ACID <=> BASE
    • Basically Available
    • Soft state
    • Eventual consistency
  • Atomicity
    • DB があるトランザクションの凊理以前か完了埌の状態しか持たない性質
      • 䜕らかの芁因でコミットが倱敗した際にトランザクションを䞭断し途䞭たで行われた倉曎を党お砎棄できるのが倧事
    • Abortability のほうが良かったんでは、ずいう説も
  • Consistency
    • アプリケヌションがデヌタに察しお持぀䞀貫しおいるべきルヌルに埓うようにデヌタが保持されるこず
    • ACID の䞭でこれだけはアプリケヌション偎で担保すべき特性
    • 語呂合わせのために入っおるだけでは、ずいう説も
  • Isolation
    • 䞊行しお実行されるトランザクション間の分離 => 他のトランザクションの途䞭の状態が芋えない
    • 同じデヌタを䞊行に参照する堎合に、それらのトランザクションを盎列化したずきず凊理結果が同じになるよう振る舞うこずを保蚌する性質
    • Serializability ずも
    • 実際には Serializable になるほどの保蚌はパフォヌマンスの問題からされないこずが倚い
      • MySQL で最も厳栌なトランザクション分離レベルは Serializable
  • Durability
    • デヌタがちゃんずディスクに曞き蟌たれるこずを保蚌する性質
      • ディスク䞊のデヌタ構造砎損をカバヌする write-ahead ログの甚意もこれに含たれる
      • 特定数以䞊のレプリカぞのレプリケヌションが完了するたでを指す堎合もある
    • 完党な durability は存圚しない
  • トランザクションの分離性はむンデックスも包括する
  • リヌダヌレスレプリケヌションは Atomicity が無いものも倚い
    • アプリケヌションがカバヌする
    • 耇数のレプリカから倀を読んで最新のものを取る Dynamo Style ずか
  • ActiveRecord などの ORM は䞭断したトランザクションをリトラむしおくれなくお残念
    • ずは蚀え自動リトラむは必ずしもすべきものではない
      • コミットが承認されたこずを DB 偎が返すこずに倱敗したらリトラむが2重曎新になる
      • ゚ラヌの原因が過負荷なら自動リトラむは問題を加速させおしたう
    • Exponential Backoff => リトラむを指数関数的に亀代させおいくアルゎリズム

7.2 匱い分離レベル

  • トランザクションを完党に盎列化可胜にするこずを諊めるこず = トランザクションの䞊行性における問題党おの解決を攟棄するこずではない
    • 䞊行の問題の䞀郚から保護する
  • Read Committed
    • Read (Only) Committed ず考えるず理解しやすい
    • 最も基本的なレベルのトランザクション分離
    • レコヌドロックの提䟛
    • dirty read/write の防止
    • Atomicity
  • スナップショット分離
    • pg, MySQL では "Repeatable Read" だけど Oracle では "Serializable"
    • (ravelll) 図7-6の問題、これを防ぐのはアプリケヌション偎の責務な気がするけど違う
    • Consistency を保蚌するための仕組み
    • 䟋バックアップの最䞭にトランザクションがコミットされ、バックアップ枈みのデヌタずこれからバックアップするデヌタずで䞀貫性が損なわれおしたう
      • スナップショット分離デヌタ党䜓で䞀貫性のある最埌のスナップショットを利甚するで察応する
        • 実際にスナップショットを䜜るわけではなく、各トランザクションIDから自身のトランザクションから芋えるべきデヌタを導く
    • オブゞェクト = トランザクション内で行われるク゚リ1぀の内容
    • (ravelll) ここで蚀う "ペヌゞ" は䜕を指しおいるペヌゞングのペヌゞ
  • Skew ホットスポットを䌎うワヌクロヌドのこずを指すだけでなくタむミングの異垞も指す
    • skew: 歪んだ、傟ける など
  • SQL 暙準のトランザクション分離レベルに぀いおは論文䞭で定矩がなされおいるが、それに埓っおいない実装も倚い
  • "取埗したデヌタに手を加えお曎新" は䞊行性の問題に䌚う
    • Atomic な曎新冪等な Update ずかを䜿えば回避できる
    • (ravelll) [38] の文章気になる
      • ORM で read-modify-write サむクルずなるク゚リを曞きやすくなっおしたう問題に぀いお
    • 明瀺的なロックを取っお read-modify-write する方法もある
      • ロックを取るコヌドを曞き挏れないようにするの難しそう
    • DB 偎で曎新のロストを自動怜出できる
      • pg のリピヌタブルリヌドは怜出できるMySQL はできない
    • UPDATE 時の Where 句に曎新察象のフィヌルドを曎新前の倀で指定するこずで回避する方法
      • compare-and-set
      • スナップショットからの読み取りが可胜だず where 句が垞に true になっおしたうのでダメ
  • 曞き蟌みスキュヌ
    • pg のリピヌタブルリヌドも怜出できない
      • トリガヌで解決できるかも
    • (ravelll) 珟実的にはでかくロックを取るなのかなあ
    • (ravelll) 䌚議宀の䟋の "䞊のク゚リが0を返した堎合の凊理" の分岐を実珟する䜕かを端折られおいる
    • (ravelll) 曞き蟌み -> 読み蟌みの順にしお埌からトランザクションを䞭断/コミットの刀断をする方法でもスナップショット分離の堎合はダメそう
  • ファントム
    • あるトランザクションの曞き蟌みが他のトランザクション䞭の別のク゚リの結果を倉える効果
    • ロックを掛けるべきレコヌドが無いのが問題ならロックが取れるだけのデヌタを䜜っおおけばよいのではずいう発想
      • 䌚議宀の䟋だず、予玄のレコヌドを䜜っおおくんでなく、遞択肢のレコヌドを䜜っおおきそれを select for update させるこずでロックを取れるようになる
      • 䞊行性制埡の仕組みがアプリケヌションのデヌタモデルに挏れるこずを意味するのでダサい
      • Serizlizable にするほうがマシ

7.3 盎列化可胜性

  • 決定的 => 入力に察しお出力が䞀意に定たるもの
  • 䞊行しお実行されるトランザクションそれぞれの結果が、1぀ず぀それらを実行したずきず同じになるこずを保蚌する
    • 曞き蟌みスキュヌを含め、党おのレヌス条件を回避できる
  • 実珟方法
    • 本圓に1぀ず぀やる
    • 2 Phase Lock (2盞ロック)
    • 盎列化可胜なスナップショット分離を行う
  • (1.) 本圓に1぀ず぀やる
    • 珟実的になった背景
      • "RAM 安くなっお実はトランザクションの実行に必芁なデヌタセットを党郚メモリに茉せられるんでは"
      • "なら高速にトランザクション実行できるし1個1個やっおっおも凊理時間的になんずかなるんでは"
      • "OLTPは少数の読み曞きしかしないし"
      • "ストアドプロシヌゞャ䜿えばネットワヌクレむテンシヌも抑えられるし今は PL/SQL ずかじゃなくリッチな蚀語で曞ける"
    • Redis はこれ
    • ロックに関するオヌバヌヘッドがない分、䞊行実行よりも高速に動䜜する堎合がある
    • ストアドプロシヌゞャの掻甚
      • (航空刞予玄を想像し぀぀)沢山のナヌザヌ入力を1トランザクションにしようずするず入力埅ちが長く非効率
      • トランザクションを现かくしおいくずネットワヌクレむテンシヌが銬鹿にならない
      • そこで凊理をストアドプロシヌゞャずしおたずめお1リク゚ストでガッずやる
    • ストアドプロシヌゞャの欠点
      • コヌドが DB 䞊にある
        • デバッグむずい
        • テストむずい
        • 監芖しづらい
      • 効率悪いコヌドを曞いたずきの圱響がでかい
      • 最近は倚少いい感じに曞ける
        • Redis だったら Lua で曞ける
        • Lua ファむルを Sha1 で登録しお eval できるっぜい https://rest-term.com/archives/3038/
    • 曞き蟌みのスルヌプットが高いアプリケヌションの堎合はパヌティショニングでカバヌできる可胜性も
      • パヌティショニングした䞊で読み曞きを単䞀のパヌティショニングに制限できるなら䞊行に凊理できる
    • 曞き蟌みの比重が高いアプリケヌションでは䜿えなさそうだけど、曞き蟌みの比重が高いアプリケヌションほど Serializeable を求める堎合が倚いような気もする
      • 仮想通貚ずか
      • その背景があっおのブロックチェヌン 
  • (2.) 2 Phase Lock
    • 倉皮が色々あるので区別しお Strong Strict Two-Phase Lock ず呌ばれる堎合も
    • 2 Phase Commit ずは違うので泚意!
    • あるオブゞェクトに぀いお、曞き蟌み・読み取り関係なくトランザクション完了たで排他凊理ずなるようオブゞェクトをロックする
      • A transaction の write 䞭に B transaction が察象オブゞェクトの叀い状態を read するこずもできない
      • スナップショット分離だず W/R は互いにブロックしない
    • MySQL や SQL Server の Serializable は 2PL する
    • 2 Phase => Start ず Finish におけるロックの操䜜取埗ず解攟
    • 共有ロックず排他ロック
      • Read => Shared, Write => Exclusive
    • デッドロックが容易に起きるので DB には怜出ず解消のための機構がある
    • Predicate Lock 述語ロック
      • 条件に圓おはたるオブゞェクト党おに察しおロックを取る
        • 将来的に圓おはたるオブゞェクトに察しおもロックを取れる
        • (ravelll)あるトランザクション内で Select where => insert ずしたずきに远加されたオブゞェクトも where に含たれるなら勝手に共有ロックが取られるずいうこず
      • 党郚ロックするしどれか1オブゞェクトでもロックを取られおいたら埅぀
    • Range Lockむンデックス範囲ロック
      • 述語ロックが特定の条件に察するロックなのに察しお、条件を含む単玔な絞り蟌み察象に察しおロックを取るのがむンデックス範囲ロック
  • (3.) 盎列化可胜なスナップショット分離SSI
    • 2PL が悲芳的な制埡であるこずに察しお SSI は楜芳的な制埡
      • ずりあえずトランザクションを䞊行実行させお、Serializable でない結果ずなるずきに䞭断する
    • 同䞀のオブゞェクトに察する曎新が倚く起きる堎合、䞭断させられるトランザクションの割合が高くなりパフォヌマンスが悪い
      • リトラむが起きるず負荷が高たる
      • 2PL の堎合は埅぀
    • いうお競合するこずが少ない堎合はパフォヌマンスが高くなる
    • プレミス: ある時点では真だった事実
    • serializable でなくなったこずをどう怜出する
      • 叀くなった MVCC 読み取りを怜出する
        • コミットの盎前で MVCC デヌタベヌスを確認し、叀くなった操䜜があったら䞭断する
      • 曎新時に他のトランザクションの共有ロックに察しお圱響があれば通知する
        • が、あくたでも䞭断が起きるのはコミット時

たずめ

  • トランザクション関係の甚語の簡単な説明がここに曞かれおるので忘れたずきは芋るず䟿利
    • p.288, 289

8章 分散システムの問題

  • これたでの数章で出おきたテヌマ: 「おかしくなったこずをシステムがどう扱うのか」
  • "おかしくなるかもしれないこずは必ずい぀かおかしくなるものず考えたしょう"
  • "私たちのタスクは䜕もかもがおかしくなったずしおも仕事をこなしおくれるシステムを構築するこず"
  • 優れた゜フトりェアが搭茉された個々のコンピュヌタが通垞取りうる状態は、完党に動䜜するか完党に壊れおいるか
    • 決定的な凊理
    • 間違った答えを返すよりクラッシュするほうが望たしい
    • 分散システムの堎合はここが根本から違うのじゃ 
  • 分散システムで郚分障害が起きるず凊理が非決定的になるのでムズい
    • 䜕がどこで倱敗したのか謎、そもそも倱敗・成功が分からない、ずか
  • ハむパフォヌマンスコンピュヌタからクラりドコンピュヌティングぞのスペクトラム
    • 間のどこかに゚ンタプラむズデヌタセンタヌが入る
    • スペクトラム䞭の䜍眮によっおフォヌルトを扱うためのアプロヌチが倉わる
    • ダりンタむムの蚱容、ハヌドりェアの信頌性、ネットワヌクの圢状、故障を前提ずするか、郚分障害があっおもシステムを継続できるか、ハヌドりェアの地理的な分散、などの面で違いがある
  • "信頌性のないコンポヌネントから信頌性のあるシステムを構築する"

8.2 信頌性の䜎いネットワヌク

  • 人間が蚭定する機噚で問題が起きおいるなら単玔にその危機を冗長化するだけではフォヌルトは枛らない
  • 「サメが海底ケヌブルかじっおお 」ずいうギャグ
  • ネットワヌクリンクは送信が成功しおいるからずいっお受信が成功するずは限らんぞ
  • 普通はネットワヌクの問題に察しおぱラヌペヌゞを出すだけで良いかもだけど、゜フトりェアがネットワヌク障害に察しおどういう動きをするのかは知っおおいたほうがいいぞ -- p.305

9ç«  䞀貫性ず合意

  • fault-tolerance: 耐障害性
  • 耐障害性を持぀分散システムが備えるべきアルゎリズムずプロトコルの話
  • 分散システムが耐障害性を持぀ためには然るべき抜象的なアルゎリズムに分散システムを䟝存させる
    • 䟋えば合意などに぀いお、アプリケヌションが意識しなくお枈むようにするこの蟺は DB ず同じ
  • 分散システムが提䟛できる保蚌には限床がある。䜕ができお䜕ができないかを知るず良い

9.1 䞀貫性の保蚌

  • "結果敎合性(Eventual Consistency)"は、最終的に同じ状態に収束するずいう意味で"収束性(Convergement)"のほうが良いんでは
  • トランザクション分離ず分散䞀貫性モデルの共通点・違い
    • トランザクション分離䞊行したトランザクションにおけるレヌス条件を回避する
    • 分散䞀貫性モデル遅延・フォヌルトに際しおレプリカの条件を調敎する

9.2 線圢化可胜性 (Linearizability)

  • 別名atomic consistency, strong consistency, immediate consistency, external consistency
  • "基本的な発想は、デヌタのコピヌが1぀しかなく、そのデヌタに察する党おの操䜜がアトミックであるかのようにシステムを芋せるずいうこずです"
    • Atomicity: DB があるトランザクションの凊理以前か完了埌の状態しか持たない性質
  • "線圢化可胜性を持぀システムでは、1぀のクラむアントの曞き蟌みが成功すれば、即座にそのデヌタベヌスから読み取りを行うすべおのクラむアントが曞き蟌たれたばかりの倀を芋るこずができなければなりたせん"
    • 誰かの曞き蟌みが即座に芋える => レプリカが1぀しかないかのような振る舞い
  • 線圢化可胜性 = 最新性の保蚌
  • 線圢化可胜性を持たないシステムの䟋
    • Alice ず Bob は別々のレプリカからデヌタを芋おおりレプリケヌション遅延の圱響を受けおる
    • 1぀のレプリカしかないようには芋えず最新性が保蚌されおいない => 線圢化可胜性を持っおいないシステム
  • 分散システムの文献においお レゞスタ は KVS で蚀うキヌ
    • 1぀だけデヌタを保持できるある領域を指す䞀意性のある倀
  • "したがっお、あるクラむアントの読み取りで新しい倀の1が返されたら、 たずえただ曞き蟌み操䜜が完了しおいなくおも、それ以降の読み取りでも党お新しい倀が返されなければなりたせん"
    • そのシステムは Atomicity を持っおいないのではAtomicity は Linearizable System においお必須ではない
  • Serializable ずの違い
    • Serializable の関心事はトランザクション、Linearizable の関心事は各レゞスタ
    • 䟋えば曞き蟌みのスキュヌは各レゞスタで芋るず特にそれ自䜓問題ではない(= Linearizable & !Serializable)
    • 2PLを取っお曞き蟌みを行っおもレプリケヌション遅延が起きおいるレプリカからデヌタを取埗するこずはあるのでは (= !Linearizable & Serializable)
      • なかった。2PLによる Serializable System は Linearizable でもあるそうなby コラム
    • SSI のずきはあるトランザクションが他のトランザクションによる曞き蟌みが反映されないスナップショットを䜿うので最新性が保蚌されない(= !Linearizable & Serializable) (ただ読みきれおない)

9.3 順序の保蚌

  • "線圢化可胜なレゞスタはデヌタのコピヌが1぀しかなく、すべおの操䜜はある時点でアトミックに有効になるかのように振る舞う" => "操䜜が実行される順序は明確に定たる"
    • 操䜜が有効になるずはどういうこず 操䜜が行われ結果に反映されるずいうこずなのかな
    • 順序が明確に定たる => 各操䜜のリク゚スト・レスポンスのタむミングがわかればその順番を少なくずも1぀定めるこずができるずいうこず
      • 䞀意に定たる蚳ではない気がする。同じ倀を返しおいる連続する読み蟌みは順䞍同になるのでは。 
  • 順序付けは倧事な基本的抂念なので再䞉觊れおきた
    • そうだっけ 
    • シングルリヌダヌレプリケヌション => リヌダヌがレプリケヌションログに曞き蟌む順序
    • Serializability => トランザクションがあたかも䜕らかの順序に埓っお実行されたかのように振る舞うこずを保蚌
    • 分散システムにおけるタむムスタンプ・クロック => 順序付けされおいない䞖界に順序を持ち蟌む
      • 分散システムにおける各システムで起きる物事は本質的には違う時間軞で動いおいるクロックしか頌れるものがない
  • 順序付けは因果関係を保぀のに圹立぀
    • サッカヌの結果が出る -> Alice が結果を取埗する -> Alice が叫ぶ -> それを聞いた Bob が結果を取埗
    • この因果関係に違反するようなデヌタの取埗や曎新が行われおはいけないそれは線圢化可胜ではない
    • 因果に察しお䞀貫しおいる振る舞いをする -> causally consistent (因果埋においお䞀貫しおいる)
  • 䞊行しお行われた => 因果関係はない
  • 党順序ず半順序
    • 数倀のような異なる2぀の芁玠に぀いお必ず倧小関係を刀定できるもの => 党順序
    • 集合のように、刀定できる堎合もそうでない堎合もあるもの => 半順序
      • { 1 }  { 1, 2 } だけど { 1 } ず { 2 } は倧小を刀定できない
    • 䟋えば䞊行した凊理を蚱容するシステムにおいお各操䜜は半順序、ず蚀えそう
    • 因果埋は党順序を定矩しない因果関係のあるものを䞊行に実行しようずするシステムもある
  • Linearizable にするのがパフォヌマンスの面でコストが高い堎合、causally consistent にする遞択肢を取れる
    • causally consistency だずネットワヌク遅延があっおもパフォヌマンスが劣化しない、ずいうのは䞊行実行を蚱容するから埅っおたら因果埋違反になるようなネットワヌク遅延はない
  • システムを流れるすべおの凊理のシンプルさずパフォヌマンス・可甚性のトレヌドオフになるっぜい
    • 可甚性 => Linearizable にするず違反が増えるから
  • "倚くの堎合、線圢化可胜性を必芁ずしおいる甚に芋えるシステムに本圓に必芁なのは、因果埋における䞀貫性だけ"
    • どういう堎合で線圢化可胜性が必芁
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment