CRDTs: The Hard Parts

hello everybody my name is Martin clapman I'm a researcher of the University of Cambridge and today I'd like to talk about some of our work on conflict free replicated data types or

CRD T's so I'm going to start this talk with a very brief introduction as to what CR duties are and why they are useful but most of this talk is going to be about new results that we have

figured out only within the last year or two so you might know me from this book here which I wrote a couple of years ago it's called designing data intensive applications and it's a broad overview

of the architecture of data systems and how to choose your database for your particular application that's not what we're talking about today so today we're talking about collaboration software so

in collaboration software I'm taking a fairly broad view of this this is any kind of software where several users can come in and update a document or

database or some kind of state shared state and various examples of software that fits in this category Google Docs is an obvious example where you can have

several people editing a document at the same time create a text document or spreadsheet similar things you get with office 365 figma is an example of graphics software that supports

multi-user real-time collaboration Trello is an example of project management software where several users can update their status of various tasks

assign the tasks and comments and so on so all of these have in common that the users are updating some kind of shared state now I'm going to use this example

collaborative text editing for now there will be some examples from other types of applications later as well so in collaborative text editing you can

end up with a scenario something like this you have to users who at the beginning of the time that we're looking at they have the same document which is hello exclamation mark and then the red

user comes along and changes this document to hello world so by inserting the word world before the exclamation mark and concurrently while the red users doing

this simultaneously the blue user changes the document to add a smiley chase after the exclamation mark so these two changes happen concurrently

without knowledge of each other and then later on as the network communicates those changes so these users communicate over the Internet or whatever network

they are using and they should converge to the same state so we want that at the end both users have the same document on their screen and that document reflects

all of the changes that were made and in this case the merged outcome is is quite reasonable what we expect to expect the word world before the exclamation mark and the smiley face after the

exclamation mark okay and so there are broadly two families of algorithms for achieving this kind of collaborative text editing one is operational

transformation or ot and that's kind of the classic of multi-user collaborative editing that has been around for a long time and that is used for example by

Google Docs and then there's a newer family of algorithms called CID T's which is what I work on which take a bit of a different approach to solving a

similar problem and we will compare these two in a minute so I will start with a brief summary of how operational transformation works because that is

then useful as a comparison point for CID T's so with operational transformation we have to first of all describe how changes are made to a

document and so when a user changes a document they insert or they delete a character at some position in the document and so we can describe the

positions at which those insertions and deletions happen by using indexes so we simply number the first index the first character and the document to be aged

the second character sorry the first character to be 0 the second character to be 1 and so on and so now you can have two users updating their document and here on the

left hand side the user changes the document HDL Oh by adding a second L at position 3 and on the right hand side we

have the user the purple user adding an exclamation mark after the letter and so now after these two changes have happened these changes need to be communicated over the network so that

one user finds out about the changes made by the other user and so from the left-hand side here we have this insertion of the letter L at position 3

or at index 3 in this document and we have the insertion of the exclamation mark at index 4 on the right hand side so let's first of all take the insertion

from the left hand side and move it over to the right hand side and so if there's a server for example that forwards these messages from one user to the other the

server can just forward this insert L at position 3 operation over to the right hand side and on the right hand side we insert L at position 3 and we end up

with hello with two L's and an exclamation mark just as we wanted now what happens if we go in the other direction so taking the exclamation mark insertion from the right hand side to

the left hand side note that if we simply forward this operation insert exclamation mark at position 4 if we simply forward that unchanged then the user on the left hand side would end up

with the document saying hell exclamation mark O which is not what we want we want both users to end up in the same state and for that stake to reflect the intention of what the users were

writing and so instead what has to happen is insert of inserting at position 4 the exclamation mark needs to be inserted at position 5 the reason for

that is that concurrently there has been another insertion at position 3 in before the position for insertion and so the insertion of position 4 needs to be

transformed into position 5 due to the concurrent insertion of the L earlier on so this is why the algorithm is called operational transformation we have to take these insertion and deletion

operations and depending on which other operations happen concurrently we have to transform the indexes or the positions at which those operations take

place so this algorithm does work but it requires one very particular assumption and fundamental assumption in most operational transformation systems is

that all of the communication goes via a single central server so in Google Docs case that server is provided by Google

and the server is you know it's it takes a really key role in this algorithm by sequencing all of the operations and the

assumption of operational transformation is that because we have this central server that is required to sequence all of the operations there cannot be any other communication channels in the

system so even if two users who are collaborating are actually sitting in the same room and they could just be using the local Wi-Fi or even Bluetooth to be communicating their changes between their two devices using that

local communication channel is not allowed because it would undermine the assumptions that are made by the operational transformation algorithm so Ooty requires all of the communication

to go by the central server even if that servers on a different continent and even if the two heaters actually sitting in the same room so this is the difference of where Co deities come in

CR DTS allow this kind of multi-user collaboration without making any assumptions about the network topology so it doesn't assume anything about servers or what kind of network is used

any type of communication channel can be used to communicate the operations or the updates from one user to another and the main correctness criterion that we

have for both ot and Ciardi T's is what we call convergence so what we require is that whenever any two users have seen

the same set of operations then those users must be in the same state and this happens even if the users actually saw the operations in a different order so

what we what we do in CR DT is is we make the operations commutative which means that even if they are swapped around their order is swapped around the end result remains the same and this is

how we can achieve convergence it's just ensuring that after everyone has communicated everyone has the same document on their screen and this makes sense it's of course a very useful property if we did not have this we

would have some kind permanent inconsistency between the users and that would be bad so convergence is clearly a minimum requirement for any of these sort of

collaboration software but as we shall see in this talk convergence by itself is not really enough because convergence doesn't say anything about what that

final state is about after the nodes have communicated so is that final merged state actually the state that we wanted and this is a little bit more

difficult to define because what state is desirable or not desirable is really a matter of human judgment it's what are as humans what is our expectations of

the software of how should the software behave and unfortunately it turns out that several of these IDI algorithms for collaborative editing sometimes have

behavior that is not really desirable that's behaved weirdly in some ways that we as humans would not expect and I have come to the conclusion after several

years of working on Co DTS that basically these problems are quite hard and a simple version of C le T's is very implement very easy to implement but

actually getting it right in such a way that it actually satisfies the user expectations is difficult so C oddities are easy to implement badly and what we

shall have a look at in this talk is how we can implement the oddities well in a way that actually behaves in a way that we want so today I want to look at these

four topics these are all areas in which C oddities are difficult in some way or another and for most of them we have solutions as well so I'm going to just talk through those one by one and the

one that I want to start with is interleaving so interleaving is a problem that can happen in collaborative text editors if several people insert

text at the same position in the document now I'm going to in order to explain why this interleaving happens I'm going to first give a little introduction as to how C oddities for

text editing work and I'm going to start us with an example so as I said earlier when we were looking at operation

formation we identify the position where we want to insert or delete a character by its index simply by counting from the start of the document and that has the problem that those indexes need to be

transformed so see Aditi's avoid the need for this kind of operational transformation by instead taking a different approach instead see our DTS create a unique identifier for every

single character in the document and that unique identifier remains stable it remains the same even if stuff is added and deleted elsewhere in the document so

each character keeps its own permanent unique identifier and there's several possible ways of constructing such identify us one way is we can choose a

number between 0 & 1 so it's some kind of fractional number a rational number and we say for example 0 is the beginning of the document 1 is the end of the document and for every position

somewhere every a character somewhere within a text document we will just pick a number that is appropriately positioned within that number line so here in our example of HDL Oh we could

say okay let's assign the number zero point two to the H the number zero point four to the air II the number zero point six to the Eldar number zero point eight to the O and so

this way we have spaced out our characters over are 0 to 1 number interval and now when we want to insert a second letter L and an exclamation

mark we pick numbers in between the intervals so we want to insert a second L in between the first L and the O so in between zero point six and zero point eight okay let's pick zero point seven

as the midpoint and likewise for the exclamation mark we'd pick a number between zero point eight and one point O so a pig zero point nine for example and

so this is a simple enough scheme and we can use this to implement a CR DT in quite a simple way so what we can now do

is we can think of our our text document as a set of tuples and each of these triples contains the character at a particular position it contains the

numeric value that tells us where this goes and then finally here the aid that I've put in these triples is just a way of referring to the the node

ID that created this particular insertion operation so this is just some kind of unique identifier for a particular user or a particular node in the system and the reason we have that

is just in case two different nodes pick the same number then we can define the ordering on these characters based on

the node ID as a tiebreaker and so we now just have this set of triples representing the document and we can make edits we can insert new characters into this text document just by picking

numbers for them and and then calculating the set Union and we get a set including the new tuples and we can reconstruct exactly what the state of the document is by just sorting those

tuples by their numbers tiebreaking based on node IDs and then we get the text document and several the oddities for text take essentially this approach

they tend to not actually use numbers between 0 and 1 instead they use things like a path through a tree but the effective idea is it's still the same they are just essentially picking

positions on a number line and so when we implement a C or D T in this way we can have some unfortunate behavior and this is an example of behavior that can

occur in some text editing CR duties so here we have two users on the left hand side user 1 who starts off with the text document saying hello exclamation mark

and user 1 inserts the word Alice between hello and the exclamation mark and concurrently on the right hand side user 2 inserts the word charlie

in between hello and the exclamation mark now the two users communicate they merge their changes and we got what we get out at the end is hello and then

some kind of weird jumble of letters that we can't read what what does this even mean how did this happen we started with Alice and Charlie and we ended up with some kind of massive letters well

what happened is this here so we started off with a text document where each each character has a number on the number line

and hello the the Oh had 0.64 and the exclamation our card 0.95 and so then the insertion of Alice or space Alice just choose some chose some numbers in

between that interval zero point six four and zero point nine five and likewise Charlie insertion independently chose some numbers within that interval

and so what a lot of CRT T's do for this kind of thing is they actually randomize the numbers a little bit because that reduces the probability that two

different nodes will pick exactly the same position pick exactly the same number for a particular for a particular character so reduce the risk of

collisions and so what has now happened with this insertion is that well we have taken all of the numbers from Alice on the code which are coded in red here and

the insertions of the Charlie letters which are in blue and we simply ordered them based on the numbers and the result unfortunately is that we've now interleaved those two character sequences that have come from the two

different users and the result is unfortunately a complete unreadable mess now this problem is bad enough if we're

just inserting a single word as we are here it gets even worse if what the two users have done is concurrently inserted an entire paragraph or maybe an entire section into their text document if you

have a paragraph or a section in which the characters have been interleaved on a basically random basis you will not be able to use that text anymore you will just have to delete it and rewrite it again and the users are not going to be

happy about this unfortunately this behavior really does occur in real si oddities and we have examined a number of different at RC OTT

