发布于 由admin

JS `Operational Transforms` (OT) 算法与 `CRDT` 的对比与适用场景

各位观众老爷们，大家好！ 今天咱们聊点硬核的，聊聊协作编辑背后的两大功臣：Operational Transforms (OT) 和 Conflict-free Replicated Data Types (CRDTs)。 这俩兄弟都是为了解决多人同时编辑同一个文档时产生的冲突问题，但解决思路却大相径庭。 今天咱们就扒一扒他们的底裤，看看谁更适合你。

一、故事的开端：协作的烦恼

想象一下，你和你的小伙伴们正在一起编写一份重要的报告。 你在第一段添加了一句话，你的小伙伴在第二段修改了一个错别字。 如果你们各自修改完就直接覆盖，那肯定会乱成一锅粥。 这就是协作编辑最核心的问题：如何保证多个客户端对同一份数据的修改能够正确地合并，最终得到一致的结果。

二、OT：先来后到，小心翼翼

OT 的核心思想是“先来后到”。 它就像一个严格的交通警察，确保每个操作都按照顺序执行。

  1. 操作的定义: 在 OT 中，所有的修改都被抽象成“操作”。 比如，插入一段文字，删除一段文字，替换一段文字等等。

    // 一个简单的插入操作
const insertOp = {
    type: 'insert',
    position: 5,  // 插入的位置
    text: 'Hello' // 插入的文本
};

// 一个简单的删除操作
const deleteOp = {
    type: 'delete',
    position: 10, // 删除的位置
    length: 5    // 删除的长度
};

  2. 中心服务器的协调: OT 通常需要一个中心服务器来协调各个客户端的操作。 当一个客户端要执行一个操作时，它首先把这个操作发送给服务器。 服务器接收到操作后，会将其广播给所有其他的客户端。

  3. 操作转换 (Transform): 这就是 OT 最核心的部分。 当一个客户端收到一个来自服务器的操作时，它需要先将这个操作转换 (transform) 成适用于自己当前文档状态的版本。 也就是说，客户端需要考虑自己已经执行过的操作对这个新操作的影响。

    举个例子：

    • 客户端 A 在位置 5 插入了 "Hello"。
    • 客户端 B 在位置 8 插入了 "World"。
    • 现在，客户端 A 收到了客户端 B 的插入操作。

    由于客户端 A 已经在位置 5 插入了 "Hello"，所以客户端 B 的插入操作实际上应该在位置 11 (5 + 5 + 1) 执行，而不是原来的位置 8. 这个转换的过程就是 OT 的核心。

    // 转换函数，用于将一个操作转换成适用于另一个文档状态的版本
function transform(op1, op2) {
    // 假设 op1 是客户端 A 的操作，op2 是客户端 B 的操作
    if (op1.type === 'insert' && op2.type === 'insert') {
        if (op1.position <= op2.position) {
            op2.position += op1.text.length;
        }
    } else if (op1.type === 'insert' && op2.type === 'delete') {
        if (op1.position <= op2.position) {
            op2.position += op1.text.length;
        } else if (op1.position < op2.position + op2.length) {
            op2.length += op1.text.length;
        }
    }
    // 其他类型的操作的转换逻辑...
    return op2;
}

  4. 缺点: OT 的缺点也很明显。

    • 复杂性: 操作转换的逻辑非常复杂，需要考虑各种情况，容易出错。
    • 中心服务器依赖: OT 需要一个中心服务器来协调操作，如果服务器宕机，整个系统就瘫痪了。
    • 延迟: 由于需要经过中心服务器，所以延迟较高，用户体验可能会受到影响。

三、CRDT：我的地盘我做主，最终一致性

CRDT 的核心思想是“我的地盘我做主”。 每个客户端都可以自由地修改自己的数据副本，然后通过某种方式将修改同步到其他客户端。 最终，所有客户端的数据副本都会收敛到一致的状态。

  1. 数据的特殊结构: CRDT 不是直接操作文本，而是将数据结构设计成可以无冲突合并的形式。 常见的 CRDT 类型包括：

    • Add-wins Set: 添加操作总是优先于删除操作。
    • Remove-wins Set: 删除操作总是优先于添加操作。
    • Last Write Wins (LWW) Element Set: 根据时间戳来决定哪个操作生效。
    • Ordered List CRDT (基于链表的 CRDT): 每个字符都有一个唯一的 ID，客户端可以根据 ID 来确定字符的顺序。

  2. 无冲突合并 (Merge): CRDT 定义了一套合并算法，可以将不同的数据副本合并成一个一致的数据副本。 这个合并算法保证了无论客户端以什么顺序合并数据，最终的结果都是一样的。

    举个例子，使用 Add-wins Set：

    // Add-wins Set 的简单实现
