There are many types of distributed ID generation algorithms, and Twitter’s SnowFlake is a classic one.

An overview of the

The result of the SnowFlake id is an integer of 64bit size. Its structure is shown below:

  • 1 aAnd don’t have to. The highest digit 1 in binary is negative, but the iD we generate is usually an integer, so the highest digit is always 0

  • 41 bits, used to record time stamps (milliseconds).

    • 41 digits can represent 2, 41 and 1 digits.
    • If used only to represent positive integers (positive numbers include 0 in computers), the range of values that can be represented is: 0 to 2 41 −1, minus 1 because the range of values that can be represented starts at 0, not 1.
    • That is, 41 bits can represent a value of 241 −1 milliseconds, which translates to (241 −1)/ (1000∗60∗60∗24∗365)=69 years

  • 10 bits, used to record the working machine ID.

    • Can be deployed in 2 10 =1024 nodes, includingFive datacenterIdandFive workerId
    • 5 bits (bit)The largest positive integer that can be expressed is 2. 5 −1 =31, which can be 0, 1, 2, 3, or…. 31 These 32 numbers represent different datecenterids or workerids

  • The 12-bit serial number is used to record different ids generated within the same millisecond.

    • 12 bits (bit)The largest positive integer that can be expressed is 2. 12 −1 =4096, which can be 0, 1, 2, 3, or…. 4095 The 4096 numbers represent 4096 ID numbers generated in the same machine at the same time (millisecond)

Since 64-bit integers in Java are of type long, the ids generated by the SnowFlake algorithm in Java are stored in longs.

SnowFlake guarantees:

  • All generated ids increase over time
  • No duplicate ids are generated across the distributed system (because datacenterId and workerId distinguish between them)

Talk is cheap, show you the code

The following is aTwitter official original”, written in Scala (I don’t know Scala either, so I can read it as Java) :

/** Copyright 2010-2012 Twitter, Inc.*/ package com.twitter.service.snowflake import com.twitter.ostrich.stats.Stats import com.twitter.service.snowflake.gen._ import java.util.Random import com.twitter.logging.Logger /** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */ class IdWorker( val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L) extends Snowflake.Iface { private[this] def genCounter(agent: String) = { Stats.incr("ids_generated") Stats.incr("ids_generated_%s".format(agent)) } private[this] val exceptionCounter = Stats.getCounter("exceptions") private[this] val log = Logger.get private[this] val rand = new Random  val twepoch = 1288834974657L private[this] val workerIdBits = 5L private[this] val datacenterIdBits = 5L private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits) private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) private[this] val sequenceBits = 12L private[this] val workerIdShift = sequenceBits private[this] val datacenterIdShift = sequenceBits + workerIdBits private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits private[this] val sequenceMask = -1L ^ (-1L << sequenceBits) private[this] var lastTimestamp = -1L // sanity check for workerId if (workerId > maxWorkerId || workerId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId)) } if (datacenterId > maxDatacenterId || datacenterId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId)) } log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId) def get_id(useragent: String): Long = { if (! validUseragent(useragent)) { exceptionCounter.incr(1) throw new InvalidUserAgentError } val id = nextId() genCounter(useragent) reporter.report(new AuditLogEntry(id, useragent, rand.nextLong)) id } def get_worker_id(): Long = workerId def get_datacenter_id(): Long = datacenterId def get_timestamp() = System.currentTimeMillis protected[snowflake] def nextId(): Long = synchronized { var timestamp = timeGen() if (timestamp < lastTimestamp) { exceptionCounter.incr(1) log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format( lastTimestamp - timestamp)) } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } lastTimestamp = timestamp ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence } protected def tilNextMillis(lastTimestamp: Long): Long = { var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp } protected def timeGen(): Long = System.currentTimeMillis() val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r def validUseragent(useragent: String): Boolean = useragent match { case AgentParser(_) => true case _ => false } }Copy the code

Scala is a language that can be compiled into bytecode, which is simply understood by adding a lot of syntactic sugar to Java syntax, such as not having to write semicolons after each statement, using dynamic typing, and so on. In the spirit of giving it a try, I “translated” the Scala code into the Java version, with the following changes:

