15 ms·

Zanzibar: Consistent, Global Authorization System

365 points by acjohnson55 7y ago

usaar333 7y ago
Excellent paper. As someone who has worked with filesystems and ACLs, but never touched Spanner before, I have some questions for any Googler who has played with Zanzibar. (in part because full-on client systems examples are limited) A check my understanding: Zanzibar is being optimized to handle zookies that are a bit stale (say 10s) old. In this case, the indexing systems (such as Leapord) can be used to vastly accelerate query evaluation. Questions I have (possibly missed explanations in the paper): 1. If I understand the zookie time (call it T) evaluation correctly, access questions for a given user are effectively "did a user have access to a document at or after T"? How in practice is this done with a check() API? The client/Zanzibar can certainly use the snapshots/indexes to give a True answer, but if the snapshot evaluation is false, is live data used (and if so by the client or Zanzibar itself?)? (e.g. how is the case handled of a user U just gaining access to a group G that is a member of some resource R?) 2. Related to #1, when is a user actually guaranteed to lose access to a document (at a version they previously had access to?) E.g. if a user has access to document D via group G and user is evicted from G, the protocol seems to inherently allow user to forever access D unless D is updated. In practice, is there some system (or application control) that will eventually block U from accessing D? 3. Is check latency going to be very high for documents that are being modified in real time (so zookie time is approximately now or close to now) that have complex group structures? (e.g. a document nested 6 levels deep in a folder where I have access to the folder via a group)? That is, there's nothing Zanzibar can do but "pointer chase", resulting in a large number of serial ACL checks? 4. How do clients consistently update ACLs alongside their "reverse edges"? For instance, the Zanzibar API allows me to view the members of a group (READ), but how do I consistently view which groups a user is a member of? (Leapord can cache this, but I'm not sure if this is available to clients and regardless it doesn't seem to be able to answer the question for "now" - only for a time earlier than indexed time). Or for a more simple example, if I drag a document into a folder, how is the Zanzibar entry that D is a child of F made consistent with F's views of its children? E.g. can you do a distributed transaction with ACL changes and client data stored in spanner? 5. It looks like the Watch API is effectively pushing updates whenever the READ(obj) would change, not the EXPAND(object). Is this correct? How are EXPAND() changes tracked by clients? Is this even possible? (e.g. if G is a member of some resource R and U is added to G, how can a client determine U now has access to R?)
- ruomingpang 7y ago
  Excellent questions. We have encountered all of them in practice and have solutions for most of them, e.g., (4) requires an ACL-aware search index. Unfortunately we don't have enough space to explain them in the paper. Please consider coming to Usenix. :-)
- sa46 7y ago
  Used to be a Googler and worked on an ACL model built on top of Zanzibar. I didn't work directly on Zanzibar so listen to ruomingpang over me. > 3. There's nothing Zanzibar can do but "pointer chase", resulting in a large number of serial ACL checks? Zanzibar enforced a max depth and would fail if the pointer-chasing traversed too deeply. Zanzibar would also fail if it traversed too many nodes. > 4. How do clients consistently update ACLs alongside their "reverse edges"? One of the recommended solutions was to store your full ACL (which includes a Zookie) in the same Spanner row of whatever it protected. So, if your ACL is for books, you might have: CREATE TABLE books ( book SERIAL PRIMARY KEY acl ZanzibarAcl ); Alternately, you could opt to only store the current zookie instead of the full ACL. Then the check becomes: 1. Fetch Zookie from Spanner 2. Call Zanzibar.Check with the zookie > but how do I consistently view which groups a user is a member of? I remember this as a large source of pain to implement. Zanzibar didn't support this use-case directly. As rpang mentioned in a sibling comment, you need an ACL-aware index. Essentially, the algorithm is: 1. Call Zanzibar.Check on all groups the user might be a part of. There's a bunch of clever tricks you can use to prune the search space that I don't know the details of.
cryptonector 7y ago
This reminds me I need to get my authz paper published, and now sooner than later... I've built an authz system that is built around labeled security and RBAC concepts. Basically: - resource owners label resources - the labels are really names for ACLs in a directory - the ACL entries grant roles to users/groups - roles are sets of verbs There are unlimited verbs, and unlimited roles. There are no negative ACL entries, which means they are sets -- entry order doesn't matter. The whole thing resembles NTFS/ZFS ACLs, but without negative ACL entries, and with indirection via naming the ACLs. ACL data gets summarized and converted to a form that makes access control evaluation fast to compute. This data then gets distributed to where it's needed. The API consists mainly of: - check(subject, verb, label) -> boolean - query(subject, verb, label) -> list of grants (supports wildcarding) - list(subject) -> list of grants - grant(user-or-group, role, label) - revoke(user-or-group, role, label) - interfaces for creating verbs, roles, and labels, and adding/removing verbs from roles. Note that access granting/revocation is done using roles, while access checking is done using verbs. What's really cool about this system is that because it is simple it is composable. If you model certain attributes of subjects (e.g., whether they are on-premises, remote, in a public cloud, ...) as special subjects, then you can compose multiple check() calls to get ABAC, CORS/on-behalf-of/impersonation, MAC and DAC, SAML/OAuth-style authorization, and more. When I started all I wanted was a labeled security system. It was only later that compositions came up. Because we built a summarized authz data distribution system first, all the systems that have data will continue to have it even in an outage -- an outage becomes just longer than usual update latencies. check() performance is very fast, on the order of 10us to 15us, with no global locks, and this could probably be made faster. check() essentially look's up the subject's group memberships (with the group transitive closure expanded) and the {verb, label}'s direct grantees, and checks if the intersection is empty (access denied) or not (access granted). In the common case (the grantee list is short) this requires N log M comparisons, and in the worst case (the two lists are comparable in size) it requires O(N) comparisons. This means check() performance is naturally very fast when using local authz data. Using a REST service adds latency, naturally, but the REST service itself can be backended with summarized authz data, making it fast. Using local data makes the system reliable and reliably fast. query() does more work, but essentially amounts to a union of the subject's direct grants and a join of the subject's groups and the groups' direct grants. special entities like "ANYONE" (akin to Authenticated Users in Windows) and "ANONYMOUS" also exist, naturally, and can be granted. These are treated like groups in the summarized authz data. We also have a "SELF" special entity which allows one to express grants to any subject who is the same as the one running the process that calls check().
eximius 7y ago
Semi-off topic: What is the latest and greatest in authorization mechanisms lately? I like capability-based at on OS level, but sadly I'm not doing anything that interesting. For things like webapps, is there anything better than ACLs or Role-based. Or at least any literature talking about them? Probably overkill for the application I work on, but it'd be nice to take inspiration from best practices.
sb8244 7y ago
How would you deal with questions like "provide all content accessible to a user" in a system like this? Would you watch and replicate to your own database?
- ruomingpang 7y ago
  You will need an ACL-aware index, which is one of the main use cases of Zanzibar.
  - sb8244 7y ago
    Do you get the ACL from Zanzibar to your data store using a watch? I'm just confirming that replication is the best strategy and there's not some magic that I'm not aware of
