发布于 由admin

JS `Operational Transforms` `String OT` / `JSON OT` 算法与协同编辑库

各位靓仔靓女，大家好！我是今天的主讲人，江湖人称“代码搬运工”。今天咱们来聊聊协同编辑的幕后英雄——Operational Transforms (OT)，也就是操作转换。这玩意儿听起来高大上，其实就是一套巧妙的算法，让多人同时编辑同一份文档而不打架。

我们今天要讲的内容包括：

  1. 啥是协同编辑？ 为什么要用OT？
  2. OT核心概念： 操作、转换、一致性
  3. String OT： 字符串操作的OT，代码撸起来！
  4. JSON OT： JSON数据结构的OT，让数据飞起来！
  5. 协同编辑库： 现有的一些JS库，咱们瞅瞅它们的实现思路。
  6. 实战演练： 手撸一个简易String OT协同编辑器。
  7. 一些问题和挑战： OT也不是万能的，说说它的局限性。

好，废话不多说，咱们开始！

1. 啥是协同编辑？为什么要用OT？

协同编辑，顾名思义，就是很多人同时编辑同一份文档。这玩意儿在Google Docs、石墨文档、腾讯文档里天天见。没了它，多人在线协作就成了“你改完了我再改”的串行操作，效率低到爆炸。

那为啥要用OT呢？ 想象一下，小明和小红同时编辑一篇文档：

  • 初始状态： "Hello"
  • 小明： 在"Hello"后面插入" World" 变成了 "Hello World"
  • 小红： 在"Hello"后面插入", " 变成了 "Hello, "

如果没有OT，服务器简单粗暴地把小明的操作应用到小红的文档上，或者反过来，就会产生冲突。例如，如果服务器先收到小明的操作，再收到小红的操作，就会变成 "Hello World, "，这显然不对。

OT的作用，就是把这些并发的操作进行转换，让它们能正确地应用到对方的文档上，最终达到一致的状态。

2. OT核心概念：操作、转换、一致性

OT有三个核心概念：

  • 操作 (Operation)： 对文档进行修改的行为，比如插入、删除、替换。
  • 转换 (Transformation)： 核心！根据操作的类型和位置，调整操作的内容，使其能正确地应用到已经发生改变的文档上。
  • 一致性 (Consistency)： 所有客户端最终都看到相同的文档内容。

为了更容易理解，我们先用String OT举例。

String OT 的操作类型

String OT里，常见的操作类型有：

操作类型 描述 参数
insert 在指定位置插入文本 position (插入位置), text (插入文本)
delete 删除指定位置的文本 position (删除位置), length (删除长度)
retain 保留指定长度的文本 length (保留长度)

retain 操作可能有些人会觉得奇怪，它好像什么都没做。但它在OT里非常重要，它代表了"不操作"，用于标记已经处理过的文本区域，在转换操作时起到定位的作用。

OT 的转换规则

OT最关键的就是转换规则。假设有两个操作 op1 和 op2，我们需要定义一个转换函数 transform(op1, op2)，返回两个新的操作 op1' 和 op2'，使得：

apply(apply(state, op1), op2') == apply(apply(state, op2), op1')

这句话的意思是：先应用 op1 再应用转换后的 op2'，和先应用 op2 再应用转换后的 op1'，最终结果是一样的。这就是OT保证一致性的关键。

3. String OT：代码撸起来！

让我们用代码来实现一个简单的String OT。

首先，定义操作的结构：

class InsertOperation {
  constructor(position, text) {
    this.type = 'insert';
    this.position = position;
    this.text = text;
  }
}

class DeleteOperation {
  constructor(position, length) {
    this.type = 'delete';
    this.position = position;
    this.length = length;
  }
}

class RetainOperation {
  constructor(length) {
    this.type = 'retain';
    this.length = length;
  }
}

然后，定义一个 apply 函数，用于将操作应用到文本上：

function apply(text, ops) {
  let newText = "";
  let currentPosition = 0;

  for (const op of ops) {
    if (op.type === 'insert') {
      newText += op.text;
    } else if (op.type === 'delete') {
      // Do nothing, effectively deleting the text
    } else if (op.type === 'retain') {
      newText += text.substring(currentPosition, currentPosition + op.length);
    }
    currentPosition += op.type === 'retain' ? op.length : 0;
  }

  return newText;
}

接下来，是核心的 transform 函数。 为了简化，我们只考虑 insert 和 delete 操作之间的转换。

