fthomas / fthomas/crjdt

Resolve conflicts of MapNode with duplicate key caused by concurrent update to the same key with different type values other than primitive

Open
#14 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Scala
Stars
298
Forks
18
PR merge metrics
No merged PRs in 30d

Description

Document state to JSON conversion introduced from #12 does not handle duplicate key as reported at [this comment](https://github.com/fthomas/crjdt/pull/12#issuecomment-270645358).

Duplicate key can be made when MapNode is updated with different type values other than primitive.

For example, concurrently updating to the same key "key" with object and string
```scala
val p1 = p0
.applyCmd(doc.downField("key") := `{}`)
.applyCmd(doc.downField("key").downField("key2") := "D")
val q1 = q0.applyCmd(doc.downField("key") := "C")
merge(p1, q1)
```

results in duplicate keys, RegT(StrK(key)) and MapT(StrK(key)).

```
MapNode(
Map(
MapT(DocK) -> MapNode(
Map(
RegT(StrK(key)) -> RegNode(Map(Id(2,q) -> Str(C))),
MapT(StrK(key)) -> MapNode(Map(RegT(StrK(key2)) -> RegNode(Map(Id(3,p) -> Str(D)))),Map(StrK(key2) -> Set(Id(3,p))))
),
Map(StrK(key) -> Set(Id(2,p), Id(3,p), Id(2,q)))
)
),
Map(DocK -> Set(Id(1,p), Id(2,p), Id(3,p), Id(2,q)))
)
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the document state to JSON conversion introduced from #12 and trace how MapNode handles concurrent updates during merge. Reproduce the Scala example with object and string values at the same key, then verify that the resulting state no longer contains both RegT(StrK(key)) and MapT(StrK(key)).

Written by the indexing model from the issue text.

Assessment

Tech stack
scala
Domain
distributed-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.