Add random jitter to selected indexes? #14
Comments
|
You can also just allow conflicts and repair them iff someone tries to insert between conflicting items. You'd have to of course |
|
Yeah I think we discovered this ourselves too. There are a number of patterns to deal with conflicts and I'm not sure which is best, I keep oscillating between options :). |
|
Would it be possible to add support for random jitter as an option? |
|
@quolpr if you are still looking, this seems promising: https://github.com/TMeerhof/fractional-indexing-jittered. While not a fork, it is apparently inspired by this package. |
Merged
6 tasks
github-merge-queue bot
pushed a commit
to tldraw/tldraw
that referenced
this issue
Jul 31, 2024
…licts (#4312) We saw several duplicates related to ungrouping of shapes and fractional indexes having conflicts — it's hard to repro but the theory is that it has to do (mainly, but not always) with multiplayer conflicts (especially if you're offline for a while, you come back online and then you both have the same indices). However, we have seen this in single-player mode too. ### Here are some of the related bugs: - #3932 - #4126 - #4210 As I looked into the issue, and looked at the original code it led me to: - this issue on the repo: rocicorp/fractional-indexing#14 - which led to this article: https://madebyevan.com/algos/crdt-fractional-indexing/ - and this repo implementing it: https://github.com/TMeerhof/fractional-indexing-jittered So! This PR now switches tldraw to using the "jittered" version of fractional indexing to help with these conflicts. It still doesn't satisfy my curiosity on why we see these issues in single-player mode (when ungrouping sometimes). But, this should help alleviate this problem in general, whether single or multiplayer. As noted in the jitter repo: > The default character set has a chance of roughly one in 47.000 to generate the same key for the same input at the cost of making the keys 3 characters longer on average. Feels definitely like a good tradeoff! I know @SomeHats mentioned about just allowing for these conflicts but then it sounded like from reading other people running into this, we'd have to repair things when someone tried to insert yet another thing between the conflicting items. ### Reference: - Original fractional index article by dgreensp: https://observablehq.com/@dgreensp/implementing-fractional-indexing ### Change type - [x] `bugfix` - [ ] `improvement` - [ ] `feature` - [ ] `api` - [ ] `other` ### Test plan - [x] Updated the unit tests, it uses the non-jitter version for testability ### Release notes - Shape ordering: upgrade fractional indexing to use jitter, avoid conflicts
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See https://madebyevan.com/algos/crdt-fractional-indexing/
I wonder if there is a principled way to choose the amount of jitter such that collisions are ~impossible.
The text was updated successfully, but these errors were encountered: