Differential Synchronization

thanks for coming this talk is going to be mostly on the whiteboard so forgive me if my back is turned interrupt me for questions at any time please the more the merrier the question means you don't understand something but it also means that you still care so it's good and this talk is going out on YouTube so hold the confidential questions until the end ok differential synchronization the purpose of it is if we have multiple users all looking and all editing the same document let's say document says cat and we've got three users one two and three if we have real-time synchronization then if user one adds and s2 caps user two changes this to my cats then the S gets pushed across to here my goes back it is merged and the S goes over here and the my comes down and so everybody is always looking at close to the same text now there's always going to be some latency so note so two people may have different things on screen at any given time I mean the speed of light is going to dictate that there's at the very minimum going to be some difference but the idea is that it should very quickly resolve itself now this diagram clearly screams out peer to peer unfortunately a peer to peer doesn't work on the internet very well unless you've either got everybody in a local environment or you've got everybody highly motivated I'll let you figure out what highly-motivated is since that's not what we are interested in we want regular users be able to use this across the Internet we're not exploring peer-to-peer so this is the first fork the first path not taken where maybe peer-to-peer is the right solution for some sort of synchronization but not for ours so this is not what this talk is going to be about so this brings us down to client-server unsurprisingly so if we have a server here server is going to have its own copy of the text and connections now this actually simplifies things significantly from an algorithmic point of view because if we can get a magical synchronization system to go to happen between one client and the server's text then we're done because if this user adds the s a change has been made to this document the synchronization will move the change over and make a change to this document therefore this document has changed and therefore it should propagate some more so all you have to do is figure out how to do this portion and the rest of the network will take care of itself the only caveat is that when a change happens it must not be mirrored backwards or else you get into this wonderful state of I add an S s o s it's been added s s and as a developer I cannot tell you how many times I have turned on the system and it immediately fills up with the first keystroke those are always fun so let's go down to just looking at how to synchronize between a client and a server the simplest way as a chair here looks like I sides this room about right the simplest way to do synchronization is simply to watch the keystrokes so if the client is not client if the client types an S you're going to have an event on key press event and so you can detect the ASCII code of the character you can look at where the cursor is you can get all the information you need about what has just changed in this documentary and you can then send across a message saying we are adding an S to position 3 or something like that and this over adds it and likewise if the server change is something we just send send back a message about that quite straightforward really easy to set up the problem with this is it's divergent if there's a problem it will never recover from that problem and let me give you an example a few years ago I was planning a computer game it was a multiplayer version of asteroids something like that so you got your little ship and an asteroid here so what I did is I shot the asteroid asteroid blew up fragments went all over the place killed my opponent and I won on his computer I shot but because of some error somewhere I missed the asteroid it didn't blow up he turned around shot me he won and it shows where if you are depending on capturing every single event if you miss something you will never recover from that and you get into a state where these two users are now talking are now editing completely different documents to each other you get a butterfly effect so what we what we really need is something that's convergent getting back to more regular text editors these problems can occur quite frequently if you've got you can capture the keyboard but what about copy and paste what about selecting some text and dragging it what about yondu stack what about auto correction what about spellcheck what about drop packets there's just so many ways that you can lose the plot there are a couple of editors that use event passing or edit that I think use event passing one of them is subethaedit very successful very good editor for the Macintosh of course that's how they managed to get it to work as far as I know because the Mac API is much cleaner than say Windows win32 in my case I'm giving the worst situation because I'm trying to get this to work on a web browser and so trying to capture every single event sometimes there are just no events being fired when it change happens so event passing is great if you can nail it down but I'm going to assume that you count always nail it down another one I think is what's called the ether pad it looks like it's using event passing and the way you can tell is just by entering some text and just abusing it a little bit shaking it copy paste delete just mangling it a bit and soon enough you'll find that the other party is now looking at something different and it will never resolve itself so it's a good solution but it's not very robust okay so we are all computer programmers we know exactly how to do rebus robusta as organization systems we've all used them in source code control so we've got our client a base version version one I'll call it and server and then we've got her magical three-way merge and that hope puts version two so we start off with Cat Cat Cat client adds an S server adds my these three get funneled down freeway merge produces version two of this document which hopefully is my cats and then this gets sent back to become the new server version and the new client version thousands of people use this every day for code reviews and other stuff very robust very good system problem is it's not real time and that is a problem because if you look at what happens if you're typing here and then it does a synchronization if you type a single letter while this synchronization is in flight suddenly you can no longer use the output if you've added an exclamation mark while this is in flight what does the client do with this my cats it can't do anything with it so it has to throw this away and synchronize again later based off of version one the result of that is that as long as you're typing you are not getting any new feedback back from the server because anything that you get is going to be obsolete this only works if you are an environment where either the network and the diff speed is lightning fast and you can afford to actually block the user or if the user is willing to stop let the thing synchronize and then continue but that's not real time and exhibit an analogy of this would be driving if you had a car rare you could either drive or you could look for the windshield but not both you could drive for a little bit stop look ahead and then start driving some more and that you can imagine what the highways would be like if everybody was like that so this doesn't this works well if you're only synchronizing once every 30 seconds or something and if you see a product that synchronizes once every 30 seconds or so chances are this is what it's using but we want something that updates live every couple of seconds without needing to wait for the chickens to stop moving before we can count them so let's see how we can build an asynchronous system and this is where the differencing comes in yeah I'm leaving a gap it's a harbinger for things to come okay so we need a dip that produces some edits goes over to the patch it's off screen but that's okay it's the same thing just mirror it up see if I can that up a little bit there we go all right let's see how this system works this is simple differential synchronization it won't actually work in the real world but we'll see why a woman Cat Cat right the client types an S we then take we don't even attempt to capture the difference or capture the on key events instead if we take the clients live copy and the shadow which is the previous version take a difference between them and that yields and edit so our edit is adding an S we then take that take a copy of the service text which by the way has changed let's say the server has added some text so we take these two texts do a fuzzy patch because this does not necessarily match identically do our best effort and patch that back to s when we took our diff we also copy across what had changed so now the common shadow says cats and on the return cycle of the difference we now take the difference between the server and the shadow and so clearly what's changed is we've added my and then we copy this across my and then patch my into the client it's simple it works it's pretty reliable too this is a best-effort patch if it had failed let's take a look at what it would have happened if the s could not have been patched in so let's assume that this patch or the edits collided with each other and we couldn't patch this so we try to put an s in we can't figure it out because this has changed too much that's okay so this patch fails the server then does a sync between between the common shadow and the server and that will returns adding my and subtracting s so my comes in s goes away and we're still in sync so no matter no matter what you do to this system it's always going to come back and sync if there's if there's a memory flip and you end up with something extra here it's no problem it'll just it will propagate through you may not get what you want on the other side and there may be no wind situations but you will always end up synchronizing to a consistent state doing this the cat become the kids become something else okay so while this edit is in flight this completely changes okay so this now becomes a dog neither of these work neither these fit that's what you're assuming so the patch fails we then do a diff between here and here and the edits become remove my cats my cat and add dog and that's what we do so some somebody's going to win how you resolve differences is really a function of what you want to do when collisions happen you can try best effort you can pop up a dialog you can guess you can throw it on the floor you can give preference to one side together it doesn't really matter I don't really care about that but whether you win or lose it's always going to be consistent state and that's that's really what's critical okay there's a problem with this I dropped a packet mm-hmm I see one common shadow ah yes okay let's address that then correct that's why I said it's not going to work so that's right this is this works great if you're synchronizing between two documents on the same computer that's useful okay now you're going to start to see why I left some of space open the worrisome is it's still going to be some space over all right now we have a client shadow and a server set shuttle and we have to add another patch algorithm and patch here and cross copy across every one so we've taken that comma shadow and we split it across so now we can put a dividing line of our network here let's bring us back into a consistent state cat cat okay so same as before we add an S take the difference it's plus s we copy this difference across we now take that plus s and patch it to different places now these look similar but they're actually different this patch should patch identically and this can be and should be really really fragile because this text must be exactly what this one wants so this is a really easy patch to make and there should also be a checksum to make sure that this really was what we thought it was as we could have just encode a checksum or length check or whatever then we do our fuzzy patch on here meanwhile this has changed we then do our diff plus my add lie here tap that across yep does this involve some sort of notion of time though because presumably the s was typed at the same time as my and packet could be going out please a good question I was actually going to hit that one right at the end as being one of the limitations that would show that this could not work on Mars and question is what happens if these packets are going simultaneously the problem is that I yes you cannot have more than one packet running at the same time the idea and what I'm working on is client-server so this is a web browser that's a server and so you would never have more than one packet circulating at any given time that's an excellent point and that's one of the limitations of this of this algorithm you can't have more than one packet in route at any given time you can on a later version on the next version of this you'll see that but you expire the previous one so if you send out a packet and you wait it never arrives and then you send out another one you can say that one ignore if you get it eventually so out of order stuff so that that will cover yes this does to single-cycle good point okay so this works really well the only flaw is what happens if we lose a packet so let's come back to base state I don't have a cat by the way right client adds an S we get a plus s s in this packet for saying add an S goes across the network and then dies server never gets in we then sit here for 30 seconds or whatever the timeout is and then we try again this time we've added say my so my goes across we patch my in oh and and immediately we fail actually we don't need to get to the patching we just fail out right because this was cats the shadow here is cat we can't recover from this we're now in a state where the shadows are out of sync we don't know who changed did we lose a packet here or did we lose a packet here it's there's no way to recover from this state short of somebody saying okay forget what you know here's a new copy let's resync ourselves and what I've decided is that a good plan is if there's a disagreement with a certain between the client and the shadow and there's more than one client that is there a the client and the server and there's more than one client then the server should win because if you imagine a network with a server and a whole bunch of clients just because this guy has got a bad connection should not mean that everybody else should suffer and so in this case we would see a mismatch and then the server would say okay whatever you've got erase it will reset the cat and start again the problem ideally this would only happen once once in a while to a couple of seconds worth of data so that would be no big deal the problem is that we've just waited for 30 seconds for a timeout to happen so potentially that's a lot of work that just vanished when we resync so that's why this system doesn't work perfectly if you're on a reliable network then you can use this so we get to the last version which offers and guaranteed synchronization this gets interesting so this is our backup shadow again our division is here so we are still divided and we have potential and it's now becomes a stack of edits which is retained and had a favorite bit version numbers can never keep these straight so this one's got an M n + + + + M right now you know why I'm giving this Tech Talk because when I throw this on the board people scream but you can see where we're getting about how we're getting here and this actually solves all the problems with synchronization because in in a sense it actually re-implement tcp/ip in JavaScript or whatever we're running it so let's take this first bin let's do a simple synchronization first ad Katz oh we are starting off these version numbers there's N and sm n is the clients version number M is the server's version number so these are all starting at 0 so we take a difference shadows initially empty at thank you you would have paid for that one lately later right we take the difference and that's still plus s and we record along with that difference what version on the client side this was based off of so this is version zero and then we copy this across in so doing we increment the clients version the one and the client is done so the client sends this across its plus s based off of version zero and the last version of M I got was zero so that's zero here server gets this and it checks ok for this edit n is 0 and the 0 M 0 M 0 good we match no prob here so we can now patch this on to the shadow that becomes an S and then when we update n - one good and then we do the same thing over here we just apply the patch yes are you straight forwards and then we could do the same thing in Reverse no problem here no juice M change M changes up here in the reverse because we updated n at this point and would urge it would change on the other side when the change originates from the server that's right yes ah the M to the right of the edits that is stored by the server this is this one here this is an acknowledgement that the client is essentially is telling the server the last version which I got from you was M of 0 does illusion of it yes that's right that's right so every individual edit will have a base version of from the clients point of view but it will also have a total acknowledgement of what was the last version I got from the server and usually outside the box because that's good question well it's actually not part of an edit it's really just this could actually be sent on the wire without any edits I don't have any edits to tell tell you about but I got it the last thing you said yeah exactly and then the server would know that the client knows where the server is which is important okay let's do the same thing in Reverse but let's lose a packet so this server has typed in my ok let's do the difference here that's plus my and that's based off of server version 0 and our n acknowledgement we are acknowledging that we got version 1 from the client so our n becomes 1 ok now we have some housekeeping to do here we need to update this to one add my am i losing a step here yes just when we did this patch after we did this patch we were supposed to have copied over there shadow to a backup so that goes that goes here that actually doesn't turn out to be important at this time yeah where's the backup retained this would just be a another copy of the full document so this is on the server again represent yes so there's our dividing line here this is server side backup this is the client-side backup each one yeah that's right the backup gets updated when this patch is done and so after we update this shadow we then but does the Ambler should the other ecosystem of the show no because it was taken before we started this round but this backup was taken as a snapshot down here when M was still 0 in fact that's the purpose we now have a 1 and a 0 here we want them to be different okay so we're now telling the client I got your version 1 I want you to add my to version 0 that would have been great it would fit in just perfectly unfortunately this client never got it because it got lost in the network client sits there for 30 seconds eventually gets bored and sends another packet and let's say the client added an exclamation mark so we just run through the same thing again this goes up we're adding an exclamation mark to version one and the last thing I got from you was from the server was a zero because we never got the previous version so this goes up to two and we still haven't gotten anything in this side so back up shadows never updated yes it is because this is now a stack we never got any confirmation yeah if we got a confirmation that yes I got your version one then with the coop come down here and delete anything that's old but we haven't gotten anything so we'll send it all again and that goes through and now we've got an issue okay first if we look at is client zero server zero fail so now we do have a we do have a server version zero in the backup so that's what this backup is for the client is still basing it off of version zero therefore we cannot do our patches off of version one so what we have to do is invoke a rollback from the backup because clearly we lost out and so now the shadow becomes cats server version zero ok so now let's try this again client version zero server version zero client version one oh well that means that we've already got this so we don't need to we can just throw this one on the floor because we've already seen the plus s there it is so we can ignore that yeah I got that if the server wanted to it could not figure out my previous reply must have gotten lost so now we need look at the next one okay client version one yes okay this matches and so now we can put an exclamation mark in here and here and then we do our difficut and we send it back when we did a rollback from the back up we also have to clear our edit stack okay so let's try this again wait a minute the backup - yes thank you I always forget this that's why I like using computers because they don't forget these things umm right so we did the patch we update the backup and and becomes - thank you very much okay so let's successfully send this across again our diff is add my everything else matches the last version we got from the client was - oh my was based off of version zero um and now we update that to one copy that over good and of course if we lose this again we just keep on going we just this stack of edits just keeps on getting longer and longer and longer until eventually something main manages to make it through but let's put the system out of its misery and let it pack it arrived okay so n is too good M is no actually that's correct because this is updated after after we do the diff first we do the diff then we copy it across an updated you can do it as before as long as you're consistent it doesn't read it better but this is base this is a diff based off of a version zero now you could decide that this is a diff that results in version one it's semantics it doesn't matter which way you do it okay so then we do our patch my we update this to one my and then we update our client shadow two to my exclamation mark and because we've got an acknowledgment of two we can now look down at our edit stack and say okay this all of these were received so we can wipe this in and we're back in business so it doesn't matter where you lose data the system will remember what's required rollback if needed and keep on going and always maintained consistency the final detail is we saw a rollback from the back up to the shadow no matter what you do to the system you will never ever see a rollback from this back up to the client shadow which is odd because this system is totally beautifully symmetric and there's a reason for that anybody see the reason why you would never have a rollback from this direction issue is yes that's right the client-server connection here is inherently asymmetrical because the server can never reach out and touch the client hey I've got an update it's always the web browser the client it has to connect to the server so this client could be sending and sending and sending and sending until it eventually gets a response the server can never send unless it has just immediately gotten a response so if you've got an asymmetrical connection like a web browser then you don't need a client-side backup and this simplifies it you can just remove this completely if on the other hand you're running this on a peer-to-peer system or server-to-server or something which is more equitable and either side can tap on the other shoulder then you'll need this backup you'll need it if you don't want a to loss when a packet is dropped and you have to resynchronize in which case somebody's loses big time soon the two user will come the separate i/o area right now they were happy no that's ok if you are diff if it's is actually a question of how good your patch is and to a certain extent how good your diff is in terms of resolving these differences if one of these differences collide so badly you cannot patch it in then it just gets dipped every will get patched into the shadow but the server won't have it in its main text and it'll just get dipped out and delete it from the client so you type something and it'll get rolled back immediately or as soon as that one completes or you'll get a collision notice or you can deal with it however you want yes let me show you what that looks like I think we're done with this we're done okay good server client let's figure out of a backup shadows we don't need the client shadow server shadow there is one synchronization loop and then if we've got another client client shadow server shadow there's another synchronization lip and so on you can have as many as you want now this poses a slight problem because now the server doesn't just know the text it also knows the shadow forever particular client which immediately calls up the question of does that mean that every user is now tied to a particular server and that's a problem if you've got data centers with thousands of computers and you need to reallocate them and that sort of thing yes and no there are two ways around it and probably the simplest approach is to have our cloud of clients hit a router which firms it off to any available load balance server but all the servers are backed by a central database so all of these shadows and the text would reside in the database and whichever server requires it can use it that's the conventional approach that's what mob right uses in App Engine which is currently out there pretty conventional it's simple it works there's another approach which is more intriguing I don't know if it's just practical but it looks cool let's say this server is at capacity let's add another server server to and it's got its own clients we can set up a server shadow here and a server shadow here and have them synchronized between each other works fine same protocol this person makes a change it arrives here this now this copy now has a change compared to this shadow so it gets sent and it was a change compared to that set shadow so it gets sent and so on you could chain this as much as you want so this this is truly expandable in the previous example I had a common database well the common database could get overloaded this can't get overloaded ever so this is a neat system the problem is you cannot easily drop a server so if you've got a long chain of servers and you'd find you don't need this one anymore and you've still got some client who's been here for a long time you can't get rid of this server because they're serving particular shadow the other problem is that latency increases so if I'm syncing once every say five seconds here once every five seconds here it takes a maximum of 10 seconds to go between this client and this client we would take a maximum of 15 seconds to make this route so if you're going to use this you probably want a tree approach so that you've got the minimum number of jumps anyway I don't I've never built this but hey Jake work those parallels and work on any individual server does the server have to process essentially round-robin between all the clients at serving because that shared document that is holding right right and so you definitely want to have locking so that if two edits are coming in simultaneously and you would want to lock this document now you can do it many ways from saying okay I'm just going to handle this request now I'm just going to handle that request the Python and implementation of mob right which I've written actually locks these resources just as needed so there's a couple of very brief points where I need to take a just a quick copy of this to make an update or and then I release it again so when you're going through the algorithm and it takes a little bit of thought to think do I need to hang along to this lock or can I let it go and let somebody else change it and it turns out that the it's very brief the biggest pain point is computing add if not making a patch patching is fairly easy it's take this text put it here there's a little bit of fuzziness that makes it interesting but calculating a diff is an O n squared operation where n is the length of the diff so that can get kind of painful but you don't need to lock it for that I just need to take a quick copy of it and then I can diff to my heart's content on that copy and I don't need to block anybody else okay the last thing I wanted to look at is timing how often do you synchronize we really want to synchronize as often as possible because that gives you a real-time update you can see people typing as they as they type but what about latency well it turns out because diff is om squared where n is the length of the Edit if you can get your disk frequent enough that they're happening one edit apart where an edit can actually just be an insertion of an arbitrary length it doesn't have to be character by character then it becomes all 101 scales really you will so that's uh yep that's my strategy too if as the load gets greater as the user starts doing more don't back off actually step forwards and synchronize eating more frequently because you will end up doing less also if you've got that edit stack down there it means that you're decoupling the differencing algorithm from the network algorithm so you can go and DIF it a couple of times a second if you want and just add those differences to the stack and then transmit the stack once every two seconds or whatever your network decides it wants to do and that means that you are spending less time doing differencing even though you're doing it more often and from the system's point of view it just thinks is getting massive packet loss but it's handling it just fine so that's one approach and and yeah my limitations I had one was you can only have one packet in flight at once as you've mentioned earlier so that means that if you are on Mars and your servers on earth I hate it when that happens the lag time is just nasty and there's nothing you can do about speed of light but ideally what you want to be able to do is send a packet every minute or so even though you haven't gotten anything back from Earth and this system does not support that so if you've got massive latency you'll have some more work to do and the other thing which this doesn't handle well is attribution to particular users so if we look at this from the point of view of three clients if these two clients both make a change those changes get integrated here and then we do a diff between the sum of these two clients and our shadow and what we get is a diff that comes through that contains both of the merge and there's no easy way the way there would be for a three-way merge to figure out who typed what who's responsible for what it can be done I thought about it a little bit but it's not inherent in the system so attributions an open question yeah sorry don't know but if you wanted if you see this document you want to say who typed this word well you don't really know because what you got from the server was this big blob so there are some strategies to sort this out but I haven't worked them out completely I mean usually 99% of the time you're only going to get one change at a time in which case you can say oh yeah I got that from over there but it's in complicated merges where it gets gray who typed one yep change the format to store the attribution and then edit that gets sent over is I added the letter S right essentially put adding metadata to every letter yep that's one of that's that is an approach I don't I've been looking for another approach because that adds an awful lot of extra data for something that's fringe but yes if you are that paranoid you can do it if you're paranoid enough to do that then do that that will work perfectly just adding metadata every character who who created this and you could also add when and where and whatever else the other fun thing is that this synchronization system works for any Content we've used plaintext well we've used my cats but this as long as you've got a diff algorithm and a fuzzy patch algorithm this algorithm will work for anything whether it's plain text rich text vectors bitmaps whatever and you just have to create appropriate patch and diff algorithms I'm only really familiar with the plaintext versions of those because I've developed some but I know people who are working on tree based ones which would allow you to do rich text missing something because like for every dip that you're applying you have the exact that's right and I only need to store two copies the current one and the backup I don't need a full backup because once I heard an acknowledgement I'm good but what I wonder is why why the why do these to be a fuzzy patch I don't need the fuzzy patch when updating the shadow that patch can be brittle in fact it should be brittle the fuzzy patch is required when updating the live text on either the client or the server because that text may have changed legitimately without there being any problems simultaneous edits so that bit does have to be fuzzy or should be if it's not then everything's going to be a collision which may be an option as well depending on your circumstances but yeah that other one can be fragile so I'll just leave by adding the webpage where you can get all the details on this is it started before I got to Google so it's on my personal account it's a deal you'll duck Fraser name / writing / sink and that's got everything we talked about here a little bit more a little bit different and it's also got links to an operating version of this mob right which is going to be it's currently in version 2 version 3 is going out tomorrow that includes the guaranteed synchronization thank you for coming

Channel: Google TechTalks

Views: 36,155

Keywords: google, techtalks, techtalk, engedu, talk, talks, googletechtalks, education

Id: S2Hp_1jqpY8

Length: 54min 43sec (3283 seconds)

Published: Sat Jan 10 2009

Reddit Comments

[u/HelveticaScenario]

See also http://neil.fraser.name/writing/sync/