# Interviewer: the more detailed the snowflake algorithm, the better

• 💻 Sword finger offer & leetcode question brushing warehouse: https://github.com/Damaer/CodeSolution
• 📒 Programming knowledge base: https://github.com/Damaer/Coding

## SnowFlake algorithm

According to Charles Knight of the National Center for atmospheric research, the average snowflake consists of about 10 ^ 19 water molecules. In the process of snowflake formation, different structural branches will be formed. Therefore, there are no two identical snowflakes in nature. Each snowflake has its own beautiful and unique shape. The snowflake algorithm indicates that the generated id is as unique as snowflake. snowflake is Twitter's open source distributed ID generation algorithm, and the result is a long ID. Its core idea is to use 41bit as the number of milliseconds, 10bit as the machine ID (five bits are the data center and five bit machine ID), 12bit as the serial number within milliseconds (meaning that each node can generate 4096 IDS per millisecond), and finally there is a symbol bit, which is always 0.

Core idea: distributed, unique.

## Algorithm specific introduction

Snowflake algorithm is a 64 bit binary, which consists of four parts:

• 1 bit is the sign bit, that is, the highest bit. It is always 0, which makes no sense, because if the only computer binary complement is negative, 0 is positive.
• 41 bits are time stamps, specific to milliseconds. 41 bits of binary can be used for 69 years. Because time increases forever in theory, it is possible to sort according to this order.
• 10 digits are machine identification, which can be used as machine ID or machine room ID + machine ID. 10 digits can represent 1024 machines at most.
• The 12 digit serial number is the counting serial number, which means that different IDS can be generated at the same time on the same machine. The 12 digit serial number can distinguish 4096 IDs.

### optimization

Since the 41 bit is a time stamp, our time calculation began in 1970 and can only be used for 69 years. In order not to waste, in fact, we can use the relative value of time, that is, taking the starting time of the project as the base time, and we can use 69 years in the future. The service for obtaining the unique ID requires high processing speed, so we all use bit operation and displacement operation. System can be used to obtain the current time currentTimeMillis().

### Time callback problem

When obtaining time, there may be a problem of time callback. What is time callback? That is, the time on the server suddenly goes back to the previous time.

1. The time of the system environment has been changed for human reasons.
2. Sometimes different machines need to synchronize time. There may be errors between different machines, so the problem of time callback may occur.

Solution

1. When the callback time is small, the ID is not generated, and the loop waits until the time point arrives.
2. The above scheme is only suitable for those with small clock callback. If the interval is too large, blocking and waiting is certainly not desirable. Therefore, either an error is reported directly and the service is refused for callback exceeding a certain size, or one scheme is to use the extension bit and add 1 to the extension bit after callback, so that the ID can still remain unique. But this requires us to reserve a certain number of digits in advance, either from the machine ID or from the serial number. When the time is dialed back, this position is + 1.

In fact, Baidu and meituan have their own solutions to the problem of producing duplicate ID S caused by time callback. If you are interested, you can go and have a look. The following is not the information in their official website documents:

• UidGenerator is a unique ID generator implemented in Java and based on Snowflake algorithm. UidGenerator works in application projects in the form of components and supports custom workerId bits and initialization strategies, which is suitable for automatic instance restart, drift and other scenarios in virtual environments such as docker. In terms of implementation, UidGenerator solves the natural concurrency limitation of sequence by borrowing the future time; RingBuffer is used to cache the generated UID, parallelize the production and consumption of UID, and supplement the CacheLine to avoid the hardware level "pseudo sharing" problem caused by RingBuffer The final single QPS can reach 6 million.
• Meituan Leaf:https://tech.meituan.com/2019/03/07/open-source-project-leaf.html
• Use the feature of Zookeeper persistent order node to automatically configure workerID for snowflake node
• Cache the workerID to reduce the dependence of third-party components
• Due to its strong dependence on the clock, it is sensitive to the requirements of time. NTP synchronization will also cause second level fallback when the machine is working. It is recommended to turn off NTP synchronization directly. Or when the clock is dialed back, the service is not provided directly and error is returned directly_ Code, wait until the clock catches up. Or do a layer retry and report to the alarm system, or automatically remove its own node and give an alarm after it is found that the clock sometimes dials back
• 1. Start the leaf snowflake service, connect Zookeeper and_ Under the forever parent node, check whether you have registered (whether there are children in this order).
• 2. If you have registered, directly retrieve your workerID (int type ID number generated by zk sequence node) and start the service.
• 3. If you have not registered, create a persistent sequence node under the parent node. After successful creation, retrieve the sequence number as your workerID number and start the service.
• Optimization: double buffer + pre allocation
• Disaster recovery: Mysql DB, one master and two slaves, remote computer room, semi synchronous mode
• Disadvantages: if the segment scheme is used: the ID is incremented and can be calculated, it is not applicable to the scenario of order ID generation. For example, if the competing pairs place orders respectively at 12 noon on two days, the order quantity of the company in one day can be roughly calculated by subtracting the order ID number. This is intolerable.
• Leaf segment scheme
• Leaf snowflake scheme

## Code display