class AddWinsSet {
    constructor() {
        this.adds = new Set();
        this.removes = new Set();
    }

    add(value) {
        this.adds.add(value);
        this.removes.delete(value); // 如果之前删除了，现在要移除删除记录
    }

    remove(value) {
        if (this.adds.has(value)) {
            this.removes.add(value); // 只记录删除操作，不真正删除
        }
    }

    contains(value) {
        return this.adds.has(value) && !this.removes.has(value);
    }

    merge(other) {
        const newSet = new AddWinsSet();
        newSet.adds = new Set([...this.adds, ...other.adds]);
        newSet.removes = new Set([...this.removes, ...other.removes]);
        return newSet;
    }
}

// 示例
const set1 = new AddWinsSet();
set1.add('A');
set1.add('B');
set1.remove('B');

const set2 = new AddWinsSet();
set2.add('B');
set2.add('C');

const mergedSet = set1.merge(set2);
console.log(mergedSet.contains('A')); // true
console.log(mergedSet.contains('B')); // true  (Add wins!)
console.log(mergedSet.contains('C')); // true

  3. 无需中心服务器: CRDT 可以直接在客户端之间同步数据，无需中心服务器的协调。 这使得 CRDT 更加健壮，并且可以支持离线协作。

  4. 缺点: CRDT 的缺点也很明显。

    • 数据结构限制: CRDT 需要将数据结构设计成特定的形式，这可能会限制应用程序的灵活性。
    • 复杂性: 虽然 CRDT 避免了操作转换的复杂性，但是合并算法的实现也可能非常复杂。
    • 性能: 某些 CRDT 的合并操作可能会比较耗时，影响性能。
    • 不直观: 对于简单的文本操作，需要转换成复杂的 CRDT 结构，开发难度会提升。

四、OT vs CRDT：正面交锋

特性 Operational Transforms (OT) Conflict-free Replicated Data Types (CRDTs)
核心思想 先来后到，操作转换 我的地盘我做主，最终一致性
数据结构 原始数据类型 (例如：文本) 特殊的数据结构 (例如：Add-wins Set, Ordered List CRDT)
冲突解决 操作转换 合并算法
服务器依赖 通常需要中心服务器 可以无需中心服务器
复杂性 操作转换逻辑复杂 数据结构设计和合并算法复杂
延迟 较高，需要经过中心服务器 较低，可以直接在客户端之间同步
适用场景 传统的协作编辑系统，对实时性要求较高，可以接受一定的服务器依赖 分布式系统，需要支持离线协作，对数据结构有一定的限制
容错性 较低，服务器宕机会影响整个系统 较高，客户端可以独立工作
开发难度 较高，操作转换逻辑容易出错 较高，需要理解和实现复杂的 CRDT 结构和合并算法
优点 更贴近原始数据，更容易理解和调试 更好的容错性和可扩展性，支持离线协作
缺点 服务器依赖，复杂性高 数据结构限制，性能问题

五、代码示例：一个简易的 CRDT 文本编辑器（Ordered List CRDT）

为了更直观地理解 CRDT 的工作方式，我们来实现一个简易的基于 Ordered List CRDT 的文本编辑器。

// 每个字符的节点
class CharNode {
    constructor(id, char, prevId, nextId) {
        this.id = id;      // 字符的唯一 ID
        this.char = char;    // 字符
        this.prevId = prevId;  // 前一个字符的 ID
        this.nextId = nextId;  // 后一个字符的 ID
    }
}

// CRDT 文本编辑器
class CrdtTextEditor {
    constructor() {
        this.nodes = {}; // 存储所有字符节点的字典，key 是字符 ID
        this.head = null;  // 第一个字符的 ID
        this.tail = null;  // 最后一个字符的 ID
        this.counter = 0;  // 用于生成唯一 ID
    }

    // 生成唯一 ID
    generateId() {
        return this.counter++;
    }

