Zanzibar: Consistent, Global Authorization System
ai.google
ai.google
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.
(You might be thinking of ordering ACEs in the ACL which isn't even a concept in Zanzibar)
Impressive!
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.
A serious conclusion should be that all these infrastructure enable application devs and researchers alike "to throw servers at problem". And these work are exactly the opposite, where they spent years and sometimes even decades meditating the nifty and figure out the most effective and efficient way of utilizing the servers.
https://blog.apnic.net/2019/04/03/the-future-of-undersea-int...
It doesn't matter if iCloud is slow or not since most of the interactions with it are in the background. And all of it's content e.g. App Store or Apple Music are cached by CDNs which are hosted in pretty much every country.
https://mobile.twitter.com/LeaKissner/status/113663143751427...
> 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"
Website: https://www.keycloak.org/
[1] You do so by implementing this interface: https://github.com/ory/ladon/blob/master/warden.go
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.
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?)
Unfortunately we don't have enough space to explain them in the paper. Please consider coming to Usenix. :-)
> 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
);
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.
I'm just confirming that replication is the best strategy and there's not some magic that I'm not aware of
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.
> 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.
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...
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.
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
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.
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().
The original name was Spice, which was nixed from a higher-up; they went to Zanzibar, one of the Spice Islands.
> 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).
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?
[1] https://twitter.com/LeaKissner/status/1136626971566149633
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.
I'm not close to Google, but from those I know on the product side it can be 'a Gaggle' with nobody really in charge ... but I guess if you have enough self-motivated conscientious actors, and mature people, without ugly turf wars, who can have reasonable discussions, and responsible enough people in charge that can steer things in an appropriate direction ... it works.
But the fact this is an evolution and not a 'new product' is probably prerequisite - so many smart people are hard to coral around new ideas, but if it's done A B C times, then a 'Z' solution speaks to an Engineers sense of efficiency and it should be natural for such an org to want to do it.
I won't name names, but I worked at a large tech company that could not get 'Single Sign On' to work. It was really frustrating to think so many reasonably smart people couldn't figure that out.
We don't need genius I think just a wealth of experience and a lot of common sense.
The underlying model of role based access control (and viewing groups as just other resources with ACLs) is already well known.
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.
I work for Google and I used to have this exact thought too. I think the reality is not quite as rosy, though far from bad!
You have to realize that there are hundreds of people who work on systems like this, and as a consequence, your day to day work is more or less the same as what you would do on systems of a smaller scale.
Before I joined Google I always wondered what things they did differently and what magical knowledge Googlers must have possessed. After joining I realized that while on average the engineers are definitely more capable than other places I've worked, there's no special wisdom and instead they just have more powerful primitives/tools to work with.
Of course, maybe I am mistaken and just don't know of the magic?
Reminds me of compound interests. Google operates at a scale where the company has enough brainpower to design systems like GFS/Colossus and Borg, which enable systems like Spanner, which enable systems like Zanzibar, and so on.
It was for me! :-)
(Of course, because it's after 5pm somewhere, I'm unfortunately already lit)
Maybe there's a place, somewhere, for the purest-of-the-pure non-boringest thoughts.
Sandstorm.io doesn't use protobuf, it uses Cap'n Proto, which was designed to replace protobuf.
Fun fact: The Zanzibar project was started in ~2011 specifically to replace my main project at the time, which was trying to solve the same problems. Apparently, some senior engineers felt letting me work on core infrastructure was too dangerous. They succeeded in turning my project into a lame duck and making me quit, which is when I then started working on Cap'n Proto and Sandstorm.io. In retrospect I'm glad it happened.
Yeah... Google is not always the most fun place to work on big infrastructure projects.
The scalability and interesting work has been factored out and handed off to infrastructure teams that build stuff like this auth framework, load balancers, highly scalable databases, data center cluster management tools, etc.
Which really is the smart way to do it. To the extent that you can stand on the shoulders of giants who've basically made scalability the default, you are free to focus on what you're actually trying to build. The only downside is if all the interesting engineering challenges are already solved for you, the remainder might not that be that interesting to people who enjoy engineering challenges.
JSON is definitely not the right stuff.
I mean in this context if you're doing that level of scale. For a lot of purposes json is totally fine.
Eg, You can do a sql join on any dataset, in any datacenter. You can turn any query into a hosted visualization.
Every test invocation is streamed to a central server and results can be shared with a url.
There’s more, but those are my two favorites.
Competition at work is something different, and you're always in competition with other companies and people to survive anyway.
1: http://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-Ke... 2: https://static.googleusercontent.com/media/research.google.c...
Google started as a C, Java and Python shops. Android is born out of a Linux Kernel.
If I remember well, long ago, the initial database they used was actually an in-shop fork of MySQL.
Easy to say bad things about free software now that you have billions and hundred of geniuses to work on your own stuff.
Actually, this kind of comment reminds me of the "linux is cancer" era of Microsoft. Funny like Google is now becoming the new MS now they got all the markets, while MS pretend to be nice now that they are not the top dog anymore.
Disclaimer: I've been bitter about MySQL-for-everything-ism lately too but think Java is pure heaven.
°I sense some irony
For example, here’s some information about memcache: 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.)
99.9 - < 90ms
That is amazing.
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).
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 :)
And yeah, the second half of my comment is trying to scope down the comparison to one that is reasonably “fair”
That's my corner of Google. We haven't published anything comparable to this paper in the time I've worked on it (maybe we could—I'm pleasantly surprised to see the Zanzibar folks got approval to share qps numbers and everything) but here's a bit about how it worked back in 2006:
https://www.usenix.org/legacy/event/worlds06/tech/prelim_pap...
Some of that still applies.
fwiw, while we do our fair share of password checking, we do a _lot_ more oauth token and cookie checking. Most folks just stay signed in on both mobile and web, so no need to recheck their passwords. In contrast, session credentials get checked on every request.
Something interesting to think about.
Zanzibar almost certainly has this type of behavior. More complex ACL structures under recent evaluations perform worse.
I'd love to see percentile data for depth of operation, but clearly the paper is limited in content size.
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
Phrased another way, when it is not availability, do end users experience service disruption, and if not, how is that mitigated?
> 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. ... 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 ofoperation 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%.
Basically, they're counting by number of requests. That's fairly typical for Google, who in their SRE book point out that measuring only total outages is a poor indicator of actual user experiences. Imagine if you had an electric company that had frequent brownouts and rolling blackouts but bragged about never having a total blackout. You'd be fairly unimpressed.
Google SREs also make the point that beyond five nines, your efforts are rendered moot by reliability issues you cannot control. Mostly network issues. If you have 99.99999% reliability but the mobile data network only has 99.99%, you've wasted a lot of money on something most folks will never notice.
The other portion is client side retry logic. It's incredibly easy for developers to mark a lookup with a retry policy and timer, and one of the reasons that that latency is so low is so that even if there's a timeout, the pageview can succeed. The application code doesn't see the error at all if the retry is successful, it just takes longer. The retry code is very good and it's already known at the first rpc call where the retry should go - the connection pool maintains connections to multiple independent servers.
I seen many internal facing teams across many companies have SLOs of four nines or less. Five is pretty rare.