-
Movable tree CRDTs and Loro's implementation
-
Contexto
- Em sistemas distribuídos e softwares colaborativos, gerenciar relações hierárquicas é algo complexo
- Ao modelar movimentos combinando exclusão e inserção em uma estrutura de dados, é difícil resolver conflitos e atender às expectativas dos usuários
- Por exemplo, se o mesmo nó for movido simultaneamente para pais diferentes, podem surgir nós duplicados com o mesmo conteúdo
-
Conflitos em árvores movíveis
- Principais operações de uma árvore movível: criar, excluir e mover
- Conflitos que podem ocorrer ao sincronizar operações concorrentes:
- o mesmo nó é excluído e movido
- o mesmo nó é movido para baixo de nós diferentes
- outros nós são movidos, gerando um ciclo
- um nó descendente é movido enquanto um nó ancestral é excluído
-
Exclusão e movimento do mesmo nó
- Relativamente fácil de resolver
- Dependendo do timestamp em sistemas distribuídos ou dos requisitos específicos da aplicação, uma das operações é aplicada e a outra é ignorada
-
Mover o mesmo nó para pais diferentes
- Mesclar operações de movimento concorrentes é mais complexo
- Dependendo da aplicação, diferentes abordagens podem ser adotadas:
- excluir o nó e criar uma cópia sob outro nó pai
- permitir que o nó fique ligado a dois pais (geralmente isso não é permitido)
- ordenar todas as operações e aplicá-las sequencialmente
-
Geração de ciclos pelo movimento de nós diferentes
- Resolver ciclos causados por operações de movimento concorrentes é complexo
- Há várias soluções:
- gerar um erro
- renderizar os nós em ciclo em uma área especial de "timeout"
- processar as operações de movimento no servidor
- usar ordenação topológica
- ocultar a aresta que causa o ciclo
-
Exclusão de nó ancestral e movimento de nó descendente
- O movimento de um nó descendente durante a exclusão de um ancestral pode passar facilmente despercebido
- Excluir diretamente todos os nós descendentes pode ser interpretado como perda de dados
-
Como aplicativos populares tratam conflitos
- Dropbox: tratava a movimentação de arquivos como exclusão seguida de criação, mas isso traz risco de perda de dados
- Figma: um servidor central detecta ciclos e rejeita a operação para manter a consistência
-
CRDTs de árvore movível
- Uso de CRDTs em vez de soluções centralizadas
- Os algoritmos iniciais baseados em CRDT eram difíceis de implementar e tinham grande overhead de armazenamento
- Com otimizações contínuas, alguns algoritmos de sincronização de árvores baseados em CRDT tornaram-se adequados para ambientes de produção
-
Operações de movimento de alta disponibilidade para árvores replicadas
- As três operações da árvore (criar, excluir e mover) são unificadas como operações de movimento
- A operação de movimento é definida como
Move t p m c
- A exclusão de nós é tratada movendo-os para o nó
TRASH
-
Timestamps lógicos globalmente ordenados
- Uso de timestamps de Lamport para determinar a ordem causal dos eventos em sistemas distribuídos
- Números menores indicam eventos mais antigos
-
Aplicação de operações remotas
- A segurança de uma operação depende do estado da árvore no momento da aplicação
- Ao processar atualizações remotas, as operações mais recentes são desfeitas, a nova operação é inserida e, em seguida, as operações desfeitas são reaplicadas
-
CRDT: hierarquia de árvore mutável
- Cada nó acompanha todos os nós pais históricos e recebe contadores
- Se surgir um ciclo durante a sincronização, o nó é reconectado ao nó pai histórico mais próximo
-
Implementação de CRDTs de árvore movível na Loro
- Implementa o algoritmo de Martin Kleppmann para oferecer alto desempenho
- Integra o algoritmo
Fractional Index para permitir a ordenação de nós filhos
-
Conflitos potenciais na ordenação de nós filhos
- Ao inserir vários nós na mesma posição, pode ser atribuído o mesmo
Fractional Index
PeerID é usado para determinar a ordem relativa entre Fractional Index idênticos
-
Implementação e tamanho da codificação
Fractional Index fornece a ordem dos nós- O tamanho da codificação pode exigir bytes adicionais no pior caso, mas isso é raro
-
Trabalhos relacionados
- Além de
Fractional Index, também existem CRDTs de lista movível
Fractional Index é simples de implementar e útil quando apenas a ordem relativa é necessária
-
Benchmark
- Foi realizado um benchmark de desempenho da implementação de árvore movível da Loro
- Há suporte para colaboração em tempo real e checkout fluido de versões históricas
-
Resumo
- Apresenta a dificuldade de implementar CRDTs de árvore movível e dois algoritmos inovadores
- A Loro integra o algoritmo de Martin Kleppmann com
Fractional Index para atender a vários cenários de aplicação
-
Resumo do GN⁺
- CRDTs de árvore movível desempenham um papel importante na gestão de estruturas hierárquicas de dados em sistemas distribuídos
- A Loro oferece alto desempenho e resolução eficiente de conflitos, sendo adequada para aplicações de colaboração em tempo real
- Usa
Fractional Index para resolver o problema de ordenação de nós filhos
- Outros projetos com funcionalidades semelhantes incluem Figma e Dropbox
1 comentários
Comentários do Hacker News
Está desenvolvendo um novo editor multiplayer
insmov(mover ou inserir)Disponibiliza a React Table Library como código aberto
Pede conselhos
Ao trabalhar com conteúdo de texto formatado como no Google Docs/Zoho Writer, é necessário manipular árvores
Pergunta se existe algum CRDT prático para aplicações densas em dados, como imagens (pixels) e modelos 3D
Acha que o primeiro parágrafo soa como a voz do ChatGPT