Part 4 of 7 · 2 min read
The layout
Sign, time, place, sequence.
A 64-bit ID is split into five parts. The book uses this split.
| Part | Bits | Meaning |
|---|---|---|
| Sign | 1 | Always 0. Reserved for later |
| Timestamp | 41 | Milliseconds since a chosen start date, the epoch |
| Data centre | 5 | 2^5 = 32 data centres |
| Machine | 5 | 2^5 = 32 machines per data centre |
| Sequence | 12 | A counter that restarts at 0 every millisecond |
The parts together add to 1 + 41 + 5 + 5 + 12 = 64.
Why this works.
- Two IDs made at different times differ in the timestamp. So they differ.
- Two IDs made in the same millisecond on different machines differ in the data centre or machine part. So they differ.
- Two IDs made in the same millisecond on the same machine differ in the sequence. So they differ.
Because the timestamp is the most significant part, sorting the numbers sorts by time. Within one millisecond, the IDs order by place and sequence.
Epoch
An epoch is the starting date from which time is counted. A custom epoch close to today makes the time part smaller and delays the day it overflows.
Example: Twitter's snowflake counts from 4 November 2010. An ID's time part is the number of milliseconds since that moment.
Numbers to know (checked).
- Time: 41 bits hold up to 2^41 - 1 = 2,199,023,255,551 milliseconds. That is about 69.7 years. With the book's epoch of 1288834974657 (4 Nov 2010), the part runs out in July 2080. Choosing a later epoch buys more years.
- Sequence: 12 bits give 4,096 IDs per millisecond per machine, which is 4,096,000 per second per machine.
- Machines: 5 + 5 bits give 1,024 machines. All together, the layout can make 1,024 × 4,096,000 = 4,194,304,000 IDs per second. That is over 400,000 times the requirement of 10,000 per second, so a handful of machines is plenty. They are there for availability.
A worked example (checked by script). A machine in data centre 3 with machine number 5 makes two IDs in the same millisecond, one millisecond after the epoch plus 1,000. The time part is the same for both. The sequence is 0 for the first and 1 for the second, so the second ID is exactly one more than the first (4194717696 and 4194717697). In the next millisecond, the sequence goes back to 0 and the time part grows by one. Reading the fields back out of a number gives data centre 3, machine 5, sequence 0, as put in.
Setting the machine numbers. The data centre and machine parts are chosen when a machine starts and are generally fixed afterwards. The book warns that changing them needs a careful review, since a wrong change can create IDs that collide with another machine's.
Check yourself: 1. Why do IDs sort by time? 2. How many IDs per second can one machine make? 3. When does the 41-bit time part overflow with a custom epoch?