🧘🏾 👲 🤙🏻 Distribuição de dados no Apache Ignite 😹 🌛 😻

Olá! Este post é uma versão resumida da minha palestra de mesmo nome na reunião da comunidade Apache Ignite . Você pode assistir à versão em vídeo completa, juntamente com perguntas e respostas aqui , e baixar os slides aqui . No relatório, tentei mostrar por exemplos como os dados são distribuídos no Apache Ignite.

Por que você precisa distribuir qualquer coisa

Um histórico bastante padrão do desenvolvimento de qualquer sistema que exija armazenamento e processamento de dados é a conquista de um determinado limite. Existem muitos dados e eles não são fisicamente colocados no dispositivo de armazenamento ou a carga está aumentando a uma taxa que um servidor não consegue mais processar um número tão grande de solicitações. Existem casos frequentes em que ambos ocorrem.

Como regra, eles vêm para uma das duas soluções: compartilhar o armazenamento existente ou alternar para um banco de dados distribuído. Ambas as soluções têm vários recursos comuns, o mais óbvio dos quais é o uso de mais de um nó para trabalhar com dados. Além disso, muitos nós chamarei de topologia.

O problema da distribuição de dados entre os nós da topologia pode ser formulado como um conjunto de requisitos, que nossa distribuição deve satisfazer:

É necessário um algoritmo que permita que todos os nós da topologia e aplicativos clientes cheguem à mesma conclusão sobre em qual nó ou nós o determinado objeto (ou chave) está.
Uniformidade de distribuição. Quanto mais uniformemente os dados são distribuídos entre os nós, mais uniformemente a carga nesses nós será distribuída. Aqui, suponho que nossos nós tenham aproximadamente os mesmos recursos.
. , , . , , , .

Atingir os dois primeiros requisitos é bastante fácil.

Uma abordagem familiar, frequentemente usada para equilibrar a carga entre servidores funcionalmente equivalentes, dividindo o módulo N, em que N é o número de nós na topologia e temos uma correspondência individual entre o número do nó e seu identificador. Então, tudo o que precisamos fazer é representar a chave do objeto como um valor numérico usando uma função hash e tirar o restante da divisão por N. do valor

imagem

obtido.O diagrama mostra a distribuição de 16 chaves em 3 nós. Pode-se observar que essa distribuição é uniforme e o algoritmo para obter o nó para o objeto é simples e garante que, se todos os nós da topologia usarem esse algoritmo, o mesmo resultado será obtido para a mesma chave e o mesmo N.

Mas o que acontece se introduzirmos o quarto nó na topologia?

imagem

Nossa função mudou, agora tomamos o restante da divisão por 4, não por 3. E se a função mudou, a distribuição mudou e muito.

Aqui, o local anterior dos objetos para a versão anterior da topologia de três nós é mostrado em vermelho e a posição dos objetos para a nova versão da topologia de quatro nós é verde, respectivamente. Isso é muito parecido com os arquivos diff comuns, mas em vez de arquivos, temos nós.

É fácil ver que os dados foram movidos não apenas para o novo nó, mas também houve uma troca de dados entre os nós que já estavam na topologia. Essa. observamos tráfego espúrio entre nós e o requisito de uma alteração mínima na distribuição não é atendido.

Duas maneiras populares de resolver o problema da distribuição de dados, levando em consideração os requisitos listados, são as seguintes:

Hash consistente
Maior algoritmo de peso aleatório (HRW), também conhecido como hash de encontro.

Ambos os algoritmos são muito simples. Suas descrições na Wikipedia se encaixam em várias frases. Embora seja difícil chamá-los óbvios. Para os interessados, recomendo a leitura dos artigos originais Hashing consistente e árvores aleatórias: protocolos de armazenamento em cache distribuídos para alívio de pontos quentes na World Wide Web e um esquema de mapeamento baseado em nome para encontro . Mais compreensivelmente, na minha opinião, a idéia de um algoritmo de hash consistente é transmitida neste curso de Stanford .

Vejamos esses algoritmos com mais detalhes.

Hashing Consistente

O truque subjacente ao algoritmo de hash consistente é mapear os nós e os objetos armazenados no mesmo espaço identificador. Isso torna nossas entidades, objetos e nós aparentemente diferentes comparáveis.

Para obter esse mapeamento, simplesmente aplicamos a mesma função de hash às chaves dos objetos e aos identificadores dos nós. O resultado da função de hash para o nó será chamado de token; isso será útil para nós posteriormente.

