Design Collaborative Editing

Prompt latihan

1. Problem Statement, Functional Requirements, and Scale Assumptions

   Tentukan ruang lingkup pengeditan dokumen kolaboratif real-time: beberapa pengguna dapat mengedit dokumen yang sama secara bersamaan dan melihat perubahan satu sama lain secara near real-time (seperti Google Docs). Pengguna melihat posisi cursor editor lain, dokumen mendukung operasi insert/delete/format teks, dan version history memungkinkan pemulihan state sebelumnya. Kecualikan secara eksplisit: sinkronisasi offline editing (asumsikan konektivitas jaringan diperlukan), tool menggambar/diagram, formula spreadsheet, audio/video real-time, dan klien mobile-native. Nyatakan asumsi skala: editor bersamaan per dokumen (tipikal vs. puncak), total dokumen aktif, operasi edit per detik per dokumen aktif, dan frekuensi update presence cursor.

2. Non-Functional Requirements

   Tentukan NFR utama: latensi propagasi edit (seberapa cepat editor lain harus melihat perubahan saya, di bawah 200ms memberi kesan real-time; di atas 500ms terasa lag), kebenaran conflict resolution (dua pengguna yang mengedit posisi yang sama secara bersamaan tidak boleh mengakibatkan teks hilang atau rusak, definisikan apa arti kebenaran di sini), kesegaran presence cursor (seberapa basi yang dapat diterima untuk menampilkan posisi cursor, 500ms? 1 detik?), durabilitas version history (apakah semua versi antara dipertahankan atau hanya checkpoint?), dan ketersediaan dokumen saat outage server parsial (apakah pengeditan dapat berlanjut jika satu node server gagal?).

3. Quantitative Analysis

   Estimasikan: laju operasi edit per dokumen aktif (sesi dengan 5 editor menghasilkan ~10 ops/detik per editor = 50 ops/detik/dokumen), jumlah koneksi WebSocket (1 juta editor bersamaan × 1 koneksi = 1 juta koneksi), bandwidth update presence cursor (1 juta editor × 1 update/200ms × 50 byte/update = 250MB/s), laju pertumbuhan log operasi dokumen (50 ops/s × 100 byte/op = 5KB/s per dokumen, berapa banyak storage setelah 1 jam pengeditan aktif?), dan jumlah node server yang dibutuhkan untuk menangani 1 juta koneksi WebSocket.

4. API Design

   Tentukan operasi API untuk: membuka sesi pengeditan dokumen (WebSocket CONNECT, membangun koneksi, menerima snapshot dokumen + riwayat operasi sejak sinkronisasi terakhir), mengirim operasi edit (WebSocket SEND OP: {op_type: insert|delete|format, position, content, client_seq_num}), menerima operasi yang di-broadcast dari editor lain (WebSocket RECEIVE OP dari server: {op_type, position, content, server_seq_num, user_id}), mengambil snapshot dokumen (REST GET /documents/{id}), mengambil version history (REST GET /documents/{id}/versions), dan memulihkan sebuah versi (REST POST /documents/{id}/restore). Jelaskan bagaimana client_seq_num dan server_seq_num memungkinkan deteksi konflik dan pengurutan operasi.

5. High-Level Design

   Usulkan komponen utama: collaboration gateway (server WebSocket, merutekan koneksi editor, menerima ops, mem-broadcast ke editor lain dalam sesi dokumen), document service (mempersistensi konten dokumen dan menyajikan snapshot), operation log (log append-only dari semua ops dalam urutan server, sumber kebenaran untuk conflict resolution), conflict resolver (mesin OT atau merge CRDT, men-transform atau me-merge ops bersamaan untuk menjaga konvergensi), presence service (melacak dan mem-broadcast posisi cursor), dan version history store (checkpoint atau operation log penuh untuk restore versi). Jelaskan bagaimana editor yang baru bergabung menerima state dokumen saat ini dan bagaimana dua edit bersamaan pada posisi yang sama diselesaikan tanpa karakter yang hilang.

