Common Problems
Google Docs

Functional Requirements

  • Users should be able to edit documents and have their changes propagated to other users in real-time
  • When other users make edits, they should be propagated to us in real-time

Non-Functional Requirements

  • Scalability: The system should be able to handle a growing number of users and documents without significant performance degradation. It should support thousands of concurrent users editing documents simultaneously while maintaining responsiveness.
  • Availability: The system should ensure high availability, with an uptime of 99.9% or higher. Users should be able to access and edit their documents at any time, with minimal downtime for maintenance or upgrades.
  • Data Consistency: The system should provide eventual consistency, ensuring that all users eventually see the same version of the document. Conflict resolution mechanisms must be in place to handle simultaneous edits by multiple users gracefully, ensuring that no data is lost or corrupted.

Capacity Estimation

  • Billions of users, billions of documents
  • Thousands of concurrent users are editing documents simultaneously.
  • Document sizes can be in the kilobytes.

Super bad solution:

  1. 每个用户使用websocket 链接到同一个服务器
  2. 当有用户编辑文档时，获得一个锁，锁住文档，修改完成之后释放锁，发送给服务端，服务端广播给其他用户

Issues:

  1. 文档非常大，每次编辑都要广播给所有用户，网络带宽消耗大
  2. 我们使用了锁，导致每次只能有一个用户编辑文档，性能瓶颈

Bad solution:

  1. 用户不发生整个文档到服务端，而是发送单个单词的修改到服务端，然后分发到其他用户

Issues:

  1. 仍然有很多锁争用的问题，当很多用户使用修改时
  2. 用户端需要处理非常多的 合并操作，才能保证文档的一致性，然后发送自己的修改到服务端，这个过程非常复杂

Good solution: Can we somehow allow our clients to send writes to the server as they please? This is the concept behind operational transformation.

  1. user 1 want to insert 'o' at position 1, so the code becomes 'Coodin'
  2. user 2 want to insert 'g' at position 5, the code should be 'Coding'
  3. however, the write 1 is processed first, so the code becomes 'Coodgin', we need to transform the write 2 to position 6

Operational Transformation

Centralized server takes in concurrent writes and transforms them as necessary before sending them back to clients.

Issues:

  • server needs to see all writes, eventual result depends on incoming order of writes.
  • hence, server needs to be stateful, and needs to keep track of all writes.
  • the single server will be a bottleneck, and a single point of failure.

How to implement Operational Transformation

CRDTs (Conflict-free Replicated Data Types)

CRDTs (Conflict-free Replicated Data Types) are a type of data structure designed to support concurrent modifications in distributed systems without central coordination. They allow multiple copies of data to be updated independently on different nodes and eventually ensure consistency across all copies.

CRDTs primarily come in two types:

State-based CRDTs: Each copy holds the complete state of the data, and consistency is achieved by merging the states of different copies. Operation-based CRDTs: Only operations (like add, remove) are propagated, and consistency is maintained by applying these operations on each copy. The advantages of CRDTs include high availability, good performance, and fault tolerance during network partitions. They are widely used in real-time collaboration tools, distributed databases, and other applications that require high availability.

Idea : we want to avoid having to send all writes to a single server before sending it off to clients, or else that server will be a bottleneck and a single point of failure.

CRDTs are when we can have data live on multiple servers such that when we eventually merge the CRDTs, all of the nodes converge to the same state.

high level overview

State CRDTs vs Operation CRDTs

State CRDTs:

  • Send full text document
  • Have a merge function that is commutative, associative, and idempotent(幂等)
  • this is problematic because the full text document can be very large

Operation CRDTs:

  • Just send the operation, 'insert x at position y'
  • need a merge function that is commutative, associative
  • idempotent? need to include additional metadata to ensure idempotency
    • how do we make character insertions commutative?

How to implement CRDTs

Operation CRDT Merge Function

How do we make it so that the order of our writes don't matter and we still get the same result?

Interleaving

How to solve idempotence?

how can we make sure that the same operation doesn't get applied twice?

  1. each write has associated uuid?
  2. a version vector?

开源项目

shareDB

ShareDB 是一个支持实时协作编辑的后端框架，常用于构建类似 Google Docs 的多用户协同编辑系统。它的核心基于Operational Transformation (OT)，确保多个用户同时修改相同的数据时能够保持一致性。

ShareDB 项目结构

