paper:zanzibar#translation@zh-Hant

Zanzibar:Google 的一致性全球授權系統

Zanzibar: Google’s Consistent, Global Authorization System

原文與譯文逐段並列。將游標移到段落上會標示對應段落,¶ 可連結到該段。原文與譯文逐段排列。點選段落末尾的 ¶ 可取得該段的連結。

非官方翻譯,與 Google、USENIX 及作者無關,亦未獲其認可。論文著作權屬於作者(2019),發表於 USENIX ATC ’19。 譯文在 AI 輔助下完成,並已對照原文校對,仍可能有錯誤。

Abstract

摘要

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 是一套用於儲存及評估存取控制清單的全球性系統。Zanzibar 提供統一的資料模型與設定語言,用以表達來自 Google 數百個客戶端服務(包括 Calendar、Cloud、Drive、Maps、Photos 與 YouTube)的各式各樣存取控制政策。其授權決策遵循使用者動作的因果順序,因此在存取控制清單與物件內容發生變更時仍能提供外部一致性。Zanzibar 可擴展至數兆份存取控制清單以及每秒數百萬次授權請求,以支援數十億人使用的服務。在 3 年的正式環境使用期間,它始終維持第 95 百分位延遲低於 10 毫秒、可用性高於 99.999%。

1Introduction

1緒論

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.

許多線上互動都需要授權檢查,以確認使用者有權對某個數位物件執行某項操作。例如,網頁式相片儲存服務通常允許相片擁有者與朋友分享部分相片,同時將其他相片保持私人。此類服務在允許使用者檢視某張相片之前,必須先檢查該相片是否已分享給該使用者。穩健的授權檢查是保護線上隱私的核心。

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,一套用於儲存權限並根據所儲存之權限執行授權檢查的系統。Google 提供的眾多服務都使用它,包括 Calendar、Cloud、Drive、Maps、Photos 與 YouTube。其中數個服務代表超過十億名使用者管理數十億個物件。

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.

相較於為個別應用程式維護各自獨立的存取控制機制,統一的授權系統具有重要優勢。第一,它有助於在各應用程式之間建立一致的語意與使用者體驗。第二,它讓應用程式更容易互通,例如當某個應用程式的物件嵌入另一個應用程式的物件時,可協調兩者的存取控制。第三,可在統一的存取控制系統之上建構實用的共通基礎設施,特別是能遵循存取控制並跨應用程式運作的搜尋索引。最後,如下文所示,授權帶來了涉及資料一致性與可擴展性的獨特挑戰。跨應用程式一次性解決這些挑戰,可節省工程資源。

We have the following goals for the Zanzibar system:

我們為 Zanzibar 系統訂定了以下目標:

  • 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 在多個面向上都以全球規模運作。它儲存超過兩兆份 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 透過兩項相互關聯的特性,支援存取控制決策的全域一致性。其一,它遵循 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 在 10 毫秒內回應超過 95% 的授權檢查,並在過去 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 的過程中所學到的教訓。

2Model, Language, and API

2模型、語言與 API

This section describes Zanzibar’s data model, configuration language, and application programming interface (API).

本節說明 Zanzibar 的資料模型、設定語言與應用程式介面(API)。

2.1Relation Tuples

2.1關係元組

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。關係元組具有高效率的二進位編碼,但在本文中我們使用一種方便的文字表示法來表示它們:

⟨tuple⟩::=⟨object⟩ ‘#’ ⟨relation⟩ ‘@’ ⟨user⟩
⟨object⟩::=⟨namespace⟩ ‘:’ ⟨object_id⟩
⟨user⟩::=⟨user_id⟩ | ⟨userset⟩
⟨userset⟩::=⟨object⟩ ‘#’ ⟨relation⟩

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)之下,這些抽象關係可能會間接影響存取控制。

以文字表示法表示的元組範例Example Tuple in Text NotationSemantics語意
doc:readme#owner@10User 10 is an owner of doc:readme使用者 10 是 doc:readme 的擁有者
group:eng#member@11User 11 is a member of group:eng使用者 11 是 group:eng 的成員
doc:readme#viewer@group:eng#memberMembers of group:eng are viewers of doc:readmegroup:eng 的成員是 doc:readme 的檢視者
doc:readme#parent@folder:A#...doc:readme is in folder:Adoc:readme 位於 folder:A 中

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 中所見。

2.2Consistency Model

2.2一致性模型

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 套用於新內容時,就可能發生此問題。請看以下兩個例子:

Example A: Neglecting ACL update order

  1. Alice removes Bob from the ACL of a folder;
  2. Alice then asks Charlie to move new documents to the folder, where document ACLs inherit from folder ACLs;
  3. 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 更新順序

  1. Alice 將 Bob 從某個資料夾的 ACL 中移除;
  2. 接著 Alice 請 Charlie 將新文件移入該資料夾,其中文件的 ACL 繼承自資料夾的 ACL;
  3. Bob 應該無法看到這些新文件,但若 ACL 檢查忽略了這兩次 ACL 變更之間的順序,他就可能看得到。

Example B: Misapplying old ACL to new content

  1. Alice removes Bob from the ACL of a document;
  2. Alice then asks Charlie to add new contents to the document;
  3. 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 誤用於新內容

  1. Alice 將 Bob 從某份文件的 ACL 中移除;
  2. 接著 Alice 請 Charlie 在該文件中加入新內容;
  3. Bob 應該無法看到這些新內容,但若 ACL 檢查是以 Bob 被移除之前的陳舊 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 必須提供兩項關鍵的一致性特性:外部一致性 [18] 以及具有有界陳舊度的快照讀取。

External consistency allows Zanzibar to assign a timestamp to each ACL or content update, such that two causally related updates x≺yx \prec y will be assigned timestamps that reflect the causal order: Tx<TyT_x < T_y. With causally meaningful timestamps, a snapshot read of the ACL database at timestamp TT, which observes all updates with timestamps ≤T\le T, will respect ordering between ACL updates. That is, if the read observes an update xx, it will observe all updates that happen causally before xx.

外部一致性讓 Zanzibar 能為每次 ACL 或內容更新指派一個時間戳記,使得兩個具有因果關係的更新 x≺yx \prec y 所獲指派的時間戳記能反映其因果順序:Tx<TyT_x < T_y。有了具因果意義的時間戳記,在時間戳記 TT 對 ACL 資料庫進行的快照讀取(會觀察到所有時間戳記 ≤T\le T 的更新)將會遵循 ACL 更新之間的順序。也就是說,若該讀取觀察到更新 xx,它也會觀察到所有在因果上發生於 xx 之前的更新。

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 TcT_c, a snapshot read at timestamp ≥Tc\ge T_c ensures that all ACL updates that happen causally before the content update will be observed by the ACL check.

此外,為了避免將舊 ACL 套用於新內容,ACL 檢查評估所用的快照不得比指派給內容更新的因果時間戳記更陳舊。給定一次在時間戳記 TcT_c 的內容更新,在時間戳記 ≥Tc\ge T_c 進行的快照讀取,可確保所有在因果上發生於該內容更新之前的 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 客戶端的配合下,讓大多數檢查都能在已複製的資料上進行評估:

  1. 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.
  2. 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.
  1. Zanzibar 客戶端在內容修改即將儲存時,透過一次內容變更 ACL 檢查(§2.4.4),為每個內容版本請求一個稱為 zookie 的不透明一致性權杖。Zanzibar 會將目前的全域時間戳記編碼進 zookie,並確保所有先前的 ACL 寫入都具有較低的時間戳記。客戶端以一次原子寫入,將 zookie 與內容變更一起儲存至客戶端儲存區。請注意,內容變更檢查不需要與應用程式內容修改在同一筆交易中評估,只需在使用者修改內容時觸發即可。
  2. 客戶端在後續的 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 TA1<TA2T_{A1} < T_{A2}, respectively. Bob will not be able to see the new documents added by Charlie: if a check is evaluated at T<TA2T < T_{A2}, the document ACLs will not include the folder ACL; if a check is evaluated at T≥TA2>TA1T \ge T_{A2} > T_{A1}, 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 ≥TB2\ge T_{B2}, the timestamp assigned to the content update. Because TB2>TB1T_{B2} > T_{B1}, such a check will also observe the ACL update B1, which removed Bob from the ACL.

外部一致性,加上以 zookie 界定陳舊度的快照讀取,可防止「new enemy」問題。在例 A 中,ACL 更新 A1 與 A2 將分別被指派時間戳記 TA1<TA2T_{A1} < T_{A2}。Bob 將無法看到 Charlie 新增的文件:若檢查在 T<TA2T < T_{A2} 評估,文件的 ACL 將不包含資料夾的 ACL;若檢查在 T≥TA2>TA1T \ge T_{A2} > T_{A1} 評估,檢查將觀察到把 Bob 從資料夾 ACL 中移除的更新 A1。在例 B 中,Bob 將看不到新加入該文件的內容。若要讓 Bob 看到新內容,檢查必須以 ≥TB2\ge T_{B2}(指派給內容更新的時間戳記)的 zookie 進行評估。由於 TB2>TB1T_{B2} > T_{B1},這樣的檢查也會觀察到把 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)。

2.3Namespace Configuration

