Announcing Delta for Elixir
We are excited to open-source our Elixir implementation of Delta – an expressive format to describe contents and changes that powers our real-time collaboration.
Today, we at Slab are excited to open-source our Elixir implementation of Delta – an expressive format to describe contents and changes.
Deltas are what power Slab's real-time collaborative editor, as well as the core data layer behind Quill, the popular rich-text editor for JavaScript. Deltas can describe any rich text document, including all text and formatting information, but without the ambiguity and complexity of HTML.
Background
When we set out to build a knowledge-base that teams would love to use, we knew that real-time collaboration had to be a key part of it.
The Delta format in JavaScript was already a part of building and open-sourcing Quill, complete with support for Operational Transform (OT). So it seemed appropriate to use Quill and Delta for Slab too.
We needed an Elixir implementation on the server as well which would accept the document diffs from the clients running in the browser, perform concurrency control and conflict resolution as part of synchronization, and update the document on the server and on clients in real-time.
Quick Overview
The core functionality of Delta is to track a document's contents and how it changes. Take the following document with the text "Gandalf the Grey" with "Gandalf" bolded and "Grey" in grey:
alias Delta.Op
gandalf = [
Op.insert("Gandalf", %{"bold" => true}),
Op.insert(" the "),
Op.insert("Grey", %{"color" => "#ccc"}),
]We can define a new change (intended to be applied to above), that keeps the first 12 characters, deletes the next 4, and inserts "White" text in white:
death = [
Op.retain(12),
Op.delete(4),
Op.insert("White", %{"color" => "#fff"}),
]Applying this change on our document results in:
Delta.compose(gandalf, death)
# => [
# %{"insert" => "Gandalf", "attributes" => %{"bold" => true}},
# %{"insert" => " the "},
# %{"insert" => "White", "attributes" => %{"color" => "#fff"}},
# ]Features
Here's a quick rundown of the features supported by Delta:
Consistent Document Model
The Delta format tracks the contents of documents, their formatting, attributes and changes over-time concisely and without ambiguity, allowing you to have a consistent data representation across different platforms.
Operational Transform
Delta implements the OT algorithm including compose, transform and invert. This is especially useful when building collaboration functionalities with concurrency and conflict-resolution.
Arbitrary Attributes
Delta supports generalized formatting with arbitrary attributes over a range of text. How they behave is up to you. Other than formatting, they can be used for tracking changes (including author or time), comments, annotations and references.
Op.insert("Slab <3 Elixir", %{"comment_thread_id" => 123})Simple and Custom Embeds
Delta has built-in support for simple embeds (e.g. image/video from a link), but is also configurable and extendable with custom handlers for more complex embed needs. This allows defining custom logic for composing and transforming the content inside embeds.
Op.insert(%{"image" => "https://app.com/logo.png"}, %{"alt" => "App Logo"})Example: Document Server with Delta
A real-life example would be utilizing the OTP features in Elixir to create a Document server which clients could connect to and perform updates to a document, fetch older versions, or undo operations.
Here's how you can write a simple implementation in Elixir that supports these features:
1. Create a GenServer
Let's start by writing a simple GenServer that represents a document and can return its contents:
defmodule Document do
use GenServer
# Define the default state with empty contents
@initial_state %{contents: []}
# Define a Public API
def start_link, do: GenServer.start_link(__MODULE__, :ok)
def get_contents(pid), do: GenServer.call(pid, :get_contents)
# Initialize the document with the default state
@impl true
def init(:ok), do: {:ok, @initial_state}
# Implement the :get_contents callback, which replies
# with the document contents
@impl true
def handle_call(:get_contents, _from, state) do
{:reply, state.contents, state}
end
endClients can now create and connect to our Document processes, fetching the contents (although they'll always be empty for now):
{:ok, pid} = Document.start_link()
# => {:ok, #PID<0.1747.0>}
Document.get_contents(pid)
# => []2. Accept Changes to the Document
Next, we'll add support for updating the document. The Document server should be able to accept changes or diffs, apply them, and return the up-to-date contents.
We'll add a new update(pid, change) method and a corresponding callback:
defmodule Document do
# ...
# Public API
def update(pid, change), do: GenServer.call(pid, {:update, change})
# Internal callback that applies the changes, updates the
# state, and returns the new contents
@impl true
def handle_call({:update, change}, _from, state) do
contents = Delta.compose(state.contents, change)
state = %{contents: contents}
{:reply, contents, state}
end
endNow clients can make changes to the document:
Document.get_contents(pid)
# => []
Document.update(pid, [Op.insert("Hello!")])
# => [%{"insert" => "Hello!"}]
Document.update(pid, [
Op.retain(5),
Op.insert(" world")
])
# => [%{"insert" => "Hello world!"}]3. Add Support for Undo
It will be really helpful if clients can undo the last change quickly.
While we can certainly keep track of all changes performed on the document, a better strategy would be to keep track of the "inverted" changes. For every change to a document, there exists an inverted version which cancels the effect of that change. Simply applying this inverted change will return the document contents prior to the change.
Delta supports this through the invert method:
base = [Op.insert("Jon: King in the North")]
change = [Op.retain(5), Op.delete(7), Op.insert("Warden of")]
inverted = Delta.invert(change, base)
# => [%{"retain" => 5}, %{"insert" => "King in"}, %{"delete" => 9}]
updated = Delta.compose(base, change)
# => [%{"insert" => "Jon: Warden of the North"}]
Delta.compose(updated, inverted)
# => [%{"insert" => "Jon: King in the North"}] # == baseWe can use this to implement the "undo" functionality. We'll update our state map to include an inverted_changes key and while we're at it let's also include a version integer to track how many changes have been performed on the document so far. Next, we'll modify our :update callback to push the inverted change in the list.
defmodule Document do
# ...
# Default state with empty contents
@initial_state %{
version: 0,
contents: [],
inverted_changes: [],
}
# Apply the change and return the updated contents
# Also track inverted versions of all changes
@impl true
def handle_call({:update, change}, _from, state) do
inverted = Delta.invert(change, state.contents)
state = %{
version: state.version + 1,
contents: Delta.compose(state.contents, change),
inverted_changes: [inverted | state.inverted_changes],
}
{:reply, state.contents, state}
end
endFinally, we'll add an undo(pid) method and a corresponding callback that simply reverts the last change.
defmodule Document do
# ...
# Public API
def undo(pid), do: GenServer.call(pid, :undo)
# Don't undo when document is already empty
@impl true
def handle_call(:undo, _from, %{version: 0} = state) do
{:reply, state.contents, state}
end
# Revert the last change, removing it from our stack
# and updating the contents
@impl true
def handle_call(:undo, _from, state) do
[last_change | changes] = state.inverted_changes
state = %{
version: state.version - 1,
contents: Delta.compose(state.contents, last_change),
inverted_changes: changes,
}
{:reply, state.contents, state}
end
endNote that the first :undo function clause handles documents with no changes, in which case it doesn't do anything. Let's try it out in IEx:
# We're creating a new document here. Reusing older document
# pids will fail because the state map has changed.
{:ok, pid} = Document.start_link
# => {:ok, #PID<0.230.0>}
Document.update(pid, [Op.insert("Hello world!")])
# => [%{"insert" => "Hello world!"}]
Document.update(pid, [Op.retain(6), Op.delete(5), Op.insert(" Elixir")])
# => [%{"insert" => "Hello Elixir!"}]
Document.undo(pid)
# => [%{"insert" => "Hello world!"}]
Document.undo(pid)
# => []4. View Document History
We want to allow clients to observe how a document changed over time. Like our undo functionality, one way would be to keep track of all changes and "replay" them on an empty document one-by-one to achieve our desired result, but since we're already tracking inverted changes, we can instead start from the current state of the document and revert the changes until we get to our document's initial state.
Again, we'll add a public get_history(pid) method and a corresponding callback that implements its functionality:
defmodule Document do
# ...
def get_history(pid), do: GenServer.call(pid, :get_history)
@impl true
def handle_call(:get_history, _from, state) do
current = {state.version, state.contents}
history =
Enum.scan(state.inverted_changes, current, fn inverted, {version, contents} ->
contents = Delta.compose(contents, inverted)
{version - 1, contents}
end)
{:reply, [current | history], state}
end
endHere we use Enum.scan/3 to compose each inverted change in the reverse order, until we get to the beginning, finally returning a list of document versions and contents at each point. Trying it out:
# Make multiple changes to a document
Document.update(pid, [Op.insert("Slab <3 Ruby")])
Document.update(pid, [Op.retain(8), Op.delete(4), Op.insert("Elixir")])
Document.update(pid, [Op.retain(8), Op.retain(6, %{"italic" => true})])
Document.get_history(pid)
# => [
# {3, [%{"insert" => "Slab <3 "}, %{"insert" => "Elixir", "attributes" => %{"italic" => true}}]},
# {2, [%{"insert" => "Slab <3 Elixir"}]},
# {1, [%{"insert" => "Slab <3 Ruby"}]},
# {0, []}
# ]Similarly, we might want to allow clients to view the diff between two versions of the document in any order. In this case, it might be useful to store both changes and the inverted_changes so we can start from any point in the document's history and quickly go both forward and backward. Continuing from our current implementation, this would not be much harder and so, this exercise is left for our readers.
Complete Code
Combining all of the above, the final code for our Document server looks like this:
defmodule Document do
use GenServer
@initial_state %{
# Number of changes made to the document so far
version: 0,
# An up-to-date Delta with all changes applied, representing
# the current state of the document
contents: [],
# The `inverted` versions of all changes performed on the
# document (useful for viewing history or undo the changes)
inverted_changes: [],
}
# Public API
# ----------
def start_link, do: GenServer.start_link(__MODULE__, :ok)
def stop(pid), do: GenServer.stop(pid)
def update(pid, change), do: GenServer.call(pid, {:update, change})
def get_contents(pid), do: GenServer.call(pid, :get_contents)
def get_history(pid), do: GenServer.call(pid, :get_history)
def undo(pid), do: GenServer.call(pid, :undo)
# GenServer Callbacks
# -------------------
# Initialize the document with the default state
@impl true
def init(:ok), do: {:ok, @initial_state}
# Apply a given change to the document, updating its contents
# and incrementing the version
#
# We also keep track of the inverted version of the change
# which is useful for performing undo or viewing history
@impl true
def handle_call({:update, change}, _from, state) do
inverted = Delta.invert(change, state.contents)
state = %{
version: state.version + 1,
contents: Delta.compose(state.contents, change),
inverted_changes: [inverted | state.inverted_changes],
}
{:reply, state.contents, state}
end
# Fetch the current contents of the document
@impl true
def handle_call(:get_contents, _from, state) do
{:reply, state.contents, state}
end
# Revert the applied changes one by one to see how the
# document transformed over time
@impl true
def handle_call(:get_history, _from, state) do
current = {state.version, state.contents}
history =
Enum.scan(state.inverted_changes, current, fn inverted, {version, contents} ->
contents = Delta.compose(contents, inverted)
{version - 1, contents}
end)
{:reply, [current | history], state}
end
# Don't undo when document is already empty
@impl true
def handle_call(:undo, _from, %{version: 0} = state) do
{:reply, state.contents, state}
end
# Revert the last change, removing it from our stack and
# updating the contents
@impl true
def handle_call(:undo, _from, state) do
[last_change | changes] = state.inverted_changes
state = %{
version: state.version - 1,
contents: Delta.compose(state.contents, last_change),
inverted_changes: changes,
}
{:reply, state.contents, state}
end
endHere's a quick recap of all the features supported by our GenServer and how they work. Clients can create new documents or make changes to existing ones by interacting with our API:
{:ok, pid} = Document.start_link
# => {:ok, #PID<0.1747.0>}
Document.update(pid, [Op.insert("Hello!")])
# => [%{"insert" => "Hello!"}]
Document.update(pid, [
Op.retain(5),
Op.insert(" world")
])
# => [%{"insert" => "Hello world!"}]
Document.update(pid, [
Op.retain(6),
Op.delete(5),
Op.insert("Elixir", %{"color" => "purple"})
])
# => [%{"insert" => "Hello "}, %{"insert" => "Elixir", "attributes" => %{"color" => "purple"}}, %{"insert" => "!"}]
Document.get_history(pid)
# => [
# {3, [%{"insert" => "Hello "}, %{"attributes" => %{"color" => "purple"}, "insert" => "Elixir"}, %{"insert" => "!"}]},
# {2, [%{"insert" => "Hello world!"}]},
# {1, [%{"insert" => "Hello!"}]},
# {0, []}
# ]
Document.undo(pid)
# => [%{"insert" => "Hello world!"}]
Document.get_history(pid)
# => [
# {2, [%{"insert" => "Hello world!"}]},
# {1, [%{"insert" => "Hello!"}]},
# {0, []}
# ]Conclusion
Elixir is the modern technology of choice today in building scalable and concurrent real-time applications. Phoenix in 2015 made waves in supporting 2 million simultaneous clients. With the release of Delta, we hope to help address the difficult real-world challenge of conflict resolution, in order to enable highly collaborative real-time experiences.
Running reliably in production at Slab for almost 4 years now, we're confident in sharing a core piece of our technology with the Elixir community, and excited to see what applications and experiences you build from it. We'd love to hear your comments, feedback and if there's anything else about Elixir or OTP you would like to learn more about.
Continue Reading other Behind Slab articles
