Catálogo de padrões de sistemas distribuídos #4
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
Data Replication — Parte 3
Neste texto, vou comentar sobre padrões relacionados ao processamento de tempo de forma distribuída.
Lamport Clock
Para ilustrar por que timestamps são um problema em computadores, é necessário uma breve explicação.
Em computadores modernos, o mecanismo usado para medir o tempo é um pequeno cristal de quartzo que fica dentro de alguns componentes eletrônicos. Como esses cristais operam em frequências específicas, é possível, com algumas contas básicas, contar o tempo (ou seja, o que conhecemos como clock). Mais detalhes desse tipo de componente eletrônico podem ser encontrados aqui.
O problema é que, com o tempo, fatores externos como poeira, temperatura do circuito e o próprio envelhecimento dos componentes afetam suas propriedades físicas, o que leva o clock a perder precisão. Se você já se deparou com um horário errado no relógio do sistema operacional após ligar um computador antigo, provavelmente foi por causa disso.
Em servidores, isso pode se tornar um problema. Dado que temos um conjunto de máquinas que precisam de sincronização de tarefas, como decidir a ordem dos eventos se o próprio relógio não é confiável?
A título de curiosidade, o Google resolveu esse problema com uma tecnologia chamada TrueTime, usada no banco de dados Spanner. Ela é feita utilizando relógios atômicos e o decaimento radioativo para contar o tempo de uma forma mais precisa.
Mas como não temos os recursos financeiros do Google, existe um mecanismo mais simples para mitigar esse problema. É aqui que entra o Lamport Clock. Sim, quem documentou o padrão foi o mesmo Leslie Lamport mencionado no texto anterior dessa série.
Ao invés de usar os relógios físicos dos servidores, podemos usar relógios lógicos. Ou seja, a cada interação de escrita feita em um determinado servidor, um contador arbitrário é incrementado. Com isso, é possível responder qual evento aconteceu antes de outro. Porém, o mecanismo é bastante limitado, pois só trata de um evento em relação ao outro e não desse evento em relação a todos os outros eventos. Ou seja, eu consigo dizer que A < B e B < C, porém, não é possível afirmar que A < C, por exemplo. Portanto, esse tipo de abordagem fornece apenas ordenações parciais, na prática.
Vamos a um exemplo para entender melhor. Considere três processos P1, P2 e P3 em um sistema distribuído:
Estado Inicial
P1, P2, P3 com Clock = 0
Evento em P1:
P1 realiza uma operação (por exemplo, envia uma mensagem para P2).
P1 incrementa seu relógio: P1.Clock = 1
Mensagem Enviada de P1 para P2:
P1 envia uma mensagem para P2 com um carimbo de tempo igual a 1.
Mensagem Recebida por P2:
P2 recebe a mensagem de P1.
P2 atualiza seu clock usando a função max*
P2.Clock = max(0, 1) + 1 = 2
*é uma função que compara A e B e retorna o maior entre eles.
Evento em P2:
P2 realiza uma operação (por exemplo, envia uma mensagem para P3).
P2 incrementa seu relógio: P2.Clock = 3
E assim sucessivamente. Em termos gráficos, temos:
Hybrid Clock
Este é um padrão que visa resolver a limitação do anterior. Como no Lamport Clock o tempo gerado pelo mecanismo é um inteiro qualquer, na hora de realizar buscas com datas no cluster, por exemplo, não é possível transformar uma data inserida pelo usuário nesse inteiro.
Para resolver esse problema, basta usar o padrão anterior com a adição de um mecanismo que associa um timestamp com o contador do Lamport Clock. Aqui está um exemplo do mecanismo completo em Javascript:
class HybridTimestamp {
constructor(systemTime, ticks) {
this.wallClockTime = systemTime;
this.ticks = ticks;
}
static fromSystemTime(systemTime) {
// Iniciar com -1, faz o metodo addticks transformar o valor em 0
return new HybridTimestamp(systemTime, -1);
}
max(other) {
if (this.getWallClockTime() === other.getWallClockTime()) {
return this.getTicks() > other.getTicks() ? this : other;
}
return this.getWallClockTime() > other.getWallClockTime() ? this : other;
}
getWallClockTime() {
return this.wallClockTime;
}
addTicks(ticks) {
//basicamente é aqui a diferença entre os dois patterns
return new HybridTimestamp(this.wallClockTime, this.ticks + ticks);
}
getTicks() {
return this.ticks;
}
compareTo(other) {
if (this.wallClockTime === other.wallClockTime) {
return this.ticks - other.ticks;
}
return this.wallClockTime - other.wallClockTime;
}
}Cada nó do cluster terá sua própria instância do Hybrid Clock. Além disso, por mais que o mecanismo usado (horário do sistema operacional), tenha os problemas de precisão já mencionados antes, ainda assim, com o uso do contador adicional, esse problema é minimizado.
Clock-Bound Wait
Esse padrão é um exemplo de que nem sempre algo que está na literatura você deve aplicar.
A ideia aqui é: mesmo usando o Hybrid Clock, pode acontecer de, em alguns cenários distribuídos, os valores ainda sofrerem atraso para serem processados, o que pode impactar o incremento dos contadores.
Vamos a um exemplo. Alice lê o valor Title no servidor Amber no clock 1 (o contador do servidor está atrasado devido aos problemas mencionados anteriormente), que retorna “Before Dawn”. Bob tenta ler o mesmo valor no servidor Blue, porém, como o clock do servidor está como 2, o retorno é “After Dawn”. Ambos os servidores estão com o Hybrid Clock rodando individualmente.
Qual o valor correto em uma replicação para o servidor Green? Before ou After Dawn?
A solução proposta por esse padrão é esperar um tempo arbitrário para garantir que os valores foram replicados para outros nós dentro do cluster.
Ou seja, para toda operação de escrita, é adicionado um overhead intencional de um determinado tempo, para esperar os nós sincronizarem.
Se o tempo que leva para uma operação média no cluster ser efetuada é 10 milisegundos, todas as operações terão um delay intencional adicionado de 10ms para lidar com isso.
Esse padrão tem algumas desvantagens: como saber qual tempo usar como parâmetro de espera? Como medir o tempo médio das operações? Por mais que você tenha alguma estatística que diga que o p99 das sincronizações é 10ms, pode acontecer de algumas operações serem mais lentas que 10ms e aí? O que acontece?
Além disso, caso o hardware mude de alguma forma (ex: uma troca de instância na nuvem para uma mais robusta ou mais lenta), esses valores podem mudar. Qualquer instabilidade na rede também pode impactar esse tempo. De uma maneira geral, qualquer solução na computação que opera através de tempos fixos ao invés de esperar eventos serem recebidos é uma ideia ruim, na minha opinião. Qualquer mínima variação no tempo de processamento quebra sua regra de espera. Fora o desperdício de ciclos de CPU e afins, com delays adicionados através de loops.
Como alternativa a essa ideia, a minha sugestão é que eventos e filas funcionem melhor para a comunicação intra-cluster.
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.
