Incorrect CRDT Merge direction #1066
Assignees
Labels
area/crdt
Related to the (Merkle) CRDT system
priority/high
refactor
This issue specific to or requires *notable* refactoring of existing codebases and components
Milestone
Comments
jsimnz
added
area/crdt
|
Ping John when working on this. |
fredcarle
added a commit
that referenced
this issue
Nov 1, 2023
## Relevant issue(s) Resolves #1066 ## Description This PR change the CRDT merge direction. Originally, when an update arrived over the P2P network, each block was added to the DAG store and merged into the datastore in the order that they were received (newest to oldest block). With this update, we start my receiving all blocks up to the version that we currently have (or until we reach the root) and then we apply the merge from oldest to newest block. This will enable more CRDT types to be added.
shahzadlone
pushed a commit
to shahzadlone/defradb
that referenced
this issue
Feb 23, 2024
## Relevant issue(s) Resolves sourcenetwork#1066 ## Description This PR change the CRDT merge direction. Originally, when an update arrived over the P2P network, each block was added to the DAG store and merged into the datastore in the order that they were received (newest to oldest block). With this update, we start my receiving all blocks up to the version that we currently have (or until we reach the root) and then we apply the merge from oldest to newest block. This will enable more CRDT types to be added.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
At the moment we merge CRDT delta state starting from the
HEADand working backwards through the DAG, "merging" along the way. This is technically wrong, as it merges state backward to how its created.However, the database still works because the primary CRDT type we use is the
LWWRegister. Registers technically only care about the "last" value that is written, so if I set "name" to "Alice" then to "Bob", in reality, the in between state of "Alice" doesn't really matter that much.However, the discussions related to #1064 its clear that this will breakdown for other CRDT types. Specifically this will already break down for
CompositeCRDTs, where the current operations are onlyCREATE, andUPDATEeffectively. But we want to introduce a new operationDELETE, which is order dependent in which direction we "merge".This will be necessary for #101 as well, since they'll likely be order dependant types.
The text was updated successfully, but these errors were encountered: