Foreverly

メモ帳

スケーラビリティの技術の基礎

サーバやアプリをクラウドに置くと安いし便利ってだけではなく、 クラウドで実現可能なことは全世界に展開するような WEBスケーラブルなシステムが作れることが可能になったこと。 技術的には大変だけど... 全世界に展開するようなWEBシステムに携わるかはわからないけど、 大規模分散システムの原理原則や考え方を知っておくのは何かの役に立つかもしれない。

複製管理における基礎技術について

べき等性

重複実行してもよい処理のこと

分散システムにおける一般的な問題

クライアントがあるリクエストに対し完了通知がこないときに、 リクエストを再送すると、すでに処理済みである場合がある

対応策1

重複実行してもよい(べき等・Idempotent)処理か確認し、 そうであれば何度でもリクエストに対し処理を起動する(固定ファイル新規作成処理など)

対応策2

ミドルウェアまたはアプリケーションがリクエストにIDを振って、 処理完了を記録することで処理済みの処理を2回起動しないようにする(課金処理など) 処理がまだなら課金処理をして、処理済みだったら終了通知を発行させる処理を入れれば、 同じリクエストを投げても、2重課金がおきない。

ACID

複数のデータストアに対するトランザクション(ひとかたまりの論理的な操作)の性質と 書き込みなどのトランザクション実施時において、ACID実現のために必要なこと(高コスト)

  • Atomicity(原子性):含まれる操作がすべて実行されるか、すべて実行されないかのいずれかの結果になる
    • 原子性のため、全ノードで全操作の実施可否を確認し、全ノードが実施可能である時の実施
  • Consistency(一貫性):アプリケーションが定める不変条件をみたす
    • 一貫性のための判断を実施可否確認時に行う
  • Isolation(孤立性):複数のトランザクションは互いに干渉しない(外部から、途中過程や部分的に実施された状態にアクセスできることはない)
    • 孤立性のため、実施時には影響がおよぶ領域への他の読み書きをブロックする
  • Durability(耐久性):一度実施することが確定すると、その変更は永続的に反映される。

2PCプロトコル

Two-Phase Commitment(2PC)Protocol

ACIDを達成するための有名なプロトコル

参加者はcommitまたはabortに投票

クォーラム(定足数)

読み書き操作に関する一貫性のみを考えると、 必ずしも全ノードを同一の状態に揃える必要はない

  • 最新値を読み出すことができる　
  • 最新値がシステム内に複数存在することはない

過半数と多数決 書き込みと読み込みの数を変えてコストを調整できる。

2QW(書き込み数) > n かつ QW(書き込み数)　+ QR(読み込み数) > n(全ノード数)

2PCとクォーラムはノードの増減は想定していないけど、 実際は増減する。障害やオートスケールなど

過半数の合意を取ることでノード増減してもクォーラムなどでも対応できる。

一貫性

データストアに格納された値が最新値(書き込みの発生順序が守られている)に関して データストア(を実現する複数ノード)で合意を取ることが前提(しかし高コスト) これがそうでない場合はどうだろうか。

複数を用いたデータストアに複数のノードからの書き込みと読み込みを行うと タイミングでは書き込みの発生順序・最新値がことなるように外から見えてしまう。

一貫性モデル

データを管理するデータストアと、アプリケーションプログラムの間の約束事

  • アプリケーションプログラムが守るべきルール
  • データストアが保証する性質

順序一貫性(Sequential Consistency)

どのような捜査の結果も、すべての読み書き操作があたかも直線的な順序で行われたとしたときの結果と同一となる 複数を用いたデータストアに複数のノードからの書き込みと読み込みを行うとタイミングでは書き込みの発生順序・最新値がことなるように外から見えてしまうことは許さない！！！！ 内部実装としては、複数間で「次に扱う書き込み」について常に合意しながら進めることになる

因果一貫性(Causal Consistency)

因果的に関連している可能性のある書き込みは、必ず同じ順序で観測される 順序一貫性で許されなかった複数を用いたデータストアに複数のノードからの書き込みと読み込みを行うとタイミングでは書き込みの発生順序・最新値がことなるように外から見えてしまうことは許される

許されないことは?

aを読んでbを書き込むという因果関係の例

P1:Write x:=a P2:Read x -> a その後、Write x:=b P3:Read x -> a その後、Read x->b P4:Read x -> b その後、Read x->a

P4の観測結果はaを読んでbを書いたという把握できる順序関係に反している！！！

ベクトルタイムスタンプ

イベントの発生順序を判別するために使う論理クロックの一手法 物理クロックは誤差があるかもしれず、物理時間での前後関係をすべて気にする必要もない 時間ではなくて、前後関係がわかるタイムスタンプのこと

概要

各ノードは、「自分や他のノードでいくつかのイベントが起きたか」に関する情報をもつ 自ノードでイベントが発生したらインクリメント 他ノードへのメッセージ送信時には、自身が持つ情報を添えて送り、受信側はその情報を使って自身が持つ情報を更新

A[5,2,8]<Y[5,5,10] # Yの方が後 C[7,5,8]?Y[5,5,10] # どっちが先か後か断言できない

因果一貫性を実現するには書き込みマルチキャストだけをカウントする

オーバヘッドが少ないので、負荷を気にせずできる。

弱一貫性(Weak Consistency)

アプリケーション側から一貫性を保たせるには、API側で最新値を取らせる(Lockなど)、順序一貫性よりかは軽い。

  • 順序一貫性を保証する「同期変数」への操作を提供して、アプリケーションプログラム側において、一貫性が必要な場合に制御可能にする
    • データストアへLockをとるイメージ
  • すべての先行の書き込みがすべての場所で完了するまで、同期変数への操作は許容されない
    • 読み込み前に同期操作を行えば、最新値を読み取れる
    • Lockをとってから読めば、最新値をとれる
  • すべての先行の同期変数へのオペレーションが完了するまで、データへの操作は許容されない
    • 書き込み後に同期操作を行えば、進行中・部分的な書き込み、書き込み結果の伝搬を完了できる

イベンチュアル一貫性/結果一貫性(Eventual COnsistency)

更新は全てのコピーに伝搬される(更新がなければすべての複製は同一に収束していく) 書き込み同士の衝突はなくて、読み込みが必ずしも最新でなくても構わないデータストアに適している(DNS,Webキャッシュ) クラウドでは、スケーラビリティを重視するために採用されている(書き込み同士の衝突もあるし、読み込みは最新がよいが、それでも採用したほうが良いと考える)

クラウドサービスにおける設計

AmazonSQS

Amazon Simple Queue Service (SQS) マイクロサービス、分散システム、およびサーバーレスアプリケーション用の完全マネージド型メッセージキュー。

  • メッセージの送受信のためのキュー機能を提供する。
    • キューは複製されている。キューが飛んでデータが吹っ飛ばないようにしている。
    • 全てのキューが同じデータを持つ状態に「収束」していく(イベンチュアル一貫性)
    • キューを読み出した時、その前におくられたメッセージが含まれるとは限らない(FIFOとは言っていない。)

キューもworkerも落ちる可能性がある。

  • 疎結合なアーキテクチャに寄与する
    • 提供者と利用者の待ち合わせなし
    • 空いたインスタンスが随時タスクを請負可能
  • 少なくとも一回実行のための仕様(2回以上しないという仕様は含まれていない)
    • 受信されたメッセージは、キューから取り除かれるけど、一定時間後に再びキューに含まれる
    • メッセージを受信してタスクを請け負ったプロセスが落ちる可能性を想定
    • タスクが完了したら、明示的にメッセージ削除をする
    • メッセージを重複して受信、処理がされる可能性がある。(処理中なのにメッセージが復活するケースなど)

AmazonSimpleDB/DynamoDB

イベンチュアル一貫性のあるデータストアで、Read/Writeするとなにがおきるか説明されてあるドキュメント。

ConsistencyのAWSのドキュメント

Amazon DynamoDB

  • 整合性があり、10 ミリ秒未満のレイテンシーを必要
  • すべての規模のアプリケーションに対応した、高速かつフレキシブルなNoSQLデータベースサービス
  • 完全マネージド型のクラウドデータベース
  • ドキュメントとキー値のストアモデルの両方をサポート
  • 支払いはスループットに発生する。1秒間に何回書き込みできるようにするか。

Amazon DynamoDB

料金概要

仮想的な測定指標に対してお金を払う。わかりづらい。

1 つの書き込みキャパシティーユニット (WCU) は、1 秒あたり最大 1 回の書き込みを提供 1 つの読み込みキャパシティーユニット (RCU) は、1 秒あたり最大 2 回の読み込みを提供

1 日に 500 万回の書き込みと500万回の結果的に整合性のある読み込みを実行する必要があるとします

結果的に整合性のある読み込み 常に最新というわけではない。誤差は出てくる。 1秒間に500万アクセスきても大丈夫だし、値段もわかる。 オートスケールさせると値段が見えにくくなってくる。

Amazon DynamoDB では、ユーザー定義プライマリキーを使用したGET/PUTオペレーションがサポート

  • BatchGetItems
    • BatchGetItems演算は、複数の項目の属性を複数のテーブルから、それぞれのプライマリキーを使用して返す。16件の応答のサイズ制限は1MBで、最大100個の項目を返す。強い整合性と結果整合性の両方をサポート
    • 16件の応答のサイズ制限は1MBで、最大100個の項目というクラウドとしては微小量の割合だけど、重い処理をしたときに他のユーザへ影響がでないようにしている。
  • BatchWriteItem
    • 1 回のトランザクションとしてではなく、1回のリクエストにより複数のテーブル間で複数の項目を挿入、置換、削除。PutまたはDeleteで最大 25 項目のバッチをサポートし、合計リクエストサイズは最大16MB。
  • UpdateItem
    • 既存の項目の属性を編集。条件付き演算子を使用して、項目の属性値が所定の条件に一致する場合にのみ更新を実行することも可能
    • カウンターのようなもの。GETして値をインクリメントしてPUTする。他の処理でインクリメントされていた場合、上書きするおそれがある。
    • この問題にはマルチスレッドではLockをとって対処する。
    • クラウドではLockは重いのでやらない、計算式を送り込む。計算式を送り込んで、サーバ側でロックをしてインクリメントすると負荷が低い。

Amazon DynamoDB では、スカラー値でアトミックなインクリメント演算とデクリメント演算を行うことができる。 アトミックとは今の値を読み込んで、+1して書き込むではなく、一度の処理でやる。 その他の書き込みなどは防がない。 タイムアウトなどしたら、書き込みはべき等ではない。 UpdateItemは正確な値を取りたいときには辞めたほうがいい。

Amazon DynamoDBはデータストアだけど、並行システム、マルチスレッドシステムの知識がないと使えない。 ユーザ側に並行システムを持つことに、これらの知識が求められている。

条件付きの書き込み

Aliceとボブがいる。今の価格が10とする。 Aliceが価格を8に更新する。Bobが後で価格を12に変更。するとAliceの価格が上書きされる。 値引きと値上げがタイミングによって起きている。 これを防ぐためにはユーザのプログラミングでUPDATEを投げる時には状況が変わっていることを前提にする。 もし価格が10なら8にする。もし価格が10なら12にする。というAPIを呼ぶ。 こういう可能性が知っていないと、気づけ無いし対応できない。 マルチスレッドプログラミングとおなじ。並行プログラミングもしっていないとだめ。 Lockすれば解決できるけど、ブロックしたくない、誰かのために他のひとを待たせたくないからこういう仕様。 悲観的、楽観的な発想。

DynamoDBにはScanもある。 1回のScanリクエストで、最大1MBのデータを取得 一度の処理で全データをみるのはやめてほしい。

ブロックさせない、他のシステムが遅くさせることはさせない。 プログラミングの不備があると、不整合によってユーザの手元のデータが消える。ユーザに試されている。

Key-Value Storeにおける思想

  • RDB
    • 依存関係の整理(正規化)に基づく設計,保存データ量の最小化
      • ex)「ID→氏名、会社名」「会社名→会社住所」
    • 実行時にSQLクエリに応じた複雑な処理が発生
      • 上の2テーブルを結合してIDから会社住所をひっぱってくる
    • 実行時にコストをとるような考え
  • KVS
    • あらかじめクエリパターンを考慮して、実行時には高速なget/putだけで済むような設計
      • ex)頻発するなら、「ID→会社名、会社住所」DBも、「会社住所→ID,氏名」DBもつくればいい
    • keyから引っ張ってくる、冗長的、書き込む時は書き直さないと正確に値を引っ張ってこれない、

内部版のDynamo

Amazonが使っていたDynamo

要求・仮定

  • 1MB未満くらいのデータの読み書き(keyへのget/put)ができればいい
    • 複数のデータにまたがる操作はない
    • Amazonの通販サイトの多くの部分がこれで動く
  • 可用性のために一貫性をゆるめる(ACIDのC)
    • 一つのkeyに対する読み書きだけ考えていて、一連操作性(I)のための保証は考えていない
  • 分布の99.9%以上に対し、読み書き数百msec未満
  • 一貫性や耐久性と性能などトレードオフは設定可能にしてある
  • 常に書き込み可能に
    • 2フェーズコミットや、イベンチュアル一貫性も使っていない
    • 古典的には、読み込みを軽くし、一貫性のための調整コスト(ブロックや失敗)は書き込みが追う
      • ex)書き込み全・読み込み1のQuorum
  • 一貫性のための競合解決方法は、アプリ開発者が決める柔軟性を残す
    • 「物理時間で最新のものを残す」などだけではなく
  • 少しずつノードを追加可能・対称性を重視(どのノードも同じ)・非中央集権・ノードは異種混合になっている

