path: root/doc/easysync/easysync-full-description.tex

\documentclass{article} 
\usepackage{hyperref}

\begin{document}

\title{Etherpad and EasySync Technical Manual}
\author{AppJet, Inc., with modifications by the Etherpad Foundation}
\date{\today}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Documents}
\begin{itemize}
\item A document is a list of characters, or a string.
\item A document can also be represented as a list of \emph{changesets}.
\end{itemize}

\section{Changesets}

\begin{itemize}
\item A changeset represents a change to a document.
\item A changeset can be applied to a document to produce a new document.
\item When a document is represented as a list of changesets, it is assumed that the first changeset applies to the empty document, [].
\end{itemize}


\section{Changeset representation} \label{representation}

$$(\ell \rightarrow \ell')[c_1,c_2,c_3,...]$$

where

\begin{itemize}
\item[] $\ell$ is the length of the document before the change,
\item[] $\ell'$ is the length of the document after the change,
\item[] $[c_1,c_2,c_3,...]$ is an array of $\ell'$ characters that described the document after the change.
\end{itemize}

Note that $\forall c_i : 0 \leq i \leq \ell'$ is either an integer or a character.

\begin{itemize}
\item Integers represent retained characters in the original document.
\item Characters represent insertions.
\end{itemize}

\section{Constraints on Changesets}

\begin{itemize}
\item Changesets are canonical and therefor comparable.  When represented in computer memory, we always use the same representation for the same changeset.  If the memory representation of two changesets differ, they must be different changesets.
\item Changesets are compact.  Thus, if there are two ways to represent a changeset in computer memory, then we always use the representation that takes up the fewest bytes.
\end{itemize}

Later we will discuss optimizations to changeset
representation (using ``strips'' and other such
techniques).  The two constraints must apply to any
representation of changesets.

\section{Notation}

\begin{itemize}
\item We use the algebraic multiplication notation to represent changeset application.
\item While changesets are defined as operations on documents, documents themselves are represented as a list of changesets, initially applying to the empty document.
\end{itemize}

\paragraph{Example}
$A=(0\rightarrow 5)[``hello"]$
$B=(5\rightarrow 11)[0-4, ``\ world"]$

We can write the document ``hello world'' as $A\cdot B$ or
just $AB$.  Note that the ``initial document'' can be made
into the changeset $(0\rightarrow
N)[``<\mathit{the\ document\ text}>"]$.

When $A$ and $B$ are changesets, we can also refer to $(AB)$ as ``the composition'' of $A$ and $B$.  Changesets are closed under composition.

\section{Composition of Changesets}

For any two changesets $A$, $B$ such that

\begin{itemize}
\item[] $A=(n_1\rightarrow n_2)[\cdots]$
\item[] $B=(n_2\rightarrow n_3)[\cdots]$
\end{itemize}
it is clear that there is a third changeset $C=(n_1\rightarrow n_3)[\cdots]$ such that applying $C$ to a document $X$ yields the same resulting document as does applying $A$ and then $B$.  In this case, we write $AB=C$.

Given the representation from Section \ref{representation}, it is straightforward to compute the composition of two changesets.

\section{Changeset Merging}

Now we come to realtime document editing.  Suppose two different users make two different changes to the same document at the same time.  It is impossible to compose these changes.    For example, if we have the document $X$ of length $n$, we may have $A=(n\rightarrow n_a)[\ldots n_a \mathrm{characters}]$,  $B=(n\rightarrow n_b)[\ldots n_b \mathrm{characters}]$ where $n\neq n_a\neq n_b$.

It is impossible to compute $(XA)B$ because $B$ can only be applied to a document of length $n$, and $(XA)$ has length $n_a$.  Similarly, $A$ cannot be applied to $(XB)$ because $(XB)$ has length $n_b$.

This is where \emph{merging} comes in.  Merging takes two changesets that apply to the same initial document (and that cannot be composed), and computes a single new changeset that preserves the intent of both changes.  The merge of $A$ and $B$ is written as $m(A,B)$.  For the Etherpad system to work, we require that $m(A,B)=m(B,A)$.

Aside from what we have said so far about merging, there are many different implementations that will lead to a workable system.  We have created one implementation for text that has the following constraints.

\section{Follows} \label{follows}

When users $A$ and $B$ have the same document $X$ on their screen, and they proceed to make respective changesets $A$ and $B$, it is no use to compute $m(A,B)$, because $m(A,B)$ applies to document $X$, but the users are already looking at document $XA$ and $XB$.  What we really want is to compute $B'$ and $A'$ such that
$$XAB' = XBA' = Xm(A,B)$$

``Following'' computes these $B'$ and $A'$ changesets.  The definition of the ``follow'' function $f$ is such that $Af(A,B)=Bf(B,A)=m(A,B)=m(B,A)$.  When we compute $f(A,B)$
\begin{itemize}
\item Insertions in $A$ become retained characters in $f(A,B)$
\item Insertions in $B$ become insertions in $f(A,B)$
\item Retain whatever characters are retained in \emph{both} $A$ and $B$
\end{itemize}

\paragraph{Example}

Suppose we have the initial document $X=(0\rightarrow 8)[``\mathit{baseball}"]$ and user $A$ changes it to ``basil'' with changeset $A$, and user $B$ changes it to ``below'' with changeset $B$.

We have
$X=(0\rightarrow 8)[``\mathit{baseball}"]$ \\
$A=(8\rightarrow 5)[0-1, ``\mathit{si}", 7]$ \\
$B=(8\rightarrow 5)[0, ``\mathit{e}", 6, ``\mathit{ow}"]$ \\

First we compute the merge $m(A,B)=m(B,A)$ according to the constraints

$$m(A,B)=(8\rightarrow 6)[0, "e", "si", "ow"] = (8\rightarrow 6)[0, ``\mathit{esiow}"]$$

Then we need to compute the follows $B'=f(A,B)$ and $A'=f(B,A)$.

$$B'=f(A,B)=(5\rightarrow 6)[0,``\mathit{e}",2,3,``\mathit{ow}"]$$

Note that the numbers $0$, $2$, and $3$ are indices into $A=(8\rightarrow 5)[0,1,``\mathit{si}",7]$

\begin{tabular}{ccccc}
0 & 1 & 2 & 3 & 4 \\
0 & 1 & s & i & 7
\end{tabular}

$A'=f(B,A)=(5\rightarrow 6)[0,1,"si",3,4]$

We can now double check that $AB'=BA'=m(A,B)=(8\rightarrow 6)[0,``\mathit{esiow}"]$.

Now that we have made the mathematical meaning of the
preceding pages complete, we can build a client/server
system to support realtime editing by multiple users.

\section{System Overview}

There is a server that holds the current state of a
document.  Clients (users) can connect to the server from
their web browsers.  The clients and server maintain state
and can send messages to one another in real-time, but
because we are in a web browser scenario, clients cannot
send each other messages directly, and must go through the
server always.  (This may distinguish from prior art?)

The other critical design feature of the system is that
\emph{A client must always be able to edit their local
  copy of the document, so the user is never blocked from
  typing because of waiting to send or receive data.}

\section{Client State}

At any moment in time, a client maintains its state in the
form of 3 changesets.  The client document looks like
$A\cdot X \cdot Y$, where

$A$ is the latest server version, the composition of all
changesets committed to the server, from this client or
from others, that the server has informed this client
about.  Initially $A=(0\rightarrow N)[<\mathit{initial\ document\ text}>]$.

$X$ is the composition of all changesets this client has
submitted to the server but has not heard back about yet.
Initially $X=(N\rightarrow N)[0,1,2,\ldots, N-1]$, in
other words, the identity, henceforth denoted $I_N$.

$Y$ is the composition of all changesets this client has
made but has not yet submitted to the server yet.
Initially $Y=(N\rightarrow N)[0,1,2,\ldots, N-1]$.

\section{Client Operations}

A client can do 5 things.

\begin{enumerate}
\item Incorporate new typing into local state
\item Submit a changeset to the server
\item Hear back acknowledgement of a submitted changeset
\item Hear from the server about other clients' changesets
\item Connect to the server and request the initial document
\end{enumerate}

As these 5 events happen, the client updates its
representation $A\cdot X \cdot Y$ according to the
relations that follow.  Changes ``move left'' as time goes
by: into $Y$ when the user types, into $X$ when change
sets are submitted to the server, and into $A$ when the
server acknowledges changesets.

\subsection{New local typing}

When a user makes an edit $E$ to the document, the client
computes the composition $(Y\cdot E)$ and updates its local
state, i.e. $Y \leftarrow Y\cdot E$.  I.e., if $Y$ is the
variable holding local unsubmitted changes, it will be
assigned the new value $(Y\cdot E)$.

\subsection{Submitting changesets to server}

When a client submit its local changes to the server, it
transmits a copy of $Y$ and then assigns $Y$ to $X$, and
assigns the identity to $Y$.  I.e.,

\begin{enumerate}
\item Send $Y$ to server,
\item $X \leftarrow Y$
\item $Y \leftarrow I_N$
  (the identity).
\end{enumerate}

This happens every 500ms as long as it receives an
acknowledgement.  Must receive ACK before submitting
again.  Note that $X$ is always equal to the identity
before the second step occurs, so no information is lost.

\subsection{Hear ACK from server}

When the client hears ACK from server,

$A \leftarrow A\cdot X$ \\
$X \leftarrow I_N$

\subsection{Hear about another client's changeset}

When a client hears about another client's changeset $B$,
it computes a new $A$, $X$, and $Y$, which we will call
$A'$, $X'$, and $Y'$ respectively.  It also computes a
changeset $D$ which is applied to the current text view on
the client, $V$.  Because $AXY$ must always equal the
current view, $AXY=V$ before the client hears about $B$,
and $A'X'Y'=VD$ after the computation is performed.

The steps are:

\begin{enumerate}
\item Compute $A' = AB$
\item Compute $X' = f(B,X)$
\item Compute $Y' = f(f(X,B), Y)$
\item Compute $D=f(Y,f(X,B))$
\item Assign $A \leftarrow A'$, $X \leftarrow X'$, $Y \leftarrow Y'$.
\item Apply $D$ to the current view of the document
  displayed on the user's screen.
\end{enumerate}

In steps 2,3, and 4, $f$ is the follow operation described
in Section \ref{follows}.

\paragraph{Proof that $\mathbf{AXY=V \Rightarrow A'X'Y'=VD}$.}
Substituting $A'X'Y'=(AB)(f(B,X))(f(f(X,B),Y))$, we
recall that merges are commutative.  So for any two
changesets $P$ and $Q$, 
$$m(P,Q)=m(Q,P)=Qf(Q,P)=Pf(P,Q)$$

Applying this to the relation above, we see
\begin{eqnarray*}
A'X'Y'&=& AB f(B,X) f(f(X,B),Y) \\
      &=&AX f(X,B) f(f(X,B),Y) \\
      &=&A X Y f(Y, f(X,B)) \\
      &=&A X Y D \\
      &=&V D 
\end{eqnarray*}
As claimed.

\subsection{Connect to server}

When a client connects to the server for the first time,
it first generates a random unique ID and sends this to
the server.  The client remembers this ID and sends it
with each changeset to the server.

The client receives the latest version of the document
from the server, called HEADTEXT.  The client then sets

\begin{itemize}
\item[] $A \leftarrow \mathrm{HEADTEXT}$
\item[] $X \leftarrow I_N$
\item[] $Y \leftarrow I_N$
\end{itemize}

And finally, the client displays HEADTEXT on the screen.

\section{Server Overview}

Like the client(s), the server has state and performs
operations.  Operations are only performed in response to
messages from clients.

\section{Server State}

The server maintains a document as an ordered list of
\emph{revision records}.  A revision record is a data
structure that contains a changeset and authorship
information.

\begin{verbatim}
RevisionRecord = {
  ChangeSet,
  Source (unique ID),
  Revision Number (consecutive order, starting at 0)
}
\end{verbatim}

For efficiency, the server may also store a variable
called HEADTEXT, which is the composition of all
changesets in the list of revision records.  This is an
optimization, because clearly this can be computed from
the set of revision records.

\section{Server Operations Overview}

The server does two things in addition to maintaining
state representing the set of connected clients and
remembering what revision number each client is up to date
with:

\begin{enumerate}
\item Respond to a client's connection requesting the initial document.
\item Respond to a client's submission of a new changeset.
\end{enumerate}

\subsection{Respond to client connect}
When a server receives a connection request from a client,
it receives the client's unique ID and stores that in the
server's set of connected clients.  It then sends the
client the contents of HEADTEXT, and the corresponding
revision number.  Finally the server notes that this
client is up to date with that revision number.

\subsection{Respond to client changeset}

When the server receives information from a client about
the client's changeset $C$, it does five things:

\begin{enumerate}
\item Notes that this change applies to revision number
  $r_c$ (the client's latest revision).
\item Creates a new changeset $C'$ that is relative to the
  server's most recent revision number, which we call
  $r_H$ ($H$ for HEAD).  $C'$ can be computed using
  follows (Section \ref{follows}).  Remember that the server has a series of
  changesets, 
$$S_0\rightarrow S_1\rightarrow \ldots S_{r_c}\rightarrow S_{r_c+1} \rightarrow \ldots \rightarrow S_{r_H} $$
$C$ is relative to $S_{r_c}$, but we need to compute $C'$ relative to $S_{r_H}$.
We can compute a new $C$ relative to $S_{r_c+1}$ by computing $f(S_{r_c+1},C)$.  Similarly we can repeat for
$S_{r_c+2}$ and so forth until we have $C'$ represented relative to $S_{r_H}$.
\item Send $C'$ to all other clients
\item Send ACK back to original client
\item Add $C'$ to the server's list of revision records by creating a new revision record out of this and the client's ID.

\appendix

\section*{Additional topics}
\begin{enumerate}
\item Optimizations (strips, more caching, etc.)
\item Pseudocode for composition, merge, and follow
\item How authorship information is used to color-code the document based on who typed what
\item How persistent connections are maintained between client and server
\end{enumerate}
\end{enumerate}


\end{document}