Representamos nosso espaço identificador na forma de um círculo, ou seja, simplesmente assumimos que o valor máximo do identificador segue imediatamente o valor mínimo do identificador.

Agora, para determinar em qual nó o objeto vive, você precisa obter o valor da função hash de sua chave e simplesmente mover no sentido horário ao redor do círculo até encontrarmos o token de um nó no caminho. A direção do movimento não é importante, mas deve ser fixa.

O movimento imaginário no sentido horário é funcionalmente equivalente a uma pesquisa binária em uma matriz classificada de tokens de nó.

imagem

No diagrama, cada setor de uma cor específica reflete o espaço identificador pelo qual um nó específico é responsável.

Se adicionarmos um novo nó,

imagem

ele dividirá um dos setores em duas partes e assumirá completamente as chaves correspondentes.

Neste exemplo, o nó 3 assumiu parte das chaves do nó 1.

Como você pode ver, essa abordagem fornece uma distribuição bastante desigual de objetos entre nós, porque é altamente dependente dos identificadores dos próprios nós. Como essa abordagem pode ser melhorada?

Você pode atribuir mais de um token aos nós (geralmente centenas). Isso pode ser alcançado, por exemplo, introduzindo muitas funções de hash para o nó (uma por token) ou aplicando repetidamente a mesma função de hash ao token obtido na etapa anterior. Mas não devemos esquecer as colisões. Não deve haver dois nós com o mesmo token.

imagem

Neste exemplo, cada nó possui 4 tokens.

O que mais é importante mencionar: se queremos garantir a segurança dos dados no caso de um nó sair da topologia, precisamos armazenar as chaves em vários nós (as chamadas réplicas ou backups). No caso do algoritmo de hash consistente, as réplicas serão os seguintes nós N-1 no círculo, onde N é o fator de replicação. Obviamente, a ordem dos nós deve ser determinada por um token específico (por exemplo, pelo primeiro), porque ao usar vários tokens para cada um deles, a organização dos nós pode ser diferente. Preste atenção ao esquema: ele não possui um padrão claro de repetição de nós.

Quanto à exigência de uma alteração mínima na distribuição ao alterar a topologia, ela é satisfeita porque a ordem mútua dos nós no círculo permanece inalterada. Essa. remover um nó da topologia não alterará a relação de ordem entre os nós restantes.

Hash de encontro

O algoritmo de hash Rendezvous parece ainda mais simples que o hash consistente. O algoritmo é baseado no mesmo princípio de invariância das relações de ordem. Mas, em vez de tornar nós e objetos comparáveis, fazemos apenas nós para um objeto específico comparável. Essa. determinamos a relação de ordem entre os nós para cada objeto independentemente.

Mais uma vez, o hash nos ajuda com isso. Mas agora, para determinar o peso do nó N para um determinado objeto O, misturamos o identificador do objeto com o identificador do nó e obtemos o hash desse mix. Depois de fazer essa operação para cada nó, obtemos um conjunto de pesos pelos quais classificamos os nós.

O nó que acabou sendo o primeiro e será responsável por armazenar o objeto.

Como todos os nós da topologia usam os mesmos dados de entrada, o resultado para eles será idêntico. O que satisfaz o primeiro requisito.

imagem

Considere um exemplo. Aqui temos uma relação de ordem entre três nós para quatro chaves diferentes. Amarelo indica o nó com maior peso, ou seja, o nó que será responsável por uma chave específica.

Adicione outro nó à topologia.

imagem

Eu deliberadamente coloquei na diagonal para levar em conta todas as opções possíveis. Aqui, o nó 3, mostrado em verde, entrou na topologia. Portanto, a distribuição de peso dos nós para cada uma das chaves foi alterada. Vermelho indica os nós que mudaram de local na lista para uma chave específica, porque os pesos desses nós eram menores que o peso do nó adicionado. No entanto, essa alteração afetou apenas uma das chaves, K3.

Vamos derivar traiçoeiramente um nó de uma topologia.

imagem

Mais uma vez, as alterações afetaram apenas uma tecla, desta vez K1. Os objetos restantes não foram afetados. O motivo, como no caso de hash consistente, é a invariância do relacionamento de ordem entre qualquer par de nós. Essa. o requisito de uma alteração mínima na distribuição é atendido e não há tráfego espúrio entre os nós.

