Normalmente, Zanzibar responde a una comprobación siguiendo las tuplas del objeto al usuario, una búsqueda cada vez. Para la mayoría de los datos eso es rápido. Para grupos anidados en muchos niveles no lo es, y Zanzibar delega esas comprobaciones en Leopard, un índice que precalcula el anidamiento.
Por qué el anidamiento es lento
Amplíese el ejemplo de referencia. group:eng está ahora dentro de group:product, que está dentro de group:all, y el readme se comparte con todo group:all. ¿Cuántas búsquedas hacen falta para saber que Beto puede ver el readme?
Las tuplas detrás de la figura son:
doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto
Obsérvese que el paso n no puede empezar hasta que haya vuelto el paso n − 1. El artículo llama a esto persecución de punteros y dice que “can be expensive when indirect ACLs or groups are deep or wide” (puede resultar costosa cuando las ACL o los grupos indirectos son profundos o anchos) (§3.2.3). La anchura también perjudica: si group:all tuviera cien grupos hijos, el paso 2 se ramificaría de cien maneras. Por eso: “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 persecución recursiva de punteros durante la evaluación de las comprobaciones tiene dificultades para mantener una latencia baja con grupos profundamente anidados o con un gran número de grupos hijos. Para determinados espacios de nombres que presentan esa estructura, Zanzibar gestiona las comprobaciones mediante Leopard, un índice especializado que admite cálculos de conjuntos eficientes.) (§3.2.4)
Dos tipos de conjunto
Leopard almacena “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” (una colección de conjuntos con nombre mediante tuplas (T, s, e), donde T es un enumerado que representa el tipo de conjunto, y s y e son enteros de 64 bits que representan el ID del conjunto y el ID del elemento) (§3.2.4). La pertenencia a grupos usa dos tipos de conjunto:
GROUP2GROUP(s): los grupos que son subgrupos “directly or indirectly” (directa o indirectamente) del grupo antecesor s.MEMBER2GROUP(s): los grupos de los que el usuario s es miembro “direct” (directo).
¿Qué contienen los conjuntos en el ejemplo?
Obsérvese la asimetría. Todo el anidamiento se pliega en GROUP2GROUP, así que el lado del usuario solo tiene que registrar dónde se añadió directamente al usuario. En palabras del artículo, “Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard” (aplanar los caminos de grupo a grupo permite que Leopard evalúe la alcanzabilidad de forma eficiente) (§3.2.4).
La pertenencia es una intersección no vacía
“To evaluate whether user U is a member of group G, we check whether” (Para evaluar si el usuario U es miembro del grupo G, comprobamos si) (§3.2.4)
(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅
Es decir: ¿alguno de los grupos a los que se añadió directamente al usuario está también en algún lugar por debajo de G? ¿Qué da eso para Beto y Anne frente a group:all?
Las cuatro lecturas secuenciales de la primera figura se han convertido en dos búsquedas de conjuntos y una intersección. Para terminar la pregunta original, Zanzibar sigue leyendo la tupla del readme que nombra group:all#member; lo que Leopard elimina es la profundidad por debajo de ella. El artículo no detalla cómo se reparte una comprobación entre la evaluación ordinaria y las consultas a Leopard, así que este reparto es una lectura de §3.2.4, no una cita.
Intersección sobre listas ordenadas
¿Cuán barata es la intersección? “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.” (Las tuplas del índice se almacenan como listas ordenadas de enteros en una estructura como una skip list, lo que permite uniones e intersecciones eficientes entre conjuntos. Por ejemplo, evaluar la intersección entre dos conjuntos, A y B, solo requiere O(min(|A|, |B|)) búsquedas en la skip list.) (§3.2.4)
Obsérvese que el trabajo sigue a la lista más corta. Cuando un usuario es miembro directo de solo unos pocos grupos, MEMBER2GROUP(U) es corta y la prueba sigue siendo barata aunque GROUP2GROUP(G) sea enorme. El artículo no da tamaños de conjuntos; ese caso es una suposición. El índice “is sharded by element IDs” (está fragmentado por ID de elemento), y los fragmentos “are usually served entirely from memory” (normalmente se sirven íntegramente desde memoria) (§3.2.4).
Tres partes
“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.” (El sistema Leopard consta de tres partes diferenciadas: un sistema de servicio capaz de realizar operaciones consistentes y de baja latencia sobre conjuntos; un sistema periódico de construcción de índices fuera de línea; y una capa en línea en tiempo real capaz de actualizar continuamente el sistema de servicio a medida que se producen cambios en las tuplas.) (§3.2.4) ¿Cómo se conectan?
- Constructor de índices fuera de línea. “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.” (genera fragmentos del índice a partir de una instantánea de las tuplas de relación y las configuraciones de Zanzibar, y replica los fragmentos globalmente. Respeta las reglas de reescritura de usersets y expande recursivamente las aristas de un grafo de ACL para formar las tuplas del índice Leopard.) Los servidores “swap old shards with new ones when they become available” (sustituyen los fragmentos antiguos por los nuevos cuando están disponibles).
- Capa incremental. El índice fuera de línea por sí solo “cannot do so at a fresh and consistent snapshot” (no puede hacerlo en una instantánea reciente y consistente), así que los servidores mantienen “an incremental layer that indexes all updates since the offline snapshot” (una capa incremental que indexa todas las actualizaciones desde la instantánea fuera de línea), cada actualización una tupla
(T, s, e, t, d)“where t is the timestamp of the update and d is a deletion marker” (donde t es la marca de tiempo de la actualización y d es un marcador de eliminación). “Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.” (Las actualizaciones con marcas de tiempo menores o iguales que la marca de tiempo de la consulta se combinan sobre el índice fuera de línea durante el procesamiento de la consulta.) - Alimentación. “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.” (el indexador incremental de Leopard llama a la API Watch de Zanzibar para recibir un flujo ordenado temporalmente de modificaciones de tuplas de Zanzibar y transforma las actualizaciones en un flujo ordenado temporalmente de adiciones, actualizaciones y eliminaciones de tuplas de Leopard.)
Todas las citas de esta lista proceden de §3.2.4. Como las actualizaciones llevan marcas de tiempo y se combinan hasta la marca de tiempo de la consulta, una respuesta de Leopard puede reflejar la misma instantánea que el resto de la comprobación; el propósito que el artículo declara para la capa incremental es “To support consistent ACL evaluation” (dar soporte a una evaluación consistente de las ACL).
El coste: una escritura, muchas actualizaciones del índice
El aplanamiento se paga en el momento de escribir. Vuélvase a antes de que eng se añadiera a product, y supóngase que group:eng tiene dos subgrupos propios, group:infra y group:web. Ahora alguien añade eng a product. ¿Cuántas tuplas del índice cambian?
La cuenta es el número de antecesores de un lado por el número de descendientes del otro, así que crece tanto con la profundidad como con la anchura. Para calcularla, “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.” (Generar actualizaciones para las tuplas GROUP2GROUP requiere que el indexador incremental mantenga la pertenencia de grupo a grupo para desnormalizar los efectos de una actualización de una tupla de relación en potencialmente múltiples actualizaciones del índice.) A la escala de Google: “In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.” (En la práctica, una sola adición o eliminación de una tupla de Zanzibar puede dar lugar potencialmente a decenas de miles de eventos discretos de tuplas de Leopard.) (§3.2.4)
Una eliminación es más sutil que la figura: una tupla del índice solo puede eliminarse si ningún otro camino sigue conectando los dos grupos. El artículo no describe cómo lo decide el indexador.
Esa es también la razón de que Leopard sea la excepción. En el resto del sistema, “Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4)” (Zanzibar evita la desnormalización del almacenamiento y se basa únicamente en datos normalizados, salvo en los casos descritos en §3.2.4) (§3.2.5), y Leopard solo se usa para determinados espacios de nombres “that exhibit such structure” (que presentan esa estructura) (§3.2.4).
En producción
Según §4.4, a lo largo de 7 días: “The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile” (el índice Leopard atiende 1.56M QPS en la mediana, o 2.22M QPS en el percentil 99), y “Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile.” (los servidores de Leopard responden en menos de 150 μs en la mediana, o en menos de 1 ms en el percentil 99.) La capa incremental “writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.” (escribe unas 500 actualizaciones del índice por segundo en la mediana, y aproximadamente 1.5K actualizaciones por segundo en el percentil 99.) Las llamadas a Leopard se cubren con hedging igual que las llamadas a Spanner (§3.2.7).
Fuentes
- 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