CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

Trade-offs

Changing the split and keeping it up.

Tuning, trade-offs and wrap-up

Changing the split. The book notes that the lengths of the parts can be tuned to the need. If an application has few IDs per millisecond but must last for many decades, give fewer bits to the sequence and more to the time. If the machine count is huge, give more bits to the machine part. The total stays 64.

A worked example (made up). A service needs 100 IDs per second in total from at most 8 machines, and must last 200 years. Time in seconds instead of milliseconds would give 200 years in about 33 bits. With 3 bits for the machine and 20 bits for a sequence per second, the whole thing fits well within 64 bits. The lesson: pick the unit of time and the part sizes from the numbers, not by habit.

Availability. An ID generator sits on the write path of everything, so it must be highly available. Since each machine makes IDs alone, the design is naturally resilient: if one machine is down, others carry on. A common choice is to run the generator as a small library inside each service, which removes the network hop, or as a small fleet of services behind a load balancer.

Trade-offs summed up.

Choice Gain Cost
Library in each service No network hop, no extra service Each service needs a unique machine number
Central fleet of generators Fewer machine numbers to manage An extra hop on every write
Larger time part Longer life Fewer bits for sequence or machines
Wait on backward clock No collisions A short stall of writes

What to say out loud. Ask the five questions, write the requirements, and show the four designs in a table. Name the snowflake as the answer, draw the 64 bits, do the arithmetic for years and IDs per second, then raise clock problems yourself.

Common mistake

Trusting the clock. IDs from a snowflake layout stay unique only if time never goes backwards on a machine and machine numbers are never shared. State both assumptions and say how each is protected.

Interview angle

Answer in your head first, then open it.

Why not auto-increment?

One database is a single point of failure and a speed limit, and several databases give IDs that do not rise with time.

Why not UUID?

It is 128 bits, not sortable by time, and may not be numeric.

How does the snowflake layout guarantee uniqueness?

Time, data centre, machine and sequence together are different for any two IDs.

How many IDs can it make?

4,096 per millisecond per machine, and 1,024 machines.

What goes wrong?

Backward clocks, duplicate machine numbers, and running out of years.

One follow-up to try. "IDs must also not reveal how many orders a day the company makes." A reply: the time-ordered layout leaks volume, since a competitor can compare two IDs. Keep the internal ID for storage, and show customers a separate, hard-to-guess public ID, such as a random string mapped to the internal one.

Check yourself: 1. How would you change the split for a service with very few IDs but a very long life? 2. Why is the generator naturally highly available? 3. Why might sortable IDs be a privacy problem?

Words you will meet

Word Meaning
Unique ID A number that names exactly one thing
UUID A 128-bit number made without coordination
Epoch The start date from which time is counted
Sequence number A counter inside one millisecond
NTP Network Time Protocol, which keeps clocks in step
Single point of failure One part whose failure stops everything