Powering Real-time Collaboration with Operational Transform

This talk will walk you through the building blocks including OTP, Phoenix PubSub, and Operational Transform to build your own coauthoring service. We'll also discuss reliability and scaling through with our real-world experiences building this in Slab.

Transcript

1. Real-time Collaboration in Elixir with Operational Transform ElixirConf US 2021 • Austin, TX
2. Find me anywhere @sheharyarn 02 Sheharyar Naseer Backend Engineer at Slab & 
 Manager at Google Developers Group
3. The Plan 03
4. Background – We build Slab – Solid foundation of Elixir & Phoenix – Technical Challenges – Collaboration – Consistency 04
5. The What – Build a simple text editor – Focus on real-time collaboration – Potential problems – How to solve them 05
6. The How – Discuss high-level architecture – Lay the groundwork – Implement a Document Server – Naive approach → The correct one – Solve problems along the way 06
7. Architecture 07
8. Architecture 08 Supervisor Document 1 Server Document 2 Server Document N Server Client 1 Client 2 Client N Phoenix Channels
9. Architecture 09 Supervisor Document 1 Server Document 2 Server Document N Server Client 1 Client 2 Client N Phoenix Channels
10. Architecture 10 Supervisor Document 1 Server Document 2 Server Document N Server Client 1 Client 2 Client N Phoenix Channels
11. Laying the Groundwork 11
12. Page and Template Router: scope "/", CollabWeb do pipe_through :browser get "/:id/", PageController, :show end 12 Controller: defmodule CollabWeb.PageController do use CollabWeb, :controller def show(conn, %{"id" => id}) do render(conn, "show.html", id: id) end end Template: <h2>Document ID: <%= @id %> </ h2> <textarea id="editor"> </ textarea>
13. GenServer defmodule Collab.Document do use GenServer alias Collab.Document.Supervisor def start_link(id), do: GenServer.start_link( __ MODULE __ , :ok, name: name(id)) def get_contents(id), do: GenServer.call(name(id), :get_contents) def update(id, data), do: GenServer.call(name(id), {:update, change, ver}) def open(id) do case GenServer.whereis(name(id)) do nil -> DynamicSupervisor.start_child(Supervisor, { __ MODULE __ , id}) pid -> {:ok, pid} end end defp name(id), do: {:global, {:doc, id}} end 13
14. Supervisor defmodule Collab.Document.Supervisor do use DynamicSupervisor def start_link(_args) do DynamicSupervisor.start_link( _ _ MODULE _ _ , :ok, name: _ _ MODULE __ ) end @impl true def init(:ok) do DynamicSupervisor.init(strategy: :one_for_one) end end 14 defmodule Collab.Application do use Application def start(_type, _args) do children = [ Collab.Document.Supervisor, # . .. ] # ... end
15. Websocket @impl true def join("doc:" <> id, _payload, socket) do {:ok, _pid} = Document.open(id) socket = assign(socket, :id, id) send(self(), :after_join) {:ok, socket} end @impl true def handle_info(:after_join, socket) do response = Document.get_contents(socket.assigns.id) push(socket, "open", response) {:noreply, socket} end 15
16. Websocket @impl true def handle_in("update", payload, socket) do case Document.update(socket.assigns.id, payload) do {:ok, response} -> broadcast_from!(socket, "update", response) {:reply, :ok, socket} {:error, reason} -> {:reply, {:error, reason}, socket} end end 16
17. Document Server 17
18. Implementation v1 SEND THE ENTIRE DOCUMENT 18 defmodule Collab.Document do # . . . @initial_state %{contents: ""} @impl true def init(:ok), do: {:ok, @initial_state} @impl true def handle_call(:get_contents, _from, state) do {:reply, state, state} end @impl true def handle_call({:update, contents}, _from, _state) do state = %{contents: contents} {:reply, state, state) end end
19. Implementation v1 SEND THE ENTIRE DOCUMENT 19 – New updates will overwrite old ones – Edits might be lost during collaboration – Consumes a lot more bandwidth – Solution: Send diffs
20. Implementation v2 SEND EDITS AS DIFFS 20 @initial_state %{contents: []} @impl true def handle_call(:get_contents, _from, state) do {:reply, state, state} end @impl true def handle_call({:update, change}, _from, state) do state = %{ contents: Delta.compose(state.contents, change) } {:reply, {:ok, change}, state} end
21. Implementation v2 SEND EDITS AS DIFFS 21 – Latency in multiple updates – Edits can be outdated – Server and client states will diverge – Solution: Consistency Models
22. Need for Speed Consistency – Latency & Disconnections – Edits don't reach server instantaneously – But must be applied locally – Combine changes from all clients – Final result is same everywhere 22
23. Operational Transform (OT) – Algorithm for Consistency Maintenance – Highly suited for text editing – Tracking edits and comparing versions – Transforms them on changes not yet seen 23
24. Delta for Elixir – Expressive format to describe contents and changes – Supports Operational Transform – Allows formatting & arbitrary attributes – In production for 4 years 24 document = [insert("Hello World!")] change = [ retain(6), delete(5), insert("ElixirConf"), ] Delta.compose(document, change) # = > [insert("Hello ElixirConf!")]
25. Implementation v3 SEND DIFFS + OPERATIONAL TRANSFORM 25 @initial_state %{ contents: [], changes: [], version: 0, } @impl true def handle_call(:get_contents, _from, state) do response = Map.take(state, [:version, :contents]) {:reply, response, state} end
26. Implementation v3 SEND DIFFS + OPERATIONAL TRANSFORM 26 @impl true def handle_call({:update, client_change, client_version}, _from, state) do edits_since = state.version - client_version transformed_change = state.changes |> Enum.take(edits_since) |> Enum.reverse() |> Enum.reduce(client_change, &Delta.transform(&1, &2, true)) state = %{ version: state.version + 1, changes: [transformed_change | state.changes], contents: Delta.compose(state.contents, transformed_change), } response = %{version: state.version, change: transformed_change} {:reply, {:ok, response}, state} end
27. Implementation v3 SEND DIFFS + OPERATIONAL TRANSFORM 27 onRemoteUpdate({ change, version }) { let remoteDelta = new Delta(change); if (this.edit) { remoteDelta = this.edit.transform(remoteDelta); if (this.queued) { remoteDelta = this.queued.transform(remoteDelta); } } this.contents = this.contents.compose(remoteDelta); this.version += 1; this.updateEditor(); }
28. Implementation v3 28 – Exhibits Eventual Consistency – But the cursor jumps around? – Solution: Also OT SEND DIFFS + OPERATIONAL TRANSFORM
29. Implementation v3.1 29 SEND DIFFS + OPERATIONAL TRANSFORM + CURSOR FIX onRemoteUpdate({ change, version }) { // ... const currentPosition = this.editor.selectionStart; const newPosition = remoteDelta.transformPosition(currentPosition); // ... this.editor.selectionStart = newPosition; this.editor.selectionEnd = newPosition; }
30. What's Next? 30
31. Going from here... – Rich-text editing and formatting – Persisting Data: What and how often – Multiple Cursors – Attribution, Comments and Embeds – Zero Downtime 31
32. Questions? We're hiring! Join us at slab.com/jobs Live Demo → collab.slabdev.com These Slides → shyr.io/t/real-time-collab Delta for Elixir → github.com/slab/delta-elixir shyr.io hi@shyr.io @sheharyarn