Conceitos
Transações distribuídas com snapshot isolation sobre armazenamento com atomicidade só por linha (Percolator)
Intuição
Imagine uma planilha gigante em que várias pessoas editam ao mesmo tempo e a única garantia é que cada linha, sozinha, muda de uma vez. Para alterar várias linhas como se fossem uma só, você cola um aviso de reserva em cada uma delas e escolhe um dos avisos como o principal; só quando todas estão reservadas você vira o aviso principal, e é essa virada que faz a mudança valer para todo mundo. Quem só quer ler consulta a planilha como ela estava num instante fixo, então nunca vê metade da mudança; e se quem estava mudando some no meio do caminho, o aviso principal mostra a qualquer outra pessoa se a mudança chegou a valer ou não.
Como funciona
O Bigtable só oferece atomicidade dentro de uma única linha, então o Percolator, uma biblioteca cliente, acrescenta as transações entre linhas e tabelas com isolamento de snapshot. Para as transações, cada coluna do Percolator usa três colunas do Bigtable (data, lock e write; o paper lista ainda notify e ack, usadas pelos observers), com as células versionadas por timestamp; um oráculo fornece timestamps estritamente crescentes, e cada transação lê num timestamp inicial e escreve num timestamp de commit posterior. As escritas ficam em buffer até o commit, que é em duas fases e coordenado pelo cliente: no prewrite, a transação tenta travar todas as células escritas, escolhe uma delas como primária e aborta se encontrar um registro write posterior ao seu timestamp inicial ou qualquer lock; senão grava o dado e o lock, e cada lock secundário guarda a localização do primário. Na segunda fase, ela obtém o timestamp de commit e troca o lock da primária por um registro write que aponta para o dado, e essa troca, feita numa transação de linha do Bigtable, é o ponto de commit; depois faz o mesmo nas secundárias. Como qualquer timestamp representa um snapshot consistente, as leituras não precisam adquirir locks: um Get() só verifica se há lock no intervalo visível do snapshot e, se houver, espera; senão, lê o último write visível. Se o cliente cai no meio do commit, outra transação que encontra o lock abandonado inspeciona a primária: se ela já virou um registro write, avança o commit (roll forward); caso contrário, faz rollback, o que é seguro porque a primária sempre é confirmada primeiro e porque tanto a limpeza quanto o commit precisam modificar a primária, cada um dentro de uma transação de linha do Bigtable, então só um dos dois tem sucesso. Se duas transações concorrentes escrevem na mesma célula, no máximo uma confirma, mas isso é isolamento de snapshot e não serializabilidade, portanto fica sujeito a write skew. Não há gerência central de transações nem detector global de deadlock, e a limpeza preguiçosa de locks pode adiar um commit em dezenas de segundos.
Na prática
O paper aplica essa técnica ao indexador do Google, onde as invariantes entre muitas linhas (como as duplicatas de URL e a inversão de links) precisam ser mantidas enquanto páginas novas chegam. Faz sentido escolhê-la quando é preciso atomicidade entre linhas sobre um armazenamento que escala bastante mas só tem atomicidade por linha, a carga tolera latência mais alta e o write skew não ameaça as invariantes. O custo é medido no paper: a escrita de uma única célula, o pior caso de sobrecarga para o Percolator, tem sobrecarga de cerca de quatro vezes sobre o Bigtable puro num benchmark com um único tablet server, dados em cache e as otimizações de batching desligadas, sem contar o custo de obter timestamps do oráculo, por causa das operações extras do commit (ler para checar locks, gravar o lock e depois removê-lo), das quais a leitura é a mais cara.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.