zeeed 7y ago
I got stuck on the first line in the abstract: > Determining whether online users are authorized to access digital objects is central to preserving privacy. Can someone dissect that sentence and explain why that is? I honestly fail to make the connection.
- Dowwie 7y ago
  Replace "digital object" with "a PDF of your checking account transactions for 2018". You want to control who can do what with that PDF. Your privacy is at stake.
  - zeeed 7y ago
    Sure, that’s privacy in the sense of “no one can access my stuff, unauthorized”. I struggled with the sentence cause, at the same time, creating one global centralized authentication source creates the opposite of privacy in the sense of anonymity. Certainly OT wrt the actual content of the work...
    - BitPolice 7y ago
      I may be misunderstanding the issue you're pointing out here... but I note that while the paper/sentence talks about "authorization" you're talking about centralized "authentication." As an authorization system Zanzibar focuses on: can agent A (identified through some means) perform action X on object Y. It isn't about deciding whether an arbitrary actor is agent A but proscribing what actions agent A can perform against the universe of all possible objects (which likewise are referenced abstractly and not stored within the system itself). The knowledge that A could do X on Y is information that might be disclosed (and thus entails some privacy risk)... but inherently doesn't reveal: anything about the identity of A; whether A has ever done X; or what Y's contents are or what it represents. On the other hand, perhaps you mean that because membership in sets of users is also stored within it (via a sort of "is member of" permission) you can use that to de-anonymize who a given actor is. This might work but it assumes you can uniquely derive which agent from a set of abstract agents represents that individual and that you extrinsically something about the person being the only person in this specific set of sets.
ubercow 7y ago
Semi-off topic but is there a curated "best of" list for systems papers like this that anyone knows about, from Google or otherwise?
- bretthardin 7y ago
  If you find this, please let me know.
GMLOOKO 7y ago
A
iampims 7y ago
“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” Impressive!
- the-rc 7y ago
  "This caching, along with aggressive pooling of read requests, allows Zanzibar to issue only 20 million read RPCs per second to Spanner." ("Only") I'm surprised by all the numbers they give out: latency, regions, operation counts, even servers. The typical Google paper omits numbers on the Y axis of its most interesting graphs. Or it says "more than a billion", which makes people think "2B", when the actual number might be closer to 10B or even higher.
  - justicezyx 7y ago
    Kind of needed in the cloud war where many actually question if the mysterious Google supermacy in global infrastructure is really true.
    - wbl 7y ago
      Throwing servers at the problem is less impressive then thinking very hard and solving it with less.
      - vajaya 7y ago
        there's physical limit as what algorithms and tricks can do. Their numbers are incredible though.
        wbl 7y ago
        Which is exactly my point: no one cares about the absolute number each cloud has. They care about the capacities.
nippoo 7y ago
As a side-note: 95th percentile latency statistics are pretty meaningless at this scale. With a million requests per second, a 95th percentile latency of 10ms still means that 50,000 requests per second are slower than that.
- jsty 7y ago
  They do give p99 latencies in the table on page 10
  - ktta 7y ago
    99 - < 20ms 99.9 - < 90ms That is amazing.
    - alexeldeib 7y ago
      This is absolutely incredible. Since we saw login with Apple yesterday, makes me wonder if any of the other big companies can compete with this. Curious about Facebook/Netflix/Amazon. Netflix seems zippy, but I've never looked at the request timings, which could differ pretty dramatically from UI load times. I imagine Google also dwarfs their login scale. Would be interesting to see numbers capturing full load time from clicking the login UI to successful redirect (or however you would measure this without including the time of the page load post-login).
      - lclarkmichalek 7y ago
        This isn't a login service, this is an ACL service. Related space, but different concerns. You wouldn't send a user's password here to find out if it's correct (authentication), you'd use this to figure out if a user can do something once you know who they are (authorization) :) Also, generating the login page etc is often more expensive than the actual 'validate the username and password'. Getting to the server is also going to dwarf these latencies; you probably don't store all your passwords in PoPs, so you need to make the full trek to your local Google datacentre to complete a login :)