A distribuição para o encontro parece muito boa e não requer truques adicionais em comparação com hash consistente como tokens.

Caso desejemos oferecer suporte à replicação, o próximo nó da lista será a primeira réplica do objeto, o próximo nó será a segunda réplica etc.

Como o hash de encontro é usado no Apache Ignite

A chamada função de afinidade é responsável pela distribuição de dados no Apache Ignite (consulte a interface AffinityFunction ). A implementação padrão é o hash de encontro (consulte a classe RendezvousAffinityFunction ).

A primeira coisa que você precisa prestar atenção é que o Apache Ignite não mapeia objetos armazenados diretamente nos nós de topologia. Em vez disso, é introduzido um conceito adicional - partição.

Uma partição é um contêiner para objetos e uma unidade de replicação. Além disso, o número de partições para um cache específico (este é um análogo da tabela nos bancos de dados familiares) é definido no estágio de configuração e não muda durante o ciclo de vida do cache.

Assim, podemos exibir objetos em partições usando divisão de módulo efetiva e usar hash de encontro para exibir partições em nós.

imagem

Porque como o número de partições para o cache é constante, podemos calcular a distribuição da partição por nós uma vez e armazenar em cache o resultado até que a topologia seja alterada.

Cada nó calcula essa distribuição independentemente, mas em todos os nós com os mesmos dados de entrada, essa distribuição será idêntica.

A partição pode ter várias cópias, nós as chamamos de backups. A partição primária é chamada de partição primária.

Para a melhor distribuição de chaves entre partições e partições por nós, a seguinte regra deve ser cumprida: o número de partições deve ser significativamente maior que o número de nós; por sua vez, o número de chaves deve ser significativamente maior que o número de partições.

Os caches no Ignite são particionados e replicados.

Em um cache particionado, o número de backups é definido no estágio de criação do cache. Partições - primárias e backups - são distribuídas igualmente entre os nós. Esse cache é mais adequado para trabalhar com dados operacionais, como fornece o melhor desempenho de gravação, o que depende diretamente do número de backups. Em geral, quanto mais backups, mais nós devem confirmar o registro de chave.

imagem

Neste exemplo, o cache possui um backup. Essa. podemos perder um nó e não perder dados, porque Os backups de partição nunca são armazenados no mesmo nó que a partição primária ou seu outro backup.

No cache replicado, o número de backups é sempre igual ao número de nós de topologia menos 1. Ou seja, cada nó sempre contém cópias de todas as partições.

imagem

Esse cache é mais adequado para trabalhar com dados raramente alterados (por exemplo, diretórios) e fornece a maior disponibilidade, como podemos perder nós N-1 (neste caso, 3) sem perder dados. Também nesta opção, obteremos o desempenho máximo de leitura se permitirmos ler dados das partições primárias e dos backups.

Colocação de dados no Apache Ignite

Um conceito importante a ser lembrado para obter o melhor desempenho é a colocação. Colocação é a colocação de qualquer objeto no mesmo local. No nosso caso, objetos são entidades armazenadas no cache e um local é um nó.

Se os objetos forem distribuídos por partições da mesma função de afinidade, é lógico que objetos com a mesma chave de afinidade caiam na mesma partição e, portanto, no mesmo nó. No Ignite, isso é chamado de colocation de afinidade.

Por padrão, uma chave de afinidade é a chave primária de um objeto. Mas no Ignite, você pode usar qualquer outro campo de um objeto como uma chave de afinidade.

A disposição reduz significativamente a quantidade de dados enviados entre os nós para executar cálculos ou consultas SQL, o que naturalmente leva a uma redução no tempo gasto nessas tarefas. Considere esse conceito por exemplo.

Deixe nosso modelo de dados consistir em duas entidades: order (Order) e position position (OrderItem). Um pedido pode corresponder a muitos itens. Os identificadores de pedido e item de linha são independentes, mas o item de linha possui uma chave estrangeira que se refere ao pedido correspondente.

Suponha que precisamos executar alguma tarefa, que para cada pedido deve executar cálculos para as posições desse pedido.

Por padrão, uma chave de afinidade é uma chave primária. Portanto, ordens e posições serão distribuídas entre os nós de acordo com suas chaves primárias, as quais, lembro-me, são independentes.

imagem

No diagrama, as ordens são representadas por quadrados e posições em círculos. Cor indica que o item pertence ao pedido.

