logo

Kolaborativní střih v JavaScriptu:Úvod do provozní transformace

Rozhodl jsem se vytvořit robustní editor kódu pro spolupráci na webu. Jmenuje se Codr a umožňuje vývojářům spolupracovat v reálném čase – například Dokumenty Google pro kód. Pro webové vývojáře slouží Codr jako sdílená reaktivní pracovní plocha, kde je každá změna okamžitě vykreslena pro všechny diváky. Podívejte se na nově spuštěnou kampaň Codr na Kickstarter, kde se dozvíte více.

Kolaborativní editor umožňuje více lidem upravovat stejný dokument současně a vzájemně si prohlížet své úpravy a změny výběru, jak k nim dojde. Souběžné úpravy textu umožňují poutavou a efektivní spolupráci, která by jinak byla nemožná. Sestavení Codr mi umožnilo lépe porozumět a (doufám) sdělit, jak vytvořit rychlou a spolehlivou aplikaci pro spolupráci.

Výzva

Pokud jste vytvořili společný editor nebo jste mluvili s někým, kdo to udělal, pak víte, že ladné zvládnutí souběžných úprav ve víceuživatelském prostředí je náročné. Ukazuje se však, že několik relativně jednoduchých konceptů tento problém značně zjednodušuje. Níže se podělím o to, co jsem se v tomto ohledu naučil prostřednictvím budování Codr.

Primárním problémem spojeným s kolaborativními úpravami je kontrola souběžnosti. Codr používá kontrolní mechanismus souběžnosti založený na provozní transformaci (OT). Pokud si chcete přečíst něco o historii a teorii OT, podívejte se na stránku wikipedie. Níže představím některé teorie, ale tento příspěvek je zamýšlen jako průvodce implementátorem a je spíše praktický než abstraktní.

Codr je postaven v JavaScriptu a příklady kódu jsou v JavaScriptu. Pro podporu společných úprav je třeba sdílet významnou logiku mezi serverem a klientem, takže backend uzlu/iojs je vynikající volbou. V zájmu čitelnosti jsou příklady kódu v ES6.

Naivní přístup ke společné editaci

V prostředí s nulovou latencí můžete napsat editor pro spolupráci, jako je tento:

Klient 

editor.on('edit', (operation) => 
    socket.send('edit', operation));
socket.on('edit', (operation) => 
    editor.applyEdit(operation));

Server 

socket.on('edit', (operation) => {
    document.applyEdit(operation);
    getOtherSockets(socket).forEach((otherSocket) => 
        otherSocket.emit('edit', operation)
    );
});

Každá akce je koncipována jako vložení nebo smazat úkon. Každá operace je:

  1. Místně použito v komponentě pro úpravy
  2. Odesláno na server
  3. Použito na kopii dokumentu na straně serveru
  4. Vysílejte dalším vzdáleným editorům
  5. Místně použito na kopii dokumentu každého vzdáleného editora

Latency Breaks Things

Když však zavedete latenci mezi klientem a serverem, narazíte na problémy. Jak jste pravděpodobně předpokládali, latence v kolaborativním editoru představuje možnost konfliktů verzí. Například:

Počáteční stav dokumentu:

bcd

Uživatel 1 vloží a na začátku dokumentu. Operace vypadá takto:

{
    type: 'insert',
    lines: ['a'],
    range: {
        start: { row: 0, column: 0}
        end: {row: 0, column: 1}
    }
}

Zároveň Uživatel 2 typy e na konci dokumentu:

{
    type: 'insert',
    lines: ['e'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 4}
    }
}

Co by měl stalo se, že Uživatel 1 a Uživatel 2 skončí s:

abcde

Ve skutečnosti Uživatel 1 vidí:

bcd    <-- Starting Document State
abcd   <-- Apply local "insert 'a'" operation at offset 0
abced  <-- Apply remote "insert 'e'" operation at offset 3

A Uživatel 2 vidí:

bcd    <-- Starting Document State
bcde   <-- Apply local "insert 'e'" operation at offset 3
abcde  <-- Apply remote "insert 'a'" operation at offset 0

Jejda! 'abced' != 'abcde' - sdílený dokument je nyní v nekonzistentním stavu.

Snadná oprava je příliš pomalá

K výše uvedenému konfliktu dochází, protože každý uživatel „optimisticky“ aplikuje úpravy lokálně, aniž by se nejprve ujistil, že úpravy neprovádí nikdo jiný. Od Uživatele 1 změnil dokument z části Uživatel 2 , došlo ke konfliktu. Uživatel 2 operace úprav předpokládá stav dokumentu, který v době, kdy je aplikován na Uživatele 1, již neexistuje 's dokument.

Jednoduchá oprava spočívá v přechodu na pesimistický model řízení souběžnosti, kde každý klient požaduje výhradní zámek proti zápisu ze serveru před místní aplikací aktualizací. Tím se zcela vyhnete konfliktům. Bohužel zpoždění vyplývající z takového přístupu na průměrném internetovém připojení by editor učinilo nepoužitelným.

Operační transformace k záchraně

Operational Transformation (OT) je technika, která podporuje souběžné úpravy bez kompromisů ve výkonu. Pomocí OT každý klient optimisticky aktualizuje svůj vlastní dokument lokálně a implementace OT zjistí, jak automaticky vyřešit konflikty.

OT nařizuje, že když aplikujeme vzdálenou operaci, nejprve operaci „transformujeme“, abychom kompenzovali konfliktní úpravy od jiných uživatelů. Cíle jsou dvojí:

  1. Zajistěte, aby všichni klienti měli konzistentní stavy dokumentu
  2. Zajistěte, aby byl zachován záměr každé operace úprav

V mém původním příkladu bychom chtěli transformovat Uživatele 2 operace vložení, která se má vložit s posunem znaků 4 místo offsetu 3 když jej použijeme na Uživatele 1 's dokument. Tímto způsobem respektujeme Uživatele 2 záměr uživatele vložte e po d a zajistit, aby oba uživatelé skončili se stejným stavem dokumentu.

Pomocí OT, Uživatel 1 uvidí:

bcd    <-- Starting Document State
abcd   <-- Apply local "insert 'a'" operation at offset 0
abcde  <-- Apply TRANSFORMED "insert 'e'" operation at offset 4

A Uživatel 2 uvidí:

bcd    <-- Starting Document State
bcde   <-- Apply local "insert 'e'" operation at offset 3
abcde  <-- Apply remote "insert 'a'" operation at offset 0

Životní cyklus operace

Užitečným způsobem, jak vizualizovat, jak jsou úpravy synchronizovány pomocí OT, je představit si společný dokument jako úložiště git:

  1. Operace úprav jsou potvrzení
  2. Server je hlavní větev
  3. Každý klient je tematickou větví od master

Sloučení úprav do hlavního serveru (na straně serveru) Když provedete úpravu v Codr, dojde k následujícímu:

  1. Klient Codr se větví z master a lokálně použije vaši úpravu
  2. Klient Codr odešle serveru požadavek na sloučení

Zde je gitův krásný (mírně upravený) diagram. Dopisy odkazující na potvrzení (operace):

Před sloučením: 

      A topic (client)
     /
    D---E---F master (server)

Po sloučení: 

      A ------ topic
     /         \
    D---E---F---G master

K provedení sloučení server aktualizuje (transformuje) operaci A takže to stále dává smysl ve světle předchozích operací E a F , pak použije transformovanou operaci (G ) zvládnout. Transformovaná operace je přímo analogická git merge commit.

Převedení na hlavní (na straně klienta) Poté, co je operace transformována a aplikována na straně serveru, je vysílána ostatním klientům. Když klient obdrží změnu, provede ekvivalent git rebase:

  1. Vrátí všechny „nevyřízené“ (nesloučené) místní operace
  2. Použije vzdálené ovládání
  3. Znovu použije čekající operace a transformuje každou operaci na novou operaci ze serveru

Tím, že změní základ klienta místo sloučení vzdálené operace, jak se to děje na straně serveru, Codr zajistí, že úpravy budou aplikovány ve stejném pořadí u všech klientů.

Vytvoření kanonického pořadí operací úprav

Důležité je pořadí, ve kterém jsou operace úprav aplikovány. Představte si, že dva uživatelé zadají znaky a a b současně při stejném ofsetu dokumentu. Pořadí, ve kterém se operace provádějí, určí, zda ab nebo ba je ukázáno. Vzhledem k tomu, že latence je proměnná, nemůžeme s jistotou vědět, v jakém pořadí se události skutečně odehrály, ale je důležité, aby se všichni klienti shodli na stejném objednávání akcí. Codr považuje pořadí, ve kterém události přicházejí na server, za kanonické pořadí.

Server ukládá číslo verze dokumentu, které se zvýší při každém použití operace. Když server přijme operaci, označí operaci číslem aktuální verze, než ji rozešle ostatním klientům. Server také odešle klientovi zprávu o zahájení operace s uvedením nové verze. Tímto způsobem každý klient ví, jaká je jeho "verze serveru".

Kdykoli klient odešle operaci na server, odešle také aktuální verzi serveru klienta. To říká serveru, kde se klient "rozvětvil", takže server ví, proti jakým předchozím operacím je třeba novou změnu transformovat.

