CSE Roadmap

Specialist tier · about 5 hours · 8 parts

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.