guide:leopard@pt-BR

Guias

Leopard, o índice de grupos

Como o Zanzibar responde sobre associação a grupos profundamente aninhados com uma única interseção de conjuntos, e quanto isso custa a cada escrita.

Fatos verificados em Seções do artigo §3.2.4, §4.4

O Zanzibar normalmente responde a um Check seguindo as tuplas do objeto até o usuário, uma consulta por vez. Para a maioria dos dados, isso é rápido. Para grupos aninhados em muitos níveis, não é, e o Zanzibar repassa essas verificações ao Leopard, um índice que pré-calcula o aninhamento.

Por que o aninhamento é lento

Estenda o exemplo recorrente. group:eng agora está dentro de group:product, que está dentro de group:all, e o readme é compartilhado com todo o group:all. Quantas consultas são necessárias para descobrir que Beto pode ver o readme?

Uma cadeia de grupos aninhadosuser:beto é membro de group:eng, os membros de group:eng são membros de group:product, os membros de group:product são membros de group:all, e os membros de group:all são visualizadores de doc:readme. Verificar o acesso de Beto começa em doc:readme e lê um objeto por passo: doc:readme, group:all, group:product e group:eng, quatro leituras em sequência.doc:readmegroup:allgroup:productgroup:enguser:beto1. lê doc:readme: visualizadores são group:all2. lê group:all: inclui group:product3. lê group:product: inclui group:eng4. lê group:eng: Beto é membroviewermembermembermember
Cada passo indica o objeto do passo seguinte, então as quatro leituras não podem começar juntas. Cada objeto também pode estar em um servidor diferente (veja a página de arquitetura).

As tuplas por trás da figura são:

doc:readme#viewer@group:all#member
group:all#member@group:product#member
group:product#member@group:eng#member
group:eng#member@user:beto

Observe que o passo n não pode começar até que o passo n − 1 tenha retornado. O artigo chama isso de pointer chasing e diz que ele “can be expensive when indirect ACLs or groups are deep or wide” (§3.2.3) (“pode ser custoso quando ACLs indiretas ou grupos são profundos ou largos”). A largura também prejudica: se group:all tivesse cem grupos filhos, o passo 2 se ramificaria de cem formas. Por isso: “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.” (§3.2.4) (“O pointer chasing recursivo durante a avaliação de verificações tem dificuldade em manter baixa latência com grupos profundamente aninhados ou que têm um grande número de grupos filhos. Para namespaces selecionados que exibem tal estrutura, o Zanzibar trata as verificações usando o Leopard, um índice especializado que oferece suporte a computação eficiente de conjuntos.”)

Dois tipos de conjunto

O Leopard armazena “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” (§3.2.4) (“uma coleção de conjuntos nomeados usando tuplas (T, s, e), em que T é um enum que representa o tipo de conjunto e s e e são inteiros de 64 bits que representam o ID do conjunto e o ID do elemento”). A associação a grupos usa dois tipos de conjunto:

  • GROUP2GROUP(s): os grupos que são, “directly or indirectly” (“direta ou indiretamente”), subgrupos do grupo ancestral s.
  • MEMBER2GROUP(s): os grupos dos quais o usuário s é membro “direct” (“direto”).

O que os conjuntos contêm no exemplo?

GROUP2GROUP e MEMBER2GROUP no exemploGROUP2GROUP(group:all) é group:all, group:product e group:eng. GROUP2GROUP(group:product) é group:product e group:eng. GROUP2GROUP(group:eng) é group:eng. MEMBER2GROUP(user:beto) é group:eng. MEMBER2GROUP(user:anne) é vazio.GROUP2GROUP(group:all)GROUP2GROUP(group:product)GROUP2GROUP(group:eng)MEMBER2GROUP(user:beto)MEMBER2GROUP(user:anne){ group:all, group:product, group:eng }{ group:product, group:eng }{ group:eng }{ group:eng }{ }
GROUP2GROUP é achatado: group:all lista group:eng, embora eng esteja dois níveis abaixo. MEMBER2GROUP não é: lista apenas associações diretas. Cada grupo aparece em seu próprio conjunto GROUP2GROUP; o artigo não diz isso, veja a nota abaixo.

Observe a assimetria. Todo o aninhamento é incorporado em GROUP2GROUP, de modo que o lado do usuário só precisa registrar onde o usuário foi adicionado diretamente. Nas palavras do artigo, “Flattening group-to-group paths allows reachability to be efficently evaluated by Leopard” (§3.2.4) (“Achatar os caminhos de grupo para grupo permite que a alcançabilidade seja avaliada de forma eficiente pelo Leopard”).

Associação é uma interseção não vazia

“To evaluate whether user U is a member of group G, we check whether” (§3.2.4) (“Para avaliar se o usuário U é membro do grupo G, verificamos se”)

(MEMBER2GROUP(U) ∩ GROUP2GROUP(G)) ≠ ∅

Ou seja: algum grupo ao qual o usuário foi adicionado diretamente também está em algum lugar abaixo de G? O que isso dá para Beto e Anne em relação a group:all?

Associação como interseçãoMEMBER2GROUP(user:beto), que é group:eng, intersectado com GROUP2GROUP(group:all), que é group:all, group:product e group:eng, dá group:eng: não vazio, então Beto é membro de group:all. MEMBER2GROUP(user:anne), que é vazio, intersectado com o mesmo conjunto dá o conjunto vazio, então Anne não é membro.MEMBER2GROUP(user:beto){ group:eng }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { group:eng }não vazio: membroMEMBER2GROUP(user:anne){ }GROUP2GROUP(group:all){ group:all, group:product, group:eng }∩ = { }vazio: não é membro
Duas consultas e uma interseção, qualquer que seja a profundidade do aninhamento. Beto está dentro; Anne, não.

As quatro leituras sequenciais da primeira figura viraram duas consultas a conjuntos e uma interseção. Para concluir a pergunta original, o Zanzibar ainda lê a tupla do readme que indica group:all#member; é a profundidade abaixo disso que o Leopard elimina. O artigo não detalha como um Check é dividido entre a avaliação comum e as consultas ao Leopard, portanto essa divisão é uma leitura da §3.2.4, não uma citação.

Interseção em listas ordenadas

Quão barata é a interseção? “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.” (§3.2.4) (“As tuplas do índice são armazenadas como listas ordenadas de inteiros em uma estrutura como uma skip list, permitindo assim uniões e interseções eficientes entre conjuntos. Por exemplo, avaliar a interseção entre dois conjuntos, A e B, requer apenas O(min(|A|, |B|)) buscas na skip list.”)

Interseção de uma lista ordenada curta com uma longaA lista A contém 17, 42 e 90. A lista B contém 3, 8, 17, 21, 30, 42, 55, 61, 77, 84, 93 e 99. Para cada elemento de A, uma busca em B encontra o primeiro elemento que não é menor: 17 encontra 17, 42 encontra 42, 90 para em 93, que não corresponde. A interseção é 17 e 42, encontrada em três buscas.AB1742903817213042556177849399busca 1: acertobusca 2: acertobusca 3: falha
Três elementos em A, três buscas em B. Os doze elementos de B nunca são percorridos um a um. Os níveis superiores da skip list, que tornam cada busca rápida, não estão desenhados.

Observe que o trabalho acompanha a lista mais curta. Quando um usuário é membro direto de apenas alguns grupos, MEMBER2GROUP(U) é curto e o teste continua barato mesmo quando GROUP2GROUP(G) é enorme. O artigo não informa tamanhos de conjuntos; esse caso é uma suposição. O índice “is sharded by element IDs” (“é particionado em shards por IDs de elemento”), e os shards “are usually served entirely from memory” (§3.2.4) (“normalmente são servidos inteiramente a partir da memória”).

Três 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.” (§3.2.4) (“O sistema Leopard consiste em três partes distintas: um sistema de serviço capaz de operações consistentes e de baixa latência sobre conjuntos; um sistema offline e periódico de construção de índice; e uma camada online em tempo real capaz de atualizar continuamente o sistema de serviço à medida que ocorrem alterações nas tuplas.”) Como elas se conectam?

As três partes do LeopardUm construtor de índice offline lê um snapshot das tuplas e configurações do Zanzibar e produz shards de índice, que são replicados e trocados no sistema de serviço do Leopard. Em paralelo, um indexador incremental lê o stream do Watch do Zanzibar e escreve atualizações com timestamp na camada incremental do sistema de serviço. Os aclservers consultam o sistema de serviço, que mescla a camada incremental sobre o índice offline no timestamp da consulta.snapshot detuplas + configconstrutor de índiceoffline (periódico)serviço do Leopardíndice offline+ camada incrementalAPI Watchindexadorincrementalaclserversnovos shardsalterações de tuplas(T, s, e, t, d)consulta
O caminho offline é completo, mas desatualizado; o caminho incremental é atual, mas cobre apenas alterações desde o último snapshot. O serviço mescla os dois.
  • Construtor de índice offline. Ele “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.” (“gera shards de índice a partir de um snapshot das tuplas de relação e configurações do Zanzibar e replica os shards globalmente. Ele respeita as regras de reescrita de userset e expande recursivamente as arestas em um grafo de ACL para formar tuplas de índice do Leopard.”) Os servidores “swap old shards with new ones when they become available” (“trocam shards antigos por novos quando estes ficam disponíveis”).
  • Camada incremental. O índice offline sozinho “cannot do so at a fresh and consistent snapshot” (“não consegue fazê-lo em um snapshot atual e consistente”), então os servidores mantêm “an incremental layer that indexes all updates since the offline snapshot” (“uma camada incremental que indexa todas as atualizações desde o snapshot offline”), cada atualização uma tupla (T, s, e, t, d) “where t is the timestamp of the update and d is a deletion marker” (“em que t é o timestamp da atualização e d é um marcador de exclusão”). “Updates with timestamps less than or equal to the query timestamp are merged on top of the offline index during query processing.” (“Atualizações com timestamps menores ou iguais ao timestamp da consulta são mescladas sobre o índice offline durante o processamento da consulta.”)
  • Alimentação. “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.” (“o indexador incremental do Leopard chama a API Watch do Zanzibar para receber um stream temporalmente ordenado de modificações de tuplas do Zanzibar e transforma as atualizações em um stream temporalmente ordenado de adições, atualizações e exclusões de tuplas do Leopard.”)