2.3命名空間設定

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 格式的儲存。

2.3.1Relation Configs and Userset Rewrites

2.3.1關係設定與使用者集合改寫

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。

name: "doc"

relation { name: "owner" }

relation {
 name: "editor"
 userset_rewrite {
  union {
   child { _this {} }
   child { computed_userset { relation: "owner" } }
} } }

relation {
 name: "viewer"
 userset_rewrite {
  union {
   child { _this {} }
   child { computed_userset { relation: "editor" } }
   child { tuple_to_userset {
     tupleset { relation: "parent" }
     computed_userset {
       object: $TUPLE_USERSET_OBJECT  # parent folder
       relation: "viewer"
   } } }
} } }

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 a viewer relation to refer to the editor userset 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.

使用者集合運算式也可以由多個子運算式組成,並以聯集、交集與排除等運算加以組合。

2.4API

2.4API

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.

除了支援 ACL 檢查之外,Zanzibar 也提供 API,讓客戶端讀取與寫入關係元組、監看元組更新,以及檢視有效的 ACL。

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 而非實際的時間戳記,是為了避免客戶端選擇任意的時間戳記,並保留未來擴充的空間。

2.4.1Read

2.4.1Read

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 或群組成員資格,或為後續的寫入做準備。讀取請求會指定一個或多個元組集合,以及一個選擇性的 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)。

2.4.2Write

2.4.2Write

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。它們也可以透過採用樂觀並行控制 [21] 的讀取—修改—寫入流程,修改與某個物件相關的所有元組;此流程先使用一次讀取 RPC,再使用一次寫入 RPC:

  1. Read all relation tuples of an object, including a per-object “lock” tuple.
  2. 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.
  3. If the write condition is not met, go back to step 1.
  1. 讀取某個物件的所有關係元組,包括一個逐物件的「鎖定」元組。
  2. 產生要寫入或刪除的元組。將這些寫入連同對鎖定元組的一次 touch 一併傳送至 Zanzibar,條件是唯有在鎖定元組自讀取以來未被修改的情況下,這些寫入才會被提交。
  3. 若寫入條件不成立,回到步驟 1。

The lock tuple is just a regular relation tuple used by clients to detect write races.

鎖定元組只是一筆一般的關係元組,供客戶端用來偵測寫入競爭。

2.4.3Watch

2.4.3Watch

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 請求會指定一個或多個命名空間,以及一個代表開始監看時間的 zookie。Watch 回應包含從請求的起始時間戳記,到 Watch 回應中所附心跳 zookie 所編碼之時間戳記為止的所有元組修改事件,並依時間戳記遞增排序。客戶端可以使用心跳 zookie,從前一個 Watch 回應結束之處繼續監看。

2.4.4Check

2.4.4Check

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.

Check 請求會指定一個以 ⟨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)。

2.4.5Expand

2.4.5Expand

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 對於我們的客戶端推論有權存取其物件的完整使用者與群組集合至關重要,這讓它們能為受存取控制的內容建構高效率的搜尋索引。

3Architecture and Implementation

3架構與實作

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 資料庫中。每個客戶端命名空間各有一個資料庫用來儲存關係元組,另有一個資料庫存放所有命名空間設定,以及一個由所有命名空間共用的變更日誌資料庫。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 資料執行各種離線功能。其中一項功能是在已知的快照時間戳記下,產生每個命名空間中關係元組的傾印。另一項則是對早於每個命名空間所設定之門檻的元組版本進行垃圾回收。

架構圖。客戶端將 Check、Read、Expand 與 Write 傳送至由相互連接的 aclservers 所組成的 Zanzibar 服務叢集。aclservers 在 Spanner 全球資料庫系統中讀寫命名空間設定與各命名空間的關係元組,並附加至變更日誌。watchserver 追蹤變更日誌的尾端,並向客戶端與 Leopard 索引系統提供 Watch。一條定期執行的離線管線讀寫 Spanner 並傾印命名空間快照,供 Leopard 讀取。Leopard 為 aclservers 提供最佳化的集合運算。

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.

本節其餘部分將更詳細地介紹這些架構元素的實作。

3.1Storage

3.1儲存

3.1.1Relation Tuple Storage

3.1.1關係元組儲存

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 與使用者計算。

3.1.2Changelog

3.1.2變更日誌

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 伺服器作為交易協調者,以盡量減少變更日誌讀取因待處理交易而被阻塞的情況。

3.1.3Namespace Config Storage

3.1.3命名空間設定儲存

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.

命名空間設定儲存在一個包含兩個資料表的資料庫中。一個資料表存放設定,以命名空間 ID 為鍵。另一個則是設定更新的變更日誌,以提交時間戳記為鍵。此結構讓 Zanzibar 伺服器能在啟動時載入所有設定,並監控變更日誌以持續更新設定。