    // 在指定位置插入字符
    insert(char, beforeId) {
        const newId = this.generateId();
        const newNode = new CharNode(newId, char, null, null);

        if (beforeId === null) {
            // 插入到开头
            if (this.head === null) {
                // 空文本
                this.head = newId;
                this.tail = newId;
            } else {
                const headNode = this.nodes[this.head];
                newNode.nextId = this.head;
                headNode.prevId = newId;
                this.head = newId;
            }
        } else {
            // 插入到指定位置之前
            const beforeNode = this.nodes[beforeId];
            if (!beforeNode) {
                console.error("Invalid beforeId:", beforeId);
                return;
            }

            newNode.prevId = beforeId;
            newNode.nextId = beforeNode.nextId;
            beforeNode.nextId = newId;

            if (newNode.nextId !== null) {
                const nextNode = this.nodes[newNode.nextId];
                nextNode.prevId = newId;
            } else {
                this.tail = newId;
            }
        }

        this.nodes[newId] = newNode;
        return newId;
    }

    // 删除指定字符
    delete(id) {
        const nodeToDelete = this.nodes[id];
        if (!nodeToDelete) {
            console.error("Invalid id:", id);
            return;
        }

        const prevId = nodeToDelete.prevId;
        const nextId = nodeToDelete.nextId;

        if (prevId !== null) {
            const prevNode = this.nodes[prevId];
            prevNode.nextId = nextId;
        } else {
            this.head = nextId;
        }

        if (nextId !== null) {
            const nextNode = this.nodes[nextId];
            nextNode.prevId = prevId;
        } else {
            this.tail = prevId;
        }

        delete this.nodes[id];
    }

    // 获取文本内容
    getText() {
        let text = "";
        let currentId = this.head;
        while (currentId !== null) {
            const node = this.nodes[currentId];
            text += node.char;
            currentId = node.nextId;
        }
        return text;
    }

    // 合并另一个编辑器
    merge(otherEditor) {
        // 遍历 otherEditor 的所有节点，将不存在于当前编辑器的节点添加到当前编辑器
        for (const id in otherEditor.nodes) {
            if (!this.nodes[id]) {
                const otherNode = otherEditor.nodes[id];
                this.nodes[id] = new CharNode(otherNode.id, otherNode.char, otherNode.prevId, otherNode.nextId);
            }
        }

        // 更新 head 和 tail
        if (otherEditor.head !== null && (this.head === null || otherEditor.head < this.head)) {
            this.head = otherEditor.head;
        }
        if (otherEditor.tail !== null && (this.tail === null || otherEditor.tail > this.tail)) {
            this.tail = otherEditor.tail;
        }
        // 重新连接链表，保证顺序正确
        this.reconnectList();
    }

    // 重新连接链表
    reconnectList() {
        // 找到最小的 ID 作为 head
        let minId = null;
        for (const id in this.nodes) {
            if (minId === null || id < minId) {
                minId = id;
            }
        }
        this.head = minId;

        // 根据 ID 排序所有节点
        const sortedNodes = Object.values(this.nodes).sort((a, b) => a.id - b.id);

        // 重新连接链表
        for (let i = 0; i < sortedNodes.length; i++) {
            const node = sortedNodes[i];
            if (i === 0) {
                node.prevId = null;
                this.head = node.id;
            } else {
                node.prevId = sortedNodes[i - 1].id;
            }

            if (i === sortedNodes.length - 1) {
                node.nextId = null;
                this.tail = node.id;
            } else {
                node.nextId = sortedNodes[i + 1].id;
            }
        }
    }
}

// 示例
const editor1 = new CrdtTextEditor();
editor1.insert('A', null); // 插入到开头
editor1.insert('B', editor1.tail);
editor1.insert('D', editor1.tail);
editor1.delete(editor1.nodes[editor1.tail].id);
editor1.insert('C', editor1.tail);

const editor2 = new CrdtTextEditor();
editor2.insert('1', null); // 插入到开头
editor2.insert('2', editor2.tail);

editor1.merge(editor2);

console.log("Editor 1 Text:", editor1.getText()); // 输出: A12BC

六、总结

OT 和 CRDT 都是解决协作编辑冲突的有效方法，但是它们各有优缺点。 选择哪种方法取决于你的具体需求。

  • 如果你的应用程序对实时性要求很高，并且可以接受一定的服务器依赖，那么 OT 可能更适合你。
  • 如果你的应用程序需要支持离线协作，并且对数据结构有一定的灵活性限制，那么 CRDT 可能更适合你。

当然，还有一些混合的方法，比如使用 OT 来处理实时性要求高的操作，使用 CRDT 来处理离线协作。

希望今天的讲座能够帮助你更好地理解 OT 和 CRDT，并在你的项目中做出更明智的选择。 谢谢大家！ 散会！

发表回复

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