colesantiago 7y ago
I love reading about Google's systems, but I wish I could work on those problems at scale, that is my dream really. I wonder what more systems Google has that we don't know about. I know Borg has become what we know as k8s but surely there must be more things that Google has made internally that are not open source. Curious about this and would like to know more about it from anyone in the trenches at Google.
- Boulth 7y ago
  On the other hand Google engineers are vendor-locked-in using Google specific tech one way or another.
  - draw_down 7y ago
    Come on.
  - lopsidedBrain 7y ago
    Um, not really. Care to elaborate? If something is available open-sourced we're typically free to use it, as long as we are abiding by the license conditions.
  - jchw 7y ago
    Not strictly true. Most software would probably require at least some modifications to run internally but as far as I know there’s no policy preventing open source software in production, quite the opposite. For example, here’s some information about memcache: https://www.quora.com/Does-Google-use-memcached-or-does-it-use-a-homegrown-alternative https://www.quora.com/Does-Google-use-memcached-or-does-it-u... There’s more, but if I can’t find a reference to them on Google Search I’ll assume its not in my place to discuss it publicly. Using protobufs as a base layer may seem like lock-in, but it very much is the opposite. Protobufs are surprisingly simple and maybe even elegant once you get past the ugly parts, but most importantly it decouples software from arbitrary protocols and makes it much easier to deal with changing implementations. (Not to mention the potential for rich backwards and forwards compatibility.)
  - shereadsthenews 7y ago
sonnyblarney 7y ago
What's interesting to me here is not the ACL thing, it's how in a way 'straight forward' this all seems to be. It's the large architecture of a fairly basic system, done I supposed 'professionally'. I'm curious to know how this works organizationally. What kind of architects involved because this system would have to interact with any number of others, so how do they do requirements gathering? Do they just 'have experience' and 'know what needs to be done' or is this something socialized with 'all the other teams'? And how many chefs in that kitchen once the preparation starts? Because there's clearly a lot of pieces. Do they have just a few folks wire it out and then check with others? Who reviews designs for such a big thing? Or was all of this developed organically, over time?
- usaar333 7y ago
  The system is actually pretty complicated and nonobvious once you consider its caching layers, heavy reliance on spanner, assumption that ACL read times can be stale, and the various assumptions and limitations in the namespace controls. The underlying model of role based access control (and viewing groups as just other resources with ACLs) is already well known.
- delroth 7y ago
  Zanzibar is basically the brainchild of a Bigtable Tech Lead + a Principal Engineer from Google's security and privacy team [1]. This led to a very sound and robust original design for the system. But it also greatly evolved over time as the system scaled up and got new clients with new requirements and new workloads. [1] https://twitter.com/LeaKissner/status/1136626971566149633 https://twitter.com/LeaKissner/status/1136626971566149633
- shereadsthenews 7y ago
  That’s how you design at this scale: keep it simple, don’t be a jackass. If the result looks complicated from the outside, you blew it.
