MergeTreeDeltaType.MOVE

[kevindiclemente]

Feature

Is your feature request related to a problem? Please describe.
The scenario is when you are rendering an object that is paired with state that does not live in fluid due to application complexity (you need to synchronize order and some metadata but not all of a data type in its entirety), if you execute a 'move' operation today you have to do so by 'removing' and then 'inserting', or using 'cut' then 'paste', but the client events are triggered in a basic way (MergeTreeDeltaType.REMOVE then MergeTreeDeltaType.INSERT), but these events don't provide you with the information that the object is going to be inserted later at the time of remove.

This causes client-side complexity where you don't want to get rendering data that lives outside of fluid to get lost, however there are no MergeTreeDeltaType data types that can indicate an object should be preserved, since the only supported operations are 'insert' and 'remove'.

Take these two objects: SharedObjectSequence<Foo> and FooWithRenderingData[].

Where interface Foo { uniqueId: string; }; is JSON Serializable.
and interface FooWithRenderingData implements Foo { complexData: ComplexRenderingData };

When you have a SharedObjectSequence with [A B C D], and you need to move object B to the end of the list, to get [A C D B], how can you have the code that implements the SequenceDeltaEvent observe the events in such a way it can simply update the FooWithRenderingData list with a move operation on the underlying objects? Today there is no simple way to accomplish this task.

Describe the solution you'd like
Adding a MergeTreeDeltaType.MOVE datatype that can simply still be a remove and insert on the backend, but abstracted away from the client in a way they receive both events across clients don't receive REMOVE then INSERT events and instead they receive a single MergeTreeDeltaType.MOVE event. (Its ok that to move we remove then insert, but its not OK that the client doesnt understand this -- so on the backend it could remove+insert just without firing the event, thus a new event could be fired instead to describe the change in a single Delta event)

Existing work
not aware of any

Describe alternatives you've considered
One option is I may be forced to switch to using SharedObjectSequence<string> for a list of IDs for the object, and then storing the actual objects in a SharedMap that maps the ID to Foo, and not rely on the SharedObjectSequence to indicate when an object is removed or inserted, and isntead only use it for ordering, and use the SharedMap to know when a new object is truely inserted or removed.

Another option is I could store metadata by placing the object Foo through MergeTreeDeltaType.ANNOTATION or using a SharedCell and add a new entry on the object to indicate on the next time the object is 'removed from the list' it should instead be 'held onto until reinserted'... but this is not straight forward and puts the client in a very bug-prone state. The 'complex data' is pointers to native memory objects that should be cleaned up on remove, so adding this metadata can stop me from cleaning them up during the 'remove' operation, however this is now a state with a cause for memory leaks (hence the alternative or work with what I have is not really a healthy state).

Additional context

Thanks!

[tylerbutler]

@pleath @anthony-murphy Any input on this? Is this a use-case that Tree would address?

[anthony-murphy]

In general sequences are not content aware, and it's not possible to implement something like move without content awareness being added to sequences. Without content awareness there is no way to know that the objec being remove than inserted is the same object. Implementing this would be a substantial change to the underlying data model.

As @tylerbutler suggests, our tree dds should better support a scenario like this, but those are not ready for production today. @DLehenbauer has more details there.

In general, I usually dissuade people from using sequence beside shared string, as the behaviors are frequently non-intuitive for just this type of issue. Can you share more details on your usage of SharedObjectSequence, specifically I'm trying to understand what propeties are needed for your scenario? is it just insertion order? Much of the same behavior, but with better semantics can be replicated using a SharedMap

[kevindiclemente]

@anthony-murphy current implementation only uses a sharedmap, I'm trying sharedobjectsequence because coding against the sharedmap for an ordered sequence has not been the best experiance and introduces a lot of code bloat, maintly because the concept of 'insertion' into an existing list highly desirable, because then the client can replay say "insert object X at index Y" into another datatype that mirrors the contents in the fluid object. Without insert, it requires doing a lot bloat code on both the fluid side and the mirrored object side to simply move indexes around. When using shared map, the same notion of ordering doesnt exist, so theres no 'insert at object x', instead there has to be a large amount of churn in the data structures to 'increment every index by 1'. The main reason i'm exploring this is based on my experiance with sharedmap so far, coupled with guidance at: https://fluidframework.com/docs/data-structures/overview/ Storing arrays, lists, or logs in a key-value entry may lead to unexpected behavior because users can’t collaboratively modify parts of one entry. Try storing the array or list data in a SharedSequence or SharedInk. (which I have found to be true). Will tree dds provide ordering/insert etc? I can do with a hacky implementation for now if the future answer is a new DDS. If this isnt enough details on my scenario, feel free to let me know.

[anthony-murphy]

@DLehenbauer should be able to answer the question about tree.

A technique that i'd recommend when using map, is to not use an integer, but a double. Think of this as a sortkey rather than an index.

On insert, if between two elements, set the sort key to a number between the other two element's sort keys. if at the end set the sort key to some number higher than all other sort keys.

then on all clients you just keep an sorted list of elements based on sort key, and move things around as their sort keys change

You will also need invariant based break tie logic, so if two elements get the same id, you break the tie based on this invariant. Alphabetical based on item will do the trick here. you'll only hit conflict if two sperate clients move an item to the same position without seeing the others change. this should be rare, and letting the user fix the order if they don't like the result should be fine, as they haven't expressed intent as neither knew about the other.

[DLehenbauer]

Yep, the tree DDS preserves moves:

• The moved node retains its identity
• Concurrent moves do not lose or duplicate nodes (ditto for undo/redo).

How we communicate the change to clients is an interesting question that @yann-achard is working on, but we're committed to ensuring clients can recognize moved nodes vs. insertion of new content.

[kevindiclemente]

tree DDS sounds like what i want if its sorted... OK i can do with a hacky implementation for now and then will move to tree DDS -- do you have a work item tracking release date i can follow?

[tylerbutler]

tree DDS sounds like what i want if its sorted... OK i can do with a hacky implementation for now and then will move to tree DDS -- do you have a work item tracking release date i can follow?

If you take this approach, what expectations do you have around migrating data from your temp solution to Tree? Will you have data that needs to be "upgraded?" Or is your Fluid data temporary?

[kevindiclemente]

All data besides presence is persisted data, looking like we will have to write migration/upgrade logic. Expectations are that migration is going to be an annoying tax.

[ghost]

This issue has been automatically marked as stale because it has had no activity for 180 days. It will be closed if no further activity occurs within 8 days of this comment. Thank you for your contributions to Fluid Framework!