Os termos estão em ordem alfabética do nome em inglês, que é seguido da tradução usada neste site quando ela difere. Os nomes de código da linguagem de configuração do artigo (_this, computed_userset, tuple_to_userset) são ordenados sem os sublinhados. Os exemplos usam o exemplo recorrente: Anne, Beto e Chen; doc:readme em folder:A; group:eng.
A–C
- ACL
- Lista de controle de acesso (access control list): o conjunto de usuários autorizados a fazer algo com um objeto. No Zanzibar, uma ACL não é armazenada como uma única lista, mas como muitas tuplas de relação. Mais: Modelos de controle de acesso, §1, §2.1.
- aclserver
- O principal tipo de servidor do Zanzibar. Responde a Check, Read, Expand e Write, e distribui trabalho para outros aclservers de seu cluster. Mais: Arquitetura, §3.
- at-least-as-fresh (pelo menos tão atual quanto)
- A regra de um zookie: o Zanzibar pode avaliar em qualquer snapshot não mais antigo do que o timestamp do zookie, e não apenas exatamente nele. É essa liberdade que lhe permite servir a maioria das requisições a partir de réplicas locais. Mais: Consistência, §2.2.
- bounded staleness (defasagem limitada)
- Uma leitura de snapshot pode ser mais antiga do que “agora”, mas não mais antiga do que um limite. No Zanzibar, o limite é o zookie que o cliente envia. O Spanner oferece isso diretamente: o cliente fornece um limite superior para a defasagem e o Spanner escolhe o timestamp (artigo do Spanner, §4.1). Mais: Consistência, §2.2.
- cache stampede
- Muitas requisições concorrentes pelo mesmo resultado ainda não armazenado em cache vão todas ao armazenamento ao mesmo tempo, antes que o cache seja preenchido. O Zanzibar evita isso com uma tabela de locks. O artigo cita o artigo da Wikipedia para o termo (referência [3]). Mais: Arquitetura, §3.2.5.
- changelog
- Um banco de dados Spanner que guarda o histórico de atualizações de tuplas, escrito na mesma transação que cada escrita de tupla. O Watch lê a partir dele. Mais: Arquitetura, §3.1.2.
- Check
- A chamada da API que pergunta se um usuário pertence a um userset ⟨object#relation⟩, por exemplo “Chen é visualizador de
doc:readme?”. É avaliada em um snapshot não anterior ao zookie fornecido. Mais: Tuplas de relação, §2.4.4, §3.2.3. computed_userset- Uma folha de regra de reescrita que toma o userset de outra relação sobre o mesmo objeto, por exemplo “todo editor é visualizador”. Mais: Tuplas de relação, §2.3.1.
- consistent hashing (hashing consistente)
- Uma forma de atribuir chaves a servidores de modo que adicionar ou remover um servidor mova apenas uma pequena fração das chaves. O Zanzibar a usa para espalhar entradas de cache pelos servidores de um cluster. Introduzido por Karger et al. (STOC 1997) para caches web. Mais: Arquitetura, §3.2.5.
- content-change check (verificação de alteração de conteúdo)
- Um Check enviado quando um usuário está prestes a salvar novo conteúdo. Não leva zookie, é avaliado no snapshot mais recente e retorna um zookie que o cliente armazena com a nova versão do conteúdo. Mais: Consistência, §2.2, §2.4.4.
D–H
- denormalization (desnormalização)
- Armazenar uma cópia pré-calculada de dados derivados, como a associação grupo-a-grupo achatada, em vez de calculá-la a partir das linhas originais. O Zanzibar a evita no armazenamento e a usa apenas no Leopard. Mais: Leopard, §3.2.4, §3.2.5.
- exclusion (exclusão)
- Um operador de regra de reescrita: os usuários que estão em um userset, mas não em outro. Mais: Tuplas de relação, §2.3.1.
- Expand
- A chamada da API que retorna o userset efetivo de ⟨object#relation⟩ como uma árvore, seguindo as regras de reescrita. As folhas são IDs de usuário ou usersets; os nós internos são união, interseção ou exclusão. Mais: Tuplas de relação, §2.4.5.
- external consistency (consistência externa)
- Se a atualização x acontece antes da atualização y, x recebe um timestamp menor do que y, mesmo quando as duas são coordenadas fora do sistema. O Zanzibar obtém isso do Spanner. O artigo cita a tese de Gifford em Stanford, de 1981, para o termo (referência [18]); o Spanner a enuncia assim: se T1 é confirmada antes de T2 começar, o timestamp de commit de T1 é menor do que o de T2. Mais: Consistência, §2.2.
- fan-out
- Uma requisição que se transforma em muitas sub-requisições, por exemplo um aclserver que envia partes de um Check a outros servidores de seu cluster. Mais: Arquitetura, §3, §3.2.5.
- heartbeat zookie (zookie de heartbeat)
- Um zookie em cada resposta do Watch que marca até onde o fluxo chegou, para que o cliente possa retomar a partir dali. Mais: §2.4.3.
- hedging
- Enviar a mesma requisição a um segundo servidor assim que se sabe que o primeiro está lento, usando a resposta que chegar primeiro e cancelando a outra. O Zanzibar aplica hedging às chamadas ao Spanner e ao Leopard, não às chamadas entre seus próprios servidores. A técnica é descrita em Dean e Barroso, “The Tail at Scale” (CACM, 2013). Mais: Arquitetura, §3.2.7.
- hot spot (ponto quente)
- Uma chave, objeto ou grupo que recebe muito mais tráfego do que os demais e pode sobrecarregar o servidor que o armazena, por exemplo um grupo popular compartilhado por muitas ACLs. Mais: Arquitetura, §3.2.5.
I–N
- intersection (interseção)
- Um operador de regra de reescrita: os usuários que estão em cada um de vários usersets. Mais: Tuplas de relação, §2.3.1.
- Leopard
- Um sistema de indexação para grupos profundamente aninhados ou muito largos. Ele achata a associação a grupos em conjuntos de inteiros, de modo que uma verificação de associação se torna uma interseção de conjuntos, e se mantém atualizado por meio do Watch. Mais: Leopard, §3.2.4.
- lock table (tabela de locks)
- Uma tabela, em cada servidor, das leituras e verificações em andamento. Das requisições que compartilham uma chave de cache, apenas uma é executada; as demais aguardam o resultado dela. Mais: Arquitetura, §3.2.5.
- lock tuple (tupla de lock)
- Uma tupla de relação comum que os clientes alteram em toda escrita sobre um objeto, para que uma escrita possa ser condicionada a ninguém mais ter escrito desde a leitura. Mais: §2.4.2.
- namespace
- Um tipo de objeto definido pelo cliente, como
docoufolder. É a parte antes dos dois-pontos emdoc:readme. As tuplas de cada namespace ficam em seu próprio banco de dados. Mais: Tuplas de relação, §2.1, §2.3, §3.1.1. - namespace config (configuração de namespace)
- A configuração de um namespace: suas relações, cada uma com uma regra de reescrita de userset opcional, mais parâmetros de armazenamento, como o sharding. Mais: Tuplas de relação, §2.3, §3.1.3.
- new enemy problem (problema do “novo inimigo”)
- Mostrar conteúdo a alguém que foi removido da ACL desse conteúdo, porque a verificação ignorou a ordem de duas alterações de ACL ou aplicou uma ACL mais antiga do que o conteúdo. Mais: Consistência, §2.2.
O–R
- object (objeto)
- Aquilo que está sendo protegido, escrito como ⟨namespace⟩:⟨object_id⟩, por exemplo
doc:readme. Mais: Tuplas de relação, §2.1. - Paxos
- Um protocolo de consenso que permite a um grupo de réplicas concordar sobre cada escrita mesmo que algumas delas falhem. O artigo situa as cinco réplicas votantes do armazenamento do Zanzibar a menos de 25 ms umas das outras, para que as transações Paxos sejam confirmadas rapidamente. Veja Lamport, “Paxos Made Simple” (2001). Mais: Arquitetura, §3.1.4.
- pointer chasing
- Responder a um Check seguindo usersets um salto por vez: dos visualizadores do readme para
group:eng#member, depois para os membros desse grupo, e assim por diante. É lento quando os grupos são profundos ou largos. Mais: Tuplas de relação, Leopard, §3.2.3, §3.2.4. - Read
- A chamada da API que retorna as tuplas armazenadas que correspondem a um ou mais conjuntos de tuplas (tuplesets). Ela não aplica regras de reescrita. Mais: Tuplas de relação, §2.4.1.
- Recent request (requisição Recent)
- Veja Requisições Safe / Recent. Mais: Consistência, §4.1.
- relation (relação)
- Um relacionamento nomeado entre um objeto e um usuário, ou entre dois objetos (como
parentliga um documento à sua pasta), por exemploowner,viewer,memberouparent. É definida na configuração de namespace. Mais: Tuplas de relação, §2.1, §2.3. - relation tuple (tupla de relação)
- Um fato armazenado, ⟨object⟩#⟨relation⟩@⟨user⟩, por exemplo
doc:readme#owner@user:anne. É o único tipo de dado de permissão que o Zanzibar armazena. Mais: Tuplas de relação, §2.1. - replica (réplica)
- Uma cópia dos dados em um local. Os dados do Zanzibar são replicados em dezenas de locais, para que a maioria das leituras possa ser servida por perto. Mais: Arquitetura, §3.1.4.
S
- Safe / Recent requests (requisições Safe / Recent)
- A divisão que o artigo faz das requisições pela idade do zookie. As requisições Safe trazem zookies com mais de 10 segundos e normalmente podem ser servidas dentro da região; as requisições Recent trazem zookies mais novos e frequentemente precisam de uma viagem de ida e volta entre regiões. Mais: Consistência, §4.1.
- Uma fatia de um banco de dados ou de um índice, armazenada e servida separadamente. O ID de shard de uma tupla normalmente vem de seu ID de objeto e, para grupos muito grandes, do ID de objeto e do usuário. Mais: Arquitetura, §3.1.1, §3.2.4.
- snapshot read (leitura de snapshot)
- Uma leitura que vê o banco de dados exatamente como estava em um timestamp: todas as escritas nele ou antes dele, e nenhuma depois. O Zanzibar avalia cada Check em um único snapshot. O Spanner a define como “a read in the past that executes without locking” (uma leitura no passado que é executada sem locks) (artigo do Spanner, §4.1). Mais: Consistência, §2.2.
- Spanner
- O banco de dados globalmente distribuído do Google. O Zanzibar armazena nele as tuplas, as configurações de namespace e o changelog, e depende de seus timestamps para a consistência. Descrito em Corbett et al., OSDI 2012. Mais: Consistência, Arquitetura, §2.2, §3.
T
- tail latency (latência na cauda)
- A latência das requisições mais lentas, como o 99º ou o 99,9º percentil. Ela importa porque uma única página de resultados de busca pode exigir de dezenas a centenas de verificações. Veja Dean e Barroso, “The Tail at Scale” (CACM, 2013). Mais: Arquitetura, §1, §3.2.7, §4.2, §4.5.
_this- A folha de regra de reescrita que retorna os usuários das tuplas armazenadas para este objeto e esta relação, incluindo os usersets para os quais essas tuplas apontam. É o padrão quando uma relação não tem regra. Mais: Tuplas de relação, §2.3.1.
- timestamp quantization (quantização de timestamps)
- Arredondar os timestamps de avaliação para cima, em uma granularidade grossa, como um ou dez segundos, para que muitas requisições compartilhem um timestamp e, portanto, entradas de cache. Isso não enfraquece a consistência: um zookie define apenas um limite inferior, e uma leitura de snapshot do Spanner em um timestamp futuro espera até que o TrueTime o tenha ultrapassado (§3.2.5). Mais: Arquitetura, Consistência, §2.2, §3.2.5.
- TrueTime
- O mecanismo de relógio do Spanner, que dá a cada escrita um timestamp com resolução de microssegundos que reflete a ordem causal. É ele que torna significativos os timestamps do Zanzibar.
TT.now()retorna um intervalo que garantidamente contém o tempo real; veja o artigo do Spanner (OSDI 2012), §3. Mais: Consistência, §2.2, §3.2.5. - tupleset (conjunto de tuplas)
- Um seletor de tuplas armazenadas: uma única chave de tupla, ou todas as tuplas de um ID de objeto ou de um userset, opcionalmente limitadas a uma relação. Usado pelo Read e por
tuple_to_userset. Mais: Tuplas de relação, §2.4.1. tuple_to_userset- Uma folha de regra de reescrita que lê algumas tuplas do objeto e calcula um userset a partir de cada uma, por exemplo “procure a pasta pai do readme e tome seus visualizadores”. Mais: Tuplas de relação, §2.3.1.
U–W
- union (união)
- Um operador de regra de reescrita: os usuários que estão em qualquer um de vários usersets. Os três ramos de
viewerna Figura 1 do artigo são unidos por união. Mais: Tuplas de relação, §2.3.1. - user (usuário)
- A terceira parte de uma tupla: um único ID de usuário ou um userset. Mais: Tuplas de relação, §2.1.
- userset
- Um par ⟨object⟩#⟨relation⟩ que representa todos os usuários com aquela relação com aquele objeto, por exemplo
group:eng#member. Permite que uma tupla conceda acesso a um grupo, e que grupos contenham grupos. Mais: Tuplas de relação, §2.1. - userset rewrite rule (regra de reescrita de userset)
- Parte de uma configuração de relação: uma função de um ID de objeto para uma árvore de expressão de userset, construída a partir de
_this,computed_usersetetuple_to_usersetcombinados por união, interseção e exclusão. Mais: Tuplas de relação, §2.3.1. - userset tree (árvore de usersets)
- O resultado do Expand: as folhas são IDs de usuário ou usersets, e os nós internos são operadores de conjuntos. Mais: Tuplas de relação, §2.4.5.
- Watch
- A chamada da API que transmite as alterações de tuplas de um ou mais namespaces em ordem de timestamp, a partir de um zookie. Usada para manter índices secundários, como o Leopard, atualizados. Mais: Arquitetura, §2.4.3.
- watchserver
- O tipo de servidor que responde ao Watch acompanhando o changelog. Mais: Arquitetura, §3.
- Write
- A chamada da API que adiciona ou remove tuplas. Os clientes que reescrevem todas as tuplas de um objeto fazem uma leitura e, em seguida, uma escrita condicionada a que a tupla de lock não tenha mudado. Mais: Arquitetura (o que uma escrita afeta), §2.4.2.
Z
- zookie
- Um token opaco que codifica um timestamp. O cliente obtém um a partir de uma verificação de alteração de conteúdo (as respostas de Read e Write também trazem zookies), armazena-o com o conteúdo e o envia nas verificações seguintes, para que elas sejam avaliadas em um snapshot pelo menos tão atual quanto ele. Mais: Consistência, §2.2, §2.4.
Fontes
- J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
- D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
- J. Dean e L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
- L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
- D. K. Gifford, “Information Storage in a Decentralized Computer System”, tese de doutorado, Stanford University, 1981 (referência [18] do artigo; nenhuma cópia online foi verificada)
- “Cache stampede”, Wikipedia, en.wikipedia.org (a fonte que o artigo cita)
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang