Pedido de compromisso - Commitment ordering

O pedido de compromisso ( CO ) é uma classe de técnicas de serialização interoperáveis no controle de simultaneidade de bancos de dados , processamento de transações e aplicativos relacionados. Ele permite implementações otimistas (sem bloqueio). Com a proliferação de processadores multi-core , o CO também tem sido cada vez mais utilizado em programação simultânea , memória transacional e memória transacional de software (STM) para atingir serializabilidade de maneira otimista . CO também é o nome da propriedade de agendamento de transação resultante (histórico), definida em 1988 com o nome atomicidade dinâmica . Em uma programação compatível com CO, a ordem cronológica dos eventos de confirmação das transações é compatível com a ordem de precedência das respectivas transações. CO é um amplo caso especial de serializabilidade de conflito e meios eficazes ( confiável , de alto desempenho, distribuído e escalonável ) para alcançar serializabilidade global (serializabilidade modular) em qualquer coleção de sistemas de banco de dados que possivelmente usam diferentes mecanismos de controle de simultaneidade (CO também torna cada compatível com a serializabilidade do sistema, se ainda não).

Cada sistema de banco de dados não compatível com CO é aumentado com um componente CO (o coordenador do pedido de confirmação - COCO) que ordena os eventos de confirmação para conformidade com CO, sem acesso a dados nem qualquer outra interferência de operação de transação. Como tal, CO fornece uma baixa sobrecarga, solução geral para serializabilidade global (e serializabilidade distribuída), instrumental para controle de simultaneidade global (e controle de simultaneidade distribuída ) de sistemas de múltiplos bancos de dados e outros objetos transacionais , possivelmente altamente distribuídos (por exemplo, dentro da computação em nuvem , computação em grade e redes de smartphones ). Um protocolo de comprometimento atômico (ACP; de qualquer tipo) é parte fundamental da solução, utilizado para quebrar ciclos globais no gráfico de conflito (precedência, serializabilidade). CO é a propriedade mais geral (uma condição necessária ) que garante serializabilidade global, se os sistemas de banco de dados envolvidos não compartilham informações de controle de simultaneidade além de mensagens de protocolo de confirmação atômica (não modificado) e não têm conhecimento se as transações são globais ou locais (os sistemas de banco de dados são autônomos ). Assim, CO (com suas variantes) é a única técnica geral que não requer a distribuição normalmente cara de informações de controle de simultaneidade local (por exemplo, relações de precedência local, bloqueios, carimbos de data / hora ou tickets). Ele generaliza a propriedade popular de bloqueio estrito estrito de duas fases (SS2PL), que em conjunto com o protocolo de confirmação de duas fases (2PC), é o padrão de fato para atingir a serialização global em sistemas de banco de dados (baseados em SS2PL). Como resultado, os sistemas de banco de dados compatíveis com CO (com quaisquer tipos diferentes de controle de simultaneidade) podem se juntar de forma transparente a tais soluções baseadas em SS2PL para serialização global.

Além disso, deadlocks globais baseados em bloqueio são resolvidos automaticamente em um ambiente multi-banco de dados baseado em CO, um benefício colateral vital (incluindo o caso especial de um ambiente totalmente baseado em SS2PL; um fato previamente despercebido para SS2PL).

Além disso, o pedido de compromisso estrito (SCO; Raz 1991c ), a interseção de Strictness e CO, fornece melhor desempenho (menor tempo médio de conclusão de transação e resultando em melhor taxa de transferência de transação ) do que SS2PL sempre que conflitos de leitura e gravação estão presentes (comportamento de bloqueio idêntico para gravação - conflitos de leitura e gravação / gravação; sobrecarga de bloqueio comparável). A vantagem do SCO é especialmente durante a contenção de bloqueio. A rigidez permite que o SS2PL e o SCO usem os mesmos mecanismos eficazes de recuperação de banco de dados .

Existem duas variantes generalizantes principais de CO, CO estendido (ECO; Raz 1993a ) e CO multi-versão (MVCO; Raz 1993b ). Eles também fornecem serializabilidade global sem distribuição de informações de controle de simultaneidade local, podem ser combinados com qualquer controle de simultaneidade relevante e permitem implementações otimistas (sem bloqueio). Ambos usam informações adicionais para relaxar as restrições de CO e obter melhor concorrência e desempenho. A ordenação de votos (VO ou CO generalizado (GCO); Raz 2009 ) é um conjunto de programação de contêiner (propriedade) e técnica para CO e todas as suas variantes. O VO local é necessário para garantir a serialização global se os participantes do protocolo de comprometimento atômico (ACP) não compartilham informações de controle de simultaneidade (têm a propriedade de autonomia generalizada ). CO e suas variantes interoperam de forma transparente, garantindo serializabilidade global e resolução automática de deadlock global juntos em um ambiente misto e heterogêneo com diferentes variantes.

Visão geral

A ordenação Compromisso (CO; Raz 1990 , 1992 , 1994 , 2009 ) propriedade programação tem sido referido também como atomicidade dinâmico (desde 1988), cometer ordenação , comprometer a seriação ordem , e recuperabilidade forte (desde 1991). O último é um nome enganoso, uma vez que CO é incomparável com capacidade de recuperação e o termo "forte" implica um caso especial. Isso significa que uma propriedade de recuperabilidade substancial não tem necessariamente a propriedade CO e vice-versa.

Em 2009, o CO foi caracterizado como um importante método de controle de concorrência, juntamente com os três métodos principais anteriormente conhecidos (desde os anos 1980): Bloqueio , ordem de registro de data e hora e teste de gráfico de serialização , e como um habilitador para a interoperabilidade de sistemas usando diferentes mecanismos de controle de concorrência.

Em um sistema de banco de dados federado ou qualquer outro sistema de vários bancos de dados definido de forma mais flexível, que são normalmente distribuídos em uma rede de comunicação, as transações abrangem vários bancos de dados e possivelmente Distribuídos . Impor a serialização global em tal sistema é problemático. Mesmo que toda programação local de um único banco de dados ainda seja serializável, a programação global de um sistema inteiro não é necessariamente serializável. As trocas massivas de comunicação de informações de conflito necessárias entre bancos de dados para alcançar a serialização de conflitos levariam a um desempenho inaceitável, principalmente devido à latência do computador e da comunicação . O problema de alcançar a serialização global efetivamente havia sido caracterizado como aberto até a divulgação pública do CO em 1991 por seu inventor Yoav Raz ( Raz 1991a ; ver também serializabilidade global ).

A aplicação de CO é uma maneira eficaz de impor a serialização de conflitos globalmente em um sistema distribuído, uma vez que a aplicação de CO localmente em cada banco de dados (ou outros objetos transacionais) também o aplica globalmente. Cada banco de dados pode usar qualquer tipo, possivelmente diferente, de mecanismo de controle de concorrência. Com um mecanismo local que já fornece serializabilidade de conflito, impor CO localmente não causa quaisquer outros abortos, uma vez que impor CO localmente não afeta a estratégia de agendamento de acesso a dados do mecanismo (este agendamento determina os abortos relacionados à serializabilidade; tal mecanismo normalmente não considere os eventos de compromisso ou seu pedido). A solução CO não requer sobrecarga de comunicação, uma vez que usa mensagens de protocolo de confirmação atômica (não modificadas) , já necessárias para cada transação distribuída para atingir a atomicidade. Um protocolo de confirmação atômica desempenha um papel central no algoritmo de CO distribuído, que impõe CO globalmente, quebrando os ciclos globais (ciclos que abrangem dois ou mais bancos de dados) no gráfico de conflito global. CO, seus casos especiais e suas generalizações são interoperáveis ​​e alcançam serializabilidade global enquanto são utilizados juntos de forma transparente em um único ambiente distribuído heterogêneo que compreende objetos com mecanismos de controle de simultaneidade possivelmente diferentes. Como tal, o pedido de compromisso , incluindo seus casos especiais, e junto com suas generalizações (ver variantes CO abaixo), fornece uma solução geral, de alto desempenho e totalmente distribuída (nenhum componente de processamento central ou estrutura de dados central são necessários) para garantir a serialização global em ambientes heterogêneos de sistemas de bancos de dados múltiplos e outros objetos transacionais múltiplos (objetos com estados acessados ​​e modificados apenas por transações; por exemplo, na estrutura de processos transacionais e na computação em nuvem e computação em grade). A solução CO aumenta com o tamanho da rede e o número de bancos de dados sem nenhum impacto negativo no desempenho (assumindo que as estatísticas de uma única transação distribuída, por exemplo, o número médio de bancos de dados envolvidos em uma única transação, permanecem inalteradas).

Com a proliferação de processadores Multi-core , Optimistic CO (OCO) também tem sido cada vez mais utilizado para alcançar serializabilidade na memória transacional de software, e vários artigos STM e patentes utilizando "ordem de confirmação" já foram publicados (por exemplo, Zhang et al. 2006 )

A solução de pedido de compromisso para serializabilidade global

Caracterização geral do CO

O pedido de compromisso (CO) é um caso especial de serializabilidade de conflito. O CO pode ser aplicado com mecanismos sem bloqueio (cada transação pode concluir sua tarefa sem ter seu acesso aos dados bloqueado, o que permite o controle de simultaneidade otimista ; no entanto, a confirmação pode ser bloqueada). Num calendário de CO, os eventos de autorização ( parcial ordem de precedência) das transacções correspondem à precedência ordem (parcial) das respectivas transacções no ( dirigida ) grafo de conflitos (gráfico precedência, gráfico serializabilidade), tal como induzida pelo seu acesso conflitantes operações (geralmente operações de leitura e gravação (inserir / modificar / excluir); CO também se aplica a operações de nível superior, onde elas são conflitantes se não comutativas , bem como para conflitos entre operações em dados de várias versões).

Definição: pedido de compromisso

