Neste artigo, examinaremos detalhadamente como a árvore B + é feita em um banco de dados distribuído do Apache Ignite .

Já existem alguns artigos sobre árvores H em árvores B ( um , dois ), mas são mais prováveis ​​teóricos e, mesmo que contenham uma implementação, não estão prontos para produção . A partir disso, é interessante observar a implementação usada na vida.

Antes de ler o artigo, aconselho a assistir a uma palestra de Maxim Babenko , se você ainda não sabe o que é a árvore B em teoria. Mas não preciso conhecer profundamente o Java ou o projeto Apache Ignite - escreverei os detalhes explicitamente ou os ocultarei em spoilers.

Ao ler fontes Ignite, aconselho que você pule os argumentos dos métodos em sua mente, cujo significado não é muito claro e leia os nomes das funções - é muito mais fácil ler o corpo da função se você souber com antecedência o que ela faz.

Observe que eu não sou o desenvolvedor principal do Apache Ignite e poderia ter entendido algo errado do código. Então, eu coloquei a frase “até onde eu entendi”, que deveria ser acrescentada mentalmente antes de cada frase afirmativa.

Por que a árvore B + no Apache Ignite

O Apache Ignite é um banco de dados na memória, mas desde a versão 2.1, ele possui um armazenamento de dados persistente - uma função para salvar dados em disco (não tem nada a ver com estrutura de dados persistente ) . Portanto, fica claro por que uma estrutura é necessária para a memória externa, resta entender por que eles não escolheram outra.

Para começar, a árvore B + é uma otimização da árvore B, na qual os valores são armazenados apenas nas folhas. Nesta otimização, mais chaves cabem em um nó, o que aumenta o grau de ramificação. Portanto, não há muitas razões para usar a árvore B clássica.

B * e B + * - são mais densos no disco, mas têm desempenho pior, porque Como armazenamos dados da RAM, o desempenho é mais importante para nós.

A julgar pelos benchmarks, uma árvore LSM é mais rápida na escrita, mas mais lenta na leitura. Além disso, a perda na leitura é maior que o ganho na escrita, portanto, para um caso geral hipotético, eu também aceitaria a árvore B +.

Existem também árvores fractais estranhas, no entanto, aparentemente, elas são patenteadas e implementadas apenas no TokuDB .

Pessoalmente, estou mais interessado em saber por que era impossível usar um back-end de disco pronto, como o LevelDB ? Uma resposta parcial é que o PDS oferece suporte a armazenamento de terceiros.

Implementação de grandes células

Inicialmente, o GridGain desenvolveu o Apache Ignite, mas antes de partir para o código-fonte aberto tinha o nome da empresa; portanto, alguns nomes de componentes começam com Grid e outros com Ignite . Portanto GridCursor , mas IgniteTree . Não há outra lógica aqui.

O código do Apache Ignite é escrito nos padrões de práticas recomendadas de Java e cada classe herda uma interface, se não uma. Na interface do IgniteTree e comece a dança. Eu dou o código sem javadoc, para abreviar.

 public interface IgniteTree<L, T> { public T put(T val) throws IgniteCheckedException; public void invoke(L key, Object x, InvokeClosure<T> c) throws IgniteCheckedException; public T findOne(L key) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException; public T findFirst() throws IgniteCheckedException; public T findLast() throws IgniteCheckedException; public T remove(L key) throws IgniteCheckedException; public long size() throws IgniteCheckedException; interface InvokeClosure<T> { void call(@Nullable T row) throws IgniteCheckedException; T newRow(); OperationType operationType(); } enum OperationType { NOOP, REMOVE, PUT } } 

A interface do IgniteTree descreve um conjunto padrão de operações. Observe que, para realizar uma pesquisa por faixa, é necessário tricotar folhas em uma lista. O bônus suporta uma operação de registro arbitrária - invoke .

A operação put usa apenas um argumento do tipo T sem uma chave. Você não encontrará uma explicação para isso no IgniteTree , no entanto, a resposta está oculta no cabeçalho do BPlusTree .

 public abstract class BPlusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T> 