在阅读 ShareDB 的源码之前，了解它的项目结构是关键。一般来说，ShareDB 的项目结构分为以下几个主要模块：

  1. Backend（服务端）：负责处理操作请求（operation），包括接收、校验和广播给其他连接的客户端。
  2. Client（客户端）：处理用户的操作，打包操作并发送到服务器。
  3. OT（Operational Transformation）模块：负责操作的转化和合并，确保操作顺序一致且冲突得到正确处理。
  4. Persistence Layer（持久化层）：处理数据的存储和读取。可以使用 MongoDB、Redis 等数据库。

代码原理

1. 连接与同步

客户端与 ShareDB 后端建立 WebSocket 连接，并通过这个连接与后端服务器同步数据。客户端在本地进行的修改会通过 WebSocket 发送到后端，后端再广播给其他客户端。

const sharedb = require('sharedb/lib/client');
const ReconnectingWebSocket = require('reconnecting-websocket');
const WebSocket = require('ws');
 
const socket = new ReconnectingWebSocket('ws://localhost:8080');
const connection = new sharedb.Connection(socket);

2. 文档模型

ShareDB 使用 Doc 对象来表示可共享的文档。每个 Doc 对象都有一个 ID 和版本号，用于标识和追踪文档的历史。

const doc = connection.get('examples', 'counter');
doc.subscribe(function(err) {
  if (err) throw err;
  console.log('Document data:', doc.data);
});

doc.get() 方法用于从数据库中获取文档的当前状态，subscribe() 方法则用于订阅文档的实时更新。

3. 操作（Operations）

每次用户对文档的修改都会生成一个操作（Operation）。操作不仅仅是简单的增删改查，它还记录了执行修改的上下文（比如操作发生在哪个位置）。

doc.submitOp([{p: ['counter'], na: 1}]); // 递增 counter 字段

p 表示路径，na 表示 number add 的缩写，表示递增操作。

4. OT（操作转换）

OT 是 ShareDB 的核心。它通过转换操作，确保每个客户端在接收到操作后，能正确应用这些操作，从而保持文档的一致性。OT 的基本思想是，当两个操作发生冲突时，后到达的操作会基于已经应用的操作进行调整，确保最终结果正确。

function transform(op1, op2) {
  // 假设两个客户端同时插入内容，OT 机制会调整操作，确保插入顺序一致
}

5. 持久化与存储

ShareDB 支持各种持久化机制。常用的是 MongoDB，通过 MongoDB 将操作和数据存储下来，便于后续同步和回滚。

const ShareDBMingoMemory = require('sharedb-mingo-memory');
const backend = new ShareDB({db: new ShareDBMingoMemory()});

sharedb-mingo-memory 提供了一个基于内存的数据库，但生产环境中通常会使用 MongoDB、Redis 等。

如何阅读源码

  1. 从入口开始：ShareDB 的入口通常是 index.js 文件，它定义了框架的初始化逻辑和核心功能。

  2. 核心模块：

  • Connection：客户端和服务端之间的 WebSocket 连接模块。
  • Doc：文档模型，用于管理共享文档。
  • OT：操作转换的核心逻辑，重点查看操作的应用、冲突解决和转换函数。

  1. 逐步分析：从简单的功能模块开始，比如客户端连接和基本的操作提交，再深入到操作转换和冲突处理。

  2. 跟踪数据流：追踪操作从客户端生成、传递到后端、广播给其他客户端的整个数据流动过程，理解每个步骤中的关键代码实现。

  3. 文档与注释：ShareDB 源码中有一些注释和文档，帮助理解其工作原理，结合官方文档和 README 来理解这些注释。

示例：从客户端到服务端的操作流

  • 客户端：当用户进行修改时，客户端通过 submitOp 提交操作。
  • 服务端：服务端接收到操作后，通过 applyOp 进行验证、转换，并广播给其他客户端。
  • OT 引擎：在服务端，OT 引擎会处理多个操作的冲突，最终将操作应用到文档上。

总结：ShareDB 项目通过 WebSocket 实现了实时的文档同步，利用 OT 来确保多个客户端同时编辑文档时的一致性。阅读源码时，可以从客户端、服务端、OT 和持久化模块入手，逐步理解各模块如何协作来实现 ShareDB 的功能。

http://13.58.13.54:8090/

Web CrawlerTinder