Zanzibar répond normalement à un Check en suivant les tuples de l’objet jusqu’à l’utilisateur, une recherche à la fois. Pour la plupart des données, c’est rapide. Pour des groupes imbriqués sur de nombreux niveaux, ce n’est pas le cas, et Zanzibar confie ces vérifications à Leopard, un index qui précalcule l’imbrication.
Pourquoi l’imbrication est lente
Étendons l’exemple suivi. group:eng se trouve désormais dans group:product, lui-même dans group:all, et le readme est partagé avec tout group:all. Combien de recherches faut-il pour établir que Beto peut consulter le readme ?
Les tuples qui sous-tendent la figure sont :
doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto
Remarquez que l’étape n ne peut pas commencer avant que l’étape n − 1 ait répondu. L’article appelle cela la poursuite de pointeurs et indique qu’elle « can be expensive when indirect ACLs or groups are deep or wide » (peut être coûteuse lorsque les ACL indirectes ou les groupes sont profonds ou larges) (§3.2.3). La largeur pénalise aussi : si group:all contenait une centaine de groupes enfants, l’étape 2 se ramifierait cent fois. D’où : « 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. » (La poursuite récursive de pointeurs lors de l’évaluation des vérifications peine à maintenir une faible latence avec des groupes profondément imbriqués ou comportant un grand nombre de groupes enfants. Pour certains espaces de noms présentant une telle structure, Zanzibar traite les vérifications à l’aide de Leopard, un index spécialisé qui prend en charge un calcul ensembliste efficace.) (§3.2.4)
Deux types d’ensembles
Leopard stocke « a collection of named sets using (T, s, e) tuples, where T is an enum representing the set type and s and e are 64-bit integers representing the set ID and the element ID » (une collection d’ensembles nommés à l’aide de tuples (T, s, e), où T est une énumération représentant le type d’ensemble, et s et e sont des entiers de 64 bits représentant respectivement l’identifiant de l’ensemble et l’identifiant de l’élément) (§3.2.4). L’appartenance aux groupes utilise deux types d’ensembles :
GROUP2GROUP(s): les groupes qui sont « directly or indirectly » (directement ou indirectement) des sous-groupes du groupe ancêtre s.MEMBER2GROUP(s): les groupes dont l’utilisateur s est membre « direct » (direct).
Que contiennent ces ensembles pour l’exemple ?
Remarquez l’asymétrie. Toute l’imbrication est repliée dans GROUP2GROUP ; le côté utilisateur n’a donc qu’à enregistrer où l’utilisateur a été ajouté directement. Selon les termes de l’article, « Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard » (L’aplatissement des chemins de groupe à groupe permet à Leopard d’évaluer efficacement l’accessibilité) (§3.2.4).
L’appartenance est une intersection non vide
« To evaluate whether user U is a member of group G, we check whether » (Pour évaluer si l’utilisateur U est membre du groupe G, nous vérifions si) (§3.2.4)
(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅
Autrement dit : l’un des groupes auxquels l’utilisateur a été ajouté directement se trouve-t-il aussi quelque part sous G ? Qu’est-ce que cela donne pour Beto et Anne par rapport à group:all ?
Les quatre lectures successives de la première figure sont devenues deux recherches d’ensembles et une intersection. Pour répondre entièrement à la question initiale, Zanzibar lit encore le tuple du readme qui désigne group:all#member ; c’est la profondeur située en dessous que Leopard supprime. L’article ne précise pas comment un Check se répartit entre évaluation ordinaire et requêtes Leopard ; cette répartition est donc une lecture du §3.2.4, et non une citation.
Intersection sur des listes triées
Que coûte l’intersection ? « 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, A and B, requires only O(min(|A|, |B|)) skip-list seeks. » (Les tuples d’index sont stockés sous forme de listes ordonnées d’entiers dans une structure telle qu’une skip list, ce qui permet des unions et des intersections efficaces entre ensembles. Par exemple, évaluer l’intersection de deux ensembles A et B ne nécessite que O(min(|A|, |B|)) positionnements dans la skip list.) (§3.2.4)
Remarquez que le travail suit la liste la plus courte. Lorsqu’un utilisateur n’est membre direct que de quelques groupes, MEMBER2GROUP(U) est court et le test reste peu coûteux même lorsque GROUP2GROUP(G) est énorme. L’article ne donne aucune taille d’ensemble ; ce cas est une hypothèse. L’index « is sharded by element IDs » (est fragmenté par identifiant d’élément), et les fragments « are usually served entirely from memory » (sont généralement servis entièrement depuis la mémoire) (§3.2.4).
Trois parties
« 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. » (Le système Leopard se compose de trois parties distinctes : un système de service capable d’effectuer des opérations cohérentes et à faible latence sur des ensembles ; un système de construction d’index périodique et hors ligne ; et une couche en ligne en temps réel capable de mettre à jour en continu le système de service au fur et à mesure que des modifications de tuples se produisent.) (§3.2.4) Comment s’articulent-elles ?
- Constructeur d’index hors ligne. Il « 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. » (génère des fragments d’index à partir d’un instantané des tuples de relation et des configurations de Zanzibar, et réplique ces fragments à l’échelle mondiale. Il respecte les règles de réécriture de userset et développe récursivement les arêtes d’un graphe d’ACL pour former les tuples d’index Leopard.) Les serveurs « swap old shards with new ones when they become available » (remplacent les anciens fragments par les nouveaux lorsqu’ils deviennent disponibles).
- Couche incrémentale. L’index hors ligne seul « cannot do so at a fresh and consistent snapshot » (ne peut pas le faire sur un instantané frais et cohérent) ; les serveurs maintiennent donc « an incremental layer that indexes all updates since the offline snapshot » (une couche incrémentale qui indexe toutes les mises à jour depuis l’instantané hors ligne), chaque mise à jour étant un tuple
(T, s, e, t, d)« where t is the timestamp of the update and d is a deletion marker » (où t est l’horodatage de la mise à jour et d un marqueur de suppression). « Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing. » (Les mises à jour dont l’horodatage est inférieur ou égal à l’horodatage de la requête sont fusionnées par-dessus l’index hors ligne lors du traitement de la requête.) - Alimentation. « 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. » (l’indexeur incrémental de Leopard appelle l’API Watch de Zanzibar pour recevoir un flux temporellement ordonné de modifications de tuples Zanzibar, et transforme ces mises à jour en un flux temporellement ordonné d’ajouts, de mises à jour et de suppressions de tuples Leopard.)
Toutes les citations de cette liste proviennent du §3.2.4. Comme les mises à jour portent des horodatages et sont fusionnées jusqu’à l’horodatage de la requête, une réponse de Leopard peut refléter le même instantané que le reste du Check ; l’objectif déclaré par l’article pour la couche incrémentale est « To support consistent ACL evaluation » (Pour permettre une évaluation cohérente des ACL).
Le coût : une écriture, de nombreuses mises à jour d’index
L’aplatissement se paie au moment de l’écriture. Revenons à l’état antérieur à l’ajout de eng dans product, et supposons que group:eng possède deux sous-groupes, group:infra et group:web. Quelqu’un ajoute maintenant eng à product. Combien de tuples d’index changent ?
Le nombre est le produit du nombre d’ancêtres d’un côté par le nombre de descendants de l’autre ; il croît donc avec la profondeur comme avec la largeur. Pour le calculer, « Generating updates for the 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. » (Générer les mises à jour des tuples GROUP2GROUP exige que l’indexeur incrémental maintienne les appartenances de groupe à groupe, afin de dénormaliser les effets d’une mise à jour de tuple de relation en potentiellement plusieurs mises à jour d’index.) À l’échelle de Google : « In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events. » (En pratique, un seul ajout ou une seule suppression de tuple Zanzibar peut produire potentiellement des dizaines de milliers d’événements distincts sur des tuples Leopard.) (§3.2.4)
Une suppression est plus délicate que ne le montre la figure : un tuple d’index ne peut être retiré que si aucun autre chemin ne relie encore les deux groupes. L’article ne décrit pas comment l’indexeur en décide.
C’est aussi pourquoi Leopard est l’exception. Ailleurs, « Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4) » (Zanzibar évite la dénormalisation du stockage et ne s’appuie que sur des données normalisées (à l’exception des cas décrits au §3.2.4)) (§3.2.5), et Leopard n’est utilisé que pour certains espaces de noms « that exhibit such structure » (présentant une telle structure) (§3.2.4).
En production
D’après le §4.4, sur 7 jours : « The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile » (L’index Leopard traite 1.56M de requêtes par seconde à la médiane, ou 2.22M au 99e centile), et « Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile. » (les serveurs Leopard répondent en moins de 150 μs à la médiane, ou en moins de 1 ms au 99e centile.) La couche incrémentale « writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile. » (écrit environ 500 mises à jour d’index par seconde à la médiane, et environ 1.5K mises à jour par seconde au 99e centile.) Les appels à Leopard font l’objet de requêtes de couverture (hedging), comme les appels à Spanner (§3.2.7).
Sources
- Pang et al., « Zanzibar: Google’s Consistent, Global Authorization System », USENIX ATC ’19, §3.2.3, §3.2.4, §3.2.5, §3.2.7, §4.4 : https://www.usenix.org/conference/atc19/presentation/pang