O Zanzibar é um conjunto de servidores à frente de um conjunto de bancos de dados Spanner. Esta página nomeia as partes, depois acompanha uma requisição Check através delas e, em seguida, examina como os dados estão dispostos em disco. Os números ao final são os que o artigo relata para a produção em 2018.
As partes
Que caixas existem e em que direção os dados fluem entre elas? O artigo responde com sua Figura 2. A versão abaixo mantém suas cores (clientes em azul, servidores em amarelo, bancos de dados Spanner em verde) e omite os detalhes.
Observe que os clientes conversam com dois tipos de servidor. Os aclservers respondem aos quatro tipos de requisição; os watchservers apenas transmitem alterações. Nas palavras do artigo, os aclservers “are organized in clusters and respond to Check, Read, Expand, and Write requests” (são organizados em clusters e respondem a requisições Check, Read, Expand e Write), enquanto os watchservers “tail the changelog and serve a stream of namespace changes to clients in near real time” (acompanham o changelog e servem aos clientes um fluxo de alterações de namespace quase em tempo real) (§3). O Leopard é um índice para grupos grandes e profundamente aninhados; ele tem sua própria página.
O pipeline offline produz “dumps of the relation tuples in each namespace at a known snapshot timestamp” (dumps das tuplas de relação de cada namespace em um timestamp de snapshot conhecido) e faz a coleta de lixo de “tuple versions older than a threshold configured per namespace” (versões de tuplas mais antigas do que um limite configurado por namespace) (§3).
Um Check, passo a passo
A requisição a acompanhar: Beto é visualizador do readme? No exemplo recorrente, os visualizadores do readme incluem os membros de group:eng, e Beto é um deles, então a resposta é sim. O Zanzibar precisa descobrir isso lendo dois objetos, doc:readme e group:eng.
Ela chega a qualquer servidor, que distribui o trabalho
Qual servidor faz o trabalho? Qualquer um deles pode receber a requisição, e o trabalho é então distribuído por objeto.
O servidor A não precisava ser responsável por nenhum dos dois objetos. O artigo descreve exatamente esse formato: “Requests arrive at any server in a cluster and that server fans out the work to other servers in the cluster as necessary. Those servers may in turn contact other servers to compute intermediate results. The initial server gathers the final result and returns it to the client.” (As requisições chegam a qualquer servidor de um cluster, e esse servidor distribui o trabalho para outros servidores do cluster conforme necessário. Esses servidores podem, por sua vez, contatar outros servidores para calcular resultados intermediários. O servidor inicial reúne o resultado final e o retorna ao cliente.) (§3)
O hashing consistente escolhe o par
Como A sabia que devia perguntar a B sobre o readme? Os servidores de um cluster formam um único cache distribuído: “Cache entries are distributed across Zanzibar servers with consistent hashing” (as entradas de cache são distribuídas entre os servidores do Zanzibar com hashing consistente) (§3.2.5). O esquema vem de Karger et al. (STOC ’97), que o artigo cita como [20]. Para a maioria dos namespaces, a chave de encaminhamento é calculada a partir do ID do objeto (§3.2.5).
Observe que viewer e owner do readme se encontram no mesmo servidor. Esse é o objetivo de usar o objeto como chave: “processing a check on ⟨object#relation⟩ often involves indirect ACL checks on other relations of the same object and reading relation tuples of the object. These checks and reads can be processed by the same server since they share the same forwarding key with the parent check request.” (processar uma verificação sobre ⟨object#relation⟩ frequentemente envolve verificações de ACL indiretas sobre outras relações do mesmo objeto e a leitura de tuplas de relação do objeto. Essas verificações e leituras podem ser processadas pelo mesmo servidor, pois compartilham a mesma chave de encaminhamento com a requisição de verificação pai.) (§3.2.5) Karger et al. projetam o hashing consistente de modo que, quando um cache é adicionado ou removido, apenas a fração mínima de objetos necessária para manter a carga equilibrada precise ser movida, e é por isso que ele é adequado a um cache.
Para chaves quentes, o artigo acrescenta que usa o Slicer “to help distribute hot keys to multiple servers” (para ajudar a distribuir chaves quentes por vários servidores) (§3.2.5).
As duas pontas de uma chamada armazenam a resposta em cache
O que acontece quando muitos servidores perguntam a C sobre group:eng ao mesmo tempo, por exemplo porque uma página de resultados de busca verifica dezenas de documentos que estão todos compartilhados com eng?
Os caches dos chamadores e o cache do chamado se empilham em uma árvore: “To handle hot forwarding keys, we cache results at both the caller and the callee of internal RPCs, effectively forming cache trees.” (Para lidar com chaves de encaminhamento quentes, armazenamos resultados em cache tanto no chamador quanto no chamado das RPCs internas, formando, na prática, árvores de cache.) (§3.2.5) As chaves de cache incluem o timestamp do snapshot, e os timestamps são “rounded up to a coarse granularity, such as one or ten seconds” (arredondados para cima até uma granularidade grosseira, como um ou dez segundos), de modo que a maioria das requisições recentes compartilhe entradas (§3.2.5). Em produção, o cache de verificações tinha “a 10% hit rate on the delegate’s side” (uma taxa de acerto de 10% no lado do delegado) e “a 2% hit rate” (uma taxa de acerto de 2%) no lado do delegante; o artigo observa que, por mais baixas que essas taxas pareçam, “they prevent 500K internal RPCs per second from creating hot spots” (elas impedem que 500 mil RPCs internas por segundo criem pontos quentes) (§4.4).
A tabela de locks reúne requisições idênticas
Um cache só ajuda depois que contém a resposta. Se muitas requisições idênticas chegarem antes de a primeira terminar, todas falhariam no cache e todas iriam ao Spanner: um cache stampede (a referência [3] do artigo). Como C evita isso?
O artigo: “we maintain a lock table on each server to track outstanding reads and checks. Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (mantemos uma tabela de locks em cada servidor para acompanhar leituras e verificações pendentes. Entre as requisições que compartilham a mesma chave de cache, apenas uma começará a ser processada; as demais ficam bloqueadas até que o cache seja preenchido.) (§3.2.5) Para verificações, a tabela de locks economizou “an additional 12%” (12% adicionais) no lado do delegado e “an additional 3%” (3% adicionais) no lado do delegante (§4.4).
Dois refinamentos vieram depois (§3.2.5). Para um objeto muito popular, o Zanzibar lê e armazena em cache todas as tuplas de ⟨object#relation⟩ de uma só vez, “trading read bandwidth for cacheability” (trocando largura de banda de leitura por capacidade de cache). E, como uma subverificação cancelada deixa sua chave de cache vazia, ele adia o “eager cancellation when there are waiters on the corresponding lock table entry” (cancelamento antecipado quando há requisições aguardando na entrada correspondente da tabela de locks).
As leituras ao Spanner são agrupadas
Agora considere uma verificação que envolve várias relações de um mesmo objeto: Chen é visualizador do readme? Com a configuração da Figura 1 do artigo, viewer inclui editor, editor inclui owner, e os visualizadores da pasta parent são visualizadores do documento. Assim, o servidor B tem quatro conjuntos de tuplas do readme para ler.
As folhas são executadas concorrentemente: “we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (avaliamos todos os nós folha da árvore de expressão booleana concorrentemente. Quando o resultado de um nó determina o resultado de uma subárvore, a avaliação dos demais nós da subárvore é cancelada.) (§3.2.3) Suas leituras são agrupadas: “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner.” (Aplicamos um mecanismo de pooling para agrupar as leituras de uma mesma verificação de ACL, a fim de minimizar o número de RPCs de leitura ao Spanner.) (§3.2.3) A tupla parent então aponta para folder:A, e folder:A#viewer é encaminhada ao servidor responsável por folder:A, onde Chen é encontrado. O artigo não diz em quantas RPCs um pool se transforma; “menos” é tudo o que ele afirma.
A disposição das tuplas torna isso barato: a ordem da chave primária “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (permite-nos consultar todas as tuplas de relação de um dado ID de objeto ou par (ID de objeto, relação)) (§3.1.1, veja Armazenamento abaixo).
Leituras lentas ao Spanner recebem hedging
Algumas leituras serão lentas por motivos que nada têm a ver com a requisição. Para chamadas ao Spanner e ao Leopard, o Zanzibar usa hedging de requisições, de Dean e Barroso, “The Tail at Scale” (CACM, 2013), a referência [16] do artigo. Quando a segunda requisição é enviada?
Hedging significa que “we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests” (enviamos a mesma requisição a vários servidores, usamos a resposta que voltar primeiro e cancelamos as demais requisições) (§3.2.7). A segunda requisição espera: “we first send one request and defer sending hedged requests until the initial request is known to be slow” (primeiro enviamos uma requisição e adiamos o envio das requisições de hedging até que se saiba que a requisição inicial está lenta), com o atraso definido por um estimador de uma “Nth percentile latency based on recent measurements” (latência no N-ésimo percentil com base em medições recentes) (§3.2.7). Em produção, “1% of Spanner reads, or 200K reads per second, benefit from hedging” (1% das leituras ao Spanner, ou 200 mil leituras por segundo, se beneficiam do hedging) (§4.4).
Cada cliente tem limites
Um serviço compartilhado precisa impedir que um cliente deixe os outros mais lentos. A §3.2.6 lista quatro limites:
- CPU: cada RPC tem seu custo medido em “generic cpu-seconds” (cpu-segundos genéricos); cada cliente tem um limite global de CPU, e “its RPCs will be throttled if it exceeds the limit and there is no spare capacity in the overall system.” (suas RPCs serão limitadas se ele exceder o limite e não houver capacidade ociosa no sistema como um todo.)
- RPCs pendentes: cada servidor limita o total e o número por cliente.
- Spanner: “the maximum number of concurrent reads per (object, client) and per client on each Spanner server.” (o número máximo de leituras concorrentes por (objeto, cliente) e por cliente em cada servidor Spanner.)
- Tabelas de locks: “different lock table keys for requests from different clients” (chaves de tabela de locks diferentes para requisições de clientes diferentes), de modo que a limitação de um cliente pelo Spanner não bloqueie outro.
O caminho do Watch
As escritas também alimentam um fluxo. Para onde vai uma alteração depois que Anne escreve uma tupla?
“Every Zanzibar write is committed to both the tuple storage and the changelog shard in a single transaction.” (Toda escrita do Zanzibar é confirmada tanto no armazenamento de tuplas quanto no shard do changelog em uma única transação.) O servidor Spanner que hospeda o shard do changelog atua como coordenador da transação “to minimize blocking of changelog reads on pending transactions” (para minimizar o bloqueio de leituras do changelog por transações pendentes) (§3.1.2). O Leopard é um dos consumidores desse fluxo: seu indexador incremental “calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications” (chama a API Watch do Zanzibar para receber um fluxo temporalmente ordenado de modificações de tuplas do Zanzibar) (§3.2.4).
Armazenamento
Que bancos de dados existem e como é uma linha? Há três tipos (§3).
Bancos de dados de tuplas. “We store relation tuples of each namespace in a separate database, where each row is identified by primary key (shard ID, object ID, relation, user, commit timestamp).” (Armazenamos as tuplas de relação de cada namespace em um banco de dados separado, em que cada linha é identificada pela chave primária (ID de shard, ID de objeto, relação, usuário, timestamp de commit).) (§3.1.1) Como o timestamp de commit faz parte da chave, as versões antigas permanecem em suas próprias linhas, “so that we can evaluate checks and reads at any timestamp within the garbage collection window” (para que possamos avaliar verificações e leituras em qualquer timestamp dentro da janela de coleta de lixo). As tuplas do exemplo recorrente ficariam nos bancos de dados doc e group assim:
| Banco de dados | ID de shard | ID de objeto | relação | usuário | timestamp de commit |
|---|---|---|---|---|---|
doc |
s(readme) | readme |
owner |
user:anne |
t₁ |
doc |
s(readme) | readme |
parent |
folder:A#... |
t₂ |
doc |
s(readme) | readme |
viewer |
group:eng#member |
t₃ |
group |
s(eng) | eng |
member |
user:beto |
t₄ |
As linhas de um mesmo objeto ficam ordenadas juntas; o artigo diz que essa ordem de chave “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (permite-nos consultar todas as tuplas de relação de um dado ID de objeto ou par (ID de objeto, relação)). “Usually the shard ID is determined solely by the object ID” (Normalmente, o ID de shard é determinado apenas pelo ID do objeto); para grupos com muitíssimos membros, ele pode ser “computed from both object ID and user” (calculado a partir tanto do ID do objeto quanto do usuário) (§3.1.1). O artigo não fornece a função de shard, então s(…) acima é um marcador de posição, e a codificação exata da coluna de usuário também não é descrita.
Changelog. Um banco de dados para todos os namespaces, com chave (ID do shard do changelog, timestamp, ID único da atualização), “where a changelog shard is randomly selected for each write” (em que um shard do changelog é selecionado aleatoriamente para cada escrita) (§3.1.2).
Configurações de namespace. Um banco de dados com duas tabelas: as configurações, “keyed by namespace IDs” (indexadas por IDs de namespace), e “a changelog of config updates” (um changelog de atualizações de configuração), “keyed by commit timestamps” (indexado por timestamps de commit). Um servidor carrega todas as configurações na inicialização e depois acompanha esse changelog (§3.1.3).
Replicação. “Replicas exist in dozens of locations around the world, with multiple replicas per region. The 5 voting replicas are in eastern and central United States, in 3 different metropolitan areas to isolate failures but within 25 milliseconds of each other so that Paxos transactions commit quickly.” (Há réplicas em dezenas de locais ao redor do mundo, com múltiplas réplicas por região. As 5 réplicas votantes ficam no leste e no centro dos Estados Unidos, em 3 áreas metropolitanas diferentes, para isolar falhas, mas a menos de 25 milissegundos umas das outras, para que as transações Paxos sejam confirmadas rapidamente.) (§3.1.4) O próprio Spanner é descrito em Corbett et al. (OSDI ’12), a referência [15] do artigo.
Números operacionais
A §4 do artigo relata estes números. Os picos por API e as latências vêm de períodos de 7 dias em dezembro de 2018 (§4, §4.2); o artigo não associa os demais números a um período declarado. Cada célula é citada como escrita, seguida da tradução.
| O quê | Nas palavras do artigo | § |
|---|---|---|
| Tempo em produção | “more than 5 years” (mais de 5 anos) | 4 |
| Namespaces | “more than 1,500 namespaces defined by hundreds of client applications” (mais de 1.500 namespaces definidos por centenas de aplicações clientes) | 4 |
| Tuplas | “more than 2 trillion relation tuples that occupy close to 100 terabytes” (mais de 2 trilhões de tuplas de relação que ocupam cerca de 100 terabytes) | 4 |
| Replicação | “fully replicated in more than 30 locations around the world” (totalmente replicados em mais de 30 locais ao redor do mundo) | 4 |
| Carga dos clientes | “more than 10 million client queries per second (QPS)” (mais de 10 milhões de consultas de clientes por segundo, QPS) | 4 |
| Pico por API | “Check requests peak at roughly 4.2M QPS, Read at 8.2M, Expand at 760K, and Write at 25K” (as requisições Check atingem pico de aproximadamente 4,2 milhões de QPS, Read de 8,2 milhões, Expand de 760 mil e Write de 25 mil) | 4 |
| Servidores | “more than 10,000 servers organized in several dozen clusters around the world” (mais de 10.000 servidores organizados em várias dezenas de clusters ao redor do mundo) | 4 |
| Servidores por cluster | “from fewer than 100 to more than 1,000, with the median near 500” (de menos de 100 a mais de 1.000, com mediana próxima de 500) | 4 |
| Latência de Check Safe | “At the 50th, 95th, 99th, and 99.9th percentiles it peaks at roughly 3, 11, 20, and 93 msec, respectively.” (Nos percentis 50, 95, 99 e 99,9, ela atinge pico de aproximadamente 3, 11, 20 e 93 ms, respectivamente.) | 4.2 |
| Disponibilidade | “above 99.999% over the past 3 years of operation at Google” (acima de 99,999% ao longo dos últimos 3 anos de operação no Google) | 4.3 |
| RPCs internas | “22 million internal “delegated” RPCs per second, split about evenly between reads and checks” (22 milhões de RPCs internas “delegadas” por segundo, divididas de forma aproximadamente igual entre leituras e verificações) | 4.4 |
| Consultas ao cache | “approximately 200 million lookups per second at peak, 150 million from checks and 50 million from reads” (aproximadamente 200 milhões de consultas por segundo no pico, 150 milhões vindas de verificações e 50 milhões vindas de leituras) | 4.4 |
| Leituras ao Spanner | “only 20 million read RPCs per second to Spanner” (apenas 20 milhões de RPCs de leitura por segundo ao Spanner) | 4.4 |
| Latência de leitura do Spanner | “0.5 msec at the median, and 2 msec at the 95th percentile” (0,5 ms na mediana e 2 ms no 95º percentil) | 4.4 |
| Leituras com hedging | “1% of Spanner reads, or 200K reads per second, benefit from hedging” (1% das leituras ao Spanner, ou 200 mil leituras por segundo, se beneficiam do hedging) | 4.4 |
Observe a proporção nas últimas linhas: 200 milhões de consultas ao cache por segundo contra 20 milhões de RPCs de leitura ao Spanner, cerca de dez consultas em memória para cada leitura enviada ao armazenamento.
Fontes
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3, §3.1, §3.2.3, §3.2.5–§3.2.7, §4: https://www.usenix.org/conference/atc19/presentation/pang
- Karger et al., “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, STOC ’97 (ref. [20] do artigo): https://people.csail.mit.edu/karger/Papers/web.pdf
- Dean e Barroso, “The Tail at Scale”, Communications of the ACM 56(2), 2013 (ref. [16] do artigo): https://research.google/pubs/the-tail-at-scale/
- “Cache stampede”, Wikipedia, conforme citado pelo artigo (ref. [3]): https://en.wikipedia.org/wiki/Cache_stampede
- Adya et al., “Slicer: Auto-sharding for datacenter applications”, OSDI ’16 (ref. [12] do artigo): https://www.usenix.org/conference/osdi16/technical-sessions/presentation/adya
- Corbett et al., “Spanner: Google’s globally-distributed database”, OSDI ’12 (ref. [15] do artigo): https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf