ACL チェックは「このユーザーはいま、これを行ってよいか」に答える。世界中に複製されたシステムでは、難しいのは「いま」の部分である。サーバーごとに、見てきた書き込みが異なるからである。このページでは、Zanzibar がどの順序を尊重すると約束しているか、Spanner がその約束を低コストで守れるようにしている仕組み、そして zookie によってクライアントがチェックに必要な最低限の新しさを指定できる仕組みを説明する。
「new enemy」問題
論文は §2.2 を 1 つの規則で始める。“ACL checks must respect the order in which users modify ACLs and object contents to avoid unexpected sharing behaviors.” (予期しない共有の挙動を避けるため、ACL チェックはユーザーが ACL やオブジェクトの内容を変更した順序を尊重しなければならない。) 論文はこの失敗を「new enemy」問題と呼ぶ。ACL から削除されたばかりのユーザーが、その削除によって隠すはずだった内容をまだ見られてしまう、という問題である。
論文は 2 つの例を挙げている。§2.2 と並べて読めるように、このページではこの 2 つの例に限って論文自身の名前 Alice、Bob、Charlie を使う。それ以外の箇所では、共通の例である Anne、Beto、Chen を使う。
チェックが 2 つ目の変更を見て 1 つ目を見なかった場合、何が問題になるのか。左のコマは順序付けのないシステムであり、右のコマは Zanzibar における同じ流れである。
A2 を含み A1 を含まないスナップショットは存在しないことに注意されたい。保証はこれに尽きる。§2.2 の説明によれば、チェックが T < T_A2 で実行されれば “the document ACLs will not include the folder ACL” (ドキュメントの ACL にはフォルダの ACL が含まれない)、T ≥ T_A2 > T_A1 で実行されれば “will observe update A1, which removed Bob from the folder ACL” (Bob をフォルダの ACL から削除した更新 A1 を観測する)。
例 B が異なるのは 1 点だけである。2 つ目の変更はドキュメントの 内容 に対するものであり、内容は Zanzibar ではなくクライアントアプリケーションのストレージにある。Zanzibar はその書き込みを一切見ない。それでは、新しい内容についてのチェックが十分に新しくなければならないことを、Zanzibar はどうやって知るのか。
破線の矢印が解決策である。zookie は内容とともに移動するので、B2 についてのチェックは B2 より古いスナップショットでは実行できず、そのようなスナップショットはすべて B1 をすでに含んでいる。このページの残りでは、これが依拠する 2 つの特性と、zookie を受け渡すプロトコルを説明する。
因果的に意味のあるタイムスタンプ
§2.2 は 2 つの特性を挙げている。外部一貫性 と 有界な古さを伴うスナップショット読み取り である。論文は外部一貫性について Gifford の 1981 年の博士論文 を引用している。Spanner の論文はトランザクションについて同じ特性を “if a transaction T1 commits before another transaction T2 starts, then T1’s commit timestamp is smaller than T2’s” (トランザクション T1 が別のトランザクション T2 の開始前にコミットするなら、T1 のコミットタイムスタンプは T2 のものより小さい) と述べ、これが “equivalently, linearizability” (同値な言い方をすれば線形化可能性) であるとして Herlihy と Wing (1990) を引用している。
Zanzibar の言葉では (§2.2)、因果的に関連する 2 つの更新 x ≺ y には T_x < T_y となるタイムスタンプが割り当てられる。タイムスタンプ T におけるスナップショット読み取りは “observes all updates with timestamps ≤ T” (タイムスタンプが ≤ T であるすべての更新を観測する)。合わせると、読み取りが y を見るなら、y より前に起きたことすべても見ることになる。これが成り立つのはストアがマルチバージョンだからである。Spanner はスナップショット読み取りを “a read in the past that executes without locking” (ロックなしで実行される過去の時点の読み取り) と定義しており (Spanner §4.1)、マルチバージョンのストアでは “each write on a data item produces a new copy (or version)” (データ項目への各書き込みが新しいコピー (すなわちバージョン) を生成する) (Bernstein と Goodman, 1983)。
この規則のもとで読み手には何が見え、結果整合性のレプリカの読み手には何が見えうるのか。この変形例では、readme は最初 folder:A の外にある。Anne はまず Chen を folder:A の閲覧者から削除し (x、T=10 でコミット)、次に doc:readme を folder:A に移動する (y、T=20)。
2 つのスナップショット読み取りは、見える 量 は異なるが 順序 が異なることはないことに注意されたい。どちらも履歴の接頭辞である。結果整合性のレプリカもいずれは収束するが、それまでは一度も存在しなかった状態を見せうる。論文自身も §5 でこの対比を示している。TAO は “offers eventual global consistency with asynchronous replication” (非同期レプリケーションによってグローバルな結果整合性を提供する) のに対し、Zanzibar は “provides external consistency and snapshot reads with bounded staleness” (外部一貫性と、有界な古さを伴うスナップショット読み取りを提供する)。
タイムスタンプの出どころ:TrueTime
Zanzibar はこれらのタイムスタンプを自分で計算しない。ACL を Spanner に格納しており、Spanner の “TrueTime mechanism assigns each ACL write a microsecond-resolution timestamp, such that the timestamps of writes reflect the causal ordering between writes” (TrueTime 機構は各 ACL 書き込みにマイクロ秒分解能のタイムスタンプを割り当て、書き込みのタイムスタンプが書き込み間の因果的順序を反映するようにする) (§2.2)。その仕組みの概要は Spanner の論文 (OSDI ’12) の §3、§4.1.2、§4.2.1 にある。
TT.now()は区間[earliest, latest]を返し、その区間は呼び出された絶対時刻を含むことが保証される。不確かさεは区間の幅の半分である。Google の本番環境では “typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval” (典型的には時間ののこぎり波状の関数であり、各ポーリング間隔の中で約 1 ms から 7 ms まで変化する) であった。- 開始:リーダーは書き込みに、
TT.now().latest以上のコミットタイムスタンプsを与える。 - コミット待ち:
TT.after(s)が真になるまで、つまりsがどこにおいても確実に過ぎるまで、クライアントはその書き込みを見られない。Spanner は “the expected wait is at least 2 ∗ ε̄” (期待される待ち時間は少なくとも 2 ∗ ε̄ である) と述べている。ここでε̄は平均の誤差上限である (§4.2.1)。
待つことでタイムスタンプが因果的になるのはなぜか。
最後のステップに注意されたい。書き込みを原因とするものはすべて、クライアントが通知を受けた後、つまり s が確実に過ぎた後に始まる。したがってその TT.now().latest、ひいてはそのタイムスタンプは s より大きい。これが外部一貫性であり、その代償は書き込みごとの数ミリ秒の待ち時間である。Zanzibar の論文の §5 はこれを、Zanzibar は “builds on Spanner’s TrueTime abstraction” (Spanner の TrueTime 抽象の上に構築され)、“provide linearizable commit timestamps encoded as zookies” (zookie としてエンコードされた線形化可能なコミットタイムスタンプを提供する) とまとめている。
同じ論文は、Zanzibar が代わりに論理時計を使えない理由も説明している。Lamport クロックは “require explicit participation of all ‘processes’, where in Zanzibar’s use cases some of the ‘processes’ can be external clients or even human users” (すべての「プロセス」の明示的な参加を必要とするが、Zanzibar のユースケースでは「プロセス」の一部が外部クライアントや人間のユーザーでさえありうる) (§5)。例 A における「依頼」の矢印は Alice が Charlie に話しかけることであり、どの時計にも見えない経路である。
zookie プロトコル
順序のよく定まったタイムスタンプでのスナップショット読み取りは、例 A を解決する。例 B ではさらに、チェックが 十分に新しい ことが必要である。すべてのチェックを最新のスナップショットで評価する方法もありうるが、§2.2 はそれを退けている。それは “would require global data synchronization with high-latency round trips and limited availability” (高レイテンシのラウンドトリップを伴うグローバルなデータ同期が必要となり、可用性も制限される)。代わりに、クライアント自身が必要な新しさを zookie として持ち運ぶ。zookie とは “an opaque byte sequence encoding a globally meaningful timestamp that reflects an ACL write, a client content version, or a read snapshot” (ACL の書き込み、クライアントのコンテンツバージョン、または読み取りスナップショットを反映する、グローバルに意味を持つタイムスタンプをエンコードした不透明なバイト列) である (§2.4)。
各ステップで zookie を持っているのは誰か。図では、Anne が doc:readme への編集を保存し、その後 Beto がそれを開く。
§2.2 と §2.4.4 に沿って、1 ステップずつ見ていく。
- コンテンツ変更チェック。 ユーザーが変更を保存しようとするとき、クライアントは コンテンツ変更 チェックを送る。これは “does not carry a zookie and is evaluated at the latest snapshot” (zookie を伴わず、最新のスナップショットで評価される) (§2.4.4)。
- zookie の発行。 変更が許可されれば、レスポンスに zookie が含まれる。Zanzibar は “encodes a current global timestamp in the zookie and ensures that all prior ACL writes have lower timestamps” (現在のグローバルタイムスタンプを zookie にエンコードし、それ以前のすべての ACL 書き込みがより小さいタイムスタンプを持つことを保証する) (§2.2)。
- 内容とともに格納。 “The client stores the zookie with the content change in an atomic write to the client storage” (クライアントは、クライアントストレージへのアトミックな書き込みで、内容の変更とともに zookie を格納する) (§2.2)。チェック自体は、内容の書き込みと同じトランザクション内にある必要はない。
- 後続のチェックが持ち運ぶ。 そのコンテンツバージョンに対する後続のチェックはすべて、格納された zookie を送る。
- 少なくとも同じだけ新しく評価。 “A check is always evaluated at a consistent snapshot no earlier than the given zookie” (チェックは常に、与えられた zookie より前でない一貫したスナップショットで評価される) (§2.4.4)。
例 B では、新しい内容とともに格納された zookie は T_B2 をエンコードしており、T_B2 > T_B1 なので、ステップ 5 における Bob のチェックは彼の削除を見ることになる。
zookie は意図的に不透明にされている。論文は “an opaque cookie instead of the actual timestamp to discourage our clients from choosing arbitrary timestamps and to allow future extensions” (クライアントが任意のタイムスタンプを選ぶのを抑止し、将来の拡張を可能にするため、実際のタイムスタンプではなく不透明な cookie) を用いている (§2.4)。§5 はさらに、このプロトコルは “does not let clients read or evaluate ACLs at an arbitrary snapshot” (クライアントが任意のスナップショットで ACL を読み取ったり評価したりすることを 許さない) と述べている。これにより選択が Zanzibar に委ねられる。
「ちょうどその時点」ではなく「少なくとも同じだけ新しい」理由
zookie は下限である。Zanzibar はチェックを zookie のタイムスタンプで評価してもよいし、それより後の任意のタイムスタンプで評価してもよい。§2.2 はこれをプロトコルの“at-least-as-fresh semantics” (少なくとも同じだけ新しいというセマンティクス) と呼び、それが “allow[s] Zanzibar to choose any timestamp fresher than the one encoded in a zookie” (Zanzibar が zookie にエンコードされたものより新しい任意のタイムスタンプを選択できるようにする) と述べている。この自由は 3 つの形で使われる。
- デフォルトの古さ (§3.2.1)。 zookie がない場合、サーバーは “a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency” (レイテンシに影響を与えずに可能な限り新しいタイムスタンプですべてのトランザクションが評価されるように選ばれたデフォルトの古さ) を選ぶ。各サーバーは、ある古さでの読み取りがゾーンの外に出なければならなかった頻度を追跡し、デフォルトを “the lowest ‘safe’ value” (最も低い「安全な」値) に動かす。論文は、これが “is purely a performance optimization” (純粋に性能の最適化である) と述べている。“Zanzibar always respects zookies when provided” (zookie が与えられれば、Zanzibar は常にそれを尊重する) からである。
- 量子化 (§3.2.5)。 評価タイムスタンプは “rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies” (リクエストの zookie による古さの制約を尊重しつつ、1 秒や 10 秒といった粗い粒度に切り上げられる)。切り上げ が下限を破ることはない。
- キャッシュの共有 (§3.2.5)。 キャッシュキーにはスナップショットのタイムスタンプが含まれるので、異なるスナップショットの結果が混ざることはない。切り上げのおかげで “the vast majority of recent checks and reads” (最近のチェックと読み取りの大多数) が同じタイムスタンプで評価され、“share cache results” (キャッシュ結果を共有する)。
3 つのチェックが数百ミリ秒ずつ異なる zookie を伴って届いたとき、切り上げによって何が得られるか。
T_q はわずかに未来であってもよいことに注意されたい。§3.2.5 はこの場合を扱っている。Spanner は “ensures that a snapshot read at timestamp T will observe all writes up to T—this holds even if T is in the future, in which case the read will wait until TrueTime has moved past T.” (タイムスタンプ T でのスナップショット読み取りが T までのすべての書き込みを観測することを保証する。これは T が未来であっても成り立ち、その場合、読み取りは TrueTime が T を過ぎるまで待つ。)
Safe リクエストと Recent リクエスト
新しさの代償は距離である。“When a zookie timestamp is higher than that of the most recent data replicated to the region, the storage reads require cross-region round trips to the leader replica” (zookie のタイムスタンプがそのリージョンに複製された最新データのタイムスタンプより大きい場合、ストレージの読み取りにはリーダーレプリカへのリージョンをまたぐラウンドトリップが必要となる) (§4.1)。ストレージは “replication heartbeats with 8-second intervals” (8 秒間隔のレプリケーションハートビート) で複製を行うので、§4.1 はリクエストを 10 秒で分けている。
- Safe リクエストは “have zookies more than 10 seconds old and can be served within the region most of time” (10 秒より古い zookie を持ち、ほとんどの場合リージョン内で処理できる)。
- Recent リクエストは “have zookies less than 10 seconds old and often require inter-region round trips” (10 秒未満の zookie を持ち、しばしばリージョン間のラウンドトリップを必要とする)。
8 秒は Spanner の論文と一致する。Spanner では “a leader by default advances MinNextTS() values every 8 seconds” (リーダーはデフォルトで 8 秒ごとに MinNextTS() の値を進める) ので、レプリカは “can serve reads at timestamps greater than 8 seconds old in the worst case” (最悪の場合でも 8 秒より古いタイムスタンプでの読み取りを処理できる) (Spanner §4.2.1)。
論文の表 2 (§4.2) は、2018 年 12 月の 7 日間について、各種リクエストのレイテンシをミリ秒単位で、平均 (標準偏差) として示している。
| API | 50%ile | 95%ile | 99%ile | |
|---|---|---|---|---|
| Safe | Check | 3.0 (0.091) | 9.46 (0.3) | 15.0 (1.19) |
| Safe | Read | 2.18 (0.031) | 3.71 (0.094) | 8.03 (3.28) |
| Safe | Expand | 4.27 (0.313) | 8.84 (0.586) | 34.1 (4.35) |
| Recent | Check | 2.86 (0.087) | 60.0 (2.1) | 76.3 (2.59) |
| Recent | Read | 2.21 (0.054) | 40.1 (2.03) | 86.2 (3.84) |
| Recent | Expand | 5.79 (0.224) | 45.6 (3.44) | 121.0 (2.38) |
| Recent | Write | 127.0 (3.65) | 233.0 (23.0) | 401.0 (133.0) |
中央値は近いが、テールは近くない。Recent の Check の 95 パーセンタイルは 60.0 ms で、Safe の 9.46 ms に対して大きい。これがリージョンをまたぐ往復のコストである。書き込みが最も遅いのは、書き込みが “always require distributed coordination among Spanner servers” (常に Spanner サーバー間の分散協調を必要とする) からである (§4.2)。Spanner ではその協調にコミット待ちが含まれる。§4.1 と図 3 によれば、Safe リクエストは Recent リクエストより “about two orders of magnitude” (約 2 桁) 多く、“which allows Zanzibar to serve the vast majority of ACL checks locally” (これにより Zanzibar は ACL チェックの大多数をローカルで処理できる)。大半のリクエストが Safe でいられるのは、zookie が下限にすぎないからである。古い内容に対するチェックは、すでに複製済みの古いデータを使ってよい。
出典
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.2, §2.4, §2.4.4, §3.2.1, §3.2.5, §4.1, §4.2 (Table 2), §5.
- James C. Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI ’12, §1, §3, §4.1, §4.1.2, §4.2.1.
- Maurice P. Herlihy and Jeannette M. Wing, Linearizability: A Correctness Condition for Concurrent Objects, ACM TOPLAS 12(3), July 1990, pp. 463–492.
- Philip A. Bernstein and Nathan Goodman, Multiversion Concurrency Control: Theory and Algorithms, ACM TODS 8(4), December 1983.
- David K. Gifford, Information Storage in a Decentralized Computer System, PhD thesis, Stanford, 1981 (Zanzibar の参考文献 18)。Xerox PARC CSL-81-8 (Spanner の参考文献 16) としても引用されている。リンクは確認していない。