Relógio Vetorial (Vector Clock)

Um Relógio Vetorial é uma estrutura de dados usada para rastrear a ordem causal de eventos em sistemas distribuídos, registrando as mudanças feitas por cada processo. É especialmente útil em ambientes onde a sincronização perfeita dos relógios entre servidores não é garantida, como em sistemas de grande escala.

História e Origem

Os Relógios Vetoriais foram introduzidos por Colin Fidge em 1988 e por Friedemann Mattern no mesmo ano, de forma independente. Essas propostas surgiram como uma evolução do conceito de Lamport Timestamps, que, embora fossem capazes de fornecer uma ordem parcial dos eventos, não podiam capturar completamente a causalidade entre eventos em sistemas distribuídos.

Contexto

Os sistemas distribuídos frequentemente enfrentam o desafio de manter a ordem correta dos eventos devido à ausência de um relógio global sincronizado. Em um ambiente onde múltiplos processos realizam mudanças de forma independente, entender a relação causal entre essas mudanças é crucial para garantir a consistência dos dados. Os Relógios Vetoriais surgiram como uma solução para esse problema, permitindo que os sistemas identifiquem a ordem causal de eventos sem a necessidade de sincronização de relógios.

Aplicabilidade

Relógios Vetoriais são amplamente utilizados em sistemas distribuídos para resolver problemas de:

• Controle de Versão: Usado em sistemas de controle de versão como o Git (que não usa Vector Clock, mas RAG) para rastrear mudanças feitas por diferentes colaboradores.
• Bancos de Dados Distribuídos: Utilizado por bancos de dados como Cassandra e DynamoDB para manter a consistência dos dados.
• Detecção de Conflitos: Ajuda a identificar e resolver conflitos de atualização em sistemas onde múltiplos processos podem modificar os dados simultaneamente.

É comum manter um Relógio Vetorial lado a lado com o objeto que se deseja versionar. Isso significa que cada versão do objeto carrega consigo um Relógio Vetorial, que registra o histórico das mudanças feitas por cada processo. Essa abordagem permite que, ao comparar diferentes versões de um objeto, seja possível identificar a relação causal entre elas de forma precisa.

Quando ocorre um conflito entre duas versões de um objeto, a determinação da relação causal comum pode auxiliar na resolução do conflito. Por exemplo, se dois processos realizaram mudanças conflitantes em um objeto, o sistema pode usar os Relógios Vetoriais para encontrar a última versão comum entre as versões conflitantes. Essa versão comum serve como um ponto de partida para entender as divergências e aplicar uma estratégia de recuperação.

Funcionamento

Um Relógio Vetorial é representado por um dicionário, onde cada chave corresponde a um processo no sistema distribuído e cada valor representa um contador de eventos para esse processo. Cada processo mantém seu próprio vetor e os atualiza de acordo com as seguintes regras:

1. Inicialização: O dicionário é inicializado com o identificador do processo e o contador começando em zero.
2. Evento Local: Quando um processo executa um evento local, ele incrementa seu contador local.
3. Envio de Mensagem: Quando um processo envia uma mensagem, ele inclui seu vetor na mensagem.
4. Recebimento de Mensagem: Quando um processo recebe uma mensagem, ele atualiza cada elemento de seu vetor para ser o máximo entre seu valor atual e o valor recebido.

Exemplo:

Considere um sistema distribuído com três processos A, B e C. Inicialmente, os vetores são:

• A: {}
• B: {}
• C: {}

1. A executa um evento local:

• A: {‘A’: 1}

1. A envia uma mensagem para B:

• Mensagem de A para B inclui: {‘A’: 1}

1. B recebe a mensagem e atualiza seu vetor:

• B: {‘A’: 1, ‘B’: 1}

1. B executa um evento local:

• B: {‘A’: 1, ‘B’: 2}

1. B envia uma mensagem para C:

• Mensagem de B para C inclui: {‘A’: 1, ‘B’: 2}

1. C recebe a mensagem e atualiza seu vetor:

• C: {‘A’: 1, ‘B’: 2, ‘C’: 1}

Comparação entre Relógios Vetoriais

A comparação entre dois Relógios Vetoriais pode resultar em quatro possíveis resultados:

• equals: Ambos os relógios são idênticos.
• less_than: O relógio local é, em relação ao comparado, menor em pelo menos um dos elementos e igual nos demais.
• greater_than: O relógio local é, em relação ao comparado, maior em pelo menos um dos elementos e igualnos demais.
• conflict: Há uma mistura de elementos maiores e menores entre os dois relógios, indicando uma divergência.

Implementação do Vector Clock

class VectorClock:
    def __init__(self, data=None):
        self.data = data or {}

    def compare(self, other):
        less_than = False
        equals_to = True
        greater_than = False

        self_keys = set(self.data.keys())
        other_keys = set(other.data.keys())
        all_keys = self_keys.union(other_keys)

        for p in all_keys:
            s_val = self.data.get(p, 0)
            other_val = self.data.get(p, 0)

            if s_val < other_val:
                less_than = True
                equals_to = False
            elif s_val > other_val:
                greater_than = True
                equals_to = False

        if equals_to:
            return 'equals'
        elif less_than and not greater_than:
            return 'less_than'
        elif greater_than and not less_than:
            return 'greater_than'
        else:
            return 'conflict'

    def update(self, pid):
        self.data[pid] = self.data.get(pid, 0) + 1

Exemplos de Uso

Classe Envelope

A classe Envelope é usada para encapsular dados e o Relógio Vetorial associado.

class Envelope:
    def __init__(self, data, vector_clock):
        self.data = data
        self.vector_clock = vector_clock

Classe ResourceServer

A classe ResourceServer gerencia um recurso compartilhado e resolve conflitos com base nos Relógios Vetoriais.

class ResourceServer:
    def __init__(self):
        self.resource = Envelope(data="initial data", vector_clock=VectorClock({}))

    def update_resource(self, process):
        conflict = self.resource.vector_clock.compare(process.local_copy.vector_clock)
        if conflict == 'conflict':
            print(f"Conflict detected when {process.pid} tried to update the resource.")
        else:
            self.resource = process.local_copy
            print(f"Resource updated by {process.pid}: {self.resource.data}")

Classe Process

A classe Process representa um processo que pode modificar o recurso compartilhado.

class Process:
    def __init__(self, pid, resource_server):
        self.pid = pid
        self.resource_server = resource_server
        self.local_copy = Envelope(
            data=resource_server.resource.data,
            vector_clock=VectorClock(resource_server.resource.vector_clock.data.copy())
        )

    def modify_resource(self, new_data):
        self.local_copy.data = new_data
        self.local_copy.vector_clock.update(self.pid)

Exemplo de Uso Completo

# Inicialmente, o servidor de recursos é criado.
resource_server = ResourceServer()

# Servidores de processo A, B e C são criados e fazem modificações no recurso.
process_a = Process('A', resource_server)
process_b = Process('B', resource_server)
process_c = Process('C', resource_server)

# O processo A faz uma modificação no recurso.
process_a.modify_resource("modified by A")
resource_server.update_resource(process_a)

# O processo B recupera o recurso atualizado e faz uma modificação.
process_b.modify_resource("modified by B")
resource_server.update_resource(process_b)

# O processo C ainda tem a versão antiga do recurso e tenta fazer uma modificação.
process_c.modify_resource("modified by C")
resource_server.update_resource(process_c)

Saída esperada:

Resource updated by A: modified by A
Resource updated by B: modified by B
Conflict detected when C tried to update the resource.

Comparações

Comparado aos Lamport Timestamps, os Relógios Vetoriais são mais robustos na captura da causalidade, mas têm um custo maior em termos de memória e processamento. Enquanto os Lamport Timestamps usam um único contador, os Relógios Vetoriais precisam de um dicionário de tamanho variável, dependendo do número de processos que interagem.

Melhores Práticas

• Sincronização Regular: Certifique-se de que os processos sincronizem seus vetores regularmente para evitar inconsistências.
• Tamanho do Sistema: Considere o tamanho do sistema, pois dicionários grandes podem impactar o desempenho.
• Tratamento de Mensagens Perdidas: Implemente mecanismos para lidar com mensagens perdidas, como retransmissões ou verificações periódicas.

Referências

• Fidge, C. J. (1988). “Timestamps in Message-Passing Systems that Preserve the Partial Ordering”. Australian National University, Department of Computer Science, Technical Report TR-CS-88-19.
• Mattern, F. (1988). “Virtual Time and Global States of Distributed Systems”. Parallel and Distributed Algorithms, North-Holland, 1988.

Conclusão

Relógios Vetoriais são ferramentas poderosas para manter a ordem e detectar causalidade

em sistemas distribuídos. Eles superam algumas limitações dos Lamport Timestamps, mas com um custo maior em termos de memória e processamento. A compreensão e a implementação correta dos Relógios Vetoriais são essenciais para o desenvolvimento eficiente de sistemas distribuídos.

Para estudos futuros, recomenda-se explorar algoritmos de controle de concorrência que utilizam Relógios Vetoriais e investigar métodos para otimizar o desempenho em grandes sistemas distribuídos.