Transformace operace

Jádrem Codrovy OT logiky je tato funkce:

function transformOperation(operation1, operation2) {
    // Modify operation2 such that its intent is preserved
    // subsequent to intervening change operation1
}

Nebudu se zde rozepisovat o celé logice, protože se to zapojuje, ale zde jsou některé příklady:

  1. Pokud op1 vložený řádek(y) před op2 's řádek, zvyšte op2 's řádkový offset odpovídajícím způsobem.

  2. Pokud op1 vložený text před op2 na stejném řádku zvyšte op2 příslušně odsazený znak.

  3. Pokud op1 došlo zcela po op2 , pak nic nedělejte.

  4. Pokud op1 vloží text do rozsahu op2 odstraní a poté zvětší op2 's rozsah odstranění pro zahrnutí vloženého textu a přidání vloženého textu. Poznámka :Dalším přístupem by bylo rozdělení op2 na dvě akce odstranění, jednu na každé straně op1 vložení 's, čímž se zachová vložený text.

  5. Pokud op1 a op2 jsou operace odstranění rozsahu a rozsahy se překrývají, pak se zmenší op2 rozsah mazání 's tak, aby zahrnoval pouze text NEODSTRANĚNÝ op1 .

Synchronizace pozice a výběru kurzoru

Uživatelský výběr je jednoduše rozsah textu. Pokud start a end body rozsahu jsou stejné, pak rozsah je sbalený kurzor. Když se změní výběr uživatele, klient odešle nový výběr na server a server tento výběr rozešle ostatním klientům. Stejně jako u editačních operací Codr transformuje výběr proti konfliktním operacím od jiných uživatelů. Transformační logika pro výběr je jednoduše podmnožinou logiky potřebné k transformaci insert nebo delete operace.

Vrátit zpět/Znovu

Codr dává každému uživateli vlastní zásobník zpět. To je důležité pro dobrý zážitek z úprav:jinak stiskněte CMD+Z mohl vrátit zpět úpravy někoho jiného v jiné části dokumentu.

Poskytnutí vlastního zásobníku zpět každému uživateli také vyžaduje OT. Ve skutečnosti jde o jeden případ, kdy by OT bylo nutné i v prostředí s nulovou latencí. Představte si následující scénář:

abc     <-- User 1 types "abc"
abcde   <-- User 2 types "de"
ce      <-- User 1 deletes "bcd"
??      <-- User 2 hits CMD+Z

Uživatel2 poslední akce uživatele byla:

{
    type: 'insert',
    lines: ['de'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 5}
    }
}

Inverzní (zpět) akce by byla:

{
    type: 'delete',
    lines: ['de'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 5}
    }
}

Ale evidentně nemůžeme použít jen inverzní akci. Díky Uživateli 1 ' s intervenující změnou, již neexistuje posun znaků 3 v dokumentu!

Opět můžeme použít OT:

var undoOperation = getInverseOperation(myLastOperation);
getOperationsAfterMyLastOperation().forEach((operation) => 
    transformOperation(operation, undoOperation);
);
editor.applyEdit(undoOperation);
socket.emit('edit', undoOperation);

Transformací operace undo proti následným operacím z jiných klientů Codr místo toho použije následující operaci na undo, čímž dosáhne požadovaného chování.

{
    type: 'delete',
    lines: ['e'],
    range: {
        start: { row: 0, column: 1}
        end: {row: 0, column: 2}
    }
}

Správná implementace undo/redo je jedním z nejnáročnějších aspektů vytváření kolaborativního editoru. Úplné řešení je poněkud složitější než to, co jsem popsal výše, protože potřebujete vrátit zpět souvislé vložení a odstranění jako jednotku. Od operací, které byly souvislý se může stát nesouvislým kvůli úpravám provedeným jinými spolupracovníky, to není triviální. Co je ale skvělé, je, že můžeme znovu použít stejné OT, které se používá pro synchronizaci úprav, abychom dosáhli historie vracení pro jednotlivé uživatele.

Závěr

OT je výkonný nástroj, který nám umožňuje vytvářet vysoce výkonné aplikace pro spolupráci s podporou neblokujících souběžných úprav. Doufám, že toto shrnutí společné implementace Codr poskytuje užitečný výchozí bod pro pochopení OT. Velké díky Davidovi za jeho pozvání, abych mohl sdílet tento kousek na jeho blogu.

Chcete se dozvědět více o Codr? Podívejte se na kampaň KickStarter nebo tweetujte na @CodrEditor a požádejte o pozvánku.