Hi there!
So for the past week I've been working on collaborative document editing and it's now available.
Making changes to a document at the same time as other people sounds like a nice thing to do, but what happens under the hood is actually pretty complicated. Let me explain!
As you may know, network communications are far from instant, the data takes time to reach the server and come back to the client. (This delay is called the round-trip time or "ping").
The client makes changes to the document as you type, and sends them to the server, which will dispatch them to everyone currently watching to the document. The change will be a simple packet containing its location in the document, and what kind of change happened (inserting a character, removing one, etc.)
But what happens if two people make changes at the same time?Well the server will receive one of them first, will apply it, and notify everyone. Then it will receive the second one (which was crafted and sent before the first one was applied!) and will try to apply it.
But hold on, the change is not valid anymore! It is based on the previous document state. As such, it must be "rebased" on the new document state. This is called "operational transform" and guess what, it's a whole field of research! Let's here a tale of two people editing a document:
Player A and
Player B are writing a story together. Their (very short) story currently goes as following:
Bob was walking down the street(Let's call this document state "state 123".)Player A wants to change "Bob" to "Jim". She starts by erasing the last letter of Bob:
Bo was walking down the streetThis generates a change which can be described as such (indices start at 0):
Remove character at index 2At the exact same time,
Player B wants to start a new sentence. She starts by adding a full stop at the end of the document:
Bob was walking down the street.Her change is encoded as:
Insert character "." at index 31Both players send their changes to the server, so that it updates the document.
Meanwhile, the server is happily sitting when suddenly it receives a message from
Player A! The message says:
Based on document state 123, remove character at index 2Without even a hint of hesitation, the server complies and updates its copy of the document, calling it "
state 124" and broadcasts the change to everyone. Having done a good job, the server wants to sit back and have a cookie, but another message comes, this time from
Player B. Reluctantly, the server opens it. It reads:
Based on document state 123, insert character "." at index 31"This is old news!", comments the server, "State 123 is so yesterday!"
(At this point, I should probably point out that the server didn't sleep well and is in kind of in a bad mood.)The server looks at the changes between
state 123 and
state 124, and realize that he has to adjust the newer change. Its
magic rule book says the following:
When an insertion happens after a deletion located before it, the insertion should move back by one character"So, let's see", mumbles the server as it looks at the changes.
Insert character "." at index 31 30"Yeah, that should do it!". And just like that, document
state 125 is created! The server broadcasts the new change and everyone is happy, ever after.
That should give a basic idea of what's involved with Operational Transform and real-time concurrent editing. There's a lot more to it, of course, and if you're interested, you should check out the
OT faq which is a good reference on the subject.
Now that I'm done with documents,
the next major CraftStudio update will add scenes & scripting! Exciting stuff... stay tuned!
Community
