Research and Development 1/^Archief/2009-2010/14/Pilot/OT

WAARSCHUWING

We zouden het fijn vinden als deze pagina niet meer verder gewijzigd werd. De tekst op deze pagina wordt gebruikt in ons verslag, en dat is dus de meest bijgewerkte versie. Enige wijzigingen aan deze pagina worden dus niet meer gebruikt. Bedankt.

Operational Transformation

Operaties

Een wavelet is opgebouwd uit operaties. Dit zijn meestal documentoperaties die op de inhoud van een wavelet werken, maar ook operaties die bijvoorbeeld deelnemers toevoegen of verwijderen. Een documentoperatie is opgebouwd uit mutaties. Een documentoperatie kan dus meer dan één mutatie bevatten. Operaties kunnen aan elkaar gekoppeld worden tot grotere operaties. Hierdoor zijn er minder operaties nodig voor een complete wavelet. Doordat een wavelet opgebouwd is uit operaties kan er makkelijk teruggedraaid worden naar een eerdere versie. De volgende mutaties voor documenten zijn er:

• skip
• insert characters
• insert element start
• insert element end
• insert anti-element start
• insert anti-element end
• delete characters
• delete element start
• delete element end
• delete anti-element start
• delete anti-element end
• set attributes
• update attributes
• commence annotation
• conclude annotation

Aan mutaties zelf worden geen posities meegegeven om aan te geven waar de mutatie plaats moet vinden, de positie wordt bepaald met de skipmutatie. Unicode-tekens en XML-tags zijn 1 item, en nemen dus 1 positie in. Het eerste item staat op positie 0. Operaties worden verstuurd in XML-documenten via het XMPP-protocol naar andere servers. Hoe die XML-documenten eruit zien staat hier. Hierin worden de operaties zelf met Base64 gecodeerd.

Operational Transformation

Als een wavelet door meerdere mensen wordt gewijzigd moet er voor gezorgd worden dat ondanks de vertragingen die er door o.a. de internetverbinding zijn gezorgd worden dat de operaties in de juiste volgorde en op de juiste positie uitgevoerd worden. Dit is Operational Transformation. Google Wave gebruikt hiervoor het al bestaande Jupiter-systeem, met wat aanpassingen..

Als er ergens bijvoorbeeld een teken wordt verwijderd, moeten van alle operaties verderop in de wavelet de posities met 1 worden verminderd om de operatie op de juiste positie plaats te laten vinden.Voorbeeld:

Hiervoor is het nodig dat de server weet wanneer een operatie werd uitgevoerd. Hiervoor houdt de wavelet zijn huidige versie bij, en krijgt elke operatie het versienummer van de wavelet op het moment voordat die operatie wordt uitgevoerd mee. Na het uitvoeren van operaties wordt het versienummer opgehoogd.

Google Wave voegt aan Jupiter toe dat de client vervolgens wacht op een bevestiging van de server voordat de volgende operatie wordt gestuurd. Dit gebeurt omdat dat voordelen biedt als er met veel mensen samengewerkt wordt. Als een client direct weer nieuwe operaties kan sturen, en de server ook, dan doorlopen client en server, afhankelijk van wanneer ze bepaalde operaties ontvangen, een heel verschillend pad door de transformaties:

De server moet deze state-space voor alle clients bijhouden, omdat niet allen de server en client verschillende paden doorlopen, maar ook alle clients dat doen. Dat kost erg veel geheugen. Als de server eerst een bevestiging stuurt, betekend dat dat hij de gestuurde operatie heeft getransformeerd, toegepast op zijn kopie van de wavelet en doorgestuurd. De client kan het pad dat de server doorloopt nu afleiden, en operaties sturen die op het pad van de server liggen. Doordat hierdoor het werk van de server vereenvoudigd wordt, en er minder bijgehouden hoeft te worden, hoeft de server maar één state-space voor alle clients samen bij te houden. Dit levert dus grote geheugenbesparingen op. Door operaties die ondertussen bij de client plaatsvinden samen te voegen kan de client wel alles versturen, ook als er sneller operaties bijkomen dan dat er een bevestiging terugkomt.

Conflicten
Er kan een conflict ontstaan als twee mensen op dezelfde positie verschillende tekst invoeren. Er moet een afspraak zijn wie er dan als eerste aan de beurt is. Deze afspraak is dat de gebruiker met grootste id eerst komt.
Als er twee mensen op dezelfde positie iets verwijderen is er geen probleem. Als beiden hetzelfde proberen te verwijderen moet dat immers gewoon verwijderd worden.

Compositie
Operaties kunnen worden samengevoegd tot één nieuwe operatie. De mutaties van meerdere operaties kunnen in één lijst worden gezet, maar er gebeurd meer. Als er tekst ingevoegd wordt die direct na elkaar komt kan dat worden samengevoegd tot één mutatie die die hele tekst invoegt. Hetzelfde geldt voor verwijderen. Toevoegen en verwijderen kunnen tegen elkaar wegvallen.

Bronnen:

• http://www.waveprotocol.org/whitepapers/operational-transform
• http://8477446762733596122-a-waveprotocol-org-s-sites.googlegroups.com/a/waveprotocol.org/wave-protocol/presentations/wave_federation_pub.pdf?attachauth=ANoY7crcr5TEXQTHW0m1SrghzkvnONOLFFhzOxhkPWm8uAswr8bZTQiZmKJCivUBulUxjxNSJFARcgmryZPujOKxgs3Yd5mib8oYyXnp8vExrHhOXamcqRvEvbdremQqCm43HUegK95_99XQI65L2IEJ0SrtPlj9ieD3Nwfvw8qSZ9sQkjd1SEDv5tZ24u2hj0ctr-bzQqMHVDXuD5PEine4M9X-3sNX3Ie8KG_ooM2pRVqMC0dEPXE%3D&attredirects=0
• http://jcit.org/files/csc562-project/report.pdf

Klassediagram

Een begin van de OT-implementatie is weergegeven in het volgende klassediagram:

Operation
In deze module staat de klasse Operation centraal. Operaties kunnen worden samengevoegd, getransformeerd en toegepast op een wavelet. Een operatie houdt een lijst van mutaties bij aangezien een operatie daaruit is opgebouwd. Aangezien documentoperaties en participantoperaties qua implementatie niet van elkaar verschillen, maar er alleen verschil is in de mutaties zijn er geen aparte klasses voor document- en participantoperaties.

Mutation
Mutaties worden gerepresenteerd door de klasse Mutation. Ze hebben een inverse, die opgevraagd word met invert. Verder kan een mutatie toegepast worden op een wavelet met apply en samengevoegd metmerge. Er zijn verschillende soorten mutaties die dit op verschillende manieren implementeren, dus Mutation is een pure abstracte klasse.

DocumentMutation
Er zijn verschillende documentmutaties, dus de klasse DocumentMutation is, net als Mutation abstract. Er zijn wel een aantal methodes die al geïmplementeerd kunnen worden. Alle soorten documentmutaties hebben een positie, die opgevraagd kan worden met getPosition en die gewijzigd kan worden met applyPositionChange. Ook kan de lengteverandering al berekend worden met de abstracte methoden getPreLength en getPostLength. Deze lengteverandering is nodig om te bepalen hoe de positie van de mutaties na deze mutatie veranderd moet worden.

ParticipantOperation
Ook van ParticipantMutations bestaan verschillende soorten, dus is ook deze klasse abstract. Aangezien ParticipantMutations altijd over een bepaalde deelnemer gaan, is er een veld participantId met bijbehorende get- en setmethodes om bij te houden over welke deelnemer het gaat.