search

dexie / Dexie.js

A Minimalistic Wrapper for IndexedDB
https://dexie.org
Apache License 2.0
11.34k stars 640 forks source link

Is Dexie.Syncable using OT? #587

Open cfilipov opened 6 years ago

cfilipov commented 6 years ago

From the looks of it, I'm guessing it's doing operational transforms (OT). I didn't see this mentioned anywhere in the docs or code so just wanted to confirm I understand correctly.

nponiros commented 6 years ago

Hmm this sounds correct, at least from what I understand by reading a bit about operational transforms. But this only holds true for dexie syncable itself. What the server does with the data is another issue. There are 2 server implementations that I know of that are open source. Both consider the last change when changing the same object from two different clients so data might get lost there. At least this is what I remember about the implementations. I would have to check the code to be sure.

Maybe if you give me more info about OT, I could give you some more information.

cfilipov commented 6 years ago

I'm no expert in distributed systems, I trust your understanding of OT is likely better than mine.

I ask because you mention the possibility of making use of CRDTs for conflict-free sync, so this had me wondering what the current implementation was doing. I dug around the code but didn't see any specific algorithm mentioned.

nponiros commented 6 years ago

I haven't worked on the code for quite some time but this is what I remember: Dexie-Syncable records every ADD/UPDATE/DELETE operation. When it is time to send the operations to the server the operations are firstly merged. I guess merge could be seen as OT. For each operation we check the ID and merge all operations which are defined for that ID. For example for the ID 1 we might have an ADD, UPDATE, UPDATE then those 3 are merged into 1 ADD operation which contains the two UPDATES. UPDATES are defined on a property level. Changing a property in an object is an UPDATE but we don't record what exactly changed in the property just the the property was changed and the new value.

Now the server comes in play. There is an official server in the Dexie examples and one that I wrote. Both basically work the same. They record all operations those got from the various dexie clients. Everytime we get a new set of operations, the server tries to merge the operations. Now if you have for example two UPDATE operations for one ID and both change the same property, then the last change would win. I'm not sure if this type of conflict resolution is allowed in OT. After the server is done all the new operations are sent back to the client.

So this is how dexie syncable + the server implementations which I know of work. Now I well let you decide if this could be considered OT or not.