3.1.4Replication

3.1.4複製

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 個不同的都會區以隔離故障,但彼此之間的距離在 25 毫秒以內,讓 Paxos 交易能快速提交。

3.2Serving

3.2服務

3.2.1Evaluation Timestamp

3.2.1評估時間戳記

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.

收集到足夠的資料後,伺服器會檢查每個陳舊度值發生區域外讀取的機率是否夠低,從而能維持低延遲。若是如此,它便將預設陳舊度界限更新為最低的「安全」值。若已知的陳舊度值都不安全,我們會使用雙比例 z 檢定,檢查提高預設值是否會在統計上顯著地更安全。若是如此,我們便提高預設值,以期改善延遲。此預設陳舊度機制純粹是一種效能最佳化。它不會違反一致性語意,因為只要提供了 zookie,Zanzibar 一律會遵循。

3.2.2Config Consistency

3.2.2設定一致性

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 必須挑選一個在所有伺服器上都可用的時間戳記。為此,一項監控工作會追蹤每台伺服器可用的時間戳記範圍並加以彙整,再將全域可用的範圍回報給其他每一台伺服器。對於每個傳入的請求,伺服器會從此範圍中挑選一個時間,確保即使伺服器已無法從設定儲存區讀取,所有伺服器仍能繼續提供服務。

3.2.3Check Evaluation

3.2.3檢查評估

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 UU against a userset ⟨object#relation⟩ can be expressed as

Zanzibar 透過將檢查請求轉換為布林運算式來評估 ACL 檢查。在沒有使用者集合改寫規則的簡單情況下,針對使用者集合 ⟨object#relation⟩ 檢查使用者 UU 可以表示為

