Dgraphによる高速並行キャッシュ - Ristretto
はじめに
RistrettoはグラフデータベースのDgraph内のキャッシュが遅いという問題から生まれたキャッシュライブラリです。
GolangWeekly(@golangweekly)で紹介されていたのを見つけて気になったので、動きを追ってみました。
Ristrettoは、以下の特徴を持っています。
- EventualConsistency(更新が遅延する)
- LFU(TinyLFU)を使用
- リングバッファ・ブルームフィルタによるmutexの削減
今回の記事では、Ristrettoの動きを通して、これらの特徴を解説します。
なお、この記事で使用したコミットは1982be43114b186bccc231adc44a72c474369470です。
また、DgraphでRistrettoを使用するプルリクエストはありますが、まだDgraphには入っていないようです。(#4025: Use ristretto in getNew)
参考資料:
全体像
Ristrettoを使って、Set→Getした場合の動きは下図のようになります
非同期
RistrettoはSetしてもすぐに参照できるわけではありません。なぜなら、
- goroutineを使うので、追加が非同期
- 追加するキーを評価しているので、追加に値しないと判断された場合は追加されない
からです。
Ristrettoは最初にインスタンスを作るときに、Cache#processItems()という関数をgoroutineで動かします。このprocessItemsがchannelを使ってキャッシュの更新をしています。そのため、Setは非同期になります。
また、キャッシュが満杯になっている場合には「重要なキーをキャッシュする」という信念のもと、既存のキーと新規に追加するキーの重要度を比較するので、新規のキーの重要度が低いと判断された場合にはキーは追加されません。(現在は、ランダムに選ばれた５個の既存のキーと重要度とを比較しています)
ちなみに、現時点では更新や削除の時にも同じchannelを使っているので非同期に更新されます。
そのため、下のように動きます。
cache.Set("key", "value", 1)
time.Sleep(time.Second / 100)
value, found := cache.Get("key")
// value は "value"
cache.Set("key", "value2", 1)
cache.Del("key")
value, found := cache.Get("key")
// まだ、value は "value"
time.Sleep(time.Second / 100)
value, found = cache.Get("key")
// value はnil (foundはfalse)
LFU(TinyLFU)を使用
RistrettoはLFUの改変版であるTinyLFUを採用しています。
まだこの論文を読んでいないのでどこまでがTinyLFUで、どこからがRistrettoの工夫なのかわからないのですが、実装では
- 参照時には、キーをリングバッファに追加するだけで、TinyLFU用の参照情報は非同期に更新する
- リングバッファが貯まると、貯めていたキーをchannelへ追加
- channelを通して、参照情報を更新する(ただし、ブルームフィルタを使用することで、対象のキーが初めて参照されたかを確認する。初めての場合には参照情報には追加せずブルームフィルタにのみ追加される)
おわりに
以上がRistrettoの動きでした。
これ以外にも解説記事には、GoがCSPを採用しているためにスレッドローカルなmapが作れなくて困った話やパフォーマンスなど面白いはなしが書いてあるので、もしRistrettoに興味が出たら一度読んでみてください。
秒間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の全体を説明しているので、読みやすいです。