algorithms for text editing and we have demonstrated this problem at least in the algorithms called blue gute and LS EQ and so in these problem in these

algorithms unfortunately this interleaving problem is very deeply baked into the fundamental way how the algorithm is constructed I cannot see any way of

fixing this problem fixing this bug in the algorithms because the way how these numbers are assigned or the waiter paths where the trees are assigned the this

this interleaving idea is just very inherently baked in to the way these algorithms work so other algorithms we have not found this problem so in tree doc and wood for example we did not find

this interleaving problem this does not entirely guarantee that that it can never happen but we think it won't happen and so in a way these algorithms

are safe however unfortunately these two algorithms are also the ones that are least efficient the entire reason why the L seq algorithm was designed for

example is because the designers wanted a CLD T that was more efficient than tree doc and route because tree doc and do unfortunately take a lot of space for their ident for their identifiers and so

unfortunately this performance optimization has now introduced bad behavior in the algorithm and in my opinion that makes the algorithm like LS EQ and la cude basically unsuitable for

use in in many text editing applications moreover there is a specification of collaborative text editing called a strong here which was published by Atia

and others in 2016 and this specification also allows interleaving as a ballad behavior though we have a paper in which we fix this specification

to rule out this interleaving behavior finally our GA is an interesting one so our GA is another text editing CR DT algorithm which does not quite have this

same interleaving problem it has a bit of a less of an interleaving problem and so I will mention that briefly because it's an interesting case study so in our GA the interleaving problem

that can happen is like this so in this example here on the left hand side we've got user one who starts off with the document saying hello then the user inserts the word leader between hello

and the exclamation mark then the user moves their cursor back again after the word hello and types the word dear so what we have here is typing the word read are moving the cursor back and then

typing the word dear on the right hand side we have user 2 who just typed the word Alice between hello and the exclamation mark and what can now happen in RTA is that the word

Alice can get interleaved in between the word dear and the word reader so even though the text dear reader was typed by the one user and the word Alice were

typed by the other user we can end up with the two mixed up a bit so we don't get the same character by character interleaving as we get with some of the other Co duties but we do still have the

ability for text to be inserted into the middle of a different users insertion and the reason this happens is the data structure that RTA uses looks a bit like

this so it's a kind of tree data structure with with very deep sub trees and a small branching factor usually and what happens here is that each node

industry is a character that was inserted and the parent of each node is the character that was the immediate predecessor character at the time of

insertion so we start off with a single special node at the root which is the beginning of the document and then when the user types

h-e-l-l-o exclamation mark each of those letters has as its predecessor the character that was just typed and so you end up with this chain of h-e-l-l-o

luckily like a linked list almost where each characters parent is just its immediate predecessor in this tree and then the users come and position their

cursors in between the hello and the exclamation mark and one type space reader another types space Alice and the

first user who typed reader moved their cursor back and type dear and so you can see every time the cursor gets moved that results in a new sub tree being

formed here and then otherwise the the order of the characters in this document is a depth-first traversal over this tree and so we can see that in the

interleaving that has happened here hello dear Alice reader what has happened is we visit hello then first the dear subtree then the Allis subtree then the winter

subtree and then the exclamation mark and the order in which we visit those sub trees is defined by a time stamp that is attached to every node industry

and so if we have in this case here several siblings so the own ode has several children then we visit those children in descending order of

timestamp and because the time stamps are unpredictable in concurrent editing cases you can end up with these three possible outcomes as the merge results

so it's not as bad as the character by character interleaving that you get with the others I should be precise it is possible to get character by character into leaving

an RG a the circumstances in which that happens is if the users type their document back to front so if the users start at the end of the document and first type the last letter then move

their cursor back to the beginning type the second to last letter move to cursor types third last letter and so on and type the entire document from the end to the beginning if they do that then they

would actually get character by character interleaving in RGA because in that case in this tree here all of our characters would be siblings there would all be children of the root

node and in our case the ordering is just defined by timestamps again but fortunately in practice people tend to not actually type documents like that and people tend to type documents in a

reasonably linear fashion from beginning to end and of course occasionally people will backtrack a bit delete a bit copy and paste some sections and so on but as the general rule

typing still happens in a fashion from beginning to end and so for that reason the interleaving problem is not actually as bad in our GA as it is in the other algorithms

however we could still say we want to be strict and we want to not allow any interleaving at all and we did actually devise an algorithm so for our GA we

were able to find a fix a modification to the algorithm which changes it such that this kind of interleaving of concurrently insertion does not happen regardless of how the cursors was moved

I don't have time in this talk to talk about this particular rhythm but if you're interested there's a paper that we published in 2019 called interleaving anomalies in collaborative

text editors and in this paper the algorithm is described exactly so let's

move on to our next topic our next topic today is reordering list items that is we have a list of things and we want to

move an item from one position in the list to another so one example in which an example application in which we might want this is a to-do list so in a to-do

list often you can drag and drop items into whatever order you want and so what happens here for example is you have a to-do list consisting of firstly by milk

secondly water the plants thirdly phone Joe and the user is dragging and dropping the phone Joe item and moving it to the top of the list so that this

is now at position one so how do we do this well we can represent the list using any of the CEO duties that we talked about earlier so all of the CEO duties for text editing are also Co

duties for lists and so we can use those to represent this ordered list of items however all of those CR duties don't actually support a move operation all

they have is operations for inserting and deleting items but no operation for moving now you might think ok well that's not too bad because we can always

