Empurrando o versionamento de banco de dados para seus limites por meio de um novo algoritmo de instantâneos deslizantes e consultas eficientes de viagem no tempo

Johannes Lichtenberger Blocked Unblock Seguir Seguindo 31 de dezembro de 2018

Como a maioria dos sistemas de banco de dados atuais ainda simplesmente armazena estado atual ou passado em uma grande tabela relacional, nós investigamos quais são os drivers de desempenho e como melhorar o atual estado da arte. Implementamos um sistema de armazenamento de código aberto chamado Sirix (.io) do zero, que armazena instantâneos de pequeno porte, além de suporte a consultas sofisticadas de viagem no tempo, ao mesmo tempo em que compete com a eficiência dos sistemas de bancos de dados não temporais.

Visualização Sunbirst de um recurso armazenado no Sirix (mostrando dados do sistema de arquivos)

O que é um sistema de banco de dados temporal?

É um termo usado para descrever que um sistema é capaz de recuperar estados passados de seus dados. Normalmente, um banco de dados temporário armazena o tempo válido , quanto tempo um fato é verdadeiro no mundo real, bem como o tempo de transação , quando os dados realmente são confirmados no banco de dados.

Perguntas como: Dá-me a história do mês passado da taxa de câmbio do Euro-Libra. Qual foi o endereço dos clientes em 12 de julho de 2015, como foi registrado no dia? Eles se moveram ou corrigimos um erro? Nós tivemos erros no banco de dados, que foram corrigidos mais tarde?

Vamos voltar ou nos concentrar na questão de porque os dados históricos não foram retidos no passado e como os novos avanços de armazenamento nos últimos anos possibilitaram a construção de soluções sofisticadas para ajudar a responder a essas perguntas sem o obstáculo, estado-da-arte sistemas trazem.

Vantagens e desvantagens de drives flash como por exemplo SSDs

Como Marc Kramis aponta em seu artigo “ Cultivando Árvores Persistentes no Século XXI ”:

A mudança para flash drives motiva profundamente a mudança do paradigma do “estado atual” para a lembrança dos passos evolutivos que levam a esse estado.

O principal insight é que drives flash, como por exemplo SSDs, são comuns hoje em dia e não têm tempo de busca enquanto não são capazes de fazer modificações no local dos dados. Flash drives são organizados em páginas e blocos, enquanto blocos Devido às suas características, eles são capazes de ler dados em um nível de página bem granular, mas só podem apagar dados no nível de bloco mais grosseiro. Os blocos precisam ser apagados antes de serem atualizados. Assim, os dados atualizados primeiro são gravados em outro local. Um coletor de lixo marca os dados, que foram reescritos no novo local como apagados, para que novos dados possam ser armazenados no futuro. Além disso, as estruturas de índice são atualizadas.

Evolução do estado através de modificações refinadas

Além disso, Marc assinala que pequenas modificações, devido aos requisitos de cluster devido a leituras aleatórias lentas de tempos de busca de cabeça de disco tradicionalmente mecânicos, geralmente envolvem escrever não apenas os dados modificados, mas também todos os outros registros na página modificada, bem como um número de páginas com dados não modificados. Isso claramente é um efeito indesejado.

Como construímos um sistema de armazenamento de código aberto baseado nessas observações do zero

O Sirix armazena por revisão e por página-delta.

Devido ao tempo de busca zero dos flash drives, não precisamos agrupar os dados. O Sirix sempre agrupa dados durante confirmações de transação. Ele é baseado em um armazenamento somente de anexação. Os dados nunca são modificados no local.

Em vez disso, ele é copiado e anexado a um arquivo em uma passagem de pós-ordem da estrutura de árvore interna em lotes, uma vez que uma transação seja confirmada.

Nós emprestamos idéias do sistema de arquivos ZFS como por exemplo somas de verificação armazenadas em páginas de banco de dados pai / fragmentos de páginas, que formam uma árvore de merkle de auto-validação, bem como nossa estrutura de árvore interna de páginas de bancos de dados.

Em contraste com outras abordagens de copy-on-write (COW), no entanto, não copiamos simplesmente toda a página de registro, o que é um desperdício de espaço de armazenamento. Dependendo do algoritmo de versionamento usado, nós copiamos apenas um número de registros da página (toda vez que os registros são alterados).

Algoritmos de controle de versão para armazenamento e recuperação de instantâneos em nível de registro

Como a maioria dos sistemas de banco de dados, armazenamos no máximo um número fixo de registros, ou seja, os dados reais por página de banco de dados (atualmente, 512 registros, no máximo). Os registros em si são de tamanho variável. Registros de overlong, que excedem um tamanho predefinido em bytes, são armazenados em páginas de estouro adicionais e são referenciados apenas nas páginas de registro.

Implementamos várias estratégias de controle de versão mais conhecidas dos sistemas de backup para operações de cópia na gravação de páginas de registro. Ou seja, nós copiamos

  • as páginas de registro completas, ou seja, qualquer registro na página ( completo )
  • somente os registros alterados em uma página de registro em relação à versão anterior ( incremental )
  • somente os registros alterados em uma página de registro desde um despejo de página inteira ( diferencial )

É bem conhecido que cada uma dessas estratégias de versionamento tem suas vantagens e desvantagens. Simplesmente armazenar a página inteira ( cheia) é muito eficiente para operações de leitura. No entanto, o desempenho de gravação em comparação com todas as outras abordagens é o pior, pois copiamos todos os registros inalterados além de todos os registros alterados.

A conversão incremental é o outro extremo e o desempenho de gravação é o melhor, pois armazena o ótimo (apenas registros alterados), mas, por outro lado, a reconstrução de uma página precisa de instantâneos intermitentes de páginas, de modo que o desempenho não se deteriore em cada página. nova revisão da página à medida que o número de incrementos aumenta a cada nova versão.

A versão diferencial tenta equilibrar as leituras e as gravações um pouco melhor, mas ainda não é ideal. Cada vez que os registros de uma página são modificados, uma nova página é gravada, com todos os registros alterados desde o último despejo completo da página. Isso significa que apenas duas revisões do fragmento de página precisam ser lidas para reconstruir uma página de registro. No entanto, o desempenho de gravação também se deteriora a cada nova revisão da página.

A captura de tela mostra uma visualização (interativa) de subárvores movidas em Sirix através de feixes de arestas hierárquicas

Versões incrementais em relação ao desempenho de gravação, devido à exigência de despejos completos intermitentes da página, resultam em picos de gravação. O versionamento diferencial também sofre de um problema semelhante. Sem um despejo completo intermitente, muitos dados teriam que ser duplicados em cada nova gravação.

Marc Kramis surgiu com a idéia de um novo algoritmo de instantâneos deslizantes, que equilibra o desempenho de leitura / gravação para contornar os picos de gravação.

O algoritmo faz uso de janelas deslizantes. Primeiro, qualquer registro alterado deve ser armazenado, segundo qualquer registro, que seja mais antigo que um comprimento predefinido N da janela e que não tenha sido alterado durante essas N -evisões. Somente estas N- revisões no máximo precisam ser lidas. A busca dos fragmentos de páginas pode ser feita em paralelo ou simplesmente paramos quando a página inteira foi reconstruída, começando pela revisão mais recente.

Uma vez que garantimos que nosso sistema de armazenamento fosse escalonado linearmente para buscar revisões antigas, bem como a revisão mais recente e logarítmica para buscar e armazenar registros únicos, bem como revisões inteiras, focamos nossa atenção nas camadas superiores.

API do mesmo tipo

Em seguida, investimos muito trabalho para implementar uma interface DOM persistente (por exemplo, para armazenar documentos XML e, no futuro, documentos JSON nativamente).

Nossos registros são armazenados com identificadores estáveis, que nunca mudam, independentemente do fato de os registros serem atualizados ou não e onde residem fisicamente. Marcadores são inseridos para registros excluídos. A codificação é simplesmente first-child-, left-sibling, right-sibling, parent- e node-id para armazenar um tipo de representação DOM de nós XML / XDM atualmente.