Como você pode ver, o valor herda a chave, portanto, na operação de venda, a chave é calculada a partir do valor. Isso não limita a funcionalidade da árvore. Minha suposição é que é mais compacto armazenar conjuntos.

Geralmente eles são definidos fora do mapa, anexando uma constante de lixo ao valor. No entanto, na árvore B +, apenas as chaves são armazenadas nos nós; se o valor também armazena a chave, nas folhas é suficiente armazenar apenas os valores . E se a árvore é um conjunto, acontece automaticamente que nas folhas haverá apenas chaves sem valores de lixo.

Agora, vejamos o código de pesquisa do elemento.

 /** * @param g Get. * @throws IgniteCheckedException If failed. */ private void doFind(Get g) throws IgniteCheckedException { for (;;) { // Go down with retries. g.init(); switch (findDown(g, g.rootId, 0L, g.rootLvl)) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; default: return; } } } /** * @param g Get. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { long page = acquirePage(pageId); try { for (;;) { // Init args. g.pageId = pageId; g.fwdId = fwdId; Result res = read(pageId, page, search, g, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert g.pageId != pageId; assert g.fwdId != fwdId || fwdId == 0; // Go down recursively. res = findDown(g, g.pageId, g.fwdId, lvl - 1); switch (res) { case RETRY: checkInterrupted(); continue; // The child page got split, need to reread our page. default: return res; } case NOT_FOUND: assert lvl == 0 : lvl; g.row = null; // Mark not found result. return res; default: return res; } } } finally { if (g.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

A base do algoritmo de travessia da árvore B permaneceu inalterada: eles descem a árvore recursivamente para a folha desejada: se o valor estiver presente, retornam o resultado e, se não, então null . Aparentemente, a recursão foi deixada por conveniência; as árvores B não são profundas.

Fiquei surpreso porque havia uma instalação clara em minha cabeça: a recursão é sempre removida em um projeto real ( não há otimização da recursão final em Java , a recursão é aceitável em projetos em outras linguagens). Mas, na verdade, a altura da árvore B é medida em unidades, porque o tamanho do bloco de pedidos $$$2 ^ {10}$e o número de dados do pedido $$$2 ^ {40}$e a altura será $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

O Apache Ignite adora simultaneidade . Portanto, a árvore suporta modificações competitivas. No momento da operação, uma página é bloqueada, mas outro encadeamento pode modificar o restante da árvore para que uma segunda leitura seja necessária. E assim o procedimento pode alcançar a raiz.

No começo, não entendi o significado dessa funcionalidade, porque o disco é lento e um thread processa calmamente todas as operações de E / S. É claro que a pesquisa no nó carregado a partir do disco custa um pouco e, durante esse tempo, você pode carregar o disco com outra operação, mas tentativas repetidas reduzirão o ganho. No entanto, ocorreu-me que, nessa implementação, os nós não foram liberados imediatamente para o disco após a modificação, mas ficaram na memória por um tempo, para aplicar muitas modificações de uma só vez. Nenhum dado é perdido graças ao Write Ahead Log. Mais sobre isso estará no final do artigo.

Agora vamos ver o código para adicionar um item.

 private T doPut(T row, boolean needOld) throws IgniteCheckedException { checkDestroyed(); Put p = new Put(row, needOld); try { for (;;) { // Go down with retries. p.init(); Result res = putDown(p, p.rootId, 0L, p.rootLvl); switch (res) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; case FOUND: // We may need to insert split key into upper level here. if (!p.isFinished()) { // It must be impossible to have an insert higher than the current root, // because we are making decision about creating new root while keeping // write lock on current root, so it can't concurrently change. assert p.btmLvl <= getRootLevel(); checkInterrupted(); continue; } return p.oldRow; default: throw new IllegalStateException("Result: " + res); } } } catch (IgniteCheckedException e) { throw new IgniteCheckedException("Runtime failure on row: " + row, e); } catch (RuntimeException e) { throw new IgniteException("Runtime failure on row: " + row, e); } catch (AssertionError e) { throw new AssertionError("Assertion error on row: " + row, e); } finally { checkDestroyed(); } } /** * @param p Put. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { assert lvl >= 0 : lvl; final long page = acquirePage(pageId); try { for (;;) { // Init args. p.pageId = pageId; p.fwdId = fwdId; Result res = read(pageId, page, search, p, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert lvl > 0 : lvl; assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; res = p.tryReplaceInner(pageId, page, fwdId, lvl); if (res != RETRY) // Go down recursively. res = putDown(p, p.pageId, p.fwdId, lvl - 1); if (res == RETRY_ROOT || p.isFinished()) return res; if (res == RETRY) checkInterrupted(); continue; // We have to insert split row to this level or it is a retry. case FOUND: // Do replace. assert lvl == 0 : "This replace can happen only at the bottom level."; return p.tryReplace(pageId, page, fwdId, lvl); case NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; return p.tryInsert(pageId, page, fwdId, lvl); default: return res; } } } finally { if (p.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

A única diferença é que, após a detecção da posição, o código bifurca-se na replace e insert . O código de remove não pode mais ser assistido. O mecanismo básico é que, com tentativas repetidas de percorrer recursivamente a árvore, junto com um objeto especial, dependendo da operação: Get , Put ou Remove .

Invoke funciona da mesma maneira, apenas a operação ocorre com uma cópia do registro, então seu tipo é determinado: NOOP para leitura, REMOVE para excluir e PUT para atualizar ou adicionar e, em seguida, é gerado o objeto Put ou Remove correspondente, que é aplicado ao registro na árvore.

Use

Abaixo, examinarei mais de perto dois BPlusTree : CacheDataTree e PendingEntriesTree . No exterior é a implementação de índices - este é um tópico para uma discussão separada, para a qual ainda não estou pronto.

Antes de IgniteCache , vou esclarecer que o mapa distribuído local tem funcionalidade IgniteCache e é chamado IgniteCache - a seguir, simplesmente um cache.

CacheDataTree

CacheDataTree é um mapeamento de vários IgniteCache para o disco. A classificação é multinível: primeiro classifique por ID do cache para agrupar chaves em um cache e depois por hashes.

CacheDataTree não itera no intervalo, pois os índices são implementados nos herdeiros do H2Tree extends BPlusTree ; portanto, o tipo específico de classificação não é importante: qualquer um é suficiente para operações de put e get . Comparar hashes é mais rápido que objetos. Mais importante, porém, um hash uniforme preencherá a árvore mais densamente.

As árvores se equilibram para que não se degenerem em uma lista. Mas se você adicionar chaves igualmente distribuídas à árvore de pesquisa, ela será automaticamente equilibrada. Como as árvores B começam a se equilibrar à medida que surgem problemas, e os hashes misturam as chaves uniformemente, a classificação por hashes reduz a frequência do equilíbrio.

O uso de hashes na árvore de pesquisa não é uma idéia tão estranha quanto parece, seu desenvolvimento lógico levará a uma tentativa mapeada da matriz Hash .

PendingEntriesTree

PendingEntriesTree armazena chaves para dados ao longo do tempo e é usado como definido. A classificação é multinível: primeiro classificada por ID de cache para agrupar chaves em um cache e depois por tempo de vida. Em seguida, há outra rodada de comparação - aparentemente, puramente técnica, para distinguir entre elementos. Ao classificar, é fácil adivinhar que essa classe é usada para pesquisar intervalos. Essa árvore duplica as chaves de entrada do cache para preempção.

Entenda como essa aventura separada funciona.

 @Override public boolean expire( GridCacheContext cctx, IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> c, int amount ) 

 private final IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> expireC = new IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion>() { @Override public void applyx(GridCacheEntryEx entry, GridCacheVersion obsoleteVer) { boolean touch = !entry.isNear(); while (true) { try { if (log.isTraceEnabled()) log.trace("Trying to remove expired entry from cache: " + entry); if (entry.onTtlExpired(obsoleteVer)) touch = false; break; } catch (GridCacheEntryRemovedException ignore) { entry = entry.context().cache().entryEx(entry.key()); touch = true; } } if (touch) entry.context().evicts().touch(entry, null); } }; 

 cctx.cache().removeEntry(this); 

Detalhes da implementação

Trabalhar com páginas no Offheap

Offheap é uma técnica para otimizar o gerenciamento manual de memória em um idioma com um coletor de lixo.

É um mito que, por causa do coletor de lixo, tudo diminua, geralmente os coletores custam uma porcentagem miserável de desempenho . Mesmo grandes montes em si não são um problema, porque os coletores trabalham competitivamente (por exemplo, CMS e G1 em Java) e os servidores possuem dezenas de núcleos . Obviamente, o coletor adiciona pausas imprevisíveis ao aplicativo, o que é importante para jogos, mas tolerável para o banco de dados.

Mas o que realmente será o problema é uma violação da hipótese de geração em uma grande pilha.

E aqui está o fato de que, antes do advento do PDS, o Apache Ignite era posicionado principalmente como um cache entre serviços e um banco de dados em disco (por exemplo, Hadoop ). Portanto, os mapas no Ignite são chamados IgniteCache e têm a funcionalidade de extrusão correspondente. E caches apenas violam a hipótese geracional - neles, a probabilidade de um objeto ser excluído aumenta com o tempo. Portanto, nesse caso, o Offheap para armazenar dados do usuário melhora o desempenho.

Mais bônus:

• A descompactação facilita a implementação de estruturas que contêm mais de elementos Integer.MAX_VALUE .
• Se você mantiver um monte de menos de 32 GB, os links terão 4 bytes , o que economiza alguns gigabytes.
• Como o coletor cria um gráfico de objetos, ele consome memória proporcionalmente ao seu número. E o número de objetos é proporcional ao heap. O coletor também consome uma CPU, que é melhor utilizada para compactação de dados, por exemplo.
• Em montões muito grandes, mesmo que a hipótese geracional não seja violada como um todo, ainda haverá muitos objetos antigos em valor absoluto que a violarão.

Como os dados são então enviados para o disco, os objetos são serializados na memória diretamente por meio de unsafe , e essa área de memória é usada para o buffer de E / S.

Gravar registro antecipado

Write Ahead Log é um log de operações com uma estrutura linear, que acrescenta a ele uma constante, diferente de uma árvore. A árvore é atualizada com menos frequência e, se os dados forem perdidos devido a uma queda, eles serão restaurados do log aplicando operações a partir do último estado salvo. O resultado é um desempenho aprimorado sem comprometer a confiabilidade. Aconselho que você dê uma olhada na interface IgniteWriteAheadLogManager - há documentação detalhada.

Desvio do nó

Como os nós nas árvores B não são pequenos, eles são ignorados pela pesquisa binária. Para isso, descendentes da classe BPlusTree.GetPageHandler são BPlusTree.GetPageHandler e, para operações diferentes, são diferentes.

 private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift) throws IgniteCheckedException { assert row != null; int high = cnt - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = compare(lvl, io, buf, mid, row); if (cmp == 0) cmp = -shift; // We need to fix the case when search row matches multiple data rows. //noinspection Duplicates if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // Found. } return -(low + 1); // Not found. } 

 if (cmp == 0) cmp = -shift; 

Lista de folhas

Para contornar o intervalo com eficiência, as folhas são vinculadas a uma lista. BPlusTree.ForwardCursor , que passa de uma folha para outra, é retornado como resultado da pesquisa. Aparentemente, a passagem do cursor não é isolada de outras operações na árvore, porque ao passar, o bloqueio é realizado apenas em uma página. Não encontrei um mecanismo de sincronização que proteja o acesso aos métodos do cursor.

Conclusão

Como a árvore B + no Apache Ignite é jovem em comparação com outros bancos de dados relacionais, obtemos o conjunto necessário para a árvore B + pronta para produção:

• O WAL oferece segurança barata, como resultado, a árvore raramente é atualizada no disco.
• Fora da pilha com dados em formato serializado.
• Concorrência - para partes da árvore carregadas na memória.