implement moving by just deleting the item from its old location and inserting it at its new location and this works except it has a problem if several

people can currently move the same item so in this example here replica a and replica B both move phone Joe to the top

of the list and so what happens if we implement this moving by deleting and reinserting well they both delete phone Joe from position 3 so it's definitely

gone from position 3 and then they both insert phone Joe at position 1 but the result now is that these two insertions at position 1 they both happen and so we

end up with two copies of phone Joe at position 1 & 2 so this item that we wanted to only move has accidentally got duplicated in the process and this is really not the kind

of behavior that a user would expect I think over to do list application just because they reordered some items on their list doesn't mean they certainly want to copies of those items appearing

so well what is the behavior actually does we want what is the desirable behavior let's look at a similar example here in this case we've also got two

replicas moving phone Joe but we've got the moving that item to different positions so replica a moves phone Joe to the top of the list whereas a replica

B moves phone Joe to be at the second position so after buying milk so what is the desirable behavior in this case well we could say that now our phone Joe should appear in both positions before

buy milk and after buy milk but then we've got duplication again and we did not want duplication so really what we want is phone Joe to appear in one of the two positions I guess that maybe

show a warning saying hey use odd as a warning we we picked one of the two positions or maybe it's just fine to just pick one of the two and forget that there were two different list positions

so I'm just going to say now let's we're going to pick one of the two concurrent positions as arbitrarily but deterministically as the winner and so

in this case example here we've got phone Joe being at the top of the list as the winner so from the point of view of the first user nothing changes but from the point of view of the second

user after they've moved from Joe to position two then additionally the phone Joe is then subsequently moved to

position one and now let's think about what is happening here so we've got two concurrently written values for the two different positions and we want to deterministic ly

but arbitrarily but deterministically pick one of them as the result as the winner as the outcome and this may look familiar to you if you have studied

existing CEO duties because it's just what happens in a last writer winds register in the last writer in red we've got except a register which is a

variable effectively which can concurrently have a value assigned to it by different users and if we have those concurrent assignments the end result

after everybody is merged their state is that we pick one of those values that has been written as the winner and we throw away any other values that have been written concurrently and so you can

think of here as the position of the list item phone Joe as having a last writer wins register semantics to it

that is first one user assigns the position of phone Joe to the head of the list the other user assigns the position of fern Joe to be after by milk and then

as the two users communicate then the end result is the winner is one of those two values either head of the list or after by milk so let's make this a

little bit more formal what we need is if we want to implement this here we need a last write of wins register okay second we need some kind of an ambiguous

way of referencing positions in the list but if you think about what we've just done earlier when we were talking about unique identifiers for the characters in a text document what the lists the

oddities and these text see oddities already doing is providing us with a stable and unique way of referencing particular positions in a list so we can just use one of these existing

algorithms and use its unique identifiers for list elements in order to reference the position of a particular item endless now difference er duties have different ways of

constructing those identifiers as we saw like tree dock uses a path through a binary tree log ooh chooses a path through a tree with a higher branching factor RGA and causal trees use some

kind of time stamps but the basic idea is still the same we've got unique identifiers for particular positions in the list and so we can take those identifiers and put them as the value

inside our last strata wins register secondly what we need now if we've got several list items is we need a separate register for each list item to hold the

for that particular list item and so well we can just construct a set we can for example use a a twin set set CR DT and the contents of that set are going

to be all of the items on our list and so we're going to say to each item on the list is going to be a pair consisting of a value which is like the text on the to-do list item for example

and they last writer wins register containing the position of that particular list item and so now we can add new items to the list by adding them

to the add win set we can move position from one position to another by updating the value of their last writer wins register in particular we use a list C R

DT to create a position identifier for the location where we want to move a particular item and then we take that position identifier and use it as the value in the last write wins register so

here we've constructed a new C R DT operation now a move operation for lists just by using three existing CRD T's any of this this range of different lists

see our duties plus an ad win set plus a last writer wins register and we've constructed a new operation and because we've just composed these existing C our duties we know that the end result is

also going to be a CLE T so this is very nice and it allows us to do these atomic moves of a single list item at a time now things get a little bit more

difficult if we want to move from more than one item at a time and so in a to-do list you really only need to move one item at a time because they typically drag and drop a list lets you

pick up one item at a time in the user interface so that's not really a problem but in text editing you could imagine other circumstances arising so in this

example here we've got a to-do list this time represented just as plain text as a list of bullet points wage bullet point starts with a bullet point character and

ends with a newline character and so here replica B is taking the item milk and wants to move that in front of bacon and so that means taking all of the

characters taking a character bullet point space m IL k new line the whole range of characters are moved a whole range to be in front of bacon

concurrently with that happening a different user is updating the milk item to say soy milk and so they do that by deleting the uppercase M and inserting

the text soy and the lowercase M okay so what do we expect to have happen here so firstly the soy milk sorry to change

from milk to soy milk takes effect and the move from milk to be in front of bacon takes effect so we would expect the desired outcome here is that we have soy milk first in the list in front of

bacon so that means that two changes have become merged together cleanly this is what we want to have happen unfortunately it's not what actually happens so if we look at the algorithm

that we just constructed for moving a single list item and if we just move each character individually according to this algorithm the end result that we get is this here so we end up with milk

is correctly moved in front of bacon that's happens exactly as we wanted but the change from milk to soy milk remains attached to the old position of where

milk was previously not the new position where milk has now been moved to and so the end result now is that the list reads milk new line bacon new line soy M

and that soy M is just standing there without any context because its context has been moved away in the meantime and this is a problem that I do not know how to solve at the time for the time being

I've spent a while thinking about it come up with a couple of half solutions that don't really work a couple of other people are thinking about it as well so if you're interested in this feel free

think about it and do publish the result if you manage to figure it out so this is the problem of moving items in lists so we've figured out how to move a

single list item at a time but these ranges are characters moving them in a way that behaves nicely is still an open challenge let's move on to point three which is

again about moving but now rather than moving elements in lists we're going to move sub trees in a tree so let's again look at an example let's say we have a

tree structure which might be set a file system and like in the case of moving elements in lists we can think about what happens if the same node in a tree

is concurrently moved by two different users to two different locations and so you can see here we start off with the tree on both replicas where a B and C

are children of the root and on replicas a we're going to take that that node a and move it to be a child of B whereas

on replicas two we're going to take the same node a and move it to be a child of C so now a has been moved to two different locations on two different

replicas in this case what do we expect the outcome to be and it's kind of similar to the case of moving elements in lists so one option is to duplicate

it and so what we can have is that we have a appearing as a child of B and also a appearing as a child of C this means then further any children of a

will also have to be duplicated and that's what you get here in the in this box labeled a that is you have the the a

subtree with a 1 a 2 a 3 children and then another whole copy of the whole subtree so this is duplication like in the case of the lists I think

duplicating nodes on concurrent news is not a good behavior so we don't want that well another option is for a to be

actually shared as a common child of both B and C this works but it's no longer a tree so if what we expect our data structure to be is a tree rather

than a dag or some other kind of graph then this is not an acceptable outcome because here a has two parents and in a tree no node ever has two parents so

that leaves C and D as the post outcomes see is simply we take the replica one operation as our outcome and

ignored the move made by replica two or vice versa we can choose replica two to be the winner and to ignore the move made by replica one so in this case

either a a pipe appears as a child of B or a appears as a child of C but not both so like in the case of of moving

atoms in lists what we have is a kind of last writer winds behavior here and I think that is reasonable now in trees additional complications appear and so

trees are definitely a harder case than lists and so another example of tricky things that can happen in trees can be illustrated with your file system so if

you want you can try this on your computer and just create a directory called a and then create a sub directory within a called B and then try moving a

into B so move a to be a child of a slash B this may sound weird what you are doing here is effectively trying to

move a directory into itself I don't know if you've ever tried this I did try it on Mac OS I get this response here from that from the shell saying invalid

argument I'm not allowed to do this movie and this makes sense because if we did perform a move where we move a directory into itself we would kind of be creating a cycle and then this would

our data structure would not no longer be a tree it would be some kind of graph with cycles in it and this would be very confusing for a file system so if we build see oddities or trees it also

makes sense that if we allow moving sub trees we also prevent this kind of cycle and prevent somebody moving an object inside itself but unfortunately with C

oddities we have the additional complication of concurrent changes so consider this example here where we start off with the same tree again on

both replicas on replica one we take the node a sorry we take the node B and move it to be a child of a so here B

appears as a child of a while C reigns as an existing child of a on replica two we start off with the same tree and in this case we move a we move a to be a

child of B so we end up here with a as a child of B and C as a child of a as before what happens now if we merge these two so we've got here to move

operations each of which by itself is perfectly fine there's nothing wrong with moving B to be a child of a and there's nothing wrong with moving a to be a trial to B but if we combine both

of these we end up with exactly the same problem as we just had we're effectively one directory gets moved inside itself and so if we are not careful with this

algorithm we end up with a and B in this kind of cycle disconnected from the root of the tree and well this is again no longer a tree it's some kind of more general graph data structure so we don't

want this if we want to preserve the factor of grandpa tree another work option as before is we can duplicate nodes so we can say that well we move B

to be a child of a and we move a to be a child of B so we have both options both B as a child of a and a as a child of the book that simply exists in in our

directory graph in our tree and so again we have to duplicate any of the children of those and as before again I think duplication is the wrong way of doing this so it seems as before what we

really want is a last writer wins semantics here where either this option here that is the outcome of moving B

into a and ignoring the other move or we choose the outcome of moving a into B and ignoring the other move so in this case we want to pick one of the two

conflicting operations and we want to just ignore the other one what we have to ensure that all of the replicas end up picking the same operation as the winner and ignoring the same other

operation because of course otherwise they weren't converged and then it's not a CR DT so how do we actually achieve this now where we want to ensure that all of these

conflicting operations exactly one gets picked well I don't know we can try some existing software I tried this with Google Drive for example and I got this

wonderful error message here I tried exactly just having two directories a and B move a into B and move me into a concurrently on two different computers

what happens I get some kind of internal unknown error try again but this error never goes away it just keeps sitting down and loop trying to sync yeah so Google Drive

hasn't solved this problem either okay I guess we'll have to think about it for ourselves so the way that we solve this is by thinking about the sequence of

operations that get applied on each replica and having a time stamp on each operation and we're just going to assume some globally unique timestamp as usual so you can use Lamport time stamps for

example that works fine and of these operations some of them are going to be move operations and some might be some other kind of operations and here we

have on replica one we have moving a into B and moving B into a on replica two and as I said before each of these operations by itself is safe and fine to

execute what we need to ensure that we detect the case when two operations are in conflict with each other in the sense that executing both of the operations

would create a cycle so we have to ensure that no matter what we do we do not create a cycle now what can happen now if these two replicas merge there

