Determining whether online users are authorized to access digital objects is central to preserving privacy. This paper presents the design, implementation, and deployment of Zanzibar, a global system for storing and evaluating access control lists. Zanzibar provides a uniform data model and configuration language for expressing a wide range of access control policies from hundreds of client services at Google, including Calendar, Cloud, Drive, Maps, Photos, and YouTube. Its authorization decisions respect causal ordering of user actions and thus provide external consistency amid changes to access control lists and object contents. Zanzibar scales to trillions of access control lists and millions of authorization requests per second to support services used by billions of people. It has maintained 95th-percentile latency of less than 10 milliseconds and availability of greater than 99.999% over 3 years of production use.
オンラインのユーザーがデジタルオブジェクトへのアクセスを認可されているかどうかを判定することは、プライバシーを守るうえで中核をなす。本論文では、アクセス制御リストを格納・評価するためのグローバルなシステムである Zanzibar の設計、実装、およびデプロイについて述べる。Zanzibar は統一されたデータモデルと設定言語を提供し、Calendar、Cloud、Drive、Maps、Photos、YouTube を含む Google の数百のクライアントサービスが求める多種多様なアクセス制御ポリシーを表現できるようにする。その認可判定はユーザーの操作の因果的順序を尊重し、それによってアクセス制御リストやオブジェクトの内容が変更される中でも外部一貫性を提供する。Zanzibar は数兆のアクセス制御リストと毎秒数百万の認可リクエストにまでスケールし、数十億人が利用するサービスを支えている。3 年間の本番運用を通じて、95 パーセンタイルレイテンシ 10 ミリ秒未満、可用性 99.999% 超を維持してきた。
Many online interactions require authorization checks to confirm that a user has permission to carry out an operation on a digital object. For example, web-based photo storage services typically allow photo owners to share some photos with friends while keeping other photos private. Such a service must check whether a photo has been shared with a user before allowing that user to view the photo. Robust authorization checks are central to preserving online privacy.
多くのオンラインのやり取りでは、ユーザーがデジタルオブジェクトに対してある操作を行う権限を持っていることを確認するための認可チェックが必要となる。たとえば、Web ベースの写真保存サービスでは一般に、写真の所有者が一部の写真を友人と共有し、他の写真は非公開のままにしておくことができる。このようなサービスは、ユーザーに写真の閲覧を許可する前に、その写真がそのユーザーと共有されているかどうかをチェックしなければならない。堅牢な認可チェックは、オンラインのプライバシーを守るうえで中核をなす。
This paper presents Zanzibar, a system for storing permissions and performing authorization checks based on the stored permissions. It is used by a wide array of services offered by Google, including Calendar, Cloud, Drive, Maps, Photos, and YouTube. Several of these services manage billions of objects on behalf of more than a billion users.
本論文では、権限を格納し、格納された権限に基づいて認可チェックを行うシステムである Zanzibar を紹介する。Zanzibar は、Calendar、Cloud、Drive、Maps、Photos、YouTube を含む、Google が提供する幅広いサービスで利用されている。これらのサービスのうちいくつかは、10 億人を超えるユーザーに代わって数十億のオブジェクトを管理している。
A unified authorization system offers important advantages over maintaining separate access control mechanisms for individual applications. First, it helps establish consistent semantics and user experience across applications. Second, it makes it easier for applications to interoperate, for example, to coordinate access control when an object from one application embeds an object from another application. Third, useful common infrastructure can be built on top of a unified access control system, in particular, a search index that respects access control and works across applications. Finally, as we show below, authorization poses unique challenges involving data consistency and scalability. It saves engineering resources to tackle them once across applications.
統一された認可システムには、個々のアプリケーションごとに別々のアクセス制御機構を維持するのに比べて重要な利点がある。第一に、アプリケーション間で一貫したセマンティクスとユーザー体験を確立しやすくなる。第二に、アプリケーション同士の相互運用が容易になる。たとえば、あるアプリケーションのオブジェクトが別のアプリケーションのオブジェクトを埋め込む場合に、アクセス制御を連携させることができる。第三に、統一されたアクセス制御システムの上に有用な共通基盤を構築できる。特に、アクセス制御を尊重し、アプリケーションをまたいで機能する検索インデックスがそれにあたる。最後に、以下で示すように、認可はデータの一貫性とスケーラビリティに関わる固有の課題を抱えている。それらにアプリケーション横断で一度だけ取り組むことで、エンジニアリングのリソースを節約できる。
- Correctness: It must ensure consistency of access control decisions to respect user intentions.
- Flexibility: It must support a rich set of access control policies as required by both consumer and enterprise applications.
- Low latency: It must respond quickly because authorization checks are often in the critical path of user interactions. Low latency at the tail is particularly important for serving search results, which often require tens to hundreds of checks.
- High availability: It must reliably respond to requests because, in the absence of explicit authorizations, client services would be forced to deny their users access.
- Large scale: It needs to protect billions of objects shared by billions of users. It must be deployed around the globe to be near its clients and their end users.
- 正確性:ユーザーの意図を尊重するため、アクセス制御判定の一貫性を保証しなければならない。
- 柔軟性:コンシューマー向けとエンタープライズ向けの両方のアプリケーションが必要とする、豊富なアクセス制御ポリシーをサポートしなければならない。
- 低レイテンシ:認可チェックはしばしばユーザーとのやり取りのクリティカルパス上にあるため、迅速に応答しなければならない。テールにおける低レイテンシは、検索結果の提供において特に重要である。検索結果の提供には、しばしば数十から数百のチェックが必要となるからである。
- 高可用性:確実にリクエストに応答しなければならない。明示的な認可がなければ、クライアントサービスはユーザーのアクセスを拒否せざるを得なくなるからである。
- 大規模性:数十億のユーザーが共有する数十億のオブジェクトを保護する必要がある。クライアントとそのエンドユーザーの近くに置くため、世界中にデプロイされなければならない。
Zanzibar achieves these goals through a combination of notable features. To provide flexibility, Zanzibar pairs a simple data model with a powerful configuration language. The language allows clients to define arbitrary relations between users and objects, such as owner, editor, commenter, and viewer. It includes set-algebraic operators such as intersection and union for specifying potentially complex access control policies in terms of those user-object relations. For example, an application can specify that users granted editing rights on a document are also allowed to comment on the document, but not all commenters are given editing rights.
Zanzibar は、いくつかの注目すべき機能を組み合わせることでこれらの目標を達成している。柔軟性を提供するため、Zanzibar はシンプルなデータモデルと強力な設定言語を組み合わせている。この言語により、クライアントはユーザーとオブジェクトの間に owner、editor、commenter、viewer といった任意の関係を定義できる。また、この言語は積集合や和集合といった集合演算子を備えており、それらのユーザーとオブジェクトの関係を用いて、潜在的に複雑なアクセス制御ポリシーを記述できる。たとえば、あるアプリケーションは、ドキュメントの編集権限を付与されたユーザーはそのドキュメントへのコメントも許可されるが、コメントできるユーザー全員に編集権限が与えられるわけではない、と指定できる。
At runtime, Zanzibar allows clients to create, modify, and evaluate access control lists (ACLs) through a remote procedure call (RPC) interface. A simple ACL takes the form of “user U has relation R to object O”. More complex ACLs take the form of “set of users S has relation R to object O”, where S is itself specified in terms of another object-relation pair. ACLs can thus refer to other ACLs, for example to specify that the set of users who can comment on a video consists of the users who have been granted viewing rights on that specific video along with those with viewing permissions on the video channel.
実行時には、Zanzibar はリモートプロシージャコール (RPC) インターフェースを通じて、クライアントがアクセス制御リスト (ACL) を作成、変更、評価できるようにする。単純な ACL は「ユーザー U はオブジェクト O に対して関係 R を持つ」という形をとる。より複雑な ACL は「ユーザーの集合 S はオブジェクト O に対して関係 R を持つ」という形をとり、ここで S 自体も別のオブジェクトと関係のペアによって指定される。このように ACL は他の ACL を参照できる。たとえば、ある動画にコメントできるユーザーの集合は、その特定の動画の閲覧権限を付与されたユーザーと、その動画のチャンネルの閲覧権限を持つユーザーから成る、と指定できる。
Group memberships are an important class of ACL where the object is a group and the relation is semantically equivalent to member. Groups can contain other groups, which illustrates one of the challenges facing Zanzibar, namely that evaluating whether a user belongs to a group can entail following a long chain of nested group memberships.
グループメンバーシップは ACL の重要な一種であり、オブジェクトがグループで、関係が意味的に member と等価なものである。グループは他のグループを含むことができる。これは Zanzibar が直面する課題の一つを示している。すなわち、ユーザーがグループに属するかどうかを評価するには、入れ子になったグループメンバーシップの長い連鎖をたどる必要が生じうるという点である。
Authorization checks take the form of “does user U have relation R to object O?” and are evaluated by a collection of distributed servers. When a check request arrives to Zanzibar, the work to evaluate the check may fan out to multiple servers, for example when a group contains both individual members and other groups. Each of those servers may in turn contact other servers, for example to recursively traverse a hierarchy of group memberships.
認可チェックは「ユーザー U はオブジェクト O に対して関係 R を持つか?」という形をとり、分散したサーバー群によって評価される。チェックリクエストが Zanzibar に到着すると、そのチェックを評価する作業は複数のサーバーにファンアウトすることがある。たとえば、グループが個々のメンバーと他のグループの両方を含む場合である。それらの各サーバーはさらに他のサーバーに問い合わせることがある。グループメンバーシップの階層を再帰的にたどる場合がその例である。
Zanzibar operates at a global scale along multiple dimensions. It stores more than two trillion ACLs and performs millions of authorization checks per second. The ACL data does not lend itself to geographic partitioning because authorization checks for any object can come from anywhere in the world. Therefore, Zanzibar replicates all ACL data in tens of geographically distributed data centers and distributes load across thousands of servers around the world.
Zanzibar は複数の次元においてグローバルな規模で稼働している。2 兆を超える ACL を格納し、毎秒数百万の認可チェックを実行している。あらゆるオブジェクトに対する認可チェックが世界のどこからでも来うるため、ACL データは地理的な分割に向かない。そのため Zanzibar は、すべての ACL データを地理的に分散した数十のデータセンターに複製し、世界中の数千台のサーバーに負荷を分散している。
Zanzibar supports global consistency of access control decisions through two interrelated features. One, it respects the order in which ACL changes are committed to the underlying data store. Two, it can ensure that authorization checks are based on ACL data no older than a client-specified change. Thus, for example, a client can remove a user from a group and be assured that subsequent membership checks reflect that removal. Zanzibar provides these ordering properties by storing ACLs in a globally distributed database system with external consistency guarantees [15, 18].
Zanzibar は、相互に関連する 2 つの機能によって、アクセス制御判定のグローバルな一貫性をサポートする。一つは、ACL の変更が基盤となるデータストアにコミットされる順序を尊重することである。もう一つは、認可チェックが、クライアントが指定した変更よりも古くない ACL データに基づくことを保証できることである。したがって、たとえばクライアントはあるユーザーをグループから削除し、その後のメンバーシップチェックにその削除が反映されることを確信できる。Zanzibar は、外部一貫性を保証するグローバル分散データベースシステムに ACL を格納することで、これらの順序特性を提供している [15, 18]。
Zanzibar employs an array of techniques to achieve low latency and high availability in this globally distributed environment. Its consistency protocol allows the vast majority of requests to be served with locally replicated data, without requiring cross-region round trips. Zanzibar stores its data in normalized forms for consistency. It handles hot spots on normalized data by caching final and intermediate results, and by deduplicating simultaneous requests. It also applies techniques such as hedging requests and optimizing computations on deeply nested sets with limited denormalization. Zanzibar responds to more than 95% of authorization checks within 10 milliseconds and has maintained more than 99.999% availability for the last 3 years.
Zanzibar は、このグローバルに分散した環境で低レイテンシと高可用性を達成するために、さまざまな技法を用いている。その一貫性プロトコルにより、リクエストの大部分はリージョンをまたぐラウンドトリップを必要とせず、ローカルに複製されたデータで処理できる。Zanzibar は一貫性のためにデータを正規化された形で格納している。正規化されたデータ上のホットスポットには、最終結果と中間結果のキャッシュ、および同時リクエストの重複排除によって対処している。また、リクエストのヘッジや、限定的な非正規化による深く入れ子になった集合上の計算の最適化といった技法も適用している。Zanzibar は認可チェックの 95% 超に 10 ミリ秒以内で応答しており、過去 3 年間にわたって 99.999% を超える可用性を維持してきた。
The main contributions of this paper lie in conveying the engineering challenges in building and deploying a consistent, world-scale authorization system. While most elements of Zanzibar’s design have their roots in previous research, this paper provides a record of the features and techniques Zanzibar brings together to satisfy its stringent requirements for correctness, flexibility, latency, availability, and scalability. The paper also highlights lessons learned from operating Zanzibar in service of a diverse set of demanding clients.
本論文の主な貢献は、一貫性のある世界規模の認可システムを構築しデプロイする際のエンジニアリング上の課題を伝える点にある。Zanzibar の設計要素の大半は先行研究にルーツを持つが、本論文は、正確性、柔軟性、レイテンシ、可用性、スケーラビリティに対する厳しい要件を満たすために Zanzibar が組み合わせた機能と技法を記録するものである。また本論文では、多様で要求の厳しいクライアント群のために Zanzibar を運用して得た教訓にも焦点を当てる。
This section describes Zanzibar’s data model, configuration language, and application programming interface (API).
本節では、Zanzibar のデータモデル、設定言語、アプリケーションプログラミングインターフェース (API) について述べる。
In Zanzibar, ACLs are collections of object-user or object-object relations represented as relation tuples. Groups are simply ACLs with membership semantics. Relation tuples have efficient binary encodings, but in this paper we represent them using a convenient text notation:
Zanzibar において、ACL はオブジェクトとユーザー、またはオブジェクトとオブジェクトの間の関係の集まりであり、リレーションタプル として表現される。グループは、単にメンバーシップのセマンティクスを持つ ACL である。リレーションタプルには効率的なバイナリエンコーディングがあるが、本論文では次のような便宜的なテキスト表記を用いて表す:
where ⟨namespace⟩ and ⟨relation⟩ are predefined in client configurations (§2.3), ⟨object_id⟩ is a string, and ⟨user_id⟩ is an integer. The primary keys required to identify a relation tuple are ⟨namespace⟩, ⟨object_id⟩, ⟨relation⟩, and ⟨user⟩. One feature worth noting is that a ⟨userset⟩ allows ACLs to refer to groups and thus supports representing nested group membership.
ここで ⟨namespace⟩ と ⟨relation⟩ はクライアントの設定で事前に定義され (§2.3)、⟨object_id⟩ は文字列、⟨user_id⟩ は整数である。リレーションタプルを識別するのに必要な主キーは ⟨namespace⟩、⟨object_id⟩、⟨relation⟩、⟨user⟩ である。注目に値する機能の一つは、⟨userset⟩ によって ACL がグループを参照でき、それにより入れ子のグループメンバーシップを表現できることである。
Table 1 shows some example tuples and corresponding semantics. While some relations (e.g. viewer) define access control directly, others (e.g. parent, pointing to a folder) only define abstract relations between objects. These abstract relations may indirectly affect access control given userset rewrite rules specified in namespace configs (§2.3.1).
表 1 に、いくつかのタプルの例と対応するセマンティクスを示す。一部の関係 (たとえば viewer) はアクセス制御を直接定義するが、他の関係 (たとえばフォルダを指す parent) はオブジェクト間の抽象的な関係を定義するだけである。これらの抽象的な関係は、名前空間設定で指定されたユーザーセット書き換えルール (§2.3.1) によって、間接的にアクセス制御に影響することがある。
Table 1: Example relation tuples. “#...” represents a relation that does not affect the semantics of the tuple.
表 1: リレーションタプルの例。「#...」はタプルのセマンティクスに影響しない関係を表す。
Defining our data model around tuples, instead of per-object ACLs, allows us to unify the concepts of ACLs and groups and to support efficient reads and incremental updates, as we will see in §2.4.
データモデルをオブジェクトごとの ACL ではなくタプルを中心に定義することで、ACL とグループの概念を統一でき、また §2.4 で見るように、効率的な読み取りと差分更新をサポートできる。
ACL checks must respect the order in which users modify ACLs and object contents to avoid unexpected sharing behaviors. Specifically, our clients care about preventing the “new enemy” problem, which can arise when we fail to respect the ordering between ACL updates or when we apply old ACLs to new content. Consider these two examples:
予期しない共有の挙動を避けるため、ACL チェックはユーザーが ACL やオブジェクトの内容を変更した順序を尊重しなければならない。具体的には、クライアントは「new enemy」問題の防止を重視している。この問題は、ACL 更新間の順序を尊重しそこねた場合や、古い ACL を新しい内容へ適用した場合に生じうる。次の 2 つの例を考える:
Example A: Neglecting ACL update order
- Alice removes Bob from the ACL of a folder;
- Alice then asks Charlie to move new documents to the folder, where document ACLs inherit from folder ACLs;
- Bob should not be able to see the new documents, but may do so if the ACL check neglects the ordering between the two ACL changes.
例 A:ACL 更新の順序の無視
- Alice がフォルダの ACL から Bob を削除する。
- 次に Alice が Charlie に、新しいドキュメントをそのフォルダに移動するよう依頼する。ドキュメントの ACL はフォルダの ACL を継承する。
- Bob は新しいドキュメントを見られないはずだが、ACL チェックが 2 つの ACL 変更間の順序を無視すると、見えてしまう可能性がある。
Example B: Misapplying old ACL to new content
- Alice removes Bob from the ACL of a document;
- Alice then asks Charlie to add new contents to the document;
- Bob should not be able to see the new contents, but may do so if the ACL check is evaluated with a stale ACL from before Bob’s removal.
例 B:古い ACL の新しい内容への誤適用
- Alice がドキュメントの ACL から Bob を削除する。
- 次に Alice が Charlie に、そのドキュメントに新しい内容を追加するよう依頼する。
- Bob は新しい内容を見られないはずだが、Bob が削除される前の古い ACL で ACL チェックが評価されると、見えてしまう可能性がある。
Preventing the “new enemy” problem requires Zanzibar to understand and respect the causal ordering between ACL or content updates, including updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar. Hence Zanzibar must provide two key consistency properties: external consistency [18] and snapshot reads with bounded staleness.
「new enemy」問題を防ぐには、Zanzibar が ACL や内容の更新間の因果的順序を理解し尊重する必要がある。これには、異なる ACL やオブジェクトに対する更新や、Zanzibar からは見えない経路を介して調整された更新も含まれる。そのため Zanzibar は、2 つの重要な一貫性特性、すなわち 外部一貫性 [18] と 有界な古さを伴うスナップショット読み取り を提供しなければならない。
External consistency allows Zanzibar to assign a timestamp to each ACL or content update, such that two causally related updates will be assigned timestamps that reflect the causal order: . With causally meaningful timestamps, a snapshot read of the ACL database at timestamp , which observes all updates with timestamps , will respect ordering between ACL updates. That is, if the read observes an update , it will observe all updates that happen causally before .
外部一貫性により、Zanzibar は各 ACL 更新や内容更新にタイムスタンプを割り当てることができ、因果的に関連する 2 つの更新 には、因果的順序を反映したタイムスタンプ が割り当てられる。因果的に意味のあるタイムスタンプがあれば、タイムスタンプ における ACL データベースのスナップショット読み取りは、タイムスタンプが であるすべての更新を観測するので、ACL 更新間の順序を尊重することになる。つまり、読み取りが更新 を観測するなら、因果的に より前に起きたすべての更新も観測する。
Furthermore, to avoid applying old ACLs to new contents, the ACL check evaluation snapshot must not be staler than the causal timestamp assigned to the content update. Given a content update at timestamp , a snapshot read at timestamp ensures that all ACL updates that happen causally before the content update will be observed by the ACL check.
さらに、古い ACL を新しい内容に適用することを避けるため、ACL チェックの評価スナップショットは、内容更新に割り当てられた因果的タイムスタンプよりも古くてはならない。タイムスタンプ における内容更新があるとき、タイムスタンプ でのスナップショット読み取りにより、内容更新より因果的に前に起きたすべての ACL 更新が ACL チェックで観測されることが保証される。
To provide external consistency and snapshot reads with bounded staleness, we store ACLs in the Spanner global database system [15]. Spanner’s TrueTime mechanism assigns each ACL write a microsecond-resolution timestamp, such that the timestamps of writes reflect the causal ordering between writes, and thereby provide external consistency. We evaluate each ACL check at a single snapshot timestamp across multiple database reads, so that all writes with timestamps up to the check snapshot, and only those writes, are visible to the ACL check.
外部一貫性と有界な古さを伴うスナップショット読み取りを提供するため、我々は ACL を Spanner グローバルデータベースシステム [15] に格納する。Spanner の TrueTime 機構は各 ACL 書き込みにマイクロ秒分解能のタイムスタンプを割り当て、書き込みのタイムスタンプが書き込み間の因果的順序を反映するようにし、それによって外部一貫性を提供する。各 ACL チェックは、複数のデータベース読み取りにまたがって単一のスナップショットタイムスタンプで評価する。これにより、チェックのスナップショットまでのタイムスタンプを持つすべての書き込み、かつそれらの書き込みのみが ACL チェックから見えるようになる。
To avoid evaluating checks for new contents using stale ACLs, one could try to always evaluate at the latest snapshot such that the check result reflects all ACL writes up to the check call. However, such evaluation would require global data synchronization with high-latency round trips and limited availability. Instead, we design the following protocol to allow most checks to be evaluated on already replicated data with cooperation from Zanzibar clients:
新しい内容に対するチェックを古い ACL で評価することを避けるため、常に最新のスナップショットで評価し、チェック呼び出し時点までのすべての ACL 書き込みをチェック結果に反映させる、という方法も考えられる。しかし、そのような評価には、高レイテンシのラウンドトリップを伴うグローバルなデータ同期が必要となり、可用性も制限される。そこで我々は、Zanzibar クライアントの協力のもとで、ほとんどのチェックを既に複製済みのデータで評価できるよう、次のプロトコルを設計した:
- A Zanzibar client requests an opaque consistency token called a zookie for each content version, via a content-change ACL check (§2.4.4) when the content modification is about to be saved. Zanzibar encodes a current global timestamp in the zookie and ensures that all prior ACL writes have lower timestamps. The client stores the zookie with the content change in an atomic write to the client storage. Note that the content-change check does not need to be evaluated in the same transaction as the application content modification, but only has to be triggered when the user modifies the contents.
- The client sends this zookie in subsequent ACL check requests to ensure that the check snapshot is at least as fresh as the timestamp for the content version.
- Zanzibar クライアントは、内容の変更が保存されようとするときに、コンテンツ変更 ACL チェック (§2.4.4) を通じて、各コンテンツバージョンに対して zookie と呼ばれる不透明な一貫性トークンを要求する。Zanzibar は現在のグローバルタイムスタンプを zookie にエンコードし、それ以前のすべての ACL 書き込みがより小さいタイムスタンプを持つことを保証する。クライアントは、クライアントストレージへのアトミックな書き込みで、内容の変更とともに zookie を格納する。なお、コンテンツ変更チェックは、アプリケーションの内容変更と同一のトランザクション内で評価する必要はなく、ユーザーが内容を変更したときにトリガーされさえすればよい。
- クライアントはその後の ACL チェックリクエストでこの zookie を送信し、チェックのスナップショットが少なくともそのコンテンツバージョンのタイムスタンプと同じだけ新しいことを保証する。
External consistency and snapshot reads with staleness bounded by zookie prevent the “new enemy” problem. In Example A, ACL updates A1 and A2 will be assigned timestamps , respectively. Bob will not be able to see the new documents added by Charlie: if a check is evaluated at , the document ACLs will not include the folder ACL; if a check is evaluated at , the check will observe update A1, which removed Bob from the folder ACL. In Example B, Bob will not see the new contents added to the document. For Bob to see the new contents, the check must be evaluated with a zookie , the timestamp assigned to the content update. Because , such a check will also observe the ACL update B1, which removed Bob from the ACL.
外部一貫性と、zookie によって古さが制限されたスナップショット読み取りによって、「new enemy」問題は防がれる。例 A では、ACL 更新 A1 と A2 にそれぞれタイムスタンプ が割り当てられる。Bob は Charlie が追加した新しいドキュメントを見ることはできない。チェックが で評価される場合、ドキュメントの ACL にはフォルダの ACL が含まれない。チェックが で評価される場合、チェックは Bob をフォルダの ACL から削除した更新 A1 を観測する。例 B では、Bob はドキュメントに追加された新しい内容を見ることはない。Bob が新しい内容を見るには、内容更新に割り当てられたタイムスタンプ以上の zookie、すなわち の zookie でチェックを評価しなければならない。 であるため、そのようなチェックは Bob を ACL から削除した ACL 更新 B1 も観測することになる。
The zookie protocol is a key feature of Zanzibar’s consistency model. It ensures that Zanzibar respects causal ordering between ACL and content updates, but otherwise grants Zanzibar freedom to choose evaluation timestamps so as to meet its latency and availability goals. The freedom arises from the protocol’s at-least-as-fresh semantics, which allow Zanzibar to choose any timestamp fresher than the one encoded in a zookie. Such freedom in turn allows Zanzibar to serve most checks at a default staleness with already replicated data (§3.2.1) and to quantize evaluation timestamps to avoid hot spots (§3.2.5).
zookie プロトコルは Zanzibar の一貫性モデルの重要な機能である。これにより、Zanzibar が ACL 更新と内容更新の間の因果的順序を尊重することが保証される一方、それ以外の点では、レイテンシと可用性の目標を満たすように評価タイムスタンプを選ぶ自由が Zanzibar に与えられる。この自由は、プロトコルの「少なくとも同じだけ新しい」というセマンティクスから生じ、これにより Zanzibar は zookie にエンコードされたものより新しい任意のタイムスタンプを選択できる。この自由によってさらに、Zanzibar はほとんどのチェックを既に複製済みのデータを用いてデフォルトの古さで処理し (§3.2.1)、ホットスポットを避けるために評価タイムスタンプを量子化する (§3.2.5) ことができる。
Before clients can store relation tuples in Zanzibar, they must configure their namespaces. A namespace configuration specifies its relations as well as its storage parameters. Each relation has a name, which is a client-defined string such as viewer or editor, and a relation config. Storage parameters include sharding settings and an encoding for object IDs that helps Zanzibar optimize storage of integer, string, and other object ID formats.
クライアントは Zanzibar にリレーションタプルを格納する前に、名前空間を設定しなければならない。名前空間設定は、その関係とストレージパラメータを指定する。各関係は、名前とリレーション設定を持つ。名前は viewer や editor のようなクライアント定義の文字列である。ストレージパラメータには、シャーディングの設定と、オブジェクト ID のエンコーディングが含まれる。後者は、Zanzibar が整数、文字列、その他のオブジェクト ID 形式のストレージを最適化するのに役立つ。
While relation tuples reflect relationships between objects and users, they do not completely define the effective ACLs. For example, some clients specify that users with editor permissions on each object should have viewer permission on the same object. While such relationships between relations can be represented by a relation tuple per object, storing a tuple for each object in a namespace would be wasteful and make it hard to make modifications across all objects. Instead, we let clients define object-agnostic relationships via userset rewrite rules in relation configs. Figure 1 demonstrates a simple namespace configuration with concentric relations, where viewer contains editor, and editor contains owner.
リレーションタプルはオブジェクトとユーザーの関係を反映するが、実効的な ACL を完全に定義するわけではない。たとえば、一部のクライアントは、各オブジェクトに対して editor 権限を持つユーザーは同じオブジェクトに対して viewer 権限も持つべきだと指定する。このような関係同士の関係はオブジェクトごとのリレーションタプルで表現することもできるが、名前空間内のオブジェクトごとにタプルを格納するのは無駄であり、全オブジェクトにまたがる変更も困難になる。そこで、クライアントがリレーション設定内の ユーザーセット書き換えルール によって、オブジェクトに依存しない関係を定義できるようにしている。図 1 は同心円状の関係を持つ単純な名前空間設定を示しており、viewer は editor を含み、editor は owner を含む。
Figure 1: Simple namespace configuration with concentric relations on documents. All owners are editors, and all editors are viewers. Further, viewers of the parent folder are also viewers of the document.
図 1: ドキュメントに対する同心円状の関係を持つ単純な名前空間設定。すべての所有者は編集者であり、すべての編集者は閲覧者である。さらに、親フォルダの閲覧者はそのドキュメントの閲覧者でもある。
Userset rewrite rules are defined per relation in a namespace. Each rule specifies a function that takes an object ID as input and outputs a userset expression tree. Each leaf node of the tree can be any of the following:
ユーザーセット書き換えルールは、名前空間内の関係ごとに定義される。各ルールは、オブジェクト ID を入力として受け取り、ユーザーセット式の木を出力する関数を指定する。木の各葉ノードは、以下のいずれかである:
_this: Returns all users from stored relation tuples for the ⟨object#relation⟩ pair, including indirect ACLs referenced by usersets from the tuples. This is the default behavior when no rewrite rule is specified.computed_userset: Computes, for the input object, a new userset. For example, this allows the userset expression for aviewerrelation to refer to theeditoruserset on the same object, thus offering an ACL inheritance capability between relations.tuple_to_userset: Computes a tupleset (§2.4.1) from the input object, fetches relation tuples matching the tupleset, and computes a userset from every fetched relation tuple. This flexible primitive allows our clients to express complex policies such as “look up the parent folder of the document and inherit its viewers”.
_this:格納されたリレーションタプルから、⟨object#relation⟩ ペアに対するすべてのユーザーを返す。これには、タプル中のユーザーセットが参照する間接 ACL も含まれる。これは、書き換えルールが指定されていない場合のデフォルトの挙動である。computed_userset:入力オブジェクトについて、新しいユーザーセットを計算する。たとえばこれにより、viewer関係のユーザーセット式が同じオブジェクトのeditorユーザーセットを参照でき、関係間での ACL 継承機能が提供される。tuple_to_userset:入力オブジェクトからタプルセット (§2.4.1) を計算し、そのタプルセットにマッチするリレーションタプルを取得して、取得した各リレーションタプルからユーザーセットを計算する。この柔軟なプリミティブにより、クライアントは「ドキュメントの親フォルダを調べて、その閲覧者を継承する」といった複雑なポリシーを表現できる。
A userset expression can also be composed of multiple sub-expressions, combined by operations such as union, intersection, and exclusion.
ユーザーセット式は、和集合、積集合、除外といった演算で組み合わされた複数の部分式から構成することもできる。
In addition to supporting ACL checks, Zanzibar also provides APIs for clients to read and write relation tuples, watch tuple updates, and inspect the effective ACLs.
Zanzibar は ACL チェックのサポートに加えて、クライアントがリレーションタプルを読み書きし、タプルの更新を監視し、実効的な ACL を調べるための API も提供している。
A concept used throughout these API methods is that of a zookie. A zookie is an opaque byte sequence encoding a globally meaningful timestamp that reflects an ACL write, a client content version, or a read snapshot. Zookies in ACL read and check requests specify staleness bounds for snapshot reads, thus providing one of Zanzibar’s core consistency properties. We choose to use an opaque cookie instead of the actual timestamp to discourage our clients from choosing arbitrary timestamps and to allow future extensions.
これらの API メソッド全体を通じて用いられる概念が zookie である。zookie は、ACL の書き込み、クライアントのコンテンツバージョン、または読み取りスナップショットを反映する、グローバルに意味を持つタイムスタンプをエンコードした不透明なバイト列である。ACL の読み取りリクエストやチェックリクエストに含まれる zookie は、スナップショット読み取りの古さの上限を指定し、それによって Zanzibar の中核的な一貫性特性の一つを提供する。実際のタイムスタンプではなく不透明な cookie を用いることにしたのは、クライアントが任意のタイムスタンプを選ぶのを抑止し、将来の拡張を可能にするためである。
Our clients read relation tuples to display ACLs or group membership to users, or to prepare for a subsequent write. A read request specifies one or multiple tuplesets and an optional zookie.
クライアントは、ユーザーに ACL やグループメンバーシップを表示するため、あるいは後続の書き込みの準備のためにリレーションタプルを読み取る。読み取りリクエストは、1 つまたは複数の タプルセット と、省略可能な zookie を指定する。
Each tupleset specifies keys of a set of relation tuples. The set can include a single tuple key, or all tuples with a given object ID or userset in a namespace, optionally constrained by a relation name. With the tuplesets, clients can look up a specific membership entry, read all entries in an ACL or group, or look up all groups with a given user as a direct member. All tuplesets in a read request are processed at a single snapshot.
各 タプルセット は、リレーションタプルの集合のキーを指定する。この集合には、単一のタプルキー、あるいは名前空間内の特定のオブジェクト ID またはユーザーセットを持つすべてのタプルを含めることができ、オプションで関係名によって絞り込むこともできる。タプルセットを用いて、クライアントは特定のメンバーシップエントリを調べたり、ACL やグループのすべてのエントリを読み取ったり、特定のユーザーを直接のメンバーとするすべてのグループを調べたりできる。読み取りリクエスト内のすべてのタプルセットは、単一のスナップショットで処理される。
With the zookie, clients can request a read snapshot no earlier than a previous write if the zookie from the write response is given in the read request, or at the same snapshot as a previous read if the zookie from the earlier read response is given in the subsequent request. If the request doesn’t contain a zookie, Zanzibar will choose a reasonably recent snapshot, possibly offering a lower-latency response than if a zookie were provided.
zookie を用いることで、クライアントは、書き込みレスポンスの zookie を読み取りリクエストに与えれば以前の書き込みより前でない読み取りスナップショットを、以前の読み取りレスポンスの zookie を後続のリクエストに与えればその読み取りと同じスナップショットを要求できる。リクエストに zookie が含まれていない場合、Zanzibar は適度に新しいスナップショットを選択し、zookie が与えられた場合よりも低レイテンシな応答を返せる可能性がある。
Read results only depend on contents of relation tuples and do not reflect userset rewrite rules. For example, even if the viewer userset always includes the owner userset, reading tuples with the viewer relation will not return tuples with the owner relation. Clients that need to understand the effective userset can use the Expand API (§2.4.5).
読み取り結果はリレーションタプルの内容のみに依存し、ユーザーセット書き換えルールは反映されない。たとえば、viewer ユーザーセットが常に owner ユーザーセットを含むとしても、viewer 関係のタプルを読み取って owner 関係のタプルが返されることはない。実効的なユーザーセットを把握する必要があるクライアントは、Expand API (§2.4.5) を使用できる。
Clients may modify a single relation tuple to add or remove an ACL. They may also modify all tuples related to an object via a read-modify-write process with optimistic concurrency control [21] that uses a read RPC followed by a write RPC:
クライアントは、ACL を追加または削除するために単一のリレーションタプルを変更できる。また、読み取り RPC の後に書き込み RPC を用いる、楽観的並行性制御 [21] による read-modify-write 処理によって、あるオブジェクトに関連するすべてのタプルを変更することもできる:
- Read all relation tuples of an object, including a per-object “lock” tuple.
- Generate the tuples to write or delete. Send the writes, along with a touch on the lock tuple, to Zanzibar, with the condition that the writes will be committed only if the lock tuple has not been modified since the read.
- If the write condition is not met, go back to step 1.
- オブジェクトのすべてのリレーションタプルを読み取る。これにはオブジェクトごとの「ロック」タプルも含まれる。
- 書き込みまたは削除するタプルを生成する。ロックタプルへの touch とともに書き込みを Zanzibar に送信する。その際、読み取り以降にロックタプルが変更されていない場合にのみ書き込みがコミットされる、という条件を付ける。
- 書き込み条件が満たされなかった場合は、ステップ 1 に戻る。
The lock tuple is just a regular relation tuple used by clients to detect write races.
ロックタプルは、クライアントが書き込みの競合を検出するために用いる、ごく普通のリレーションタプルにすぎない。
Some clients maintain secondary indices of relation tuples in Zanzibar. They can do so with our Watch API. A watch request specifies one or more namespaces and a zookie representing the time to start watching. A watch response contains all tuple modification events in ascending timestamp order, from the requested start timestamp to a timestamp encoded in a heartbeat zookie included in the watch response. The client can use the heartbeat zookie to resume watching where the previous watch response left off.
一部のクライアントは、Zanzibar 内のリレーションタプルの二次インデックスを維持している。これは Watch API を用いて実現できる。Watch リクエストは、1 つ以上の名前空間と、監視を開始する時刻を表す zookie を指定する。Watch レスポンスは、要求された開始タイムスタンプから、Watch レスポンス内の ハートビート zookie にエンコードされたタイムスタンプまでの、すべてのタプル変更イベントをタイムスタンプの昇順で含む。クライアントはハートビート zookie を用いて、前回の Watch レスポンスが終わったところから監視を再開できる。
A check request specifies a userset, represented by ⟨object#relation⟩, a putative user, often represented by an authentication token, and a zookie corresponding to the desired object version. Like reads, a check is always evaluated at a consistent snapshot no earlier than the given zookie.
チェックリクエストは、⟨object#relation⟩ で表されるユーザーセット、多くの場合は認証トークンで表されるチェック対象のユーザー、および目的のオブジェクトバージョンに対応する zookie を指定する。読み取りと同様に、チェックは常に、与えられた zookie より前でない一貫性のあるスナップショットで評価される。
To authorize application content modifications, our clients send a special type of check request, a content-change check. A content-change check request does not carry a zookie and is evaluated at the latest snapshot. If a content change is authorized, the check response includes a zookie for clients to store along with object contents and use for subsequent checks of the content version. The zookie encodes the evaluation snapshot and captures any possible causality from ACL changes to content changes, because the zookie’s timestamp will be greater than that of the ACL updates that protect the new content (§2.2).
アプリケーションの内容変更を認可するために、クライアントは特別な種類のチェックリクエストである コンテンツ変更 チェックを送信する。コンテンツ変更チェックのリクエストは zookie を持たず、最新のスナップショットで評価される。内容変更が認可された場合、チェックレスポンスには zookie が含まれ、クライアントはそれをオブジェクトの内容とともに格納し、そのコンテンツバージョンに対する後続のチェックで使用する。zookie は評価スナップショットをエンコードしており、ACL の変更から内容の変更へのあらゆる因果関係を捕捉する。zookie のタイムスタンプは、新しい内容を保護する ACL 更新のタイムスタンプよりも大きくなるからである (§2.2)。
The Expand API returns the effective userset given an ⟨object#relation⟩ pair and an optional zookie. Unlike the Read API, Expand follows indirect references expressed through userset rewrite rules. The result is represented by a userset tree whose leaf nodes are user IDs or usersets pointing to other ⟨object#relation⟩ pairs, and intermediate nodes represent union, intersection, or exclusion operators. Expand is crucial for our clients to reason about the complete set of users and groups that have access to their objects, which allows them to build efficient search indices for access-controlled content.
Expand API は、⟨object#relation⟩ ペアと省略可能な zookie を与えると、実効的なユーザーセットを返す。Read API とは異なり、Expand はユーザーセット書き換えルールによって表現された間接参照をたどる。結果は ユーザーセット木 で表される。その葉ノードはユーザー ID か、他の ⟨object#relation⟩ ペアを指すユーザーセットであり、中間ノードは和集合、積集合、除外の演算子を表す。Expand は、クライアントが自身のオブジェクトにアクセスできるユーザーとグループの完全な集合を把握するうえで不可欠であり、これによりアクセス制御されたコンテンツのための効率的な検索インデックスを構築できる。
Figure 2 shows the architecture of the Zanzibar system. aclservers are the main server type. They are organized in clusters and respond to Check, Read, Expand, and Write requests. 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.
図 2 に Zanzibar システムのアーキテクチャを示す。aclservers は主要なサーバー種別である。これらはクラスタとして編成され、Check、Read、Expand、Write の各リクエストに応答する。リクエストはクラスタ内の任意のサーバーに到着し、そのサーバーは必要に応じてクラスタ内の他のサーバーに作業をファンアウトする。それらのサーバーはさらに、中間結果を計算するために他のサーバーに問い合わせることがある。最初のサーバーが最終結果を集約し、クライアントに返す。
Zanzibar stores ACLs and their metadata in Spanner databases. There is one database to store relation tuples for each client namespace, one database to hold all namespace configurations, and one changelog database shared across all namespaces. aclservers read and write those databases in the course of responding to client requests.
Zanzibar は ACL とそのメタデータを Spanner データベースに格納する。クライアントの名前空間ごとにリレーションタプルを格納するデータベースが 1 つ、すべての名前空間設定を保持するデータベースが 1 つ、そしてすべての名前空間で共有される変更ログ (changelog) データベースが 1 つある。aclservers は、クライアントリクエストに応答する過程でこれらのデータベースを読み書きする。
watchservers are a specialized server type that respond to Watch requests. They tail the changelog and serve a stream of namespace changes to clients in near real time.
watchservers は、Watch リクエストに応答する特化したサーバー種別である。変更ログを末尾から追跡し、名前空間の変更のストリームをほぼリアルタイムでクライアントに提供する。
Zanzibar periodically runs a data processing pipeline to perform a variety of offline functions across all Zanzibar data in Spanner. One such function is to produce dumps of the relation tuples in each namespace at a known snapshot timestamp. Another is to garbage-collect tuple versions older than a threshold configured per namespace.
Zanzibar は定期的にデータ処理パイプラインを実行し、Spanner 内のすべての Zanzibar データに対してさまざまなオフライン処理を行う。その一つは、既知のスナップショットタイムスタンプにおける各名前空間のリレーションタプルのダンプを生成することである。もう一つは、名前空間ごとに設定されたしきい値より古いタプルのバージョンをガベージコレクションすることである。
Figure 2: Zanzibar architecture. Arrows indicate the direction of data flow.
図 2: Zanzibar のアーキテクチャ。矢印はデータの流れの方向を示す。
Leopard is an indexing system used to optimize operations on large and deeply nested sets. It reads periodic snapshots of ACL data and watches for changes between snapshots. It performs transformations on that data, such as denormalization, and responds to requests from aclservers.
Leopard は、大規模で深く入れ子になった集合に対する操作を最適化するために用いられるインデックスシステムである。ACL データの定期的なスナップショットを読み取り、スナップショット間の変更を監視する。そのデータに対して非正規化などの変換を行い、aclservers からのリクエストに応答する。
The rest of this section presents the implementation of these architectural elements in more detail.
本節の残りでは、これらのアーキテクチャ要素の実装をより詳細に説明する。
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). Multiple tuple versions are stored on different rows, so that we can evaluate checks and reads at any timestamp within the garbage collection window. The ordering of primary keys allows us to look up all relation tuples for a given object ID or (object ID, relation) pair.
各名前空間のリレーションタプルは個別のデータベースに格納し、各行は主キー (シャード ID, オブジェクト ID, 関係, ユーザー, コミットタイムスタンプ) で識別される。複数のタプルバージョンは別々の行に格納されるため、ガベージコレクションのウィンドウ内であれば任意のタイムスタンプでチェックや読み取りを評価できる。主キーの順序により、特定のオブジェクト ID または (オブジェクト ID, 関係) ペアに対するすべてのリレーションタプルを検索できる。
Our clients configure sharding of a namespace according to its data pattern. Usually the shard ID is determined solely by the object ID. In some cases, for example, when a namespace stores groups with very large numbers of members, the shard ID is computed from both object ID and user.
クライアントは、名前空間のデータパターンに応じてそのシャーディングを設定する。通常、シャード ID はオブジェクト ID のみによって決定される。場合によっては、たとえば非常に多数のメンバーを持つグループを格納する名前空間では、シャード ID はオブジェクト ID とユーザーの両方から計算される。
Zanzibar also maintains a changelog database that stores a history of tuple updates for the Watch API. The primary keys are (changelog shard ID, timestamp, unique update ID), where a changelog shard is randomly selected for each write.
Zanzibar はまた、Watch API のためにタプル更新の履歴を格納する変更ログデータベースも維持している。主キーは (変更ログシャード ID, タイムスタンプ, 一意な更新 ID) であり、変更ログシャードは各書き込みでランダムに選択される。
Every Zanzibar write is committed to both the tuple storage and the changelog shard in a single transaction. We designate the Spanner server hosting the changelog shard as the transaction coordinator to minimize blocking of changelog reads on pending transactions.
Zanzibar のすべての書き込みは、単一のトランザクションでタプルストレージと変更ログシャードの両方にコミットされる。保留中のトランザクションによって変更ログの読み取りがブロックされるのを最小限に抑えるため、変更ログシャードをホストする Spanner サーバーをトランザクションコーディネーターに指定している。
Namespace configs are stored in a database with two tables. One table contains the configs and is keyed by namespace IDs. The other is a changelog of config updates and is keyed by commit timestamps. This structure allows a Zanzibar server to load all configs upon startup and monitor the changelog to refresh configs continuously.
名前空間設定は、2 つのテーブルを持つデータベースに格納される。一方のテーブルは設定を保持し、名前空間 ID をキーとする。もう一方は設定更新の変更ログであり、コミットタイムスタンプをキーとする。この構造により、Zanzibar サーバーは起動時にすべての設定を読み込み、変更ログを監視して設定を継続的に更新できる。
To reduce latency, Zanzibar data is replicated to be close to our clients. 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.
レイテンシを削減するため、Zanzibar のデータはクライアントの近くに置かれるよう複製される。レプリカは世界中の数十か所に存在し、リージョンごとに複数のレプリカがある。5 つの投票レプリカは米国東部および中部にある。これらは障害を分離するため 3 つの異なる都市圏に置かれているが、Paxos トランザクションが迅速にコミットされるよう、互いの距離は 25 ミリ秒以内である。
As noted in §2.4, clients can provide zookies to ensure a minimum snapshot timestamp for request evaluation. When a zookie is not provided, the server uses a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency.
§2.4 で述べたように、クライアントは zookie を提供することで、リクエスト評価の最小スナップショットタイムスタンプを保証できる。zookie が提供されない場合、サーバーはデフォルトの古さを用いる。これは、レイテンシに影響を与えない限りできるだけ新しいタイムスタンプですべてのトランザクションが評価されるよう選ばれる。
On each read request it makes to Spanner, Zanzibar receives a hint about whether or not the data at that timestamp required an out-of-zone read and thus incurred additional latency. Each server tracks the frequency of such out-of-zone reads for data at a default staleness as well as for fresher and staler data, and uses these frequencies to compute a binomial proportion confidence interval of the probability that any given piece of data is available locally at each staleness.
Spanner に対して行う各読み取りリクエストで、Zanzibar は、そのタイムスタンプのデータがゾーン外読み取りを必要とし、したがって追加のレイテンシが発生したかどうかについてのヒントを受け取る。各サーバーは、デフォルトの古さのデータ、およびそれより新しいデータと古いデータについて、こうしたゾーン外読み取りの頻度を追跡し、これらの頻度を用いて、各古さにおいて任意のデータがローカルで利用可能である確率の二項比率信頼区間を計算する。
Upon collecting enough data, the server checks to see if each staleness value has a sufficiently low probability of incurring an out-of-zone read, and thus will be low-latency. If so, it updates the default staleness bound to the lowest “safe” value. If no known staleness values are safe, we use a two-proportion z-test to see if increasing the default will be a statistically significant amount safer. In that case, we increase the default value in the hopes of improving latency. This default staleness mechanism is purely a performance optimization. It does not violate consistency semantics because Zanzibar always respects zookies when provided.
十分なデータが集まると、サーバーは各古さの値について、ゾーン外読み取りの発生確率が十分に低く、したがって低レイテンシになるかどうかを確認する。そうであれば、デフォルトの古さの上限を最も低い「安全な」値に更新する。既知の古さの値がいずれも安全でない場合は、2 標本比率の z 検定を用いて、デフォルトを増やすことで安全性が統計的に有意な程度まで高まるかどうかを調べる。その場合、レイテンシの改善を期待してデフォルト値を増やす。このデフォルトの古さの機構は純粋に性能最適化である。Zanzibar は zookie が提供された場合、常にそれを尊重するので、一貫性のセマンティクスに違反することはない。
Because changes to namespace configs can change the results of ACL evaluations, and therefore their correctness, Zanzibar chooses a single snapshot timestamp for config metadata when evaluating each client request. All aclservers in a cluster use that same timestamp for the same request, including for any subrequests that fan out from the original client request.
名前空間設定の変更は ACL 評価の結果、ひいてはその正しさを変えうるため、Zanzibar は各クライアントリクエストを評価する際に、設定メタデータに対して単一のスナップショットタイムスタンプを選択する。クラスタ内のすべての aclservers は、同じリクエストに対しては、元のクライアントリクエストからファンアウトするあらゆるサブリクエストも含めて、同じタイムスタンプを使用する。
Each server independently loads namespace configs from storage continuously as they change (§3.1.3). Therefore, each server in a cluster may have access to a different range of config timestamps due to restarts or network latency. Zanzibar must pick a timestamp that is available across all of them. To facilitate this, a monitoring job tracks the timestamp range available to every server and aggregates them, reporting a globally available range to every other server. On each incoming request the server picks a time from this range, ensuring that all servers can continue serving even if they are no longer able to read from the config storage.
各サーバーは、名前空間設定が変更されるたびに、それをストレージから独立して継続的に読み込む (§3.1.3)。そのため、再起動やネットワークレイテンシによって、クラスタ内の各サーバーが利用できる設定タイムスタンプの範囲は異なりうる。Zanzibar は、それらすべてで利用可能なタイムスタンプを選ばなければならない。これを容易にするため、監視ジョブがすべてのサーバーで利用可能なタイムスタンプ範囲を追跡・集約し、グローバルに利用可能な範囲を他のすべてのサーバーに報告する。各受信リクエストに対し、サーバーはこの範囲から時刻を選ぶ。これにより、設定ストレージから読み取れなくなった場合でも、すべてのサーバーがサービスを継続できる。
Zanzibar evaluates ACL checks by converting check requests to boolean expressions. In a simple case, when there are no userset rewrite rules, checking a user against a userset ⟨object#relation⟩ can be expressed as
Zanzibar は、チェックリクエストをブール式に変換することで ACL チェックを評価する。ユーザーセット書き換えルールがない単純な場合、ユーザーセット ⟨object#relation⟩ に対するユーザー のチェックは次のように表せる:
Finding a valid involves evaluating membership on all indirect ACLs or groups, recursively. This kind of “pointer chasing” works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide. §3.2.4 explains how we handle this problem. Userset rewrite rules are also translated to boolean expressions as part of check evaluation.
有効な を見つけるには、すべての間接 ACL やグループのメンバーシップを再帰的に評価する必要がある。この種の「ポインタ追跡」はほとんどの種類の ACL やグループではうまく機能するが、間接 ACL やグループが深い、あるいは幅広い場合にはコストが高くなりうる。§3.2.4 で、この問題への対処方法を説明する。ユーザーセット書き換えルールも、チェック評価の一環としてブール式に変換される。
To minimize check latency, 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.
チェックのレイテンシを最小化するため、ブール式の木のすべての葉ノードを並行に評価する。あるノードの結果が部分木の結果を決定した時点で、その部分木内の他のノードの評価はキャンセルされる。
Evaluation of leaf nodes usually involves reading relation tuples from databases. We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner.
葉ノードの評価には通常、データベースからのリレーションタプルの読み取りが伴う。Spanner への読み取り RPC の数を最小化するため、同一の ACL チェックに対する読み取りをまとめるプーリング機構を適用している。
Recursive pointer chasing during check evaluation has difficulty maintaining low latency with groups that are deeply nested or have a large number of child groups. For selected namespaces that exhibit such structure, Zanzibar handles checks using Leopard, a specialized index that supports efficient set computation.
チェック評価中の再帰的なポインタ追跡では、深く入れ子になったグループや、多数の子グループを持つグループに対して低レイテンシを維持するのが難しい。そのような構造を示す選ばれた名前空間については、Zanzibar は効率的な集合計算をサポートする特化したインデックスである Leopard を用いてチェックを処理する。
A Leopard index represents a collection of named sets using tuples, where is an enum representing the set type and and are 64-bit integers representing the set ID and the element ID, respectively. A query evaluates an expression of union, intersection, or exclusion of named sets and returns the result set ordered by the element ID up to a specified number of results.
Leopard インデックスは、名前付き集合の集まりを タプルを用いて表現する。ここで は集合の種類を表す列挙型であり、 と はそれぞれ集合 ID と要素 ID を表す 64 ビット整数である。クエリは名前付き集合の和集合、積集合、除外から成る式を評価し、結果の集合を要素 ID 順に、指定された件数まで返す。
To index and evaluate group membership, Zanzibar represents group membership with two set types, and , which we show here as functions mapping from a set ID to element IDs:
グループメンバーシップをインデックス化して評価するため、Zanzibar はグループメンバーシップを と の 2 つの集合種別で表現する。ここではそれらを、集合 ID から要素 ID への写像を行う関数として示す:
- , where represents an ancestor group and represents a descendent group that is directly or indirectly a sub-group of the ancestor group.
- , where represents an individual user and represents a parent group in which the user is a direct member.
- :ここで は祖先グループを表し、 はその祖先グループの 直接または間接の サブグループである子孫グループを表す。
- :ここで は個々のユーザーを表し、 はそのユーザーが 直接の メンバーである親グループを表す。
To evaluate whether user is a member of group , we check whether
ユーザー がグループ のメンバーであるかどうかを評価するには、次が成り立つかどうかをチェックする:
Group membership can be considered as a reachability problem in a graph, where nodes represent groups and users and edges represent direct membership. Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard, though other types of denormalization can also be applied as data patterns demand.
グループメンバーシップは、ノードがグループとユーザーを、エッジが直接のメンバーシップを表すグラフにおける到達可能性問題とみなせる。グループからグループへのパスを平坦化することで、Leopard は到達可能性を効率的に評価できる。ただし、データパターンの必要に応じて他の種類の非正規化を適用することもできる。
The Leopard system consists of three discrete parts: a serving system capable of consistent and low-latency operations across sets; an offline, periodic index building system; and an online real-time layer capable of continuously updating the serving system as tuple changes occur.
Leopard システムは 3 つの独立した部分から成る。集合をまたいで一貫性のある低レイテンシな操作を行えるサービングシステム、オフラインで定期的にインデックスを構築するシステム、そしてタプルの変更が発生するにつれてサービングシステムを継続的に更新できるオンラインのリアルタイム層である。
Index tuples are stored as ordered lists of integers in a structure such as a skip list, thus allowing for efficient union and intersections among sets. For example, evaluating the intersection between two sets, and , requires only skip-list seeks. The index is sharded by element IDs and can be distributed across multiple servers. Shards are usually served entirely from memory, but they can also be served from a mix of hot and cold data spread between memory and remote solid-state devices.
インデックスタプルは、スキップリストのような構造に整数の順序付きリストとして格納され、これにより集合間の和集合や積集合を効率的に計算できる。たとえば、2 つの集合 と の積集合の評価には、 回のスキップリストのシークしか必要としない。インデックスは要素 ID によってシャーディングされ、複数のサーバーに分散できる。シャードは通常すべてメモリから提供されるが、メモリとリモートのソリッドステートデバイスにまたがって配置されたホットデータとコールドデータの組み合わせから提供することもできる。
The offline index builder generates index shards from a snapshot of Zanzibar relation tuples and configs, and replicates the shards globally. It respects userset rewrite rules and recursively expands edges in an ACL graph to form Leopard index tuples. The Leopard servers continously watch for new shards and swap old shards with new ones when they become available.
オフラインインデックスビルダーは、Zanzibar のリレーションタプルと設定のスナップショットからインデックスシャードを生成し、そのシャードをグローバルに複製する。ユーザーセット書き換えルールを尊重し、ACL グラフのエッジを再帰的に展開して Leopard のインデックスタプルを形成する。Leopard サーバーは新しいシャードを継続的に監視し、新しいシャードが利用可能になると古いシャードと入れ替える。
The Leopard system described thus far is able to efficiently evaluate deeply and widely nested group membership, but cannot do so at a fresh and consistent snapshot due to offline index generation and shard swapping. To support consistent ACL evaluation, Leopard servers maintain an incremental layer that indexes all updates since the offline snapshot, where each update is represented by a tuple, where is the timestamp of the update and is a deletion marker. Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.
ここまで述べた Leopard システムは、深くかつ広く入れ子になったグループメンバーシップを効率的に評価できるが、オフラインでのインデックス生成とシャードの入れ替えのため、新しく一貫性のあるスナップショットでそれを行うことはできない。一貫性のある ACL 評価をサポートするため、Leopard サーバーはオフラインスナップショット以降のすべての更新をインデックス化するインクリメンタル層を維持する。各更新は タプルで表され、 は更新のタイムスタンプ、 は削除マーカーである。クエリ処理中に、クエリのタイムスタンプ以下のタイムスタンプを持つ更新がオフラインインデックスの上にマージされる。
To maintain the incremental layer, the Leopard incremental indexer calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications and transforms the updates into a temporally ordered stream of Leopard tuple additions, updates, and deletions. Generating updates for the tuples requires the incremental indexer to maintain group-to-group membership for denormalizing the effects of a relation tuple update to potentially multiple index updates.
インクリメンタル層を維持するため、Leopard のインクリメンタルインデクサは Zanzibar の Watch API を呼び出して、時間順に並んだ Zanzibar のタプル変更のストリームを受け取り、その更新を時間順に並んだ Leopard のタプルの追加、更新、削除のストリームに変換する。 タプルの更新を生成するには、インクリメンタルインデクサがグループ間のメンバーシップを維持し、1 つのリレーションタプル更新の影響を潜在的に複数のインデックス更新へと非正規化する必要がある。
In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events. Each Leopard serving instance receives the complete stream of these Zanzibar tuple changes through the Watch API. The Leopard serving system is designed to continuously ingest this stream and update its various posting lists with minimal impact to query serving.
実際には、Zanzibar のタプルの追加または削除 1 件が、潜在的に数万件の個別の Leopard タプルイベントを生み出すことがある。各 Leopard サービングインスタンスは、こうした Zanzibar のタプル変更の完全なストリームを Watch API を通じて受け取る。Leopard サービングシステムは、このストリームを継続的に取り込み、クエリ処理への影響を最小限に抑えながら各種ポスティングリストを更新するよう設計されている。
The workload of ACL reads and checks is often bursty and subject to hot spots. For example, answering a search query requires conducting ACL checks for all candidate results, whose ACLs often share common groups or indirect ACLs. To facilitate consistency, Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4). With normalized data, hot spots on common ACLs (e.g., popular groups) may overload the underlying database servers. We found the handling of hot spots to be the most critical frontier in our pursuit of low latency and high availability.
ACL の読み取りとチェックのワークロードは、しばしばバースト的であり、ホットスポットが生じやすい。たとえば、検索クエリに答えるにはすべての候補結果に対して ACL チェックを行う必要があり、それらの ACL は共通のグループや間接 ACL を共有していることが多い。一貫性を確保しやすくするため、Zanzibar はストレージの非正規化を避け、正規化されたデータのみに依存している (§3.2.4 で述べた場合を除く)。正規化されたデータでは、共通の ACL (人気のあるグループなど) 上のホットスポットが、基盤となるデータベースサーバーを過負荷にすることがある。我々は、ホットスポットへの対処が、低レイテンシと高可用性を追求するうえで最も重要な最前線であることを見出した。
Zanzibar servers in each cluster form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing. Cache entries are distributed across Zanzibar servers with consistent hashing [20]. To process checks or reads, we fan out requests to the corresponding Zanzibar servers via an internal RPC interface. To minimize the number of internal RPCs, for most namespaces we compute the forwarding key from the object ID, since 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. To handle hot forwarding keys, we cache results at both the caller and the callee of internal RPCs, effectively forming cache trees. We also use Slicer [12] to help distribute hot keys to multiple servers.
各クラスタの Zanzibar サーバーは、読み取りとチェック評価の両方のための分散キャッシュを形成する。これにはポインタ追跡中に評価された中間的なチェック結果も含まれる。キャッシュエントリは、コンシステントハッシュ [20] によって Zanzibar サーバー間に分散される。チェックや読み取りを処理するため、内部 RPC インターフェースを介して対応する Zanzibar サーバーにリクエストをファンアウトする。内部 RPC の数を最小化するため、ほとんどの名前空間ではオブジェクト ID から転送キーを計算する。⟨object#relation⟩ に対するチェックの処理は、同じオブジェクトの他の関係に対する間接 ACL チェックや、そのオブジェクトのリレーションタプルの読み取りを伴うことが多いからである。これらのチェックと読み取りは、親のチェックリクエストと同じ転送キーを共有するため、同じサーバーで処理できる。ホットな転送キーに対処するため、内部 RPC の呼び出し側と呼び出される側の両方で結果をキャッシュし、実質的にキャッシュツリーを形成している。また、Slicer [12] を用いて、ホットなキーを複数のサーバーに分散させている。
We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys. We choose evaluation timestamps rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies. This timestamp quantization allows the vast majority of recent checks and reads to be evaluated at the same timestamps and to share cache results, despite having microsecond-resolution timestamps in cache keys. It is worth noting that rounding up timestamps does not affect Zanzibar’s consistency properties, since Spanner ensures that a snapshot read at timestamp will observe all writes up to —this holds even if is in the future, in which case the read will wait until TrueTime has moved past .
スナップショットタイムスタンプをキャッシュキーにエンコードすることで、異なるスナップショットで評価された結果の再利用を避けている。リクエストの zookie による古さの制約を尊重しつつ、評価タイムスタンプを 1 秒や 10 秒といった粗い粒度に切り上げて選択する。このタイムスタンプの量子化により、キャッシュキーにマイクロ秒分解能のタイムスタンプを持ちながらも、最近のチェックと読み取りの大部分を同じタイムスタンプで評価し、キャッシュ結果を共有できる。注目すべきは、タイムスタンプの切り上げが Zanzibar の一貫性特性に影響しないことである。Spanner は、タイムスタンプ でのスナップショット読み取りが までのすべての書き込みを観測することを保証するからである。これは が未来であっても成り立ち、その場合、読み取りは TrueTime が を過ぎるまで待機する。
To handle the “cache stampede” problem [3], where concurrent requests create flash hot spots before the cache is populated with results, 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.
キャッシュが結果で埋まる前に同時リクエストが瞬間的なホットスポットを生み出す「キャッシュスタンピード」問題 [3] に対処するため、各サーバーに ロックテーブル を保持し、処理中の読み取りとチェックを追跡する。同じキャッシュキーを共有するリクエストのうち、処理を開始するのは 1 つのリクエストだけであり、残りはキャッシュが埋まるまでブロックされる。
We can effectively handle the vast majority of hot spots with distributed caches and lock tables. Over time we made the following two improvements.
分散キャッシュとロックテーブルによって、ホットスポットの大部分に効果的に対処できる。時間をかけて、我々は次の 2 つの改良を行った。
First, direct membership checks of a user for an object and relation (i.e. ⟨object#relation@user⟩) are usually handled by a single relation tuple lookup. However, occasionally a very popular object invites many concurrent checks for different users, causing a hot spot on the storage server hosting relation tuples for the object. To avoid these hot spots, we read and cache all relation tuples of ⟨object#relation⟩ for the hot object, trading read bandwidth for cacheability. We dynamically detect hot objects to apply this method to by tracking the number of outstanding reads on each object.
第一に、あるオブジェクトと関係に対するユーザーの直接メンバーシップチェック (すなわち ⟨object#relation@user⟩) は、通常 1 回のリレーションタプル検索で処理される。しかし、ときに非常に人気のあるオブジェクトが、異なるユーザーに対する多数の同時チェックを招き、そのオブジェクトのリレーションタプルをホストするストレージサーバー上にホットスポットを生じさせる。こうしたホットスポットを避けるため、ホットなオブジェクトについて ⟨object#relation⟩ の すべての リレーションタプルを読み取ってキャッシュし、読み取り帯域幅と引き換えにキャッシュ可能性を得ている。この手法を適用するホットなオブジェクトは、各オブジェクトに対する処理中の読み取りの数を追跡することで動的に検出する。
Second, indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated. While eager cancellation reduces resource usage significantly, it negatively affects latency of concurrent requests that are blocked by the lock table entry. To prevent this latency impact, we delay eager cancellation when there are waiters on the corresponding lock table entry.
第二に、間接 ACL チェックは、親の ACL チェックの結果が既に決定している場合に頻繁にキャンセルされる。これにより、キャッシュキーが埋まらないまま残る。積極的なキャンセルはリソース使用量を大幅に削減するが、ロックテーブルのエントリでブロックされている同時リクエストのレイテンシに悪影響を与える。このレイテンシへの影響を防ぐため、対応するロックテーブルのエントリに待機者がいる場合には積極的なキャンセルを遅延させる。
Performance isolation is indispensable for shared services targeting low latency and high availability. If Zanzibar or one of its clients occasionally fails to provision enough resources to handle an unexpected usage pattern, the following isolation mechanisms ensure that performance problems are isolated to the problematic use case and do not adversely affect other clients.
低レイテンシと高可用性を目指す共有サービスにとって、性能分離は不可欠である。Zanzibar またはそのクライアントの一つが、予期しない利用パターンへの対処に十分なリソースをときにプロビジョニングできなかった場合でも、以下の分離機構によって、性能問題は問題のあるユースケースに隔離され、他のクライアントに悪影響を与えない。
First, to ensure proper allocation of CPU capacity, Zanzibar measures the cost of each RPC in terms of generic cpu-seconds, a hardware-agnostic metric. Each client has a global limit on maximum CPU usage per second; its RPCs will be throttled if it exceeds the limit and there is no spare capacity in the overall system.
第一に、CPU 容量を適切に割り当てるため、Zanzibar は各 RPC のコストを、ハードウェアに依存しない指標である汎用的な cpu-seconds で測定する。各クライアントには、1 秒あたりの最大 CPU 使用量に関するグローバルな上限がある。クライアントがその上限を超え、かつ システム全体に余剰容量がない場合、その RPC はスロットリングされる。
Each Zanzibar server also limits the total number of outstanding RPCs to control its memory usage. Likewise it limits the number of oustanding RPCs per client.
各 Zanzibar サーバーはまた、メモリ使用量を制御するために、処理中の RPC の総数を制限する。同様に、クライアントごとの処理中の RPC の数も制限する。
Zanzibar further limits the maximum number of concurrent reads per (object, client) and per client on each Spanner server. This ensures that no single object or client can monopolize a Spanner server.
Zanzibar はさらに、各 Spanner サーバー上で、(オブジェクト, クライアント) ごと、およびクライアントごとの同時読み取りの最大数を制限する。これにより、単一のオブジェクトやクライアントが Spanner サーバーを独占することがないようにしている。
Finally, we use different lock table keys for requests from different clients to prevent any throttling that Spanner applies to one client from affecting other clients.
最後に、異なるクライアントからのリクエストには異なるロックテーブルキーを用いることで、Spanner があるクライアントに適用したスロットリングが他のクライアントに影響することを防いでいる。
Zanzibar’s distributed processing requires measures to accommodate slow tasks. For calls to Spanner and to the Leopard index we rely on request hedging [16] (i.e. we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests). To reduce round-trip times, we try to place at least two replicas of these backend services in every geographical region where we have Zanzibar servers. To avoid unnecessarily multiplying load, we first send one request and defer sending hedged requests until the initial request is known to be slow.
Zanzibar の分散処理では、遅いタスクに対応するための措置が必要となる。Spanner と Leopard インデックスへの呼び出しについては、リクエストのヘッジ [16] に依存している (すなわち、同じリクエストを複数のサーバーに送信し、最初に返ってきたレスポンスを使用して、他のリクエストをキャンセルする)。ラウンドトリップ時間を短縮するため、Zanzibar サーバーを置くすべての地理的リージョンに、これらのバックエンドサービスのレプリカを少なくとも 2 つ配置するよう努めている。不必要に負荷を増やさないよう、まず 1 つのリクエストを送信し、最初のリクエストが遅いと判明するまでヘッジリクエストの送信を遅らせる。
To determine the appropriate hedging delay threshold, each server maintains a delay estimator that dynamically computes an Nth percentile latency based on recent measurements. This mechanism allows us to limit the additional traffic incurred by hedging to a small fraction of total traffic.
適切なヘッジの遅延しきい値を決定するため、各サーバーは、最近の計測に基づいて N パーセンタイルのレイテンシを動的に計算する遅延推定器を維持している。この機構により、ヘッジによって生じる追加トラフィックを総トラフィックのごく一部に抑えることができる。
Effective hedging requires the requests to have similar costs. In the case of Zanzibar’s authorization checks, some checks are inherently more time-consuming than others because they require more work. Hedging check requests would result in duplicating the most expensive workloads and, ironically, worsening latency. Therefore we do not hedge requests between Zanzibar servers, but rely on the previously discussed sharding among multiple replicas and on monitoring mechanisms to detect and avoid slow servers.
効果的なヘッジを行うには、リクエストのコストが同程度でなければならない。Zanzibar の認可チェックの場合、一部のチェックはより多くの作業を必要とするため、本質的に他のチェックより時間がかかる。チェックリクエストをヘッジすると、最もコストの高いワークロードが重複し、皮肉にもレイテンシが悪化することになる。そのため、Zanzibar サーバー間ではリクエストをヘッジせず、前述の複数レプリカ間でのシャーディングと、遅いサーバーを検出して回避する監視機構に依存している。
Zanzibar has been in production use for more than 5 years. Throughout that time, the number of clients using Zanzibar and the load they place on Zanzibar have grown steadily. This section discusses our experience operating Zanzibar as a globally distributed authorization system.
Zanzibar は 5 年以上にわたって本番環境で利用されてきた。その間、Zanzibar を利用するクライアントの数と、それらが Zanzibar にかける負荷は着実に増加してきた。本節では、グローバルに分散した認可システムとして Zanzibar を運用してきた経験について述べる。
Zanzibar manages more than 1,500 namespaces defined by hundreds of client applications. The size of a namespace configuration file serves as a rough measure of the complexity of the access control policy implemented by that namespace. These configuration files range from tens of lines to thousands of lines, with the median near 500 lines.
Zanzibar は、数百のクライアントアプリケーションによって定義された 1,500 を超える名前空間を管理している。名前空間設定ファイルのサイズは、その名前空間が実装するアクセス制御ポリシーの複雑さの大まかな尺度となる。これらの設定ファイルは数十行から数千行に及び、中央値は 500 行前後である。
These namespaces contain more than 2 trillion relation tuples that occupy close to 100 terabytes. The number of tuples per namespace ranges over many orders of magnitude, from tens to a trillion, with the median near 15,000. This data is fully replicated in more than 30 locations around the world to maintain both proximity to users and high availability.
これらの名前空間には、100 テラバイト近くを占める 2 兆を超えるリレーションタプルが含まれている。名前空間あたりのタプル数は、数十から 1 兆まで何桁にもわたり、中央値は 15,000 前後である。このデータは、ユーザーへの近さと高可用性の両方を維持するため、世界中の 30 を超える拠点に完全に複製されている。
Zanzibar serves more than 10 million client queries per second (QPS). Over a sample 7-day period in December 2018, Check requests peak at roughly 4.2M QPS, Read at 8.2M, Expand at 760K, and Write at 25K. Queries that read data are thus two orders of magnitude more frequent than those that write data.
Zanzibar は毎秒 1,000 万を超えるクライアントクエリ (QPS) を処理している。2018 年 12 月の 7 日間のサンプル期間において、ピーク時のリクエストは Check が約 4.2M QPS、Read が 8.2M、Expand が 760K、Write が 25K であった。したがって、データを読み取るクエリはデータを書き込むクエリより 2 桁多い。
Zanzibar distributes this load across more than 10,000 servers organized in several dozen clusters around the world. The number of servers per cluster ranges from fewer than 100 to more than 1,000, with the median near 500. Clusters are sized in proportion to load in their geographic regions.
Zanzibar はこの負荷を、世界中の数十のクラスタに編成された 10,000 台を超えるサーバーに分散している。クラスタあたりのサーバー数は 100 台未満から 1,000 台超まで幅があり、中央値は 500 台前後である。クラスタの規模は、それぞれの地理的リージョンの負荷に比例している。
We divide requests into two categories according to the required data freshness, which can have a large impact on latency and availability of the requests. Specifically, Check, Read, and Expand requests carry zookies to specify lower bounds on evaluation timestamps. 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 to retrieve fresher data. As our storage is configured with replication heartbeats with 8-second intervals, we divide our requests into two categories: Safe requests have zookies more than 10 seconds old and can be served within the region most of time, while Recent requests have zookies less than 10 seconds old and often require inter-region round trips. We report separate statistics for each.
我々はリクエストを、必要とされるデータの鮮度に応じて 2 つのカテゴリに分ける。鮮度はリクエストのレイテンシと可用性に大きな影響を与えうる。具体的には、Check、Read、Expand の各リクエストは、評価タイムスタンプの下限を指定する zookie を持つ。zookie のタイムスタンプが、そのリージョンに複製された最新のデータのタイムスタンプより大きい場合、ストレージの読み取りには、より新しいデータを取得するためにリーダーレプリカへのリージョン間ラウンドトリップが必要となる。ストレージは 8 秒間隔のレプリケーションハートビートで構成されているため、リクエストを 2 つのカテゴリに分ける。Safe リクエストは 10 秒より古い zookie を持ち、ほとんどの場合リージョン内で処理できる。一方 Recent リクエストは経過時間が 10 秒未満の zookie を持ち、しばしばリージョン間のラウンドトリップを必要とする。それぞれについて別々に統計を報告する。
Figure 3: Rate of Check Safe and Check Recent requests over a 7-day period in December 2018.
図 3: 2018 年 12 月の 7 日間における Check Safe リクエストと Check Recent リクエストのレート。
Figure 3 shows the rate of Check Safe and Check Recent requests over 7 days. Both exhibit a diurnal cycle. The rate of Safe requests is about two orders of magnitude larger than that of Recent requests, which allows Zanzibar to serve the vast majority of ACL checks locally.
図 3 に、7 日間にわたる Check Safe リクエストと Check Recent リクエストのレートを示す。どちらも日周期を示している。Safe リクエストのレートは Recent リクエストのレートより約 2 桁大きく、これにより Zanzibar は ACL チェックの大部分をローカルで処理できる。
Zanzibar’s latency budget is generally a small fraction of the few hundreds of milliseconds of total response time that its clients must provide to be viable interactive services. Consider for example a client that performs authorization checks on multiple documents before it can show the results of a search on those documents.
Zanzibar のレイテンシ予算は一般に、クライアントが実用的な対話型サービスであるために提供しなければならない数百ミリ秒の総応答時間のうち、ごく一部である。たとえば、複数のドキュメントに対する検索結果を表示する前に、それらのドキュメントに対して認可チェックを行うクライアントを考えるとよい。
We measure latency on the server side using live traffic because (1) latency is heavily influenced by our caching and de-duplication mechanisms so that it is only realistically reflected by live traffic, and (2) accurately measuring latency from clients requires well-behaving clients. Provisioning of client jobs is outside of Zanzibar’s control and sometimes client jobs are overloaded.
我々はレイテンシをライブトラフィックを用いてサーバー側で計測している。その理由は、(1) レイテンシはキャッシュと重複排除の機構に大きく左右されるため、ライブトラフィックでしか現実的に反映されないこと、そして (2) クライアントからレイテンシを正確に計測するには、行儀のよいクライアントが必要となることである。クライアントジョブのプロビジョニングは Zanzibar の管理外であり、クライアントジョブが過負荷になっていることもある。
Figure 4: Latency of Check Safe responses at different percentiles over a 7-day period in December 2018.
図 4: 2018 年 12 月の 7 日間における、各パーセンタイルでの Check Safe レスポンスのレイテンシ。
Figure 4 shows the latency of Check Safe responses over 7 days. At the 50th, 95th, 99th, and 99.9th percentiles it peaks at roughly 3, 11, 20, and 93 msec, respectively. This performance meets our latency goals for an operation that is frequently in the critical path of user interactions.
図 4 に、7 日間にわたる Check Safe レスポンスのレイテンシを示す。50、95、99、99.9 パーセンタイルにおけるピークは、それぞれ約 3、11、20、93 ミリ秒である。この性能は、ユーザーとのやり取りのクリティカルパス上にしばしば置かれる操作に対するレイテンシ目標を満たしている。
Table 2 summarizes the latency distributions of Check, Read, Expand, and Write responses over the same 7 days. As intended, the more frequently used Safe versions of Check, Read, and Expand are significantly faster than the less frequently used Recent versions. Writes are the least frequently used of all the APIs, and the slowest because they always require distributed coordination among Spanner servers.
表 2 に、同じ 7 日間における Check、Read、Expand、Write のレスポンスのレイテンシ分布をまとめる。意図したとおり、より頻繁に使われる Check、Read、Expand の Safe 版は、あまり使われない Recent 版よりも大幅に高速である。Write はすべての API の中で最も使用頻度が低く、また Spanner サーバー間での分散協調を常に必要とするため最も遅い。
Table 2: Mean and standard deviation of RPC response latency over a 7-day period in December 2018.
表 2: 2018 年 12 月の 7 日間における RPC レスポンスレイテンシの平均と標準偏差。
We define availability as the fraction of “qualified” RPCs the service answers successfully within latency thresholds: 5 seconds for a Safe request, and 15 seconds for a Recent request as leader re-election in Spanner may take up to 10 seconds. For an RPC to be qualified, the request must be well-formed and have a deadline longer than the latency threshold. In addition, the client must stay within its resource quota.
我々は可用性を、サービスがレイテンシしきい値内に正常に応答した「適格な」RPC の割合として定義する。しきい値は、Safe リクエストでは 5 秒、Recent リクエストでは 15 秒である。後者は、Spanner におけるリーダーの再選出に最大 10 秒かかることがあるためである。RPC が適格であるためには、リクエストが正しい形式であり、レイテンシしきい値より長いデッドラインを持っていなければならない。加えて、クライアントがそのリソースクォータの範囲内にとどまっていなければならない。
For these reasons, we cannot measure availability directly with live traffic, as our clients sometimes send RPCs with short deadlines or cancel their in-progress RPCs. Instead, we sample a small fraction of valid requests from live traffic and replay them later with our own probers. When replaying the requests, we set the timeout to be longer than the availability threshold. We also adjust the request zookie, if one is specified, so that the relative age of the zookie remains the same as when the request was received in the live traffic. Finally, we run 3 probers per cluster and exclude outliers to eliminate false alarms caused by rare prober failures.
こうした理由から、ライブトラフィックで可用性を直接計測することはできない。クライアントはときに短いデッドラインで RPC を送信したり、処理中の RPC をキャンセルしたりするからである。代わりに、ライブトラフィックから有効なリクエストのごく一部をサンプリングし、後で独自のプローバで再生する。リクエストを再生する際には、タイムアウトを可用性のしきい値より長く設定する。また、リクエストの zookie が指定されている場合は、zookie の相対的な経過時間がライブトラフィックでリクエストを受信したときと同じになるよう、それを調整する。最後に、クラスタごとに 3 つのプローバを実行し、まれなプローバの障害による誤警報を排除するために外れ値を除外する。
To compute availability, we aggregate success ratios over 90-day windows averaged across clusters. Figure 5 shows Zanzibar’s availability as measured by these probers. Availability has remained above 99.999% over the past 3 years of operation at Google. In other words, for every quarter, Zanzibar has less than 2 minutes of global downtime and fewer than 13 minutes when the global error ratio exceeds 10%.
可用性を算出するため、90 日間のウィンドウで成功率を集計し、クラスタ間で平均する。図 5 に、これらのプローバで計測した Zanzibar の可用性を示す。可用性は、Google における過去 3 年間の運用を通じて 99.999% を上回り続けている。言い換えれば、どの四半期においても、Zanzibar のグローバルなダウンタイムは 2 分未満であり、グローバルなエラー率が 10% を超える時間は 13 分未満である。
Figure 5: Zanzibar’s availability over the past three years has remained above 99.999%.
図 5: 過去 3 年間にわたり、Zanzibar の可用性は 99.999% を上回り続けている。
Zanzibar servers delegate checks and reads to each other based on consistent hashing, and both the caller and the callee sides of the delegated operations cache the results to prevent hot spots (§3.2.5). At peak, Zanzibar handles 22 million internal “delegated” RPCs per second, split about evenly between reads and checks. In-memory caching handles approximately 200 million lookups per second at peak, 150 million from checks and 50 million from reads. Caching for checks has a 10% hit rate on the delegate’s side, with an additional 12% saved by the lock table. Meanwhile, caching on the delegator’s side has a 2% hit rate with an additional 3% from the lock table. While these hit rates appear low, they prevent 500K internal RPCs per second from creating hot spots.
Zanzibar サーバーはコンシステントハッシュに基づいてチェックと読み取りを互いに委譲し、委譲された操作の呼び出し側と呼び出される側の両方が、ホットスポットを防ぐために結果をキャッシュする (§3.2.5)。ピーク時、Zanzibar は毎秒 2,200 万件の内部「委譲」RPC を処理しており、その内訳は読み取りとチェックでほぼ半々である。インメモリキャッシュはピーク時に毎秒約 2 億件のルックアップを処理しており、そのうち 1 億 5,000 万件がチェックから、5,000 万件が読み取りからのものである。チェックのキャッシュは、委譲先側で 10% のヒット率があり、さらにロックテーブルによって 12% が節約される。一方、委譲元側のキャッシュのヒット率は 2% で、ロックテーブルによってさらに 3% が加わる。これらのヒット率は低く見えるが、毎秒 50 万件の内部 RPC がホットスポットを生み出すのを防いでいる。
Delegated reads see higher hit rates on the delegate’s side—24% on the cache and 9% on the lock table—but the delegator’s cache is hit less than 1% of the time. For super-hot groups, Zanzibar further optimizes by reading and caching the full set of members in advance—this happens for 0.1% of groups but further prevents hot spots.
委譲された読み取りでは、委譲先側でより高いヒット率 (キャッシュ 24%、ロックテーブル 9%) が見られる。しかし委譲元のキャッシュがヒットするのは 1% 未満である。超ホットなグループについては、Zanzibar はメンバーの全集合を事前に読み取ってキャッシュすることでさらに最適化している。これはグループの 0.1% で行われているが、ホットスポットをさらに防いでいる。
This caching, along with aggressive pooling of read requests, allows Zanzibar to issue only 20 million read RPCs per second to Spanner. The median of these requests reads 1.5 rows per RPC, but at the 99th percentile they each read close to 1 thousand rows.
このキャッシュと、読み取りリクエストの積極的なプーリングによって、Zanzibar が Spanner に発行する読み取り RPC は毎秒 2,000 万件にとどまっている。これらのリクエストの中央値は RPC あたり 1.5 行を読み取るが、99 パーセンタイルではそれぞれ 1,000 行近くを読み取る。
Zanzibar’s Spanner reads take 0.5 msec at the median, and 2 msec at the 95th percentile. We find that 1% of Spanner reads, or 200K reads per second, benefit from hedging. We note that Zanzibar uses an instance of Spanner that runs internally to Google, not an instance of Cloud Spanner [6].
Zanzibar の Spanner 読み取りは、中央値で 0.5 ミリ秒、95 パーセンタイルで 2 ミリ秒かかる。Spanner 読み取りの 1%、すなわち毎秒 20 万件の読み取りがヘッジの恩恵を受けていることがわかった。なお、Zanzibar が使用しているのは Google 内部で稼働する Spanner のインスタンスであり、Cloud Spanner [6] のインスタンスではない。
The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile, based on data aggregated over 7 days. Over the same 7 days, Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile. Leopard’s incremental layer during those 7 days writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.
7 日間にわたって集計したデータに基づくと、Leopard インデックスは中央値で 1.56M QPS、99 パーセンタイルで 2.22M QPS を処理している。同じ 7 日間において、Leopard サーバーの応答時間は中央値で 150 マイクロ秒未満、99 パーセンタイルで 1 ミリ秒未満である。その 7 日間、Leopard のインクリメンタル層は、中央値で毎秒約 500 件、99 パーセンタイルで毎秒約 1.5K 件のインデックス更新を書き込んでいる。
Zanzibar has evolved to meet the varied and heavy demands of a growing set of clients, including Google Calendar, Google Cloud, Google Drive, Google Maps, Google Photos, and YouTube. This section highlights lessons learned from this experience.
Zanzibar は、Google Calendar、Google Cloud、Google Drive、Google Maps、Google Photos、YouTube を含む、増え続けるクライアント群の多様で重い要求を満たすために進化してきた。本節では、この経験から得られた教訓を取り上げる。
One common theme has been the importance of flexibility to accommodate differences between clients. For example:
共通するテーマの一つは、クライアント間の違いに対応するための柔軟性の重要性である。たとえば:
- Access control patterns vary widely: Over time we have added features to support specific clients. For instance, we added
computed_usersetto allow inferring an object’s owner ID from the object ID prefix, which reduces space requirements for clients such as Drive and Photos that manage many private objects. Similarly, we addedtuple_to_usersetto represent object hierarchy with only one relation tuple per hop. The benefits are both space reduction and flexibility—it allows clients such as Cloud both to express ACL inheritance compactly and to change ACL inheritance rules without having to update large numbers of tuples. See §2.3.1. - Freshness requirements are often but not always loose: Clients often allow unspecified, moderate staleness during ACL evaluation, but sometimes require more precisely specified freshness. We designed our zookie protocol around this property so that we can serve most requests from a default, already replicated snapshot, while allowing clients to bound the staleness when needed. We also tuned the granularity of our snapshot timestamps to match clients’ freshness requirements. The resulting coarse timestamp quanta allow us to perform the majority of authorization checks on a small number of snapshots, thus greatly reducing the frequency of database reads. See §3.2.1.
- アクセス制御のパターンは多種多様である:時間をかけて、特定のクライアントをサポートするための機能を追加してきた。たとえば、オブジェクト ID のプレフィックスからオブジェクトの所有者 ID を推論できるよう
computed_usersetを追加した。これにより、多数の非公開オブジェクトを管理する Drive や Photos などのクライアントの所要容量が削減される。同様に、ホップあたり 1 つのリレーションタプルだけでオブジェクト階層を表現できるようtuple_to_usersetを追加した。その利点は、容量の削減と柔軟性の両方である。これにより、Cloud などのクライアントは、ACL 継承をコンパクトに表現できるとともに、大量のタプルを更新することなく ACL 継承ルールを変更できる。§2.3.1 を参照。 - 鮮度の要件は緩いことが多いが、常にそうとは限らない:クライアントは ACL 評価において、明示されない適度な古さを許容することが多いが、より厳密に指定された鮮度を必要とすることもある。我々はこの特性を中心に zookie プロトコルを設計し、ほとんどのリクエストをデフォルトの既に複製済みのスナップショットから処理しつつ、必要に応じてクライアントが古さの上限を指定できるようにした。また、スナップショットタイムスタンプの粒度を、クライアントの鮮度要件に合わせて調整した。その結果得られた粗いタイムスタンプの量子により、認可チェックの大部分を少数のスナップショット上で実行でき、データベース読み取りの頻度を大幅に削減できる。§3.2.1 を参照。
Another theme has been the need to add performance optimizations to support client behaviors observed in production. For example:
もう一つのテーマは、本番環境で観測されたクライアントの挙動をサポートするために性能最適化を追加する必要性である。たとえば:
- Request hedging is key to reducing tail latency: Clients that offer search capabilities to their users, such as Drive, often issue tens to hundreds of authorization checks to serve a single set of search results. We introduced hedging of Spanner and Leopard requests to prevent an occasional slow operation from slowing the overall user interaction. See §3.2.7.
- Hot-spot mitigation is critical for high availability: Some workloads create hot spots in ACL data that can overwhelm the underlying database servers. A common pattern is a burst of ACL checks for an object that is indirectly referenced by the ACLs for many different objects. Specific instances arise from the search use case mentioned above, where the documents in the search indirectly share ACLs for a large social or work group, and Cloud use cases where many objects indirectly share ACLs for the same object high in a hierarchy. Zanzibar handles most hot spots with general mechanisms such as its distributed cache and lock table, but we have found the need to optimize specific uses cases. For example, we added cache prefetching of all relation tuples for a hot object. We also delayed cancellation of secondary ACL checks when there are concurrent requests for the same ACL data. See §3.2.5.
- Performance isolation is indispensable to protect against misbehaving clients: Even with hot-spot mitigation measures, unexpected and sometimes unintended client behaviors could still overload our system or its underlying infrastructure. Examples include when clients launch new features that prove unexpectedly popular or exercise Zanzibar in unintended ways. Over time we have added isolation safeguards to ensure that there are no cascading failures between clients or between objects of the same client. These safeguards include fine-grained cost accounting, quotas, and throttling. See §3.2.6.
- リクエストのヘッジはテールレイテンシの削減の鍵である:Drive のように、ユーザーに検索機能を提供するクライアントは、1 組の検索結果を提供するために数十から数百の認可チェックを発行することが多い。我々は、ときおり発生する遅い操作がユーザーとのやり取り全体を遅らせるのを防ぐため、Spanner と Leopard へのリクエストのヘッジを導入した。§3.2.7 を参照。
- ホットスポットの緩和は高可用性にとって極めて重要である:一部のワークロードは ACL データにホットスポットを生み出し、基盤となるデータベースサーバーを圧倒しうる。よくあるパターンは、多数の異なるオブジェクトの ACL から間接的に参照されるオブジェクトに対する ACL チェックのバーストである。具体的な事例としては、前述の検索のユースケースで、検索対象のドキュメントが大規模なソーシャルグループや職場グループの ACL を間接的に共有している場合や、Cloud のユースケースで、多数のオブジェクトが階層の上位にある同じオブジェクトの ACL を間接的に共有している場合がある。Zanzibar はほとんどのホットスポットを分散キャッシュやロックテーブルといった汎用的な機構で処理しているが、特定のユースケースを最適化する必要性も見出した。たとえば、ホットなオブジェクトのすべてのリレーションタプルをキャッシュにプリフェッチする機能を追加した。また、同じ ACL データに対する同時リクエストがある場合に、二次的な ACL チェックのキャンセルを遅延させるようにした。§3.2.5 を参照。
- 性能分離は行儀の悪いクライアントから守るために不可欠である:ホットスポットの緩和策をもってしても、予期しない、ときには意図しないクライアントの挙動が、システムやその基盤インフラを過負荷にする可能性は残る。たとえば、クライアントが予想外に人気を集める新機能をリリースした場合や、Zanzibar を意図しない方法で使用した場合である。時間をかけて、クライアント間や同一クライアントのオブジェクト間で連鎖的な障害が起きないよう、分離のための安全策を追加してきた。こうした安全策には、きめ細かいコスト計上、クォータ、スロットリングが含まれる。§3.2.6 を参照。
Zanzibar is a planet-scale distributed ACL storage and evaluation system. Many of its authorization concepts have been explored previously within the domains of access control and social graphs, and its scaling challenges have been investigated within the field of distributed systems.
Zanzibar は、惑星規模の分散 ACL ストレージおよび評価システムである。その認可の概念の多くは、アクセス制御やソーシャルグラフの分野で以前から探究されており、そのスケーリングの課題は分散システムの分野で研究されてきた。
Access control is a core part of multi-user operating systems. Multics [23] supports ACLs on segments and directories. ACL entries consist of a principal identifier and a set of permissions bits. In the first edition of UNIX [9], file flags indicate whether owner and non-owner can read or write the file. By the 4th edition, the permissions bits had been expanded to read/write/execute bits for owner, group, and others. POSIX ACLs [4] add an arbitrary list of users and groups, each with up to 32 permissions bits. VMS [7, 8] supports ACL inheritance for files created within a directory tree. Zanzibar’s data model supports permissions, users, groups, and inheritance as found in the above systems.
アクセス制御は、マルチユーザーオペレーティングシステムの中核をなす部分である。Multics [23] は、セグメントとディレクトリに対する ACL をサポートしている。ACL エントリは、プリンシパル識別子と権限ビットの集合から成る。UNIX の初版 [9] では、ファイルフラグによって、所有者と非所有者がファイルを読み書きできるかどうかが示されていた。第 4 版までに、権限ビットは所有者、グループ、その他それぞれに対する読み取り/書き込み/実行ビットへと拡張された。POSIX ACL [4] は、それぞれ最大 32 個の権限ビットを持つ、任意のユーザーとグループのリストを追加している。VMS [7, 8] は、ディレクトリツリー内に作成されたファイルに対する ACL 継承をサポートしている。Zanzibar のデータモデルは、上記のシステムに見られる権限、ユーザー、グループ、継承をサポートしている。
Taos [24, 10] supports compound principals that incorporate how an identity has been transformed as it passes through a distributed system. For example, if user logged into workstation to access file server , would see requests authenticated as “ for ” rather than just . This would allow one to write an ACL on a user’s e-mail that would be accessible only to the user, and only if being accessed via the mail server. Abadi et al. discuss in [11] a model of group-based ACLs with support for compound identities. Their notion of “blessings” are similar to Zanzibar tuples. However, Zanzibar adopts a unified representation for ACLs and groups using usersets, while they are separate concepts in [11].
Taos [24, 10] は、アイデンティティが分散システムを通過する際にどのように変換されたかを組み込んだ複合プリンシパルをサポートしている。たとえば、ユーザー がワークステーション にログインしてファイルサーバー にアクセスした場合、 からは、リクエストが単なる ではなく「 の代理としての 」として認証されて見える。これにより、ユーザーの電子メールに対して、そのユーザーだけが、しかもメールサーバー経由でアクセスされる場合にのみアクセスできる ACL を記述できる。Abadi らは [11] において、複合アイデンティティをサポートするグループベースの ACL のモデルを論じている。彼らの「blessing」という概念は Zanzibar のタプルに類似している。しかし、Zanzibar はユーザーセットを用いて ACL とグループを統一的に表現するのに対し、[11] ではそれらは別々の概念である。
Role-based access control (RBAC), first proposed in [17], introduced the notion of roles, which are similar to Zanzibar relations. Roles can inherit from each other and imply permissions. A number of Zanzibar clients have implemented RBAC policies on top of Zanzibar’s namespace configuration language.
ロールベースアクセス制御 (RBAC) は、[17] で最初に提案され、Zanzibar の関係に類似したロールの概念を導入した。ロールは互いに継承でき、権限を含意する。多くの Zanzibar クライアントは、Zanzibar の名前空間設定言語の上に RBAC ポリシーを実装している。
A discussion of ACL stores in 2019 would be remiss without mentioning the Identity and Access Management (IAM) systems offered commercially by Amazon [1], Google [5], Microsoft [2], and others. These systems allow customers of those companies’ cloud products to configure flexible access controls based on various features such as: assigning users to roles or groups; domain-specific policy languages; and APIs that allow the creation and modification of ACLs. What all of these systems have in common is unified ACL storage and an RPC-based API, a philosophy also core to Zanzibar’s design. Google’s Cloud IAM system [5] is built as a layer on top of Zanzibar’s ACL storage and evaluation system.
2019 年に ACL ストアを論じるにあたって、Amazon [1]、Google [5]、Microsoft [2] などが商用で提供している Identity and Access Management (IAM) システムに触れないのは手落ちであろう。これらのシステムにより、各社のクラウド製品の顧客は、ユーザーをロールやグループに割り当てること、ドメイン固有のポリシー言語、ACL の作成と変更を可能にする API といった、さまざまな機能に基づいて柔軟なアクセス制御を設定できる。これらすべてのシステムに共通するのは、統一された ACL ストレージと RPC ベースの API であり、これは Zanzibar の設計の中核をなす思想でもある。Google の Cloud IAM システム [5] は、Zanzibar の ACL ストレージおよび評価システムの上の層として構築されている。
TAO [13] is a distributed datastore for Facebook’s social graph. Several Zanzibar clients also use Zanzibar to store their social graphs. Both Zanzibar and TAO provide authorization checks to clients. Both are deployed as single-instance services, both operate at a large scale, and both are optimized for read-only operations. TAO offers eventual global consistency with asynchronous replication and best-effort read-after-write consistency with synchronous cache updates. In contrast, Zanzibar provides external consistency and snapshot reads with bounded staleness, so that it respects causal ordering between ACL and content updates and thus protects against the “new enemy” problem.
TAO [13] は、Facebook のソーシャルグラフのための分散データストアである。いくつかの Zanzibar クライアントも、Zanzibar を用いて自身のソーシャルグラフを格納している。Zanzibar と TAO はいずれも、クライアントに認可チェックを提供する。両者とも単一インスタンスのサービスとしてデプロイされ、大規模に稼働し、読み取り専用の操作に最適化されている。TAO は、非同期レプリケーションによる結果的なグローバル一貫性と、同期的なキャッシュ更新によるベストエフォートの read-after-write 一貫性を提供する。これに対して Zanzibar は、外部一貫性と有界な古さを伴うスナップショット読み取りを提供し、それによって ACL 更新と内容更新の間の因果的順序を尊重し、「new enemy」問題を防ぐ。
Lamport clocks [22] provide partially ordered vector timestamps that can be used to determine the order of events. However, Lamport clocks require explicit participation of all “processes”, where in Zanzibar’s use cases some of the “processes” can be external clients or even human users. In contrast, Zanzibar relies on its underlying database system, Spanner [15], to offer both external consistency and snapshot reads with bounded staleness. In particular, Zanzibar builds on Spanner’s TrueTime abstraction [15] to provide linearizable commit timestamps encoded as zookies.
Lamport クロック [22] は、イベントの順序を決定するのに使用できる半順序のベクトルタイムスタンプを提供する。しかし、Lamport クロックはすべての「プロセス」の明示的な参加を必要とする一方、Zanzibar のユースケースでは「プロセス」の一部は外部のクライアントや、さらには人間のユーザーでありうる。これに対して Zanzibar は、外部一貫性と有界な古さを伴うスナップショット読み取りの両方を提供するために、基盤となるデータベースシステムである Spanner [15] に依存している。特に、Zanzibar は Spanner の TrueTime 抽象化 [15] の上に構築されており、zookie としてエンコードされる線形化可能なコミットタイムスタンプを提供する。
At the same time, Zanzibar adds a number of features on top of those provided by Spanner. For one, the zookie protocol does not let clients read or evaluate ACLs at an arbitrary snapshot. This restriction allows Zanzibar to choose a snapshot that facilitates fast ACL evaluation. In addition, Zanzibar provides resilience to database hotspots (e.g. authorization checks on a suddenly popular video) and safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups).
同時に、Zanzibar は Spanner が提供する機能の上にいくつもの機能を追加している。一つには、zookie プロトコルはクライアントが任意のスナップショットで ACL を読み取ったり評価したりすることを 許さない。この制約により、Zanzibar は高速な ACL 評価を容易にするスナップショットを選択できる。加えて、Zanzibar はデータベースのホットスポット (たとえば、突然人気を集めた動画への認可チェック) に対する耐性と、潜在的に深い再帰があっても安全なポインタ追跡 (たとえば、階層的なグループに対するメンバーシップチェック) を提供する。
The Chubby distributed lock service [14] offers reliable storage, linearizes writes, and provides access control, but it lacks features needed to support Zanzibar’s use cases. In particular, it does not support high volumes of data, efficient range reads, or reads at a client-specified snapshot with bounded staleness. Its cache invalidation mechanism also limits its write throughput.
Chubby 分散ロックサービス [14] は、信頼性の高いストレージを提供し、書き込みを線形化し、アクセス制御を提供するが、Zanzibar のユースケースをサポートするのに必要な機能を欠いている。特に、大量のデータ、効率的な範囲読み取り、クライアントが指定したスナップショットでの有界な古さを伴う読み取りをサポートしていない。また、そのキャッシュ無効化機構によって書き込みスループットも制限される。
Finally, ZooKeeper offers a high-performance coordination service [19] but also lacks features required by Zanzibar. Relative to Chubby, it can handle higher read and write rates with more relaxed cache consistency. However, it does not provide external consistency for updates across different nodes since its linearizability is on a per-node basis. It also does not provide snapshot reads with bounded staleness.
最後に、ZooKeeper は高性能な協調サービス [19] を提供するが、やはり Zanzibar が必要とする機能を欠いている。Chubby と比べると、より緩いキャッシュ一貫性によって、より高い読み取りレートと書き込みレートを処理できる。しかし、線形化可能性がノード単位であるため、異なるノードにまたがる更新に対して外部一貫性を提供しない。また、有界な古さを伴うスナップショット読み取りも提供しない。
The Zanzibar authorization system unifies access control data and logic for Google. Its simple yet flexible data model and configuration language support a variety of access control policies from both consumer and enterprise applications.
Zanzibar 認可システムは、Google のアクセス制御のデータとロジックを統一する。そのシンプルでありながら柔軟なデータモデルと設定言語は、コンシューマー向けとエンタープライズ向けの両方のアプリケーションによる多様なアクセス制御ポリシーをサポートする。
Zanzibar’s external consistency model is one of its most salient features. It respects the ordering of user actions, yet at the same time allows authorization checks to be evaluated at distributed locations without global synchronization.
Zanzibar の外部一貫性モデルは、その最も顕著な特徴の一つである。ユーザーの操作の順序を尊重しつつ、同時に、グローバルな同期なしに分散した拠点で認可チェックを評価することを可能にする。
Zanzibar employs other key techniques to provide scalability, low latency, and high availability. For example, it evaluates deeply or widely nested group membership with Leopard, a specialized index for efficient computation of set operations with snapshot consistency. As another example, it combines a distributed cache with a mechanism to deduplicate in-flight requests. It thus mitigates hot spots, a critical production issue when serving data on top of normalized, consistent storage. These measures together result in a system that scales to trillions of access control rules and millions of authorization requests per second.
Zanzibar は、スケーラビリティ、低レイテンシ、高可用性を提供するために、他にも重要な技法を用いている。たとえば、深くあるいは広く入れ子になったグループメンバーシップを、スナップショット一貫性を備えた集合演算を効率的に計算するための特化したインデックスである Leopard を用いて評価する。また別の例として、分散キャッシュと、処理中のリクエストを重複排除する機構とを組み合わせている。これによってホットスポットを緩和している。ホットスポットは、正規化された一貫性のあるストレージの上でデータを提供する際の、本番環境における重大な問題である。これらの施策が合わさって、数兆のアクセス制御ルールと毎秒数百万の認可リクエストにまでスケールするシステムが実現されている。
Many people have made technical contributions to Zanzibar. We thank previous and recent members of the development team, including Dan Barella, Miles Chaston, Daria Jung, Alex Mendes da Costa, Xin Pan, Scott Smith, Matthew Steffen, Riva Tropp, and Yuliya Zabiyaka. We also thank previous and current members of the Site Reliability Engineering team, including Randall Bosetti, Hannes Eder, Robert Geisberger, Tom Li, Massimo Maggi, Igor Oks, Aaron Peterson, and Andrea Yu.
多くの人々が Zanzibar に技術的な貢献をしてくれた。Dan Barella、Miles Chaston、Daria Jung、Alex Mendes da Costa、Xin Pan、Scott Smith、Matthew Steffen、Riva Tropp、Yuliya Zabiyaka をはじめとする、開発チームの過去および最近のメンバーに感謝する。また、Randall Bosetti、Hannes Eder、Robert Geisberger、Tom Li、Massimo Maggi、Igor Oks、Aaron Peterson、Andrea Yu をはじめとする、Site Reliability Engineering チームの過去および現在のメンバーにも感謝する。
In addition, a number of people have helped to improve this paper. We received insightful comments from David Bacon, Carolin Gäthke, Brad Krueger, Ari Shamash, Kai Shen, and Lawrence You. We are also grateful to Nadav Eiron and Royal Hansen for their support. Finally, we thank the anonymous reviewers and our shepherd, Eric Eide, for their constructive feedback.
加えて、多くの人々が本論文の改善に協力してくれた。David Bacon、Carolin Gäthke、Brad Krueger、Ari Shamash、Kai Shen、Lawrence You から洞察に富むコメントをいただいた。また、支援をいただいた Nadav Eiron と Royal Hansen にも感謝する。最後に、建設的なフィードバックをくださった匿名の査読者と、シェパードの Eric Eide に感謝する。