CHECK(U,⟨object#relation⟩)=∃ tuple ⟨object#relation@U⟩∨ ∃ tuple ⟨object#relation@U′⟩, whereU′=⟨object′#relation′⟩ s.t. CHECK(U,U′).\begin{aligned} \mathrm{CHECK}(U, \langle \mathit{object}\#\mathit{relation} \rangle) ={} & \exists\ \text{tuple}\ \langle \mathit{object}\#\mathit{relation}@U \rangle \\ \lor\ & \exists\ \text{tuple}\ \langle \mathit{object}\#\mathit{relation}@U' \rangle,\ \text{where} \\ & U' = \langle \mathit{object}'\#\mathit{relation}' \rangle\ \text{s.t.}\ \mathrm{CHECK}(U, U'). \end{aligned}

Finding a valid U′=⟨object′#relation′⟩U' = \langle \mathit{object}'\#\mathit{relation}' \rangle 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.

找出有效的 U′=⟨object′#relation′⟩U' = \langle \mathit{object}'\#\mathit{relation}' \rangle 需要以遞迴方式評估所有間接 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.

葉節點的評估通常涉及從資料庫讀取關係元組。我們採用一種池化機制,將同一 ACL 檢查的讀取歸併在一起,以盡量減少發送至 Spanner 的讀取 RPC 數量。

3.2.4Leopard Indexing System

3.2.4Leopard 索引系統

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 處理檢查;Leopard 是一種支援高效率集合運算的專用索引。

A Leopard index represents a collection of named sets using (T,s,e)(T, s, e) tuples, where TT is an enum representing the set type and ss and ee 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 索引使用 (T,s,e)(T, s, e) 元組來表示一組具名集合,其中 TT 為代表集合類型的列舉值,ss 與 ee 為 64 位元整數,分別代表集合 ID 與元素 ID。查詢會評估由具名集合的聯集、交集或排除所構成的運算式,並傳回依元素 ID 排序的結果集合,最多傳回指定數量的結果。

To index and evaluate group membership, Zanzibar represents group membership with two set types, GROUP2GROUP\textsf{GROUP2GROUP} and MEMBER2GROUP\textsf{MEMBER2GROUP}, which we show here as functions mapping from a set ID to element IDs:

為了索引及評估群組成員資格,Zanzibar 以兩種集合類型 GROUP2GROUP\textsf{GROUP2GROUP} 與 MEMBER2GROUP\textsf{MEMBER2GROUP} 來表示群組成員資格,此處我們將其表示為從集合 ID 映射到元素 ID 的函式:

  • GROUP2GROUP(s)→{e}\textsf{GROUP2GROUP}(s) \to \{e\}, where ss represents an ancestor group and ee represents a descendent group that is directly or indirectly a sub-group of the ancestor group.
  • MEMBER2GROUP(s)→{e}\textsf{MEMBER2GROUP}(s) \to \{e\}, where ss represents an individual user and ee represents a parent group in which the user is a direct member.
  • GROUP2GROUP(s)→{e}\textsf{GROUP2GROUP}(s) \to \{e\},其中 ss 代表一個祖先群組,ee 代表一個直接或間接屬於該祖先群組之子群組的後代群組。
  • MEMBER2GROUP(s)→{e}\textsf{MEMBER2GROUP}(s) \to \{e\},其中 ss 代表一位個別使用者,ee 代表該使用者為其直接成員的上層群組。

To evaluate whether user UU is a member of group GG, we check whether

為了評估使用者 UU 是否為群組 GG 的成員,我們檢查是否滿足

(MEMBER2GROUP(U)∩GROUP2GROUP(G))≠∅(\textsf{MEMBER2GROUP}(U) \cap \textsf{GROUP2GROUP}(G)) \neq \emptyset

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 系統由三個獨立部分組成:一套能跨集合執行一致且低延遲操作的服務系統;一套離線、定期執行的索引建構系統;以及一個線上即時層,能在元組變更發生時持續更新服務系統。

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, AA and BB, requires only O(min⁡(∣A∣,∣B∣))O(\min(|A|, |B|)) 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.

索引元組以有序整數清單的形式,儲存在跳躍串列之類的結構中,從而能在集合之間高效率地進行聯集與交集。例如,評估兩個集合 AA 與 BB 的交集,只需要 O(min⁡(∣A∣,∣B∣))O(\min(|A|, |B|)) 次跳躍串列搜尋。索引依元素 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 (T,s,e,t,d)(T, s, e, t, d) tuple, where tt is the timestamp of the update and dd 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 伺服器維護一個增量層,為自離線快照以來的所有更新建立索引,其中每次更新以一個 (T,s,e,t,d)(T, s, e, t, d) 元組表示,tt 為更新的時間戳記,dd 為刪除標記。在查詢處理期間,時間戳記小於或等於查詢時間戳記的更新會合併至離線索引之上。

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 GROUP2GROUP\textsf{GROUP2GROUP} 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 元組新增、更新與刪除串流。為 GROUP2GROUP\textsf{GROUP2GROUP} 元組產生更新時,增量索引器需要維護群組到群組的成員關係,以便將一次關係元組更新的影響反正規化為可能多次的索引更新。

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 元組的新增或刪除,可能產生多達數萬個個別的 Leopard 元組事件。每個 Leopard 服務實例都透過 Watch API 接收這些 Zanzibar 元組變更的完整串流。Leopard 服務系統的設計目標是持續攝取此串流,並在對查詢服務影響最小的情況下更新其各種倒排清單。

3.2.5Handling Hot Spots

3.2.5處理熱點

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 TT will observe all writes up to TT—this holds even if TT is in the future, in which case the read will wait until TrueTime has moved past TT.

我們透過將快照時間戳記編碼進快取鍵,避免重複使用從不同快照評估出的結果。我們選擇的評估時間戳記會向上取整至較粗的粒度,例如一秒或十秒,同時遵循請求 zookie 所施加的陳舊度限制。這種時間戳記量化讓絕大多數近期的檢查與讀取能在相同的時間戳記上評估並共用快取結果,儘管快取鍵中的時間戳記具有微秒解析度。值得注意的是,將時間戳記向上取整並不會影響 Zanzibar 的一致性特性,因為 Spanner 確保在時間戳記 TT 進行的快照讀取會觀察到直到 TT 為止的所有寫入——即使 TT 位於未來也是如此,此時讀取會等待,直到 TrueTime 越過 TT 為止。

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](亦即在快取填入結果之前,並行請求造成瞬間熱點),我們在每台伺服器上維護一個鎖定表,以追蹤未完成的讀取與檢查。在共用相同快取鍵的請求中,只有一個請求會開始處理;其餘請求則會阻塞,直到快取被填入為止。

We can effectively handle the vast majority of hot spots with distributed caches and lock tables. Over time we made the following two improvements.

透過分散式快取與鎖定表,我們能有效處理絕大多數熱點。隨著時間推移,我們做了以下兩項改進。

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⟩)通常只需一次關係元組查找即可處理。然而,偶爾會有非常熱門的物件吸引大量針對不同使用者的並行檢查,導致託管該物件關係元組的儲存伺服器出現熱點。為了避免這些熱點,我們針對熱門物件讀取並快取 ⟨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 檢查經常會被取消。這會使快取鍵維持未填入的狀態。雖然積極取消可大幅減少資源使用量,但它會對被鎖定表項目阻塞的並行請求的延遲造成負面影響。為了防止這種延遲影響,當對應的鎖定表項目上有等待者時,我們會延後積極取消。