are sequences of operations is well we take the union of the operations from both of the replicas we can put them in

time snap order and now if we say that the operations get executed exactly in increasing time stamp order then the first move is fine because by this point

nothing bad has happened yet but then by the time we get to the second move operation that move is unsafe and so if we want to ensure that there are no cycles in our tree then we have to skip

that operation just pretend it didn't happen this is our tricky because replica 2 has already executed this operation so replica 2

will sell somehow have to undo this operation that it is really performed in order to ensure that it converges again with replica 1 so the basic principle

we're going to use is to take these sequences of operations where we have a time stamp on each operation and we're going to merge them such that we get a

single sequence of operations in time stamp order and so for example here on replica 1 we have time stamps 1 3 4 and 5 on replica 2 we have time stamps 2 6 7

& 8 and so if we imagine your replica one and you've executed 1 3 4 5 and now you receive the operation with time stamp -

from replicas - well what you need to do is you need to take this time stamp - operation and insert it somewhere earlier into your sequence of operations

that you've executed but you know time has already moved on by this point and we've really executed the operations with time stamp 3 4 & 5 so how do we handle this well we can just take a

fairly simple approach which is to undo and redo operations and this is exactly what we do in our algorithm and so that is if you are replica one here that wants to apply operation - and with time

stamp - you've got your log of operations that you've performed where x x 1 3 4 & 5 and we're first going to undo operations until we are back at the

point until we've undone all of the operations with time stamps greater than the new operation so that is we're going to undo up 5 we're going to undo the move we're going to undo up 3 now we're

only left with off 1 so now we can apply up to on top of that with time stamp - and now we we do the three operations that we've undone and the end result is now that we have this log of operations

we're up to has been inserted in the right place and if we keep performing this kind of logic on each of the replicas then this will actually ensure that all of the

replicas end up with the same operation as exit shoot it in the same order just means we have a bit of extra work to do because if some operation needs to be inserted

somewhere quite early on in the order we have to do a lot of undos to do that one operation and then a lot of reduce to replay all of the operations that have happened so you might wonder what is the performance of this isn't the

performance going to be terrible well we did some performance experiments and it was okay it was of course there was certainly a cost in order of performing

all of these undos and redos and you can see that here so we set up a system with three replicas on three different

continents and so there was a delay of over a hundred milliseconds round-trip time between these different replicas and we then just started generating move

operations at a high rate and the higher the rate of move operations in this system the more undo and redo these need to be done and so the slower it becomes to execute each individual operation and

we were able to get this system to at least 600 operations per second which you know is it's not massive on sort of big data scales but on the other hand

for like a single user updating their file system I think I think a single user is not going to perform more than 600 move operations per second on their own local file systems so for a lot of

collaboration software actually this performance is it's perfectly fine and we don't have to worry too much so I will explain a little bit more about how

this how this algorithm works in terms of the data structures that we use and so we have to first find a way of describing the move operation that we

want to perform we're going to say move operation is a structure here with the following fields first of all like I said earlier and weave operation has a globally unique time stamps such as a LAN port time stamp then a move

operation has got to have a child which is the the node in the tree that we are moving and the parent which is the new location the new parent of that child in

the tree now we are not going to note in this operation here what the old parent of this child was so this is like we can call this stealing move that is we're simply going

to take child from wherever it currently is in the tree and move it to be a parent of this new parent here and further we can have a bit of metadata associated with the operation so for

example in a file system you have at one file within a directory and the file has a name within the directory and so that can be the metadata that is associated

with a particular file in a particular directory and then we have to construct this log of operations in order to perform the undo and redo and in order

to perform this undo we need to associate a little bit of extra data with each entry and the log so each entry here has several fields that come

straight from the move operations so the timestamp is from the move operation as before the new parent the new metadata and the child these come directly from the move operations and so in addition

to these we've now also recalled the old parent and the old metadata so that is what was the parent of child before we performed this move and was what was its

old file name for example if we're using the metadata for file names and so now this allows us to perform the undo because what we do in order to undo this

operation is just to set child's parent and metadata back to its old parent and it's old metadata and given this log of

log entries of move operations we can now construct the current state of the tree the tree is just a set of triples of current metadata and trial triples

whenever child is a parent or parent in the tree and so we can now define this ancestor relation here so we say that a is ancestor of B if either a is a direct

parent of tree as in there's a comma M comma B triple exists in the tree or if there exists some tree node C such that

a is a parent of C and C is an ancestor of me okay so this defines just a transitive closure over the parent-child relationship

and so given this definition of ancestry now we can define what it makes for a move operation to be safe so for a move operation if we want to

perform this move we look at the child that is being moved and the parent which is the destination of where the child is being moved to and if the child is

currently already an ancestor of the destination where it's being moved to then this would be unsafe we would create a cycle so we do nothing similarly if the child and the parent

are in fact the same node that would also be unsafe so again we do nothing but in all other cases it's fine so we

can update the tree by removing from the tree the node the existing location of C that is this is exactly what I said we steal the child node from wherever it

currently is in the tree for any peak on Miami here and then we add this new parent metadata child relationship to the tree and this defines our updated

state of the tree and so given this function here for performing a move operation and given the undo/redo procedure that I explained previously

we now have an algorithm for safely performing move operations on a tree C R DT and we proved several theorems about this algorithm so in particular we

showed that this algorithm does indeed preserve the tree structure so to preserve a tree structure what we need is that every node has a unique parent and that the tree contains no cycles

