paper:zanzibar#translation@zh-Hans

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 是一个用于存储和评估访问控制列表的全球性系统,它提供统一的数据模型和配置语言,用于表达来自 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.

许多在线交互都需要进行授权检查,以确认用户有权对某个数字对象执行某项操作。例如,基于 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,一个用于存储权限并基于所存储的权限执行授权检查的系统。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} 上评估,检查将观察到更新 A1,而该更新已将 Bob 从文件夹 ACL 中移除。在例 B 中,Bob 将看不到添加到文档中的新内容。若要 Bob 看到新内容,检查必须使用 ≥TB2\ge T_{B2}(即分配给该内容更新的时间戳)的 zookie 进行评估。由于 TB2>TB1T_{B2} > T_{B1},这样的检查也将观察到 ACL 更新 B1,而该更新已将 Bob 从 ACL 中移除。

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 还为客户端提供了用于读写关系元组、监听元组更新以及查看有效 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 而不是实际时间戳,是为了避免客户端选择任意时间戳,并为未来的扩展留有余地。

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 响应按时间戳升序包含从请求的起始时间戳到响应中所含心跳 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.

检查请求指定一个以 ⟨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 请求。它们跟踪(tail)变更日志,并以近乎实时的方式向客户端提供命名空间变更流。

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 数据执行多种离线功能。其中一项功能是在已知的快照时间戳上生成每个命名空间中关系元组的转储。另一项功能是对早于按命名空间配置的阈值的元组版本进行垃圾回收。

架构图。客户端向由相互连接的 aclservers 组成的 Zanzibar 服务集群发送 Check、Read、Expand 和 Write。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.

我们将每个命名空间的关系元组存储在一个单独的数据库中,其中每一行由主键 (shard ID, object ID, relation, user, commit timestamp) 标识。多个元组版本存储在不同的行中,这样我们就可以在垃圾回收窗口内的任意时间戳上评估检查和读取。主键的排序使我们能够查找给定对象 ID 或 (object ID, relation) 对的所有关系元组。

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 存储元组更新的历史记录。其主键为 (changelog shard ID, timestamp, unique update 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 都会收到一个提示,指出该时间戳上的数据是否需要进行区外(out-of-zone)读取,从而产生额外延迟。每台服务器都会跟踪默认陈旧度下的数据以及更新和更陈旧的数据发生此类区外读取的频率,并利用这些频率计算在每个陈旧度下任意给定数据片段可在本地获得的概率的二项比例置信区间。

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 服务系统被设计为持续摄取该流,并在对查询服务影响最小的情况下更新其各类倒排列表(posting list)。

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.

为处理“缓存踩踏”(cache stampede)问题 [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 服务器上限制每个 (object, client) 以及每个客户端的最大并发读取数。这确保了没有任何单个对象或客户端能够独占一台 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 请求峰值约为 4.2M QPS,Read 为 8.2M,Expand 为 760K,Write 为 25K。因此,读取数据的查询比写入数据的查询频繁两个数量级。

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 响应的延迟分布。符合设计意图的是,使用更频繁的 Safe 版本的 Check、Read 和 Expand 明显快于使用较少的 Recent 版本。Write 是所有 API 中使用频率最低的,也是最慢的,因为它们总是需要在 Spanner 服务器之间进行分布式协调。

延迟(毫秒),μ (σ)
API第 50 百分位第 95 百分位第 99 百分位
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。取而代之的是,我们从实时流量中抽取一小部分有效请求作为样本,随后用我们自己的探测器(prober)重放这些请求。重放请求时,我们将超时时间设置为长于可用性阈值。如果请求指定了 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,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 毫秒。我们发现,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 索引在中位数上处理 1.56M QPS,在第 99 百分位上处理 2.22M QPS。在同样的 7 天内,Leopard 服务器在中位数上的响应时间不到 150 微秒,在第 99 百分位上不到 1 毫秒。在这 7 天中,Leopard 的增量层在中位数上每秒写入约 500 次索引更新,在第 99 百分位上每秒写入约 1.5K 次更新。

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 看到的请求将被认证为“WW 代表 UU”,而不仅仅是 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。我们还感谢站点可靠性工程(Site Reliability Engineering)团队的前任和现任成员,包括 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 的支持。最后,我们感谢匿名审稿人以及我们的论文指导人(shepherd)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.