O que é CRDT em Sistemas Distribuídos?
Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type
3 answers
Os CRDTs em diferentes réplicas podem divergir uns dos outros, mas no final podem ser fundidos com segurança, desde que eventualmente, um valor consistente. Em outras palavras, CRDTs têm um método de junção que é idempotente, comutativo e associativo.
As duas alternativas são equivalentes, uma pode emular a outra, mas os CRDTs baseados em operações requerem garantias adicionais do middleware de comunicação. CRDTs são usados para replicar dados através de vários computadores em uma rede, executando atualizações sem a necessidade de sincronização remota. Isso levaria a uma fusão de conflitos em sistemas usando o convencional eventual tecnologia de consistência, mas CRDTs são projetados de tal forma que os conflitos são matematicamente impossíveis. Under the constraints of the CAP theorem they provide the strongest consistency guaranties for available / partition-tolerant (AP) settings.Alguns exemplos em que são utilizados
O Riak é a biblioteca de código aberto mais popular do CRDT e é usado pela Bet365 e pelo League of Legends. Abaixo estão alguns links úteis que suportam Riak.1 - Bet365 (usa Erlang e Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf
2 - League of Legends USA a implementação Riak CRDT para o seu sistema de chat no jogo (que lida com 7,5 milhões de utilizadores concorrentes e 11 mil mensagens por segundo)
3-Roshi implementado por SoundCloud que suporta um conjunto de tempo LWW: - Post no Blog: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events
Os CRDTs usam a matemática para impor consistência através de um conjunto distribuído, sem ter que se preocupar com consenso e latência/indisponibilidade associada.
O conjunto de valores que um CRDT pode tomar a qualquer momento, vem sob a categoria de uma semi-Estrutura (especificamente uma semi-Estrutura de junção), que é um POSET (conjunto parcialmente ordenado) com uma função de limite inferior superior (LUB).
Em termos simples, um POSET é uma coleção de itens em que nem todos são comparáveis. Por exemplo, em uma matriz de pares: {(2,4), (4, 5), (2, 1), (6, 3)}, (2,4) is (4,5), but can't be compared with (6,3) (since one element is larger and the other smaller). Agora, um semi-retículo é um POSET em que dado 2 pares, mesmo que você não possa comparar os dois, você pode encontrar um elemento maior do que ambos (LUB).
Outra condição é que as actualizações deste tipo de dados tenham de aumentar, os CRDTs têm um estado monotonicamente crescente, onde os clientes nunca observam a reversão do estado.
Este artigoExcelente usa a matriz I usado acima como exemplo. Para um CRDT que mantenha esses valores, se duas réplicas estão tentando alcançar um consenso entre (4,5) e (6,3), elas podem escolher um LUB = (6,5) como consenso e atribuir ambas as réplicas a ele. Uma vez que os valores
estão a aumentar, este é um bom valor para resolver.
Soundcloud's Roshi é um bom exemplo (embora não esteja mais em desenvolvimento, parece), eles armazenam dados associados a um timestamp, onde o timestamp está obviamente aumentando. Todas as atualizações que venham com um timestamp menor ou igual do que o armazenado são descartadas, o que garante idempotência (as escritas repetidas são OK) e comutatividade (as escritas fora de ordem são ok. A comutatividade é a=b means b=a, que neste case means update1 followed by update2 is same as update2 followed by update1)
As escritas são enviadas para todos os grupos, e se certos nós não respondem devido a um problema como lentidão ou partição, espera-se que eles alcancem mais tarde através de a read-repair, o que garante que os valores convergem. A convergência pode ser alcançada através de 2 protocolos como eu mencionei acima, propagar estado ou atualizações para outras réplicas. Acho que o Roshi faz o primeiro. Como parte do read-repair, o estado de permuta das réplicas, e porque os dados aderem à propriedade semi-retículo, convergem.
PS. Sistemas que usam CRDTs são eventualmente consistentes, ou seja, adotam AP (altamente disponível e tolerante à partição) no teorema de CAP .
Um CRDT é convergente se as mesmas operações aplicadas numa sequência diferente produz (converge para) o mesmo resultado. Isto é, as operações podem ser comutadas - é um RDT comutativo. A razão pela qual as operações podem ser aplicadas em uma sequência diferente e ainda obter o mesmo resultado é que as operações são livres de conflitos.
Então CRDT significa a mesma coisa, qualquer uma das três expansões você usa-embora pessoalmente eu prefira "convergente".