- the-rc 7y ago
  Especially at Google, you first see the same problem appearing and getting solved in multiple products, then someone tries to come up with a more generic solution that works for most projects and, just as importantly, can serve more traffic than the existing solutions. Having to rewrite things on a regular basis because of growth is painful, but can also be a blessing in disguise. Who that someone is who works on the generic solution, can vary. Sometimes it's one or more of the teams already mentioned. Sometimes, like in this case, it's someone with expertise in related areas that takes the initiative. And a project of this scope invariably gets reviewed on a regular basis by senior engineers, all the way to Urs (who leads all of technical infrastructure). Shared technologies require not just headcount to design and write the systems, but also to operate them (by SREs when they're large enough), so you need to get upper management involved as well.
argd678 7y ago
The distinguishing feature I see compared to other systems is the ACL ordering and consistency, which is indeed difficult to do at scale. Looks like Spanner is doing most the heavy lifting, great use case for the database.
- cryptonector 7y ago
  If you don't have negative ACL entries then ordering is not important.
  - usaar333 7y ago
    GP means ordering with respect to time for snapshot reads, which is essential for correctness. (You might be thinking of ordering ACEs in the ACL which isn't even a concept in Zanzibar)
- usaar333 7y ago
  Well even more broadly it is how generalizable it is, while still providing ordering guarantees (though not necessarily perfect ones.. see my long sibling post) Using Windows style ACEs for ACLs is also perfectly scalable and consistent, (and more performant) so long as users don't end up in too many groups and objects only inherit ACLs from objects on the same shard. It's just no where as generalizable as Zanzibar which allows much more complex dependencies. There's always tradeoffs! But this is the best system I've seen for the general ACL evaluation against non recently updated objects.
  - argd678 7y ago
    I’ve been part of similarly generalized ACL systems and it’s pretty straightforward and very similar to Zanzibar. Though we didn’t need n ACLs and could assume the list wasn’t too long, so we didn’t need a tree. If we did, then we’d have ended up in a similar place as Zanzibar I believe, there are a limited number of ways to solve that problem.
stingraycharles 7y ago
Am I alone in thinking that 99.999% measured availability for a service so completely in the critical path for almost everything is relatively low? Phrased another way, when it is not availability, do end users experience service disruption, and if not, how is that mitigated?
- xyzzy_plugh 7y ago
  You might not be alone but five nines is pretty good. I seen many internal facing teams across many companies have SLOs of four nines or less. Five is pretty rare.
- gtirloni 7y ago
  I think you might be alone. 5.26 minutes of down time per year is beyond excellent for any moderately complex system.
  - cheez 7y ago
    I have a simple system that depends on another system and I can't keep it up for a week without 15 minutews downtime
- bradleyjg 7y ago
  Overall uptime isn't the only stat that matters here, the distribution of downtime matters too. One 15 minute outage in three years is a lot worse than 900 1 second outages over that same time period. One second blips are a part of the web, we click refresh and move on--not even knowing who's fault it was.
- lclarkmichalek 7y ago
  It kinda depends what availability means? That .001% unavailability might be degraded service, might be .001% of clients having a bad time across the entire year, might be 'acts of god' (i.e. broken CPUs and the like). This kind of service is also usually fairly low down on the stack, and higher level applications can usually degrade gracefully. If they couldn't, complex applications such as Google would fail to operate; there's always _something_ broken.
wallflower 7y ago
> There's also a story behind that project name. That is not the original project name. The original project name was force-removed by my SVP. Once my hands are free again, I can explain https://mobile.twitter.com/LeaKissner/status/1136631437514272768 https://mobile.twitter.com/LeaKissner/status/113663143751427...
- delroth 7y ago
  https://mobile.twitter.com/LeaKissner/status/1136691523104280576 https://mobile.twitter.com/LeaKissner/status/113669152310428...
- koboll 7y ago
  Yeah, that's kinda understandable. Although I'm not sure how the current name fits the project any better.
  - Iv 7y ago
    It sounds pretty appropriate. This is another SF reference "Stand on Zanzibar", one of the earliest inspirations for cyberpunk, in which we are routinely remembered that all of humanity would be able to stand on the small island of Zanzibar, but that growth is problematic. https://en.wikipedia.org/wiki/Stand_on_Zanzibar https://en.wikipedia.org/wiki/Stand_on_Zanzibar
    - kjeetgill 7y ago
      For others that were confused as I was: SF here is Science Fiction not San Francisco.
- pronoiac 7y ago
  https://twitter.com/LeaKissner/status/1136691523104280576 https://twitter.com/LeaKissner/status/1136691523104280576 > Zanzibar was not the original name of the system. It was originally called "Spice". I have read Dune more times than I can count and an access control system is designed so that people can safely share things, so the project motto was "the shares must flow"
victor106 7y ago
What do other large (non-google scale) to medium companies use for authorization? Can anyone recommend open source (preferably) or close source products?
- MrSaints 7y ago
  A pretty simple, and configurable one: https://github.com/casbin/casbin https://github.com/casbin/casbin
- ucarion 7y ago
  https://github.com/ory/ladon https://github.com/ory/ladon is an option. Essentially, it imposes a lot of the fine-grained access control model on you, but then it's up to you to implement the actual database/business-logic layer [1] as well as the API layer to actually expose the service. [1] You do so by implementing this interface: https://github.com/ory/ladon/blob/master/warden.go https://github.com/ory/ladon/blob/master/warden.go
- jamafu 7y ago
  We use Keycloak at our place and are really happy with it. Website: https://www.keycloak.org/ https://www.keycloak.org/ GitHub: https://github.com/keycloak/keycloak https://github.com/keycloak/keycloak
  - dusty_mc_dusty 7y ago
    Jup, it's quite nice!
- perlgeek 7y ago
  There's also Open Policy Agent (OPA) https://github.com/open-policy-agent/opa https://github.com/open-policy-agent/opa
- gen220 7y ago
  We use LDAP for managing group memberships (i.e. person x is a member of `engineering` and `eng_team_y`; only members of `eng_team_y` can change the deployment status of service Z). We then define ACLs for these groups. IDK how they are enforced, but they're visible/malleable via Ansible recipes, such that the process of adding permissions for your group (or user) involves submitting a diff to said Ansible recipe and getting approval from an SRE. In practice, we use Kerberos to obtain/distribute authorization tokens, which live for less than 24 hours. The authorization-value of these tokens is determined by the LDAP affinities of the bearer. If everything is configured correctly (which it always is, until you need new permissions / switch teams), all you have to do is auth with kerberos at the beginning of each day. We have ~200 engineers.
malicioususer11 7y ago
i wish google could authenticate my own sense of self worth, because then id save a lot on Therapy. :)
1023bytes 7y ago
Why is it called Zanzibar though? I'm kind of intrigued
- pronoiac 7y ago
  There's another thread about naming it - https://twitter.com/LeaKissner/status/1136691523104280576 https://twitter.com/LeaKissner/status/1136691523104280576 The original name was Spice, which was nixed from a higher-up; they went to Zanzibar, one of the Spice Islands.
  - ddebernardy 7y ago
    Odd. Zanzibar is off the coast of Tanzania in East Africa. The Spice Islands (the Moluccas) are in Eastern Indonesia.
    - pronoiac 7y ago
      I was going by the twitter thread, but I looked and found this in Wikipedia: > the Zanzibar Archipelago, together with Tanzania's Mafia Island, are sometimes referred to locally as the "Spice Islands" (a term borrowed from the Maluku Islands of Indonesia). https://en.wikipedia.org/wiki/Zanzibar https://en.wikipedia.org/wiki/Zanzibar
deleted 7y ago
[deleted]
demarq 7y ago
Not sure how I feel about adopting a countries name for a project. Or more to the point I'm not sure how I would feel if every time I searched my countries name on the web this Google project appears rather than my actual country. i.e Zanzibar is a national identity not just a "spice" island
- ocdtrekkie 7y ago
  Countries who have the Amazon rainforest within their borders are still a little annoyed about the company. https://mashable.com/article/amazon-domain-name-icann-approved/ https://mashable.com/article/amazon-domain-name-icann-approv...
- NameOfTeam 7y ago
  To be clear, Zanzibar is neither a country nor a national identity. It’s a semi-autonomous region of Tanzania.

365 points by acjohnson55 7y ago

Excellent paper. As someone who has worked with filesystems and ACLs, but never touched Spanner before, I have some questions for any Googler who has played with Zanzibar. (in part because full-on client systems examples are limited) A check my understanding: Zanzibar is being optimized to handle zookies that are a bit stale (say 10s) old. In this case, the indexing systems (such as Leapord) can be used to vastly accelerate query evaluation. Questions I have (possibly missed explanations in the paper): 1. If I understand the zookie time (call it T) evaluation correctly, access questions for a given user are effectively "did a user have access to a document at or after T"? How in practice is this done with a check() API? The client/Zanzibar can certainly use the snapshots/indexes to give a True answer, but if the snapshot evaluation is false, is live data used (and if so by the client or Zanzibar itself?)? (e.g. how is the case handled of a user U just gaining access to a group G that is a member of some resource R?) 2. Related to #1, when is a user actually guaranteed to lose access to a document (at a version they previously had access to?) E.g. if a user has access to document D via group G and user is evicted from G, the protocol seems to inherently allow user to forever access D unless D is updated. In practice, is there some system (or application control) that will eventually block U from accessing D? 3. Is check latency going to be very high for documents that are being modified in real time (so zookie time is approximately now or close to now) that have complex group structures? (e.g. a document nested 6 levels deep in a folder where I have access to the folder via a group)? That is, there's nothing Zanzibar can do but "pointer chase", resulting in a large number of serial ACL checks? 4. How do clients consistently update ACLs alongside their "reverse edges"? For instance, the Zanzibar API allows me to view the members of a group (READ), but how do I consistently view which groups a user is a member of? (Leapord can cache this, but I'm not sure if this is available to clients and regardless it doesn't seem to be able to answer the question for "now" - only for a time earlier than indexed time). Or for a more simple example, if I drag a document into a folder, how is the Zanzibar entry that D is a child of F made consistent with F's views of its children? E.g. can you do a distributed transaction with ACL changes and client data stored in spanner? 5. It looks like the Watch API is effectively pushing updates whenever the READ(obj) would change, not the EXPAND(object). Is this correct? How are EXPAND() changes tracked by clients? Is this even possible? (e.g. if G is a member of some resource R and U is added to G, how can a client determine U now has access to R?)

ruomingpang 7y ago
Excellent questions. We have encountered all of them in practice and have solutions for most of them, e.g., (4) requires an ACL-aware search index. Unfortunately we don't have enough space to explain them in the paper. Please consider coming to Usenix. :-)
sa46 7y ago
Used to be a Googler and worked on an ACL model built on top of Zanzibar. I didn't work directly on Zanzibar so listen to ruomingpang over me. > 3. There's nothing Zanzibar can do but "pointer chase", resulting in a large number of serial ACL checks? Zanzibar enforced a max depth and would fail if the pointer-chasing traversed too deeply. Zanzibar would also fail if it traversed too many nodes. > 4. How do clients consistently update ACLs alongside their "reverse edges"? One of the recommended solutions was to store your full ACL (which includes a Zookie) in the same Spanner row of whatever it protected. So, if your ACL is for books, you might have: CREATE TABLE books ( book SERIAL PRIMARY KEY acl ZanzibarAcl ); Alternately, you could opt to only store the current zookie instead of the full ACL. Then the check becomes: 1. Fetch Zookie from Spanner 2. Call Zanzibar.Check with the zookie > but how do I consistently view which groups a user is a member of? I remember this as a large source of pain to implement. Zanzibar didn't support this use-case directly. As rpang mentioned in a sibling comment, you need an ACL-aware index. Essentially, the algorithm is: 1. Call Zanzibar.Check on all groups the user might be a part of. There's a bunch of clever tricks you can use to prune the search space that I don't know the details of.

cryptonector 7y ago

This reminds me I need to get my authz paper published, and now sooner than later... I've built an authz system that is built around labeled security and RBAC concepts. Basically: - resource owners label resources - the labels are really names for ACLs in a directory - the ACL entries grant roles to users/groups - roles are sets of verbs There are unlimited verbs, and unlimited roles. There are no negative ACL entries, which means they are sets -- entry order doesn't matter. The whole thing resembles NTFS/ZFS ACLs, but without negative ACL entries, and with indirection via naming the ACLs. ACL data gets summarized and converted to a form that makes access control evaluation fast to compute. This data then gets distributed to where it's needed. The API consists mainly of: - check(subject, verb, label) -> boolean - query(subject, verb, label) -> list of grants (supports wildcarding) - list(subject) -> list of grants - grant(user-or-group, role, label) - revoke(user-or-group, role, label) - interfaces for creating verbs, roles, and labels, and adding/removing verbs from roles. Note that access granting/revocation is done using roles, while access checking is done using verbs. What's really cool about this system is that because it is simple it is composable. If you model certain attributes of subjects (e.g., whether they are on-premises, remote, in a public cloud, ...) as special subjects, then you can compose multiple check() calls to get ABAC, CORS/on-behalf-of/impersonation, MAC and DAC, SAML/OAuth-style authorization, and more. When I started all I wanted was a labeled security system. It was only later that compositions came up. Because we built a summarized authz data distribution system first, all the systems that have data will continue to have it even in an outage -- an outage becomes just longer than usual update latencies. check() performance is very fast, on the order of 10us to 15us, with no global locks, and this could probably be made faster. check() essentially look's up the subject's group memberships (with the group transitive closure expanded) and the {verb, label}'s direct grantees, and checks if the intersection is empty (access denied) or not (access granted). In the common case (the grantee list is short) this requires N log M comparisons, and in the worst case (the two lists are comparable in size) it requires O(N) comparisons. This means check() performance is naturally very fast when using local authz data. Using a REST service adds latency, naturally, but the REST service itself can be backended with summarized authz data, making it fast. Using local data makes the system reliable and reliably fast. query() does more work, but essentially amounts to a union of the subject's direct grants and a join of the subject's groups and the groups' direct grants. special entities like "ANYONE" (akin to Authenticated Users in Windows) and "ANONYMOUS" also exist, naturally, and can be granted. These are treated like groups in the summarized authz data. We also have a "SELF" special entity which allows one to express grants to any subject who is the same as the one running the process that calls check().

eximius 7y ago

Semi-off topic: What is the latest and greatest in authorization mechanisms lately? I like capability-based at on OS level, but sadly I'm not doing anything that interesting. For things like webapps, is there anything better than ACLs or Role-based. Or at least any literature talking about them? Probably overkill for the application I work on, but it'd be nice to take inspiration from best practices.

sb8244 7y ago

How would you deal with questions like "provide all content accessible to a user" in a system like this? Would you watch and replicate to your own database?

ruomingpang 7y ago
You will need an ACL-aware index, which is one of the main use cases of Zanzibar.
- sb8244 7y ago
  Do you get the ACL from Zanzibar to your data store using a watch? I'm just confirming that replication is the best strategy and there's not some magic that I'm not aware of

zeeed 7y ago

I got stuck on the first line in the abstract: > Determining whether online users are authorized to access digital objects is central to preserving privacy. Can someone dissect that sentence and explain why that is? I honestly fail to make the connection.

Dowwie 7y ago
Replace "digital object" with "a PDF of your checking account transactions for 2018". You want to control who can do what with that PDF. Your privacy is at stake.
- zeeed 7y ago
  Sure, that’s privacy in the sense of “no one can access my stuff, unauthorized”. I struggled with the sentence cause, at the same time, creating one global centralized authentication source creates the opposite of privacy in the sense of anonymity. Certainly OT wrt the actual content of the work...
  - BitPolice 7y ago
    I may be misunderstanding the issue you're pointing out here... but I note that while the paper/sentence talks about "authorization" you're talking about centralized "authentication." As an authorization system Zanzibar focuses on: can agent A (identified through some means) perform action X on object Y. It isn't about deciding whether an arbitrary actor is agent A but proscribing what actions agent A can perform against the universe of all possible objects (which likewise are referenced abstractly and not stored within the system itself). The knowledge that A could do X on Y is information that might be disclosed (and thus entails some privacy risk)... but inherently doesn't reveal: anything about the identity of A; whether A has ever done X; or what Y's contents are or what it represents. On the other hand, perhaps you mean that because membership in sets of users is also stored within it (via a sort of "is member of" permission) you can use that to de-anonymize who a given actor is. This might work but it assumes you can uniquely derive which agent from a set of abstract agents represents that individual and that you extrinsically something about the person being the only person in this specific set of sets.

ubercow 7y ago

Semi-off topic but is there a curated "best of" list for systems papers like this that anyone knows about, from Google or otherwise?

bretthardin 7y ago
If you find this, please let me know.

GMLOOKO 7y ago

iampims 7y ago

“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” Impressive!

the-rc 7y ago
"This caching, along with aggressive pooling of read requests, allows Zanzibar to issue only 20 million read RPCs per second to Spanner." ("Only") I'm surprised by all the numbers they give out: latency, regions, operation counts, even servers. The typical Google paper omits numbers on the Y axis of its most interesting graphs. Or it says "more than a billion", which makes people think "2B", when the actual number might be closer to 10B or even higher.
- justicezyx 7y ago
  Kind of needed in the cloud war where many actually question if the mysterious Google supermacy in global infrastructure is really true.
  - wbl 7y ago
    Throwing servers at the problem is less impressive then thinking very hard and solving it with less.
    - vajaya 7y ago
      there's physical limit as what algorithms and tricks can do. Their numbers are incredible though.
      - wbl 7y ago
        Which is exactly my point: no one cares about the absolute number each cloud has. They care about the capacities.

nippoo 7y ago

As a side-note: 95th percentile latency statistics are pretty meaningless at this scale. With a million requests per second, a 95th percentile latency of 10ms still means that 50,000 requests per second are slower than that.

jsty 7y ago
They do give p99 latencies in the table on page 10
- ktta 7y ago
  99 - < 20ms 99.9 - < 90ms That is amazing.
  - alexeldeib 7y ago
    This is absolutely incredible. Since we saw login with Apple yesterday, makes me wonder if any of the other big companies can compete with this. Curious about Facebook/Netflix/Amazon. Netflix seems zippy, but I've never looked at the request timings, which could differ pretty dramatically from UI load times. I imagine Google also dwarfs their login scale. Would be interesting to see numbers capturing full load time from clicking the login UI to successful redirect (or however you would measure this without including the time of the page load post-login).
    - lclarkmichalek 7y ago
      This isn't a login service, this is an ACL service. Related space, but different concerns. You wouldn't send a user's password here to find out if it's correct (authentication), you'd use this to figure out if a user can do something once you know who they are (authorization) :) Also, generating the login page etc is often more expensive than the actual 'validate the username and password'. Getting to the server is also going to dwarf these latencies; you probably don't store all your passwords in PoPs, so you need to make the full trek to your local Google datacentre to complete a login :)