3.2.6Performance Isolation

3.2.6效能隔離

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 以通用的 cpu-seconds(一種與硬體無關的指標)來衡量每個 RPC 的成本。每個客戶端都有一個全域的每秒最大 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 對某個客戶端施加的節流影響到其他客戶端。

3.2.7Tail Latency Mitigation

3.2.7尾端延遲緩解

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 伺服器的地理區域中,為這些後端服務放置至少兩個副本。為了避免不必要地使負載倍增,我們會先傳送一個請求,並延後傳送對沖請求,直到已知最初的請求很慢為止。

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 伺服器之間對沖請求,而是仰賴先前討論過的多副本間分片,以及監控機制來偵測並避開緩慢的伺服器。

4Experience

4經驗

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.

這些命名空間包含超過 2 兆筆關係元組,佔用將近 100 TB。每個命名空間的元組數量橫跨多個數量級,從數十筆到一兆筆不等,中位數接近 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 請求的尖峰約為 420 萬 QPS,Read 為 820 萬,Expand 為 76 萬,Write 為 2.5 萬。因此,讀取資料的查詢比寫入資料的查詢頻繁兩個數量級。

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 台。各叢集的規模依其所在地理區域的負載比例配置。

4.1Requests

4.1請求

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.

我們依據所需的資料新鮮度將請求分為兩類,新鮮度可能對請求的延遲與可用性造成很大影響。具體而言,Check、Read 與 Expand 請求會攜帶 zookie,以指定評估時間戳記的下限。當 zookie 的時間戳記高於已複製到該區域之最新資料的時間戳記時,儲存讀取就需要跨區域往返至領導者副本,以取得較新的資料。由於我們的儲存設定為以 8 秒間隔進行複製心跳,我們將請求分為兩類:Safe 請求的 zookie 時齡超過 10 秒,大多數時候可在區域內提供服務;而 Recent 請求的 zookie 時齡未滿 10 秒,經常需要跨區域往返。我們分別報告兩者的統計數據。

一週(星期日至星期六)的對數刻度折線圖。Safe QPS 每日在約 200 萬至 400 萬之間波動;Recent QPS 在約 2 萬至 8 萬之間波動,約低兩個數量級。

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 請求高兩個數量級,這讓 Zanzibar 能在本地處理絕大多數 ACL 檢查。

4.2Latency

4.2延遲

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 的掌控範圍內,而客戶端工作有時會過載。

一週內 Check Safe 延遲的對數刻度折線圖。第 50 百分位維持在 3 ms 左右,第 95 百分位在 10 ms 左右,第 99 百分位約在 13 至 20 ms 之間,第 99.9 百分位約在 50 至 90 ms 之間。

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 版本更快。在所有 API 中,Write 的使用頻率最低,速度也最慢,因為它們一律需要 Spanner 伺服器之間的分散式協調。

延遲(毫秒),μ (σ)
API50%ile95%ile99%ile
SafeCheck3.0 (0.091)9.46 (0.3)15.0 (1.19)
Read2.18 (0.031)3.71 (0.094)8.03 (3.28)
Expand4.27 (0.313)8.84 (0.586)34.1 (4.35)
RecentCheck2.86 (0.087)60.0 (2.1)76.3 (2.59)
Read2.21 (0.054)40.1 (2.03)86.2 (3.84)
Expand5.79 (0.224)45.6 (3.44)121.0 (2.38)
Write127.0 (3.65)233.0 (23.0)401.0 (133.0)
Latency in milliseconds, μ (σ)
API50%ile95%ile99%ile
SafeCheck3.0 (0.091)9.46 (0.3)15.0 (1.19)
Read2.18 (0.031)3.71 (0.094)8.03 (3.28)
Expand4.27 (0.313)8.84 (0.586)34.1 (4.35)
RecentCheck2.86 (0.087)60.0 (2.1)76.3 (2.59)
Read2.21 (0.054)40.1 (2.03)86.2 (3.84)
Expand5.79 (0.224)45.6 (3.44)121.0 (2.38)
Write127.0 (3.65)233.0 (23.0)401.0 (133.0)

Table 2: Mean and standard deviation of RPC response latency over a 7-day period in December 2018.

表 2:2018 年 12 月一段 7 天期間內 RPC 回應延遲的平均值與標準差。

4.3Availability

4.3可用性

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 分鐘。

2015 年 12 月至 2018 年 12 月 Safe 與 Recent 請求可用性的折線圖。兩者幾乎始終維持在 99.9995% 至 100% 之間,遠高於 99.999% 的虛線。

Figure 5: Zanzibar’s availability over the past three years has remained above 99.999%.

