Catálogo de padrões de sistemas distribuídos #3
Olá!
Esse texto faz parte de uma série. Você encontra os textos anteriores nos links abaixo:
Data Replication — Parte 1
Data Replication — Parte 2
No texto de hoje, vou comentar brevemente sobre a parte final de patterns relacionados a replicação de dados.
Paxos
A ideia aqui é um algoritmo de um artigo específico desenvolvido por uma grande referência em sistemas distribuídos: Leslie Lamport, em 1998. Ele, inclusive, foi ganhador do prêmio Turing pelo seu trabalho na área.
O algoritmo é composto por duas fases: promise e commit. Na primeira fase, um nó recebe o valor proposto para alteração e sugere esse valor para todos os outros nós do cluster, através de broadcast. Os outros retornam a chamada de proposta de alteração (propose) com o ID da proposta e o valor aceito, após processar alguma regra para decidir se aceitam o valor ou não.
Após o recebimento dos valores aceitos dos outros nós (no mínimo, 50% + 1, que é o Majority Quorum, padrão comentado na parte 1)), o valor que é o consenso é replicado para todos os outros nós, o que faz o cluster entrar na fase de commit.
Após a execução da fase de commit, o valor é aceito em sua versão final. Caso ocorra alguma discordância sobre o que é o consenso entre os nós, o processo volta do início.
Se pareceu complicado, é porque o domínio de resolução de consenso é algo complicado mesmo. Atualmente, o que é usado em sistemas distribuídos modernos é um outro algoritmo, chamado Raft, que basicamente é uma versão mais simples do Paxos.
Uma curiosidade engraçada aqui: o Paxos tem fama entre os profissionais de computação de “ninguém entendeu o paper oficial direito, então a indústria criou o Raft no lugar para ver se alguém entendia”. Fica o link do paper original do Paxos e do Raft se você quiser se aprofundar.
Inclusive, o Raft é usado em várias aplicações distribuídas modernas e robustas, como etcd, Consul e CockroachDB.
Fixed Partitions
O problema que esse padrão resolve é o seguinte: imagine que você precisa distribuir dados entre um conjunto de nós dentro de um cluster. Para simplificar, vou sugerir usar o mecanismo mais simples de distribuição de dados que existe nesses casos: uma hash table.
Ou seja, um valor é distribuído para uma determinada partição (nó) após a execução do algoritmo de hashing. Lembrando que, para isso funcionar corretamente, o algoritmo precisa ser balanceado para que não ocorram colisões em casos de valores que gerem hashes similares. Em termos gráficos, temos um processo assim:
Agora, imagine que o cluster aumentou de tamanho e foram adicionadas as partições D e E. O que vai acontecer agora é que dados novos serão inseridos nas partições novas. Até aqui, tudo certo.
Porém, a distribuição dos dados não está uniforme dentro do cluster, podendo acarretar que a partição A tenha 40% dos dados ao invés de cada uma ter 20% (considerando 5 partições) ou cenários de desbalanceamento similares. A metáfora aqui é a seguinte: imagine que o critério de sucesso é que 5 pessoas andem 100m. Se uma corre e as outras não, o output total do mecanismo é nivelado por baixo (nesse caso, por quem anda mais devagar).
O mesmo acontece com clusters e nós. Portanto, a solução passa por não usar partições físicas (ou seja, atreladas aos clusters) e sim partições lógicas de tamanho fixo (por exemplo, podemos usar 1024 partições lógicas para 3, 5, 120, 777 ou 1024 nós físicos, não importa). Dessa forma, garantimos uma distribuição mais uniforme dos dados de maneira geral. E mesmo em caso de movimentação de dados (ex: saindo de 1024 para 2046), a movimentação fica mais rápida, porque são pedaços pequenos de dados, o que melhora a performance do ecossistema.
Key-Range Partitions
Como fazer queries em dados distribuídos de forma eficiente? Sem ter que buscar em todos os nós realizando um full scan, por exemplo?
Uma das formas é usar o padrão anterior de partições lógicas em conjunto com um critério de distribuição dos dados por um determinado intervalo (range) de valores.
Se a busca é por nome, a distribuição pode ser feita pela primeira letra. Se a busca é por IDs numéricos, pode ser feita por intervalos de valores, de acordo com suas necessidades (ex: 1 milhão de registros por partição ou algo similar). Em um exemplo com preços, temos:
Se pareceu ilógico usar hashing e esse critério de range juntos (dado que são mecanismos de decisão diferentes), saiba que é por isso que o domínio de sistemas distribuídos é tão complexo de uma maneira geral.
Two-Phase Commit
É um mecanismo muito similar ao Paxos, com duas fases (prepare e commit). Porém, a diferença é uma só: enquanto o Paxos requer um Majority Quorum para aplicar os novos valores, o 2PC requer que todos os nós aceitem um determinado valor, pois mais do que consenso, ele é pensado para resolver transações distribuídas (ou seja, operações indivisíveis que dão certo ou não em um conjunto X de nós).
O mecanismo que ele usa para aplicar os valores são locks individuais em cada nó durante o processo de decisão de aplicação das alterações.
O que acontece caso um dos nós fique indisponível nesse processo? Bloqueios. Essa é a principal limitação do 2PC. O cluster pode ficar com algum lock ativo caso alguma máquina pare de funcionar e não solte a trava corretamente. Para mitigar isso, pode-se utilizar um WAL para garantir que o nó mantenha a consistência após o término da indisponibilidade.
O 2PC possui uma evolução, chamada Three Phase Commit, que visa mitigar alguns desses problemas em troca de um pouco mais de passos adicionais de verificação e que consequentemente, aumenta a latência geral do ecossistema.
Espero que esse texto tenha sido útil para você de alguma forma.
Até!
Você gostou do conteúdo e gostaria de fazer mentoria comigo? Clique aqui e descubra como.
