6.824 阅读笔记3 —— operational transformation

今天来看operational transformation, google doc背后的技术。

Operational Transformation in Real-Time Group Editors: Issues, algorithms, and Achievement

这篇文章不是提出operatinal transformation的那篇，不过通讯是提出论文的一作，插一句别的话，这个通讯Clarence (Skip) Ellis是美国第一个非裔博士，真是厉害了。因为这篇文章是比较泛泛的综述，所以我还引用到了其中一些方法具体实现的论文内容。

Introduction

Group editor的一个难点就是如何在有限的反应时间下维持consistency。operational transformation就是为了达成这一效果的一个技术，其由GROVE (GRoup Outline Viewing Editor)系统在1989年首先提出。之后不同的研究组织都独立的对operational transformation进行了延展。本文会对operationial transformation的进化进行一个整合性的综述，以识别这其中的主要问题，算法，成就与剩余的挑战。除此之外，本文还提出了一个新的generic operational transformation control algorithm。

Preliminaries

这部分做一些基本的定义。

定义： casual ordering relation "$\rightarrow$"

Given $O_a$ and $O_b$ at site $i$ and $j$, then

$O_a\rightarrow O_b$, iff one of the following:

1. $i=j$ and the generation of $O_a$ happened before the generation of $O_b$.
2. $i\ne j$ and the execution of $O_a$ at site $j$ happened before the generation of $O_b$.
3. There exist an operation $O_x$, such that $O_a\rightarrow O_x$ and $O_x\rightarrow O_b$.

定义: dependent and independent operations

Given $O_a$ and $O_b$

1. $O_b$ is dependent on $O_a$ iff $O_a\rightarrow O_b$
2. $O_a$ and $O_b$ are independent (or concurrent), expressed as $O_a || O_b$, iff neither $O_a$ and $O_b$, nor $O_b$ and $O_a$.

举个例子：

上图的黑点是generation的时刻。这里假设operation在local site被立即执行，之后传播到remote sites并在抵达时执行。上图的箭头就是传播路径。比如在site 1, 4个operation的执行顺序是$O_2$, $O_1$, $O_3$, $O_4$。

根据定义1，有$O_1\rightarrow O_3$，$O_2\rightarrow O_3$，$O_2\rightarrow O_4$。同时有$O_1 || O_2$，$O_1 || O_4$，$O_3 || O_4$.

The GROVE approach

为了得到好的responsiveness并防止single-point of failure，GROVE提出了一个replicated architecture：

共享的文档在每个site的本地有一份备份。一个operation会在generation之后马上在本地备份上执行，之后传播到remote sites以执行。

Divergence and causality-violation problems

假设remote operations以他们的original form被执行，那么会发生2种inconsistency，divergence和causality-violation。

例如上图中，因为不同operation在不同site的到达时间不同，而这些operator是不能相互交换的，所以就会在不同site得到不同的结果，这就称为divergence。比如说上图中site 0和site 1的$O_1$和$O_2$顺序不同。

因为上述的genertates and broadcasts的流程不存在synchronization，operation可能会以和他们的natural causal order不同的顺序到达。如上图中$O_1\rightarrow O_3$, 但是在site 2中$O_3$先到达，而其可能会使用还没定义的$O_1$，或者出现先果后因。这种情况称之为causality-violation。如果需要用户间的synchronized interaction，就需要避免这一问题。

Consistency correctness criteria

通过上述问题，GROVE提出了以下的2点性质：

• Convergence property：在静止(quescence)情况下，各个副本完全相同。
• Precedence property：如果$O_a -> O_b$，那么在任何site，$O_a$都需要先于$O_b$执行。

GROVE根据上述的性质提出了distributed Operational Transformation (dOPT)算法。GROVE的解决方案包含两个部分：

• the state-vector timestamping scheme for ensuring the precedence property
• the dOPT algorithm for ensuring the convergence property

A transformation property

为了保证convergence，dOPT算法要求transformation funciton $T$满足：

For any $O_a$ and $O_b$, for which $O_a||O_b$, suppose $O'_a=T(O_a, O_b)$ and $O'_b=T(O_b, O_a)$, it must be that

除了上述条件，GROVE还发现，在一些条件下，transformation function需要满足non-serializable. 比如，$O_a$和$O_b$是两个相互独立的delete operations，其删除的是同一位置，那么$T$必须满足不管这两个operation是什么执行顺序，只能删掉1个字符。不过这个non-serializable的特性并不包含在上述的性质中。

这里我们举引用文献[3] (Concurrency Control in Groupware Systems)中的transformation function作为一个例子：

// o_i = insert[X_i; P_i] (在P_i位置插入X_i)
// o_j = insert[X_j; P_j]
T11(o_i, o_j, p_i, p_j) {  // p_i, p_j分别是两个操作的优先级
    if (P_i < P_j)  // 先做插入后面的，不用变
        return insert[X_i; P_i]
    else if 9P_i > P_j)
        return insert[X_i; P_i+1]
    else {
        if (X_i = X_j) // 注意，覆盖了
            return null
        else {
            if (p_i < p_j)  // 这里和原文相反，修改是为了和下文的例子相应
                return insert[X_i; P_i+1]
            else
                return insert[X_i, P_i]
        }
    }
}
// delete[P] (删除P位置的字符)
T22(delete[P_i], delete[P_j], p_i, p_j) {
    if (P_i < P_j)
        return delete[P_i]
    else if (P_i > P_j)
        return delete[P_i-1]
    else
        return null
}

T12(insert[X_i, P_i], delete[P_j]) {
    if (P_i < P_j)
        return insert[X_i, P_i]
    else
        return insert[X_i, P_i-1]
}

T21(delete[P_j], insert[X_i, P_i]) {
    if (P_i < P_j)
        return insert[X_i, P_i]
    else
        return insert[X_i, P_i+1]
}

A sketch of the dOPT algorithm

对于不同应用，transformation operation是不同的。dOPT是generic的。其主要负责选择需要transform的operation，并决定transformation order。dOPT的基本结构很简单：给一个causally ready operation $O$, dOPT扫描Log来transform O against any operation in the Log which is independent of O；之后被转化的$O$，被称为$EO$（execution form of $O$）会被执行并记录在Log中。

dOPT(O, log) {
	EO = O;
    for (i = 1; i <= n; i++) {
        if (Log[i] || O)  // here || means independent
            then EO = T(EO, Log[i]);
    }
    Execute EO;
    Appennd EO at the end of the Log;
}

An unsolved dOPT puzzle

在一个情况下，dOPT可能不会收敛。如下图：

假设GROVE transformation function使用如下的priority rule：

当两个插入操作有相同的position parameter，the position of the operation with a lower priority (i.e. smaller site identifier) will be shifited。

根据generic dOPT算法和上面提到的transformation function，对于上图我们有：

首先，$O_3\rightarrow O_1$，所以$O_1 || O_2$，$O_2||O_3$，对于3个site，其最终结果如下

• site 3：先按顺序进行$O_3$，$O_1$得到xz，之后对于$O_2$，第一次转换变为insert[y, 2]，第二次变为insert[y, 3]，所以最终是xzy
• site 1：完全同site 3，得到xzy
• site 2：先执行$O_2$得到y，之后O_3进行转换，为insert[z, 1]，变为zy，之后x转化，为insert[x, 2]，得到zxy

这样就出现了问题。在引用文献[3]中提到了这个问题不能通过颠倒优先级顺序来解决，因为虽然颠倒优先级可以解决上面这个例子，但是会出现其余相似的问题。在解决问题的过程中，认为问题出在现在的优先级设定太粗暴了（用single site identifier），所以在[3]中提出了一个负载的priority scheme。

Priority Calculation: The priority of an operation Oi is calculated at the originating site at the time of execution, and is included when the operation is sent to all other sites. If there are operations in the local log whose original position (before transformation) is equal to the operation being initiated, then the highest of these priorities is chosen and the local site ID is appended to it to form the priority of Oi. If there are no such operations in the local log, then the priority is simply the local site ID.

Priority Comparison: Two priorities are compared element by element, from beginning of the list to the first element in which they differ. Which ever is larger at the element where the lists differ has the higher priority. If one list is a sublist of the other, then one operation is a predecessor of the other.

--[3]中提出的priority scheme，没看懂。。。

但是没有给出这个方法是否正确的证明。实际上不同的研究机构都发现在一些情况下dOPT不work。之后的各个小节，我们将介绍他们的修正方法。

The REDUCE Approach

REDUCE和GROVE一样采用了distributed and replicated system architecture。其使用了一个线性的History Buffer (HB)（和GROVE中的Log相同），用来追踪所有被执行过的operation。此外，REDUCE还加入了垃圾回收以回收HB中无用的operation。

