CRDTs em Csharp e Go: Implementando Estruturas de Dados Distribuídas Livre de Conflitos

Definição

Os Conflict-free Replicated Data Types (CRDTs) constituem uma classe formal de estruturas de dados distribuídas projetadas para garantir convergência determinística em ambientes replicados e assíncronos, sem dependência de coordenação central ou bloqueios globais. Fundamentam-se em propriedades algébricas específicas, associatividade, comutatividade e idempotência, que asseguram a fusão consistente de estados ou operações concorrentes. Formalmente, CRDTs são modelados sobre join-semilattices, garantindo monotonicidade do estado e permitindo alcançar Consistência Eventual Forte (Strong Eventual Consistency – SEC), mesmo sob partições de rede (SHAPIRO et al., 2011).

Do ponto de vista teórico, CRDTs posicionam-se como uma alternativa prática dentro do teorema CAP, priorizando disponibilidade e tolerância a partições, enquanto oferecem convergência determinística sem a necessidade de consenso distribuído síncrono.

Tipos de CRDTs

CRDTs de Estado (CvRDTs – State-based)

CRDTs baseados em estado propagam snapshots completos entre réplicas. Cada nó mantém um estado monotonicamente crescente, e a função de merge é definida como um operador de join em um semilattice parcialmente ordenado. A convergência é garantida porque o merge é matematicamente idempotente, comutativo e associativo, permitindo sincronização via mecanismos simples como anti-entropy ou gossip.

CRDTs Operacionais (CmRDTs – Operation-based)

CRDTs operacionais disseminam apenas operações incrementais, reduzindo overhead de rede. Nesse modelo, pressupõe-se entrega confiável e causal das mensagens, frequentemente implementada com vetores de versão ou mecanismos happens-before. A correção depende de que cada operação seja intrinsecamente comutativa ou transformada de forma que preserve invariantes semânticos globais (BURCKHARDT et al., 2014).

Propriedades Formais

Ambas as categorias compartilham garantias essenciais:

• Convergência: todas as réplicas atingem o mesmo estado após propagação completa.
• Monotonicidade: estados evoluem apenas em direção ao join do semilattice.
• Tolerância a concorrência: operações paralelas não geram conflitos.
• Ausência de coordenação global: não há dependência de locks distribuídos ou consenso síncrono.

Aplicações

CRDTs são amplamente empregados em sistemas colaborativos, plataformas distribuídas e aplicações offline-first. Editores colaborativos, bancos de dados geo-replicados e plataformas de mensageria utilizam CRDTs para permitir atualizações concorrentes mantendo coerência lógica. Um exemplo clássico são editores colaborativos, nos quais múltiplos usuários modificam documentos simultaneamente sem conflitos estruturais (KLEPPMANN; BERESFORD, 2017).

Implementação em C# (PN-Counter – CRDT Formal)

Abaixo está um exemplo simplificado de um PN-Counter (Positive-Negative Counter), um CRDT formalmente correto, que mantém contadores independentes por réplica e realiza merge via máximo por nó.

public class PNCounter
{
    private readonly Dictionary<string, int> _increments = new();
    private readonly Dictionary<string, int> _decrements = new();
    private readonly string _replicaId;

    public PNCounter(string replicaId)
    {
        _replicaId = replicaId;
        _increments[_replicaId] = 0;
        _decrements[_replicaId] = 0;
    }

    public void Increment() => _increments[_replicaId]++;

    public void Decrement() => _decrements[_replicaId]++;

    public int Value() => _increments.Values.Sum() - _decrements.Values.Sum();

    public void Merge(PNCounter other)
    {
        foreach (var kv in other._increments)
            _increments[kv.Key] = Math.Max(_increments.GetValueOrDefault(kv.Key), kv.Value);

        foreach (var kv in other._decrements)
            _decrements[kv.Key] = Math.Max(_decrements.GetValueOrDefault(kv.Key), kv.Value);
    }
}

Comparação com Go

Go é frequentemente adotada em implementações de CRDTs devido ao suporte nativo à concorrência e ao modelo leve de goroutines, favorecendo arquiteturas baseadas em gossip e replicação assíncrona.

type PNCounter struct {
    inc map[string]int
    dec map[string]int
    id  string
}

func NewPNCounter(id string) *PNCounter {
    return &PNCounter{
        inc: map[string]int{id: 0},
        dec: map[string]int{id: 0},
        id:  id,
    }
}

func (c *PNCounter) Increment() { c.inc[c.id]++ }
func (c *PNCounter) Decrement() { c.dec[c.id]++ }

func (c *PNCounter) Value() int {
    sum := 0
    for _, v := range c.inc { sum += v }
    for _, v := range c.dec { sum -= v }
    return sum
}

func (c *PNCounter) Merge(o *PNCounter) {
    for k, v := range o.inc {
        if c.inc[k] < v { c.inc[k] = v }
    }
    for k, v := range o.dec {
        if c.dec[k] < v { c.dec[k] = v }
    }
}

Casos de Uso

• Colaboração em tempo real: editores distribuídos e whiteboards.
• Sistemas offline-first: sincronização posterior sem conflitos.
• Plataformas geo-replicadas: bancos de dados distribuídos e caches globais.
• Telemetria e contadores distribuídos: métricas agregadas sem coordenação.

Conclusão

Do ponto de vista arquitetural, CRDTs deslocam a complexidade do controle de consistência do plano operacional para o plano matemático do modelo de dados, simplificando significativamente a engenharia de sistemas geo-replicados e aplicações colaborativas. Essa abordagem possibilita arquiteturas mais resilientes, alinhadas aos princípios de disponibilidade contínua e tolerância a falhas descritos pelo teorema CAP, ao mesmo tempo em que preserva invariantes semânticos essenciais.

Entretanto, a adoção de CRDTs exige rigor conceitual: implementações ingênuas podem violar propriedades formais e comprometer a convergência. A correta modelagem, como exemplificado pelo uso de PN-Counters, semilattices e merges monotônicos, é indispensável para garantir Strong Eventual Consistency. Além disso, aspectos como causalidade, granularidade de estado e custo de sincronização devem ser cuidadosamente avaliados conforme o domínio da aplicação.

Referências

SHAPIRO, M. et al. Conflict-Free Replicated Data Types. Stabilization, Safety, and Security of Distributed Systems, Springer, 2011.

BURCKHARDT, S. et al. Replicated Data Types: Specification, Verification, Optimality. POPL, 2014.

KLEPPMANN, M.; BERESFORD, A. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems, 2017.