```public class SnowFlake {

// Data center (machine room) id
private long datacenterId;
// Machine ID
private long workerId;
// Same time series
private long sequence;

public SnowFlake(long workerId, long datacenterId) {
this(workerId, datacenterId, 0);
}

public SnowFlake(long workerId, long datacenterId, long sequence) {
// Legal judgment
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}

// Start time stamp (20210-22:32)
private long twepoch = 1634393012000L;

// Machine room number, the number of digits occupied by the ID of the machine room is 5 bit s, the maximum is 11111 (binary) - > 31 (decimal)
private long datacenterIdBits = 5L;

// The maximum number of digits occupied by the machine ID is 5 bit s: 11111 (binary) - > 31 (decimal)
private long workerIdBits = 5L;

// 5 bit can only have 31 digits at most, that is, the machine id can only be within 32 at most
private long maxWorkerId = -1L ^ (-1L << workerIdBits);

// 5-bit can only have 31 digits at most, and the machine room id can only be within 32 at most
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

// The number of bits occupied by the sequence at the same time is 12 bits 111111111111 = 4095. At most, 4096 bits are generated in the same millisecond
private long sequenceBits = 12L;

// Offset of workerId
private long workerIdShift = sequenceBits;

// Offset of datacenter ID
private long datacenterIdShift = sequenceBits + workerIdBits;

// Offset of timestampLeft
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

// Serial number mask 4095 (0b111111 = 0xfff = 4095)
// It is used for the sum operation of serial number to ensure that the maximum value of serial number is between 0-4095
private long sequenceMask = -1L ^ (-1L << sequenceBits);

// Last timestamp
private long lastTimestamp = -1L;

// Get machine ID
public long getWorkerId() {
return workerId;
}

// Get machine room ID
public long getDatacenterId() {
return datacenterId;
}

// Get the latest timestamp
public long getLastTimestamp() {
return lastTimestamp;
}

// Get the next random ID
public synchronized long nextId() {
// Gets the current timestamp in milliseconds
long timestamp = timeGen();

if (timestamp < lastTimestamp) {
System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}

// duplicate removal
if (lastTimestamp == timestamp) {

sequence = (sequence + 1) & sequenceMask;

// Sequence sequence is greater than 4095
if (sequence == 0) {
// Method called to the next timestamp
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// If it is the first acquisition of the current time, it is set to 0
sequence = 0;
}

// Record the last timestamp
lastTimestamp = timestamp;

// Offset calculation
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}

private long tilNextMillis(long lastTimestamp) {
// Get latest timestamp
long timestamp = timeGen();
// If the latest timestamp is found to be less than or equal to the timestamp whose serial number has exceeded 4095
while (timestamp <= lastTimestamp) {
// If not, continue
timestamp = timeGen();
}
return timestamp;
}

private long timeGen() {
return System.currentTimeMillis();
}

public static void main(String[] args) {
SnowFlake worker = new SnowFlake(1, 1);
long timer = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
worker.nextId();
}
System.out.println(System.currentTimeMillis());
System.out.println(System.currentTimeMillis() - timer);
}

}

```

## problem analysis

### 1. First, why not use it?

In the computer representation, the first bit is the sign bit, 0 represents the integer, and if the first bit is 1, it represents a negative number. The ID we use is a positive number by default, so the default is 0, so this bit is meaningless by default.

### 2. How to use the machine position?

Machine bits or machine room bits, a total of 10 bit s. If all represent machines, it can represent 1024 machines. If split, 5 bits represent the machine room and 5 bits represent the machines in the machine room, there can be 32 machine rooms, and 32 machines can be used in each machine room.

### 3. What does tweet mean?

Since the timestamp can only be used for 69 years, and our timing starts in 1970, this tweet represents the time from the beginning of the project. Using the time of generating ID minus tweet as the timestamp can be used for a longer time.

### 4. What does - 1L ^ (- 1L < < x) mean?

Indicates how many values can be represented by x-bit binary, assuming that x is 3:

In the computer, the first bit is the sign bit, the inverse code of negative number is in addition to the sign bit, 1 becomes 0, 0 becomes 1, and the complement is the inverse code + 1:

```-1L Original code: 1000 0001
-1L Inverse code: 1111 1110
-1L Complement: 1111 1111
```

From the above results, we can know that - 1L is actually all 1 in binary. Then - 1L moves 3 bits to the left to get 1111 1000, that is, the last 3 bits are 0. After XOR calculation with - 1L, we actually get that the last 3 bits are all 1- 1L ^ (- 1L < < x) represents the value that x bits are all 1, that is, the maximum value that x-bit binary can represent.

### 5. Timestamp comparison

When the acquired timestamp is less than the last acquired timestamp, the ID cannot be generated, but continues to cycle until the available ID is generated. Here, the extended bit is not used to prevent clock callback.

### 6. The accuracy is lost when the front end is directly used

If the front end directly uses the long type id generated by the server, the accuracy will be lost, because the Number in JS is 16 bits (referring to the decimal Number), while the longest Number calculated by the snowflake algorithm is 19 bits. At this time, String needs to be used as an intermediate conversion and output to the front end.

## Qin Huaiyi's viewpoint

In fact, the snowflake algorithm depends on the consistency of time. If the time is dialed back, there may be problems. It is generally solved by using the extended bit. The time limit of 69 years can only be used. In fact, you can set more digits of the timestamp according to your own needs. For example, 42 digits can be used for 139 years, but many companies have to survive first. Of course, the snowflake algorithm is not a silver bullet. It also has disadvantages. It increases on a single machine, while multiple machines only increase roughly, not strictly.

There is no best design scheme, only suitable and inappropriate schemes.

Added by smclay on Thu, 17 Feb 2022 03:32:32 +0200