function transform(op1, op2) {
  if (op1.type === 'insert' && op2.type === 'insert') {
    // 两个都是插入操作
    if (op1.position <= op2.position) {
      // op1 在 op2 前面或相同位置插入，op2 的位置需要后移
      return [op1, new InsertOperation(op2.position + op1.text.length, op2.text)];
    } else {
      // op1 在 op2 后面插入，op1 的位置不需要改变
      return [new InsertOperation(op1.position + op2.text.length, op1.text), op2];
    }
  } else if (op1.type === 'insert' && op2.type === 'delete') {
    // op1 是插入，op2 是删除
    if (op1.position <= op2.position) {
      // op1 在 op2 前面插入，op2 的位置需要后移
      return [op1, new DeleteOperation(op2.position + op1.text.length, op2.length)];
    } else if (op1.position >= op2.position + op2.length) {
      // op1 在 op2 后面插入，op1 的位置不需要改变
      return [op1, op2];
    } else {
      // op1 的插入位置在 op2 的删除范围内，需要分割 op2
      let newDelete1 = new DeleteOperation(op2.position, op1.position - op2.position);
      let newDelete2 = new DeleteOperation(op1.position + op1.text.length, op2.position + op2.length - op1.position);

      return [op1, newDelete1, newDelete2]; // 返回两个删除操作
    }
  } else if (op1.type === 'delete' && op2.type === 'insert') {
    // op1 是删除，op2 是插入
    if (op1.position <= op2.position) {
      // op1 在 op2 前面删除，op2 的位置需要前移
      return [op1, new InsertOperation(op2.position - op1.length, op2.text)];
    } else if (op1.position >= op2.position + op2.text.length) {
      // op1 在 op2 后面删除，op1 的位置不需要改变
      return [op1, op2];
    } else {
      // op1 的删除范围在 op2 的插入范围内，需要分割 op1
      let newDelete1 = new DeleteOperation(op1.position, op2.position - op1.position);
      let newDelete2 = new DeleteOperation(op2.position + op2.text.length, op1.position + op1.length - op2.position);

      return [newDelete1, op2, newDelete2];
    }
  } else if (op1.type === 'delete' && op2.type === 'delete') {
    // 两个都是删除操作
    if (op1.position <= op2.position) {
      // op1 在 op2 前面删除
      return [op1, new DeleteOperation(op2.position - op1.length, op2.length)];
    } else {
      // op1 在 op2 后面删除
      return [op1, op2];
    }
  } else {
    // 不支持的操作类型
    return [op1, op2];
  }
}

注意： 上面的 transform 函数只是一个简化的示例，只考虑了 insert 和 delete 之间的转换。完整的String OT还需要处理 retain 操作，以及更复杂的边界情况。

4. JSON OT：让数据飞起来！

String OT只能处理字符串，对于更复杂的数据结构（比如JSON对象），就需要JSON OT了。JSON OT的操作更加灵活，可以对JSON的任何部分进行修改。

JSON OT 的操作类型

JSON OT的操作类型有很多，常见的有：

操作类型 描述 参数
insert 在指定位置插入数据 path (JSON路径，比如 ['a', 'b', 0]), value (要插入的值)
delete 删除指定位置的数据 path (JSON路径)
replace 替换指定位置的数据 path (JSON路径), oldValue (旧值), newValue (新值)
move 移动指定位置的数据到另一个位置 from (JSON路径), to (JSON路径)
add 向数组或对象添加元素 path (JSON路径，指向数组或对象), key (键名，如果path指向对象), index (索引，如果path指向数组), value (要添加的值)
remove 从数组或对象删除元素 path (JSON路径，指向数组或对象), key (键名，如果path指向对象), index (索引，如果path指向数组)
test 测试指定位置的值是否符合预期 path (JSON路径), value (期望的值)

JSON OT 的转换规则

JSON OT的转换规则比String OT复杂得多，因为JSON的结构更加灵活。不同的操作类型之间，以及相同操作类型的不同位置之间，都需要定义转换规则。

例如，假设有两个操作：

  • op1: 在 ['a', 'b', 0] 插入值 123
  • op2: 在 ['a', 'b', 1] 插入值 456

如果先应用 op1，再应用 op2，那么 op2 的路径应该变成 ['a', 'b', 2]。

实现JSON OT的 transform 函数非常复杂，需要考虑各种情况。这里就不贴代码了，感兴趣的同学可以参考一些开源的JSON OT库，比如ShareDB。

5. 协同编辑库：咱们瞅瞅它们的实现思路