Todas as citações desta lista são da §3.2.4. Como as atualizações carregam timestamps e são mescladas até o timestamp da consulta, uma resposta do Leopard pode refletir o mesmo snapshot que o restante do Check; o propósito declarado pelo artigo para a camada incremental é “To support consistent ACL evaluation” (“Para dar suporte a uma avaliação de ACL consistente”).

O custo: uma escrita, muitas atualizações de índice

O achatamento é pago no momento da escrita. Volte para antes de eng ser adicionado a product e suponha que group:eng tenha dois subgrupos próprios, group:infra e group:web. Agora alguém adiciona eng a product. Quantas tuplas de índice mudam?

Uma escrita de tupla se desdobra em muitas atualizações de índiceAdicionar a tupla group:product#member@group:eng#member torna group:eng, group:infra e group:web novos descendentes tanto de group:product quanto de group:all. O indexador incremental transforma essa única tupla em seis adições a GROUP2GROUP: product ganha eng, infra e web, e all ganha eng, infra e web.group:product#member@group:eng#memberindexadorincremental+ G2G(product, eng)+ G2G(product, infra)+ G2G(product, web)+ G2G(all, eng)+ G2G(all, infra)+ G2G(all, web)1 escrita
1 tupla do Zanzibar, 6 tuplas do Leopard (o prefixo group: foi omitido): cada ancestral de product (product, all) vezes cada descendente de eng (eng, infra, web). MEMBER2GROUP não muda.

A contagem é o número de ancestrais de um lado vezes o número de descendentes do outro, então ela cresce tanto com a profundidade quanto com a largura. Para calculá-la, “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.” (“Gerar atualizações para as tuplas GROUP2GROUP exige que o indexador incremental mantenha a associação de grupo para grupo, a fim de desnormalizar os efeitos de uma atualização de tupla de relação em potencialmente múltiplas atualizações de índice.”) Na escala do Google: “In practice, a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events.” (§3.2.4) (“Na prática, uma única adição ou exclusão de tupla do Zanzibar pode gerar potencialmente dezenas de milhares de eventos distintos de tuplas do Leopard.”)

Uma exclusão é mais sutil do que a figura: uma tupla de índice só pode ser removida se nenhum outro caminho ainda conectar os dois grupos. O artigo não descreve como o indexador decide isso.

Essa também é a razão pela qual o Leopard é a exceção. Em outros pontos, “Zanzibar avoids storage denormalization and relies only on normalized data (except for the cases described in §3.2.4)” (§3.2.5) (“o Zanzibar evita a desnormalização do armazenamento e depende apenas de dados normalizados (exceto nos casos descritos na §3.2.4)”), e o Leopard é usado apenas para namespaces selecionados “that exhibit such structure” (§3.2.4) (“que exibem tal estrutura”).

Em produção

Da §4.4, ao longo de 7 dias: “The Leopard index is performing 1.56M QPS at the median, or 2.22M QPS at the 99th percentile” (“O índice Leopard está executando 1,56M QPS na mediana, ou 2,22M QPS no 99º percentil”), e “Leopard servers respond in fewer than 150 μsec at the median, or under 1 msec at the 99th percentile.” (“os servidores do Leopard respondem em menos de 150 μs na mediana, ou em menos de 1 ms no 99º percentil.”) A camada incremental “writes roughly 500 index updates per second at the median, and approximately 1.5K updates per second at the 99th percentile.” (“escreve aproximadamente 500 atualizações de índice por segundo na mediana e aproximadamente 1,5 mil atualizações por segundo no 99º percentil.”) As chamadas ao Leopard usam hedging, assim como as chamadas ao Spanner (§3.2.7).

Fontes