5 ms·
I believe their counter only works when they have 2 replicas: 0 / \ +1 / \ +2 / \ 1 2 \ / \ /
by Jyaif 7y ago
I believe their counter only works when they have 2 replicas:
0
/ \
+1 / \ +2
/ \
1 2
\ /
\ /
\ /
3 <= correct result
With 3 replicas it breaks apart:
0
/|\
/ | \
/ | \
/ | \
/ | \
+1 / |+100 \ +2
/ | \
1 100 2
\ / \ /
\ / \ /
\ / \ /
101 102
\ /
\ /
\ /
203 <= incorrect result, 100 is accounted for twice.
It is accounted for twice because the lowest
common ancestor is '0'.
My team solved that problem by creating virtual common ancestors. This is similar to what git does in some cases.
- cousin_it 7y agoWait, that doesn't look right. Why does 100 have two children? It seems to me that 1 should get merged with 100 to end up with 101, then that should be merged with 2 to end up with 103.
- Jyaif 7y agoThis is a distributed system. You can have some replica that has 100, merge with an other replica and get 101. Then an other replica that also had the same 100 merge with an other replica and get 102. Then when 101 and 102 merge, the lowest common ancestor is still 0, so you get 203.
- cousin_it 7y agoAh I see, sorry, that makes sense.
- deleted 7y ago[deleted]
- contravariant 7y agoIn this case 100 is the LCA isn't it? Then you'd end up with 100 + (101 - 100) + (102 - 100) = 103, which is correct.
- Jyaif 7y agoYes, 100 is the LCA. The problem I should have started with is that regular LCAs are not useable for conflict resolution because there can be multiple different LCAs. For example, in the graph at https://cs.stackexchange.com/questions/72538/lowest-single-common-ancestor-in-a-directed-acyclic-graph https://cs.stackexchange.com/questions/72538/lowest-single-c... which LCA do you use to merge 3 and 4? So you have to use some sort of "unique LCA", which is 0 in the example I gave. But even that does not work as I showed in 2nd example.
- deleted 7y ago[deleted]
- contravariant 7y agoAfter looking at it for a bit I've determined that it's not so much a problem that you can't pick a unique LCA (you just need a guarantee that either works). However you run into problems when you merge two nodes that already contain some merges. Consider the following example: 0 /\ +1 / \ +2 / \ 1 2 | \ / | | \/ | | /\ | | / \ | 3 3 | \ / | | \/ | | /\ | | / \ | ? ? Here you've got two choices for LCA (which aren't equivalent but that aside), both will give you the wrong answer. As the correct answer should obviously be 3 as only 1 and 2 were ever added to the counter, exactly once. Basically the problem is that the merge operation isn't idempotent, hence it doesn't define a semilattice, which seems to be what you want if you want to ensure consistency even over distributed systems. They could have easily fixed this by picking a better merge operation such as a union or maximum, but it's not encouraging when someone picks an illustrative example that doesn't quite work.
- infinity0 7y ago