search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 467 forks source link

Keeping track of most recently used items #505

Closed fo-fo closed 2 years ago

fo-fo commented 2 years ago

I've been toying around with this library for a little bit (thanks for all the great work to all contributors!), and recently started wondering what would be a proper way to track "most recently used" status of a list of items. The first idea that came to mind was to store a "last used" timestamp in each item, but I'm not sure if that would work well with conflict resolution. If I've understood correctly, if two peers would modify the "last used" field at the same time, a random of the two would get picked? In this case I'd prefer the result to always be the maximum of the two.

Another idea that came to mind was to keep a kind of a linked list or an array of the most recently used items (for example, the least recently used item would be the first item in a list, and the most recently used would be the last one). But I'm not sure if those array manipulations (that delete an item from its current position and move it to the end of the array) would merge well without possibly causing duplicates in the array.

Any ideas/pointers as to what would be a robust way to implement something like that?

ept commented 2 years ago

Hi @fo-fo, I think a linked list would get very messy when several users concurrently manipulate it, so I would recommend using the timestamp field approach. When several users concurrently update the timestamp, by default Automerge shows you one of the values arbitrarily, but you can get all of the latest values by calling Automerge.getConflicts(doc.path.to.item, 'timestampKey'). You can then take the greatest value among those conflicts and present that to the user. Please do not write back the greatest value into the document (otherwise you could end up with multiple clients in a loop repeatedly creating and resolving conflicts) — simply leave the conflict in the document, and it will be resolved the next time you need to increase the last used timestamp.

fo-fo commented 2 years ago

Thanks, that sounds like a good idea! Thanks also for the tip of not writing the resolved value back.

I was also going to ask if getConflicts is an expensive operation, but looking at the source code looks like it's a fairly straightforward lookup. I'll give this one a shot.

ept commented 2 years ago

getConflicts should be very fast – no need to worry.