市面上有很多协同编辑库，它们都或多或少地用到了OT的思想。

  • ShareDB： 一个基于Node.js的协同编辑后端，支持String OT和JSON OT。它使用MongoDB作为数据存储，并通过WebSocket与客户端通信。ShareDB的架构非常清晰，易于扩展。
  • Operational Transformation Library (OT.js)： 一个纯JavaScript的OT库，提供了String OT和JSON OT的实现。OT.js的设计目标是轻量级和高性能，适合嵌入到各种Web应用中。
  • Yjs： 一个基于CRDTs（Conflict-free Replicated Data Types）的协同编辑库。CRDTs是另一种解决冲突的算法，与OT相比，CRDTs不需要进行转换操作，但可能会占用更多的内存。Yjs的性能非常好，支持离线编辑。

这些库的实现思路大致相同：

  1. 客户端生成操作，并将操作发送到服务器。
  2. 服务器接收到操作后，对操作进行转换，然后将转换后的操作广播给所有客户端。
  3. 客户端接收到操作后，将操作应用到本地文档上。

6. 实战演练：手撸一个简易String OT协同编辑器

为了更好地理解String OT，我们来手撸一个简易的String OT协同编辑器。

HTML结构：

<!DOCTYPE html>
<html>
<head>
  <title>Simple OT Editor</title>
</head>
<body>
  <textarea id="editor" cols="80" rows="10"></textarea>
  <script src="ot.js"></script>
  <script>
    const editor = document.getElementById('editor');
    const otClient = new OTClient(editor);
  </script>
</body>
</html>

JavaScript代码 (ot.js):

class InsertOperation {
  constructor(position, text) {
    this.type = 'insert';
    this.position = position;
    this.text = text;
  }
}

class DeleteOperation {
  constructor(position, length) {
    this.type = 'delete';
    this.position = position;
    this.length = length;
  }
}

class RetainOperation {
  constructor(length) {
    this.type = 'retain';
    this.length = length;
  }
}

function apply(text, ops) {
  let newText = "";
  let currentPosition = 0;

  for (const op of ops) {
    if (op.type === 'insert') {
      newText += op.text;
    } else if (op.type === 'delete') {
      // Do nothing, effectively deleting the text
    } else if (op.type === 'retain') {
      newText += text.substring(currentPosition, currentPosition + op.length);
    }
    currentPosition += op.type === 'retain' ? op.length : 0;
  }

  return newText;
}

function transform(op1, op2) {
    // 简化版，只处理 insert vs insert
    if (op1.type === 'insert' && op2.type === 'insert') {
        if (op1.position <= op2.position) {
            return [op1, new InsertOperation(op2.position + op1.text.length, op2.text)];
        } else {
            return [new InsertOperation(op1.position + op2.text.length, op1.text), op2];
        }
    } else {
        return [op1, op2]; // 简化版：不处理其他情况
    }
}

class OTClient {
  constructor(editor) {
    this.editor = editor;
    this.socket = new WebSocket('ws://localhost:8080'); // 假设有一个WebSocket服务器
    this.socket.onmessage = this.onMessage.bind(this);
    this.editor.addEventListener('input', this.onInput.bind(this));
    this.version = 0; // 文档版本号
    this.buffer = []; // 待发送的操作队列
    this.serverState = editor.value; // 服务器端的状态
  }

  onInput(event) {
    const ops = this.computeOperations(this.serverState, this.editor.value);
    this.buffer.push(ops);
    this.serverState = this.editor.value;
    this.sendOperation(ops);
  }

  computeOperations(oldText, newText) {
    let ops = [];
    let i = 0;
    let j = 0;

    while (i < oldText.length || j < newText.length) {
      if (i < oldText.length && oldText[i] === newText[j]) {
        // 字符相同，retain
        let retainLength = 1;
        while (i + retainLength < oldText.length && j + retainLength < newText.length && oldText[i + retainLength] === newText[j + retainLength]) {
          retainLength++;
        }
        ops.push(new RetainOperation(retainLength));
        i += retainLength;
        j += retainLength;
      } else if (i < oldText.length && (j >= newText.length || oldText[i] !== newText[j])) {
        // 需要删除字符
        let deleteLength = 1;
        while (i + deleteLength < oldText.length && (j >= newText.length || oldText[i + deleteLength] !== newText[j])) {
          deleteLength++;
        }
        ops.push(new DeleteOperation(i, deleteLength));
        i += deleteLength;
      } else if (j < newText.length && (i >= oldText.length || oldText[i] !== newText[j])) {
        // 需要插入字符
        let insertText = "";
        while (j < newText.length && (i >= oldText.length || oldText[i] !== newText[j])) {
          insertText += newText[j];
          j++;
        }
        ops.push(new InsertOperation(i, insertText));
      }
    }

    return ops;
  }

