50 anos depois, o Two-Phase Locking ainda é a melhor opção?
(concurrencyfreaks.blogspot.com)- O Two-Phase Locking (2PL), apresentado em 1976, oferece Opacity, que é mais forte que serializabilidade, mas mesmo após cerca de 50 anos ainda tem limitações de escalabilidade de leitura e garantias de progresso
- Com regras simples de aquisição e liberação de locks, ele processa transações com vários registros enquanto fornece níveis fortes de isolamento, por isso ainda é amplamente usado em bancos de dados transacionais comerciais e estruturas de dados concorrentes
- O 2PL tradicional pode fazer até leituras entrarem em conflito por causa de locks de exclusão mútua, e mesmo com reader-writer locks surge contenção no read-indicator em pontos com concentração de leituras, como a raiz de uma árvore de busca binária
- O 2PLSF reduz a contenção na aquisição de read lock ao distribuir a marcação de cada reader por cache lines, e aplica fetch_and_add() em um contador atômico central apenas às transações que entraram em conflito
- Variantes de 2PL como No-Wait, Deadlock-detection e Wait-Or-Die ainda deixam problemas de live-lock ou escalabilidade, e o 2PLSF é uma melhoria voltada a escalabilidade de leitura junto com transações starvation-free
Por que o 2PL ainda importa
- O Two-Phase Locking (2PL) é um dos primeiros controles de concorrência de uso geral a oferecer serializabilidade (Serializability) e, na prática, fornece o nível de isolamento mais forte chamado Opacity
- O 2PL foi publicado em 1976 no artigo de Jim Gray e colegas, e a ideia em si pode ser ainda anterior, então é tratado como uma técnica com quase 50 anos
- Controle de concorrência de uso geral significa um algoritmo que permite transações com semântica all-or-nothing sobre vários itens de dados, como objetos, registros e tuplas
- A vantagem do 2PL está na simplicidade e no forte isolamento
- Antes de ler ou escrever um registro, primeiro se adquire o lock que protege esse registro
- Os locks adquiridos são mantidos até o fim da transação, o que permite formar uma visão consistente
O isolamento criado por regras simples
- No 2PL, um lock é adquirido a cada acesso durante a transação, e todos os locks são liberados no encerramento da transação, quando se sabe que não haverá mais acessos
- Nesse momento final, todos os locks dos dados acessados estão mantidos, o que cria um ponto de linearização (linearization point) para aquela transação
- Há 50 anos, muitos pesquisadores de banco de dados achavam que era aceitável liberar o lock logo após terminar o acesso ao registro, mas esse tipo de controle de concorrência não é serializável
- Bancos de dados transacionais comerciais conhecidos usam 2PL ou T/O, em combinação com MVCC
- Na área de estruturas de dados concorrentes, linearizability é praticamente o padrão, e para escrever de forma consistente em vários nós normalmente é preciso algo como 2PL para acessos de escrita
- A exceção são estruturas de dados lock-free, mas destaca-se que implementações lock-free corretas são difíceis
Gargalos do 2PL: escalabilidade de leitura e live-lock
- As grandes fraquezas do 2PL são a baixa escalabilidade de leitura e as garantias de progresso em live-lock
- O 2PL clássico foi pensado com base em locks de exclusão mútua, então mesmo que duas threads apenas leiam o mesmo registro, elas podem entrar em conflito e uma ou ambas podem abortar e reiniciar
- Ao trocar por reader-writer locks, os conflitos entre leituras diminuem, mas o custo do lock e o uso de memória aumentam
- Um lock de exclusão mútua pode ser implementado com 1 bit para indicar estado travado/liberado
- Um reader-writer lock precisa, além desse bit, de um contador para o número de readers que atualmente possuem o lock em modo de leitura
- Por exemplo, um contador de 7 bits pode representar até 128 threads, e cada lock pode ocupar 1 byte
- Se um banco de dados tiver bilhões de registros, só os locks já exigirão bilhões de bytes
- Um problema ainda maior é a contenção no contador
- Em workloads read-non-disjoint, muitas leituras se concentram nos mesmos dados
- O nó raiz de uma árvore de busca binária é um exemplo típico, porque toda operação precisa lê-lo antes de descer para os nós inferiores
- No 2PL, cada acesso à raiz exige adquirir lock, e mesmo usando reader-writer lock há forte contenção no lock do nó raiz
Abordagens existentes e read-indicator escalável
- O TLRW é uma abordagem apresentada por Dave Dice e Nir Shavit na SPAA 2010 que, usando reader-writer lock, melhorou o desempenho em relação a locks de exclusão mútua, embora ainda não seja tão rápida quanto controle de concorrência otimista
- De forma semelhante ao TLRW, se uma implementação em que cada acesso de leitura disputa uma única variável do reader-writer lock for aplicada a uma árvore de busca binária Rank-based Relaxed AVL, a escalabilidade da maioria das transações, sejam de escrita ou de leitura, fica praticamente estagnada
- A contenção no read-indicator pode ser amenizada com um read-indicator escalável
- A abordagem preferida é um reader-writer lock em que cada reader marca sua chegada e saída em uma cache line separada
- A aquisição de read lock deixa de ter contenção
- A thread que quer obter write lock precisa escanear todas as cache lines para verificar se o lock pode ser concedido, então o custo de aquisição do write lock aumenta
- NUMA Aware reader-writer locks trata de algoritmos de reader-writer lock que usam essa técnica
- Dois dos três algoritmos de reader-writer lock têm alta escalabilidade, mas não são starvation-free
O design de reader-writer lock do 2PLSF
- Two-Phase Locking Starvation-Free (2PLSF) é um controle de concorrência implementado com um reader-writer lock que escala bem na aquisição de read lock e tem propriedades adicionais
- O reader-writer lock do 2PLSF reserva 1 bit por thread para o read lock
- Esses bits são colocados em suas próprias cache lines
- Eles são posicionados junto com os bits de read-indicator de locks adjacentes
- Assim como no artigo sobre reader-writer locks NUMA-aware, o custo é deslocado para a aquisição do write lock
- O write lock precisa escanear várias cache lines
- Não é uma solução mágica, e sim um trade-off
- Esse trade-off é útil porque a maioria dos workloads tende a ser read-heavy, e mesmo workloads write-intensive passam bastante tempo em acessos de leitura, como na etapa de busca por registros
- Com o reader-writer lock aprimorado, o 2PL pode escalar mesmo em workloads read-non-disjoint, mas o problema de live-lock ainda precisa ser resolvido separadamente
Problemas de garantia de progresso que permanecem nas variantes de 2PL
- O 2PL clássico tem variantes conhecidas como No-Wait, Deadlock-detection e Wait-Or-Die, dependendo de como tratam contenção
-
No-Wait
- Quando ocorre conflito, a própria transação ou a transação adversária é abortada e tentada novamente
- A nova tentativa pode ser imediata ou posterior, com backoff exponencial
- Se uma transação quiser modificar o registro A e depois B, e outra quiser modificar B e depois A, elas podem continuar colidindo e repetindo abort-restart sem que nenhuma consiga fazer commit, o que caracteriza progresso por live-lock
-
Deadlock-detection
- Mantém listas de threads esperando por locks e detecta ciclos, isto é, deadlocks
- Em reader-writer locks, cada reader precisa ter sua própria lista, e também é necessário um lock de exclusão mútua para proteger cada lista
- Como é preciso escanear todas as listas de readers ao adquirir o lock em modo read-lock, o custo aumenta
- Em teoria pode ser starvation-free, mas isso exigiria locks starvation-free, e não há reader-writer locks públicos de alta escalabilidade e starvation-free, o que entra em conflito com o objetivo
- Ter uma lista por reader também pode aumentar o uso de memória
-
Wait-Or-Die
- Todas as transações recebem uma ordem, e quando há conflito de lock a decisão entre esperar ou abortar é tomada comparando o timestamp da transação com o timestamp do dono do lock
- Em locks de exclusão mútua, isso funciona bem porque o proprietário pode ser armazenado dentro do lock como um identificador único de thread
- Para fazer o mesmo com reader-writer lock, seria necessário um thread-id para cada reader
- Para suportar 256 threads, seriam necessários 8 bits × 256 = 256 bytes por reader-writer lock
O gargalo do contador atômico central e a diferença do 2PLSF
- Um obstáculo ainda maior do Wait-Or-Die é que toda transação precisa ter um ID de transação único
- Por exemplo, é possível criar essa ordem obtendo números de uma variável atômica central com fetch_and_add()
- Na maioria das CPUs modernas, é difícil executar mais de 40 milhões de fetch_and_add() por segundo em uma variável atômica contendida
- Em comparação com cerca de 660 milhões de transações por dia da Visa, isso pode parecer muito
- Mas para DBMS em memória ou estruturas de dados concorrentes, pode não ser suficiente
- Em uma máquina de teste, foi difícil passar de 20 milhões de fetch_and_add() por segundo
- Esse fetch_and_add() é necessário não só para transações de escrita, mas para todas as transações, inclusive as de leitura, o que limita a escalabilidade
- O TL2 faz leituras otimistas sem fetch_and_add() atômico para transações de leitura
- Pode escalar para centenas de milhões de tps no caso de transações de leitura
- Já o 2PL baseado em Wait-Or-Die não consegue ultrapassar 40M tps/sec
- O 2PLSF ordena apenas as transações que entram em conflito
- Assim, diminui o número de transações que fazem fetch_and_add() em uma variável atômica central
- Transações sem conflito não ficam presas ao platô de 40M tps
- Por exemplo, 200M tps sem conflito podem continuar rodando, enquanto apenas 40M tps em conflito ficam limitados pelo fetch_and_add()
- O algoritmo oferece starvation-freedom
Materiais e avaliação final
- O algoritmo 2PLSF em si não é detalhado a fundo, mas é avaliado como relativamente simples para um algoritmo starvation-free
- São fornecidos artigo e código-fonte como referência
- Artigo: https://zenodo.org/record/7886718
- Código-fonte: https://github.com/pramalhe/2PLSF/blob/main/stms/2PLSF.hpp
- O 2PLSF também aparece ligado a um artigo da ACM e é resumido como um algoritmo criado por Pedro Ramalhete, Andreia e Pascal Felber
- O objetivo do 2PLSF é se aproximar das propriedades que o 2PL deveria ter tido desde o início
- Escala bem mesmo em situações read-non-disjoint, nas quais as leituras se sobrepõem
- Fornece transações starvation-free, a forma mais forte de blocking progress
- Pode manter escalabilidade mesmo em alguns cenários com conflito
- O 2PLSF não é perfeito, mas é avaliado como melhor que o TL2 no aspecto de resolução de conflitos, e a diferença em relação ao 2PL tradicional é comparada à diferença entre uma picareta e uma britadeira
1 comentários
Opiniões no Hacker News
Fico me perguntando quais são as melhores práticas do setor para sincronizar, ou manter “consistentes”, vários armazenamentos de dados em uma arquitetura distribuída de microsserviços
Alguns dias atrás tentei resolver o problema de inconsistência com um “settled timestamp”; é algo próximo de uma abordagem multiversão em que, se o tempo passa sem relatório de erro, aquilo é considerado um armazenamento/commit válido. No two-phase commit, a segunda fase seria o tempo
A ideia era observar os relógios de outros servidores e, se eles não fossem atualizados, não confiar no settled timestamp daquele servidor; como a cada atualização não seria necessário esperar uma resposta, mas apenas aguardar a próxima faixa de timestamp, a intenção era escalar a consistência para muitos servidores
Criei um código Python multithread e multiprocessamento, com 10 threads trocando atualizações aleatórias, para testar a não determinismo: https://replit.com/@Chronological/InconsistencySimulation#ma...
Nessa simulação, uma leitura é o menor valor entre todos os timestamps relatados por todos os servidores; se, depois de 10 segundos, eu perguntar a cada thread o valor do contador, às vezes todas retornam o mesmo valor, mas com bastante frequência entram em estado de split-brain
Sei que, em sistemas distribuídos, timestamps de wall clock não são adequados para determinar ordem, e que é preciso usar relógios lógicos ou relógios vetoriais
Seria bom conseguir fazer a simulação relatar o mesmo número em qualquer momento. Bloomlang tenta resolver, em consistência eventual, o problema em que valores que chegam atrasados afetam o resultado, impedindo linearizabilidade
Tenho interesse especial em escalar mantendo consistência, mas isso parece um problema bem difícil
Vários sistemas escrevem sequencialmente no journal central, e o journal recebe requisições como um armazenamento chave-valor. Esse journal é replicado para todos os nós, e os nós leem o journal para executar a lógica complexa solicitada
Como Kubernetes usa etcd, ele escala razoavelmente bem como armazenamento chave-valor com consistência forte
Como você disse “vários armazenamentos de dados”, estou presumindo que há dados heterogêneos e que opções como CockroachDB não se aplicam
Se você é iniciante, construir isso por conta própria é arriscado. https://aphyr.com/ é praticamente uma referência em testes e também é excelente para fins educacionais. É possível testar sistemas distribuídos com Jepsen, mas é melhor usar um armazenamento de dados que o Kyle já demonstrou ser robusto
Não sou familiarizado com essas técnicas, mas, quando estudei bancos de dados, SSI foi apresentado como o “melhor” two-phase locking do futuro. Gostaria de saber como SSI difere de 2PLSF e por que não foi mencionado aqui
Mas, para efeitos distribuídos, ainda são necessários locks, transações em duas fases etc. Pessoalmente, vejo isso mais como recursos complementares do que como substitutos
Para estruturas de dados em memória, isso é natural; mas, se você estiver lidando com um banco de dados externo ou outro recurso externo compartilhado, pode haver uma abordagem melhor
Muitas vezes é possível processar requisições em lote para acessar o recurso externo com menor concorrência e payloads maiores. Se esse recurso lida bem com lotes, a concorrência e o locking necessários caem bastante
Por exemplo, se você usa Postgres, isso pode reduzir o número de conexões e evitar a necessidade de adicionar o PgBouncer, que aumenta a complexidade
Porém, batching de requisições não combina bem com a maioria das linguagens de programação. Linguagens otimizadas para alta concorrência, como canais em Go ou processos em Elixir, conseguem fazer isso bem, mas pode ser doloroso em linguagens que tratam tudo como threads
Em sites que não podem ser atualizados para HTTPS, aparece um alerta; em sites que oferecem ambos, ele vai direto para a versão HTTPS
E, se o link HTTP for sobre bons algoritmos de concorrência, ainda assim eu vou ler
fetch_and_addpara obter o ID da transação? Para começo de conversa, questiono se um ID de transação é necessárioO objetivo parece ser estabelecer uma ordem arbitrária, mas consistente, entre transações ativas para que, em caso de conflito, elas possam concordar entre si sobre quem espera e quem morre. Então não daria para usar o ID da thread?
Um número aleatório também poderia funcionar. Se empates forem tratados como “morte”, no pior caso ambas as transações seriam abortadas desnecessariamente e apenas tentariam de novo com um novo número aleatório
Não foi mencionado, mas parece que a ideia é dar prioridade a transações mais antigas para que transações de longa duração não sofram starvation por causa de transações curtas. Por exemplo, se uma transação longa conflita, em média, com três transações curtas, e em cada conflito o vencedor é efetivamente aleatório, a probabilidade de a transação longa vencer as três vezes e fazer commit é de apenas 1/8
Mas, para evitar starvation, não é preciso priorizar a transação mais antiga todas as vezes; na maioria dos casos já é suficiente. Especialmente se ela for só um pouquinho mais antiga
Portanto, algo como um timestamp ou cycle counter pode funcionar bem mesmo havendo desvios de relógio entre threads ou outras imprecisões. Empates podem ser desfeitos pelo ID da thread, ou, novamente, fazendo ambas abortarem
Ele se encaixa bem neste caso e em muitos outros
O commit em duas fases é algo comparável ao Paxos, e ambos se enquadram na categoria de protocolos de consenso
O bloqueio em duas fases é um mecanismo de controle de concorrência
Quando a primeira mensagem de lock desaparece, o problema é: como saber que o que se perdeu não foi a mensagem de resposta?
Em casos simples, como GitHub ou Dropbox, dá para simplesmente seguir em frente e resolver o conflito depois. Se for um banco de dados, boa sorte; se for um banco, ainda mais
Em uma transação somente leitura, o TL2 só precisa amostrar a versão global e, para cada leitura, verificar se a versão local é menor ou igual à versão amostrada
Então é difícil entender por que o gráfico é sublinear e por que o TL2 não é tão rápido quanto outras implementações de STM
Por exemplo, suponha que normalmente haja 1000 tarefas e 10 a 100 threads de hardware
Crie uma lista ordenada dessas 1000 tarefas, faça uma cópia dela para cada thread e, a cada vez, randomize a ordem da cópia
Então cada thread pode ler sua própria lista e executar as tarefas, e depois assinar uma lista implementada como uma fila multithread não bloqueante
No pior caso, algumas threads podem executar repetidamente uma determinada tarefa
Com esse método, operações atômicas poderiam escalar até 1000 vezes