秒間100万リクエストをさばく - Googleの共通認可基盤 Zanzibar
はじめに
Googleの提供するサービス郡が共通して利用している認可システムにはZanzibarという名前がついています。ZanzibarはGoogleDrive・Google Map・Youtubeなどの巨大なサービスにも使用されています。
そのため、利用量も凄まじく
もの量をさばいています。
にも関わらず、Zanzibarはこれを10ミリ秒以内に返します(95パーセンタイル)。
この記事では、そんなZanzibarの内部構造に関する論文「Zanzibar: Google’s Consistent, Global Authorization System」の中から、主に大量のリクエストをさばくための工夫を紹介します。
ちなみに、以前Googleの社内システム用の認可システム「Beyond Corp」について書きましたが、Beyond CorpがGoogleの社員の利用を想定して強固なセキュリティに重きを置いているのに対して、Zanzibarは世界中の人が使用しても耐えられるような柔軟性と速度を重点に設計されています。
Zanzibarとは
多くのサービスがそうであるように、Googleのサービスでも認可は必須です。GoogleはZanzibarという認可システムを自作しています。
そのZanzibarは、以下を目標にしています。
- Correctness: ユーザーが意図したとおりのアクセス制御を実現する
- Flexibility: toC, toBのサービス両方の要望を満たせる柔軟なアクセス制御
- Low latency: 頻繁に利用されるので、素早く返したい
- High availability: 認可が止まるとサービス提供ができなくなるので、止まるのは厳禁
- Large scale: ユーザーは世界中に居るので、ユーザーの近くにシステムを置くために世界中に配置したい
アーキテクチャ
前章のZanzibarの目標を達成したアーキテクチャについて概説します。
Zanzibarには３つの種類のデータを保持するストレージがあります。(上図の緑の円柱部分)
- Relation Tuple Storage
オブジェクト(アクセス制限対象。GoogleDriveにあるファイルなど)とユーザーの関係を保持するストレージ。
バージョン管理も持っているので、少し昔のデータにもアクセスできます。
シャーディングされていて、シャーディングキーはクライアントが決めています。 - Changelog
権限情報の変更をストリーミングするための履歴をもつストレージ。
権限管理のためにはリアルタイムで情報を更新する必要もあるので、その部分を担当している。ちなみに、Relation Tuple StorageとChangelogは同一のトランザクションで更新しています。 - Namespace Config Storage
Namespace Configという、アプリケーションが事前に定義する権限設定を保持するストレージ。
開始時からの変更履歴を保持しています。
Zanzibarはこの３つのストレージが管理しているデータを使って、検索しています。
ちなみに、内部通信はRPCです。
Access Control List
Zanzibarは、RPCを通して権限を管理できます。
オブジェクトとユーザーの関係の宣言の仕方は、
- オブジェクトとユーザーの関係を直接書く
- グループを定義して、そのグループとオブジェクトの関係を書く
の２通りが出来ます。例えば、
doc:readme#owner@10 group:eng#member@11 doc:readme#viewer@group:eng#member
という書き方で、「readmeというファイルをid10のユーザーが所有している」、「11はengグループのメンバー」、「readmeはengグループのメンバーは閲覧可能」という関係をZanzibarに伝えることが出来ます。
高速化のために
ZanzibarはGoogleが提供するあらゆるサービスの認可基盤になることを想定しているので、速度と安定性はとても重要です。高速化のためにZanzibarが行っている工夫を紹介します。
Leopard Indexing System
ZanzibarにはLeopard Indexing Systemという、オブジェクトやグループの関係を高速に検索するためのインデックスが存在します。
Zanzibarは前章のACLを使って「グループに所属している人」も「グループ(親)に所属するグループ(子)」という関係も定義できます。すると、あるグループに多くの子グループが存在したり、グループのネストが深くなったりした場合に検索が大変です。
それを解消するために、Leopardはグループの関係をフラットにして
- Group2Group: あるグループの子孫のグループ
- Member2Group: あるユーザーが直接所属しているグループ (所属グループの親グループは含まない)
の２種類のグループの集合を保持しています。
更に、スキップリストのような順序付きリスト(ordered list)でグループを管理しているので、集合A・Bの和や交叉を O(min(|A|, |B|)) で計算できます。
すると、例えば
Member2Group(U) ∩ Group2Group(G)
の関係が空集合かどうかをLeopardで調べることで、「ユーザーUがグループGに所属しているか」を上記の計算量で答えられます。
Leopardのおかげで、Zanzibarが高速に権限チェックができるということです。
ホットスポット対策
Zanzibarで参照されるデータには偏りがあります。
Zanzibarはデータを非正規化をせずに(Leopardは例外)、代わりにキャッシュを使って対処しています。
例えば、権限チェックや参照のリクエストの結果は中間結果も含めてキャッシュされ分散されています。
また、cache stampede対策として、各サーバーは「lock table」を使って、同じリクエストが同時に複数実行されそうな場合に、リクエストを１つしか実行しないよう調整しています。
他にも、よく参照されるオブジェクトの結果を事前に読み込んでおくという工夫もあります。
パフォーマンスの分離
重いリクエストの影響でシステム全体が遅くなることも避ける必要があります。
Zanzibarでは、あるリクエストが他のリクエストに影響を与えないように、
- 各RPCが使用しているCPUを監視し、システム全体として余裕がない場合には閾値を超えたRPCに調整が入る
- クライアントとサーバーそれぞれに、RPCの同時送信・受信数の制限がある
- Spannerのために、クライアントとクライアントが参照するオブジェクト毎のアクセス制限がある
- クライアント毎に別のキーをlock tableに使って、Spannerのthrottlingの影響を他のクライアントが受けないようにする
という工夫をしています。
Reqeust hedging
その他にも障害に備えて、SpannerとLeopardを使う時には同一リクエストを２つのサーバーに送信して障害や遅延に備えています。そして、どちらかのリクエストが返ってきたらもう一方をキャンセルするのです(request hedging)。ただし、同時に２つリクエストを出すのではなく、最初に１つリクエストを出して「遅い」と判断された時にもう一つのリクエストが追加で出されます
おわりに
このように、Zanzibarは大量のリクエストをさばくために多くの工夫をしています。
また、この記事ではパフォーマンスの工夫に焦点を当てましたが論文では実測やZanzibarのACL構造や提供するAPIなど別のことも多く書いているので、Zanzibarに興味が湧いたらぜひ読んでみてください。
Aurora - クラウド時代のDBアーキテクチャ
はじめに
Amazon Auroraは、AWSを触る人ならほとんどの人が利用を検討したことがあるでしょう。
Amazon社内ではOracleを止めたというtweetもありました
SHUTDOWN ABORT the last Oracle database running Amazon Fulfillment! pic.twitter.com/DorqTua2Lt
— John Darrow (@jdarrow) 2019年3月29日
そんなAuroraは、従来のRDBとは違いクラウド上で動くことを念頭に設計されています。
また、ログが中心的な役割を持つことから「The log is the database」と表現されることもあります。
そんなAuroraの仕組みについての論文を読んだので紹介します。
読んだ論文は以下の２つです。
- Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
- Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes
The log is the database
従来のDB(MySQL, PostgreSQL, Oracle, SQLServer etc)は１台のマシン上で動作することを基本に設計されています。その上で、バックアップや性能向上などより複雑なニーズに対応するために複数台構成をサポートしています。
しかし、Auroraが前提としているのはクラウドです。
つまり、コンピュータが世界中に分散され、莫大な数のマシンが共同する世界です。
クラウドの世界ではレジリエンスとスケーラビリティを向上させるために、計算とストレージを分離しストレージを複数ノードで管理することが重要だとされています。
そこで、Auroraでもストレージは複数のAZを利用して６つの場所に保存されています。大まかには下図の構成をもっています。
しかし、複数のAZを使用するとネットワークがボトルネックになります。また、関わるノードが増えるということは故障率も上がるということです。
そのため、Auroraでは以下を念頭に設計されています。
- 複数台へのデータ保存
- 通信量削減
- 高速なバックアップ・リカバリ
- 簡易なノード変更
これらを実現するために採用された「ログ中心のアーキテクチャ」を端的に表した言葉が、
The log is the database
です。
以下の章ではこれらについて、紹介します。
複数台へのデータ保存
Auroraはクラウドの世界に合わせ、6ノードに同じデータを保存するようになっています。
Auroraでは10GB単位で6ノードにデータを保存しています。
6箇所のデータをまとめた単位がPG(Protection Group)と呼ばれます。
このPGに保存されていることが、「DBに保存された」ということを表すので、PG内での合意やPG内のノード入れ替えなど、PGに関する動作がAuroraの耐久性に影響します。
ちなみに、10GB単位なのは各ノードの修復時間(MTTR)を短縮するためです。
さて、PGの合意にはquorumを使っています。
通常のquorumでは3ノードを使用して、2/3の票があればよいとしていますが、Auroraでは6ノードを使用しています。
具体的には、readが3/6, writeが4/6の票を必要とします。
これは、6ノードを3つのAZに配置して、AZ+1ノードの障害を許容するためにあります。
AZ+1ノードの障害を許容するとは「一つのAZ全体が障害になり、さらにもう１台の障害が起きた場合でも動く」ことを指します。これは、火災や洪水、屋根の崩落などでAZ全体が障害になる可能性があるため、同一AZに所属しているノードの障害は独立していないと考えたことから来ています。
下図のように障害耐性があがるということです。
さらに、各ノードが持つデータについて詳しく見ると、全ノードが同じデータを持っているわけではありません。
６ノードは全てがredoログという、Auroraの変更履歴を持っていますが、３ノードしかAuroraの現在のデータをマテリアライズしていません。
これは、redoログだけがあればデータをマテリアライズすることが可能であることと、保有するデータ量を削減する目的で行われています。
通信量削減
Auroraの前提がクラウド環境であり、ネットワークがボトルネックだという話を最初に書きましたが、それに対するAuroraの対策を紹介します。
Auroraを象徴する「The log is the database」について、です。
従来のDBではレプリケーションのために多くのデータが共有されます。例えば、redo log、binary log,FRMなどです。
対して、Auroraではredo log(以下、redoログ)のみを各ノードが共有します。
AuroraはDB上のデータを変更するためにログを共有しているのではなく、DBにあった出来事を記録するためにログを共有しています。
つまり、クライアントからSQLでデータ変更を指示された場合、各ノードはredoログを受け取り、そのログを基にデータを再生します。
下図がデータの流れを表しています。
これは、ノードが新規に追加された場合や再起動された時にも同じです。足りないログを受け取り、再生する。
これによって、従来のDBにあるcheckpointやクラッシュリカバリに対する特殊処理が不要になります。
checkpointのように、定期的な「ディスク書き込み」は無くなり、redoログの書き込みで十分なのです。
また、障害が発生した場合にはAuroraが合意できる地点までのログを再生すれば良いのです。
この「ログを再生する」という処理はデータ変更時に常に行っている作業なので、障害発生時でも通常通りの動作を行っているということを意味します。
さて、各redoログにはLSN(Log Sequence Number)という番号が振られています。Auroraの各ストレージがどこまで変更に追いついているかを把握するためにも使われ、また、quorumで使用する4/6のwrite制限もLSNを利用しています。
つまり、Auroraは書き込み時に4/6の合意がある事をもって「書き込み」としています。
また、quorumのreadは通常使われません。各ノードのLSNの進み具合も把握しているため、通常のデータ読み込み時にはquorumでの合意は必要とせず、直接ノードに対してLSN時点でのデータを返させています。
quorumのreadの合意はクラッシュの復旧時などに使われます。
高速なバックアップ・リカバリ
redoログへの一本化によりバックアップ、リカバリも高速化されます。
Auroraにとってのバックアップとは、redoログを保存することです。また、リストアはredoログを再生することです。
各ノードは10GB単位でデータを持つので、各ノードにとっては自身に関わるログを手にすればリストアできるということです。
これは、障害時にも新規追加されるときにも同様で、自身が持っていないログをPG内の別ノードから貰えばよいということです。
同期の操作は10秒で終わります。
つまり、Auroraのquorumを破壊するためには、10秒以内に3台のノードを同時に破壊する必要が有ります。
この耐障害性によって、ソフトウェア更新などのためにノードを外すことが簡単に出来ます。LSNの進行が遅い(ノードが遅い)と検知されるたときも、簡単に交換できます。
簡易なノード変更
前章で簡単にノードを外せることに触れました。その時の動作について深堀します。
通常、quorumのノードを変更する場合、障害や遅延に対する影響が大きくなるので辛い作業です。
しかし、Auroraでは最大38,400(64TB使用時)のノードが存在するので障害の頻度が高くメンバー変更は簡単に出来る必要があります。
そのために、Auroraでは２段階の遷移を行います。
１度目は故障したノードと新規ノードを入れ替えたquorumを追加します。そして、新規ノードのデータが追いついたところで、故障したノードを含むquorumを削除します。
これによって、故障したノードが復帰することを考慮して、新規ノードの追加を遅延させる必要がなくなります。
下図のような遷移をします。
ちなみに、故障したノードが現在データをマテリアライズしている唯一のノードだった場合、新規ノードは他のマテリアライズしているノードからデータをコピーした後に、redoログを再生することで最新までのデータをマテリアライズすることができます。
終わりに
以上、Auoraについてでした。
記事としては長くなりましたが、論文はさらにAuroraの詳細を語っています。
例えば、redoログに関する動作(readやwrite、共有方法、パフォーマンスなど)こそが、両論文のメインテーマですがこの記事では大幅に削っています。
もし、Auroraへの興味がさらに湧いたなら、ぜひ両論文を読んでみてください。特にAmazon Aurora: Design Considerations for High Throughput Cloud-Native Relational DatabasesはAuroraの全体を説明しているので、読みやすいです。
Uber製Docker registy「Kraken」とTorrent
Krakenとは
Uberから、Krakenという拡張性と可用性に焦点を当てたP2P型のDocker registryが公開されました。
3Gのdocker imageを2,600ホストから同時にダウンロードしても、半数以上のホストが10秒で完了し、99％のホストで18秒以内にダウンロードを完了するという性能を持つ、強力なDocker registryです。
ただ、このレポジトリに注目した理由は性能や機能ではなく、torrentというディレクトリがあったからです。
正直、BitTorrentがまだ使われていることすら知らなかったので、「Krakenが言っているtorrentって何を指すんだろう」という興味から覗きました。
※本記事では3bca40a660c0da0a381b84865af3ad3c623283f3のコミットを使用しています。
また、Ubuntuで動作させていますが、サンプルコードがMacのみを想定していたため、スクリプトや設定を少しいじりました。
参考リンク:
Krakenのフロー
Krakenは以下のようなフローで動作します。
つまり、 docker pushをした場合には、
- Proxyサーバーにpush
- Originサーバーを通してimageを保存
という順番でアップロードしたdocker imageがKraken上に保存されます。
また、docker pull には
という２通りの選択肢がありますが、P2P無しは動作確認目的で、実際の稼働時にはP2Pを使用します。
P2Pダウンロード
さて、以下の画像のようにDocker imageのダウンロード元は既にダウンロードしている別ホストです。
Trackerを通して、要求データがあるホスト(Agent)を見つけ、そこからダウンロードします。
なので、Agentがダウンロードする先は別のAgentです。P2Pですね。
この、「ダウンロード」を司るコードの中にTorrentという言葉が出てきます。
これは、Krakenの開発当初にBitTorrentのdriverを使用していたところから来ているようです。
ただBitTorrentの実装は要求に合わなかったようで、独自にP2Pを実装し直しています。
しかし、Krakenの作成者たちはBitTorrentが大好きなのか、KrakenにBitTorrentとの互換性をもたせたいという夢をROADMAPに掲げています。(ストレージのエンドポイントはただのHTTPなので、Docker registry以外の用途にも使えます)
Scheduler
Scheduler機能がKrakenにも実装されています。
Schedulerは1つのgoプロセス内で動くキューのことで、色々なイベントを順番に実行するために使われます。
例えばKrakenでは、
- 別ホストとのコネクションを確立する
- imageをダウンロードする
- コネクションを切る
などの動作をSchedulerに入れて、順次実行しています。
また、多くの動作はその場で処理を終えるのではなく、ゴルーチンを使って後続処理をしています。
このようにすることで、順次実行しつつ平行に処理できるようになっています。
終わりに
以上Krakenについてでした。
