Part 8 of 8 · 2 min read
Exercises
Easy
Easy 1: Operations rate (20 minutes)
600,000 active typists, each 2 operations a second. Give the operations a second, and the log bandwidth at 120 bytes each.
Done when: you write 1,200,000 per second and 144 MB/s.
Hint
600,000 × 2, then × 120 bytes.
Easy 2: Storage (20 minutes)
50 million documents at 800 KB each, including history. Give the total in TB.
Done when: you write 40 TB.
Hint
50,000,000 × 800 KB.
Easy 3: Servers (20 minutes)
Each server handles 25,000 operations a second. Peak is 1.2 million. Give the number of servers and a count with 30 per cent spare capacity.
Done when: you write 48 and about 63.
Hint
1,200,000 / 25,000, then × 1.3.
Medium
Medium 1: Transform by hand (30 minutes)
Text "HELLO". User 1 deletes position 1. User 2 inserts "!" at position 4. The server applies user 1's first. Give the transformed operation of user 2 and the final text.
Done when: you write Insert("!", 3) and "HLL!O".
Hint
A deletion before the position moves it left.
Medium 2: Same position (30 minutes)
Two users insert "A" and "B" at position 2 of "XY" at the same time. The server takes A first. Give the transform of B's operation and the final text.
Done when: you write Insert("B", 3) and the final text "XYAB", with the steps shown.
Hint
Check what a tie rule does to the second insert.
Medium 3: Tombstones (30 minutes)
A document has 10,000 visible characters and 30,000 tombstones, with 16 bytes of metadata per character. Give the metadata size and say when a clean-up is allowed.
Done when: you write 640,000 bytes (40,000 × 16) and a clean-up after all replicas saw the deletes.
Hint
40,000 characters in all, 16 bytes each.
Hard
Hard 1: Draw the architecture (60 minutes)
Draw clients, gateway, routing, owner servers, log, snapshot store and presence. Number the flow of one edit and the flow of a server crash.
Done when: a diagram with at least 7 parts and two numbered flows.
Hint
One owner per document.
Hard 2: Offline merge (60 minutes)
A user edits offline for 2 hours and sends 3,000 operations. Describe the work for OT and for a CRDT, and a limit to protect the server.
Done when: two descriptions with costs, and one limit rule.
Hint
Transform against everything since the old revision.
Hard 3: Comments anchored to text (60 minutes)
Design how a comment stays attached to a word when others insert and delete text around it. Say what happens when the word is deleted.
Done when: a design that adjusts the anchor by each operation, and a rule for deleted anchors.
Hint
Treat an anchor like a cursor.