Escalando o controle de simultaneidade otimista em multicores

Este artigo do SIGMOD 2016 propõe uma abordagem de recuperação de transações para melhorar a escalabilidade do Optimistic Concurrency Control (OCC) em sistemas OLTP de memória principal executados em arquiteturas multicore. Em vez de descartar toda a execução quando a validação falha, o sistema repara apenas as operações inconsistentes para melhorar o rendimento em cenários de alta contenção.

Se isto lhe parece familiar, é porque revisámos recentemente o artigo Morty do EuroSys 2023, que aplicou ideias curativas a transações interativas usando continuações para apoiar a reexecução. Este artigo sobre Transaction Healing de 2016 tem como escopo procedimentos armazenados estáticos e se concentra mais na integração da recuperação no OCC para procedimentos armazenados.

Ideias-chave

OCC funciona bem sob baixa contenção porque separa leituras de gravações e mantém seções críticas curtas (apenas para validação). Mas sob alta contenção, especialmente em cargas de trabalho com padrões de acesso distorcidos (como distribuições Zipfian), as transações são frequentemente invalidadas por atualizações simultâneas. A resposta ingênua do OCC de abortar e reiniciar leva ao desperdício de ciclos de CPU e à degradação da localidade do cache.

A cura de transações visa resolver esse problema observando/apostando que a maioria das falhas de validação afetam apenas um subconjunto das operações de uma transação. Se apenas as operações afetadas puderem ser detectadas e recuperadas, o sistema poderá evitar refazer toda a transação. Eles implementam isso aproveitando dois componentes.

Primeiro, uma fase de análise estática extrai dependências de operação do procedimento armazenado a priori. A análise de dependência distingue dois tipos de relações: dependências-chave, onde o resultado de uma operação determina a chave de consulta para outra; e dependências de valor, onde o valor produzido por uma operação é usado em uma operação subsequente. Com este gráfico em mãos, a recuperação de transações pode reparar cirurgicamente qualquer operação não serializável em tempo de execução.

Segundo, um cache de acesso em tempo de execução, mantido por thread, rastreia o comportamento de cada operação executada (suas entradas, saídas, efeitos e os endereços de memória acessados) e identifica partes conflitantes de uma transação em tempo de execução. O cache de acesso suporta isso registrando endereços de memória (evitando pesquisas repetidas de índice) e permitindo a reutilização eficiente de resultados não afetados.

Cura de transação

O processo de recuperação é acionado durante a fase de validação, quando uma inconsistência é detectada no conjunto de leitura/gravação. Em vez de abortar imediatamente, o sistema identifica a primeira operação afetada (utilizando o seu gráfico de dependência) e restaura-a. Se a operação depender de valor, a reparação atualiza seus efeitos com base nas entradas e saídas armazenadas em cache. Se for dependente de chave, é necessária uma reexecução, pois o registro acessado pode mudar. A recuperação se propaga através do gráfico de dependência, restaurando recursivamente todas as operações afetadas pela inconsistência inicial.

O mecanismo de recuperação foi criado para preservar a serialização. A validação adquire bloqueios em uma ordem globalmente consistente (por exemplo, classificados por endereço de memória) para evitar conflitos. Se durante a recuperação um bloqueio precisar ser adquirido fora de ordem (por exemplo, devido a novas dependências introduzidas por operações reexecutadas), a transação será abortada para não correr o risco de um impasse. O artigo diz que esta situação é rara devido às otimizações da ordem de validação. Apesar dos abortos ocasionais, a recuperação da transação garante o progresso e eventual encerramento: o conjunto de leitura/gravação de cada transação é finito e cada elemento é validado no máximo uma vez, o que garante que a recuperação seja bem-sucedida ou falhe definitivamente.

Destaques da avaliação

