CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 3 of 7 · 2 min read

Four designs

Counters, UUID, ticket server, snowflake.

The book compares four options.

Multi-master replication. Use several databases. Instead of adding 1 each time, each database adds k, where k is the number of databases. With two databases, one makes 1, 3, 5 and the other 2, 4, 6. IDs stay unique, and the count of IDs grows with the number of servers. The drawbacks listed in the book: it is hard to spread over several data centres, the IDs do not rise with time across servers, and adding or removing a server breaks the pattern.

UUID. A UUID is a 128-bit number made by each server on its own, with no coordination. The book quotes a figure: to reach a 50 per cent chance of one duplicate, a system would need to make 1 billion UUIDs per second for about 100 years. Pros: simple, no shared state, scales with the web servers. Cons: 128 bits is twice the 64 bits wanted, IDs do not rise with time, and they may contain letters.

Ticket server. One database with auto-increment hands out numbers to everyone. The book credits Flickr with this idea. Pros: numbers only, and easy to build, fine for small and medium systems. Con: a single point of failure. Adding more ticket servers brings back the problem of keeping them in step.

Snowflake layout. Twitter's "snowflake" does not make a plain counter. It builds each ID from parts (divide and conquer). Each machine makes IDs alone, with no call to anyone else, and the parts guarantee that two machines never make the same one.

Design Unique 64-bit Time order No central server
Multi-master counters yes yes no yes, but fragile when servers change
UUID almost surely no (128) no yes
Ticket server yes yes roughly no, single point
Snowflake layout yes yes yes yes

Only the last meets all five requirements, so the book picks it.

Check yourself: 1. Why do IDs from multi-master counters not rise with time? 2. Which design needs no coordination but gives 128 bits? 3. What is the weakness of a single ticket server?