SnowFlake algorithm , yes Twitter Open source distributed id generating algorithm . The core idea is : Use a 64 bit Of long Number of type as global unique
id. Widely used in distributed system , And ID Time stamp introduced , Basically self increasing , There are detailed comments in the following code .

 

this 64 individual bit in , among 1 individual bit No need , And then use the 41 bit As milliseconds , use 10 bit As working machine id,12 bit
As serial number .

 

Let me give you an example , Like the one below 64 bit Of long Type number :

*
First part , yes 1 individual bit:0, This is meaningless .

*
The second part is 41 individual bit: Time stamp .

*
The third part is 5 individual bit: It means the machine room id,10001.

*
The fourth part is 5 individual bit: It's a machine id,1 1001.

*
The fifth part is 12 individual bit: Indicated sequence number , It's generated at the same time in a millisecond on a machine in a computer room id No. of ,0000 00000000.

 

①1 bit: No need , Why ?

 

Because the first binary bit For if it is 1, So it's all negative , But we generated id All positive numbers , So the first bit Unity is 0.

 

②41 bit: Time stamp , In milliseconds .

 

41 bit Up to numbers can be represented 2^41 - 1, That is to say, it can be identified 2 ^ 41 - 1 Milliseconds , Conversion to adult means 69 Year time .

 

③10 bit: Record working machine id, It represents that this service can be deployed at most in 2^10 On machines , that is 1024 Machines .

 

however 10 bit in 5 individual bit Representative machine room id,5 individual bit On behalf of the machine id. It means the most representative 2 ^ 5 Machine rooms (32
Machine rooms ), Each computer room can represent 2 ^ 5 Machines (32 Machines ), It can also be determined according to the actual situation of the company .

 

④12 bit: This is used to record the difference within the same millisecond id.

 

12 bit The largest positive integer that can be represented is 2 ^ 12 - 1 = 4096, That is to say, you can use this 12 bit Represents a number to distinguish between 4096
Different id.

 

In a nutshell , One of your services is supposed to generate a globally unique id, Then you can send a request to the deployment SnowFlake Algorithmic system , By this SnowFlake
Algorithm system to generate unique id.

 

this SnowFlake The algorithm system must first know its own computer room and machine , For example, the computer room id = 17, machine id = 12.

 

next SnowFlake After the algorithm system receives the request , First of all, a binary operation will be used to generate a 64 bit Of long type id,64 individual bit
First of bit It's meaningless .

 

next 41 individual bit, You can use the current timestamp ( Units to milliseconds ), And then 5 individual bit Set up this computer room id, also 5 individual bit Set up the machine id.

 

Finally, let's judge , Within one millisecond on this machine in the current machine room , This is the number one request , For this generation id Add a sequence number to the request of , As the last 12 individual bit.

 

The last one 64 individual bit Of id It's coming out , be similar to :

 

This algorithm can guarantee that , On a machine in a machine room , In the same millisecond , Generated a unique id. More than one may be generated in one millisecond id, But in the end 12 individual bit
To distinguish .

 

Let's take a look at this SnowFlake A code implementation of the algorithm , This is an example , If you understand that, then , You can try to change this algorithm later .

 

All in all, one 64 bit Each of the bit Bit to set different flag bits , Differentiate each id.

 

SnowFlake The implementation code of the algorithm is as follows :
public class IdWorker { // Because the first binary bit For if it is 1, So it's all negative , But we generated id All positive numbers , So the first
bit Unity is 0. // machine ID 2 Base 5 position 32 Digit subtraction 1 position 31 individual private long workerId; // computer room ID 2 Base 5 position
32 Digit subtraction 1 position 31 individual private long datacenterId; // Represents multiple generated in one millisecond id Latest serial number of 12 position 4096 -1 = 4095
individual private long sequence; // Set a time initial value 2^41 - 1 Almost working 69 year private long twepoch =
1585644268888L; //5 Bit machine id private long workerIdBits = 5L; //5 Computer room of id private
long datacenterIdBits = 5L; // Generated in milliseconds id number 2 Of 12 Power private long sequenceBits =
12L; // This is a binary operation , namely 5 bit At most 31 Number , That is to say, machine id At most 32 within private long maxWorkerId =
-1L ^ (-1L << workerIdBits); // That's what it means , namely 5 bit At most 31 Number , computer room id At most 32 within private
long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); private long
workerIdShift = sequenceBits; private long datacenterIdShift = sequenceBits +
workerIdBits; private long timestampLeftShift = sequenceBits + workerIdBits +
datacenterIdBits; private long sequenceMask = -1L ^ (-1L << sequenceBits);
// Record generation time milliseconds , Judge whether it is the same 1 millisecond private long lastTimestamp = -1L; public long
getWorkerId(){ return workerId; } public long getDatacenterId() { return
datacenterId; } public long getTimestamp() { return System.currentTimeMillis();
} public IdWorker(long workerId, long datacenterId, long sequence) { //
Check the machine room id And machines id Whether more than 31 Cannot be less than 0 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)); } this.workerId = workerId; this.datacenterId =
datacenterId; this.sequence = sequence; } //
This is the core approach , By calling nextId() method , Let the current snowflake Algorithmic program generates a globally unique id public synchronized
long nextId() { // Here is to get 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)); } // The following is to say that it is assumed that in the same millisecond , Another request was sent to generate a id
// This is the time seqence Sequence number to increment 1, At most 4096 if (lastTimestamp == timestamp) { //
This means that there can only be at most one millisecond 4096 Number , No matter how much you pass in ,
// This bit operation ensures that the 4096 In this range , Avoid passing on your own sequence More than 4096 This range sequence = (sequence + 1) &
sequenceMask; // When a millisecond of time , Generated id number exceed 4095, The system will enter and wait , Until the next millisecond , The system continues to generate ID if (sequence ==
0) { timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0; } //
Here is a record of the last generation id Time stamp of , In milliseconds lastTimestamp = timestamp; //
Here is the core binary operation , Generate a 64bit Of id // Move the current timestamp to the left first , put to 41 bit there ; Machine room id Move left to 5
bit there ; Turn the machine id Move left to 5 bit there ; Put sequence number last 12 bit // And then we put them together 64 bit Binary number of , convert to 10 Base is a long type
return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId <<
datacenterIdShift) | (workerId << workerIdShift) | sequence; } /** *
When a millisecond of time , Generated id number exceed 4095, The system will enter and wait , Until the next millisecond , The system continues to generate ID * @param lastTimestamp * @return
*/ private long tilNextMillis(long lastTimestamp) { long timestamp = timeGen();
while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp;
} // Get current timestamp private long timeGen(){ return System.currentTimeMillis(); } /** *
main Test class * @param args */ public static void main(String[] args) {
System.out.println(1&4596); System.out.println(2&4596);
System.out.println(6&4596); System.out.println(6&4596);
System.out.println(6&4596); System.out.println(6&4596); // IdWorker worker =
new IdWorker(1,1,1); // for (int i = 0; i < 22; i++) { //
System.out.println(worker.nextId()); // } } }
SnowFlake Advantages of the algorithm :

(1) High performance and high availability : Build without database dependency , Built entirely in memory .

(2) Large capacity : Millions of self growth per second ID.

(3)ID Self increasing : Store in database , High index efficiency .

 

SnowFlake Disadvantages of the algorithm :

Consistency between dependency and system time , If the system time is called back , Or change , May cause id Conflict or repetition .
 

 

In fact, we don't have so many computer rooms , We can improve the algorithm , take 10bit 's machine id optimization , Business table or business related to our system .

Technology
©2019-2020 Toolsou All rights reserved,
JS How to operate java Realize the function of grabbing red packets C Language programming to find a student's grade The United Nations 《 Glory of Kings 》 Please go to the studio : To save the earth Dialogue between apple and Nissan suspended ,Apple Car How's it going ?CSS architecture design China's longest high speed rail officially opened ! The fastest way to finish the race 30.5 hour First knowledge MySQL Comprehensive review ( dried food )2021 year 1 Monthly programmer salary statistics , average 14915 element How to use it quickly html and css Write static page