akka/akka-core

Provide a 'tree' CRDT type

Open

#30,753 opened on Oct 6, 2021

View on GitHub
 (0 comments) (0 reactions) (0 assignees)Scala (13,277 stars) (3,547 forks)batch import
help wantedt:distributed-data

Description

It is already possible to distribute 'trees' in Distributed Data CRDT's by encoding them into the generic ORMap data type. However, that may lead to surprising effects when you encode a 'move' operation as multiple updates of the map: since those updates are distributed independently (and conflicts in those updates are resolved independently), you might end up with a Map that doesn't encode the tree you expected. To avoid such problems, we might provide a Tree CRDT data type that has an explicit 'move' operation, so conflicts involving those can be handled while keeping the tree structure intact.

https://martin.kleppmann.com/papers/move-op.pdf might be interesting inspiration.

Contributor guide

Tech stack
scala
Domain
data
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
fresh
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
needs investigation
Prerequisites
Understanding of CRDTsScala programmingDistributed systems concepts
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
20
Research direction
Review the referenced paper by Martin Kleppmann on move operations in CRDTs. Investigate how the existing ORMap type is implemented in Akka and consider how a specialized Tree CRDT could be added. The implementation would need to handle move operations atomically to avoid inconsistencies. Start by examining the current CRDT types in the Akka codebase, such as ORMap, and evaluate the design space.