/** Copyright 2010-2012 Twitter, Inc.*/ package com.twitter.service.snowflake import com.twitter.ostrich.stats.Stats import com.twitter.service.snowflake.gen._ import java.util.Random import com.twitter.logging.Logger /** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */ class IdWorker( // | val workerId: Long, // | val datacenterId: Long, / / | < -- this part into a Java constructor form private val reporter: reporter, / / log related to delete / / | var sequence: Long = 0) / / l | extends Snowflake. Iface {/ / interface can not find, delete / / | private [this] def genCounter (agent: String) = {/ / | Stats. Incr (" ids_generated ") / / | Stats. The incr (" ids_generated_ % s ". The format (agent)) / / | < -- error, log processing related, Delete} / / | private [this] val exceptionCounter = Stats. GetCounter (" exceptions ") / / | private [this] val log = Logger. Get / / | private[this] val rand = new Random // | val twepoch = 1288834974657L private[this] val workerIdBits = 5L private[this] val datacenterIdBits = 5L private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits) private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) private[this] val sequenceBits = 12L private[this] val workerIdShift =  sequenceBits private[this] val datacenterIdShift = sequenceBits + workerIdBits private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits private[this] val sequenceMask = -1L ^ (-1L << sequenceBits) private[this] var lastTimestamp = -1L //---------------------------------------------------------------------------------------------------------------------- ------// // sanity check for workerId // if (workerId > maxWorkerId || workerId < 0) { // exceptionCounter.incr(1) //<-- error handling related, Delete // throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0". Format (maxWorkerId)) // | - > change to: Format ("worker Id can't be greater than %d or less than } 0, "maxWorkerId)) / / / / / / to the if (datacenterId > maxDatacenterId | | datacenterId < 0) {/ / compose exceptionCounter incr (1) //<-- error handling related, Throw new IllegalArgumentException(" Datacenter Id can't be greater than %d or less than 0 ". The format (maxDatacenterId)) / / / / letter | - > change to: Throw new IllegalArgumentException // number // (string. format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId)) //中} // // log.info("worker starting. Timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", // timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, WorkerId) / / / / | - - > change: System. Out. Printf (" worker... %d..." ,timestampLeftShift,...) ; // //---------------------------------------------------------------------------------------------------------------------- -- -- -- -- -- - / / / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / / / this function to delete the error handling code, the remaining one line of code: // def get_id(userAgent: String): Long = {// if (! ValidUseragent (userAgent)) {// ExceptionCounter. incr(1) // throw new InvalidUserAgentError // Delete} // exception // valid = nextId() // genCounter(useragent) // // reporter.report(new AuditLogEntry(id, useragent, rand.nextLong)) // id // } // //-------------------------------------------------------------------// def get_worker_id(): Long = workerId // | def get_datacenter_id(): Long = datacenterId / / | < -- into a Java function def get_timestamp () = System. CurrentTimeMillis / / | protected snowflake def nextId(): Var timestamp = timeGen() if (timestamp < lastTimestamp) {exceptionCounter.incr(1) // Error ("clock is moving backwards. Replaced requests until % D.", lastTimestamp); / / change System. Err. Printf (...). throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format( lastTimestamp -timestamp)) // change RumTimeException} if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } lastTimestamp = timestamp ((timestamp - twepoch) < < timestampLeftShift) | | < / - plus the return keyword (datacenterId < < datacenterIdShift) | / / | (workerId << workerIdShift) | // | sequence // | } protected def tilNextMillis(lastTimestamp: Long): Var timestamp = timeGen() while (timestamp <= lastTimestamp) {timestamp = timeGen()} timestamp // Return} protected def timeGen(): Long = System. CurrentTimeMillis () / / into a Java function val AgentParser = "" "([a zA - Z] [a zA - Z \ 0-9] *) ""." r / / | / / | def validUseragent(useragent: String): Boolean = useragent match {/ / | < -- log related to delete case AgentParser (_) = > true / / / / | | case _ = > false} / / |}Copy the code

Modified Java version:

public class IdWorker{ private long workerId; private long datacenterId; private long sequence; public IdWorker(long workerId, long datacenterId, long sequence){ // sanity check for workerId 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; } private long twepoch = 1288834974657L; private long workerIdBits = 5L; private long datacenterIdBits = 5L; private long maxWorkerId = -1L ^ (-1L << workerIdBits); private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); private long sequenceBits = 12L; private long workerIdShift = sequenceBits; private long datacenterIdShift = sequenceBits + workerIdBits; private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private long sequenceMask = -1L ^ (-1L << sequenceBits); private long lastTimestamp = -1L; public long getWorkerId(){ return workerId; } public long getDatacenterId(){ return datacenterId; } public long getTimestamp(){ return System.currentTimeMillis(); } public synchronized long nextId() { 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)); } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0; } lastTimestamp = timestamp; return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift)  | sequence; } private long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } private long timeGen(){ return System.currentTimeMillis(); } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- test -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the public static void main (String [] args) {IdWorker worker = new IdWorker,1,1 (1); for (int i = 0; i < 30; i++) { System.out.println(worker.nextId()); }}}Copy the code

The code to understand

In the above code, there is partial bit operation code, such as:

sequence = (sequence + 1) & sequenceMask; private long maxWorkerId = -1L ^ (-1L << workerIdBits); return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift)  | sequence;Copy the code

To get a better understanding, I did some research.

The binary representation of negative numbers

In computers, the binary of negative numbers is represented by complement. Suppose I store numbers using the Java int type, which is 32 bits, or 4 bytes. (1 byte = 8 bit) Then the decimal number 3 in binary would look like this:

00000000 00000000 00000000 00000011 // 3 binary representation, is the source codeCopy the code

So what is the number minus three in binary? We can think in reverse, because -3+3=0, in binary operation, the binary of -3 is regarded as the unknown x to solve, and the binary expression of the solution is as follows:

00000000 00000000 00000000 00000011 //3, source code + XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX //3, Complement -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 00000000, 00000000, 00000000, 00000000Copy the code

What value does it take to reverse the value of x, the binary of 3 to make the result 00000000 00000000 00000000 00000000 00000000 00000000? :

00000000 00000000 00000000 00000011 //3, source code + 1111111111 11111111 11111111 11111101 //-3, Complement -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 1 00000000 00000000 00000000 00000000Copy the code

The idea is that the binary number of 3 is incremented by 1 bit by bit from the lowest digit, so that the overflow 1 continues toward the highest digit until the overflow reaches the 33rd digit. Then, since int can only hold a maximum of 32 bits, the highest 1 overflows, leaving the remaining 32 bits as a (decimal) 0.

The meaning of the complement is that you can take the complement and add it to the source code (the binary of three) and end up with an overflow zero.

The above is the process of understanding, and in practice it is easy to calculate if you remember the formula:

  • Complement = inverse + 1
  • Complement = (original code -1) and then take the inverse code

So the binary of -1 should look like this:

00000000 00000000 00000000 00000001 // Source code: 1 binary 11111111 11111111 11111111 11111110 // reverse code: 11111111 11111111 11111111 11111111 // add 1: the binary representation of -1 (complement)Copy the code

Use a bit operation to calculate the largest number of n bits

For example, a line like this:

    private long workerIdBits = 5L;
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);       Copy the code

Long maxWorkerId = -1l ^ (-1l << 5L)

At first glance, I couldn’t see which part should be evaluated first, so I checked the priority table of the Java operators:

So in the above line of code, the running order is:

  • Minus 1 moves 5 to the left, and you get a
  • 1 a vision or a

Long maxWorkerId = -1l ^ (-1l << 5L)

-1 moves 5 to the left, resulting in a:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000 // 11111111 11111111 11111111 11100000 // result ACopy the code

-1 XOR A:

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000 // Different is 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 00000000, 00000000, 00000000, 00011111 // Final result 31Copy the code

The final result is 31. Binary 00000000 00000000 0000000000011111 can be converted to decimal as follows:

Long maxWorkerId = -1l ^ (-1l << 5L) maxWorkerId = 31 Why do we move 5 to the left? If you’ve seen the overview, check this out:

The maximum number of 5-bit positive integers is 2. 5 −1 =31, which can be 0, 1, 2, 3, or…. 31 These 32 numbers represent different datecenterids or workerids

-1l ^ (-1L << 5L) results in 31, and 2 5 −1 also results in 31, so in code, -1L ^ (-1L << 5L) is written as a bitwise operation to figure out what the largest positive integer represented by 5 bits of energy is

Mask to prevent overflow

Here’s an interesting piece of code:

sequence = (sequence + 1) & sequenceMask;Copy the code

Test it out with different values and you’ll see how interesting it is:

long seqMask = -1L ^ (-1L << 12L); System.out.println("seqMask: "+seqMask); System.out.println(1L & seqMask); System.out.println(2L & seqMask); System.out.println(3L & seqMask); System.out.println(4L & seqMask); System.out.println(4095L & seqMask); System.out.println(4096L & seqMask); System.out.println(4097L & seqMask); System.out.println(4098L & seqMask); /** seqMask: 4095 1 2 3 4 4095 0 1 2 */Copy the code

This code passeswithThe operation ensures that the result range of the calculation is always 0-4095!

Summarize the results with bitwise operations

Here’s another weird code:

return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift)  | sequence;Copy the code