that is the definition of a tree and so we prove that these things hold so for any sequence of operations that are executed the data structure remains a tree and then obviously we have to prove

that it's a CR DT which means that it converges so given any two sequences of operations on this tree if one sequence of operation is a

permutation of the other sequence of operations then applying those sequences of operations leads to the same state in other words operations are commutative

so this algorithm works and we have implemented and and proved these properties about performing move opera

Shinzon trees okay moving on from moving subtrees NCR duties let's talk about efficiency and making co DTS more

efficient so one particular problem that occurs with a lot of CDT algorithms especially the text editing CR DTS is the overhead that the metadata the CR DT

metadata incurs so if you think about a text document what we said is we give every single character and a text document a unique identifier and so what you end up with is each character in

English text would be one bite for the ASCII character the unicode utf-8 encoding of that character but then you have additional metadata so you might have for example some path through a

tree which might take a couple of dozen bytes to encode then you might have some identifier for the node that inserted a particular character which if that is a

UID will be at least another 16 bytes if you encode it in hexadecimal it'll be like 36 bytes or something like that and so very quickly you end up with this really disproportionate situation

where you have one byte for the actual data that you want and something like a hundred bytes of metadata or even more than that just for the CR DT metadata in

order to make the CDT work and that's not a particularly great situation to be in so what I would like to talk about now is some work that we've been doing as

part of the Auto merge project which is a CR DT implementation that I work on in order to bring down that metadata overhead and we've had some really good

successful results by using some carefully designed algorithms and data structures so let me start with the results of what we have here so the old

version of Otto emerge uses a JSON encoding in order to encode all of the metadata and send it over the network and write it to disk and this JSON

encoding is incredibly verbose so what we've done here is as an example to take a particular case study which is the editing history of the latex source of a paper

so in order to generate this editing history a colleague and I actually wrote this paper using a homegrown text editor and so we were able to capture every single keystroke that went into the

writing of this paper so the final file is about 100 kilobytes of plain text so this is just ASCII text containing latex

markup and we captured over 300,000 operations that is the in 300,000 individual keystrokes of the editing history going into that and so that

includes all of the individual characters that were typed in order to create this document all of the characters that were deleted for any stuff that was added or removed or any typos that were corrected and so on and

we also recorded all of the cursor movements so every single time the cursor was moved from one position and document to a different one that was

also recorded and so if you take this history of 300 thousands or so changes and you encode it in the current or to

merge data format in this JSON data format the file size is about a hundred and fifty megabytes so that is we're

using almost 500 bytes per change here which is which is pretty terrible and so you can see now in the in the new binary

data format that we've designed in order to bring down that over metadata overhead we've actually made some some really big improvements on that and so

what we have done is first of all designed a binary format that encodes the full editing history including every single insertion and deletion and

including when that happened and encodes that in a compact form so it doesn't lose any information at all this is a completely lossless encoding and what

we've managed to do is reduce this file size by over a factor of 200 down to about 700 kilobytes containing exactly the same information just encoded

differently so I should emphasize if you would just take the JSON history and encode it using one of the binary equivalents for Jason you would not anywhere near this so if you use

protocol buffers or message pack or something like that you know you you might reduce it by a factor of two or three at the most

but in order to get this factor of 200 improvement you have to design data format doses specific to see oddities and specific to the particular heading

patterns that tend to occur in these sorts of applications now you concede that by gzipping these files you can reduce it so you can reduce 150

megabytes down to about 6 megabytes but the 6 megabytes are still huge compared with the 700 kilobytes that we were achieved uncompressed in our binary

format and that still does gzip down further to about 300 kilobytes without losing any information at all so note

that by this point here now we've been able to Inc encode a change history the change history consists of over 300,000 changes we've encoded that in 300

kilobytes so we're now actually using less than one byte per change in order to encode the full change history so we can look back at any past version of

this document week and if any two versions at any points in time and all of that data is it's still there encoded in this very compact form which I find very exciting now of course we can still

compress it further by throwing away some of the history so one of the first things we might choose to throw away is the cursor movements because to be honest who cares about exactly where the cursor

was at which point in the editing history so we can save about 22% by throwing away two cursor movements and

we can we can go down to about 230 kilobytes by also throwing away all of the change history for the text so by this point here where we're at 230

kilobytes we still have all of the CR DT metadata including all of the tombstones so this means at this point we're still able to

perform arbitrary merges between different replicas of this data and yet we are down to only about twice the

or data set size so about 100 kilobytes is the raw text document with no CR DT metadata at all that's just the final state of the text document and all of

the CR DT metadata is adding only a bit more than 100 percent overhead to this without gzip if we actually apply gzip then that file sizes are almost the same

so the the file containing 2 CR DT metadata gzipped is about the same size as the plain text file non gzipped now

we can get even further down by removing the tombstones the tombstones are the markers for deleted characters in the

document and if we do so then we save what is that another 70 kilobytes or something like that for the tombstones whether you want to do that or not

depends because if you throw away their tombstones it means you can no longer merge with edits that happened concurrently so any edits that happen before that to stone removal or

concurrently with the tombstone removal now can't be merged anymore but but if you do remove the tombstones then just the raw CR DT metadata just that is just

the unique identifiers for the characters at that point takes only 50 kilobytes so it's only about 48 percent overhead on top of the the raw text

document using using our data format very exciting I find this so I should tell you a bit about how this actually works and how we were able to achieve