Índices digitados, digitados e definidos pelo usuário

Em seguida, mudamos nosso foco novamente para implementar estruturas de índice definidas pelo usuário com versão.

Durante cada transação, faça um instantâneo não apenas dos dados armazenados, mas também dos índices gerados. Os índices atualmente são baseados em AVL-trees / AVL-nodes armazenados em páginas de registro em diferentes subárvores de nossa estrutura de árvore do ZFS interna.

Um resumo de caminho de todos os caminhos no recurso é mantido sempre atualizado.

Para permitir que os usuários aproveitem ao máximo nosso sistema de banco de dados temporário e, na verdade, respondam facilmente às perguntas mencionadas, provavelmente seria possível obter respostas de um sistema de banco de dados temporário que estendemos um compilador de consultas chamado Brackit.

Os usuários agora podem abrir revisões específicas, navegar na estrutura de árvore semelhante ao DOM para selecionar nós em uma revisão específica e, em seguida, navegar no tempo. Através de um novo eixo baseado no tempo é, por exemplo, facilmente possível analisar como o selecionado ou uma seqüência de registros / nós se parece na próxima revisão, a revisão anterior, a primeira ou a última revisão, as revisões passadas ou futuras , todas as revisões …

Além disso, podemos consultar um intervalo de revisões com base em determinados registros de data e hora ou nos IDs das revisões.

Mas e se quisermos importar várias revisões de documentos preexistentes ou comparar qualquer revisão armazenada em nosso sistema, independentemente do algoritmo de controle de versão que escolhemos?

Algoritmos de dif.

Algoritmo diff do FMSE

Primeiro implementamos um algoritmo diff chamado fast-matching-simple-editscript (FMSE) para suportar a importação de diferentes versões de um documento e cometer várias revisões em nosso sistema de armazenamento. O algoritmo não depende de identificadores de nó. Ele corresponde com base nas semelhanças de subárvores, calculando primeiro uma subseqüência comum mais longa (LCF) nos nós de folha do documento estruturado em árvore a ser importado (atualmente, XML, no futuro também JSON). Então ele tenta combinar o caminho de baixo para cima. Na próxima etapa, as operações de edição são aplicadas para transformar o documento de uma versão para outra. O algoritmo obviamente usa heurística na forma do problema de correção árvore-árvore e, portanto, NP-difícil. Ele funciona melhor e produz um script de edição mínimo, se os nós folha forem muito distintos.

Algoritmo baseado em ID usando opcionalmente os hashes armazenados

Para calcular diffs entre qualquer revisão de recursos do Sirix e independente do versioning em nível de página do registro nós desenvolvemos um algoritmo, que faz uso de nossos identificadores de registros estáveis (que é baseado em um gerador de seqüências, que nunca reatribui IDs ( a partir de registros excluídos, por exemplo) Se armazenarmos hashes dos nós durante a inserção, o algoritmo diff será capaz de pular subárvores inteiras se os identificadores de nó, assim como os hashes, corresponderem.

Descreve como o algoritmo de diff baseado em ID funciona

API RESTful não-bloqueante e assíncrona

Recentemente, criamos, em cima de nossas camadas XQuery e DOM-API, uma API de nível superior para se comunicar com um servidor Sirix baseado em Vert.x, Kotlin / Coroutines e Keycloak para autenticação. Os exemplos de implementação e uso já foram o assunto de outro artigo .

Uma abordagem de análise visual para comparar estruturas de árvore

Como mostrado em algumas capturas de tela, desenvolvemos uma abordagem do Visual Analytics para comparar as estruturas de árvore armazenadas no Sirix. No entanto, é um pouco datado e precisa ser portado para a web.

O que estamos trabalhando

Em seguida, investigaremos como melhor armazenar documentos JSON, o que simplesmente se resume à questão de quão detalhistas queremos que nossos registros sejam (por exemplo, nós de registro de objeto, nós de índice de array …)

No entanto, ficaríamos mais do que felizes em discutir futuras orientações e ideias. Qualquer ajuda é muito apreciada.