Serializabilidade modular

Benefícios do CO para a serialização global

Seamless, low overhead integration with any concurrency control mechanism, with neither changing any transaction's operation scheduling or blocking it, nor adding any new operation.Heterogeneity: Global serializability is achieved across multiple transactional objects (e.g., database management systems) with different (any) concurrency control mechanisms, without interfering with the mechanisms' operations.Modularity: Transactional objects can be added and removed transparently.Autonomy of transactional objects: No need of conflict or equivalent information distribution (e.g., local precedence relations, locks, timestamps, or tickets; no object needs other object's information).Scalability: With "normal" global transactions, computer network size and number of transactional objects can increase unboundedly with no impact on performance, andAutomatic global deadlock resolution.

Todos esses aspectos, exceto os dois primeiros, também são possuídos pelo popular SS2PL, que é um caso especial (restrito, bloqueador) de CO e herda muitas das qualidades de CO.

O problema global de serialização

Declaração de problemas

As dificuldades descritas acima se traduzem no seguinte problema:

Find an efficient (high-performance and fault tolerant) method to enforce Global serializability (global conflict serializability) in a heterogeneous distributed environment of multiple autonomous database systems. The database systems may employ different concurrency control methods. No limitation should be imposed on the operations of either local transactions (confined to a single database system) or global transactions (span two or more database systems).

Citações

A falta de uma solução apropriada para o problema global de serialização levou os pesquisadores a procurar alternativas à serialização como critério de correção em um ambiente multidatabase (por exemplo, consulte a serialização global relaxante abaixo) e o problema foi caracterizado como difícil e aberto. As duas citações a seguir demonstram a mentalidade sobre ela até o final do ano de 1991, com citações semelhantes em vários outros artigos:

"Without knowledge about local as well as global transactions, it is highly unlikely that efficient global concurrency control can be provided... Additional complications occur when different component DBMSs [Database Management Systems] and the FDBMSs [Federated Database Management Systems] support different concurrency mechanisms... It is unlikely that a theoretically elegant solution that provides conflict serializability without sacrificing performance (i.e., concurrency and/or response time) and availability exists."

A ordem de compromisso, introduzida publicamente em maio de 1991 (veja abaixo), fornece uma solução geral elegante eficiente, desde pontos de vista práticos e teóricos, até o problema global de serialização entre os sistemas de banco de dados com mecanismos de controle de simultaneidade possivelmente diferentes. Ele fornece serializabilidade de conflito sem efeito negativo na disponibilidade e sem desempenho não pior do que o padrão de fato para a serialização global, o caso especial de bido bifásico estrito da CO (SS2PL). Requer conhecimento sobre transações locais nem globais.

"Transaction management in a heterogeneous, distributed database system is a difficult issue. The main problem is that each of the local database management systems may be using a different type of concurrency control scheme. Integrating this is a challenging problem, made worse if we wish to preserve the local autonomy of each of the local databases, and allow local and global transactions to execute in parallel. One simple solution is to restrict global transactions to retrieve-only access. However, the issue of reliable transaction management in the general case, where global and local transactions are allowed to both read and write data, is still open."

A solução de ordenação de compromisso compreende integração eficaz de sistemas de gerenciamento de banco de dados autônomos com mecanismos de controle de simultaneidade possivelmente diferentes. Enquanto as transações locais e globais são executadas em paralelo sem restringir nenhuma operação de leitura ou gravação em transações locais ou globais e sem comprometer a autonomia dos sistemas.

Mesmo nos últimos anos, após a introdução pública da solução geral de ordenação de compromisso em 1991, o problema ainda foi considerado por muitos insolúveis:

"We present a transaction model for multidatabase systems with autonomous component systems, coined heterogeneous 3-level transactions. It has become evident that in such a system the requirements of guaranteeing full ACID properties and full local autonomy can not be reconciled..."

A citação acima é de um artigo de 1997 que proponha uma solução relaxada de serialização global (consulte Relaxing Global Serializability abaixo) e referenciando artigos de ordenação de compromisso (CO). A solução de CO suporta efetivamente as propriedades de ácido completo e a autonomia local completa, além de atender aos outros requisitos representados acima na seção Declaração do Problema e, aparentemente, foi incompreendido.

Pensamento semelhante que vemos também na citação a seguir de um artigo de 1998:

"The concept of serializability has been the traditionally accepted correctness criterion in database systems. However in multidatabase systems (MDBSs), ensuring global serializability is a difficult task. The difficulty arises due to the heterogeneity of the concurrency control protocols used by the participating local database management systems (DBMSs), and the desire to preserve the autonomy of the local DBMSs. In general, solutions to the global serializability problem result in executions with a low degree of concurrency. The alternative, relaxed serializability, may result in data inconsistency."

Além disso, o artigo citado acima propõe uma solução relaxada de serialização global, enquanto faz referência ao trabalho de CO. A solução CO para a serialização global, ambas as pontes entre diferentes protocolos de controle de simultaneidade, sem redução substancial de concorrência (e tipicamente menores, se houver) e mantém a autonomia dos DBMSs locais. Evidentemente, também aqui a CO foi mal interpretada. Esse mal -entendido continua até 2010 em um livro de alguns dos mesmos autores, onde a mesma técnica de serialização global relaxada, serialização de dois níveis, é enfatizada e descrita em detalhes, e o CO não é mencionado.

Por outro lado, a seguinte citação em CO aparece em um livro de 2009:

"Not all concurrency control algorithms use locks... Three other techniques are timestamp ordering, serialization graph testing, and commit ordering. Timestamp ordering assigns each transaction a timestamp and ensures that conflicting operations execute in timestamp order. Serialization graph testing tracks conflicts and ensures that the serialization graph is acyclic. Commit ordering ensures that conflicting operations are consistent with the relative order in which their transactions commit, which can enable interoperability of systems using different concurrency control mechanisms."Comments:Beyond the common locking based algorithm SS2PL, which is a CO variant itself, also additional variants of CO that use locks exist, (see below). However, generic, or "pure" CO does not use locks.Since CO mechanisms order the commit events according to conflicts that already have occurred, it is better to describe CO as "Commit ordering ensures that the relative order in which transactions commit is consistent with the order of their respective conflicting operations."

As características e propriedades da solução de CO são discutidas abaixo.

Soluções propostas

Várias soluções, algumas parciais, foram propostas para o problema global de serialização. Entre eles:

Global conflict graph (serializability graph, precedence graph) checkingDistributed Two phase locking (Distributed 2PL)Distributed Timestamp orderingTickets (local logical timestamps which define local total orders, and are propagated to determine global partial order of transactions)Commitment ordering

Perspectiva tecnológica

O problema da serialização global tem sido um assunto bastante pesquisado no final dos anos 80 e início dos anos 90. A Ordem de Compromisso (CO) forneceu uma solução geral eficaz para o problema, a visão sobre ela e o entendimento sobre possíveis generalizações de forte bloqueio estrito de duas fases (SS2PL), que é utilizado de maneira prática e quase exclusiva (em conjunto com os bifásicos Compromer protocolo (2pc)) desde a década de 1980 para alcançar a serialização global entre os bancos de dados. Um importante benefício lateral do CO é a resolução automática de impasse global global que ele fornece (isso é aplicável também ao SS2PL distribuído; embora os impasse globais tenham sido um importante sujeito de pesquisa para o SS2PL, a resolução automática foi negligenciada, exceto nos artigos de CO, até que hoje (2009)). Naquela época, existiam muitos tipos de sistemas de banco de dados comerciais, muitos não relacionais, e os bancos de dados eram relativamente muito pequenos. Os sistemas multi -banco de dados foram considerados uma chave para a escalabilidade do banco de dados por interoperabilidade dos sistemas de banco de dados, e a serialização global era urgentemente necessária. Desde então, o tremendo progresso na computação de poder, armazenamento e redes de comunicação resultou em ordens de magnitude aumentos nos tamanhos, taxas de transação e acesso remoto aos recursos de banco de dados, além de desaparecer os limites entre computação centralizada e distribuída um sobre redes locais rápidas e de baixa latência (por exemplo, Infiniband). Estes, juntamente com o progresso nas soluções distribuídas dos fornecedores de banco de dados (principalmente o SS2PL popular com 2PC, um padrão de fato que permite a interoperabilidade entre os bancos de dados de diferentes fornecedores (baseados em SS2PL); as tecnologias SS2PL e 2PC ganharam experiência e eficiência substanciais) Os sistemas de gerenciamento do fluxo de trabalho e a tecnologia de replicação de banco de dados, na maioria dos casos, forneceram soluções de tecnologia da informação satisfatórias e às vezes melhores, sem transações distribuídas atômicas de banco de dados multi em bancos de dados com diferentes controle de simultaneidade (ignorando o problema acima). Como resultado, o senso de urgência que existia com o problema naquele período e, em geral, com transações atômicas distribuídas de alto desempenho em bancos de dados com diferentes tipos de controle de concorrência, reduziu. No entanto, a necessidade de transações atômicas distribuídas simultâneas como um elemento fundamental da confiabilidade existe em sistemas distribuídos também além dos sistemas de banco de dados e, portanto, a necessidade da serialização global como critério de correção fundamental para esses sistemas transacionais (consulte também a serialização distribuída na serialização). Com a proliferação da Internet, computação em nuvem, computação de grade, pequenos, portáteis e poderosos dispositivos de computação (por exemplo, smartphones) e gerenciamento sofisticado de sistemas que a necessidade de técnicas eficazes de serialização global para garantir a correção dentro e entre as aplicações transacionais distribuídas parece aumentar, e, portanto, também a necessidade de ordenação de compromisso (incluindo os populares dos bancos de dados SS2PL; SS2PL, no entanto, não atende aos requisitos de muitos outros objetos transacionais).

A solução de ordenação de compromisso

Ordem de comprometimento (ou ordenação de comprometimento; CO) é a única serialização de alto desempenho, tolerante a falhas, que fornece uma solução que foi proposta como um mecanismo geral totalmente distribuído (nenhum componente central de computação ou estrutura de dados é necessária), mecanismo geral que pode ser combinado perfeitamente com qualquer mecanismo de controle de simultaneidade local (para um banco de dados) (consulte o resumo técnico). Como a propriedade CO de um cronograma é uma condição necessária para a serializabilidade global de bancos de dados autônomos (no contexto do controle de simultaneidade), ela fornece a única solução geral para bancos de dados autônomos (ou seja, se os bancos de dados autônomos não cumprirem a CO, a Serializability Global pode ser violado). Aparentemente, por pura sorte, a solução de CO possui muitas propriedades atraentes:

does not interfere with any transaction's operation, particularly neither block, restrict nor delay any data-access operation (read or write) for either local or global transactions (and thus does not cause any extra aborts); thus allows seamless integration with any concurrency control mechanism.allows optimistic implementations (non-blocking, i.e., non data access blocking).allows heterogeneity: Global serializability is achieved across multiple transactional objects with different (any) concurrency control mechanisms, without interfering with the mechanisms' operations.allows modularity: Transactional objects can be added and removed transparently.allows full ACID transaction support.maintains each database's autonomy, and does not need any concurrency control information distribution (e.g., local precedence relations, locks, timestamps, or tickets).does not need any knowledge about the transactions.requires no communication overhead since it only uses already needed, unmodified atomic commitment protocol messages (any such protocol; using fault tolerant atomic commitment protocols and database systems makes the CO solution fault tolerant).automatically resolves global deadlocks due to locking.scales up effectively with computer network size and number of databases, almost without any negative impact on performance, since each global transaction is typically confined to certain relatively small numbers of databases and network nodes.requires no additional, artificial transaction access operations (e.g., "take timestamp" or "take ticket"), which typically result in additional, artificial conflicts that reduce concurrency.requires low overhead.

A única sobrecarga incorrida pela solução de CO é a detecção localmente de conflitos (que já é feita por qualquer mecanismo de serialização conhecido, tanto pessimista quanto otimista) e pedindo localmente em cada sistema de banco de dados, tanto os compromissos (locais) das transações locais quanto a votação para o compromisso atômico de transações globais. Essa sobrecarga é baixa. O efeito líquido do CO pode ser alguns atrasos de eventos de confirmação (mas nunca mais atrasos que o SS2PL e, em média, menos). Isso torna o CO instrumental para o controle global de simultaneidade de sistemas multidatabase (por exemplo, sistemas de banco de dados federados). A teoria subjacente da ordem de compromisso, parte da teoria da serialização, é sólida e elegante (e até "matematicamente bonita"; referindo -se à estrutura e dinâmica de conflitos, ciclos gráficos e deadlocks), com implicações interessantes para aplicações distribuídas transacionais.

Todas as qualidades do CO na lista acima, exceto as três primeiras, também são possuídas pelo SS2PL, que é um caso especial de CO, mas bloqueando e restritivo. Isso explica parcialmente a popularidade do SS2PL como uma solução (praticamente, a única solução, por muitos anos) para alcançar a serialização global. No entanto, a propriedade 9 acima, a resolução automática de impasse global, não foi notada para SS2PL na literatura de pesquisa de banco de dados até hoje (2009; exceto nas publicações de CO). Isso, desde que o fenômeno dos mortes de votação em tais ambientes e sua resolução automática pelo protocolo de comprometimento atômico foi negligenciado.

A maioria dos sistemas de banco de dados existentes, incluindo todos os principais sistemas de banco de dados comercial, são baseados em bloqueio de duas fases rigorosos (SS2PL) e já compatíveis com CO. Assim, eles podem participar de uma solução baseada em CO para a serialização global em ambientes multidatabase sem nenhuma modificação (exceto o multiverso popular, onde aspectos adicionais de CO devem ser considerados). A obtenção de serialização global em bancos de dados baseados em SS2PL usando comprometimento atômico (principalmente usando o commit em duas fases, 2PC) tem sido empregado por muitos anos (ou seja, usando a mesma solução de CO para um caso especial específico; no entanto, nenhuma referência é conhecida antes de CO, que Observa a resolução automática de impasse global automática deste caso especial pelo processo de eliminação do ciclo global de conflito aumentado do Protocolo de Compromisso Atômico). Praticamente todos os ambientes de processamento de transações distribuídos existentes e produtos de suporte dependem do SS2PL e fornecem 2pc. De fato, o SS2PL, juntamente com o 2PC, tornou -se um padrão de fato. Esta solução é um controle de simultaneidade homogêneo, abaixo do ideal (quando a serialização e a rigor são necessárias; consulte a ordem estrita de compromisso; SCO), mas ainda assim eficazes na maioria dos casos, às vezes ao custo de aumento da potência de computação necessária relativamente ao ideal. (No entanto, para melhor desempenho, a serialização relaxada é usada sempre que os aplicativos permitem). Permite a inter-operação entre os diferentes tipos de sistemas de banco de dados compatíveis com SS2PL, ou seja, permitem heterogeneidade em aspectos que não sejam o controle de simultaneidade. O SS2PL é uma propriedade de programação muito restritiva e "assume" quando combinada com qualquer outra propriedade. Por exemplo, quando combinado com qualquer propriedade otimista, o resultado não é mais otimista, mas caracteristicamente SS2pl. Por outro lado, a CO não altera os padrões de agendamento de acesso de dados e as características de qualquer propriedade combinada permanecem inalteradas. Como também o CO usa o comprometimento atômico (por exemplo, 2PC) para alcançar a serialização global, como o SS2PL, qualquer sistema de banco de dados compatível com CO ou objeto transacional pode unir transparentemente ambientes baseados em SS2PL, usar 2PC e manter a serializabilidade global sem nenhuma mudança de ambiente. Isso faz com que o CO seja uma generalização natural e direta do SS2PL para qualquer sistema de banco de dados baseado em serialização de conflito, para todos os fins práticos.

A ordem de compromisso tem sido amplamente conhecida dentro das comunidades de processamento e bancos de dados de transações da Digital Equipment Corporation (DEC) desde 1990. Ela está sob confidencialidade da empresa devido a processos de patenteamento. O CO foi divulgado fora do DEC por palestras e distribuição de relatórios técnicos às pesquisas de banco de dados em maio de 1991, imediatamente após seu primeiro registro de patentes. Foi mal interpretado por muitos pesquisadores de banco de dados anos após sua introdução, o que é evidente pelas citações acima dos artigos em 1997-1998, referenciando os artigos de ordenação de compromisso. Por outro lado, o CO tem sido utilizado extensivamente como uma solução para a serialização global nos trabalhos em processos transacionais e, mais recentemente, no Re: Gridit, que é uma abordagem para o gerenciamento de transações na computação da grade convergente e na computação em nuvem. Veja mais na história da ordem do compromisso.

Relaxando a serialização global

Algumas técnicas foram desenvolvidas para a serialização global relaxada (ou seja, elas não garantem a serialização global; ver também a serialização relaxante). Entre eles (com várias publicações cada):

Quasi serializabilityTwo-level serializability

Embora os métodos de serialização relaxados locais (para um sistema de banco de dados) comprometam a serialização do ganho de desempenho (e são utilizados apenas quando o aplicativo pode tolerar possíveis imprecisões, ou sua integridade é ilesa), não é claro que vários métodos de seriização global relaxados propostos que comprometem global global Serializabilidade, forneça qualquer ganho de desempenho sobre a ordem de compromisso que garante a serialização global. Normalmente, a intenção declarada de tais métodos não tem sido o ganho de desempenho sobre os métodos eficazes de serialização global (que aparentemente foram desconhecidos pelos inventores), mas alternativas de critérios de correção devido à falta de um método de serialização global eficaz e efetiva. Estranhamente, alguns deles foram introduzidos anos após a introdução do CO, e outros até cotações sem perceber que fornece uma solução eficaz de serialização global e, portanto, sem fornecer nenhuma comparação de desempenho com o CO para justificá -los como alternativas à serialização global para algumas aplicações (por exemplo, serialização de dois níveis). A serialização de dois níveis é apresentada como um importante método global de controle de simultaneidade em uma edição de 2010 de um livro de texto sobre bancos de dados (de autoria de dois dos autores originais da serialização de dois níveis, onde um deles, Avi Silberschatz, também é um autor dos artigos de recuperação fortes originais). Este livro não menciona CO nem faz referência a ele e, estranhamente, aparentemente não considera a Co uma solução de serialização global válida.

Outra razão comum hoje em dia para o relaxamento global da serialização é 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 vários computadores e redes que algumas delas 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 da mesma forma), enquanto a serialização global é relaxada e comprometida por eventual consistência. Nesse caso, o relaxamento é feito apenas para aplicativos que não devem ser prejudicados por ele.

As classes de horários definidos pelas propriedades de serialização global relaxadas contêm a classe de serialização global ou são incomparáveis ​​com ela. O que diferencia as técnicas para as propriedades relaxadas de serialização de conflitos globais (RGCSR) das propriedades relaxadas de serialização de conflitos (RCSR) que não são RGCSR é tipicamente a maneira diferente dos ciclos globais (abrange dois ou mais bancos de dados) no gráfico de conflitos globais. Não existe distinção entre ciclos globais e locais para propriedades RCSR que não são RGCSR. RCSR contém rgcsr. Normalmente, as técnicas de RGCSR eliminam os ciclos locais, isto é, fornecem serialização local (que pode ser alcançada efetivamente por métodos regulares de controle de concorrência conhecidos); No entanto, obviamente eles não eliminam todos os ciclos globais (que alcançariam a serialização global).