The intention-violation problem

除去最开始提到的divergence和causality-violation，REDUCE还提出了一种特殊的inconsistency problem——intention-violation。

例如，假设文档的初始值是ABCDE。假设$O_1$为insert["12", 2]，$O_2$为delete[2, 3]（删除位置3开始的2个字符）。$O_2$的本意是删除CD。执行完两个operation之后，intention-preserved的结果应该是A12BE。然而实际上在site-0，会得到A1CDE。需要注意intention-violation和divergence的本质是不同的，divergence总可以通过串行化解决，而intention-violation不行。

A consistency model

由于intentio-violation问题，REDUCE相correctness criteria更改为：

定义：A consistency model

一个合作编辑系统是consistent的前提为其总是满足如下性质：

• Convergence：当同一组operation在所有site上执行过之后，所有副本完全相同。
• Causality-preservation：如果$O_a -> O_b$，那么在任何site，$O_a$都需要先于$O_b$执行。

• Intention-preservation：对于任何operation $O$，执行$O$的效果在任何site上都是与$O$的intention相同的，且执行$O$的效果不会影响其他independent operations的效果。

  定义：Intention of an operation

  operation $O$的intention就是$O$对在generate $O$时的文档做出的改变

Causality-preservation

为了支持这一consistency model，REDUCE继承了GROVE中的state-vector timestamping scheme以达到Causality-preservation。

定义：State Vector (SV) timestamping scheme

假设有$N$个sites，编号为$0, ..., N-1$。每个site都维护一个长为$N$的state vector。在site k的$SV_k$满足

1. 初始化全部为0
2. 当执行了在site i生成的operation的时候，$SV_k[i]=SV_k[i]+1$

对于在site k生成的$O_k$，

1. $O_k$会被site k立即执行
2. $O_k$会被local state vector $SV_k[k]$ 进行timestamp，并传播给其他的site

对于remote site i生成的$O_i$，其需要等到以下的两点才可以执行（这里$SV_{O_i}$应该是$O_i$生成时的$SV_i$）：

1. $SV_{O_i}[i]=SV_k[i]+1$ ($O_i$必须是site i的下一个指令)
2. $SV_{O_i}[j]<=SV_k[j]$，对于所有非$i$的j（生成$O_i$前执行的必须都已经执行了）

这两个条件可以让在site d所有casually precede $O_i$的都被执行之后再执行$O_i$，从而保证了causality-preservation。

convergence

为了实现convergence，REDUCE提出了如下定义：

定义：Total ordering relation $\Rightarrow$

Given two operations $O_a$ and $O_b$ generated at site $i$ and $j$ and timestamped by $SV_{O_a}$ and $SV_{O_b}$, then $O_a \Rightarrow O_b$ iff:

1. $sum(SV_{O_a}) < sum(SV_{O_b})$, or
2. $sum(SV_{O_a}) = sum(SV_{O_b})$ and $i<j$,

where $sum(SV_{O_a}) = \sum_{i=0}^{N-1} SV[i]$. 我们称$O_a$ totally precedes $O_b$或者$O_a$ totally follows $O_b$。We can see that if $O_a \rightarrow O_b$, then $O_a\Rightarrow O_b$.

有了这个定义之后进行了如下的scheme。（HB就是记录所有执行过的operations的log）

定义：The undo/do/redo scheme

如果incoming $O$已经通过了remote operation execution conditions test(上面的两条)，那么：

1. Undo：HB中所有totally follow $O$的指令要撤销到施加其之前的状态。（注意撤销一定是从某一个元素撤销到最后）
2. Do: 运行$O$，并记录在HB中
3. Redo：把所有undone的operation执行一下

注意这里假设了所有的operation可逆。

这样就可以做到convergence了。有论文证明了，通过基于$\Rightarrow$的顺序，所有的editing effect会是一样的。

Transformation pre-/post-conditions

因为REDUCE中transformation function不是用来保证convergence的，所以也不需要满足GROVE中提到的要求。

为了表明operation之间的关系，我们需要引入context这样一个术语，其意思为文档从初始状态到当前状态之间执行的operation序列。

定义：definition context and execution context

The definition context, denoted as $DC(O)$, is the context of the document state on which $O$ is defined.

The execution context, denoted as $EC(O)$, is the context of the the document state on which $O$ is to be executed.

当$DC(O)=EC(O)$的时候，操作就保留了intention。

REDUCE引入了两种transformation function——$IT(O_a, O_b)$ (inclusion transformation)和$ET(O_a, O_b)$ (exlusion transformation)——以达成$DC(O)=EC(O)$。为了确定变换前后的条件，我们还做了如下两个定义：

定义：Context equivalent relation "$\sqcup$"

$O_a \sqcup O_b$, iff $DC(O_a)=DC(O_b)$

定义：Context preceding relation "$\mapsto$"

$O_a \mapsto O_b$, iff $DC(O_b)=DC(O_a)+[O_a]$. ($+$ means list concatenation)

根据以上的条件，我们有：

Specification：$IT(O_a, O_b): O'_a$，把两个同时进行的operation变为先后执行

1. Precondition for input parameters: $O_a \sqcup O_b$
2. Postcondition for output: $O_b \mapsto O'_a$ and the effect of $O'_a$ in $DC(O'_a)$ is the same as the effect of $O_a$ in $DC(O_a)$.

Specification：$ET(O_a, O_b): O'_a$，把两个先后执行的指令变为同时执行

1. Precondition for input parameters: $O_b \mapsto O_a$
2. Postcondition for output: $O_b \sqcup O'_a$ and the effect of $O'_a$ in $DC(O'_a)$ is the same as the effect of $O_a$ in $DC(O_a)$.

定义 Reversibility Requirement

1. if $O_a\sqcup O_b$, then $O_a=ET(IT(O_a, O_b), O_b)$
2. if $O_b\mapsto O_a$, then $O_a=IT(ET(O_a, O_b), O_b)$

为了方便，[17]中还定义了两个genertic的辅助函数：

// precondition
// 1. OL[1] context context equivalent with O
// 2. OL[i] context preceding OL[i+1]
LIT(O, OL) {
    if OL = []
        return O
    else
        return LIT(IT(O, OL[1]), Tail(OL))  // 这里1表示第一个元素
}

// precondition
// 1. OL[1] context preceding O
// 2. OL[i+1] context preceding OL[i]
LET(O, OL) {
    if OL = []
        return O
    else
        return LET(ET(O, OL[1]), Tail(OL))  // 这里1表示第一个元素
}

Generic Operation Transformation Control Alorithm

假设$O_{new}$是一个causally ready operation （causaly precede的都执行完了）。然后假设其context为$DC(O_{new})$，$HB=[EO_1, EO_2, ..., EO_m]$，且有

1. $EO_1\Rightarrow EO_2\Rightarrow ... \Rightarrow EO_m \Rightarrow O_{new}$ 与
2. $EO_1\mapsto EO_2\mapsto ... \mapsto EO_m$ （连着进行的）

我们的目标是确定$O_{new}$的转化状态$EO_{new}$满足：

1. $EO_m\mapsto EO_{new}$
2. $EO_{new}$达成的效果和$DC(O_{new})$一样。

GOT(O_new, HB) {
    k = -1
    for (i=1; i<=m; i++) {
        if HB[k] || O_new {
            k = i
            break
        }
    }
    if k == -1  // 所有EO都casualy precede O_new, O_new不需要做变换
        return O_new
    EOL = []  // list of EO in HB[k+1, m] that are causally preceding O_new
    for (i=k+1; i<=m; i++) {
        if HB[i] causally precede O_new
            EOL.append(HB[i]);
    }
    if EOL == []  // 如果EOL为空，HB[k,m]都不在DC(O_new)中，集体转化
        return LIT(O_new, HB[k, m]);
    r = len(EOL)
    // c_1 is the origin index of EOL[1]
    EOL[1] = LET(EOL[1], revese(HB[k, c_1-1]));
    for (i=2; i<=r; i++) {
        TO = LET(EOL[i], revese(HB[k, c_i-1]));
        EOL[i] = LIT(TO, EOL[1, i])
    }
    O_new = LET(O_new, reverse(EOL));
    return LIT(O_new, HB[k, m]);
}

把transformation和上面的undo/do/redo scheme结合记起来就有了如下的scheme

定义：The undo/transform-do/transform-redo scheme

如果incoming $O_new$已经通过了remote operation execution conditions test，那么

1. Undo：从右往左一个一个撤销HB中的operation $EO_m$直到$EO_m\Rightarrow O_new$
2. Transform-do: 用GOT算法把$O_new$ transform为$EO_{new}$，之后执行转化完的$O$。

3. Transform-redo，所有未执行的在$HB[m+1, n]$中的operation $EO_{m+i}$都进行如下变换：

   • $EO'_{m+1}:=IT(EO_{m+1}, EO_new)$
   • for $2<=i<=n-m$
   • $TO:=LET(EO_{m+i}, reverse(HB[m+1, m+i-1]))$
   • $EO'_{m+i}:=LIT(TO, [EO_{new}, EO'_{m+1}, ..., EO'_{m+i-1}])$
   • redo $EO'_{m+1}, EO'_{m+2}, ..., EO'_{n}$
4. 把转化完的$EO_{new}$插入进HB，使得

对于插入删除问题的$IT/ET$例子

下面是$IT$的例子，来自[17] (Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems)

// insertion[S, P]
// delete[N, P]
// P(O) is the  position parameter of O
// L(O) is the length of operation O
// S(O) for insert O is the string to insert
// save_LI is to remember the lost of information for future reverse
IT_II(O_a, O_b) {  // insert, insert
    if P(O_a) < P(O_b)  // 在前面插入，不需要变
        return O_a
    else
        return insert[S(O_a), P(O_a)+L(O_b)]
}
IT_ID(O_a, O_b) {  // insert, delete
    if P(O_a) <= P(O_b)
        return O_a
    else if P(O_a) > P_(O_b) + L(O_b)  // 在删掉的后面插入
        return insert(S(O_a), P(O_a)-L(O_b))
    else  // 插入的位置被删除了，就要在删除的初始位置插入
        save_LI()
        return insert(S(O_a), P(O_b))
}
IT_DI(O_a, O_b) {  // delete, insert
    if P(O_a) + L(O_a) <= P(O_b) // 插入与删除无关
        return O_a
    else if P(O_a) >= P(O_b)
        return delete(L(O_a), P(O_a)+L(O_b))
    else  // 如果插入在删除中间，要把插入跳过
        return delete[P(O_b)-P(O_a), P(O_a)] +  // 这里的"+"是要两个同时进行的
               delete[L(O_a)-(P(O_b)-P(O_a)), P(O_b)+L(O_b)
}
IT_DD(O_a, O_b) {  // delete, delete
    if P(O_a) + L(O_a) <= P(O_b) // O_b与O_a无关
        return O_a
    else if P(O_a) >= P(O_b) + L(O_b)  // O_b完全在O_a前面
        return delete[L(o_a), P(O_a)-L(O_b)]
    else {
        save_LI()
        if P(O_b) <= P(O_a) and P(O_a) + L(O_a) <= P(O_b) + L(O_b)
            return delete[0, P(O_a)]  // O_a被O_b包住了
        else if P(O_b) <= P(O_a) and P(O_a) + L(O_a) > P(O_b) + L(O_b)
            // 把o_b没删掉的删掉
            return delete[P(O_a) + L(O_a) > P(O_b) - (L(O_b), P(O_b)), P(O_b)]
        else if P(O_a) < P(O_b) and P(O_a) + L(O_a) <= P(O_b) + L(O_b)
            return delete[P(O_b)-P(O_a), P(O_a)]
        else
            return delete[L(O_a)-L(O_b), P(O_a)]
    }
}

然后是$ET$的例子就是用于恢复$IT$的，在[17]中也有记录。

A solution to the dOPT puzzle

REDUCE的方案解决了上文提出的dOPT puzzle，证明我没看...有兴趣的同学可以去自己看一下。

The Jupiter Approach

jupyter和GROVE的不同在于，jupyter有一个central server。一个client site本地生成operation之后，现在本地副本上执行，之后要把修改发送给central server。central server会对收到的operation做transformation，并在central server自己的副本上执行，最后再传播给其他的client sites。这样直接避免了发生causality violation (因为相当于做了symchronization)，同时大幅简化了transformation control算法。

为了convergence，Jupiter approach也对transformation operation做和GROVE一样的要求。不过其使用一个state space图，而不是线性的Log/HB，来记录所有可能的operation transfomration paths。Jupyter算法保证任何一对进行transformation的算法都来源于state space graph的同意starting state，其本质上和GOT中的context equivalent一样。所以Jupyter算法可以纠正GROVE的问题。

文中后面还提到了两个算法，等之后有时间再看看吧~

The Adopted Approcah

An Optimized Algorithm: GOTO