CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Requirements (20 minutes)

Write five requirements for an ID generator from the book's questions, and one extra question you would ask.

Done when: five numbered rules and one new question.

Hint

Include uniqueness, the 64-bit limit and time order.

Easy 2: Add up the bits (20 minutes)

A layout has 1 sign bit, 39 bits of time, 4 bits of data centre, 6 bits of machine and the rest sequence. How many sequence bits, machines per data centre and IDs per millisecond per machine?

Done when: you write 14 sequence bits, 64 machines and 16,384 IDs per millisecond.

Hint

64 - 1 - 39 - 4 - 6 = 14.

Easy 3: Years of life (20 minutes)

With 41 bits of milliseconds, give the life in years. Then with 39 bits.

Done when: you write about 69.7 years, and about 17.4 years.

Hint

Divide 2^41 milliseconds by about 31.5 billion milliseconds per year.

Medium

Medium 1: Compare designs (30 minutes)

Fill the comparison table for the four designs from memory, then check it against the page.

Done when: a table with four rows and four columns, with every cell filled.

Hint

Use yes or no for each requirement.

Medium 2: Write the generator (30 minutes)

Write the snowflake generator in a language you like, with a fake clock. Make 30,000 IDs over 10 simulated milliseconds across 3 machines and show that all are unique.

Done when: a script prints 30,000 unique IDs, and a test shows the backward-clock refusal.

Hint

Shift the time by 22, the data centre by 17 and the machine by 12.

Medium 3: Decode (30 minutes)

Write a function that takes an ID and returns its time, data centre, machine and sequence. Test it on three IDs you made.

Done when: three IDs decode to the values you put in.

Hint

Use shifts and masks, the reverse of making the ID.

Hard

Hard 1: Design for a long life (60 minutes)

A service needs 50 IDs per second from at most 20 machines and must last 300 years. Choose the time unit and the bit counts, and show that it fits in 64 bits.

Done when: a layout table with bit counts and the arithmetic for life and rate.

Hint

Counting seconds instead of milliseconds saves 10 bits.

Hard 2: Machine numbers (60 minutes)

Design how 500 services each get a unique machine number at startup, and what happens when a service is restarted or when two start together. Think about failure.

Done when: a written design with a store, a lease or fixed list, and a rule for restarts.

Hint

A lease expires if a service stops renewing it.

Hard 3: Clock failure drill (60 minutes)

A machine's clock jumps back by 2 seconds. Describe three policies (refuse, wait, use last time plus one), their effect on uptime and on IDs, and choose one.

Done when: a table with three policies, each effect, and a choice with one reason.

Hint

Waiting is safe but stalls writes for 2 seconds.