Serializabilidade
Content
Correção
Serializabilidade
A serialização é usada para manter os dados no item de dados em um estado consistente. A serialização é uma propriedade de um cronograma de transações (histórico). Ele se refere à propriedade de isolamento de uma transação de banco de dados.
Serializability of a schedule means equivalence (in the outcome, the database state, data values) to a serial schedule (i.e., sequential with no transaction overlap in time) with the same transactions. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems.[citation needed]The rationale behind serializability is the following:If each transaction is correct by itself, i.e., meets certain integrity conditions, then a schedule that comprises any serial execution of these transactions is correct (its transactions still meet their conditions): "Serial" means that transactions do not overlap in time and cannot interfere with each other, i.e, complete isolation between each other exists. Any order of the transactions is legitimate, if no dependencies among them exist, which is assumed (see comment below). As a result, a schedule that comprises any execution (not necessarily serial) that is equivalent (in its outcome) to any serial execution of these transactions, is correct.Os cronogramas que não são serializáveis provavelmente gerarão resultados incorretos. Exemplos bem conhecidos são com transações que débito e crédito com dinheiro: se os cronogramas relacionados não forem serializáveis, a soma total de dinheiro pode não ser preservada. O dinheiro pode desaparecer ou ser gerado do nada. Isso e violações de outras conservantes invariantes possivelmente necessárias são causadas por uma escrita de transações e "pisando" e apagar o que foi escrito por outra transação antes de se tornar permanente no banco de dados. Isso não acontece se a serialização for mantida.
Se alguma ordem específica entre algumas transações for solicitada por um aplicativo, ela será aplicada independentemente dos mecanismos de serialização subjacente. Esses mecanismos são tipicamente indiferentes a qualquer ordem específica e geram alguma ordem parcial imprevisível que normalmente é compatível com várias ordens seriais dessas transações. Esta ordem parcial resulta das ordens de agendamento das operações de acesso a dados de transações simultâneas, que dependem de muitos fatores.
Uma característica importante de uma transação de banco de dados é a atomicidade, o que significa que ela se compromete, ou seja, todos os resultados de suas operações entram em vigor no banco de dados ou abortos (reverso), todos os resultados de suas operações não têm nenhum efeito no Database ("All ou Nada" Semântica de uma transação). Em todos os sistemas reais, as transações podem abortar por muitas razões, e a serializabilidade por si só não é suficiente para a correção. Os horários também precisam possuir a propriedade de recuperação (de abort). A recuperação significa que as transações comprometidas não leram dados escritos por transações abortadas (cujos efeitos não existem nos estados do banco de dados resultantes). Embora a serialização seja atualmente comprometida de propósito em muitos aplicativos para um melhor desempenho (apenas nos casos em que a correção do aplicativo não é prejudicada), comprometer a recuperação violar rapidamente a integridade do banco de dados, bem como os resultados das transações externas ao banco de dados. Um cronograma com a propriedade de recuperação (um cronograma recuperável) "se recupera" de abortos por si só, ou seja, os abortos não prejudicam a integridade de suas transações comprometidas e o banco de dados resultante. Isso é falso sem recuperação, onde as prováveis violações de integridade (dados de banco de dados incorretas resultantes) precisam de ações corretivas especiais, normalmente manuais no banco de dados.
A implementação da recuperação em sua forma geral pode resultar em abortos em cascata: abortar uma transação pode resultar na necessidade de abortar uma segunda transação e, em seguida, um terceiro e assim por diante. Isso resulta em um desperdício de transações já executadas parcialmente e pode resultar também em uma penalidade de desempenho. Evitar abortos em cascata (ACA, ou cascata) é um caso especial de recuperação que impede exatamente esses fenômenos. Muitas vezes, na prática, é utilizado um caso especial de ACA: rigor. O rigor permite a recuperação eficiente do banco de dados da falha.
Observe que a propriedade de recuperação é necessária, mesmo que não ocorra falha no banco de dados e nenhuma recuperação de banco de dados da falha seja necessária. É necessário que seja necessário lidar corretamente automaticamente abortos, o que pode não estar relacionado à falha do banco de dados e à recuperação da falha.
Serializabilidade relaxante
Em muitas aplicações, diferentemente das finanças, não é necessário correção absoluta. Por exemplo, ao recuperar uma lista de produtos de acordo com a especificação, na maioria dos casos, isso não importa muito se um produto, cujos dados foram atualizados há pouco tempo, não aparecerá na lista, mesmo que atenda à especificação. Normalmente, ele aparecerá em uma lista assim quando tentada novamente pouco tempo depois. Os bancos de dados comerciais fornecem controle de simultaneidade com toda uma gama de níveis de isolamento que são de fato violações de serialização (controladas) para obter maior desempenho. O desempenho mais alto significa melhor taxa de execução da transação e tempo médio de resposta mais curto da transação (duração da transação). O isolamento do instantâneo é um exemplo de um método de serialização relaxado e eficiente amplamente utilizado popular, com muitas características de serialização total, mas ainda sem algumas, e imprópria em muitas situações.
Outra razão comum hoje em dia para o relaxamento de serialização distribuída (veja abaixo) é a exigência de disponibilidade de produtos e serviços da Internet. Esse requisito é normalmente respondido por replicação de dados em larga escala. A solução direta para sincronizar as atualizações das réplicas do mesmo objeto de banco de dados está incluindo todas essas atualizações em uma única transação distribuída atômica. No entanto, com muitas réplicas, essa transação é muito grande e pode abranger o suficiente de vários computadores e redes que alguns deles provavelmente não estão disponíveis. Assim, é provável que essa transação termine com abortar e perder seu propósito. Consequentemente, a replicação otimista (replicação preguiçosa) é frequentemente utilizada (por exemplo, em muitos produtos e serviços do Google, Amazon, Yahoo e similares), enquanto a serialização é relaxada e comprometida por eventual consistência. Novamente, neste caso, o relaxamento é feito apenas para aplicativos que não devem ser prejudicados por essa técnica.
As classes de cronogramas definidos por propriedades de serialização relaxadas contêm a classe de serialização ou são incomparáveis com ela.
Visualização e serialização de conflito
Os mecanismos que aplicam a serialização precisam ser executados em tempo real, ou quase em tempo real, enquanto as transações estão sendo executadas a taxas altas. Para atender a esse requisito, são utilizados casos especiais de serialização, condições suficientes de serialização que podem ser aplicadas de maneira eficaz, são utilizadas.
Existem dois tipos principais de serialização: visualização de visualização e conflito-serriizabilidade. View-seriizability corresponde à definição geral de serialização fornecida acima. O conflito-seriizabilidade é um amplo caso especial, ou seja, qualquer cronograma que seja serializável ao conflito também é serializável à vista, mas não necessariamente o oposto. A serialização de conflito é amplamente utilizada porque é mais fácil determinar e abrange uma parte substancial dos cronogramas serviados em exibição. Determinar a assistência à vista de um cronograma é um problema de NP-completo (uma classe de problemas apenas com soluções conhecidas de dificuldades e com demora).
View-serializability of a schedule is defined by equivalence to a serial schedule (no overlapping transactions) with the same transactions, such that respective transactions in the two schedules read and write the same data values ("view" the same data values).Conflict-serializability of a schedule is defined by equivalence to a serial schedule (no overlapping transactions) with the same transactions, such that both schedules have the same sets of respective chronologically ordered pairs of conflicting operations (same precedence relations of respective conflicting operations).As operações nos dados são lidas ou graves (uma gravação: insira ou modifique ou exclua). Duas operações são conflitantes se forem de transações diferentes, no mesmo dado (item de dados) e pelo menos um deles é gravação. Cada um desses pares de operações conflitantes tem um tipo de conflito: é um conflito de leitura - escrita ou gravação ou gravação. Diz -se que a transação da segunda operação no par está em conflito com a transação da primeira operação. Uma definição mais geral de operações conflitantes (também para operações complexas, que podem consistir em várias operações "simples" de leitura/gravação) exige que elas sejam não comutativas (alterando seu pedido também altera seu resultado combinado). Cada uma operação precisa ser atômica por si só (usando o suporte adequado do sistema) para ser considerado uma operação para uma verificação de comutatividade. Por exemplo, as operações de leitura -leitura são comutativas (ao contrário de Read -Write e outras possibilidades) e, portanto, a leitura de leitura não é um conflito. Outro exemplo mais complexo: o incremento e o decréscimo de operações de um contador são as duas operações de gravação (ambos modificam o contador), mas não precisam ser considerados conflitantes (tipo de conflito de gravação de gravação), pois são comutativos (assim o incremento-o declínio não é Um conflito; por exemplo, já foi apoiado no IMS "Path Fast" do antigo IBM). Somente a precedência (ordem do tempo) em pares de operações conflitantes (não comutativas) é importante ao verificar a equivalência a um cronograma serial, uma vez que diferentes agendas que consistem nas mesmas transações podem ser transformadas de uma para outra, alterando as ordens entre as diferentes operações de transações ( intercalação de diferentes transações) e, uma vez que a alteração das ordens de operações comutativas (não conflitos) não altera um resultado geral da sequência de operação, isto é, um resultado de cronograma (o resultado é preservado através da mudança de ordem entre operações não conflitantes, mas normalmente não quando quando Operações conflitantes alteram a ordem). Isso significa que, se um cronograma puder ser transformado em qualquer cronograma serial sem alterar as ordens de operações conflitantes (mas alterando ordens de não conflição, preservando a ordem de operação dentro de cada transação), o resultado de ambos os horários é o mesmo e o cronograma é conflito serializável por definição.
Os conflitos são a razão para bloquear transações e atrasos (conflitos não materiais) ou para abortar transações devido à prevenção da violação da serializabilidade. Ambas as possibilidades reduzem o desempenho. Reduzir assim o número de conflitos, por exemplo, por transferência (quando possível), é uma maneira de aumentar o desempenho.
Uma transação pode emitir/solicitar uma operação conflitante e estar em conflito com outra transação enquanto sua operação conflitante é atrasada e não executada (por exemplo, bloqueada por um bloqueio). Somente operações conflitantes executadas (materializadas) são relevantes para a serialização de conflitos (veja mais abaixo).
Aplicação da serializabilidade do conflito
Teste de serialização do conflito
A conformidade com o cronograma com a serialização de conflitos pode ser testada com o gráfico de precedência (gráfico de serialização, gráfico de serialização, gráfico de conflitos) para transações comprometidas do cronograma. É o gráfico direcionado que representa a precedência de transações no cronograma, conforme refletido pela precedência de operações conflitantes nas transações.
In the precedence graph transactions are nodes and precedence relations are directed edges. There exists an edge from a first transaction to a second transaction, if the second transaction is in conflict with the first (see Conflict serializability above), and the conflict is materialized (i.e., if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a lock on the operation's object, held by another transaction, or when writing to a transaction's temporary private workspace and materializing, copying to the database itself, upon commit; as long as a requested/issued conflicting operation is not executed upon the database itself, the conflict is non-materialized; non-materialized conflicts are not represented by an edge in the precedence graph).Comment: In many text books only committed transactions are included in the precedence graph. Here all transactions are included for convenience in later discussions.A observação a seguir é uma caracterização essencial da serialização de conflitos:
A schedule is conflict-serializable if and only if its precedence graph of committed transactions (when only committed transactions are considered) is acyclic. This means that a cycle consisting of committed transactions only is generated in the (general) precedence graph, if and only if conflict-serializability is violated.Ciclos de transações comprometidas podem ser evitadas abortando uma transação indecisa (nem comprometida, nem abortada) em cada ciclo no gráfico de precedência de todas as transações, que de outra forma podem se transformar em um ciclo de transações comprometidas (e uma transação comprometida não pode ser abortada) . Uma transação abortada por ciclo é necessária e suficiente em número para quebrar e eliminar o ciclo (mais abortos são possíveis e podem ocorrer sob alguns mecanismos, mas são desnecessários para a serialização). A probabilidade de geração de ciclo é tipicamente baixa, mas, no entanto, essa situação é cuidadosamente tratada, normalmente com uma quantidade considerável de sobrecarga, pois a correção está envolvida. As transações abortadas devido à prevenção da violação da serialização são reiniciadas e executadas novamente imediatamente.
Os mecanismos de reforço de serialização normalmente não mantêm um gráfico de precedência como uma estrutura de dados, mas impedem ou quebram ciclos implicitamente (por exemplo, SS2pl abaixo).
Mecanismo comum - SS2PL
O forte bloqueio bifásico rigoroso (SS2PL) é um mecanismo comum utilizado nos sistemas de banco de dados desde seus primeiros dias na década de 1970 (o "SS" no nome SS2PL é mais recente, no entanto) para aplicar a serializabilidade do conflito e a rigor (um caso especial de Recuperação que permite a recuperação eficaz do banco de dados da falha) de um cronograma. Sob esse mecanismo, cada dado é bloqueado por uma transação antes de acessá -lo (em qualquer operação de leitura ou gravação): o item é marcado e associado a uma trava de um certo tipo, dependendo da operação que está sendo realizada (e da implementação específica da transação ; existem vários modelos com diferentes tipos de bloqueio; em alguns modelos, os bloqueios podem mudar o tipo durante a vida da transação). Como resultado, o acesso por outra transação pode ser bloqueado, normalmente em um conflito (os atrasos na trava ou impede completamente o conflito de ser materializado e refletido no gráfico de precedência, bloqueando a operação conflitante), dependendo do tipo de bloqueio e da outra transação Tipo de operação de acesso. Empregar um mecanismo SS2PL significa que todos os bloqueios em dados em nome de uma transação são liberados somente após o término da transação (comprometida ou abortada).
O SS2PL também é o nome da propriedade de programação resultante, que também é chamada de rigor. SS2PL é um caso especial (subconjunto adequado) de bloqueio bifásico (2pl)
O bloqueio mútuo entre as transações resulta em um impasse, onde a execução dessas transações é paralisada e nenhuma conclusão pode ser alcançada. Assim, os deadlocks precisam ser resolvidos para concluir a execução dessas transações e liberar recursos de computação relacionados. Um impasse é um reflexo de um ciclo potencial no gráfico de precedência que ocorreria sem o bloqueio quando os conflitos são materializados. Um impasse é resolvido abortando uma transação envolvida com esse ciclo potencial e quebrando o ciclo. É frequentemente detectado usando um gráfico de espera (um gráfico de conflitos bloqueados por bloqueios de ser materializado; também pode ser definido como o gráfico de conflitos não materiais; conflitos não materializados não são refletidos no gráfico de precedência e não afetam Serializability), que indica qual transação está "aguardando" a liberação de um dos mais bloqueios pelos quais outras transações ou transações, e um ciclo neste gráfico significa um impasse. Abortar uma transação por ciclo é suficiente para quebrar o ciclo. As transações abortadas devido à resolução de impasse são reiniciadas e executadas novamente imediatamente.
Outras técnicas de aplicação
Outros mecanismos conhecidos incluem:
Precedence graph (or Serializability graph, Conflict graph) cycle eliminationTwo-phase locking (2PL)Timestamp ordering (TO)Serializable snapshot isolation (SerializableSI)As técnicas de serialização (conflitos) acima (conflitos) em sua forma geral não fornecem recuperação. Aprimoramentos especiais são necessários para adicionar recuperação.
Optimistic versus pessimistic techniquesAs técnicas de controle de simultaneidade são de três tipos principais:
Pessimistic: In Pessimistic concurrency control, a transaction blocks the data access operations of other transactions upon conflicts, and conflicts are non-materialized until blocking is removed. This is done to ensure that operations that may violate serializability (and in practice also recoverability) do not occur.Optimistic: In Optimistic concurrency control, the data access operations of other transactions are not blocked upon conflicts, and conflicts are immediately materialized. When the transaction reaches the ready state, i.e., its running state has been completed, possible serializability (and in practice also recoverability) violation by the transaction's operations (relative to other running transactions) is checked: if violation has occurred, the transaction is typically aborted (sometimes aborting another transaction to handle serializability violation is preferred). Otherwise, it is committed.Semi-optimistic: Mechanisms that mix blocking in certain situations with not blocking in other situations and employ both materialized and non-materialized conflictsAs principais diferenças entre os tipos de técnicas são os tipos de conflito gerados por eles. Um método pessimista bloqueia uma operação de transação em conflito e gera um conflito não materializado, enquanto um método otimista não bloqueia e gera um conflito materializado. Um método semi-otimista gera ambos os tipos de conflitos. Ambos os tipos de conflito são gerados pelas ordens cronológicas nas quais as operações de transação são invocadas, independentemente do tipo de conflito. Um ciclo de transações comprometidas (com conflitos materializados) no gráfico de precedência (conflito gráfico) representa uma violação de serialização e deve ser evitado para manter a serialização. Um ciclo de conflitos (não materiais) no gráfico de espera representa uma situação de impasse, que deve ser resolvida quebrando o ciclo. Ambos os tipos de ciclo resultam de conflitos e devem ser quebrados. Sob qualquer tipo de técnica, os conflitos devem ser detectados e considerados, com despesas gerais semelhantes para conflitos materializados e não materiais (normalmente usando mecanismos como travamento, bloqueando bloqueios ou não bloqueando, mas registrando conflitos para conflitos materializados). Em um método de bloqueio, normalmente ocorre uma troca de contexto após o conflito, com (adicional) sobrecarga incorrida. Caso contrário, os recursos de computação relacionados às transações bloqueadas permanecem ociosos, não utilizados, o que pode ser uma alternativa pior. Quando os conflitos não ocorrem com frequência, os métodos otimistas geralmente têm uma vantagem. Com diferentes cargas de transação (mixagens de tipos de transação) um tipo de técnica (isto é, otimista ou pessimista) pode proporcionar um melhor desempenho que o outro.
A menos que as classes de cronograma estejam bloqueando inerentemente (ou seja, elas não podem ser implementadas sem o bloqueio de operações de acesso a dados; por exemplo, 2PL, SS2PL e SCO acima; consulte o gráfico), eles também podem ser implementados usando técnicas otimistas (por exemplo, serialização, recuperação).
Serializable multi-version concurrency controlSee also Multiversion concurrency control (partial coverage) and Serializable Snapshot Isolation in Snapshot isolationO controle de simultaneidade de várias versões (MVCC) é uma maneira comum hoje para aumentar a simultaneidade e o desempenho, gerando uma nova versão de um objeto de banco de dados sempre que o objeto é escrito e permitindo as operações de leitura das transações de várias últimas versões relevantes (de cada objeto), dependendo do método de agendamento. O MVCC pode ser combinado com todas as técnicas de serialização listadas acima (exceto Serializablesi, que é originalmente baseado em MVCC). É utilizado na maioria dos produtos DBMS de uso geral.
Atualmente, o MVCC é especialmente popular através da seriizabilidade relaxada (veja acima) Isolamento de instantâneos do método (SI), que fornece melhor desempenho do que a maioria dos mecanismos de serialização conhecidos (ao custo de possível violação de serialização em certos casos). O Serializablesi, que é um aprimoramento eficiente do SI para torná -lo serializável, destina -se a fornecer uma solução serializável eficiente. Serializablesi foi analisado através de uma teoria geral do MVCC
Serializabilidade distribuída
Visão geral
A serialização distribuída é a serialização de um cronograma de um sistema distribuído transacional (por exemplo, um sistema de banco de dados distribuído). Esse sistema é caracterizado por transações distribuídas (também chamadas de transações globais), isto é, transações que abrangem processos de computador (uma abstração do processo em um sentido geral, dependendo do ambiente de computação; por exemplo, encadeamento do sistema operacional) e possivelmente nós de rede. Uma transação distribuída compreende mais de uma das várias sub-transações locais que cada um tem estados, conforme descrito acima, para uma transação de banco de dados. Uma sub-transação local compreende um único processo, ou mais processos que normalmente falham juntos (por exemplo, em um único núcleo do processador). As transações distribuídas implicam a necessidade de um protocolo de confirmação atômica alcançar um consenso entre suas sub-transações locais sobre o comprometimento ou o aborto. Esses protocolos podem variar de um aperto de mão simples (unidirecional) entre os processos que falham juntos em protocolos mais sofisticados, como comprometimento bifásico, para lidar com casos mais complicados de falha (por exemplo, processo, nó, comunicação, etc. falha). A serialização distribuída é um dos principais objetivos do controle de simultaneidade distribuído para correção. Com a proliferação da Internet, computação em nuvem, computação em grade e dispositivos de computação pequenos, portáteis e poderosos (por exemplo, smartphones), a necessidade de técnicas de serialização distribuída eficaz para garantir a correção dentro e entre as aplicações distribuídas parece aumentar.
A serialização distribuída é alcançada pela implementação de versões distribuídas das técnicas centralizadas conhecidas. Normalmente, todas essas versões distribuídas exigem a utilização de informações de conflito (de conflitos materializados ou não materiais, ou, equivalentemente, precedência da transação ou informação de bloqueio; a serialização de conflito é geralmente utilizada) que não é gerada localmente, mas em diferentes processos e remoto Localizações. Assim, é necessária a distribuição de informações (por exemplo, relações de precedência, informações de bloqueio, registro de data e hora ou ingressos). Quando o sistema distribuído é de uma escala relativamente pequena e atrasos de mensagens no sistema são pequenos, os métodos centralizados de controle de simultaneidade podem ser usados inalterados enquanto certos processos ou nós no sistema gerenciam os algoritmos relacionados. No entanto, em um sistema em larga escala (por exemplo, grade e nuvem), devido à distribuição de tais informações, uma penalidade de desempenho substancial é normalmente incorrida, mesmo quando as versões distribuídas dos métodos (vs. os centralizados) são usados, principalmente Devido à latência de computador e comunicação. Além disso, quando essas informações são distribuídas, as técnicas relacionadas normalmente não são bem escaladas. Um exemplo bem conhecido em relação aos problemas de escalabilidade é um gerente de bloqueio distribuído, que distribui informações de bloqueio (conflito não materializado) em todo o sistema distribuído para implementar técnicas de travamento.