And to make sense of this code,

First of all,We need to calculate the relevant values:

private long twepoch = 1288834974657L; Private long workerIdBits = 5L; private long workerIdBits = 5L; //workerId Number of bits: 5 Private Long datacenterIdBits = 5L; Private Long maxWorkerId = -1L ^ (-1L << workerIdBits); private Long maxWorkerId = -1L ^ (-1L << workerIdBits); // workerId Maximum value that can be used: 31 private Long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // Maximum number of bytes that can be used: 31 Private Long sequenceBits = 12L; Private Long workerIdShift = sequenceBits; private Long workerIdShift = sequenceBits; // 12 private long datacenterIdShift = sequenceBits + workerIdBits; // 12+5 = 17 private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 12+5+5 = 22 private long sequenceMask = -1L ^ (-1L << sequenceBits); //4095 private long lastTimestamp = -1L;Copy the code

The secondWrite a test, write the parameters are dead, and run the print information, convenient later to check the calculation result:

/ / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- test -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the public static void main (String [] args) {long timestamp = 1505914988849 l; long twepoch = 1288834974657L; long datacenterId = 17L; long workerId = 25L; long sequence = 0L; System.out.printf("\ntimestamp: %d \n",timestamp); System.out.printf("twepoch: %d \n",twepoch); System.out.printf("datacenterId: %d \n",datacenterId); System.out.printf("workerId: %d \n",workerId); System.out.printf("sequence: %d \n",sequence); System.out.println(); System.out.printf("(timestamp - twepoch): %d \n",(timestamp - twepoch)); System.out.printf("((timestamp - twepoch) << 22L): %d \n",((timestamp - twepoch) << 22L)); System.out.printf("(datacenterId << 17L): %d \n" ,(datacenterId << 17L)); System.out.printf("(workerId << 12L): %d \n",(workerId << 12L)); System.out.printf("sequence: %d \n",sequence); long result = ((timestamp - twepoch) << 22L) | (datacenterId << 17L) | (workerId << 12L) | sequence; System.out.println(result); ** Timestamp: 1505914988849 twepoch: 1288834974657 datacenterId: 17 workerId: 25 sequence: 0 (timestamp - twepoch): 217080014192 ((timestamp - twepoch) << 22L): 910499571845562368 (datacenterId << 17L): 2228224 (workerId << 12L): 102400 sequence: 0 910499571847892992 */Copy the code

After plugging in the value of the displacement, it looks like this:

return ((timestamp - 1288834974657) << 22) |
        (datacenterId << 17) |
        (workerId << 12) |
        sequence;Copy the code

For values we don’t know yet, we can look at the SnowFlake structure explained in the overview and then plug in values in the legal range (Windows can easily compute binary values using a calculator) to see how the calculation works. Of course, since my test code already has these values written out, I can simply use these values to verify the results manually:

        long timestamp = 1505914988849L;
        long twepoch = 1288834974657L;
        long datacenterId = 17L;
        long workerId = 25L;
        long sequence = 0L;Copy the code
Set: Timestamp = 1505914988849, twePOch = 1288834974657 1505914988849-1288834974657 = 217080014192 (timestamp millisecond offset from start time), The calculation process of (a) binary shift 22 bits to the left is as follows: | < -- here around 22 ‭ | 00 00110010 10001010 11111010 00100101 01110000 00000000 00000000 000000 / / a = 217080014192, 00001100 00 10100010 10111110 10001001 01011100 | 000000 00000000 00000000 / / a left shift value after 22 (la) | < -- here behind a 0Copy the code
If datacenterId = 17, then (b) binary shift 17 bits to the left is calculated as follows: | < -- here left 17 ‭ 00000000 00000000 00000000 00000000 00000000 00000000 | 0000000/00010001 / b = 17 0000000 ‭ 0 00000000 00000000 00000000 00000000 0010001 00000000 00000000 | 0 / / b shift to the left after 17 values (lb) | < -- here behind a 0Copy the code
If workerId = 25, (c) binary shift 12 bits to the left is calculated as follows: | < -- here began to shift to the left 12 ‭ 00000000 0000 0000 00000000 00000000 00000000 00000000 00000000 00011001 | ‬ / / c = 25, 00000000, 00000000 00000000 00000000 00000000 00000001 1001 0000 00000000 | ‬ / / c value after left 12 (lc) | < -- here behind a 0Copy the code
Set: sequence = 0, its binary is as follows: 00000000 00000000 00000000 00000000 00000000 00000000 0000 0000 00000000 ‬ ‭ / / sequence = 0Copy the code

Now that we know the left-shifted values of each part (la,lb,lc), the code can be simplified to read as follows:

return ((timestamp - 1288834974657) << 22) | (datacenterId << 17) | (workerId << 12) | sequence; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | | simplified \ | / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the return (la) | (lb) | | (lc) sequence.Copy the code

The pipe symbol | in Java is an operator. As long as either the NTH bit of x or the NTH bit of y is 1, the NTH bit of the result is also 1; otherwise, it is 0. Therefore, we calculate the bits or of the four numbers as follows:

1 12 0 | | | | | 5 5 41 0001100 10100010 10111110 10001001 01011100 0000 | | 00000 | 0, 00000000/0000 / la 0 | 000000 ‭ 0 00000000  00000000 00000000 00000000 00|10001|0 0000|0000 00000000 //lb 0|0000000 00000000 00000000 00000000 00000000 00|00000|1 1001 | 0000/00000000 / lc or 00 0 | 0000000 00000000 00000000 00000000 00000000 0000 | | 00000 | 0 ‭ ‬ 00000000/0000 / sequence -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | 0, 0001100, 10100010, 10111110 10001001 01011100 1001 | | 10001 | 1 00 ‭ ‬ 00000000/0000 / results: 910499571847892992Copy the code

Results: 1) List the subscripts of 1 from left (counting from 0) :