Eles implementaram um mecanismo de banco de dados em memória C++, THEDB, para testar essas ideias. THEDB emprega LLVM para realizar análise de dependência estática em procedimentos armazenados e inclui suporte para recursos de banco de dados padrão, como inserções, exclusões e consultas de intervalo (estas últimas protegidas contra fantasmas por meio de controle de versão de árvore B+, como no Silo). Os autores avaliam o THEDB em uma máquina AMD de 48 núcleos usando dois benchmarks comuns: TPC-C e Smallbank. THEDB é comparado com cinco sistemas: variantes de OCC (incluindo estilo Silo), 2PL, uma abordagem híbrida OCC-2PL e um sistema particionado determinístico.

Os resultados mostram que, sob alta contenção, o THEDB supera significativamente as alternativas, alcançando um rendimento até 6,2x maior que o Silo e aproximando-se do desempenho de um sistema OCC idealizado com validação desabilitada. Isso mostra que a recuperação de transações adiciona sobrecarga mínima e elimina com êxito os custos de reinicialização que dominam o desempenho do OCC sob carga. Além disso, o THEDB mantém um rendimento estável à medida que a contenção aumenta (por exemplo, sob distribuições Zipfian mais distorcidas), enquanto o OCC e o Silo tradicionais se degradam rapidamente. A escalabilidade também é ótima até 48 núcleos.

Discussão

**** Quais são as limitações da análise estática utilizada?

A recuperação de transações proposta aqui é limitada a procedimentos armazenados porque depende da extração de dependência estática. Ao contrário do Morty, que lida com transações interativas usando continuações de tempo de execução, este trabalho não pode lidar com fluxo de controle dinâmico ou lógica de transação desconhecida em tempo de execução. Como resultado, as consultas ad hoc revertem para o OCC padrão, onde qualquer benefício de cura é perdido.

Por outro lado, há alguma sutileza aqui. A cura de transações não exige que conjuntos de leitura/gravação sejam declarados antecipadamente, como fazem os sistemas determinísticos como Calvin. Os sistemas determinísticos devem saber os registros exatos que uma transação acessará antes de iniciar a execução, para que possam atribuir transações a partições e estabelecer uma ordem de execução global. A cura de transações evita essa rigidez. Não é necessário saber antecipadamente quais registros específicos uma transação acessará. Em vez disso, baseia-se na análise estática para extrair a estrutura da lógica da transação, nomeadamente quais operações dependem de quais outras. Essas dependências, como dependências de chave ou valor entre operações, são conhecidas estaticamente porque a lógica da transação é escrita como um procedimento armazenado. Mas as chaves e os valores reais envolvidos são descobertos dinamicamente à medida que a transação é executada. O sistema usa um cache de acesso para registrar quais locais de memória foram lidos ou gravados, e a validação ocorre posteriormente. Essa flexibilidade permite que a recuperação de transações suporte padrões de acesso dinâmicos entre partições sem declaração prévia.

**** Como isso se compara ao Morty?

O Transaction Healing foi projetado para sistemas OLTP na memória executados com OCC em máquinas multicore, onde a carga de trabalho consiste em procedimentos armazenados estáticos. Morty, por outro lado, foi desenvolvido para um sistema distribuído geo-replicado e lida com transações interativas com fluxo de controle dinâmico. Utiliza MVTSO, com execução especulativa e ordenação a priori. Ao contrário do THEDB, o Morty permite que as transações leiam versões não confirmadas, expondo a simultaneidade que os sistemas tradicionais suprimem. Ele rastreia a execução por meio do estilo de passagem de continuação (CPS) para tornar explícitas as dependências de controle e permitir a reexecução parcial de ramificações lógicas. Embora a recuperação de transações empregasse o LLVM para executar automaticamente a análise de dependência estática em procedimentos armazenados, Morty não automatizou a tradução do programa de transação para o programa CPS. Por fim, como é distribuído e implantado pela WAN, o Morty integra o controle de simultaneidade com a replicação para reduzir a latência e usa votação de quorum para manter a correção tolerante a falhas sem registro centralizado.