Zanzibar は、Spanner データベース群の前に置かれたサーバー群である。本ページではまず構成要素を挙げ、次に 1 つの Check リクエストがそれらをどう通るかを追い、最後にデータがディスク上でどう配置されているかを見る。末尾の数値は、論文が 2018 年の本番環境について報告しているものである。
構成要素
どんな箱があり、その間をデータはどちら向きに流れるのか。論文は図 2 でこれに答えている。下の図はその配色 (クライアントは青、サーバーは黄、Spanner データベースは緑) を保ち、細部を省いたものである。
クライアントが 2 種類のサーバーとやり取りしている点に注目してほしい。aclservers は 4 種類のリクエストに答え、watchservers は変更をストリームするだけである。論文の言葉では、aclservers は “are organized in clusters and respond to Check, Read, Expand, and Write requests” (クラスタとして編成され、Check、Read、Expand、Write の各リクエストに応答する)。一方 watchservers は “tail the changelog and serve a stream of namespace changes to clients in near real time” (変更ログを追いかけ、名前空間の変更のストリームをほぼリアルタイムでクライアントに提供する) (§3)。Leopard は大きなグループや深く入れ子になったグループのためのインデックスであり、専用のページ がある。
オフラインパイプラインは “dumps of the relation tuples in each namespace at a known snapshot timestamp” (既知のスナップショットタイムスタンプにおける各名前空間のリレーションタプルのダンプ) を作り、“tuple versions older than a threshold configured per namespace” (名前空間ごとに設定されたしきい値より古いタプルバージョン) をガベージコレクションする (§3)。
1 つの Check を順に追う
追うリクエストは「Beto は readme の閲覧者か」である。共通の例では readme の閲覧者には group:eng のメンバーが含まれ、Beto はその一人なので、答えは yes である。Zanzibar はそれを、doc:readme と group:eng の 2 つのオブジェクトを読んで確かめなければならない。
任意のサーバーに届き、そこからファンアウトする
どのサーバーが作業をするのか。どのサーバーでもリクエストを受けられ、作業はそこからオブジェクトごとに分散される。
サーバー A はどちらのオブジェクトも担当している必要がなかった。論文はまさにこの形を説明している。“Requests arrive at any server in a cluster and that server fans out the work to other servers in the cluster as necessary. Those servers may in turn contact other servers to compute intermediate results. The initial server gathers the final result and returns it to the client.” (リクエストはクラスタ内の任意のサーバーに到着し、そのサーバーは必要に応じて作業をクラスタ内の他のサーバーにファンアウトする。それらのサーバーはさらに、中間結果を計算するために他のサーバーに問い合わせることがある。最初のサーバーが最終結果を集めてクライアントに返す。) (§3)
コンシステントハッシュが問い合わせ先を決める
A は readme について B に尋ねればよいとどうやって知ったのか。クラスタのサーバー群は 1 つの分散キャッシュを構成している。“Cache entries are distributed across Zanzibar servers with consistent hashing” (キャッシュエントリはコンシステントハッシュによって Zanzibar のサーバー群に分散される) (§3.2.5)。この方式は Karger ら (STOC ’97) によるもので、論文は [20] として引用している。ほとんどの名前空間では、転送キーはオブジェクト ID から計算される (§3.2.5)。
readme の viewer と owner が同じサーバーで出会う点に注目してほしい。それがオブジェクトをキーにする理由である。“processing a check on ⟨object#relation⟩ often involves indirect ACL checks on other relations of the same object and reading relation tuples of the object. These checks and reads can be processed by the same server since they share the same forwarding key with the parent check request.” (⟨object#relation⟩ に対するチェックの処理には、しばしば同じオブジェクトの他の関係に対する間接的な ACL チェックや、そのオブジェクトのリレーションタプルの読み取りが伴う。これらのチェックと読み取りは、親のチェックリクエストと同じ転送キーを共有するので、同じサーバーで処理できる。) (§3.2.5) Karger らは、キャッシュが追加・削除されたときに、負荷の均衡を保つのに必要な最小限の割合のオブジェクトだけが移動すればよいようにコンシステントハッシュを設計した。キャッシュに向いているのはそのためである。
ホットなキーについて、論文は Slicer を “to help distribute hot keys to multiple servers” (ホットなキーを複数のサーバーに分散させるのを助けるために) 使っていると付け加えている (§3.2.5)。
呼び出しの両端が答えをキャッシュする
多数のサーバーが一度に C へ group:eng について尋ねたらどうなるか。たとえば、検索結果ページが eng と共有されている数十のドキュメントをチェックする場合である。
呼び出し元のキャッシュと呼び出し先のキャッシュは積み重なって木になる。“To handle hot forwarding keys, we cache results at both the caller and the callee of internal RPCs, effectively forming cache trees.” (ホットな転送キーに対処するため、内部 RPC の呼び出し元と呼び出し先の両方で結果をキャッシュし、実質的にキャッシュの木を形成している。) (§3.2.5) キャッシュキーにはスナップショットタイムスタンプが含まれ、タイムスタンプは “rounded up to a coarse granularity, such as one or ten seconds” (1 秒や 10 秒といった粗い粒度に切り上げられる) ので、最近のリクエストの大半がエントリを共有できる (§3.2.5)。本番環境では、チェックのキャッシュは “a 10% hit rate on the delegate’s side” (委譲先側で 10% のヒット率) と、委譲元側で “a 2% hit rate” (2% のヒット率) だった。論文は、これらの率は低く見えるが “they prevent 500K internal RPCs per second from creating hot spots” (毎秒 50 万の内部 RPC がホットスポットを生むのを防いでいる) と述べている (§4.4)。
ロックテーブルが同一のリクエストをまとめる
キャッシュが役に立つのは、答えを保持してからである。最初のリクエストが終わる前に同一のリクエストが多数届けば、すべてがミスして Spanner に向かうことになる。これが キャッシュスタンピード である (論文の参考文献 [3])。C はそれをどう避けるのか。
論文によれば、“we maintain a lock table on each server to track outstanding reads and checks. Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (各サーバーに ロックテーブル を保持し、処理中の読み取りとチェックを追跡する。同じキャッシュキーを共有するリクエストのうち処理を始めるのは 1 つだけであり、残りはキャッシュが埋まるまでブロックされる。) (§3.2.5) チェックについては、ロックテーブルによって委譲先側で “an additional 12%” (さらに 12%)、委譲元側で “an additional 3%” (さらに 3%) が節約された (§4.4)。
2 つの改良が後から加えられた (§3.2.5)。非常に人気のあるオブジェクトについては、Zanzibar は ⟨object#relation⟩ の すべての タプルを一度に読んでキャッシュし、“trading read bandwidth for cacheability” (読み取り帯域と引き換えにキャッシュしやすさを得る)。また、キャンセルされたサブチェックはキャッシュキーを空のまま残すので、“eager cancellation when there are waiters on the corresponding lock table entry” (対応するロックテーブルのエントリに待機者がいる場合の積極的なキャンセル) を遅らせる。
Spanner への読み取りはプールされる
次に、1 つのオブジェクトの複数の関係に触れるチェックを考える。Chen は readme の閲覧者か。論文の図 1 の設定では、viewer は editor を含み、editor は owner を含み、parent フォルダの閲覧者はドキュメントの閲覧者である。したがってサーバー B は readme のタプルセットを 4 つ読む必要がある。
葉は並行に実行される。“we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (ブール式の木のすべての葉ノードを並行に評価する。あるノードの結果が部分木の結果を決めたときは、その部分木の他のノードの評価はキャンセルされる。) (§3.2.3) その読み取りはまとめられる。“We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner.” (同じ ACL チェックのための読み取りをまとめるプーリング機構を適用し、Spanner への読み取り RPC の数を最小限に抑えている。) (§3.2.3) その後 parent タプルが folder:A を指し、folder:A#viewer は folder:A を担当するサーバーに転送され、そこで Chen が見つかる。1 つのプールが何回の RPC になるかは論文に書かれておらず、「減る」というところまでしか言えない。
タプルの配置がこれを安価にしている。主キーの順序は “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (あるオブジェクト ID や (オブジェクト ID, 関係) ペアに対するすべてのリレーションタプルを引けるようにする) (§3.1.1、後述の ストレージ を参照)。
遅い Spanner 読み取りはヘッジされる
リクエストとは無関係な理由で遅くなる読み取りもある。Spanner と Leopard への呼び出しについて、Zanzibar はリクエストのヘッジを用いる。これは論文の参考文献 [16] である Dean と Barroso の「The Tail at Scale」(CACM、2013) による技法である。2 つ目のリクエストはいつ送られるのか。
ヘッジとは “we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests” (同じリクエストを複数のサーバーに送り、最初に返ってきた応答を使い、他のリクエストをキャンセルする) ことである (§3.2.7)。2 つ目のリクエストは待つ。“we first send one request and defer sending hedged requests until the initial request is known to be slow” (まず 1 つのリクエストを送り、最初のリクエストが遅いとわかるまでヘッジリクエストの送信を遅らせる)。遅延時間は “Nth percentile latency based on recent measurements” (最近の測定に基づく N パーセンタイルのレイテンシ) の推定器で決まる (§3.2.7)。本番環境では “1% of Spanner reads, or 200K reads per second, benefit from hedging” (Spanner 読み取りの 1%、すなわち毎秒 20 万の読み取りがヘッジの恩恵を受けている) (§4.4)。
クライアントごとに上限を設ける
共有サービスは、あるクライアントが他のクライアントを遅くするのを防がなければならない。§3.2.6 は 4 つの制限を挙げている。
- CPU: 各 RPC のコストは “generic cpu-seconds” (汎用の CPU 秒) で計られる。各クライアントにはグローバルな CPU 上限があり、“its RPCs will be throttled if it exceeds the limit and there is no spare capacity in the overall system.” (上限を超え、かつ システム全体に余剰容量がない場合、その RPC はスロットリングされる。)
- 処理中の RPC: 各サーバーは総数と、クライアントごとの数を制限する。
- Spanner: “the maximum number of concurrent reads per (object, client) and per client on each Spanner server.” (各 Spanner サーバー上での (オブジェクト, クライアント) ごと、およびクライアントごとの同時読み取りの最大数。)
- ロックテーブル: “different lock table keys for requests from different clients” (異なるクライアントからのリクエストには異なるロックテーブルキーを用いる)。これにより、Spanner があるクライアントをスロットリングしても、別のクライアントがブロックされない。
Watch の経路
書き込みはストリームにも流れる。Anne がタプルを書き込んだ後、その変更はどこへ行くのか。
“Every Zanzibar write is committed to both the tuple storage and the changelog shard in a single transaction.” (Zanzibar のすべての書き込みは、単一のトランザクションでタプルストレージと変更ログシャードの両方にコミットされる。) 変更ログシャードをホストする Spanner サーバーは、“to minimize blocking of changelog reads on pending transactions” (保留中のトランザクションによって変更ログの読み取りがブロックされるのを最小限に抑えるため) トランザクションコーディネータとして振る舞う (§3.1.2)。Leopard はこのストリームの消費者の一つである。そのインクリメンタルインデクサは “calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications” (Zanzibar の Watch API を呼び出して、時間順に並んだ Zanzibar のタプル変更のストリームを受け取る) (§3.2.4)。
ストレージ
どんなデータベースがあり、行はどんな形をしているのか。データベースは 3 種類ある (§3)。
タプルデータベース。 “We store relation tuples of each namespace in a separate database, where each row is identified by primary key (shard ID, object ID, relation, user, commit timestamp).” (各名前空間のリレーションタプルを別々のデータベースに格納し、各行は主キー (シャード ID, オブジェクト ID, 関係, ユーザー, コミットタイムスタンプ) で識別される。) (§3.1.1) コミットタイムスタンプがキーの一部なので、古いバージョンはそれぞれ別の行に残り、“so that we can evaluate checks and reads at any timestamp within the garbage collection window” (ガベージコレクションの期間内の任意のタイムスタンプでチェックと読み取りを評価できる)。共通の例のタプルは、doc と group のデータベースに次のように置かれることになる。
| データベース | シャード ID | オブジェクト ID | 関係 | ユーザー | コミットタイムスタンプ |
|---|---|---|---|---|---|
doc |
s(readme) | readme |
owner |
user:anne |
t₁ |
doc |
s(readme) | readme |
parent |
folder:A#... |
t₂ |
doc |
s(readme) | readme |
viewer |
group:eng#member |
t₃ |
group |
s(eng) | eng |
member |
user:beto |
t₄ |
1 つのオブジェクトの行はまとまって並ぶ。論文によれば、このキー順序は “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (あるオブジェクト ID や (オブジェクト ID, 関係) ペアに対するすべてのリレーションタプルを引けるようにする)。“Usually the shard ID is determined solely by the object ID” (通常、シャード ID はオブジェクト ID だけで決まる)。メンバーが非常に多いグループでは、“computed from both object ID and user” (オブジェクト ID とユーザーの両方から計算される) こともある (§3.1.1)。論文はシャード関数を示していないので、上の s(…) は仮置きであり、ユーザー列の正確なエンコーディングも説明されていない。
変更ログ。 すべての名前空間で 1 つのデータベースであり、(変更ログシャード ID, タイムスタンプ, 一意の更新 ID) をキーとする。“where a changelog shard is randomly selected for each write” (変更ログシャードは書き込みごとにランダムに選ばれる) (§3.1.2)。
名前空間設定。 2 つのテーブルを持つ 1 つのデータベースである。“keyed by namespace IDs” (名前空間 ID をキーとする) 設定と、“keyed by commit timestamps” (コミットタイムスタンプをキーとする) “a changelog of config updates” (設定更新の変更ログ) である。サーバーは起動時にすべての設定を読み込み、その後はその変更ログを追いかける (§3.1.3)。
レプリケーション。 “Replicas exist in dozens of locations around the world, with multiple replicas per region. The 5 voting replicas are in eastern and central United States, in 3 different metropolitan areas to isolate failures but within 25 milliseconds of each other so that Paxos transactions commit quickly.” (レプリカは世界中の数十の場所にあり、リージョンごとに複数のレプリカがある。5 つの投票レプリカは米国東部と中部にあり、障害を隔離するために 3 つの異なる都市圏に置かれているが、Paxos トランザクションが速くコミットするよう互いに 25 ミリ秒以内の距離にある。) (§3.1.4) Spanner 自体は論文の参考文献 [15] である Corbett ら (OSDI ’12) で説明されている。
運用上の数値
論文の §4 は次の数値を報告している。API ごとのピークとレイテンシは 2018 年 12 月の 7 日間のものである (§4、§4.2)。その他の数値について、論文は期間を明示していない。各セルは原文のまま引用する。
| 項目 | 論文の記述 | § |
|---|---|---|
| 本番運用期間 | “more than 5 years” (5 年以上) | 4 |
| 名前空間 | “more than 1,500 namespaces defined by hundreds of client applications” (数百のクライアントアプリケーションが定義した 1,500 以上の名前空間) | 4 |
| タプル | “more than 2 trillion relation tuples that occupy close to 100 terabytes” (100 テラバイト近くを占める 2 兆以上のリレーションタプル) | 4 |
| レプリケーション | “fully replicated in more than 30 locations around the world” (世界中の 30 以上の場所に完全に複製) | 4 |
| クライアント負荷 | “more than 10 million client queries per second (QPS)” (毎秒 1,000 万以上のクライアントクエリ (QPS)) | 4 |
| API ごとのピーク | “Check requests peak at roughly 4.2M QPS, Read at 8.2M, Expand at 760K, and Write at 25K” (ピークは Check が約 4.2M QPS、Read が 8.2M、Expand が 760K、Write が 25K) | 4 |
| サーバー | “more than 10,000 servers organized in several dozen clusters around the world” (世界中の数十のクラスタに編成された 10,000 台以上のサーバー) | 4 |
| クラスタあたりのサーバー | “from fewer than 100 to more than 1,000, with the median near 500” (100 台未満から 1,000 台超まで、中央値は 500 台前後) | 4 |
| Check Safe のレイテンシ | “At the 50th, 95th, 99th, and 99.9th percentiles it peaks at roughly 3, 11, 20, and 93 msec, respectively.” (50、95、99、99.9 パーセンタイルで、ピークはそれぞれ約 3、11、20、93 ミリ秒。) | 4.2 |
| 可用性 | “above 99.999% over the past 3 years of operation at Google” (Google での過去 3 年間の運用で 99.999% 超) | 4.3 |
| 内部 RPC | “22 million internal “delegated” RPCs per second, split about evenly between reads and checks” (毎秒 2,200 万の内部「委譲」RPC。読み取りとチェックがほぼ半々) | 4.4 |
| キャッシュ参照 | “approximately 200 million lookups per second at peak, 150 million from checks and 50 million from reads” (ピーク時に毎秒約 2 億回の参照。うちチェックが 1.5 億、読み取りが 5,000 万) | 4.4 |
| Spanner への読み取り | “only 20 million read RPCs per second to Spanner” (Spanner への読み取り RPC は毎秒わずか 2,000 万) | 4.4 |
| Spanner の読み取りレイテンシ | “0.5 msec at the median, and 2 msec at the 95th percentile” (中央値で 0.5 ミリ秒、95 パーセンタイルで 2 ミリ秒) | 4.4 |
| ヘッジされた読み取り | “1% of Spanner reads, or 200K reads per second, benefit from hedging” (Spanner 読み取りの 1%、すなわち毎秒 20 万の読み取りがヘッジの恩恵を受けている) | 4.4 |
最後の数行の比率に注目してほしい。毎秒 2 億回のキャッシュ参照に対して、Spanner への読み取り RPC は 2,000 万回である。ストレージに送られる読み取り 1 回につき、約 10 回のメモリ内参照が行われている。
出典
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3, §3.1, §3.2.3, §3.2.5–§3.2.7, §4: https://www.usenix.org/conference/atc19/presentation/pang
- Karger et al., “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, STOC ’97 (論文の参考文献 [20]): https://people.csail.mit.edu/karger/Papers/web.pdf
- Dean and Barroso, “The Tail at Scale”, Communications of the ACM 56(2), 2013 (論文の参考文献 [16]): https://research.google/pubs/the-tail-at-scale/
- “Cache stampede”, Wikipedia、論文が引用しているもの (参考文献 [3]): https://en.wikipedia.org/wiki/Cache_stampede
- Adya et al., “Slicer: Auto-sharding for datacenter applications”, OSDI ’16 (論文の参考文献 [12]): https://www.usenix.org/conference/osdi16/technical-sessions/presentation/adya
- Corbett et al., “Spanner: Google’s globally-distributed database”, OSDI ’12 (論文の参考文献 [15]): https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf