No outono de 2019, um evento muito esperado ocorreu na equipe Mail.ru Cloud iOS. O principal banco de dados para armazenamento persistente do estado do aplicativo tornou-se muito exótico para o mundo móvel Banco de dados mapeado em memória do Lightning (LMDB). Abaixo do corte, oferecemos uma revisão detalhada em quatro partes. Primeiro, vamos falar sobre as razões para uma escolha tão nada trivial e difícil. Em seguida, passaremos a considerar os três pilares no centro da arquitetura LMDB: arquivos mapeados em memória, árvore B+, abordagem copy-on-write para implementar transacionalidade e multiversão. Por fim, para a sobremesa - a parte prática. Nele veremos como projetar e implementar um esquema de banco de dados com várias tabelas, incluindo uma de índice, sobre a API de valor-chave de baixo nível.

Conteúdo

1. Motivação para implementação
2. Posicionamento LMDB
3. Três pilares do LMDB
   3.1. Baleia #1. Arquivos mapeados na memória
   3.2. Baleia #2. Árvore B+
   3.3. Baleia #3. Cópia na gravação
4. Projetando um esquema de dados sobre a API de valor-chave
   4.1. Abstrações Básicas
   4.2. Modelagem de Tabela
   4.3. Modelando relacionamentos entre tabelas

1. Motivação para implementação

Um ano em 2015, nos demos ao trabalho de medir a frequência com que a interface do nosso aplicativo fica atrasada. Fizemos isso por um motivo. Temos recebido reclamações mais frequentes de que às vezes o aplicativo para de responder às ações do usuário: os botões não podem ser pressionados, as listas não rolam, etc. Sobre a mecânica das medições contado no AvitoTech, então aqui dou apenas a ordem dos números.

Os resultados da medição tornaram-se um banho frio para nós. Descobriu-se que existem muito mais problemas causados ​​por congelamentos do que qualquer outro. Se antes de perceber esse fato o principal indicador técnico de qualidade era livre de falhas, então após o foco mudou em congelamento livre.

Tendo construído painel com congelamentos e depois de gastar quantitativo и qualidade análise de seus motivos, o principal inimigo ficou claro - a pesada lógica de negócios executada no thread principal da aplicação. A reação natural a essa desgraça foi um desejo ardente de empurrá-la para os fluxos de trabalho. Para resolver sistematicamente este problema, recorremos a uma arquitetura multithread baseada em atores leves. Dediquei-o à sua adaptação para o mundo iOS dois tópicos no Twitter coletivo e artigo sobre Habré. Como parte da narrativa atual, quero enfatizar os aspectos da decisão que influenciaram a escolha do banco de dados.​

O modelo de ator de organização do sistema assume que o multithreading se torna sua segunda essência. Os objetos modelados nele gostam de cruzar os limites do fluxo. E eles fazem isso não às vezes, aqui e ali, mas quase constantemente e em todos os lugares.​

O banco de dados é um dos componentes fundamentais do diagrama apresentado. Sua principal tarefa é implementar o macropadrão Banco de dados compartilhado. Se no mundo corporativo é usado para organizar a sincronização de dados entre serviços, no caso da arquitetura de atores - dados entre threads. Assim, precisávamos de um banco de dados que não causasse dificuldades mínimas ao trabalhar com ele em um ambiente multithread. Em particular, isso significa que os objetos obtidos dele devem ser pelo menos thread-safe e, idealmente, completamente não mutáveis. Como você sabe, este último pode ser utilizado simultaneamente a partir de vários threads sem recorrer a nenhum bloqueio, o que tem um efeito benéfico no desempenho.

O segundo fator significativo que influenciou a escolha do banco de dados foi nossa API em nuvem. Foi inspirado na abordagem de sincronização adotada pelo git. Tal como ele, pretendíamos API offline primeiro, o que parece mais do que apropriado para clientes em nuvem. Supunha-se que eles extrairiam o estado completo da nuvem apenas uma vez e, então, a sincronização, na esmagadora maioria dos casos, ocorreria por meio da implementação de alterações. Infelizmente, esta oportunidade ainda está apenas na zona teórica e os clientes não aprenderam a trabalhar com patches na prática. Há uma série de razões objetivas para isso, que, para não atrasar a introdução, deixaremos entre parênteses. Agora, o que interessa muito mais são as conclusões instrutivas da lição sobre o que acontece quando uma API diz “A” e seu consumidor não diz “B”.

Então, se você imaginar o git, que, ao executar um comando pull, em vez de aplicar patches a um instantâneo local, compara seu estado completo com o estado completo do servidor, então você terá uma ideia bastante precisa de como ocorre a sincronização na nuvem clientes. É fácil adivinhar que para implementá-lo, você precisa alocar duas árvores DOM na memória com metainformações sobre todos os arquivos locais e do servidor. Acontece que se um usuário armazena 500 mil arquivos na nuvem, então para sincronizá-lo é necessário recriar e destruir duas árvores com 1 milhão de nós. Mas cada nó é um agregado contendo um gráfico de subobjetos. Diante disso, os resultados do perfil eram esperados. Descobriu-se que mesmo sem levar em conta o algoritmo de fusão, o próprio procedimento de criação e posterior destruição de um grande número de pequenos objetos custa um bom dinheiro. A situação é agravada pelo fato de que a operação básica de sincronização está incluída em um grande número de scripts de usuário. Como resultado, fixamos o segundo critério importante na escolha de um banco de dados - a capacidade de implementar operações CRUD sem alocação dinâmica de objetos.

Outros requisitos são mais tradicionais e a lista completa é a seguinte.

1. Segurança do fio.
2. Multiprocessamento. Ditado pelo desejo de usar a mesma instância de banco de dados para sincronizar o estado não apenas entre threads, mas também entre o aplicativo principal e as extensões do iOS.
3. A capacidade de representar entidades armazenadas como objetos não mutáveis.​
4. Nenhuma alocação dinâmica nas operações CRUD.
5. Suporte a transações para propriedades básicas ACID: atomicidade, consistência, isolamento e confiabilidade.
6. Rapidez nos casos mais populares.

Com este conjunto de requisitos, o SQLite foi e continua sendo uma boa escolha. No entanto, como parte do estudo de alternativas, me deparei com um livro "Introdução ao LevelDB". Sob sua liderança, foi escrito um benchmark comparando a velocidade de trabalho com diferentes bancos de dados em cenários reais de nuvem. O resultado superou nossas expectativas mais loucas. Nos casos mais populares - colocar o cursor em uma lista ordenada de todos os arquivos e uma lista ordenada de todos os arquivos de um determinado diretório - o LMDB acabou sendo 10 vezes mais rápido que o SQLite. A escolha tornou-se óbvia.

2. Posicionamento LMDB

LMDB é uma biblioteca muito pequena (apenas 10 mil linhas) que implementa a camada fundamental mais baixa dos bancos de dados - armazenamento.

O diagrama acima mostra que comparar LMDB com SQLite, que também implementa níveis mais altos, geralmente não é mais correto do que SQLite com Core Data. Seria mais justo citar os mesmos mecanismos de armazenamento que concorrentes iguais - BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Existem até desenvolvimentos onde o LMDB atua como um componente de mecanismo de armazenamento para SQLite. O primeiro experimento desse tipo foi em 2012 Passei da LMDB Howard Chu. Descobertas acabou sendo tão intrigante que sua iniciativa foi adotada por entusiastas do OSS e encontrou sua continuação na pessoa LumoSQL. Em janeiro de 2020, o autor deste projeto foi Den Shearer apresentado em LinuxConfAu.