圖 5:Zanzibar 過去三年的可用性始終維持在 99.999% 以上。

4.4Internals

4.4內部運作

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 億次來自檢查,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 發出 2,000 萬次讀取 RPC。這些請求的中位數為每個 RPC 讀取 1.5 列,但在第 99 百分位,每個請求讀取接近 1 千列。

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 毫秒。我們發現 1% 的 Spanner 讀取(即每秒 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 索引在中位數執行 156 萬 QPS,在第 99 百分位執行 222 萬 QPS。在同樣的 7 天內,Leopard 伺服器在中位數的回應時間少於 150 微秒,在第 99 百分位則低於 1 毫秒。在這 7 天內,Leopard 的增量層在中位數每秒寫入約 500 次索引更新,在第 99 百分位每秒約 1,500 次更新。

4.5Lessons Learned

4.5經驗教訓

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_userset to 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 added tuple_to_userset to 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.
  • 存取控制模式差異極大:隨著時間推移,我們加入了一些功能以支援特定客戶端。例如,我們加入了 computed_userset,讓系統能從物件 ID 前綴推斷物件擁有者的 ID,這減少了 Drive 與 Photos 等管理大量私人物件之客戶端的空間需求。同樣地,我們加入了 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)經常需要發出數十到數百次授權檢查,才能提供單一一組搜尋結果。我們引入了對 Spanner 與 Leopard 請求的對沖,以避免偶發的緩慢操作拖慢整體使用者互動。請參閱 §3.2.7。
  • 熱點緩解對高可用性至關重要:某些工作負載會在 ACL 資料中造成熱點,足以壓垮底層資料庫伺服器。一種常見模式是針對某個物件的突發大量 ACL 檢查,而該物件被許多不同物件的 ACL 間接參照。具體實例來自上述的搜尋使用情境,其中搜尋中的文件間接共用某個大型社交群組或工作群組的 ACL;以及 Cloud 的使用情境,其中許多物件間接共用位於階層高處之同一物件的 ACL。Zanzibar 以分散式快取與鎖定表等通用機制處理大多數熱點,但我們發現仍需要針對特定使用情境進行最佳化。例如,我們加入了針對熱門物件預先擷取所有關係元組至快取的功能。我們也在有針對相同 ACL 資料的並行請求時,延後取消次要 ACL 檢查。請參閱 §3.2.5。
  • 效能隔離是防範行為異常之客戶端不可或缺的手段:即使採取了熱點緩解措施,非預期且有時並非刻意的客戶端行為,仍可能使我們的系統或其底層基礎設施過載。例子包括客戶端推出出乎意料地受歡迎的新功能,或以非預期的方式使用 Zanzibar。隨著時間推移,我們加入了隔離防護措施,以確保客戶端之間或同一客戶端的物件之間不會發生連鎖故障。這些防護措施包括細粒度的成本計算、配額與節流。請參閱 §3.2.6。

5Related Work

