Papers we love: Collaborative editing: hoe werkt dat eigenlijk?

 
01 februari 2017

Google drive, Microsoft office 365. Iedereen kent minimaal een van die producten. Maar hoe werken ze? Hoe kan er zo gemakkelijk met meerdere mensen aan een document gewerkt worden? Dat is precies wat ik me dus afvroeg. Na wat googlen kwam ik uit bij een artikel op Wikipedia, over Operational Transformation. Die pagina linkte weer naar een onderliggende paper die Concurrency control in groupware systems heet. Dit is dan ook de paper die ik deze maand wil bekijken.

In de paper wordt een algoritme beschreven om met meerdere deelnemers realtime samen te werken aan een document. Dit document leeft in de context van GROVE (group outline viewing edit), een programma wat in een inmiddels niet meer bestaand research instituut gemaakt is om het idee te valideren. Je kunt GROVE zien als een soort oerversie van Google Wave, waarbij er voor het eerst realtime samenwerking mogelijk is. Er worden wel enkele aannames gemaakt over het communicatie medium: berichten worden gegarandeerd afgeleverd en er is sprake van een “deliver-once” mechanisme.

Op het moment van schrijven (1989) was er geen manier bekend om realtime samen te kunnen werken aan documenten. Zoals te verwachten zijn er voor de hand liggende problemen wanneer er parallelle mutaties aan dezelfde datastructuur plaatsvinden. Traditionele oplossingen als locking of het rondgeven van een “handle”, een indicatie die aangeeft dat jij en alleen jij mutaties mag aanbrengen, zijn geen opties om samen te kunnen werken. Men was zich hier van bewust en besloot een oplossing te zoeken.

Deze oplossing kwam in de vorm van operational transformation, een methode waarin iedere operatie aan het document wordt gerepresenteerd door een commando. Deze commando’s zijn primitieven zoals delete(0) of insert(0, ‘H’). Als je deze commando’s uit zou voeren op de string “hello” krijg je dus na het eerste commando de string “ello”, wat na commando twee “Hello” geworden is. Dit is een goede basis, maar bied geen oplossing voor concurrency. Stel je voor dat er een zin “helo orld” is, welke gebruikers A en B beiden in beeld hebben. Gebruiker A wil een insert(2, ‘l’) doen, en gebruiker drie een insert(5, ‘W’). Wat er nu gebeurt is afhankelijk van de volgorde van het uitvoeren van de commando’s. In het ene geval krijg je “helloW orld”, in het andere geval “hello World”. Omdat de operaties in ieders lokale omgeving worden uitgevoerd kan ook bij iedereen de volgorde anders zijn. Laat staan wat er gebeurd als je met meer als twee personen aan het werk bent.

De crux om wel samen te kunnen werken zit hem in de nog niet toegelichte stap van de transformatie. Hierbij heb je een functie dat commando’s accepteert en een getransformeerde commando’s teruggeeft. Deze getransformeerde commando’s kun je op het andere, originele commando toepassen (compositie) waarna je onafhankelijk van de volgorde hetzelfde resultaat krijgt. Oftewel: transform(c1, c2) = (c1′, c2′), waarbij c1 ∘ c2′ ≡ c1′ ∘ c2. Hierdoor kun je dus commando’s uitvoeren op de state van een document zonder dat je je zorgen hoeft te maken dat de documenten gaan divergeren; volgordelijkheid is inmiddels immers niet meer belangrijk.

De exacte werking van deze transform-functie wordt dus in de paper toegelicht, dat ga ik hier niet met informeel taalgebruik herhalen. In het kort komt het er op neer dat zij een gedistribueerde variant van OT (dOPT) hebben geformuleerd. Deze werkt met zogenaamde state vectors en een bijbehorend request log, een historie van al toegepaste commandos. In een commando zit een zogenaamde “site identifier”, welke identificeert vanaf welke deelnemer het commando afkomstig is, een state vector, welke historie bevat van welke commando’s al zijn uitgevoerd op de betreffende state, een operatie en een prioriteit. Door de combinatie van de state vector en de eigen request log kan er voor ieder commando bepaald worden tegen welke state dit commando is uitgevoerd en hoe de transformatiefunctie op het gewenste resultaat kan uitkomen. Belangrijk is dat deze uitkomsten dus wel per deelnemer kunnen verschillen, aangezien deze deelnemers commando’s in een andere volgorde kunnen ontvangen.

Omdat dit nogal een vage beschrijving is en de paper erg formeel is wil ik jullie graag wijzen op een animatie. Deze is op github pages te vinden en laat je vanuit de browser eenvoudig experimenteren met het uitvoeren van commando’s. Dit is niet exact dezelfde oplossing als uit de paper, aangezien er hier gebruik wordt gemaakt van een decentrale variant van OT, maar het zit behoorlijk dicht bij elkaar. Ik kan jullie aanraden daar eens mee te spelen, het geeft een duidelijk inzicht in hoe tooling als Google drive ons samen laat werken aan documenten. Om goed te kunnen begrijpen is het handig om te weten hoe je de getekende diagram kunt lezen: deze heten diamond diagrams en daar is ook uitgebreide toelichting over te vinden.


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Gave Technologie