such good compression the basic idea is as I said we want to still maintain all of the change history as much as possible and so we're going to store the

full set of all of the insertion operations all the deletion operations and all of the custom movements if necessary each operation is given a unique ID which is just the lamp or timestamp and I'm poor timestamp is just

a pair of a counter and the ID of the node generated it or we call it actor ID in auto mode and the the algorithm that we use for text editing is based on CR

DT so it's based on whenever you perform an insertion you reference the in the identifier that is the lamp or timestamp of the character

that is immediately before the inserted position and we keep this set of all of the operations and stored in document order that it's in in the order in which

the characters appear in the document and what we get is this kind of table here so you can think of this almost like a table in a relational database

where each row is one operation and so you can see that is typing h-e-l-l-o so it's hello were three L's and then

somebody came along and deleted one of the three L's so that the final result is just hello and so the way this is encoded is each row here is a is an

insertion operation into this document and you can see that each row has an operation ID which consists or which is a lamp or timestamp so it consists of a counter that just increments and the

actor ID I just wrote a here but in reality our actor IDs are actually new IDs so they're actually like 16 bytes or even 32 bytes long and and so we have

this unique identifier for each for each character dispenser that was inserted here we have the reference element that is the predecessor character the idea the predecessor character and so this is

just saying here the e comes after the H so the H has ID 1a the e has ID 2a and comes after 1a and so we can then encode

all of the operations this way furthermore if an operation is marked as deleted we do that by having these additional deletion columns that we can

regroup sorry record the operation ID of the operation that deleted this particular character in fact it could happen that there are multiple deletion operations for the same character if

multiple users deleted the same character and now we can take this table and include it in a very compact form using some fairly simple tricks so we'll

go to first of all encode each column of this table individually and so for example we can look at this first column the counter call which consists of two numbers one two three four five six how do we encode

that efficiently well first of all we Delta encode it which means for each number we calculate the difference between that number and its predecessor so one two three four five six the difference between any two subsequent

numbers is one so this delta encodes 2 1 1 1 1 1 1 which we can then one length encode to 6 times the number 1 and then we can use a variable length in binary

encoding for integers to encode 6 comma 1 in 2 bytes so this variable length encoding just ensures that small numbers get represented in one byte slightly bigger numbers get represented

in 2 bytes bigger numbers still get represented in 3 bytes and so on and so here we've now encoded this entire counter column here in 2 bytes similarly

we can proceed to the actor ID column so for this actor column well first of all if we make a lookup table we don't need to keep repeating the huge IDs so we

just map a to 0 B to 1 for example and so now this translates into 0 0 0 0 0 0 we can run length encoding use the variable length

binary encoding again running again we've encoded this entire column in 2 bytes moving on let's look at this actual text column here what I've done

actually represented the text in two separate columns so here this is the the utf-8 byte string for that particular character that is being inserted and in

this length column here we have the number of bytes for that particular Unicode character so if what we're doing is just typing English text then every

single character is going to be within the 1 byte encoding of utf-8 and so this column here is just going to consists of lots of ones it's just all of the

characters have length 1 so that encodes again super compactly and now as we've encoded the length columns for the actual characters we can just concatenate them because we can still

then later split out where the boundaries are between the characters by just looking at the length column and so we're simply going to concatenate all of the bytes in the utf-8 column hello with

triple L which is encoded in six bytes so what we've done here just by encoding each column individually we can represent each

column extremely compactly in just a couple of bites and it turns out then that because of the editing patterns that you tend to get with text you tend

to get these increasing sequences because people just tend to type letters in sequential order which means you get to use increasing sequences of counters

that always increase by one each time so the whole data has a structure which compresses really nicely and we can take advantage of our knowledge of this

structure to encode it very compactly so this gives us the set of operations now in order to have the full change history we need some little bit of extra

metadata that is for each set of changes that were made at some point in time we need the timestamp of when that was occurred and the range of operation IDs and with this extra metadata we can now

reconstruct exactly what the document looked like at every passed point in time even while using a very small

amount of additional storage space so if people tell you that with CRD T's you know you have to put effort into tombstone collection because tombstones waste a lot of space you know just think

back at this table here the tombstones actually just cost us 48 percent of the space it's a fairly small amount of costs to to maintain here whereas

choosing the difference between a simple JSON format and an optimized binary format made a factor of 200 difference

so I think this means we have the ability if we want to store the full change history and to allow us to do you know dips and interesting visualizations

or to change history for our documents with very low cost very low cost and we don't actually have to throw away all of

this extra metadata that we have so this brings me to the end as I said at the beginning I think C oddities are very easy to implement badly so they're very easy to implement

in a way that is inefficient and that has all sorts of weird behaviors like the interleaving anomaly that we saw and they're all these problems of how do we

do a move operation both on lists and on trees in a way that is safe and that is recently intuitive to our users but as you've seen from this talk we have made

a lot of progress in just the last few years on these topics and I think it's going in the direction we're really see oddities are starting to become something that can be really the

foundation for a very large set of applications so we can start to build like actual real practical user software not just research prototypes on top of

these these basic principles so I hope you will join me in finding this very interesting and exploring where this ends up going in the future so I will

end with some references that is here first of all the list of the various text editing CRD T's that I talked about in the context of interleaving and

finally the publications that I've worked on for the various algorithms and anomalies and problems that we talked about in the context of this talk all of

the slides are online so you can find them there thank you very much for listening I hope you enjoyed this talk and I'll see you again soon