Transfomation side ("left", "right")

[TheDominik]

Hey,

I have been working on a new document type. But I found something which is a little bit odd. It might be an issue or I need some clarification or explanation for it. I hope you can help me out. So I had an issue that the server transformed some messages differently than the clients and I think I tracked it down to 2 classes. The first one is the file ot.js line 143 – 147. Here the transform method will be called with op.op, appliedop and side = left. For me that means the side “pointer” points on the operation that has not been executed yet. Basically it’s still pending.

  try {
      op.op = type.transform(op.op, appliedOp.op, 'left');
    } catch (err) {
      return err;
    }

On the other side there is the client, which also has to call the transform method, but here the pointer points the other way around, see file doc.js, line 479 – 488. The transform in line 484 and 485 will be executed with client.op, server.op and left. If I compare it to the ot.js file, I would say that the client.op has not been executed yet. In my opinion the client.op has been executed, since it is on the client right? I assume that the client is not sending an operation to the server and then waiting for a response. I assume that the client will execute the changes locally and then send it to the server. In case that there is a transformation needed, the client should call (client.op, server.op, “right”) since the client.op would be the applied one (if you compare it to the ot.js), right?

if (client.type.transformX) {
    var result = client.type.transformX(client.op, server.op);
    client.op = result[0];
    server.op = result[1];
  } else {
    var clientOp = client.type.transform(client.op, server.op, 'left');
    var serverOp = client.type.transform(server.op, client.op, 'right');
    client.op = clientOp;
    server.op = serverOp;
  }

It would be great if you could tell me if I am on the wrong way or if that is an issue. The order is in my protocol essential and cannot be executed the other way around. Best Regards, Dom

[DetweilerRyan]

Hi @TheDominik, I've been using custom Operational Transform types in production at Retrium for almost three years now and I'm always happy to hear of new use cases for custom OT types. But first, before answering your question, I want to caution you against rolling your own custom OT types. The OT algorithms are complex, counter intuitive, and come with little to no documentation or best practices. You will not find answers to your questions on StackOverflow nor will you find much guidance from others. Building, maintaining and improving your custom OT types creates some serious technical debt so the justification must be worth the cost. I strongly urge you to consider using the built in generic JSON OT Type that the fine people at ShareDB painstakingly crafted. But if the justification is sufficient for rolling your own OT types then the payoff is an unparalleled user experience.

( Stepping down from my soap box )

The transform function is the bread and butter of the OT algorithm and you must fully understand it in order to implement your own OT types. Thankfully the transform method is documented here.

transform(op1, op2, side) -> op1': Transform op1 by op2. Return the new op1. Side is either 'left' or 'right'. It exists to break ties, for example if two operations insert at the same position in a string. Both op1 and op2 must not be modified by transform. Transform must conform to Transform Property 1. That is, apply(apply(snapshot, op1), transform(op2, op1, 'left')) == apply(apply(snapshot, op2), transform(op1, op2, 'right')).

The equation at the end of the above quote is all you need to fully understand how transform works, study it. If the equation is ever not true for any combination of snapshot, op1, or op2 then the snapshot on the client and the snapshot on the server will diverge and fail to be eventually consistent. Here are a few pointers to get you going if you choose to go down this road:

• Notice how that the transform function ( unlike the apply function ) does not have access to the state. This means, every operation must contain all of the properties necessary to identify and resolve the conflict between two operations. For instance, if you have an operation that sets the value of a property the operation must not only contain the value that is being set but also the current value of the property.
• The transform is not dependent on whether or not it is executing on the client or the server. All it needs to know is which operation should win if there is a conflict. The transform function knows this via the side property.
• You need to implement transform for every single combination of operations. If you have N operations then you have N^2 possible conflicts. At Retrium one of our custom OT types has 39 operations. That's a lot of conflict!

I hope this helps. Good luck.

[TheDominik]

Hey @DetweilerRyan thanks for your reply. I am aware of that and the JSON protocol is not sufficient for me. I already have implemented my ottype, which works pretty well if I change either the part in the ot.js or the part in doc.js file (switching the sides). That is the reason why I have the question if the ot.js and the doc.js is implemented correctly. For me it seems not to be correct (see my first post). Since the sides seems to be odd. On the server side it is pointing to the non-applied operation and on client side it is pointing to the applied operation. Therefore the transformation could be different because -> Transform (applied, non-applied, ‘right’) != Transform(applied, non-applied, ‘left’).

[gkubisa]

Hi @TheDominik,

TL;DR I think the current implementation is correct.

Assume we have 2 conflicting operations, Oa and Ob, sent by clients Ca and Cb respectively.

Here's what happens step by step:

1. Ca applies Oa and sends it to the server.
2. Cb applies Ob and sends it to the server.
3. The server applies Oa first - arbitrary choice.
4. The server transforms Ob against Oa. Ob' = transform(Ob, Oa, 'left') ot.js:144.
5. The server applies Ob'.
6. The server acknowledges Oa to Ca.
7. The server sends Ob' to Ca.
8. Ca applies Ob'.
9. The server sends Oa to Cb.
10. Cb transforms Ob against Oa. Ob' = transform(Ob, Oa, 'left') doc.js:484. It is the same transformation as the server performed above. Keep in mind that Cb already applied Ob. Ob' is calculated only in case it has to be resubmitted to the server for any reason. Ob' is the same on the server and on the client!
11. Cb transforms Oa against Ob. Oa' = transform(Oa, Ob, 'right') doc.js:485.
12. Cb applies Oa'.
13. The server acknowledges Ob to Cb.

Takeaways:

• Ob' = transform(Ob, Oa, 'left') is performed on both Cb and the server, so Ob' is guaranteed to be the same - I think this is what you questioned.
• The server applies Oa and Ob', Ca applies Oa and Ob', Cb applies Ob and Oa'. So, both clients and the server are guaranteed to end up with the same snapshot, assuming that the apply and transform functions are implemented correctly, see https://github.com/ottypes/docs.
• I'll also mention just in case, you can reverse the meaning of the side parameter in your custom OT type - the bottom line is that apply(apply(snapshot, op1), transform(op2, op1, 'left')) == apply(apply(snapshot, op2), transform(op1, op2, 'right')) is always true.