In a distributed system, how to solve the unique sequence problem, how to solve the duplication id problem, there are currently many algorithms can be solved, today we introduce a classic solution: Twitter SnowFlake.
The result of id generated by SnowFlake algorithm is a 64bit integer, and its structure is as shown in the figure below:
1 bit, don’t use it. In the binary system, the highest bit of 1 is all negative numbers, but the IDs we generate generally use integers, so the highest bit is fixed at 0.
41 bits, used to record the time stamp (milliseconds).
41 digits can represent $2^{41}-1$ numbers,
If it is only used to represent a positive integer (a positive number in a computer contains 0), the range of values that can be represented is: 0 to $2^{41}-1$, minus 1 because the range of representable values starts from 0, Not 1.
In other words, 41 bits can represent the value of $2^{41}-1$ milliseconds, and converted into a unit year is $(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69 $year
10 bits, used to record the working machine id.
Can be deployed on $2^{10} = 1024$ nodes, including 5 datacenterId and 5 workerId
The largest positive integer that can be represented by 5 bits is $2^{5}-1 = 31$, that is, the 32 numbers 0, 1, 2, 3, … 31 can be used to represent different datecenterId or workerId
12 digits, serial number, used to record different IDs generated within the same millisecond.
The largest positive integer that can be represented by 12 bits is $2^{12}-1 = 4095$, that is, 4095 numbers such as 0, 1, 2, 3,…4094 can be used to represent the same machine at the same time 4095 ID serial numbers generated within the intercept (milliseconds)
Since 64-bit integers in Java are of type long, the id generated by the SnowFlake algorithm in Java is stored in long.
SnowFlake can guarantee:
All generated ids increase in time trend
There will be no duplicate IDs in the entire distributed system (because there are datacenterId and workerId to distinguish)
Complete java code as follow:
package xxx.xxx.xxx;
/**
* Twitter_Snowflake<br>
* The structure of SnowFlake is as follows (each part is separated by -):<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
* 1 bit identification, because the long basic type is signed in Java, the highest bit is the sign bit,
* positive numbers are 0, negative numbers are 1, so id is generally positive, and the highest bit is 0<br>
* 41-bit time cutoff (millisecond level). Note that the 41-bit time cutoff is not the time cutoff for
* storing the current time, but the difference between the time cutoff (current time cutoff-start time cutoff),
* where the start time is Cut is generally the time when our id generator starts to be used,
* which is specified by our program (the startTime attribute of the IdWorker class of the program below).
* 41-bit time cutoff, you can use 69 years, year T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69,
* 10-bit data machine bits, can be deployed on 1024 nodes, including 5-bit datacenterId and 5-bit workerId 12-bit sequence,
* counting within milliseconds, 12-bit counting sequence number supports each node every millisecond (same machine, same time cut)
* to generate 4096 ID sequence numbers, which add up to exactly 64 bits, which is a Long type.
* The advantage of SnowFlake is that, as a whole, it is sorted in increments of time,
* and there is no ID collision in the entire distributed system (differentiated by data center ID and machine ID),
* and the efficiency is high. After testing, SnowFlake can generate 26 per second. Thousands of IDs.
*/
public class SnowflakeId {
// ===================Fields======================
/** Start time(2018-01-01) */
private final long twepoch = 1514736000000L;
/** Number of digits occupied by machine id */
private final long workerIdBits = 5L;
/** The number of digits occupied by the data identifier id */
private final long datacenterIdBits = 5L;
/** The maximum supported machine id, the result is 31 (this shift algorithm can quickly calculate the maximum decimal number that can be represented by a few binary numbers) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** The largest supported data identification id, the result is 31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
/** The number of digits in the id of the sequence */
private final long sequenceBits = 12L;
/** The machine ID is shifted to the left by 12 bits */
private final long workerIdShift = sequenceBits;
/** The data identification id is shifted 17 bits to the left (12+5) */
private final long datacenterIdShift = sequenceBits + workerIdBits;
/** Time truncation shifted 22 bits to the left (5+5+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
/** Generate sequence mask, here is 4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
/** Working machine ID (0~31) */
private long workerId;
/** Data center ID (0~31) */
private long datacenterId;
/** Sequence within milliseconds (0~4095) */
private long sequence = 0L;
/** Time cut of the last ID generation */
private long lastTimestamp = -1L;
//================Constructors=================
/**
* Constructor
* @param workerId work ID (0~31)
* @param datacenterId data center ID (0~31)
*/
public SnowflakeId(long workerId, long datacenterId) {
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;
}
// ================Methods===================
/**
* Get the next ID (this method is thread-safe)
* @return SnowflakeId
*/
public synchronized long nextId() {
long timestamp = timeGen();
//If the current time is less than the timestamp of the last ID generation, it means that the system clock should throw an exception after this time.
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//If it is generated at the same time, the sequence within milliseconds
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
//Sequence overflow within milliseconds
if (sequence == 0) {
//Block to the next millisecond, get a new timestamp
timestamp = tilNextMillis(lastTimestamp);
}
}
//Time stamp changes, sequence resets within milliseconds
else {
sequence = 0L;
}
//Time cut of the last ID generation
lastTimestamp = timestamp;
//Shift and put together by OR operation to form a 64-bit ID
return ((timestamp - twepoch) << timestampLeftShift) //
| (datacenterId << datacenterIdShift) //
| (workerId << workerIdShift) //
| sequence;
}
/**
* Block until the next millisecond until a new timestamp is obtained
* @param lastTimestamp Time cut of the last ID generation
* @return Current timestamp
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
*Returns the current time in milliseconds
* @return Current time (milliseconds)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
//=============Test====================
/** test */
public static void main(String[] args) {
SnowflakeId idWorker = new SnowflakeId(0, 0);
for (int i = 0; i < 100; i++) {
long id = idWorker.nextId();
System.out.println(Long.toBinaryString(id));
System.out.println(id);
}
}
}Test result:
11000000100011001111111100010111010110000000000000000000000
433585782117105664
11000000100011001111111100010111010110000000000000000000001
433585782117105665
11000000100011001111111100010111010110000000000000000000010
433585782117105666
11000000100011001111111100010111010110000000000000000000011
433585782117105667
11000000100011001111111100010111010110000000000000000000100
433585782117105668
11000000100011001111111100010111010110000000000000000000101
433585782117105669
11000000100011001111111100010111010110000000000000000000110
433585782117105670
11000000100011001111111100010111010110000000000000000000111
433585782117105671
11000000100011001111111100010111010110000000000000000001000
433585782117105672
11000000100011001111111100010111010110000000000000000001001
433585782117105673
11000000100011001111111100010111010110000000000000000001010
433585782117105674
11000000100011001111111100010111010110000000000000000001011
433585782117105675
11000000100011001111111100010111011000000000000000000000000
433585782121299968
11000000100011001111111100010111011000000000000000000000001
433585782121299969
11000000100011001111111100010111011000000000000000000000010
433585782121299970
11000000100011001111111100010111011000000000000000000000011
433585782121299971
11000000100011001111111100010111011000000000000000000000100
433585782121299972
11000000100011001111111100010111011000000000000000000000101
433585782121299973
11000000100011001111111100010111011000000000000000000000110
433585782121299974
11000000100011001111111100010111011000000000000000000000111
433585782121299975
11000000100011001111111100010111011000000000000000000001000
433585782121299976
11000000100011001111111100010111011000000000000000000001001
433585782121299977
11000000100011001111111100010111011000000000000000000001010
433585782121299978
11000000100011001111111100010111011000000000000000000001011
433585782121299979
11000000100011001111111100010111011000000000000000000001100
433585782121299980
11000000100011001111111100010111011000000000000000000001101
433585782121299981
11000000100011001111111100010111011000000000000000000001110
433585782121299982
11000000100011001111111100010111011000000000000000000001111
433585782121299983
11000000100011001111111100010111011000000000000000000010000
433585782121299984
11000000100011001111111100010111011000000000000000000010001
433585782121299985
11000000100011001111111100010111011000000000000000000010010
433585782121299986
11000000100011001111111100010111011000000000000000000010011
433585782121299987
11000000100011001111111100010111011000000000000000000010100
433585782121299988
11000000100011001111111100010111011010000000000000000000000
433585782125494272
11000000100011001111111100010111011010000000000000000000001
433585782125494273
11000000100011001111111100010111011010000000000000000000010
433585782125494274
11000000100011001111111100010111011010000000000000000000011
433585782125494275
11000000100011001111111100010111011010000000000000000000100
433585782125494276
11000000100011001111111100010111011010000000000000000000101
433585782125494277
11000000100011001111111100010111011100000000000000000000000
433585782129688576
11000000100011001111111100010111011100000000000000000000001
433585782129688577
11000000100011001111111100010111011100000000000000000000010
433585782129688578
11000000100011001111111100010111011100000000000000000000011
433585782129688579
11000000100011001111111100010111011100000000000000000000100
433585782129688580
11000000100011001111111100010111011100000000000000000000101
433585782129688581
11000000100011001111111100010111011100000000000000000000110
433585782129688582
11000000100011001111111100010111011100000000000000000000111
433585782129688583
11000000100011001111111100010111011100000000000000000001000
433585782129688584
11000000100011001111111100010111011100000000000000000001001
433585782129688585
11000000100011001111111100010111011100000000000000000001010
433585782129688586
11000000100011001111111100010111011100000000000000000001011
433585782129688587
11000000100011001111111100010111011100000000000000000001100
433585782129688588
11000000100011001111111100010111011100000000000000000001101
433585782129688589
11000000100011001111111100010111011100000000000000000001110
433585782129688590
11000000100011001111111100010111011100000000000000000001111
433585782129688591
11000000100011001111111100010111011100000000000000000010000
433585782129688592
11000000100011001111111100010111011100000000000000000010001
433585782129688593
11000000100011001111111100010111011100000000000000000010010
433585782129688594
11000000100011001111111100010111011100000000000000000010011
433585782129688595
11000000100011001111111100010111011100000000000000000010100
433585782129688596
11000000100011001111111100010111011100000000000000000010101
433585782129688597
11000000100011001111111100010111011100000000000000000010110
433585782129688598
11000000100011001111111100010111011100000000000000000010111
433585782129688599
11000000100011001111111100010111011100000000000000000011000
433585782129688600
11000000100011001111111100010111011100000000000000000011001
433585782129688601
11000000100011001111111100010111011100000000000000000011010
433585782129688602
11000000100011001111111100010111011100000000000000000011011
433585782129688603
11000000100011001111111100010111011100000000000000000011100
433585782129688604
11000000100011001111111100010111011100000000000000000011101
433585782129688605
11000000100011001111111100010111011100000000000000000011110
433585782129688606
11000000100011001111111100010111011100000000000000000011111
433585782129688607
11000000100011001111111100010111011100000000000000000100000
433585782129688608
11000000100011001111111100010111011100000000000000000100001
433585782129688609
11000000100011001111111100010111011100000000000000000100010
433585782129688610
11000000100011001111111100010111011100000000000000000100011
433585782129688611
11000000100011001111111100010111011100000000000000000100100
433585782129688612
11000000100011001111111100010111011100000000000000000100101
433585782129688613
11000000100011001111111100010111011100000000000000000100110
433585782129688614
11000000100011001111111100010111011110000000000000000000000
433585782133882880
11000000100011001111111100010111011110000000000000000000001
433585782133882881
11000000100011001111111100010111011110000000000000000000010
433585782133882882
11000000100011001111111100010111011110000000000000000000011
433585782133882883
11000000100011001111111100010111011110000000000000000000100
433585782133882884
11000000100011001111111100010111011110000000000000000000101
433585782133882885
11000000100011001111111100010111011110000000000000000000110
433585782133882886
11000000100011001111111100010111011110000000000000000000111
433585782133882887
11000000100011001111111100010111011110000000000000000001000
433585782133882888
11000000100011001111111100010111011110000000000000000001001
433585782133882889
11000000100011001111111100010111011110000000000000000001010
433585782133882890
11000000100011001111111100010111011110000000000000000001011
433585782133882891
11000000100011001111111100010111011110000000000000000001100
433585782133882892
11000000100011001111111100010111100000000000000000000000000
433585782138077184
11000000100011001111111100010111100000000000000000000000001
433585782138077185
11000000100011001111111100010111100000000000000000000000010
433585782138077186
11000000100011001111111100010111100000000000000000000000011
433585782138077187
11000000100011001111111100010111100000000000000000000000100
433585782138077188
11000000100011001111111100010111100000000000000000000000101
433585782138077189
11000000100011001111111100010111100000000000000000000000110
433585782138077190
11000000100011001111111100010111100000000000000000000000111
433585782138077191
11000000100011001111111100010111100000000000000000000001000
433585782138077192