0000 1 1 00 0 1 000 1 0 0 1 1 1 1 1 0 1 000 1 00 1 0 0 1 1 1 1 1 1 1 00 1 000 0000 ‭ 55, 0000, 0000, 0000, 58 59 53 49 47 45 44 43 42 41 39 35 32 30 28 27 26 21 17 16 15 12Copy the code

2) Each subscript is calculated as a power of 2 and added:

2 59 +2 58 +2 55 +2 53 +2 49 +2 47 +2 45 +2 44 +2 43 +2 42 +2 41 +2 39 +2 35 +2 32 +2 30 +2 28 +2 26 +2 21 +2 17 Plus 2, 16, plus 2, 15, plus 2, 2

2^53} : 9007199254740992 2^53} : 9007199254740992 2^49} : 56 ^47} : 140737488355328 2^45} : 35184372088832 2^44} : 17592186044416 2^43} : 8796093022208 2^42} : 439804659104 2^39} : 54975595552 2^39} : 54975595588 2^35} : 34359738368 2^32} : 4294967296 2^30} : 1073741824 2^28} : 268435456 2^27} : 134217728 2^26} : 67108864 2^21} : 2097152 2^17} : 131072 2^16} : 65536 2^15} : 32768 + 2 ^ 12} : 4096 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 910499571847892992Copy the code