読み書きの実装

  • "Sloppy"(だらしない)Quorum
    • 読み書きリクエストを受け取ったノードは、N個の複製に送信し、読み書きそれぞれに定められた一定数(R,W)以上の確認をもって成功とする ※必ずR+W >N(全ノード数), 2W>Nにするとは言っていない
  • 書き込みの周知が想定ノードに届かなかった場合、別の代替ノードに送信 (可能であれば元のノードに書き戻す)
  • 耐久性への保証を犠牲にして性能を上げる設定
    • 基本的にはメモリ上のバッファを使って、そこへの書き込み完了を持って確認を返信する
    • バックグラウンドで随時二次記憶に書き込む(その前にクラッシュするとその複製では書き込みが失われる)
    • N個の書き込み周知先のうち、1つだけ二次記憶にすぐに書かせることで耐久性を少し向上

書き込み競合

  • 常に書き込み可能
    • 書き込みを受け付けた後で複製間の同期を行う
    • 並行する書き込みや一時的なネットワーク分断により、複数の「最新」値が存在しうる
  • ベクトルタイムスタンプを使ってバージョンを管理する
    • 把握できる因果順序がある場合、自動的に競合解決可能
  • そうでない場合は、次の書き込み手に意味を考慮した競合解決が委ねられる
  • アプリ依存の競合解決の例
    • ショッピングカート内の商品リストへ追加
    • セッションではなく二次記憶に保存している
  • 以上は論文から読み取れる内容
  • 同じ仕組みで「ショッピングカート内の商品リストから削除」を実現するとどうなるか
    • 削除はどうしているかは不明
    • 操作ログだけをもっているのかもしれない
  • 実際の発生率(複数の最新値が存在するときは)
    • 最新値が1つ:99.94%
    • 2つ:0.0005%
    • 3つ:0.00047%
    • 4つ:0.00009%
    • 最新値2つ以上は殆どbotのせいらしい

CAP定理

  • 複数を用いるアプリケーションは、下記のうち3つのうち2つのみを実現することができる
  • 定理よりかは原理原則
    • Consistency(一貫性):複数全体での結果一致を守ってのデータ更新やその耐久性(Durability)、一貫性の程度もある
    • Availability(可用性):(十分に早く)結果を返答する
    • Partition Tolerance(ネットワーク分断への耐性):システムの一部が分断・故障しても機能する

CAP定理とクラウド

  • First Tier:リクエスト処理を行うWEBページ
    • すぐに応答を返さないといけない。一貫性を妥協して古い情報をみせるとか。APが重要でCを妥協する。
    • ユーザ体験を大事にする気持ち。
  • Second Tier:スケーラブルなKey-Valueデータ

  • Inner Tiers/Backend:データベースやインデックスバッチ分析処理など

  • フロントエンド側において、CよりAPを優先する例

    • バックエンド側と繋がらなくなっても、ユーザにはキャッシュやエラー時用の情報などを見せる
    • 予約状況DBとは別に、残室情報DBをもって、「残り◯室」といった宣伝表示に使うとしても、この残室情報DBは正確な最新値とは限らない
      • ユーザには最新ではない可能性と表示する
      • フロントエンドでキャッシュをもっててもいいかもしれない
    • 人気の限定商品の開始時に、在庫数がある程度減るまでは、システム全体で正確な在庫数を共有することはせず、各複製サーバがどんどん売ってしまう
      • ほんとはACIDやらないといけないけど、ある程度まではだいだいあるってことでガンガン売る
      • Amazonのあれとか

CAP定理の位置づけ

  • バックエンド側ではCが必要
  • Cのための技術は確立されている(RDBとか)のに、Cを実現すると、APが犠牲になるのか
    • 今のRDBははやいので、十分APを実現している論
    • いやいや、想定しているスケーラビリティが違うし、コストが違うと反論
  • CAP定理とは高いスケーラビリティを実現するために一貫性を弱める事を受け入れることが低コストな解であることが多いということ

BASEトランザクション

ACIDすてたもの ACIDに対するBASE

  • Basic Availability;基本的に常に利用可能,部分的にでもリクエストが返ってる(すべての機能ではないかもしれないが)
  • Soft-State Replication:耐久性のあるメモリ上のデータストア(キャッシュ)を活用、2次記憶に書き込むのが正義ではない
  • Eventual Consistency:イベンチュアル一貫性(書き込み操作完了時には、その最新値がシステム内で合意されたとは限らない)

「D.Pritchett(EBay),Base An Acid Alternative,2008」

※少しの不整合やACID違反を「正常動作」と定義することを真剣に検討すべき [Vogles(AmazonCTO)] 何らかの不整合がでることも0ではない

今までの話はクラウドでしかできないスケーラビリティがある。 サーバやアプリをクラウドに置くと安いってだけの話ではない。 技術的には大変だけど全世界に展開するようなWEBスケーラブルなシステムが作れることが可能になった。