5相關研究

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 UU logged into workstation WW to access file server SS, SS would see requests authenticated as “WW for UU” rather than just UU. 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] 支援複合主體,可納入身分在通過分散式系統時被轉換的方式。例如,若使用者 UU 登入工作站 WW 以存取檔案伺服器 SS,SS 看到的請求將被驗證為「代表 UU 的 WW」,而非僅僅是 UU。這使得人們可以為使用者的電子郵件撰寫一條 ACL,使其只有該使用者能存取,且僅限於透過郵件伺服器存取時。Abadi 等人在 [11] 中討論了一種支援複合身分、以群組為基礎的 ACL 模型。他們的「blessings」概念類似於 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] 等公司商業提供的身分與存取管理(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 透過非同步複製提供最終全域一致性,並透過同步快取更新提供盡力而為的寫後讀一致性。相較之下,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,它能以較寬鬆的快取一致性處理更高的讀寫速率。然而,由於其可線性化性是以個別節點為單位,它並未為跨不同節點的更新提供外部一致性。它也不提供具有有界陳舊度的快照讀取。

6Conclusion

6結論

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 評估深層或廣泛巢狀的群組成員資格;Leopard 是一種專用索引,能以快照一致性高效率地計算集合運算。另一個例子是,它將分散式快取與一種對進行中請求去重複的機制結合。藉此,它緩解了熱點——在正規化、一致的儲存之上提供資料時,這是一個關鍵的正式環境問題。這些措施共同造就了一套可擴展至數兆條存取控制規則與每秒數百萬次授權請求的系統。

7Acknowledgments

7致謝

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。

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 提供的建設性回饋。

References

參考文獻

  1. Amazon Web Services Identity and Access Management. https://aws.amazon.com/iam/. Accessed: 2019-04-16.
  2. Azure Identity and Access Management. https://www.microsoft.com/en-us/cloud-platform/identity-management. Accessed: 2019-04-16.
  3. Cache stampede. https://en.wikipedia.org/wiki/Cache_stampede. Accessed: 2019-04-16.
  4. DCE 1.1: Authentication and Security Services. http://pubs.opengroup.org/onlinepubs/9668899. Accessed: 2019-04-16.
  5. Google Cloud Identity and Access Management. https://cloud.google.com/iam/. Accessed: 2019-04-16.
  6. Google Cloud Spanner. https://cloud.google.com/spanner/. Accessed: 2019-04-16.
  7. HP OpenVMS System Management Utilities Reference Manual. https://support.hpe.com/hpsc/doc/public/display?docId=emr_na-c04622366. Accessed: 2019-04-16.
  8. OpenVMS Guide to System Security. http://www.itec.suny.edu/scsys/vms/ovmsdoc073/V73/6346/6346pro_006.html#acl_details. Accessed: 2019-04-16.
  9. Unix Manual. https://www.bell-labs.com/usr/dmr/www/pdfs/man22.pdf. Accessed: 2019-04-16.
  10. Abadi, M., Burrows, M., Lampson, B., and Plotkin, G. A calculus for access control in distributed systems. ACM Trans. Program. Lang. Syst. 15, 4 (Sept. 1993), 706–734.
  11. Abadi, M., Burrows, M., Pucha, H., Sadovsky, A., Shankar, A., and Taly, A. Distributed authorization with distributed grammars. In Essays Dedicated to Pierpaolo Degano on Programming Languages with Applications to Biology and Security - Volume 9465 (New York, NY, USA, 2015), Springer-Verlag New York, Inc., pp. 10–26.
  12. Adya, A., Myers, D., Howell, J., Elson, J., Meek, C., Khemani, V., Fulger, S., Gu, P., Bhuvanagiri, L., Hunter, J., Peon, R., Kai, L., Shraer, A., Merchant, A., and Lev-Ari, K. Slicer: Auto-sharding for datacenter applications. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16) (Savannah, GA, 2016), USENIX Association, pp. 739–753.
  13. Bronson, N., Amsden, Z., Cabrera, G., Chakka, P., Dimov, P., Ding, H., Ferris, J., Giardullo, A., Kulkarni, S., Li, H., Marchukov, M., Petrov, D., Puzar, L., Song, Y. J., and Venkataramani, V. TAO: Facebook’s distributed data store for the social graph. In Proceedings of the 2013 USENIX Annual Technical Conference (2013), USENIX ATC ’13, pp. 49–60.
  14. Burrows, M. The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (Berkeley, CA, USA, 2006), OSDI ’06, USENIX Association, pp. 335–350.
  15. Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., Hsieh, W., Kanthak, S., Kogan, E., Li, H., Lloyd, A., Melnik, S., Mwaura, D., Nagle, D., Quinlan, S., Rao, R., Rolig, L., Saito, Y., Szymaniak, M., Taylor, C., Wang, R., and Woodford, D. Spanner: Google’s globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (2012), OSDI ’12, pp. 251–264.
  16. Dean, J., and Barroso, L. A. The tail at scale. Communications of the ACM 56, 2 (Feb. 2013), 74–80.
  17. Ferraiolo, D., and Kuhn, R. Role-based access control. In In 15th NIST-NCSC National Computer Security Conference (1992), pp. 554–563.
  18. Gifford, D. K. Information Storage in a Decentralized Computer System. PhD thesis, Stanford, CA, USA, 1981. AAI8124072.
  19. Hunt, P., Konar, M., Junqueira, F. P., and Reed, B. Zookeeper: Wait-free coordination for internet-scale systems. In Proceedings of the 2010 USENIX Annual Technical Conference (Berkeley, CA, USA, 2010), USENIX ATC ’10, USENIX Association.
  20. Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and Lewin, D. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (New York, NY, USA, 1997), STOC ’97, ACM, pp. 654–663.
  21. Kung, H. T., and Robinson, J. T. On optimistic methods for concurrency control. ACM Trans. Database Syst. 6, 2 (June 1981), 213–226.
  22. Lamport, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558–565.
  23. Saltzer, J. H. Protection and control of information sharing in Multics. In Proceedings of the Fourth ACM Symposium on Operating System Principles (New York, NY, USA, 1973), SOSP ’73, ACM.
  24. Wobber, E., Abadi, M., Burrows, M., and Lampson, B. Authentication in the Taos operating system. In Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles (New York, NY, USA, 1993), SOSP ’93, ACM, pp. 256–269.