colesantiago 7y ago

I love reading about Google's systems, but I wish I could work on those problems at scale, that is my dream really. I wonder what more systems Google has that we don't know about. I know Borg has become what we know as k8s but surely there must be more things that Google has made internally that are not open source. Curious about this and would like to know more about it from anyone in the trenches at Google.

Boulth 7y ago
On the other hand Google engineers are vendor-locked-in using Google specific tech one way or another.
- draw_down 7y ago
  Come on.
- lopsidedBrain 7y ago
  Um, not really. Care to elaborate? If something is available open-sourced we're typically free to use it, as long as we are abiding by the license conditions.
- jchw 7y ago
  Not strictly true. Most software would probably require at least some modifications to run internally but as far as I know there’s no policy preventing open source software in production, quite the opposite. For example, here’s some information about memcache: https://www.quora.com/Does-Google-use-memcached-or-does-it-use-a-homegrown-alternative https://www.quora.com/Does-Google-use-memcached-or-does-it-u... There’s more, but if I can’t find a reference to them on Google Search I’ll assume its not in my place to discuss it publicly. Using protobufs as a base layer may seem like lock-in, but it very much is the opposite. Protobufs are surprisingly simple and maybe even elegant once you get past the ugly parts, but most importantly it decouples software from arbitrary protocols and makes it much easier to deal with changing implementations. (Not to mention the potential for rich backwards and forwards compatibility.)