  sendOperation(ops) {
    this.socket.send(JSON.stringify({
      version: this.version,
      ops: ops
    }));
  }

  onMessage(event) {
    const data = JSON.parse(event.data);
    if (data.version === this.version) {
      // 应用服务器发送的操作
      this.applyRemoteOperation(data.ops);
      this.version++;
    } else if (data.version > this.version) {
        // 重新请求服务器状态
        this.socket.send(JSON.stringify({type: "requestState"}));

    } else {
        //忽略过期的操作
    }
  }

  applyRemoteOperation(ops) {
    // 1. 转换本地buffer中的操作
    for (let i = 0; i < this.buffer.length; i++) {
        let transformed = transform(this.buffer[i], ops);
        this.buffer[i] = transformed[0];
        ops = transformed[1];
    }

    // 2. 应用服务器发来的操作
    this.serverState = apply(this.serverState, [ops]);
    this.editor.value = this.serverState;
  }

  // 重新设置状态
  setState(newState) {
      this.serverState = newState;
      this.editor.value = newState;
  }
}

WebSocket服务器 (Node.js):

const WebSocket = require('ws');

const wss = new WebSocket.Server({ port: 8080 });

let documentState = "";
let version = 0;
const clients = [];

wss.on('connection', ws => {
  clients.push(ws);
  console.log('Client connected');

  // 发送当前文档状态
  ws.send(JSON.stringify({ version: version, state: documentState }));

  ws.on('message', message => {
    try {
      const data = JSON.parse(message);

      if (data.type === "requestState") {
        ws.send(JSON.stringify({version: version, state: documentState}));
        return;
      }

      if (data.version === version) {
        // 应用操作到服务器端状态
        documentState = apply(documentState, data.ops);
        version++;

        // 广播操作给所有客户端
        clients.forEach(client => {
          if (client !== ws && client.readyState === WebSocket.OPEN) {
            client.send(JSON.stringify({ version: version, ops: data.ops }));
          }
        });

        console.log(`Document State: ${documentState}`);
      } else {
        console.log(`Received outdated operation (version: ${data.version}, current: ${version})`);
      }
    } catch (error) {
      console.error('Error processing message:', error);
    }
  });

  ws.on('close', () => {
    clients.splice(clients.indexOf(ws), 1);
    console.log('Client disconnected');
  });
});

function apply(text, ops) {
  let newText = "";
  let currentPosition = 0;

  for (const op of ops) {
    if (op.type === 'insert') {
      newText += op.text;
    } else if (op.type === 'delete') {
      // Do nothing, effectively deleting the text
    } else if (op.type === 'retain') {
      newText += text.substring(currentPosition, currentPosition + op.length);
    }
    currentPosition += op.type === 'retain' ? op.length : 0;
  }

  return newText;
}

console.log('WebSocket server started on port 8080');

使用方法：

  1. 保存HTML文件为一个 .html 文件。
  2. 保存JavaScript代码为 ot.js 文件，并确保它与HTML文件在同一目录下。
  3. 保存Node.js代码为一个 .js 文件，比如 server.js。
  4. 运行Node.js服务器：node server.js
  5. 用浏览器打开HTML文件。
  6. 打开多个浏览器窗口，访问同一个HTML文件。
  7. 在不同的浏览器窗口中编辑文本，看看是否能够协同编辑。

注意： 这个例子只是一个非常简化的String OT实现，没有处理所有的边界情况和操作类型。它主要用于演示OT的基本原理。

7. 一些问题和挑战：OT也不是万能的

OT虽然很强大，但也不是万能的。它有一些问题和挑战：

  • 复杂性： OT的转换规则非常复杂，特别是对于复杂的数据结构。实现和维护OT算法需要花费大量的精力。
  • 性能： OT的转换操作可能会影响性能，特别是当并发操作很多时。
  • 实时性： OT需要等待服务器确认操作，才能应用到本地文档上，这可能会导致一定的延迟。
  • 状态同步： 当客户端离线一段时间后重新连接时，需要进行状态同步，这可能会比较复杂。

为了解决这些问题，人们提出了很多其他的协同编辑算法，比如CRDTs。CRDTs不需要进行转换操作，但可能会占用更多的内存。

OT vs CRDTs：

| 特性 | OT | CRDTs in the absence of synchronization. |
| 实现难度 | 相对复杂，需要处理各种操作之间的转换关系。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注