6. Additional High-Level Design Prompts

   Bahas tiga area lanjutan: (1) Pengurutan operasi lintas beberapa server gateway, jika dua editor terhubung ke node gateway yang berbeda dan mengirim ops secara bersamaan, bagaimana sistem menetapkan pengurutan sisi-server yang kanonik sehingga semua klien konvergen ke state dokumen yang sama? (2) Protokol heartbeat presence, posisi cursor adalah state ephemeral; jika koneksi pengguna terputus, seberapa cepat cursornya harus hilang dari tampilan editor lain, dan mekanisme apa yang memastikan state presence dibersihkan tanpa notifikasi disconnect? (3) Undo/redo dengan edit bersamaan, jika pengguna A mengetik sebuah kata dan pengguna B secara bersamaan menghapus posisi tersebut, lalu pengguna A menekan Undo, apa perilaku yang benar, dan apakah mungkin mengimplementasikan local undo secara benar dengan OT?

7. Deep Dives

   Deep dive ke tiga area: (1) OT vs. CRDT, Operational Transformation (OT): setiap klien mengirim ops ke server pusat yang menetapkan sequence number dan men-transform ops bersamaan sebelum mem-broadcast; fungsi transform harus memenuhi properti TP1 (f(op_a, op_b) · op_b' = f(op_b, op_a) · op_a'); kompleksitas transform O(n²) untuk n ops bersamaan; teruji baik pada skala besar (Google Docs menggunakan OT via Operational Transformation + algoritma Jupiter); bottleneck: semua ops harus mengalir melalui satu otoritas pengurutan; Conflict-Free Replicated Data Type (CRDT): setiap op direpresentasikan sebagai tipe data yang komutatif dan asosiatif (mis. RGA, Replicated Growable Array menetapkan pengenal posisi unik untuk setiap karakter); tidak perlu koordinator pusat; operasi dapat diterapkan dalam urutan apa pun dan konvergen ke state yang sama; overhead: setiap karakter membawa ID unik (memori lebih tinggi); CRDT lebih kompleks untuk diimplementasikan secara benar; lebih baik untuk peer-to-peer atau multi-master; pilih OT untuk pengeditan kolaboratif single-server dengan kebutuhan latensi ketat; pilih CRDT untuk multi-region atau peer-to-peer dengan eventual consistency; (2) Presence cursor, posisi cursor adalah stream kontinu (update posisi setiap keystroke); diimplementasikan sebagai key ephemeral di Redis: `cursor:{doc_id}:{user_id}` = {position, user_id, color}; heartbeat: klien mengirim posisi setiap 200ms; TTL: 2 detik (5 heartbeat terlewat = cursor dihapus); saat disconnect: cursor dihapus segera via event WebSocket close atau setelah TTL; reconnection: cursor muncul kembali saat heartbeat dilanjutkan; state presence bersifat eventually consistent, sedikit lag posisi dapat diterima; (3) Pengurutan operasional, dengan beberapa server gateway, ops dari klien berbeda mungkin tiba dalam urutan berbeda; sisi-server: operation log pusat dengan sequence number yang meningkat monoton yang ditetapkan saat ingestion; sisi-klien: rebase klien, setiap klien menerapkan ops dalam urutan lokal lalu menerima urutan kanonik server dan me-rebase ops lokal yang belum di-ack di atasnya; causal ordering: klien mengirim parent_seq_num (op server terakhir yang telah dilihatnya) untuk menandakan konteks kausal; server menolak ops dengan parent_seq_num basi di luar toleransi window.

8. Final Review Handoff Readiness

   Ringkas keputusan desain utama: pendekatan conflict resolution (OT dengan server pusat vs. CRDT), operation log sebagai sumber kebenaran, presence cursor dengan heartbeat TTL, sequence number yang ditetapkan server untuk pengurutan kanonik, rebasing klien untuk konvergensi tanpa celah, dan version history via kompaksi operation log. Soroti dua pertanyaan terbuka terbesar yang tersisa (kebenaran transform OT pada interaksi delete-insert di posisi yang sama, memerlukan verifikasi formal, dan latensi reconnection presence, jika pengguna kehilangan konektivitas sesaat, berapa lama sebelum cursornya berkedip) dan usulkan rollout bertahap: pengeditan kolaboratif single-document (2 editor bersamaan) dulu, lalu skalakan ke dokumen dengan 50 editor.

Preview solusi

Solution: Design Collaborative Editing Framing Problem Pengeditan dokumen kolaboratif secara real-time memungkinkan banyak user memodifikasi dokumen yang sama secara bersamaan dan melihat perubahan satu sama lain secara near real-time (nyaris seketika). Tantangan intinya adalah conflict resolution (resolusi konflik): dua user yang mengedit posisi yang sama t…