O LMDB é usado principalmente como mecanismo para bancos de dados de aplicativos. A biblioteca deve sua aparência aos desenvolvedores OpenLDAP, que estavam altamente insatisfeitos com o BerkeleyDB como base para seu projeto. Partindo de uma biblioteca modesta bárvore, Howard Chu foi capaz de criar uma das alternativas mais populares do nosso tempo. Ele dedicou seu relatório muito legal a essa história, bem como à estrutura interna do LMDB. "O banco de dados mapeado pela memória Lightning". Um bom exemplo de conquista de um depósito foi compartilhado por Leonid Yuryev (também conhecido como ileo) da Positive Technologies em seu relatório na Highload 2015 “O motor LMDB é um campeão especial”. Nele, ele fala sobre LMDB no contexto de uma tarefa semelhante de implementação do ReOpenLDAP, e o LevelDB já foi alvo de críticas comparativas. Como resultado da implementação, a Positive Technologies teve até um fork em desenvolvimento ativo MDBX com recursos, otimizações e recursos muito saborosos correções de bugs.

O LMDB é frequentemente usado como armazenamento no estado em que se encontra. Por exemplo, navegador Mozilla Firefox escolheu para uma série de necessidades e, a partir da versão 9, o Xcode preferido seu SQLite para armazenar índices.

O mecanismo também deixou sua marca no mundo do desenvolvimento móvel. Vestígios de seu uso podem ser encontrar no cliente iOS do Telegram. O LinkedIn foi ainda mais longe e escolheu o LMDB como armazenamento padrão para sua estrutura de cache de dados desenvolvida internamente, Rocket Data, sobre a qual contado em seu artigo em 2016.

O LMDB está lutando com sucesso por um lugar ao sol no nicho deixado pelo BerkeleyDB depois que ficou sob o controle da Oracle. A biblioteca é apreciada por sua velocidade e confiabilidade, mesmo em comparação com seus pares. Como você sabe, não existem almoços grátis, e gostaria de enfatizar a compensação que você terá que enfrentar ao escolher entre LMDB e SQLite. O diagrama acima demonstra claramente como o aumento da velocidade é alcançado. Primeiro, não pagamos por camadas adicionais de abstração além do armazenamento em disco. É claro que uma boa arquitetura ainda não pode prescindir deles, e eles inevitavelmente aparecerão no código da aplicação, mas serão muito mais sutis. Eles não conterão recursos que não sejam exigidos por uma aplicação específica, por exemplo, suporte para consultas na linguagem SQL. Em segundo lugar, torna-se possível implementar de forma otimizada o mapeamento das operações do aplicativo em solicitações de armazenamento em disco. Se SQLite no meu trabalho é baseado nas necessidades estatísticas médias de um aplicativo médio, então você, como desenvolvedor de aplicativos, conhece bem os principais cenários de carga de trabalho. Para uma solução mais produtiva, você terá que pagar um preço maior tanto pelo desenvolvimento da solução inicial quanto pelo seu suporte posterior.

3. Três pilares do LMDB

Tendo olhado para o LMDB de uma perspectiva aérea, era hora de ir mais fundo. As próximas três seções serão dedicadas a uma análise dos principais pilares sobre os quais assenta a arquitetura de armazenamento:

1. Arquivos mapeados em memória como mecanismo para trabalhar com disco e sincronizar estruturas de dados internas.
2. Árvore B+ como organização da estrutura dos dados armazenados.
3. Copy-on-write como uma abordagem para fornecer propriedades de transação ACID e multiversão.

3.1. Baleia #1. Arquivos mapeados na memória

Os arquivos mapeados na memória são um elemento arquitetônico tão importante que aparecem até no nome do repositório. As questões de cache e sincronização de acesso às informações armazenadas são inteiramente deixadas para o sistema operacional. O LMDB não contém nenhum cache dentro de si. Esta é uma decisão consciente do autor, uma vez que a leitura de dados diretamente dos arquivos mapeados permite cortar muitos atalhos na implementação do mecanismo. Abaixo está uma lista longe de ser completa de alguns deles.

1. Manter a consistência dos dados no armazenamento ao trabalhar com eles a partir de diversos processos passa a ser responsabilidade do sistema operacional. Na próxima seção, essa mecânica é discutida em detalhes e com fotos.
2. A ausência de caches elimina completamente o LMDB da sobrecarga associada às alocações dinâmicas. Ler dados na prática significa definir um ponteiro para o endereço correto na memória virtual e nada mais. Parece ficção científica, mas no código-fonte do armazenamento todas as chamadas para calloc estão concentradas na função de configuração de armazenamento.
3. A ausência de caches significa também a ausência de bloqueios associados à sincronização do seu acesso. Os leitores, dos quais pode haver um número arbitrário de leitores ao mesmo tempo, não encontram um único mutex no caminho para os dados. Devido a isso, a velocidade de leitura possui escalabilidade linear ideal com base no número de CPUs. No LMDB, apenas as operações de modificação são sincronizadas. Só pode haver um escritor por vez.
4. Um mínimo de lógica de cache e sincronização elimina o tipo extremamente complexo de erros associados ao trabalho em um ambiente multithread. Houve dois estudos interessantes de banco de dados na conferência Usenix OSDI 2014: "Todos os sistemas de arquivos não são criados iguais: sobre a complexidade da criação de aplicativos consistentes com falhas" и "Torturando bancos de dados para diversão e lucro". A partir deles você pode obter informações sobre a confiabilidade sem precedentes do LMDB e a implementação quase perfeita das propriedades de transação ACID, que é superior à do SQLite.
5. O minimalismo do LMDB permite que a representação da máquina de seu código esteja completamente localizada no cache L1 do processador com as características de velocidade resultantes.

Infelizmente, no iOS, com arquivos mapeados na memória, nem tudo é tão tranquilo quanto gostaríamos. Para falar de forma mais consciente sobre as deficiências a eles associadas, é necessário lembrar os princípios gerais de implementação deste mecanismo em sistemas operacionais.

Informações gerais sobre arquivos mapeados em memória

A cada aplicativo executado, o sistema operacional associa uma entidade chamada processo. Cada processo recebe um intervalo contíguo de endereços nos quais coloca tudo o que precisa para funcionar. Nos endereços mais baixos há seções com código e dados e recursos codificados. Em seguida vem um bloco crescente de espaço de endereço dinâmico, bem conhecido por nós como heap. Contém os endereços das entidades que aparecem durante o funcionamento do programa. No topo está a área de memória usada pela pilha de aplicativos. Ou cresce ou contrai, ou seja, seu tamanho também tem natureza dinâmica. Para evitar que a pilha e o heap se empurrem e interfiram entre si, eles estão localizados em extremidades diferentes do espaço de endereço.​ Há um buraco entre as duas seções dinâmicas na parte superior e inferior. O sistema operacional usa endereços nesta seção intermediária para associar uma variedade de entidades ao processo. Em particular, ele pode associar um determinado conjunto contínuo de endereços a um arquivo no disco. Esse arquivo é chamado de mapeado em memória.​

O espaço de endereço alocado para o processo é enorme. Teoricamente, o número de endereços é limitado apenas pelo tamanho do ponteiro, que é determinado pela capacidade de bits do sistema. Se a memória física fosse mapeada 1 para 1, então o primeiro processo consumiria toda a RAM e não haveria conversa sobre multitarefa.​

No entanto, pela nossa experiência, sabemos que os sistemas operacionais modernos podem executar simultaneamente quantos processos desejar. Isso é possível porque eles alocam muita memória apenas para processos no papel, mas na realidade carregam na memória física principal apenas a parte que está em demanda aqui e agora. Portanto, a memória associada a um processo é chamada de virtual.

O sistema operacional organiza a memória virtual e física em páginas de um determinado tamanho. Assim que uma determinada página da memória virtual é solicitada, o sistema operacional a carrega na memória física e as compara em uma tabela especial. Se não houver slots livres, uma das páginas carregadas anteriormente será copiada para o disco e a que estiver em demanda tomará seu lugar. Este procedimento, ao qual voltaremos em breve, é chamado de troca. A figura abaixo ilustra o processo descrito. Nela, a página A com endereço 0 foi carregada e colocada na página da memória principal com endereço 4. Esse fato foi refletido na tabela de correspondência na célula número 0.​

A história é exatamente a mesma com arquivos mapeados na memória. Logicamente, eles estão supostamente localizados contínua e inteiramente no espaço de endereço virtual. No entanto, eles entram na memória física página por página e somente mediante solicitação. A modificação dessas páginas é sincronizada com o arquivo no disco. Dessa forma, você pode realizar E/S de arquivos simplesmente trabalhando com bytes na memória - todas as alterações serão transferidas automaticamente pelo kernel do sistema operacional para o arquivo de origem.​

A imagem abaixo demonstra como o LMDB sincroniza seu estado ao trabalhar com o banco de dados de diferentes processos. Ao mapear a memória virtual de diferentes processos para o mesmo arquivo, obrigamos de fato o sistema operacional a sincronizar transitivamente certos blocos de seus espaços de endereço entre si, onde o LMDB olha.​

Uma nuance importante é que o LMDB, por padrão, modifica o arquivo de dados por meio do mecanismo de chamada do sistema de gravação e exibe o próprio arquivo no modo somente leitura. Esta abordagem tem duas consequências importantes.

A primeira consequência é comum a todos os sistemas operacionais. Sua essência é adicionar proteção contra danos não intencionais ao banco de dados por código incorreto. Como você sabe, as instruções executáveis ​​de um processo são livres para acessar dados de qualquer lugar em seu espaço de endereço. Ao mesmo tempo, como acabamos de lembrar, exibir um arquivo no modo leitura-gravação significa que qualquer instrução também pode modificá-lo. Se ela fizer isso por engano, tentando, por exemplo, sobrescrever um elemento do array em um índice inexistente, ela poderá alterar acidentalmente o arquivo mapeado para esse endereço, o que levará à corrupção do banco de dados. Se o arquivo for exibido no modo somente leitura, uma tentativa de alterar o espaço de endereço correspondente levará ao encerramento emergencial do programa com um sinal SIGSEGVe o arquivo permanecerá intacto.

A segunda consequência já é específica do iOS. Nem o autor nem quaisquer outras fontes o mencionam explicitamente, mas sem ele o LMDB não seria adequado para execução neste sistema operacional móvel. A próxima seção é dedicada à sua consideração.

Especificidades dos arquivos mapeados na memória no iOS

Houve um relatório maravilhoso na WWDC em 2018 "Aprofundamento da memória do iOS". Diz-nos que no iOS todas as páginas localizadas na memória física são de 3 tipos: sujas, compactadas e limpas.

Memória limpa é uma coleção de páginas que podem ser descarregadas da memória física sem problemas. Os dados que eles contêm podem ser recarregados conforme necessário a partir de suas fontes originais. Arquivos mapeados em memória somente leitura se enquadram nesta categoria. O iOS não tem medo de descarregar da memória as páginas mapeadas para um arquivo a qualquer momento, pois elas estão garantidamente sincronizadas com o arquivo no disco.

Todas as páginas modificadas acabam na memória suja, não importa onde estavam originalmente localizadas. Em particular, os arquivos mapeados na memória modificados pela gravação na memória virtual associada a eles serão classificados desta forma. Abrindo LMDB com flag MDB_WRITEMAP, depois de fazer alterações, você pode verificar isso pessoalmente.​

Assim que um aplicativo começa a ocupar muita memória física, o iOS o sujeita à compactação de páginas sujas. A memória total ocupada por páginas sujas e compactadas constitui o chamado consumo de memória do aplicativo. Uma vez atingido um determinado valor limite, o daemon do sistema OOM killer vem após o processo e o encerra à força. Essa é a peculiaridade do iOS em comparação aos sistemas operacionais de desktop. Em contraste, a redução do consumo de memória através da troca de páginas da memória física para o disco não é fornecida no iOS. As razões só podem ser adivinhadas. Talvez o procedimento de movimentação intensiva de páginas para o disco e vice-versa consuma muita energia para dispositivos móveis, ou o iOS economize o recurso de reescrever células em unidades SSD, ou talvez os designers não tenham ficado satisfeitos com o desempenho geral do sistema, onde tudo está constantemente trocado. Seja como for, o fato permanece um fato.

A boa notícia, já mencionada anteriormente, é que o LMDB por padrão não utiliza o mecanismo mmap para atualizar arquivos. Isso significa que os dados exibidos são classificados pelo iOS como memória limpa e não contribuem para o consumo de memória. Você pode verificar isso usando uma ferramenta Xcode chamada VM Tracker. A captura de tela abaixo mostra o estado da memória virtual iOS do aplicativo Cloud durante a operação. No início, 2 instâncias LMDB foram inicializadas nele. O primeiro teve permissão para exibir seu arquivo em 1GiB de memória virtual, o segundo - 512MiB. Apesar de ambos os armazenamentos ocuparem uma certa quantidade de memória residente, nenhum deles contribui com tamanho sujo.

E agora é hora de más notícias. Graças ao mecanismo de troca em sistemas operacionais de desktop de 64 bits, cada processo pode ocupar tanto espaço de endereço virtual quanto o espaço livre no disco rígido permitir para sua troca potencial. Substituir a troca pela compactação no iOS reduz radicalmente o máximo teórico. Agora todos os processos vivos devem caber na memória principal (leia-se RAM), e todos aqueles que não cabem devem ser forçados a encerrar. Isto é afirmado como no mencionado acima reportare em documentação oficial. Como consequência, o iOS limita severamente a quantidade de memória disponível para alocação via mmap. Aqui aqui Você pode observar os limites empíricos da quantidade de memória que pode ser alocada em diferentes dispositivos usando esta chamada de sistema. Nos modelos de smartphones mais modernos, o iOS tornou-se generoso em 2 gigabytes, e nas versões superiores do iPad - em 4. Na prática, é claro, você tem que focar nos modelos de dispositivos com menor suporte, onde tudo é muito triste. Pior ainda, observando o estado da memória do aplicativo no VM Tracker, você descobrirá que o LMDB está longe de ser o único que reivindica memória mapeada em memória. Bons pedaços são consumidos por alocadores de sistema, arquivos de recursos, estruturas de imagens e outros predadores menores.

Com base nos resultados dos experimentos na nuvem, chegamos aos seguintes valores de compromisso para a memória alocada pelo LMDB: 384 megabytes para dispositivos de 32 bits e 768 para dispositivos de 64 bits. Depois que esse volume se esgota, quaisquer operações de modificação começam a terminar com o código MDB_MAP_FULL. Observamos tais erros na nossa monitorização, mas são suficientemente pequenos para que, nesta fase, possam ser negligenciados.

Uma razão não óbvia para o consumo excessivo de armazenamento pode ser transações de longa duração. Para compreender como estes dois fenómenos estão ligados, será útil considerar os restantes dois pilares do LMDB.

3.2. Baleia #2. Árvore B+

Para emular tabelas sobre um armazenamento de valores-chave, as seguintes operações devem estar presentes em sua API:

1. Inserindo um novo elemento.
2. Procure um elemento com uma determinada chave.
3. Removendo um elemento.
4. Itere em intervalos de chaves na ordem em que são classificadas.

A estrutura de dados mais simples que pode implementar facilmente todas as quatro operações é uma árvore de pesquisa binária. Cada um de seus nós representa uma chave que divide todo o subconjunto de chaves filhas em duas subárvores. O esquerdo contém aqueles que são menores que o pai e o direito contém aqueles que são maiores. A obtenção de um conjunto ordenado de chaves é obtida por meio de uma das clássicas travessias em árvore.​

As árvores binárias têm duas falhas fundamentais que as impedem de serem eficazes como estrutura de dados baseada em disco. Em primeiro lugar, o grau do seu equilíbrio é imprevisível. Existe um risco considerável de obter árvores em que as alturas dos diferentes ramos podem diferir muito, o que agrava significativamente a complexidade algorítmica da pesquisa em comparação com o esperado. Em segundo lugar, a abundância de ligações cruzadas entre nós priva as árvores binárias de localidade na memória.Nós próximos (em termos de conexões entre eles) podem estar localizados em páginas completamente diferentes na memória virtual. Como consequência, mesmo uma simples travessia de vários nós vizinhos em uma árvore pode exigir a visita de um número comparável de páginas. Isso é um problema mesmo quando falamos sobre a eficácia das árvores binárias como uma estrutura de dados na memória, uma vez que a rotação constante de páginas no cache do processador não é um prazer barato. Quando se trata de recuperar frequentemente páginas associadas a nós do disco, a situação torna-se completamente deplorável.

As árvores B, sendo uma evolução das árvores binárias, resolvem os problemas identificados no parágrafo anterior. Em primeiro lugar, eles são auto-equilibrados. Em segundo lugar, cada um de seus nós divide o conjunto de chaves filhas não em 2, mas em M subconjuntos ordenados, e o número M pode ser bastante grande, da ordem de várias centenas ou até milhares.

Deste modo:

1. Cada nó contém um grande número de chaves já ordenadas e as árvores são muito curtas.
2. A árvore adquire a propriedade de localidade de localização na memória, uma vez que chaves de valor próximo estão naturalmente localizadas próximas umas das outras no mesmo nó ou em nós vizinhos.
3. O número de nós de trânsito ao descer uma árvore durante uma operação de busca é reduzido.
4. O número de nós alvo lidos durante consultas de intervalo é reduzido, pois cada um deles já contém um grande número de chaves ordenadas.

O LMDB usa uma variação da árvore B chamada árvore B+ para armazenar dados. O diagrama acima mostra os três tipos de nós que existem nele:

1. No topo está a raiz. Nada mais materializa do que o conceito de banco de dados dentro de um warehouse. Dentro de uma instância do LMDB, você pode criar vários bancos de dados que compartilham um espaço de endereço virtual mapeado. Cada um deles começa com sua própria raiz.
2. No nível mais baixo estão as folhas. Eles e somente eles contêm os pares chave-valor armazenados no banco de dados. A propósito, esta é a peculiaridade das árvores B+. Se uma árvore B regular armazena partes de valor em nós de todos os níveis, então a variação B+ ocorre apenas no nível mais baixo. Tendo corrigido esse fato, chamaremos ainda mais o subtipo da árvore usada no LMDB simplesmente de árvore B.
3. Entre a raiz e as folhas existem 0 ou mais níveis técnicos com nós de navegação (ramificação). A tarefa deles é dividir o conjunto classificado de chaves entre as folhas.

Fisicamente, os nós são blocos de memória com comprimento predeterminado. Seu tamanho é um múltiplo do tamanho das páginas de memória do sistema operacional, que discutimos acima. A estrutura do nó é mostrada abaixo. O cabeçalho contém metainformações, a mais óbvia das quais, por exemplo, é a soma de verificação. A seguir vêm informações sobre os deslocamentos nos quais as células com dados estão localizadas. Os dados podem ser chaves, se estivermos falando de nós de navegação, ou pares inteiros de valores-chave, no caso de folhas.​ Você pode ler mais sobre a estrutura das páginas no trabalho "Avaliação de armazenamentos de valores-chave de alto desempenho".

Tendo lidado com o conteúdo interno dos nós da página, representaremos ainda a árvore B do LMDB de maneira simplificada no seguinte formato.

As páginas com nós estão localizadas sequencialmente no disco. As páginas com numeração mais alta estão localizadas no final do arquivo. A chamada metapágina contém informações sobre os deslocamentos pelos quais as raízes de todas as árvores podem ser encontradas. Ao abrir um arquivo, o LMDB verifica o arquivo página por página, do início ao fim, em busca de uma meta-página válida e, através dela, encontra bancos de dados existentes.​

Agora, tendo uma ideia da estrutura lógica e física da organização dos dados, podemos passar a considerar o terceiro pilar do LMDB. É com sua ajuda que todas as modificações de armazenamento ocorrem de forma transacional e isoladas umas das outras, conferindo ao banco de dados como um todo a propriedade de multiversão.

3.3. Baleia #3. Cópia na gravação

Algumas operações da árvore B envolvem fazer uma série de alterações em seus nós. Um exemplo é adicionar uma nova chave a um nó que já atingiu a sua capacidade máxima. Neste caso, é necessário, em primeiro lugar, dividir o nó em dois e, em segundo lugar, adicionar um link para o novo nó filho emergente em seu pai. Este procedimento é potencialmente muito perigoso. Se por algum motivo (queda, queda de energia, etc.) ocorrer apenas parte das alterações da série, a árvore permanecerá em um estado inconsistente.

Uma solução tradicional para tornar um banco de dados tolerante a falhas é adicionar uma estrutura de dados adicional em disco próxima à árvore B - um log de transações, também conhecido como log write-ahead (WAL). É um arquivo ao final do qual a operação pretendida é escrita estritamente antes de modificar a própria árvore B. Assim, caso seja detectada corrupção de dados durante o autodiagnóstico, o banco de dados consulta o log para se colocar em ordem.

O LMDB escolheu um método diferente como mecanismo de tolerância a falhas, chamado copy-on-write. Sua essência é que, em vez de atualizar os dados de uma página existente, primeiro ele a copia inteiramente e faz todas as modificações na cópia.​

A seguir, para que os dados atualizados estejam disponíveis, é necessário alterar a ligação ao nó que se tornou atual em seu nó pai. Como também precisa ser modificado para isso, também é copiado previamente. O processo continua recursivamente até a raiz. A última coisa a mudar são os dados na metapágina.​​

Se de repente o processo travar durante o procedimento de atualização, uma nova meta-página não será criada ou não será gravada completamente no disco e sua soma de verificação estará incorreta. Em qualquer um desses dois casos, as novas páginas ficarão inacessíveis, mas as antigas não serão afetadas. Isso elimina a necessidade do LMDB gravar antecipadamente o log para manter a consistência dos dados. De facto, a estrutura de armazenamento de dados no disco descrita acima assume simultaneamente a sua função. A ausência de um log de transações explícito é um dos recursos do LMDB que proporciona alta velocidade de leitura de dados.​

O design resultante, chamado de árvore B somente para acréscimos, fornece naturalmente isolamento de transação e multiversão. No LMDB, cada transação aberta está associada à raiz da árvore atualmente relevante. Até que a transação seja concluída, as páginas da árvore associadas a ela nunca serão alteradas ou reutilizadas para novas versões dos dados. Assim, você poderá trabalhar pelo tempo que quiser exatamente com o conjunto de dados que era relevante no momento. a transação foi aberta, mesmo que o armazenamento continue sendo atualizado ativamente neste momento. Esta é a essência da multiversão, tornando o LMDB uma fonte de dados ideal para nossos amados UICollectionView. Depois de abrir uma transação, não há necessidade de aumentar o consumo de memória do aplicativo, bombeando apressadamente os dados atuais para alguma estrutura na memória, por medo de ficar sem nada. Esse recurso distingue o LMDB do mesmo SQLite, que não pode se orgulhar de tal isolamento total. Tendo aberto duas transações nesta última e apagado um determinado registro dentro de uma delas, não será mais possível obter o mesmo registro dentro do segundo restante.

O outro lado da moeda é o consumo potencialmente significativamente maior de memória virtual. O slide mostra como será a estrutura do banco de dados se for modificada simultaneamente com 3 transações de leitura abertas observando diferentes versões do banco de dados. Como o LMDB não pode reutilizar nós acessíveis a partir de raízes associadas às transações atuais, o armazenamento não tem escolha a não ser alocar outra quarta raiz na memória e mais uma vez clonar as páginas modificadas nela.​

Aqui seria útil relembrar a seção sobre arquivos mapeados na memória. Parece que o consumo adicional de memória virtual não deve nos preocupar muito, pois não contribui para o consumo de memória da aplicação. Porém, ao mesmo tempo, notou-se que o iOS é muito mesquinho em alocá-lo, e não podemos, como em um servidor ou desktop, fornecer uma região LMDB de 1 terabyte e nem pensar nesse recurso. Se possível, você deve tentar tornar o tempo de vida das transações o mais curto possível.

4. Projetando um esquema de dados sobre a API de valor-chave

Vamos começar nossa análise de API observando as abstrações básicas fornecidas pelo LMDB: ambiente e bancos de dados, chaves e valores, transações e cursores.

Uma observação sobre listagens de códigos

Todas as funções na API pública do LMDB retornam o resultado de seu trabalho na forma de um código de erro, mas em todas as listagens subsequentes sua verificação é omitida por uma questão de brevidade.​ Na prática, usamos até o nosso próprio para interagir com o repositório garfo Invólucros C++ lmdbxx, em que os erros são materializados como exceções C++.

Como a maneira mais rápida de conectar o LMDB a um projeto para iOS ou macOS, sugiro meu CocoaPod POSLMDB.

4.1. Abstrações básicas

Ambiente

Estrutura MDB_env é o repositório do estado interno do LMDB. Família de funções prefixadas mdb_env permite que você configure algumas de suas propriedades. No caso mais simples, a inicialização do mecanismo é assim.

mdb_env_create(env);​
mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

No aplicativo Mail.ru Cloud, alteramos os valores padrão de apenas dois parâmetros.

O primeiro é o tamanho do espaço de endereço virtual para o qual o arquivo de armazenamento está mapeado. Infelizmente, mesmo no mesmo dispositivo, o valor específico pode variar significativamente de execução para execução. Para levar em conta esse recurso do iOS, o volume máximo de armazenamento é selecionado dinamicamente. A partir de um determinado valor, ele é dividido sequencialmente pela metade até que a função mdb_env_open não retornará um resultado diferente de ENOMEM. Em teoria, também existe o caminho oposto - primeiro aloque um mínimo de memória para o mecanismo e depois, quando forem recebidos erros, MDB_MAP_FULL, aumente-o. No entanto, é muito mais espinhoso. A razão é que o procedimento para realocar memória (remapear) usando a função mdb_env_set_map_size invalida todas as entidades (cursores, transações, chaves e valores) recebidas anteriormente do mecanismo. Levar essa reviravolta em consideração no código levará a uma complicação significativa. Se, no entanto, a memória virtual é muito importante para você, então este pode ser um motivo para dar uma olhada mais de perto na bifurcação que já avançou muito. MDBX, onde entre os recursos anunciados está o “ajuste automático do tamanho do banco de dados em tempo real”.

O segundo parâmetro, cujo valor padrão não nos convém, regula a mecânica de garantia da segurança do thread. Infelizmente, pelo menos o iOS 10 tem problemas com suporte para armazenamento local de threads. Por este motivo, no exemplo acima, o repositório é aberto com a flag MDB_NOTLS. Além disso, também foi necessário garfo Invólucro C++ lmdbxxpara cortar variáveis ​​com este atributo e nele.

Bases de dados

O banco de dados é uma instância separada da árvore B, que discutimos acima. Sua abertura ocorre dentro de uma transação, o que pode parecer um pouco estranho a princípio.

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

Na verdade, uma transação no LMDB é uma entidade de armazenamento, não uma entidade específica de banco de dados. Este conceito permite realizar operações atômicas em entidades localizadas em diferentes bancos de dados. Em teoria, isso abre a possibilidade de modelar tabelas na forma de diferentes bancos de dados, mas certa vez tomei um caminho diferente, descrito em detalhes a seguir.

Chaves e valores

Estrutura MDB_val modela o conceito de chave e valor. O repositório não tem ideia sobre sua semântica. Para ela, outra coisa é apenas uma matriz de bytes de um determinado tamanho. O tamanho máximo da chave é 512 bytes.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Usando um comparador, a loja classifica as chaves em ordem crescente. Se você não substituí-lo pelo seu próprio, será usado o padrão, que os classifica byte por byte em ordem lexicográfica.​

Transações

A estrutura da transação é descrita em detalhes em capítulo anterior, então aqui repetirei brevemente suas propriedades principais:

1. Suporta todas as propriedades básicas ACID: atomicidade, consistência, isolamento e confiabilidade. Não posso deixar de notar que há um bug em termos de durabilidade no macOS e iOS que foi corrigido no MDBX. Você pode ler mais em seus README.
2. A abordagem para multithreading é descrita pelo esquema “escritor único/leitores múltiplos”. Os escritores bloqueiam uns aos outros, mas não bloqueiam os leitores. Os leitores não bloqueiam os escritores ou uns aos outros.
3. Suporte para transações aninhadas.
4. Suporte multiversão.

A multiversão no LMDB é tão boa que quero demonstrá-la em ação. Pelo código abaixo você pode perceber que cada transação funciona exatamente com a versão do banco de dados que estava em vigor no momento em que foi aberta, ficando completamente isolada de todas as alterações subsequentes. Inicializar o armazenamento e adicionar um registro de teste a ele não representa nada de interessante, então esses rituais ficam sob spoiler.

Adicionando uma entrada de teste

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Recomendo que você tente o mesmo truque com SQLite e veja o que acontece.

O Multiversion traz vantagens muito legais para a vida de um desenvolvedor iOS. Usando essa propriedade, você pode ajustar de maneira fácil e natural a taxa de atualização da fonte de dados para formulários de tela, com base em considerações de experiência do usuário. Por exemplo, vamos usar um recurso do aplicativo Mail.ru Cloud, como o carregamento automático de conteúdo da galeria de mídia do sistema. Com uma boa conexão, o cliente consegue adicionar diversas fotos por segundo ao servidor. Se você atualizar após cada download UICollectionView com conteúdo de mídia na nuvem do usuário, você pode esquecer os 60 fps e a rolagem suave durante esse processo. Para evitar atualizações frequentes da tela, você precisa limitar de alguma forma a taxa na qual os dados mudam no subjacente. UICollectionViewDataSource.

Se o banco de dados não suportar multiversão e permitir que você trabalhe apenas com o estado atual atual, para criar um instantâneo dos dados com tempo estável, você precisará copiá-lo para alguma estrutura de dados na memória ou para uma tabela temporária. Qualquer uma dessas abordagens é muito cara. No caso do armazenamento em memória, obtemos custos tanto em memória, causados ​​pelo armazenamento de objetos construídos, quanto em tempo, associados a transformações ORM redundantes. Quanto à mesa temporária, é um prazer ainda mais caro, fazendo sentido apenas em casos não triviais.

A solução multiversão do LMDB resolve o problema de manter uma fonte de dados estável de uma forma muito elegante. Basta abrir uma transação e pronto - até concluí-la, o conjunto de dados será corrigido. A lógica para sua velocidade de atualização está agora inteiramente nas mãos da camada de apresentação, sem sobrecarga de recursos significativos.

Cursores

Os cursores fornecem um mecanismo para iterar ordenadamente pares de valores-chave por meio da travessia da árvore B. Sem eles, seria impossível modelar efetivamente as tabelas no banco de dados, ao qual nos voltaremos agora.

4.2. Modelagem de Tabela

A propriedade de ordenação de chaves permite construir uma abstração de alto nível, como uma tabela, sobre abstrações básicas. Vamos considerar esse processo usando o exemplo da tabela principal de um cliente em nuvem, que armazena em cache informações sobre todos os arquivos e pastas do usuário.

Esquema de tabela

Um dos cenários comuns para os quais uma estrutura de tabela com uma árvore de pastas deve ser adaptada é a seleção de todos os elementos localizados dentro de um determinado diretório.Um bom modelo de organização de dados para consultas eficientes deste tipo é Lista de Adjacência. Para implementá-lo no armazenamento de valores-chave, é necessário classificar as chaves dos arquivos e pastas de forma que sejam agrupadas com base em sua participação no diretório pai. Além disso, para exibir o conteúdo do diretório na forma familiar ao usuário do Windows (primeiro as pastas, depois os arquivos, ambos classificados em ordem alfabética), é necessário incluir os campos adicionais correspondentes na chave.

A imagem abaixo mostra como, com base na tarefa em questão, seria uma representação de chaves na forma de uma matriz de bytes. Os bytes com o identificador do diretório pai (vermelho) são colocados primeiro, depois com o tipo (verde) e na cauda com o nome (azul).Sendo classificados pelo comparador LMDB padrão em ordem lexicográfica, eles são ordenados no maneira exigida. Percorrer sequencialmente as chaves com o mesmo prefixo vermelho nos dá seus valores associados na ordem em que devem ser exibidos na interface do usuário (à direita), sem exigir nenhum pós-processamento adicional.

Serializando Chaves e Valores

Muitos métodos para serializar objetos foram inventados no mundo. Como não tínhamos outro requisito além da velocidade, escolhemos o mais rápido possível para nós mesmos - um dump da memória ocupada por uma instância da estrutura da linguagem C. Assim, a chave de um elemento de diretório pode ser modelada com a seguinte estrutura NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Salvar NodeKey no armazenamento necessário no objeto MDB_val posicione o ponteiro de dados no endereço do início da estrutura e calcule seu tamanho com a função sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

No primeiro capítulo sobre critérios de seleção de banco de dados, mencionei a minimização de alocações dinâmicas nas operações CRUD como um importante fator de seleção. Código de função serialize mostra como no caso do LMDB eles podem ser completamente evitados na inserção de novos registros no banco de dados. A matriz de bytes de entrada do servidor é primeiro transformada em estruturas de pilha e, em seguida, são despejadas trivialmente no armazenamento. Considerando que também não há alocações dinâmicas dentro do LMDB, você pode obter uma situação fantástica para os padrões do iOS - use apenas memória de pilha para trabalhar com dados ao longo de todo o caminho da rede ao disco!

Ordenando chaves com um comparador binário

O relacionamento de ordem de chave é especificado por uma função especial chamada comparador. Como o mecanismo não sabe nada sobre a semântica dos bytes que eles contêm, o comparador padrão não tem escolha senão organizar as chaves em ordem lexicográfica, recorrendo a uma comparação byte por byte. Usá-lo para organizar estruturas é semelhante a fazer a barba com um machado de corte. Porém, em casos simples considero esse método aceitável. A alternativa é descrita abaixo, mas aqui observarei alguns ancinhos espalhados ao longo deste caminho.

A primeira coisa a lembrar é a representação na memória de tipos de dados primitivos. Assim, em todos os dispositivos Apple, as variáveis ​​inteiras são armazenadas no formato Pequeno endian. Isso significa que o byte menos significativo estará à esquerda e não será possível classificar inteiros usando uma comparação byte a byte. Por exemplo, tentar fazer isso com um conjunto de números de 0 a 511 produzirá o seguinte resultado.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

Para resolver este problema, os inteiros devem ser armazenados na chave em um formato adequado para o comparador byte-byte. As funções da família irão ajudá-lo a realizar a transformação necessária hton* (em particular htons para números de byte duplo do exemplo).

O formato para representar strings em programação é, como você sabe, um todo história. Se a semântica das strings, bem como a codificação usada para representá-las na memória, sugerem que pode haver mais de um byte por caractere, então é melhor abandonar imediatamente a ideia de usar um comparador padrão.

A segunda coisa a ter em mente é princípios de alinhamento compilador de campo de estrutura. Por causa deles, bytes com valores inúteis podem ser formados na memória entre os campos, o que, obviamente, quebra a classificação byte-byte. Para eliminar o lixo, você precisa declarar os campos em uma ordem estritamente definida, mantendo as regras de alinhamento em mente, ou usar o atributo na declaração da estrutura packed.

Solicitando chaves com um comparador externo

A lógica de comparação chave pode ser muito complexa para um comparador binário. Um dos muitos motivos é a presença de áreas técnicas nas estruturas. Ilustrarei sua ocorrência usando o exemplo de uma chave para um elemento de diretório que já nos é familiar.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Apesar de sua simplicidade, na grande maioria dos casos consome muita memória. O buffer para o nome ocupa 256 bytes, embora em média os nomes de arquivos e pastas raramente excedam 20 a 30 caracteres.

​Uma das técnicas padrão para otimizar o tamanho de um registro é “cortá-lo” para o tamanho real. Sua essência é que o conteúdo de todos os campos de comprimento variável seja armazenado em um buffer no final da estrutura e seus comprimentos sejam armazenados em variáveis ​​separadas.​ De acordo com esta abordagem, a chave NodeKey é transformado da seguinte forma.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

Além disso, ao serializar, o tamanho dos dados não é especificado sizeof toda a estrutura, e o tamanho de todos os campos é um comprimento fixo mais o tamanho da parte realmente usada do buffer.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

Como resultado da refatoração, obtivemos economias significativas no espaço ocupado pelas chaves. Porém, devido ao campo técnico nameLength, o comparador binário padrão não é mais adequado para comparação de chaves. Se não o substituirmos pelo nosso, o comprimento do nome será um fator de maior prioridade na classificação do que o próprio nome.

O LMDB permite que cada banco de dados tenha sua própria função de comparação de chaves. Isso é feito usando a função mdb_set_compare estritamente antes de abrir. Por razões óbvias, não pode ser alterado durante a vida do banco de dados. O comparador recebe como entrada duas chaves em formato binário, e na saída retorna o resultado da comparação: menor que (-1), maior que (1) ou igual a (0). Pseudocódigo para NodeKey parece com isso.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

Contanto que todas as chaves no banco de dados sejam do mesmo tipo, é legal converter incondicionalmente sua representação de bytes para o tipo da estrutura de chave do aplicativo. Há uma ressalva aqui, mas será discutida abaixo na subseção “Leitura de Registros”.

Serializando Valores

O LMDB trabalha de forma extremamente intensa com as chaves dos registros armazenados. A comparação entre eles ocorre no âmbito de qualquer operação aplicada, e o desempenho de toda a solução depende da velocidade do comparador. Em um mundo ideal, o comparador binário padrão deveria ser suficiente para comparar chaves, mas se você tivesse que usar o seu próprio, o procedimento para desserializar chaves nele deveria ser o mais rápido possível.

O banco de dados não está particularmente interessado na parte do valor do registro (valor). Sua conversão de representação de bytes para objeto ocorre somente quando já é exigido pelo código da aplicação, por exemplo, para exibi-lo na tela. Como isso acontece relativamente raramente, os requisitos de velocidade para este procedimento não são tão críticos, e em sua implementação temos muito mais liberdade para focar na conveniência. Por exemplo, para serializar metadados sobre arquivos que ainda não foram baixados, usamos NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

No entanto, há momentos em que o desempenho ainda é importante. Por exemplo, ao salvar metainformações sobre a estrutura de arquivos de uma nuvem de usuário, usamos o mesmo despejo de memória de objetos. O destaque da tarefa de gerar uma representação serializada deles é o fato dos elementos de um diretório serem modelados por uma hierarquia de classes.​

Para implementá-lo na linguagem C, campos específicos dos herdeiros são colocados em estruturas separadas, e sua conexão com a base é especificada através de um campo do tipo união. O conteúdo real da união é especificado através do tipo de atributo técnico.

typedef struct NodeValue {​
    EntityId localId;​
    EntityType type;​
    union {​
        FileInfo file;​
        DirectoryInfo directory;​
    } info;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeValue;​

Adicionando e atualizando registros

A chave e o valor serializados podem ser adicionados ao armazenamento. Para fazer isso, use a função mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

Na fase de configuração, o armazenamento pode ser permitido ou proibido de armazenar vários registros com a mesma chave. Se a duplicação de chaves for proibida, ao inserir um registro, você pode determinar se a atualização de um registro existente é permitida ou não. Se o desgaste só puder ocorrer como resultado de um erro no código, você poderá se proteger dele especificando o sinalizador NOOVERWRITE.

Lendo entradas

Para ler registros no LMDB, use a função mdb_get. Se o par chave-valor for representado por estruturas descartadas anteriormente, este procedimento será semelhante a este.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

A listagem apresentada mostra como a serialização por meio de dump de estrutura permite que você se livre de alocações dinâmicas não apenas durante a gravação, mas também durante a leitura de dados. Derivado da função mdb_get o ponteiro olha exatamente para o endereço da memória virtual onde o banco de dados armazena a representação de bytes do objeto. Na verdade, obtemos uma espécie de ORM que oferece altíssima velocidade de leitura de dados quase gratuitamente. Apesar de toda a beleza da abordagem, é preciso lembrar de diversas características a ela associadas.

1. Para uma transação somente leitura, é garantido que o ponteiro para a estrutura de valor permanecerá válido apenas até que a transação seja fechada. Conforme observado anteriormente, as páginas da árvore B nas quais um objeto está localizado, graças ao princípio copy-on-write, permanecem inalteradas desde que sejam referenciadas por pelo menos uma transação. Ao mesmo tempo, assim que a última transação associada a elas for concluída, as páginas podem ser reutilizadas para novos dados. Se for necessário que os objetos sobrevivam à transação que os gerou, eles ainda terão que ser copiados.
2. ​​Para uma transação de leitura e gravação, o ponteiro para a estrutura de valor resultante será válido somente até o primeiro procedimento de modificação (escrita ou exclusão de dados).
3. Embora a estrutura NodeValue não completo, mas aparado (veja a subseção “Ordenando chaves usando um comparador externo”), você pode acessar com segurança seus campos através do ponteiro. O principal é não desreferenciar!
4. Sob nenhuma circunstância a estrutura deve ser modificada através do ponteiro recebido. Todas as alterações devem ser feitas somente através do método mdb_put. Porém, por mais que você queira fazer isso, não será possível, pois a área da memória onde esta estrutura está localizada está mapeada em modo somente leitura.
5. Remapeie um arquivo para o espaço de endereço do processo com a finalidade de, por exemplo, aumentar o tamanho máximo de armazenamento usando a função mdb_env_set_map_size invalida completamente todas as transações e entidades relacionadas em geral e aponta para determinados objetos em particular.

Por fim, outra característica é tão insidiosa que revelar sua essência não cabe em apenas mais um parágrafo. No capítulo sobre a árvore B, forneci um diagrama de como suas páginas estão organizadas na memória. Conclui-se que o endereço inicial do buffer com dados serializados pode ser absolutamente arbitrário. Por causa disso, o ponteiro para eles recebido na estrutura MDB_val e reduzido a um ponteiro para uma estrutura, acaba sendo desalinhado no caso geral. Ao mesmo tempo, as arquiteturas de alguns chips (no caso do iOS é armv7) exigem que o endereço de qualquer dado seja um múltiplo do tamanho da palavra da máquina ou, em outras palavras, do tamanho do bit do sistema ( para armv7 é 32 bits). Em outras palavras, uma operação como *(int *foo)0x800002 neles equivale a fuga e leva à execução com veredicto EXC_ARM_DA_ALIGN. Existem duas maneiras de evitar um destino tão triste.

A primeira se resume à cópia preliminar dos dados em uma estrutura obviamente alinhada. Por exemplo, em um comparador personalizado, isso será refletido da seguinte forma.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

Uma maneira alternativa é notificar o compilador com antecedência de que as estruturas de valores-chave podem não estar alinhadas por atributos aligned(1). No ARM você pode ter o mesmo efeito para atingir e usando o atributo embalado. Considerando que também ajuda a optimizar o espaço ocupado pela estrutura, este método parece-me preferível, embora приводит a um aumento no custo das operações de acesso a dados.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Consultas de intervalo

Para iterar sobre um grupo de registros, o LMDB fornece uma abstração de cursor. Vejamos como trabalhar com isso usando o exemplo de uma tabela com metadados de nuvem do usuário já familiares para nós.

Como parte da exibição de uma lista de arquivos em um diretório, é necessário encontrar todas as chaves às quais seus arquivos e pastas filhos estão associados. Nas subseções anteriores, classificamos as chaves NodeKey de modo que sejam ordenados principalmente pelo ID do diretório pai. Assim, tecnicamente, a tarefa de recuperar o conteúdo de uma pasta se resume a colocar o cursor no limite superior do grupo de chaves com um determinado prefixo e depois iterar até o limite inferior.

O limite superior pode ser encontrado diretamente por pesquisa sequencial. Para fazer isso, o cursor é colocado no início de toda a lista de chaves do banco de dados e incrementado ainda mais até que uma chave com o identificador do diretório pai apareça abaixo dele. Esta abordagem tem 2 desvantagens óbvias:

1. Complexidade de pesquisa linear, embora, como se sabe, em árvores em geral e em uma árvore B em particular possa ser realizada em tempo logarítmico.​
2. Em vão, todas as páginas anteriores àquela procurada são transferidas do arquivo para a memória principal, o que é extremamente caro.

Felizmente, a API LMDB fornece uma maneira eficaz de posicionar inicialmente o cursor. Para fazer isso, você precisa gerar uma chave cujo valor seja obviamente menor ou igual à chave localizada no limite superior do intervalo. Por exemplo, em relação à lista da figura acima, podemos fazer uma chave na qual o campo parentId será igual a 2 e todo o resto será preenchido com zeros. Essa chave parcialmente preenchida é fornecida à entrada da função mdb_cursor_get indicando a operação MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Se o limite superior de um grupo de chaves for encontrado, iteramos sobre ele até nos encontrarmos ou a chave encontrar outra parentId, ou as chaves não acabarão.​

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

O que é bom é que como parte da iteração usando mdb_cursor_get, obtemos não apenas a chave, mas também o valor. Se, para cumprir as condições de amostragem, for necessário verificar, entre outras coisas, os campos da parte de valor do registro, então eles são bastante acessíveis sem gestos adicionais.

4.3. Modelando relacionamentos entre tabelas

Até agora, conseguimos considerar todos os aspectos do projeto e do trabalho com um banco de dados de tabela única. Podemos dizer que uma tabela é um conjunto de registros classificados que consiste no mesmo tipo de pares chave-valor. Se você exibir uma chave como um retângulo e o valor associado como um paralelepípedo, obterá um diagrama visual do banco de dados.

No entanto, na vida real raramente é possível sobreviver com tão pouco derramamento de sangue. Freqüentemente, em um banco de dados é necessário, em primeiro lugar, ter várias tabelas e, em segundo lugar, fazer seleções nelas em uma ordem diferente da chave primária. Esta última seção é dedicada às questões de sua criação e interconexão.

Tabelas de índice

O aplicativo em nuvem possui uma seção "Galeria". Ele exibe conteúdo de mídia de toda a nuvem, classificado por data. Para implementar tal seleção de maneira ideal, próximo à tabela principal você precisa criar outra com um novo tipo de chaves. Eles conterão um campo com a data em que o arquivo foi criado, que atuará como critério de classificação principal. Como as novas chaves fazem referência aos mesmos dados que as chaves da tabela principal, elas são chamadas de chaves de índice. Na imagem abaixo eles estão destacados em laranja.

Para separar as chaves de diferentes tabelas dentro de um mesmo banco de dados, um campo técnico adicional tableId foi adicionado a todas elas. Ao torná-la a mais alta prioridade para classificação, conseguiremos o agrupamento de chaves primeiro por tabelas e dentro de tabelas - de acordo com nossas próprias regras.​

A chave do índice faz referência aos mesmos dados que a chave primária. Uma implementação direta desta propriedade através da associação a ela de uma cópia da parte do valor da chave primária não é ideal sob vários pontos de vista:

1. Em termos de espaço ocupado, os metadados podem ser bastante ricos.
2. Do ponto de vista de desempenho, pois ao atualizar os metadados de um nó, será necessário reescrevê-lo usando duas chaves.
3. Do ponto de vista do suporte de código, se esquecermos de atualizar os dados de uma das chaves, teremos um erro indescritível de inconsistência de dados no armazenamento.

A seguir, consideraremos como eliminar essas deficiências.

Organizando relacionamentos entre tabelas

O padrão é adequado para vincular a tabela de índice à tabela principal "chave como valor". Como o próprio nome sugere, a parte do valor do registro do índice é uma cópia do valor da chave primária. Esta abordagem elimina todas as desvantagens mencionadas acima associadas ao armazenamento de uma cópia da parte do valor do registro primário. O único custo é que para obter um valor por chave de índice, você precisa fazer 2 consultas ao banco de dados em vez de uma. Esquematicamente, o esquema de banco de dados resultante é assim.

Outro padrão para organizar relacionamentos entre tabelas é "chave redundante". Sua essência é adicionar atributos adicionais à chave, que são necessários não para a classificação, mas para recriar a chave associada. No aplicativo Mail.ru Cloud existem exemplos reais de seu uso, no entanto, para evitar um mergulho profundo No contexto de frameworks iOS específicos, darei um exemplo fictício, mas mais claro.​

Os clientes móveis em nuvem têm uma página que exibe todos os arquivos e pastas que o usuário compartilhou com outras pessoas. Dado que existem relativamente poucos ficheiros deste tipo e que existem muitos tipos diferentes de informações específicas sobre a publicidade a eles associada (a quem é concedido acesso, com que direitos, etc.), não será racional sobrecarregar a parte do valor do grave na tabela principal com ele. No entanto, se quiser exibir esses arquivos offline, você ainda precisará armazená-los em algum lugar. Uma solução natural é criar uma tabela separada para isso. No diagrama abaixo, sua chave é prefixada com “P”, e o espaço reservado “propname” pode ser substituído pelo valor mais específico “informações públicas”.​

Todos os metadados exclusivos, para fins de armazenamento dos quais a nova tabela foi criada, são colocados na parte de valor do registro. Ao mesmo tempo, você não deseja duplicar os dados sobre arquivos e pastas que já estão armazenados na tabela principal. Em vez disso, dados redundantes são adicionados à chave “P” na forma dos campos “ID do nó” e “carimbo de data/hora”. Graças a eles, você pode construir uma chave de índice, da qual você pode obter uma chave primária, da qual, finalmente, você pode obter os metadados do nó.

Conclusão

Avaliamos positivamente os resultados da implementação do LMDB. Depois disso, o número de congelamentos de aplicativos diminuiu 30%.

Os resultados do trabalho realizado repercutiram além da equipe do iOS. Atualmente, uma das principais seções de “Arquivos” do aplicativo Android também passou a usar LMDB, e outras partes estão a caminho. A linguagem C, na qual o armazenamento de valores-chave é implementado, foi uma boa ajuda para criar inicialmente uma estrutura de aplicativo em torno de plataforma cruzada em C++. Um gerador de código foi usado para conectar perfeitamente a biblioteca C++ resultante com código de plataforma em Objective-C e Kotlin djinni do Dropbox, mas isso é uma história completamente diferente.

Fonte: habr.com