- shereadsthenews 7y ago

sonnyblarney 7y ago

What's interesting to me here is not the ACL thing, it's how in a way 'straight forward' this all seems to be. It's the large architecture of a fairly basic system, done I supposed 'professionally'. I'm curious to know how this works organizationally. What kind of architects involved because this system would have to interact with any number of others, so how do they do requirements gathering? Do they just 'have experience' and 'know what needs to be done' or is this something socialized with 'all the other teams'? And how many chefs in that kitchen once the preparation starts? Because there's clearly a lot of pieces. Do they have just a few folks wire it out and then check with others? Who reviews designs for such a big thing? Or was all of this developed organically, over time?

usaar333 7y ago
The system is actually pretty complicated and nonobvious once you consider its caching layers, heavy reliance on spanner, assumption that ACL read times can be stale, and the various assumptions and limitations in the namespace controls. The underlying model of role based access control (and viewing groups as just other resources with ACLs) is already well known.
delroth 7y ago
Zanzibar is basically the brainchild of a Bigtable Tech Lead + a Principal Engineer from Google's security and privacy team [1]. This led to a very sound and robust original design for the system. But it also greatly evolved over time as the system scaled up and got new clients with new requirements and new workloads. [1] https://twitter.com/LeaKissner/status/1136626971566149633 https://twitter.com/LeaKissner/status/1136626971566149633
shereadsthenews 7y ago
That’s how you design at this scale: keep it simple, don’t be a jackass. If the result looks complicated from the outside, you blew it.
the-rc 7y ago
Especially at Google, you first see the same problem appearing and getting solved in multiple products, then someone tries to come up with a more generic solution that works for most projects and, just as importantly, can serve more traffic than the existing solutions. Having to rewrite things on a regular basis because of growth is painful, but can also be a blessing in disguise. Who that someone is who works on the generic solution, can vary. Sometimes it's one or more of the teams already mentioned. Sometimes, like in this case, it's someone with expertise in related areas that takes the initiative. And a project of this scope invariably gets reviewed on a regular basis by senior engineers, all the way to Urs (who leads all of technical infrastructure). Shared technologies require not just headcount to design and write the systems, but also to operate them (by SREs when they're large enough), so you need to get upper management involved as well.

argd678 7y ago

The distinguishing feature I see compared to other systems is the ACL ordering and consistency, which is indeed difficult to do at scale. Looks like Spanner is doing most the heavy lifting, great use case for the database.

cryptonector 7y ago
If you don't have negative ACL entries then ordering is not important.
- usaar333 7y ago
  GP means ordering with respect to time for snapshot reads, which is essential for correctness. (You might be thinking of ordering ACEs in the ACL which isn't even a concept in Zanzibar)
usaar333 7y ago
Well even more broadly it is how generalizable it is, while still providing ordering guarantees (though not necessarily perfect ones.. see my long sibling post) Using Windows style ACEs for ACLs is also perfectly scalable and consistent, (and more performant) so long as users don't end up in too many groups and objects only inherit ACLs from objects on the same shard. It's just no where as generalizable as Zanzibar which allows much more complex dependencies. There's always tradeoffs! But this is the best system I've seen for the general ACL evaluation against non recently updated objects.
- argd678 7y ago
  I’ve been part of similarly generalized ACL systems and it’s pretty straightforward and very similar to Zanzibar. Though we didn’t need n ACLs and could assume the list wasn’t too long, so we didn’t need a tree. If we did, then we’d have ended up in a similar place as Zanzibar I believe, there are a limited number of ways to solve that problem.

stingraycharles 7y ago

Am I alone in thinking that 99.999% measured availability for a service so completely in the critical path for almost everything is relatively low? Phrased another way, when it is not availability, do end users experience service disruption, and if not, how is that mitigated?

xyzzy_plugh 7y ago
You might not be alone but five nines is pretty good. I seen many internal facing teams across many companies have SLOs of four nines or less. Five is pretty rare.
gtirloni 7y ago
I think you might be alone. 5.26 minutes of down time per year is beyond excellent for any moderately complex system.
- cheez 7y ago
  I have a simple system that depends on another system and I can't keep it up for a week without 15 minutews downtime
bradleyjg 7y ago
Overall uptime isn't the only stat that matters here, the distribution of downtime matters too. One 15 minute outage in three years is a lot worse than 900 1 second outages over that same time period. One second blips are a part of the web, we click refresh and move on--not even knowing who's fault it was.
lclarkmichalek 7y ago
It kinda depends what availability means? That .001% unavailability might be degraded service, might be .001% of clients having a bad time across the entire year, might be 'acts of god' (i.e. broken CPUs and the like). This kind of service is also usually fairly low down on the stack, and higher level applications can usually degrade gracefully. If they couldn't, complex applications such as Google would fail to operate; there's always _something_ broken.

wallflower 7y ago

> There's also a story behind that project name. That is not the original project name. The original project name was force-removed by my SVP. Once my hands are free again, I can explain https://mobile.twitter.com/LeaKissner/status/1136631437514272768 https://mobile.twitter.com/LeaKissner/status/113663143751427...

delroth 7y ago
https://mobile.twitter.com/LeaKissner/status/1136691523104280576 https://mobile.twitter.com/LeaKissner/status/113669152310428...
koboll 7y ago
Yeah, that's kinda understandable. Although I'm not sure how the current name fits the project any better.
- Iv 7y ago
  It sounds pretty appropriate. This is another SF reference "Stand on Zanzibar", one of the earliest inspirations for cyberpunk, in which we are routinely remembered that all of humanity would be able to stand on the small island of Zanzibar, but that growth is problematic. https://en.wikipedia.org/wiki/Stand_on_Zanzibar https://en.wikipedia.org/wiki/Stand_on_Zanzibar
  - kjeetgill 7y ago
    For others that were confused as I was: SF here is Science Fiction not San Francisco.
pronoiac 7y ago
https://twitter.com/LeaKissner/status/1136691523104280576 https://twitter.com/LeaKissner/status/1136691523104280576 > Zanzibar was not the original name of the system. It was originally called "Spice". I have read Dune more times than I can count and an access control system is designed so that people can safely share things, so the project motto was "the shares must flow"

victor106 7y ago

What do other large (non-google scale) to medium companies use for authorization? Can anyone recommend open source (preferably) or close source products?

MrSaints 7y ago
A pretty simple, and configurable one: https://github.com/casbin/casbin https://github.com/casbin/casbin
ucarion 7y ago
https://github.com/ory/ladon https://github.com/ory/ladon is an option. Essentially, it imposes a lot of the fine-grained access control model on you, but then it's up to you to implement the actual database/business-logic layer [1] as well as the API layer to actually expose the service. [1] You do so by implementing this interface: https://github.com/ory/ladon/blob/master/warden.go https://github.com/ory/ladon/blob/master/warden.go
jamafu 7y ago
We use Keycloak at our place and are really happy with it. Website: https://www.keycloak.org/ https://www.keycloak.org/ GitHub: https://github.com/keycloak/keycloak https://github.com/keycloak/keycloak
- dusty_mc_dusty 7y ago
  Jup, it's quite nice!
perlgeek 7y ago
There's also Open Policy Agent (OPA) https://github.com/open-policy-agent/opa https://github.com/open-policy-agent/opa
gen220 7y ago
We use LDAP for managing group memberships (i.e. person x is a member of `engineering` and `eng_team_y`; only members of `eng_team_y` can change the deployment status of service Z). We then define ACLs for these groups. IDK how they are enforced, but they're visible/malleable via Ansible recipes, such that the process of adding permissions for your group (or user) involves submitting a diff to said Ansible recipe and getting approval from an SRE. In practice, we use Kerberos to obtain/distribute authorization tokens, which live for less than 24 hours. The authorization-value of these tokens is determined by the LDAP affinities of the bearer. If everything is configured correctly (which it always is, until you need new permissions / switch teams), all you have to do is auth with kerberos at the beginning of each day. We have ~200 engineers.

malicioususer11 7y ago

i wish google could authenticate my own sense of self worth, because then id save a lot on Therapy. :)

1023bytes 7y ago

Why is it called Zanzibar though? I'm kind of intrigued

pronoiac 7y ago
There's another thread about naming it - https://twitter.com/LeaKissner/status/1136691523104280576 https://twitter.com/LeaKissner/status/1136691523104280576 The original name was Spice, which was nixed from a higher-up; they went to Zanzibar, one of the Spice Islands.
- ddebernardy 7y ago
  Odd. Zanzibar is off the coast of Tanzania in East Africa. The Spice Islands (the Moluccas) are in Eastern Indonesia.
  - pronoiac 7y ago
    I was going by the twitter thread, but I looked and found this in Wikipedia: > the Zanzibar Archipelago, together with Tanzania's Mafia Island, are sometimes referred to locally as the "Spice Islands" (a term borrowed from the Maluku Islands of Indonesia). https://en.wikipedia.org/wiki/Zanzibar https://en.wikipedia.org/wiki/Zanzibar

deleted 7y ago

[deleted]

demarq 7y ago

Not sure how I feel about adopting a countries name for a project. Or more to the point I'm not sure how I would feel if every time I searched my countries name on the web this Google project appears rather than my actual country. i.e Zanzibar is a national identity not just a "spice" island

ocdtrekkie 7y ago
Countries who have the Amazon rainforest within their borders are still a little annoyed about the company. https://mashable.com/article/amazon-domain-name-icann-approved/ https://mashable.com/article/amazon-domain-name-icann-approv...
NameOfTeam 7y ago
To be clear, Zanzibar is neither a country nor a national identity. It’s a semi-autonomous region of Tanzania.