Calculation screenshot:

As the test program printed results, manual verification completed!

To observe the

1 | 41 | 5 | 5 | 12 0|0001100 10100010 10111110 10001001 01011100 00| | | //la 0| |10001| | //lb 0| | |1 1001| //lc or 0 | | | | ‭ ‬ 00000000/0000 / sequence -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - | 0, 0001100, 10100010, 10111110 10001001 01011100 1001 | | 10001 | 1 00 ‭ ‬ 00000000/0000 / results: 910499571847892992Copy the code

The 64 bits above are cut off by bits 1, 41, 5, 5 and 12 for easy observation.

  • Longitudinal observations revealed that:

    • In bit 41, all lines (lb, LC, sequence) are 0 except la.
    • In the first 5 bits from the left, all the lines are 0 except for the lb line
    • In the second 5 bits from the left, all lines are 0 except lc
    • If the sequence is any value other than 0, then the 12-bit sequence will have a value, and all the other rows will be 0

  • Cross-sectional observations found that:

    • In row LA, we moved 5+5+12 bits to the left, so we added zeros to 5, 5, and 12, so row LA must be all zeros except for 41
    • In the same way, lb, LC, sequnece lines are similar
    • Because of the left shift operation, four different values are moved to the corresponding positions in SnowFlake theory, then four lines are doneorThe operation (the result is 1 whenever there is 1) merges the four bits into a single binary number.

Conclusion: So, in this code

return ((timestamp - 1288834974657) << 22) |
        (datacenterId << 17) |
        (workerId << 12) |
        sequence;Copy the code

The left shift operation is to move the value to the corresponding segment (41, 5, 5 and 12 are already on the right, so they don’t need to move to the left).

Then bitwise or operation is performed on each left-shifted value (la, lb, LC, sequence) in order to combine the shorter data into a binary number.

Finally, it converts to base 10, which is the resulting ID

extension

After you understand the algorithm, there are actually a few things you can do to extend it:

  1. Modify the information stored in each bit segment according to your business. The algorithm is universal and you can adjust the size of each segment and the stored information according to your own needs.
  2. Decrypt the ID, since each segment of the ID holds specific information, so given an ID, it should be possible to try to reverse the original information for each segment. The information from the reverse derivation can help us with the analysis. For example, as an order, you can know the generation date of the order, the data center responsible for processing, and so on.