Com essa distribuição de dados, nossa tarefa hipotética será enviada para o nó em que a ordem desejada está localizada e, em seguida, será necessário ler as posições de todos os outros nós ou enviar uma subtarefa para esses nós e obter o resultado do cálculo. Essa é uma interação de rede desnecessária que pode e deve ser evitada.

E se dissermos ao Ignite que os itens do pedido devem ser colocados nos mesmos nós que os próprios pedidos, ou seja, coletar dados?

Como chave de afinidade para a posição, pegamos a chave estrangeira OrderId e esse campo será usado ao calcular a partição à qual o registro pertence. Além disso, dentro da partição, sempre podemos encontrar nosso objeto pela chave primária.

imagem

Agora, se os dois caches (Order e OrderItem) usarem a mesma função de afinidade com os mesmos parâmetros, nossos dados estarão próximos e não precisaremos percorrer a rede para obter itens de pedido.

Configuração de afinidade no Apache Ignite

Na implementação atual, um objeto de função de afinidade é um parâmetro de configuração de cache.

A própria função de afinidade aceita os seguintes argumentos ao criar:

Número de partições;
O número de backups (na verdade, esse também é o parâmetro de configuração do cache);
Filtro de backup;
Sinalizar excludeNeighbors.

Essas configurações não podem ser alteradas.

Com o número de partições e backups, tudo parece estar claro. Falarei sobre o filtro de backup e o sinalizador excludeNeighbors um pouco mais tarde.

No tempo de execução, a função de afinidade de entrada recebe a topologia atual do cluster - essencialmente uma lista de nós do cluster - e calcula a distribuição da partição por nós de acordo com os exemplos que mostrei quando falei sobre o algoritmo de hash de encontro.

Quanto ao filtro de backup, este é um predicado que permite impedir que funções de afinidade designem partições de backup para um nó para o qual o predicado retornou falso.

Como exemplo, suponha que nossos nós físicos - servidores - estejam localizados no datacenter em diferentes racks. Normalmente, cada rack tem seu próprio poder independente ...

imagem

... e se perdermos o rack, perderemos os dados.

imagem

Neste exemplo, perdemos metade das partições.

Mas se definirmos o filtro de backup correto, a distribuição será alterada de maneira que ...

imagem

... se o rack for perdido, não haverá perda de dados e eles ainda estarão disponíveis.

imagem

O sinalizador excludeNeighbors executa uma função semelhante e, na verdade, é uma abreviação para um caso específico.

Geralmente, vários nós do Ignite são executados no mesmo host físico. Esse caso é muito parecido com o exemplo de racks no data center, só que agora estamos lutando contra a perda de dados com a perda do host, não os racks.

imagem

O resto é o mesmo. Você pode implementar esse comportamento usando um filtro de backup. Esse sinalizador é um legado histórico e pode ser removido na próxima versão principal do Ignite.

Parece que eu falei sobre a função de afinidade e distribuição de dados, tudo o que um desenvolvedor que usa o Apache Ignite precisa saber.

Concluindo, vejamos um exemplo da distribuição de 16 partições de acordo com a topologia de 3 nós. Por simplicidade e clareza, acreditamos que as partições não possuem backups.

Acabei de fazer e escrevi um pequeno teste que me trouxe a distribuição real:

imagem

como você pode ver, a uniformidade da distribuição não é ideal. Mas o erro será visivelmente mais baixo com um aumento no número de nós e partições. A regra principal que deve ser observada é que o número de partições é significativamente maior que o número de nós. Agora, no Ignite, o número padrão de partições para um cache particionado é 1024.

Agora, adicione um novo nó à topologia.

imagem

Parte das partes se mudou para ele. Ao mesmo tempo, foi observado o requisito de uma alteração mínima na distribuição: o novo nó recebeu parte das partições, enquanto os outros nós não trocaram partições.

Removemos da topologia o nó que estava presente no estágio inicial:

imagem

Agora todas as partições associadas ao nó zero foram redistribuídas entre outros nós da topologia, sem violar nossos requisitos de distribuição.

Como você pode ver, a solução para problemas complexos geralmente é baseada em idéias bastante triviais, embora não totalmente óbvias. As soluções descritas são usadas na maioria dos bancos de dados distribuídos e fazem um bom trabalho. Mas essas decisões são aleatórias e, portanto, a uniformidade da distribuição está longe de ser ideal. A uniformidade pode ser aprimorada sem sacrificar o desempenho e outros requisitos de distribuição? A questão permanece em aberto.