Sejam duas transações confirmadas em uma programação, de modo que esteja em conflito com ( precede ). A programação tem a propriedade de pedido de confirmação (CO), se para cada duas dessas transações confirma antes de confirmações. ${\ displaystyle T_ {1}, T_ {2}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {1}}$ ${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

Os eventos de decisão de confirmação são gerados por um mecanismo de confirmação local ou um protocolo de confirmação atômica se diferentes processos precisarem chegar a um consenso sobre se devem ser confirmadas ou abortadas. O protocolo pode ser distribuído ou centralizado. As transações podem ser confirmadas simultaneamente se a ordem parcial de confirmação permitir (se elas não tiverem operações conflitantes). Suponha que diferentes operações conflitantes induzam diferentes ordens parciais das mesmas transações. Nesse caso, o gráfico de conflito tem ciclos e a programação violará a serializabilidade quando todas as transações em um ciclo forem confirmadas. Nesse caso, nenhum pedido parcial para eventos de confirmação pode ser encontrado. Assim, os ciclos no gráfico de conflito precisam ser quebrados abortando as transações. No entanto, qualquer programação serializável por conflito pode ser transformada em CO sem abortar qualquer transação, atrasando adequadamente os eventos de confirmação para cumprir a ordem parcial de precedência das transações.

A imposição de CO por si só não é suficiente como mecanismo de controle de simultaneidade, uma vez que CO não possui a propriedade de recuperabilidade, que também deve ser suportada.

O algoritmo de CO distribuído

Existe um algoritmo de execução de pedido de confirmação global totalmente distribuído que usa CO local de cada banco de dados participante e precisa apenas (não modificado) de mensagens do protocolo de confirmação Atômica sem comunicação adicional. O algoritmo distribuído é a combinação de processos de algoritmo CO locais (para cada banco de dados) e um protocolo de confirmação atômica (que pode ser totalmente distribuído). O protocolo de confirmação atômica é essencial para garantir a atomicidade de cada transação distribuída (para decidir se deseja confirmá-la ou abortá-la; este procedimento é sempre realizado para transações distribuídas, independentemente do controle de concorrência e CO). Um exemplo comum de protocolo de confirmação atômica é o protocolo de confirmação de duas fases , que é resiliente a muitos tipos de falha do sistema. Em um ambiente confiável, ou quando os processos geralmente falham juntos (por exemplo, no mesmo circuito integrado ), um protocolo mais simples para o compromisso atômico pode ser usado (por exemplo, um aperto de mão simples dos processos participantes da transação distribuída com algum participante especial arbitrário, mas conhecido, o coordenador da transação, ou seja, um tipo de protocolo one-phase commit ). Um protocolo de confirmação atômica chega a um consenso entre os participantes sobre se deve confirmar ou abortar uma transação distribuída (global) que abrange esses participantes. Uma etapa essencial em cada um desses protocolos é o voto SIM (explícito ou implícito) de cada participante, o que significa uma obrigação do participante votante de obedecer à decisão do protocolo, seja cometer ou abortar. Caso contrário, um participante pode abortar unilateralmente a transação por um voto NÃO explícito. O protocolo confirma a transação apenas se votos SIM forem recebidos de todos os participantes (portanto, um voto ausente é normalmente considerado um NÃO). Caso contrário, o protocolo aborta a transação. Os vários protocolos de confirmação atômica diferem apenas em suas habilidades para lidar com diferentes situações de falha de ambiente de computação e as quantidades de trabalho e outros recursos de computação necessários em diferentes situações.

Toda a solução CO para serializabilidade global é baseada no fato de que o protocolo de confirmação atômica eventualmente aborta essa transação no caso de falta de voto para uma transação distribuída.

Aplicando CO global

Em cada sistema de banco de dados, um algoritmo CO local determina a ordem de confirmação necessária para esse banco de dados. Pela caracterização do CO acima, essa ordem depende da ordem de precedência local das transações, que resulta dos mecanismos de escalonamento de acesso a dados locais. Consequentemente, votos SIM no protocolo de compromisso atômico são agendados para cada transação distribuída (não abortada) (a seguir, "um voto" significa um voto SIM). Suponha que uma relação de precedência (conflito) exista entre duas transações. Nesse caso, o segundo não será votado antes que o primeiro seja concluído (confirmado ou abortado), para evitar uma possível violação da ordem de confirmação pelo protocolo de confirmação atômica. Isso pode acontecer porque a ordem de confirmação pelo protocolo não é necessariamente a mesma que a ordem de votação. Se não houver relação de precedência, ambos podem ser votados simultaneamente. Esta estratégia de ordenação de votos garante que também o protocolo de comprometimento atômico mantenha a ordem de comprometimento, e é uma condição necessária para garantir o CO Global (e o CO local de um banco de dados; sem ele CO Global e CO Local (uma propriedade que significa que cada banco de dados é Compatível com CO) pode ser violado).

No entanto, como os sistemas de banco de dados agendam suas transações de forma independente, é possível que as ordens de precedência das transações em dois bancos de dados ou mais não sejam compatíveis (não existe uma ordem parcial global que possa incorporar as respectivas ordens parciais locais). Com o CO, as ordens de precedência também são as ordens de reserva. Quando os bancos de dados participantes na mesma transação distribuída não têm ordens de precedência local compatíveis para essa transação (sem "saber"; normalmente não existe coordenação entre os sistemas de banco de dados em conflitos, uma vez que a comunicação necessária é massiva e degrada inaceitavelmente o desempenho), isso significa que o transação reside em um ciclo global (envolvendo dois ou mais bancos de dados) no gráfico de conflito global. Neste caso, o protocolo de confirmação atômica falhará em coletar todos os votos necessários para confirmar aquela transação: Pela estratégia de ordenação de votos acima, pelo menos um banco de dados irá atrasar sua votação para aquela transação indefinidamente para cumprir sua própria ordem de compromisso (precedência) , uma vez que estará aguardando a conclusão de outro, transações anteriores nesse ciclo global atrasadas indefinidamente por outro banco de dados com uma ordem diferente. Isso significa uma situação de impasse de votação envolvendo os bancos de dados naquele ciclo. Como resultado, o protocolo acabará por abortar alguma transação em impasse neste ciclo global, uma vez que cada uma dessas transações está faltando pelo menos um voto de participante. A seleção da transação específica no ciclo a ser abortado depende das políticas de aborto do protocolo de confirmação atômica (um mecanismo de tempo limite é comum, mas pode resultar em mais de um aborto necessário por ciclo; ambos evitando abortos desnecessários e encurtamento do tempo de aborto podem ser alcançados por um mecanismo de aborto dedicado para CO). Esse aborto quebrará o ciclo global que envolve aquela transação distribuída. Ambas as transações em impasse e possivelmente outras em conflito com o impasse (e, portanto, bloqueadas) estarão livres para serem votadas. É importante notar que cada banco de dados envolvido com o impasse de votação continua a votar regularmente em transações que não estão em conflito com sua transação travada, normalmente quase todas as transações pendentes. Portanto, no caso de pedidos de confirmação locais incompatíveis (parciais), nenhuma ação é necessária, pois o protocolo de confirmação atômica o resolve automaticamente, abortando uma transação que é a causa da incompatibilidade. Isso significa que a estratégia de ordenação de votos acima também é uma condição suficiente para garantir o CO Global.

Conclui-se o seguinte:

• A estratégia de ordenação de votos para o Teorema Global do CO Enforcing

Deixe ser transações indecisas (nem confirmadas nem abortadas) em um sistema de banco de dados que impõe CO para transações locais, tais que são globais e em conflito com ( precede ). Então, ter terminado (seja confirmado ou abortado) antes de ser votado para ser confirmado (a estratégia de ordenação de votos ), em cada sistema de banco de dados em um ambiente de várias bases de dados, é uma condição necessária e suficiente para garantir o CO Global (a condição garante CO Global , que pode ser violado sem ele). ${\ displaystyle T_ {1}, T_ {2}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {1}}$ ${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

Comentários:

1. A estratégia de ordenação de votos que impõe CO global é referida como em ( Raz 1992 ). ${\ displaystyle CD ^ {3} C}$
2. A propriedade CO local de uma programação global significa que cada banco de dados é compatível com CO. Da discussão da necessidade, a parte acima segue diretamente que o teorema também é verdadeiro ao substituir "CO Global" por "CO Local" quando as transações globais estão presentes. Juntos, isso significa que o CO global é garantido se e somente se o CO local for garantido (o que não é verdade para serializabilidade de conflito global e serializabilidade de conflito local: global implica local, mas não o oposto).

CO global implica serializabilidade global.

O algoritmo Global CO compreende a imposição de CO (local) em cada sistema de banco de dados participante, ordenando commits de transações locais (consulte Impingindo CO localmente abaixo) e impondo a estratégia de ordenação de votos no teorema acima (para transações globais).

A caracterização exata dos impasses de votação por ciclos globais

O processo de eliminação do ciclo global acima por um impasse de votação pode ser explicado em detalhes pela seguinte observação:

Primeiro, presume-se, para simplificar, que toda transação atinge o estado pronto para confirmação e é votada por pelo menos um banco de dados (isso implica que não ocorre bloqueio por travamento). Defina um gráfico de "espera pelo voto para confirmar" como um gráfico direcionado com transações como nós e uma borda direcionada de qualquer primeira transação para uma segunda transação se a primeira transação bloquear o voto para confirmar da segunda transação (oposto à direção convencional da borda em um gráfico de espera ). Esse bloqueio ocorre apenas se a segunda transação entrar em conflito com a primeira transação (veja acima). Portanto, este gráfico de "espera pelo voto para confirmar" é idêntico ao gráfico de conflito global. Um ciclo no gráfico "aguarde a votação para confirmar" significa um impasse na votação. Portanto, haverá um impasse na votação se houver um ciclo no gráfico de conflito. Os mecanismos de serialização local eliminam os ciclos locais (confinados a um único banco de dados). Conseqüentemente, apenas os ciclos globais são deixados, que são então eliminados pelo protocolo de confirmação atômica quando ele aborta transações em conflito com os respectivos votos ausentes (bloqueados).

Em segundo lugar, também os commits locais são tratados: Observe que ao aplicar CO, também aguardar um commit local regular de uma transação local pode bloquear commits locais e votos de outras transações em conflitos, e a situação para transações globais também não muda sem o premissa simplificadora acima: O resultado final é o mesmo também com um compromisso local para transações locais, sem votar no compromisso atômico para elas.

Finalmente, o bloqueio por um bloqueio (que foi excluído até agora) precisa ser considerado: Um bloqueio bloqueia uma operação conflitante e evita que um conflito seja materializado. Suponha que o bloqueio seja liberado somente após o término da transação. Nesse caso, pode bloquear indiretamente um voto ou um commit local de outra transação (que agora não pode ficar pronta), com o mesmo efeito que um bloqueio direto de uma votação ou um commit local. Um ciclo é gerado no gráfico de conflito apenas se o bloqueio por um bloqueio também for representado por uma aresta. Com essas arestas adicionadas representando eventos de bloqueio por bloqueio, o gráfico de conflito está se tornando um gráfico de conflito aumentado .

• Definição: gráfico de conflito aumentado

Um gráfico de conflito aumentado é um gráfico de conflito com bordas adicionadas: além das bordas originais, existe uma borda direcionada de transação para transação, se duas condições forem atendidas: ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

1. ${\ displaystyle T_ {2}}$ é bloqueado por um bloqueio de acesso a dados aplicado por (o bloqueio evita que o conflito de com seja materializado e tem uma vantagem no gráfico de conflito regular), e ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$
2. Este bloqueio não vai parar antes do fim (confirma ou aborta; verdadeiro para qualquer CO baseado em bloqueio) ${\ displaystyle T_ {1}}$

O gráfico também pode ser definido como a união do gráfico de conflito (regular) com o gráfico de espera (borda reversa, regular)

Comentários:

1. Aqui, ao contrário do gráfico de conflito regular, que possui arestas apenas para conflitos materializados, todos os conflitos materializados e não materializados são representados por arestas.
2. Observe que todas as novas arestas são todas as arestas (revertidas para o convencional) do gráfico de espera . O gráfico de espera também pode ser definido como o gráfico de conflitos não materializados. Pelas convenções comuns, a direção da borda em um gráfico de conflito define a ordem de tempo entre as operações conflitantes, que é oposta à ordem de tempo definida por uma borda em um gráfico de espera .
3. Observe que tal gráfico global contém (incorporou) todos os (borda reversa) gráficos locais regulares de espera e também pode incluir ciclos globais baseados em bloqueio (que não podem existir nos gráficos locais). Por exemplo, se todos os bancos de dados em um ciclo global são baseados em SS2PL, então todas as situações de bloqueio de voto relacionadas são causadas por bloqueios (esta é a clássica e provavelmente a única situação de impasse global tratada na literatura de pesquisa de banco de dados). Este é um caso de deadlock global onde cada banco de dados relacionado cria uma parte do ciclo, mas o ciclo completo não reside em nenhum gráfico de espera local.

Na presença de CO, o gráfico de conflito aumentado é, na verdade, um (borda reversa) gráfico de espera local e votação : Uma borda existe de uma primeira transação, local ou global, para uma segunda, se a segunda está aguardando que o primeiro termine para ser votado (se global) ou confirmado localmente (se local). Todos os ciclos globais (em dois ou mais bancos de dados) neste gráfico geram conflitos de votação. Os ciclos globais do gráfico fornecem uma caracterização completa de impasses de votação e podem incluir qualquer combinação de conflitos materializados e não materializados. Apenas ciclos de (apenas) conflitos materializados também são ciclos do gráfico de conflito regular e afetam a serialização. Um ou mais conflitos não materializados (relacionados ao bloqueio) em um ciclo evitam que ele seja um ciclo no gráfico de conflito regular e o torna um conflito relacionado ao bloqueio. Todos os ciclos globais (votos-deadlocks) precisam ser quebrados (resolvidos) para manter a serializabilidade global e resolver deadlocks globais envolvendo bloqueio de acesso a dados. Na verdade, todos eles foram quebrados pelo protocolo de compromisso atômico devido à falta de votos em um impasse de votação.

Comentário: Esta observação também explica a correção do Extended CO (ECO) abaixo: A ordem de votação das transações globais deve seguir a ordem do gráfico de conflito com bloqueio de voto quando existe relação de ordem (caminho do gráfico) entre duas transações globais. As transações locais não são votadas e seus commits (locais) não são bloqueados em conflitos. Isso resulta nas mesmas situações de impasse de votação e processo de eliminação do ciclo global resultante para ECO.

A situação de impasse de votação pode ser resumida da seguinte forma:

• O Teorema CO Voting-Deadlock

Deixe um ambiente de vários bancos de dados compreender sistemas de banco de dados compatíveis com CO (o que elimina os ciclos locais ) que impõem cada CO Global (usando a condição no teorema acima). Um impasse de votação ocorre se e somente se um ciclo global (abrange dois ou mais bancos de dados) existe no gráfico de conflito aumentado Global (também o bloqueio por um bloqueio de acesso a dados é representado por uma borda). Suponha que o ciclo não seja interrompido por nenhum aborto. Nesse caso, todas as transações globais sobre ele implicam no respetivo impasse de votação. Eventualmente, cada um tem seu voto bloqueado (direta ou indiretamente por um bloqueio de acesso a dados); se uma transação local residir no ciclo, eventualmente, ela terá seu commit (local) bloqueado.

Comentário: Uma situação rara de impasse de votação (por falta de votos bloqueados) pode ocorrer, sem votação para qualquer transação no ciclo relacionado por qualquer um dos sistemas de banco de dados envolvidos com essas transações. Isso pode ocorrer quando as subtransações locais são multiencadeadas . A instância de maior probabilidade de tal evento raro envolve duas transações em dois ciclos opostos simultâneos. Esses ciclos globais (deadlocks) se sobrepõem aos ciclos locais que são resolvidos localmente e são normalmente resolvidos por mecanismos locais sem envolver o comprometimento atômico. Formalmente, é também um ciclo global, mas é praticamente local (partes de ciclos locais geram um global; para ver isso, divida cada transação global (nó) em subtransações locais (suas partes confinadas cada uma em um único banco de dados); existe uma borda direcionada entre as transações se existir uma borda entre quaisquer respectivas subtransações locais; um ciclo é local se todas as suas bordas se originam de um ciclo entre as subtransações do mesmo banco de dados e global se não; global e local podem se sobrepor: o mesmo ciclo entre transações pode resultar de vários ciclos diferentes entre subtransações e ser local e global).

Além disso, o seguinte caso especial baseado em bloqueio é concluído:

• Teorema de conflito global baseado em bloqueio de CO

Em um sistema multi-banco de dados compatível com CO, um deadlock global baseado em bloqueio, envolvendo pelo menos um bloqueio de acesso a dados (conflito não materializado) e dois ou mais sistemas de banco de dados, é um reflexo de um ciclo global no gráfico de conflito ampliado global , o que resulta em um impasse de votação. Esse ciclo não é um ciclo no gráfico de conflito global (regular) (que reflete apenas os conflitos materializados, portanto, esse ciclo não afeta a serialização ).

Comentários:

1. Qualquer bloqueio (borda) no ciclo que não seja por um bloqueio de acesso a dados bloqueia diretamente a votação ou o commit local. Todos os impasses de votação são resolvidos (quase todos por confirmação Atomic ; consulte o comentário acima), incluindo este tipo baseado em bloqueio.
2. Os deadlocks globais baseados em bloqueio também podem ser gerados em um ambiente distribuído completamente baseado em SS2PL (caso especial de baseado em CO). Todos os bloqueios de votação (e impasses de votação) são causados ​​por bloqueios de acesso a dados. Muitos artigos de pesquisa lidaram por anos com a resolução de tais impasses globais, mas nenhum (exceto os artigos CO) é conhecido (a partir de 2009) para notar que o comprometimento atômico os resolve automaticamente. Essas resoluções automáticas ocorrem regularmente sem serem notadas em todos os sistemas existentes de vários bancos de dados baseados em SS2PL, muitas vezes contornando mecanismos de resolução dedicados.

Os impasses de votação são a chave para a operação do CO distribuído.

A eliminação do ciclo global (aqui, resolução de impasse de votação por confirmação atômica ) e as reexecuções de transações abortadas resultantes são demoradas, independentemente do controle de simultaneidade usado. Se os bancos de dados agendam as transações de forma independente, os ciclos globais são inevitáveis ​​(em uma analogia completa com os ciclos / impasses gerados no SS2PL local; com distribuição, qualquer transação ou coordenação de agendamento de operação resulta em violação de autonomia e normalmente está em penalidade de desempenho substancial). No entanto, sua probabilidade pode ser muito baixa em muitos casos com a implementação de diretrizes de design de banco de dados e transação que reduzem o número de conflitos envolvendo uma transação global. Isso, principalmente por meio do tratamento adequado de pontos de acesso (objetos de banco de dados com acesso frequente) e evitando conflitos usando a comutatividade quando possível (por exemplo, ao usar amplamente contadores, como nas finanças, e especialmente contadores de acumulação de várias transações , que são normalmente pontos de acesso) .

Os protocolos de confirmação atômica são projetados e projetados para atingir atomicidade sem considerar o controle de simultaneidade do banco de dados. Eles abortam ao detectar ou encontrar heuristicamente (por exemplo, por um tempo limite; às vezes por engano, desnecessariamente) em falta de votos e normalmente não têm conhecimento dos ciclos globais. Esses protocolos podem ser especialmente aprimorados para CO (incluindo as variantes de CO abaixo) para evitar abortos desnecessários e acelerar abortos usados ​​para interromper os ciclos globais no gráfico de conflito aumentado global (para melhor desempenho pela liberação anterior no final da transação de recursos de computação e dados normalmente bloqueados ) Por exemplo, os métodos existentes de detecção de deadlock global baseados em bloqueio, além do tempo limite, podem ser generalizados também para considerar commit local e bloqueio direto de voto, além do bloqueio de acesso a dados. Um possível compromisso em tais mecanismos é efetivamente detectar e interromper os ciclos globais de comprimento 2 mais frequentes e relativamente simples, e usar o tempo limite para ciclos mais longos não detectados, muito menos frequentes.

Aplicando CO localmente

O pedido de compromisso pode ser executado localmente (em um único banco de dados) por um algoritmo CO dedicado, ou por qualquer algoritmo / protocolo que forneça qualquer caso especial de CO. Um protocolo importante, sendo utilizado extensivamente em sistemas de banco de dados, que gera uma programação CO, é o protocolo de bloqueio estrito de duas fases forte (SS2PL: "libere os bloqueios da transação somente após a transação ter sido confirmada ou abortada"; veja abaixo). SS2PL é um subconjunto adequado da interseção de 2PL e rigidez.

Um algoritmo local genérico de CO

Um algoritmo local genérico de CO ( Raz 1992 ; Algoritmo 4.1) é um algoritmo independente dos detalhes de implementação que impõe exatamente a propriedade CO. Não bloqueia o acesso aos dados (não bloqueante) e consiste em abortar um determinado conjunto de transações (apenas se necessário) ao confirmar uma transação. Ele aborta um conjunto mínimo (determinado exclusivamente em um determinado momento) de outras transações indecisas (nem confirmadas, nem canceladas) que são executadas localmente e pode causar violação de serializabilidade no futuro (pode posteriormente gerar ciclos de transações confirmadas no gráfico de conflito; isso é o conjunto ABORT de uma transação confirmada T; depois de confirmar T, nenhuma transação em ABORT no momento da confirmação pode ser confirmada, e todas elas estão condenadas a serem canceladas). Este conjunto consiste em todas as transações indecisas com arestas direcionadas no gráfico de conflito para a transação confirmada. O tamanho desse conjunto não pode aumentar quando a transação está aguardando para ser confirmada (no estado pronto: o processamento foi encerrado) e geralmente diminui com o tempo, conforme suas transações estão sendo decididas. Portanto, a menos que existam restrições em tempo real para concluir essa transação, é preferível aguardar com a confirmação dessa transação e deixar este conjunto diminuir de tamanho. Se outro mecanismo de serialização existe localmente (o que elimina ciclos no gráfico de conflito local), ou se nenhum ciclo envolvendo aquela transação existe, o conjunto ficará vazio eventualmente, e nenhum aborto de um membro do conjunto será necessário. Caso contrário, o conjunto se estabilizará com transações em ciclos locais, e o aborto de membros do conjunto terá que ocorrer para interromper os ciclos. Visto que no caso de conflitos de CO geram bloqueio na confirmação, os ciclos locais no gráfico de conflito de aumento (veja acima) indicam commit-deadlocks locais, e técnicas de resolução de deadlock como em SS2PL podem ser usadas (por exemplo, como gráfico de tempo limite e espera ) . Um ciclo local no gráfico de conflito aumentado com pelo menos um conflito não materializado reflete um impasse baseado em bloqueio. O algoritmo local acima, aplicado ao gráfico de conflito aumentado local em vez do gráfico de conflito local regular, compreende o algoritmo CO local aprimorado genérico , um mecanismo de eliminação de ciclo único local, tanto para garantir a serialização local quanto para lidar com bloqueios locais baseados em bloqueios. Praticamente, um mecanismo de controle de simultaneidade adicional é sempre utilizado, mesmo apenas para garantir a capacidade de recuperação. O algoritmo CO genérico não afeta a estratégia de agendamento de acesso de dados local quando é executado junto com qualquer outro mecanismo de controle de simultaneidade local. Afeta apenas a ordem de confirmação e, por esse motivo, não precisa abortar mais transações do que aquelas que precisavam ser abortadas para prevenção de violação de serializabilidade por qualquer mecanismo de controle de simultaneidade local combinado. No máximo, o efeito líquido do CO pode ser um atraso de eventos de confirmação (ou votação em um ambiente distribuído), para cumprir a ordem de confirmação necessária (mas não mais atraso do que seus casos especiais, por exemplo, SS2PL, e em média significativamente menos).

O seguinte teorema é concluído:

• O Teorema do Algoritmo Local Genérico de CO

Ao executar sozinho ou ao lado de qualquer mecanismo de controle de simultaneidade em um sistema de banco de dados, então

1. O algoritmo de CO local genérico garante CO (local) (uma programação compatível com CO).
2. O algoritmo de CO local aprimorado genérico garante a resolução de deadlock baseada em CO (local) e em bloqueio (local). E (quando não está usando um tempo limite , e nenhuma restrição de conclusão de transação em tempo real é aplicada) nenhum algoritmo aborta mais transações do que o mínimo necessário (que é determinado pelo agendamento das operações das transações, fora do escopo dos algoritmos).

Exemplo: programação simultânea e memória transacional

Veja também Programação simultânea e Memória transacional.

Com a proliferação de processadores Multi-core, as variantes do algoritmo CO local genérico também têm sido cada vez mais utilizadas na programação simultânea, memória transacional e especialmente na memória transacional de software para alcançar serializabilidade de forma otimista por "ordem de confirmação" (por exemplo, Ramadan et al. 2009, Zhang et al. 2006, von Parun et al. 2007). Vários artigos relacionados e patentes que utilizam CO já foram publicados.

Considerações de implementação: O Coordenador de Ordem de Compromisso (COCO)

Um sistema de banco de dados em um ambiente de vários bancos de dados é considerado. Do ponto de vista da arquitetura de software , um componente CO que implementa o algoritmo CO genérico localmente, o Coordenador de Ordem de Compromisso (COCO), pode ser projetado diretamente como um mediador entre um (único) sistema de banco de dados e um componente de protocolo de compromisso atômico ( Raz 1991b ) No entanto, o COCO é normalmente uma parte integrante do sistema de banco de dados. As funções do COCO são votar para confirmar em transações globais prontas (o processamento foi encerrado) de acordo com a ordem de confirmação local, votar para cancelar em transações para as quais o sistema de banco de dados iniciou um cancelamento (o sistema de banco de dados pode iniciar o cancelamento para qualquer transação , por muitos motivos) e para passar a decisão de confirmação atômica para o sistema de banco de dados. Para transações locais (quando podem ser identificadas), nenhuma votação é necessária. Para determinar a ordem de confirmação, o COCO mantém uma representação atualizada do gráfico de conflito local (ou gráfico de conflito aumentado local para capturar também bloqueios de travamento) das transações indecisas (nem confirmadas nem abortadas) como uma estrutura de dados (por exemplo, utilizando mecanismos semelhantes a bloqueio para capturar conflitos, mas sem bloqueio de acesso aos dados). O componente COCO tem uma interface com seu sistema de banco de dados para receber notificações de "conflito", "pronto" (o processamento foi encerrado; prontidão para votar em uma transação global ou confirmar uma local) e notificações de "aborto" do sistema de banco de dados. Ele também faz interface com o protocolo de confirmação atômica para votar e receber a decisão do protocolo de confirmação atômica em cada transação global. As decisões são entregues do COCO ao sistema de banco de dados por meio de sua interface, bem como notificações de confirmação de transações locais, em uma ordem de confirmação adequada. O COCO, incluindo suas interfaces, pode ser aprimorado, se implementar outra variante do CO (veja abaixo) ou desempenhar uma função no mecanismo de controle de simultaneidade do banco de dados além da votação no compromisso atômico.

O COCO também garante CO localmente em um sistema de banco de dados único e isolado, sem interface com um protocolo de confirmação atômica.

CO é uma condição necessária para a serialização global em sistemas de banco de dados autônomos.

Suponha que os bancos de dados que participam de transações distribuídas (ou seja, transações que abrangem mais de um único banco de dados) não usam nenhuma informação de controle de simultaneidade compartilhada e usam mensagens de protocolo de confirmação atômica não modificadas (para atingir a atomicidade). Nesse caso, manter a ordem de compromisso (local) ou uma de suas variantes generalizantes (veja abaixo) é uma condição necessária para garantir a serializabilidade global (uma técnica de prova pode ser encontrada em ( Raz 1992 ), e um método de prova diferente para isso em ( Raz 1993a )); também é uma condição suficiente . Este é um fato matemático derivado das definições de serializabilidade e uma transação . Isso significa que, se não estiver em conformidade com o CO, a serializabilidade global não pode ser garantida sob esta condição (a condição de nenhum compartilhamento de informações de controle de simultaneidade local entre bancos de dados além de mensagens de protocolo de confirmação atômica). A confirmação atômica é um requisito mínimo para uma transação distribuída, pois é sempre necessária, o que está implícito na definição da transação.

( Raz 1992 ) define autonomia e independência de banco de dados como conformidade com este requisito sem usar nenhum conhecimento local adicional:

• Definição: (baseado em controle de simultaneidade) sistema de banco de dados autônomo

Um sistema de banco de dados é Autônomo , se ele não compartilha nenhuma informação de controle de simultaneidade além de mensagens de protocolo de confirmação atômica não modificadas com qualquer outra entidade. Além disso, ele não usa para controle de simultaneidade nenhuma informação local adicional além dos conflitos (a última sentença não aparece explicitamente, mas sim implícita em uma discussão posterior em Raz 1992 ).

Usando esta definição, o seguinte é concluído:

• O CO e o teorema de serializabilidade global

1. A conformidade CO de cada sistema de banco de dados autônomo (ou objeto transacional) em um ambiente de vários bancos de dados é uma condição necessária para garantir a serialização global (sem CO, a serialização global pode ser violada).
2. A conformidade CO com cada sistema de banco de dados é uma condição suficiente para garantir a serialização global.

No entanto, a definição de autonomia acima implica, por exemplo, que as transações são agendadas de forma que as transações locais (confinadas a um único banco de dados) não possam ser identificadas como tal por um sistema de banco de dados autônomo. Isso é realista para alguns objetos transacionais, mas muito restritivo e menos realista para sistemas de banco de dados de propósito geral. Se a autonomia é aumentada com a capacidade de identificar transações locais, então a conformidade com uma propriedade mais geral, pedido de compromisso estendido (ECO, veja abaixo), torna ECO a condição necessária.

Apenas em ( Raz 2009 ) a noção de autonomia generalizada captura a noção pretendida de autonomia:

• Definição: autonomia generalizada

Um sistema de banco de dados tem a propriedade Autonomia generalizada se não compartilhar nenhum outro sistema de banco de dados, nenhuma informação de simultaneidade local além das mensagens de protocolo de confirmação atômica (não modificadas) (no entanto, qualquer informação local pode ser utilizada).

Esta definição é provavelmente a mais ampla possível no contexto do controle de simultaneidade do banco de dados, e torna CO junto com qualquer uma de suas (úteis: distribuição de informações de controle de simultaneidade) generalizando as variantes (Ordenação de voto (VO); consulte as variantes de CO abaixo). condição necessária para serializabilidade global (ou seja, a união de CO e suas variantes generalizantes é o conjunto necessário VO, que também pode incluir novas variantes generalizantes úteis desconhecidas).

Resumo

A solução (técnica) de pedido de compromisso (CO) para serialização global pode ser resumida da seguinte forma:

Se cada banco de dados (ou qualquer outro objeto transacional ) em um ambiente de vários bancos de dados está em conformidade com o CO, ou seja, organiza seus compromissos de transações locais e seus votos em transações (globais, distribuídas) para o protocolo de compromisso atômico de acordo com o local (para o banco de dados) ordem parcial induzida pelo gráfico de conflito local (gráfico de serializabilidade) para as respectivas transações, então CO Global e serializabilidade Global são garantidos. A conformidade de CO de um banco de dados pode ser alcançada efetivamente com qualquer mecanismo de controle de simultaneidade baseado em serializabilidade de conflito local , sem afetar o processo de execução ou programação de qualquer transação, nem abortá-la. Além disso, a autonomia do banco de dados não é violada. A única baixa sobrecarga incorrida é a detecção de conflitos (por exemplo, com bloqueio, mas sem bloqueio de acesso a dados; se já não for detectado para outros fins) e ordenação de votos e commits de transações locais de acordo com os conflitos.

Programar contenção de classes: Uma seta da classe A para a classe B indica que a classe A contém estritamente B; a falta de um caminho direcionado entre as classes significa que as classes são incomparáveis. Uma propriedade é inerentemente bloqueadora , se puder ser aplicada apenas bloqueando as operações de acesso a dados da transação até que certos eventos ocorram em outras transações. ( Raz 1992 )

No caso de pedidos parciais incompatíveis de dois ou mais bancos de dados (nenhum pedido parcial global pode incorporar os respectivos pedidos parciais locais juntos), um ciclo global (abrange dois bancos de dados ou mais) no gráfico de conflito global é gerado. Isso, junto com o CO, resulta em um ciclo de votos bloqueados. A voting- impasse ocorre para os bancos de dados em que o ciclo (no entanto, permitiu a votação simultânea em cada banco de dados, geralmente para quase todos os pendentes votos, continuar a executar). Nesse caso, o protocolo de confirmação atômica falha em coletar todos os votos necessários para as transações bloqueadas naquele ciclo global. Conseqüentemente, o protocolo aborta algumas transações com um voto ausente. Isso quebra o ciclo global, o impasse de votação é resolvido e os votos bloqueados relacionados estão livres para serem executados. Romper o ciclo global no gráfico de conflito global garante que o CO global e a serialização global sejam mantidos. Portanto, no caso de pedidos de confirmação locais (parciais) incompatíveis, nenhuma ação é necessária, pois o protocolo de confirmação atômica resolve automaticamente ao abortar uma transação que é a causa da incompatibilidade. Além disso, deadlocks globais devido ao locking (ciclos globais no gráfico de conflito aumentado com pelo menos um bloqueio de acesso a dados) resultam em deadlocks de votação e são resolvidos automaticamente pelo mesmo mecanismo.

CO local é uma condição necessária para garantir a serializabilidade global se os bancos de dados envolvidos não compartilharem nenhuma informação de controle de simultaneidade além das mensagens de protocolo de confirmação atômica (não modificada), ou seja, se os bancos de dados forem autônomos no contexto de controle de simultaneidade. Isso significa que toda solução de serialização global para bancos de dados autônomos deve estar em conformidade com CO. Caso contrário, a serialização global pode ser violada (e, portanto, é provável que seja violada muito rapidamente em um ambiente de alto desempenho).

A solução CO aumenta com o tamanho da rede e o número de bancos de dados sem prejuízo de desempenho quando utiliza arquitetura de comprometimento atômico distribuído comum .

Serializabilidade distribuída e CO

CO distribuído

Uma característica distintiva da solução CO para serialização distribuída de outras técnicas é o fato de que ela não requer nenhuma informação de conflito distribuída (por exemplo, relações de precedência local, bloqueios, carimbos de data / hora , tickets), o que a torna excepcionalmente eficaz. Ele utiliza mensagens de protocolo de confirmação atômica (não modificadas) (que já são usadas).

Uma maneira comum de alcançar a serialização distribuída em um sistema (distribuído) é por um gerenciador de bloqueio distribuído (DLM). DLMs, que comunicam informações de bloqueio (conflito não materializado) em um ambiente distribuído, normalmente sofrem com a latência do computador e da comunicação , o que reduz o desempenho do sistema. CO permite atingir a serializabilidade distribuída em condições muito gerais, sem um gerenciador de bloqueio distribuído, exibindo os benefícios já explorados acima para ambientes de múltiplas bases de dados; em particular: confiabilidade, alto desempenho, escalabilidade, a possibilidade de usar o controle de simultaneidade otimista quando desejado, nenhuma comunicação de informações de conflito relacionada na rede (que incorreram em sobrecarga e atrasos) e resolução automática de impasse distribuído.

Todos os sistemas transacionais distribuídos contam com algum protocolo de confirmação atômica para coordenar a atomicidade (seja para confirmar ou abortar) entre os processos em uma transação distribuída . Além disso, os dados normalmente recuperáveis (ou seja, dados sob controle de transações, por exemplo, dados de banco de dados; não deve ser confundida com a propriedade de recuperabilidade de um cronograma) são acessados ​​diretamente por um único componente do gerenciador de dados transacionais (também referido como um gerenciador de recursos ) que lida com subtransações locais (a parte da transação distribuída em um único local, por exemplo, nó de rede), mesmo se esses dados forem acessados ​​indiretamente por outras entidades no sistema distribuído durante uma transação (ou seja, o acesso indireto requer um acesso direto por meio de um subtransação local). Assim, os dados recuperáveis ​​em um sistema transacional distribuído são normalmente particionados entre gerenciadores de dados transacionais. Nesse sistema, esses gerenciadores de dados transacionais normalmente incluem os participantes do protocolo de confirmação atômica do sistema. Se cada participante está em conformidade com CO (por exemplo, usando SS2PL, ou COCOs, ou uma combinação; veja acima), todo o sistema distribuído fornece CO (pelos teoremas acima; cada participante pode ser considerado um objeto transacional separado) e, portanto serializabilidade (distribuída). Além disso: Quando o CO é utilizado junto com um protocolo de confirmação atômico, também os deadlocks distribuídos (ou seja, os deadlocks que abrangem dois ou mais gerenciadores de dados) causados ​​pelo bloqueio de acesso aos dados são resolvidos automaticamente. Assim, o seguinte corolário é concluído:

• O Teorema da Serializabilidade Distribuída Baseada em CO

Permita que um sistema transacional distribuído (por exemplo, um sistema de banco de dados distribuído ) inclua gerenciadores de dados transacionais (também chamados de gerenciadores de recursos ) que gerenciam todos os dados recuperáveis do sistema . Os gerenciadores de dados atendem a três condições:

1. Partição de dados: os dados recuperáveis ​​são particionados entre os gerenciadores de dados, ou seja, cada dado recuperável (item de dados) é controlado por um único gerenciador de dados (por exemplo, como comum em uma arquitetura de nada compartilhado ; até mesmo cópias do mesmo dado em diferentes gerenciadores de dados são fisicamente distinto, replicado ).
2. Participantes do protocolo de confirmação atômica: esses gerenciadores de dados são os participantes do protocolo de confirmação atômica do sistema para coordenar a atomicidade das transações distribuídas.
3. Conformidade com CO: cada gerenciador de dados é compatível com CO (ou alguma variante de CO compatível; veja abaixo).

Então

1. Todo o sistema distribuído garante serializabilidade (CO distribuído e) , e
2. Deadlocks distribuídos baseados em acesso a dados (deadlocks envolvendo dois ou mais gerenciadores de dados com pelo menos um conflito não materializado) são resolvidos automaticamente.

Além disso: Os gerenciadores de dados serem compatíveis com CO é uma condição necessária para serializabilidade (distribuída) em um sistema que atende às condições 1, 2 acima, quando os gerenciadores de dados são autônomos , ou seja, não compartilham informações de controle de simultaneidade além de mensagens não modificadas do protocolo de confirmação atômica.

Este teorema também significa que quando SS2PL (ou qualquer outra variante CO) é usado localmente em cada gerenciador de dados transacionais, e cada gerenciador de dados tem controle exclusivo de seus dados, nenhum gerenciador de bloqueio distribuído (que muitas vezes é utilizado para impor SS2PL distribuído) é necessário para SS2PL distribuído e serializabilidade. É relevante para uma ampla gama de aplicações transacionais distribuídas, que podem ser facilmente projetadas para atender às condições do teorema.

CO otimista distribuído (DOCO)

Para implementar o Distributed Optimistic CO (DOCO), o algoritmo local genérico de CO é utilizado em todos os participantes do protocolo de confirmação atômica no sistema, sem bloqueio de acesso a dados e, portanto, sem deadlocks locais. O teorema anterior tem o seguinte corolário:

• O Teorema do CO otimista distribuído (DOCO)

Se DOCO for utilizado, então:

1. Nenhum impasse local ocorre, e
2. Impasses globais (votação) são resolvidos automaticamente (e todos são relacionados à serializabilidade (com conflitos de não bloqueio) em vez de relacionados ao bloqueio (com bloqueio e possivelmente também conflitos de não bloqueio)).

Portanto, nenhum tratamento de deadlock é necessário.

Exemplos

SS2PL distribuído

Um sistema de banco de dados distribuído que utiliza SS2PL reside em dois nós remotos, A e B. O sistema de banco de dados tem dois gerenciadores de dados transacionais ( gerenciadores de recursos ), um em cada nó, e os dados do banco de dados são particionados entre os dois gerenciadores de dados de uma maneira que cada um tem um controle exclusivo de sua própria porção de dados (local para o nó): cada um lida com seus próprios dados e bloqueia sem nenhum conhecimento do outro gerente. Para cada transação distribuída, esses gerenciadores de dados precisam executar o protocolo de confirmação atômica disponível.

Duas transações distribuídas, e , estão sendo executadas simultaneamente, e ambas acessam os dados x e y. x está sob o controle exclusivo do gerenciador de dados em A (o gerente de B não pode acessar x) e y sob o controle de B. ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

${\ displaystyle T_ {1}}$ lê x em A e escreve y em B, ou seja, ao usar notação comum para controle de concorrência. ${\ displaystyle T_ {1} = R _ {\ text {1A}} (x)}$ ${\ displaystyle W _ {\ text {1B}} (y)}$

${\ displaystyle T_ {2}}$ lê y em B e escreve x em A, ou seja, ${\ displaystyle T_ {2} = R _ {\ text {2B}} (y)}$ ${\ displaystyle W _ {\ text {2A}} (x)}$

As respectivas subtransações locais em A e B (as partes de e em cada um dos nós) são as seguintes: ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

Subtransações locais

Nó Transação	UMA	B
${\ displaystyle T_ {1}}$	${\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$	${\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$
${\ displaystyle T_ {2}}$	${\ displaystyle T _ {\ text {2A}} = W _ {\ text {2A}} (x)}$	${\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} (y)}$

A programação do sistema de banco de dados em um determinado momento é a seguinte:

${\ displaystyle R _ {\ text {1A}} (x)}$ ${\ displaystyle R _ {\ text {2B}} (y)}$

(também é possível) ${\ displaystyle R _ {\ text {2B}} (y)}$ ${\ displaystyle R _ {\ text {1A}} (x)}$

${\ displaystyle T_ {1}}$ mantém um bloqueio de leitura em xe mantém bloqueios de leitura em y. Assim, e são bloqueados pelos compatibilidade bloqueio regras de SS2PL e não pode ser executado. Esta é uma situação de deadlock distribuído, que também é um deadlock de votação (veja abaixo) com um ciclo distribuído (global) de comprimento 2 (número de arestas, conflitos; 2 é o comprimento mais frequente). As subtransações locais estão nos seguintes estados: ${\ displaystyle T_ {2}}$${\ displaystyle W _ {\ text {1B}} (y)}$${\ displaystyle W _ {\ text {2A}} (x)}$

${\ displaystyle T _ {\ text {1A}}}$ está pronto (a execução terminou) e votou (em compromisso atômico)

${\ displaystyle T _ {\ text {1B}}}$ está em execução e bloqueado (uma situação de conflito não materializada; nenhuma votação pode ocorrer)

${\ displaystyle T _ {\ text {2B}}}$ está pronto e votou

${\ displaystyle T _ {\ text {2A}}}$ está em execução e bloqueado (um conflito não materializado; sem votação).

Uma vez que o protocolo de confirmação atômica não pode receber votos para subtransações bloqueadas (um impasse de votação), ele acabará abortando alguma transação com voto (s) ausente (s) por tempo limite , ou , ou (ou ambos, se os tempos limite ficarem muito próximos ) Isso resolverá o impasse global. A transação restante será concluída em execução, votada e confirmada. Uma transação abortada é imediatamente reiniciada e executada novamente. ${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

Comentários

1. A partição de dados (x em A; y em B) é importante uma vez que, sem ele, por exemplo, x pode ser acedida directamente a partir de B. Se uma transacção está a executar a B simultaneamente com e e escreve directamente x, em seguida, sem um bloqueio distribuído gerenciador, o bloqueio de leitura para x mantido por A não é visível em B e não pode bloquear a gravação de (ou sinalizar um conflito materializado para uma variante CO sem bloqueio; veja abaixo). Assim, a serialização pode ser violada. ${\ displaystyle T_ {3}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {3}}$
2. Devido à partição de dados, x não pode ser acessado diretamente de B. No entanto, a funcionalidade não é limitada e uma transação em execução em B ainda pode emitir uma solicitação de gravação ou leitura de x (não comum). Essa solicitação é comunicada à subtransação local da transação em A (que é gerada, se ainda não existir), que emite essa solicitação ao gerenciador de dados local em A.

Variações

No cenário acima, ambos os conflitos não são materializados , e o impasse de votação global é refletido como um ciclo no gráfico de espera global (mas não no gráfico de conflito global ; consulte a caracterização exata dos impasses de votação por ciclos globais acima) . No entanto, o sistema de banco de dados pode utilizar qualquer variante CO com exatamente os mesmos conflitos e situação de impasse de votação e mesma resolução. Os conflitos podem ser materializados ou não , dependendo da variante de CO usada. Por exemplo, se SCO (abaixo) for usado pelo sistema de banco de dados distribuído em vez de SS2PL, então os dois conflitos no exemplo são materializados , todas as subtransações locais estão prontas e o bloqueio de voto ocorre nas duas transações, uma em cada nó, por causa da regra de votação CO aplicada independentemente em A e B: devido a conflitos, não é votado antes do final, e não é votado antes do final, o que é um impasse de votação. Agora o gráfico de conflito tem o ciclo global (todos os conflitos são materializados), e novamente é resolvido pelo protocolo de confirmação atômica, e a serialização distribuída é mantida. Improvável para um sistema de banco de dados distribuído, mas possível em princípio (e ocorre em um banco de dados múltiplo), A pode empregar SS2PL enquanto B emprega SCO. Nesse caso, o ciclo global não está no gráfico de espera nem no gráfico de serializabilidade, mas ainda no gráfico de conflito aumentado (a união dos dois). As várias combinações estão resumidas na seguinte tabela: ${\ displaystyle T _ {\ text {2A}} = W _ {\ text {2A}} (x)}$${\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$${\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$${\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} (y)}$

Situações de impasse na votação

Caso	Nó A	Nó B	Possível programação	Conflitos materializados no ciclo	Conflitos não materializados	${\ displaystyle T _ {\ text {1A}} = R _ {\ text {1A}} (x)}$	${\ displaystyle T _ {\ text {1B}} = W _ {\ text {1B}} (y)}$	${\ displaystyle T _ {\ text {2A}} = W _ {\ text {2A}} (x)}$	${\ displaystyle T _ {\ text {2B}} = R _ {\ text {2B}} (y)}$
1	SS2PL	SS2PL	${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y)}$	0	2	pronto Votado	Em execução (bloqueado)	Em execução (bloqueado)	pronto Votado
2	SS2PL	SCO	${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y)}$	1	1	pronto Votado	Voto pronto bloqueado	Em execução (bloqueado)	pronto Votado
3	SCO	SS2PL	${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {2A}} (x)}$	1	1	pronto Votado	Em execução (bloqueado)	Voto pronto bloqueado	pronto Votado
4	SCO	SCO	${\ displaystyle R _ {\ text {1A}} (x) R _ {\ text {2B}} (y) W _ {\ text {1B}} (y) W _ {\ text {2A}} (x)}$	2	0	pronto Votado	Voto pronto bloqueado	Voto pronto bloqueado	pronto Votado

Comentários:

1. Os conflitos e, portanto, os ciclos no gráfico de conflito aumentado são determinados apenas pelas transações e sua programação inicial, independentemente do controle de concorrência utilizado. Com qualquer variante de CO, qualquer ciclo global (ou seja, abrange dois bancos de dados ou mais) causa um impasse de votação . Diferentes variantes de CO podem diferir sobre se um determinado conflito é materializado ou não materializado .
2. Algumas mudanças limitadas de ordem de operação nas programações acima são possíveis, restringidas pelas ordens dentro das transações, mas tais mudanças não alteram o resto da tabela.
3. Conforme observado acima, apenas o caso 4 descreve um ciclo no gráfico de conflito (regular) que afeta a serializabilidade. Os casos 1-3 descrevem ciclos de bloqueios globais baseados em bloqueio (existe pelo menos um bloqueio de bloqueio). Todos os tipos de ciclo são igualmente resolvidos pelo protocolo de confirmação atômica. O caso 1 é o SS2PL distribuído comum, utilizado desde os anos 1980. No entanto, nenhum artigo de pesquisa, exceto os artigos CO, é conhecido por notar essa resolução de deadlock global de bloqueio automático a partir de 2009. Esses deadlocks globais normalmente têm sido tratados por mecanismos dedicados.
4. O caso 4 acima também é um exemplo de um impasse de votação típico quando o CO otimista distribuído (DOCO) é usado (ou seja, o caso 4 permanece inalterado quando o CO otimista (OCO; veja abaixo) substitui o SCO em A e B): Sem dados- ocorre bloqueio de acesso e existem apenas conflitos materializados.

Ambiente hipotético Multi Single-Threaded Core (MuSiC)

Comentário: Embora os exemplos acima descrevam a utilização real e recomendada de CO, este exemplo é hipotético, apenas para demonstração.

Certos bancos de dados residentes em memória distribuídos experimentais defendem ambientes transacionais multi single-threaded core (MuSiC). "Single-threaded" refere-se apenas a threads de transação e à execução serial de transações. O objetivo é um possível ganho de ordens de magnitude no desempenho (por exemplo, H-Store e VoltDB ) em relação à execução de transações convencionais em vários threads em um mesmo núcleo. No que é descrito a seguir, MuSiC é independente da forma como os núcleos são distribuídos. Eles podem residir em um circuito integrado (chip), ou em muitos chips, possivelmente distribuídos geograficamente em muitos computadores. Em tal ambiente, se os dados recuperáveis ​​(transacionais) forem particionados entre threads (núcleos) e forem implementados de maneira convencional para CO distribuído, conforme descrito nas seções anteriores, então DOCO e Strictness existem automaticamente. No entanto, existem desvantagens com essa implementação direta de tal ambiente, e sua praticidade como uma solução de uso geral é questionável. Por outro lado, um enorme ganho de desempenho pode ser alcançado em aplicativos que podem contornar essas desvantagens na maioria das situações.

Comentário: A implementação direta MuSiC descrita aqui (que usa, por exemplo, como de costume em CO distribuído, bloqueio de votação (e thread de transação) no protocolo de confirmação atômica quando necessário) é apenas para demonstração e não tem conexão com a implementação em H- Loja ou qualquer outro projeto.

Em um ambiente MuSiC, as programações locais são em série . Assim, tanto o CO otimista local (OCO; veja abaixo) quanto a condição de estratégia de ordenação de voto de imposição de CO Global para o protocolo de confirmação atômica são atendidos automaticamente. Isso resulta em conformidade CO distribuída (e, portanto, serializabilidade distribuída) e resolução de impasse global automática (votação).

Além disso, também a rigidez local segue automaticamente em uma programação em série. Pelo Teorema 5.2 em ( Raz 1992 ; página 307), quando a estratégia de ordenação de votos do CO é aplicada, também a Restrição Global é garantida. Observe que serial localmente é o único modo que permite rigidez e "otimismo" (sem bloqueio de acesso a dados) juntos.

Conclui-se o seguinte:

• O Teorema MuSiC

Em ambientes MuSiC, se os dados recuperáveis ​​(transacionais) forem particionados entre os núcleos (threads), então ambos

1. OCO (e serialização implícita ; ou seja, DOCO e serializabilidade distribuída)
2. Restrição (permitindo a recuperação eficaz; 1 e 2 implicando Strict CO - ver SCO abaixo) e
3. (votação) resolução de impasse

existe automaticamente globalmente com escalabilidade ilimitada no número de núcleos usados.

Comentário: No entanto, podem existir duas desvantagens principais, que precisam de tratamento especial:

1. As subtransações locais de uma transação global são bloqueadas até a confirmação, o que torna os respectivos núcleos inativos. Isso reduz a utilização do núcleo substancialmente, mesmo se o agendamento das subtransações locais tentar executar todas elas em proximidade de tempo, quase juntas. Isso pode ser superado desanexando a execução do commit (com algum protocolo de confirmação atômico) para transações globais, ao custo de possíveis abortos em cascata.
2. aumentar o número de núcleos para uma determinada quantidade de dados recuperáveis ​​(tamanho do banco de dados) diminui a quantidade média de dados (particionados) por núcleo. Isso pode deixar alguns núcleos ociosos, enquanto outros muito ocupados, dependendo da distribuição de utilização de dados. Além disso, uma transação local (para um núcleo) pode se tornar global (vários núcleos) para alcançar seus dados necessários, com sobrecarga adicional incorrida. Assim, conforme o número de núcleos aumenta, a quantidade e o tipo de dados atribuídos a cada núcleo devem ser balanceados de acordo com o uso de dados, para que um núcleo não seja sobrecarregado para se tornar um gargalo, nem fique ocioso com muita frequência e subutilizado em um sistema ocupado. Outra consideração é colocar em uma mesma partição de núcleo todos os dados que geralmente são acessados ​​por uma mesma transação (se possível), para maximizar o número de transações locais (e minimizar o número de transações globais distribuídas). Isso pode ser conseguido por meio da partição ocasional de dados entre os núcleos com base no balanceamento de carga (balanceamento de acesso a dados) e padrões de uso de dados por transações. Outra maneira de atenuar consideravelmente essa desvantagem é por meio da replicação de dados físicos adequados entre algumas partições centrais de forma que as transações globais somente leitura sejam possivelmente (dependendo dos padrões de uso) completamente evitadas e as alterações de replicação sejam sincronizadas por um mecanismo de confirmação dedicado.

Variantes CO: casos especiais e generalizações

Classes de propriedade de cronograma de caso especial (por exemplo, SS2PL e SCO abaixo) estão estritamente contidas na classe CO. As classes generalizantes (ECO e MVCO) contêm estritamente a classe CO (ou seja, incluem também programações que não são compatíveis com CO). As variantes generalizantes também garantem serializabilidade global sem distribuir informações de controle de simultaneidade local (cada banco de dados tem a propriedade de autonomia generalizada : ele usa apenas informações locais), enquanto relaxa as restrições de CO e utiliza informações adicionais (locais) para melhor concorrência e desempenho: ECO usa conhecimento sobre as transações são locais (ou seja, confinadas a um único banco de dados) e o MVCO usa a disponibilidade dos valores das versões dos dados. Como o CO, as duas variantes generalizantes não bloqueiam , não interferem no agendamento de nenhuma operação da transação e podem ser combinadas perfeitamente com qualquer mecanismo de controle de simultaneidade relevante.

O termo variante de CO refere-se em geral a CO, ECO, MVCO ou uma combinação de cada um deles com qualquer mecanismo ou propriedade de controle de simultaneidade relevante (incluindo ECO baseado em várias versões, MVECO). Nenhuma outra variante generalizante (que garante serializabilidade global sem distribuição de informações de controle de simultaneidade local) é conhecida, mas pode ser descoberta.

Bloqueio estrito de duas fases forte (SS2PL)

Strong Strict Two Phase Locking (SS2PL; também conhecido como Rigorousness ou Rigorous scheduling ) significa que os bloqueios de leitura e gravação de uma transação são liberados somente após o término da transação (confirmada ou abortada). O conjunto de programações SS2PL é um subconjunto adequado do conjunto de programações CO. Esta propriedade é amplamente utilizada em sistemas de banco de dados e, uma vez que implica CO, os bancos de dados que a usam e participam de transações globais geram juntos uma programação global serializável (ao usar qualquer protocolo de confirmação atômica, que é necessário para atomicidade em um ambiente de vários bancos de dados) . Nenhuma modificação ou adição de banco de dados é necessária neste caso para participar de uma solução distribuída de CO: O conjunto de transações indecisas a serem abortadas antes da confirmação no algoritmo de CO genérico local acima está vazio por causa dos bloqueios e, portanto, tal algoritmo é desnecessário em este caso. Uma transação pode ser votada por um sistema de banco de dados imediatamente após entrar em um estado "pronto", ou seja, concluir a execução de sua tarefa localmente. Seus bloqueios são liberados pelo sistema de banco de dados somente após ser decidido pelo protocolo de confirmação atômica e, portanto, a condição no teorema de reforço Global CO acima é mantida automaticamente. Se um mecanismo de tempo limite local é usado por um sistema de banco de dados para resolver bloqueios SS2PL (locais), então abortar transações bloqueadas quebra não apenas os ciclos locais potenciais no gráfico de conflito global (ciclos reais no gráfico de conflito aumentado), mas também o potencial global do sistema de banco de dados ciclos como um efeito colateral, se o mecanismo de aborto do protocolo de confirmação atômica for relativamente lento. Esses abortos independentes por várias entidades normalmente podem resultar em abortos desnecessários para mais de uma transação por ciclo global. A situação é diferente para mecanismos baseados em gráfico de espera local : eles não podem identificar ciclos globais e o protocolo de confirmação atômica interromperá o ciclo global, se o impasse de votação resultante não for resolvido anteriormente em outro banco de dados.

O SS2PL local junto com o compromisso atômico que implica serializabilidade global também pode ser deduzido diretamente: Todas as transações, inclusive distribuídas, obedecem às regras 2PL (SS2PL). O mecanismo de protocolo de confirmação atômica não é necessário aqui para o consenso sobre a confirmação, mas sim para o final do ponto de sincronização da fase dois. Provavelmente por esse motivo, sem considerar o mecanismo de votação de comprometimento atômico, a resolução automática do impasse global não foi percebida antes do CO.

CO estrito (SCO)

Conflito de leitura e gravação: SCO vs. SS2PL . A duração da transação T2 é maior com SS2PL do que com SCO. SS2PL atrasa a operação de gravação w2 [x] de T2 até que T1 seja confirmado, devido a um bloqueio em x por T1 após a operação de leitura r1 [x]. Se t unidades de tempo são necessárias para a transação T2 após o início da operação de gravação w2 [x] a fim de alcançar o estado pronto, então T2 confirma t unidades de tempo após a confirmação de T1. No entanto, SCO não bloqueia w2 [x] e T2 pode confirmar imediatamente após a confirmação de T1. ( Raz 1991c )

A Ordenação de Compromisso Estrito (SCO; ( Raz 1991c )) é a interseção da rigidez (um caso especial de recuperabilidade) e CO, e fornece um limite superior para a simultaneidade de uma programação quando ambas as propriedades existem. Ele pode ser implementado usando mecanismos de bloqueio (travamento) semelhantes aos usados ​​para o SS2PL popular com sobrecargas semelhantes.

Ao contrário do SS2PL, o SCO não bloqueia em um conflito de leitura e gravação, mas possivelmente bloqueia na confirmação. SCO e SS2PL têm comportamento de bloqueio idêntico para os outros dois tipos de conflito: gravação-leitura e gravação-gravação. Como resultado, o SCO tem períodos de bloqueio médios mais curtos e mais simultaneidade (por exemplo, simulações de desempenho de um único banco de dados para a variante mais significativa de bloqueios com compartilhamento ordenado , que é idêntico ao SCO, mostra isso claramente, com ganho de aproximadamente 100% para algumas cargas de transacção; também para cargas de transacção idênticos SCO podem atingir taxas de transacção mais elevados do que SS2PL antes bloqueio debulha ocorre). Mais simultaneidade significa que, com determinados recursos de computação, mais transações são concluídas em unidade de tempo (maior taxa de transação, rendimento ) e a duração média de uma transação é mais curta (conclusão mais rápida; consulte o gráfico). A vantagem do SCO é especialmente significativa durante a contenção de bloqueio.

• O SCO vs. Teorema de Desempenho SS2PL

SCO fornece tempo médio de conclusão de transação mais curto do que SS2PL, se houver conflitos de leitura e gravação. SCO e SS2PL são idênticos de outra forma (têm comportamento de bloqueio idêntico com conflitos de gravação-leitura e gravação-gravação).

O SCO é tão prático quanto o SS2PL, pois, como o SS2PL, ele fornece, além de serializabilidade, também rigidez, que é amplamente utilizado como base para recuperação eficiente de bancos de dados de falhas. Um mecanismo SS2PL pode ser convertido em um SCO para melhor desempenho de maneira direta, sem alterar os métodos de recuperação. Uma descrição de uma implementação SCO pode ser encontrada em (Perrizo e Tatarinov 1998). Consulte também Agendador de banco de dados semi-otimista .

SS2PL é um subconjunto adequado de SCO (que é outra explicação de porque SCO é menos restritivo e fornece mais simultaneidade do que SS2PL).

CO otimista (OCO)

Para implementar o pedido de confirmação otimista (OCO), o algoritmo local genérico de CO é utilizado sem bloqueio de acesso a dados e, portanto, sem bloqueios locais. OCO sem transações ou restrições de agendamento de operação cobre toda a classe CO e não é um caso especial da classe CO, mas sim uma variante CO útil e caracterização do mecanismo.

CO estendido (ECO)

Caracterização geral do ECO

O pedido de compromisso estendido (ECO; ( Raz 1993a )) generaliza CO. Quando as transações locais (transações confinadas a um único banco de dados) podem ser distinguidas de transações globais (distribuídas) (transações que abrangem dois bancos de dados ou mais), o pedido de compromisso é aplicado ao global transações apenas. Assim, para que uma programação local (para um banco de dados) tenha a propriedade ECO, a ordem cronológica (parcial) dos eventos de confirmação de transações globais apenas (sem importância para transações locais) é consistente com sua ordem no respectivo gráfico de conflito local.

• Definição: pedido de compromisso estendido

Sejam duas transações globais confirmadas em uma programação, de forma que um caminho direcionado de transações não interrompidas exista no gráfico de conflito ( gráfico de precedência ) de para ( precede , possivelmente transitivamente , indiretamente). A programação tem a propriedade de pedido de confirmação estendida (ECO), se para cada duas dessas transações confirma antes de confirmações. ${\ displaystyle T_ {1}, T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

Um algoritmo distribuído para garantir a existência de ECO global. Quanto ao CO, o algoritmo precisa apenas (não modificado) de mensagens de protocolo de confirmação atômica. Para garantir a serialização global, cada banco de dados precisa garantir também a serialização de conflitos de suas próprias transações por qualquer mecanismo de controle de simultaneidade (local).

• O ECO e o Teorema da Serializabilidade Global

1. (Local, o que implica global) ECO juntamente com serializabilidade de conflito local, é uma condição suficiente para garantir serializabilidade de conflito global.
2. Quando nenhuma informação de controle de simultaneidade além das mensagens de confirmação atômica é compartilhada fora de um banco de dados (autonomia) e as transações locais podem ser identificadas, também é uma condição necessária.

Veja uma prova de necessidade em ( Raz 1993a ).

Esta condição (ECO com serializabilidade local) é mais fraca do que CO e permite mais simultaneidade ao custo de um algoritmo local um pouco mais complicado (no entanto, não existe nenhuma diferença prática de sobrecarga com CO).

Quando todas as transações são consideradas globais (por exemplo, se nenhuma informação estiver disponível sobre as transações serem locais), ECO se reduz a CO.

O algoritmo ECO

Antes de uma transação global ser confirmada, um algoritmo ECO local genérico (para um banco de dados) aborta um conjunto mínimo de transações indecisas (nem confirmadas, nem canceladas; transações locais ou globais que são executadas localmente), que pode causar um ciclo posterior no gráfico de conflito. Este conjunto de transações abortadas (não únicas, ao contrário de CO) pode ser otimizado, se cada transação for atribuída com um peso (que pode ser determinado pela importância da transação e pelos recursos computacionais já investidos na transação em execução; a otimização pode ser realizada , por exemplo, por uma redução do problema de fluxo máximo em redes ( Raz 1993a ). Como no CO, esse conjunto depende do tempo e eventualmente se torna vazio. Praticamente, quase em todas as implementações necessárias, uma transação deve ser confirmada apenas quando o conjunto está vazio (e nenhuma otimização de conjunto é aplicável). O mecanismo de controle de simultaneidade local (para o banco de dados) (separado do algoritmo ECO) garante que os ciclos locais sejam eliminados (ao contrário do CO, o que implica serializabilidade por si só; no entanto, praticamente também para o CO um mecanismo de simultaneidade local é utilizado, pelo menos para garantir a Recuperabilidade). As transações locais podem ser sempre confirmadas simultaneamente (mesmo se existir uma relação de precedência, ao contrário do CO). Quando a ordem parcial local das transações globais (que é determinada pelo gráfico de conflito local, agora apenas com possíveis ciclos locais temporários, uma vez que os ciclos são eliminados por um mecanismo de serializabilidade local) permite, também as transações globais podem ser votadas para serem confirmadas simultaneamente ( quando todas as transações globais transitivamente (indiretas) precedentes (via conflito) são confirmadas, enquanto as transações locais transitivamente precedentes podem estar em qualquer estado. Isso em analogia à condição de votação simultânea mais forte do algoritmo de CO distribuído, onde todas as transações transitivamente precedentes precisam ser comprometido).

A condição para garantir o ECO Global pode ser resumida de forma semelhante ao CO:

• Teorema da estratégia de ordenação do ECO Global para Forçar o Voto

Sejamos indecisos (nem confirmados nem abortados) transações globais em um sistema de banco de dados que garante a serialização localmente, de modo que um caminho direcionado de transações não interrompidas exista no gráfico de conflito local (o do próprio banco de dados) de para . Então, ter encerrado (seja confirmado ou abortado) antes de ser votado para ser confirmado, em cada um desses sistemas de banco de dados em um ambiente multi-banco de dados, é uma condição necessária e suficiente para garantir o ECO Global (a condição garante ECO Global, que pode ser violada sem isto). ${\ displaystyle T_ {1}, T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$${\ displaystyle T_ {1}}$${\ displaystyle T_ {2}}$

ECO global (todos os ciclos globais no gráfico de conflito global são eliminados por comprometimento atômico) junto com serializabilidade local (ou seja, cada sistema de banco de dados mantém a serialização localmente; todos os ciclos locais são eliminados) implicam serializabilidade global (todos os ciclos são eliminados). Isso significa que se cada sistema de banco de dados em um ambiente de vários bancos de dados fornece serialização local (por qualquer mecanismo) e impõe a estratégia de ordenação de votos no teorema acima (uma generalização da estratégia de ordenação de votos de CO), então a serializabilidade global é garantida (nenhum CO local é necessário mais).

Da mesma forma que o CO, a situação de impasse de votação ECO pode ser resumida da seguinte forma:

• O Teorema do Impasse de Votação ECO

Deixe um ambiente de banco de dados múltiplo compreender sistemas de banco de dados que impõem, cada um, tanto Global ECO (usando a condição no teorema acima) quanto serializabilidade de conflito local (que elimina ciclos locais no gráfico de conflito global). Então, um impasse de votação ocorre se e somente se um ciclo global (abrange dois ou mais bancos de dados) existe no gráfico de conflito aumentado Global (também o bloqueio por um bloqueio de acesso a dados é representado por uma borda). Se o ciclo não for interrompido por qualquer aborto, então todas as transações globais nele envolvidas estão envolvidas no respectivo impasse de votação e, eventualmente, cada uma tem seu voto bloqueado (seja direta ou indiretamente por uma trava de acesso a dados). Se uma transação local reside no ciclo, ela pode estar em qualquer estado não interrompido (em execução, pronto ou confirmado; ao contrário de CO, nenhum bloqueio de confirmação local é necessário).

Tal como acontece com CO, isso significa que também deadlocks globais devido ao bloqueio de acesso a dados (com pelo menos um bloqueio de bloqueio) são deadlocks de votação e são resolvidos automaticamente por confirmação atômica.

CO multi-versão (MVCO)

O Pedido de Compromisso Multi-versão (MVCO; ( Raz 1993b )) é uma generalização do CO para bancos de dados com recursos multi-versão . Com esses recursos , as transações somente leitura não bloqueiam ou são bloqueadas para melhor desempenho. A utilização de tais recursos é uma forma comum hoje em dia de aumentar a simultaneidade e o desempenho, gerando uma nova versão de um objeto de banco de dados cada vez que o objeto é escrito e permitindo operações de leitura de transações de várias versões relevantes (de cada objeto). MVCO implica serializabilidade em uma cópia (1SER ou 1SR) que é a generalização da serialização para recursos de várias versões. Como o CO, o MVCO não bloqueia e pode ser combinado com qualquer mecanismo de controle de simultaneidade multi-versão relevante sem interferir nele. Na teoria subjacente apresentada para MVCO, os conflitos são generalizados para diferentes versões de um mesmo recurso (diferentemente das teorias anteriores de múltiplas versões). Para versões diferentes, a ordem cronológica do conflito é substituída pela ordem da versão e, possivelmente, revertida, mantendo as definições usuais para operações conflitantes. Os resultados para os gráficos de conflito regular e aumentado permanecem inalterados e, da mesma forma que para CO, existe um algoritmo de aplicação MVCO distribuído, agora para um ambiente misto com recursos de versão única e versão múltipla (agora versão única é um caso especial de versão múltipla ) Quanto ao CO, o algoritmo MVCO precisa apenas (não modificado) de mensagens de protocolo de confirmação atômica sem sobrecarga de comunicação adicional. Impasses globais baseados em bloqueio se traduzem em bloqueios de votação e são resolvidos automaticamente. Em analogia ao CO, o seguinte é válido:

• O MVCO e o Teorema Global de serializabilidade de uma cópia

1. A conformidade com MVCO de cada sistema de banco de dados autônomo (ou objeto transacional) em um ambiente de vários bancos de dados misto de bancos de dados de versão única e versão múltipla é uma condição necessária para garantir a serialização de uma cópia global (1SER).
2. A conformidade com MVCO de cada sistema de banco de dados é uma condição suficiente para garantir o Global 1SER.
3. Impasses globais baseados em bloqueio são resolvidos automaticamente.

Comentário : Agora, um sistema de banco de dados de versão única compatível com CO é automaticamente compatível com MVCO.

MVCO pode ser ainda mais generalizado para empregar a generalização de ECO (MVECO).

Exemplo: isolamento de instantâneo baseado em CO (COSI)

Isolamento de instantâneo baseado em CO (COSI) é a interseção do isolamento de instantâneo (SI) com MVCO. SI é um método de controle de simultaneidade multiversão amplamente utilizado devido ao bom desempenho e semelhança com serializabilidade (1SER) em vários aspectos. A teoria em (Raz 1993b) para MVCO descrita acima é utilizada posteriormente em (Fekete et al. 2005) e outros artigos sobre SI, por exemplo, (Cahill et al. 2008); veja também Tornando o isolamento de instantâneo serializável e as referências lá), para analisar conflitos no SI a fim de torná-lo serializável. O método apresentado em (Cahill et al. 2008), isolamento de instantâneo serializável (SerializableSI), uma modificação de baixa sobrecarga de SI, fornece bons resultados de desempenho em relação ao SI, com apenas uma pequena penalidade para impor a serialização. Um método diferente, combinando SI com MVCO (COSI), torna o SI serializável também, com uma sobrecarga relativamente baixa, semelhante a combinar o algoritmo CO genérico com mecanismos de versão única. Além disso, a combinação resultante, COSI, sendo compatível com MVCO, permite que sistemas de banco de dados compatíveis com COSI interfiram e participem de forma transparente em uma solução de CO para serialização distribuída / global (veja abaixo). Além dos overheads, também os comportamentos dos protocolos precisam ser comparados quantitativamente. Por um lado, todas as programações de SI serializáveis ​​podem ser feitas MVCO pelo COSI (por possíveis atrasos de confirmação quando necessário) sem abortar transações. Por outro lado, SerializableSI é conhecido por abortar e reiniciar desnecessariamente certas porcentagens de transações também em programações SI serializáveis.

CO e suas variantes são interoperáveis ​​de forma transparente para serialização global

Com CO e suas variantes (por exemplo, SS2PL, SCO, OCO, ECO e MVCO acima) a serialização global é alcançada por meio de algoritmos distribuídos baseados em protocolo de compromisso atômico . Para CO e todas as suas variantes, o protocolo de compromisso atômico é o instrumento para eliminar os ciclos globais (ciclos que abrangem dois ou mais bancos de dados) no gráfico de conflito global aumentado (e, portanto, também regular) (implicitamente; nenhuma implementação de estrutura de dados global é necessária). Em casos de pedidos de compromisso local incompatíveis em dois ou mais bancos de dados (quando nenhum pedido parcial global pode incorporar os respectivos pedidos parciais locais juntos), ou um bloqueio de acesso de dados relacionado ao impasse de votação, ambos implicando em um ciclo global no gráfico de conflito ampliado global e votos perdidos, o protocolo de confirmação atômica quebra tal ciclo abortando uma transação indecisa nele (veja O algoritmo de CO distribuído acima). As diferenças entre as várias variantes existem apenas no nível local (dentro dos sistemas de banco de dados participantes). Cada instância local de CO de qualquer variante tem a mesma função, para determinar a posição de cada transação global (uma transação que abrange dois ou mais bancos de dados) dentro da ordem de confirmação local, ou seja, para determinar quando é a vez da transação ser votada localmente no protocolo de confirmação atômica. Assim, todas as variantes do CO exibem o mesmo comportamento em relação ao comprometimento atômico. Isso significa que todos eles são interoperáveis ​​via compromisso atômico (usando as mesmas interfaces de software, normalmente fornecidas como serviços , alguns já padronizados para compromisso atômico, principalmente para o protocolo two phase commit , por exemplo, X / Open XA ) e de forma transparente podem ser utilizados juntos em qualquer ambiente distribuído (enquanto cada instância de variante CO está possivelmente associada a qualquer tipo de mecanismo de controle de simultaneidade local relevante).

Em resumo, qualquer transação global única pode participar simultaneamente em bancos de dados que podem empregar cada uma, possivelmente diferente, variante de CO (enquanto executa processos simultaneamente em cada banco de dados e simultaneamente com transações locais e outras transações globais em cada banco de dados). O protocolo de comprometimento atômico é indiferente ao CO e não faz distinção entre as várias variantes de CO. Qualquer ciclo global gerado no gráfico de conflito global aumentado pode abranger bancos de dados de diferentes variantes de CO e gerar (se não for quebrado por qualquer aborto local) um impasse de votação que é resolvido por comprometimento atômico exatamente da mesma maneira que em um ambiente de variante de CO único. ciclos locais (agora possivelmente com conflitos mistos materializados e não materializados, tanto serializabilidade quanto deadlock de bloqueio de acesso de dados relacionados, por exemplo, SCO) são resolvidos localmente (cada um por seus respectivos mecanismos locais de instância de variante).

A ordenação de votos (VO ou CO generalizado (GCO); Raz 2009 ), a união de CO e todas as suas variantes acima, é um conceito útil e uma técnica de serializabilidade global. Para cumprir o VO, serializabilidade local (em sua forma mais geral, baseada na comutatividade e incluindo multi-versão) e a estratégia de ordem de voto (votação por ordem de precedência local) são necessárias.

Combinando os resultados para CO e suas variantes, conclui-se o seguinte:

• O Teorema de Interoperabilidade das Variantes CO

1. Em um ambiente de banco de dados múltiplo, onde cada sistema de banco de dados (objeto transacional) é compatível com alguma propriedade de variante CO (compatível com VO), qualquer transação global pode participar simultaneamente em bancos de dados de variantes CO possivelmente diferentes, e serializabilidade global é garantida ( condição suficiente para Serializabilidade global e serialização global de uma cópia (1SER), para um caso em que existe um banco de dados de várias versões).
2. Se apenas informações de controle de simultaneidade local (para um sistema de banco de dados) forem utilizadas por cada sistema de banco de dados (cada um tem a propriedade de autonomia generalizada , uma generalização de autonomia ), então a conformidade de cada um com alguma (qualquer) propriedade variante de CO (conformidade de VO) é um condição necessária para garantir a serializabilidade Global (e Global 1SER; caso contrário, podem ser violados).
3. Além disso, em tal ambiente de bloqueio de acesso a dados, deadlocks globais relacionados são resolvidos automaticamente (cada um desses deadlock é gerado por um ciclo global no gráfico de conflito aumentado (ou seja, um deadlock de votação ; veja acima), envolvendo pelo menos um bloqueio de acesso a dados (conflito não materializado) e dois sistemas de banco de dados; portanto, não é um ciclo no gráfico de conflito regular e não afeta a serialização).

Referências

• Raz, Yoav (agosto de 1992), "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment" (PDF) , Anais da Décima Oitava Conferência Internacional sobre Bases de Dados Muito Grandes , Vancouver, Canadá , pp. 292-312 (também DEC-TR 841, Digital Equipment Corporation , novembro de 1990)
• Raz, Yoav (setembro de 1994), "Serializability by Commitment Ordering", Information Processing Letters , 51 (5): 257–264, doi : 10.1016 / 0020-0190 (94) 90005-1
• Raz, Yoav (junho de 2009), Teoria da Ordem de Compromisso: Resumo , recuperado em 11 de novembro de 2011
• Raz, Yoav (novembro de 1990), On the Significance of Commitment Ordering (PDF) , Digital Equipment Corporation
• Yoav Raz (1991a): Patentes dos EUA 5.504.899 (ECO) 5.504.900 (CO) 5.701.480 (MVCO)
• Yoav Raz (1991b): "O Coordenador de Pedidos de Compromisso (COCO) de um Gerente de Recursos ou Arquitetura para Controle de Concorrência Baseado em Pedidos de Compromisso Distribuído", DEC-TR 843, Digital Equipment Corporation, dezembro de 1991.
• Yoav Raz (1991c): "Locking Based Strict Commitment Ordering, or How to better Concurrency in Locking Based Resource Managers", DEC-TR 844, dezembro de 1991.
• Yoav Raz (1993a): "Pedido de Compromisso Estendido ou Garantindo Serializabilidade Global Aplicando Seletividade de Pedido de Compromisso a Transações Globais." Proceedings of the Twelfth ACM Symposium on Principles of Database Systems (PODS), Washington, DC, pp. 83-96, maio de 1993. (também DEC-TR 842, novembro de 1991)
• Yoav Raz (1993b): "Controle de simultaneidade distribuída com base em pedidos de compromisso para recursos de uma e várias versões". Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Vienna, Austria, pp. 189-198, abril de 1993. (também DEC-TR 853, julho de 1992)

Notas de rodapé

links externos

• Página de pedidos de Compromisso de Yoav Raz