Bạn có biết làm thế nào để 100 người cùng sửa một file Google Docs, cùng lúc, mà không ai bị khóa file, không ai bị ghi đè, và cuối cùng ai cũng thấy đúng một nội dung giống hệt nhau không?
Nghe thì tưởng đơn giản: “thì gửi thay đổi lên server rồi server gộp lại thôi”. Nhưng mình đã thử tự viết một editor cộng tác nhỏ theo đúng cách nghĩ đó, và nó hỏng ngay ở lần test đầu tiên với hai tab trình duyệt. Văn bản ở hai tab lệch nhau vài ký tự, và càng gõ thì càng lệch.
Bài này đi theo đúng thứ tự mình đã gặp: bài toán trước, các cách “hiển nhiên” thất bại ra sao, rồi mới đến thuật toán giải quyết nó: Operational Transformation (OT).
Bài toán: hai người, một chuỗi, hai cú gõ cùng lúc
Bỏ qua 100 người, bắt đầu với hai người thôi. Tài liệu hiện tại là chuỗi "abc". Cả hai cùng mở nó, mỗi người có một bản sao trên máy mình:
- Người A chèn ký tự
"X"vào vị trí 0. - Người B xóa ký tự ở vị trí 2 (tức là chữ
"c").
Hai thao tác này xảy ra đồng thời, trước khi máy này kịp nhận thao tác của máy kia. Sau đó mỗi bên gửi thao tác của mình cho bên còn lại và áp dụng nguyên xi:
Máy A: "abc" → insert(0, "X") → "Xabc"
nhận delete(2) của B → xóa ký tự ở vị trí 2 → "Xac" ❌ (xóa nhầm chữ "b")
Máy B: "abc" → delete(2) → "ab"
nhận insert(0, "X") của A → "Xab" ✅
Kết quả: máy A = "Xac", máy B = "Xab" → phân kỳLỗi nằm ở chỗ: lúc B ra lệnh “xóa vị trí 2”, vị trí 2 là chữ c trong tài liệu của B. Khi lệnh đó đến máy A, tài liệu của A đã dài thêm một ký tự ở đầu, nên “vị trí 2” giờ trỏ vào chữ b. Thao tác vẫn y nguyên, nhưng ngữ cảnh của nó đã đổi.
Giờ nhân lên: 100 người, mỗi người gõ vài ký tự mỗi giây, mạng có độ trễ khác nhau. Số cặp thao tác “đụng ngữ cảnh nhau” tăng nhanh đến mức không thể xử lý bằng mắt hay bằng if-else rải rác.
Ba cách “hiển nhiên” và vì sao đều không ổn
| Cách làm | Ý tưởng | Vấn đề |
|---|---|---|
| Khóa file (lock) | Ai đang sửa thì giữ khóa, người khác chờ | 100 người xếp hàng chờ nhau. Không còn là “cộng tác thời gian thực” |
| Last-write-wins | Ai lưu sau thì bản của người đó thắng | Người lưu trước mất sạch thay đổi mà không hề hay biết |
| Diff / merge kiểu Git | Gộp hai nhánh, có conflict thì giải tay | Chạy tốt với commit, nhưng không ai muốn bấm “resolve conflict” mỗi lần gõ một chữ |
Cả ba đều né bài toán thay vì giải nó. Thứ cần có là một cách để hai thao tác đồng thời cùng được giữ lại, và cả hai máy vẫn hội tụ về một kết quả giống nhau. Đó là chỗ OT xuất hiện.
Operational Transformation là gì?
OT là một họ thuật toán cho phép nhiều người sửa cùng một tài liệu đồng thời, bằng cách biến đổi (transform) mỗi thao tác nhận được sao cho nó vẫn đúng ý định ban đầu của người gửi, dù tài liệu đã bị các thao tác khác thay đổi trong lúc đó.
Analogy dễ hình dung nhất là xếp hàng mua vé. Bạn đứng thứ 3 trong hàng và nhắn bạn mình “đứng ngay sau mình nhé”. Nếu trong lúc đó có một người chen vào đầu hàng, bạn giờ đứng thứ 4. Câu “đứng sau mình” vẫn đúng, nhưng con số tuyệt đối đã đổi. OT làm đúng việc đó cho văn bản: giữ nguyên ý định (“xóa chữ c”) và tự cập nhật lại tọa độ (vị trí 2 thành vị trí 3) khi có thao tác khác chen vào trước.
Mọi thay đổi được mô hình hóa thành các operation đơn giản: insert, delete và (trong nhiều thư viện) retain để “đi qua” một đoạn không đổi. Phần cốt lõi là một hàm transform(a, b): cho thao tác a và thao tác b xảy ra đồng thời, trả về phiên bản của a đã được điều chỉnh để áp dụng sau khi b đã được áp dụng.
Transform hoạt động như thế nào: tự viết bản tối giản
Mình viết bản rút gọn với hai loại thao tác, insert một chuỗi và delete một ký tự, đủ để thấy toàn bộ ý tưởng:
function apply(doc, op) {
if (op.type === 'insert') return doc.slice(0, op.pos) + op.text + doc.slice(op.pos);
if (op.type === 'delete') return doc.slice(0, op.pos) + doc.slice(op.pos + 1);
return doc; // noop
}
// Biến đổi a để áp dụng được SAU khi b đã được áp dụng
function transform(a, b, aWinsTie = false) {
if (a.type === 'insert' && b.type === 'insert') {
// b chèn trước a (hoặc cùng chỗ mà b thắng) thì a bị đẩy lùi
if (b.pos < a.pos || (b.pos === a.pos && !aWinsTie)) {
return { ...a, pos: a.pos + b.text.length };
}
return a;
}
if (a.type === 'insert' && b.type === 'delete') {
return b.pos < a.pos ? { ...a, pos: a.pos - 1 } : a;
}
if (a.type === 'delete' && b.type === 'insert') {
return b.pos <= a.pos ? { ...a, pos: a.pos + b.text.length } : a;
}
// delete vs delete
if (b.pos < a.pos) return { ...a, pos: a.pos - 1 };
if (b.pos === a.pos) return { type: 'noop' }; // cùng một ký tự đã bị xóa rồi
return a;
}Chạy lại đúng ví dụ ở đầu bài:
const doc = 'abc';
const A = { type: 'insert', pos: 0, text: 'X' };
const B = { type: 'delete', pos: 2 };
// Máy A: đã áp dụng A, nhận B → transform B qua A
const siteA = apply(apply(doc, A), transform(B, A)); // B.pos: 2 → 3
// Máy B: đã áp dụng B, nhận A → transform A qua B
const siteB = apply(apply(doc, B), transform(A, B)); // A.pos giữ nguyên
console.log(siteA, siteB); // "Xab" "Xab" ✅Hai máy giờ cùng ra "Xab". Để ý tham số aWinsTie: khi hai người cùng chèn vào đúng một vị trí, phải có quy ước ai đứng trước (thường dựa vào ID của client). Nếu không có quy ước này, cả hai cùng nhường hoặc cùng giành, và kết quả lại phân kỳ.
Từ 2 người lên 100 người: vai trò của server
Transform giữa hai thao tác thì dễ. Khó là khi 100 client cùng gửi lên, mỗi người đang ở một phiên bản tài liệu khác nhau. Các hệ thống OT thực tế (kiểu ShareDB, hay giao thức mà Google Wave từng dùng) giải quyết bằng cách đặt một server trung tâm làm trọng tài. Hình dung nó như người thư ký ghi biên bản cuộc họp: ai nói gì cũng phải qua thư ký, và thư ký quyết định thứ tự ghi.
- Server giữ lịch sử các operation đã chấp nhận, mỗi cái có một số revision tăng dần.
- Client gửi operation kèm revision mà nó dựa trên. Ví dụ “mình sửa dựa trên bản rev 10”.
- Nếu server đã ở rev 13, nó transform operation đó lần lượt qua các operation rev 11, 12, 13, rồi áp dụng, lưu thành rev 14 và broadcast cho mọi client.
- Phía client, mỗi lúc chỉ giữ một operation đang chờ server xác nhận, phần gõ thêm được gom vào buffer. Nhờ vậy client chỉ cần transform với một luồng thao tác duy nhất từ server, thay vì với 99 người còn lại.
Điểm mấu chốt là server tuần tự hóa mọi thứ. Dù 100 người gõ cùng lúc, trên server vẫn chỉ có một dòng thời gian duy nhất. Đây cũng là lý do OT phát triển mạnh trong kiến trúc client-server và khó hơn nhiều khi bỏ server đi.
Dùng OT trong thực tế với ShareDB
Không ai nên tự viết OT cho sản phẩm thật (lý do ở phần sau). Nếu dùng Node.js, ShareDB là lựa chọn quen thuộc. Server tối giản:
// npm i sharedb ws @teamwork/websocket-json-stream
const http = require('http');
const WebSocket = require('ws');
const ShareDB = require('sharedb');
const WebSocketJSONStream = require('@teamwork/websocket-json-stream');
const backend = new ShareDB(); // mặc định lưu trong RAM, production nên gắn DB adapter
const server = http.createServer();
const wss = new WebSocket.Server({ server });
wss.on('connection', (ws) => {
backend.listen(new WebSocketJSONStream(ws));
});
server.listen(8080);Client: kết nối, mở một document và gửi operation. Type mặc định của ShareDB là json0, trong đó si là chèn chuỗi (string insert) và sd là xóa chuỗi (string delete):
const ShareDB = require('sharedb/lib/client');
const socket = new WebSocket('ws://localhost:8080');
const connection = new ShareDB.Connection(socket);
const doc = connection.get('docs', 'bai-blog-1');
doc.subscribe((err) => {
if (err) throw err;
if (!doc.type) doc.create({ content: '' });
// Mỗi khi có thay đổi (từ mình hoặc từ người khác)
doc.on('op', (op, source) => {
console.log(source ? 'Mình gõ:' : 'Người khác gõ:', doc.data.content);
});
});
// Chèn chữ "Xin chào" vào đầu nội dung
doc.submitOp([{ p: ['content', 0], si: 'Xin chào' }]);Mở hai tab chạy cùng đoạn client này, cùng gõ vào một vị trí. ShareDB tự lo phần transform và hội tụ mà bạn vừa tự viết ở trên. Với editor rich text (bold, italic, danh sách), người ta thường dùng type rich-text kết hợp với Quill.
Khi nào nên và không nên dùng OT
OT không phải đáp án cho mọi bài toán cộng tác, và nó có những cái giá thật:
- Khó cài đặt đúng. Mỗi cặp loại operation cần một quy tắc transform riêng. Có n loại thao tác thì có khoảng n² cặp cần xử lý. Đã có nhiều thuật toán OT bị phát hiện sai sót sau khi công bố, nên tự viết cho production là rủi ro lớn.
- Gắn chặt với server trung tâm. Server chết hoặc là điểm nghẽn thì cả hệ thống ảnh hưởng.
- Offline dài hạn và peer-to-peer là điểm yếu. Làm việc offline cả ngày rồi sync lại là kịch bản khó cho OT.
Hướng thay thế phổ biến là CRDT (Yjs, Automerge). Thay vì transform thao tác, CRDT thiết kế cấu trúc dữ liệu sao cho các thao tác có thể áp dụng theo bất kỳ thứ tự nào mà vẫn ra cùng kết quả:
| Tiêu chí | OT | CRDT |
|---|---|---|
| Server trung tâm | Gần như bắt buộc | Không bắt buộc |
| Offline / P2P | Khó | Phù hợp |
| Độ phức tạp | Nằm ở hàm transform | Nằm ở cấu trúc dữ liệu, thường tốn thêm metadata cho mỗi ký tự |
| Thư viện phổ biến | ShareDB, ot.js | Yjs, Automerge |
Quan điểm của mình: nếu bạn đã có server, document chủ yếu là text và cần hệ thống ổn định ngay, ShareDB vẫn là lựa chọn ổn. Nếu bắt đầu một dự án mới và cần offline-first hoặc P2P, mình sẽ xem Yjs trước. Còn nếu app chỉ có 2-3 người thỉnh thoảng sửa cùng lúc, last-write-wins kèm cảnh báo conflict đã đủ, đừng kéo OT vào cho phức tạp.
Câu trả lời cho câu hỏi đầu bài là: không ai “gộp” cả. Hệ thống không hỏi “ai đúng”, mà hỏi “thao tác này còn đúng ý định không sau khi những thao tác kia xảy ra”, rồi sửa tọa độ cho khớp. 100 người sửa chung một file được là nhờ cái hàm transform nhỏ ấy, cộng với một server giữ thứ tự.
Tóm lại những gì cần nhớ:
- Vấn đề gốc: vị trí của một thao tác chỉ đúng trong ngữ cảnh lúc nó được tạo ra. Áp dụng nguyên xi ở máy khác sẽ phân kỳ.
- OT giữ ý định bằng cách biến đổi tọa độ của thao tác nhận được dựa trên các thao tác đã xảy ra đồng thời.
- Hệ thống thực tế dùng server trung tâm đánh số revision và tuần tự hóa mọi operation.
- Đừng tự viết OT cho production. Dùng ShareDB hoặc cân nhắc CRDT như Yjs, Automerge.
- Không phải app nào cũng cần cộng tác real-time. Ít người, ít xung đột thì giải pháp đơn giản hơn là đủ.
Copy đoạn transform ở trên vào một file ot.js, chạy bằng node, rồi thử thêm ca “hai người cùng insert vào đúng vị trí 0”. Bạn sẽ thấy ngay vì sao cần tham số aWinsTie. Chỉ mất 10 phút và bạn sẽ hiểu OT sâu hơn đọc thêm mười bài lý thuyết.
Chúc anh em code vui! 🚀
Tags: #OperationalTransformation #OT #RealtimeCollaboration #ShareDB #CRDT #GoogleDocs #DistributedSystems