An overview of the

Snowflake is Twitter’s open source distributed ID generation algorithm that results in a Long ID. It consists of 41 bits for the number of milliseconds, 10 bits for the machine ID (5 bits for the data center, 5 bits for the machine ID), 12 bits for the serial number in milliseconds (meaning that each node can generate 4096 ids per millisecond), and one symbol bit, always 0. We do not consider the local time fallback that causes the current timestamp to be smaller than the last timestamp. Such a problem should not occur and should not be solved by the program.

The characteristics of

  1. As ID, globally unique;
  2. Self-increment, dependent on timestamp generation, sequential increment of serial number;
  3. Supports a large number of service ids. A maximum of 2^10=1024 service nodes can be generated. A maximum of 2^12=4096 ids can be generated for a service node in one millisecond606024365)=69.73) about 70 years;
  4. The implementation is simple, does not rely on other third-party components, does not rely on external data sources, and does not even require any import.

chart

SnowflakeId is a 64-bit Long ID with the following structure:

  1. The first bit is always 0, indicating a positive number;
  2. Bits 2-42 indicate the timestamp, the timestamp of the current time minus the timestamp of the start time;
  3. Service node ID, different value for each node;
  4. Serial number in milliseconds.

Realize the principle of

Once you know the structure, it’s easy to implement.

41 bit – a timestamp

The timestamp of the current time minus the timestamp of the start time is shifted 22 bits to the left.

(ts - beginTs) << 22
Copy the code

10bit indicates the ID of the working machine

User-defined service node ID, fixed value, shifted 12 bits to the left.

workerId << 12
Copy the code

12 bit – serial number

The sequence number is incremented in milliseconds, and if overflow blocks to the next second counting from 0.

If (ts == lastTimestamp) {if (++sequence > maxSequence) {ts = tilNextMillis(lastTimestamp); sequence = 0L; }} else {// Timestamp changed, reset sequence = 0L; } lastTimestamp = ts;Copy the code
** @param lastTimestamp * @return */ private long tilNextMillis(long lastTimestamp) {long ts = System.currentTimeMillis(); while (ts <= lastTimestamp) { ts = System.currentTimeMillis(); } return ts; }Copy the code

Generate the final ID

return (ts - beginTs) << timestampLeftOffset | workerId << workerIdLeftOffset | sequence;
Copy the code

The complete code

Finally, post the complete code.

Public class SnowflakeIdWorker {/** * start time: 2020-01-01 00:00:00 */ private final Long beginTs = 1577808000000L; private final long workerIdBits = 10; /** * 2^10 - 1 = 1023 */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); private final long sequenceBits = 12; /** * 2^12 - 1 = 4095 */ private final long maxSequence = -1L ^ (-1L << sequenceBits); */ Private final Long timestampLeftOffset = workerIdBits + sequenceBits; */ Private final Long timestampLeftOffset = workerIdBits + sequenceBits; /** * Leftoffset = sequenceBits; /** * Leftoffset = */ private final Long workerIdLeftOffset = sequenceBits; Private long workerId; /** * private long workerId; /** * private long sequence = 0L; /** private long sequence = 0L; */ private long lastTimestamp = -1l; */ private long lastTimestamp = -1l; public SnowflakeIdWorker(long workerId) { if (workerId > maxWorkerId || workerId < 0) { throw new Format ("WorkerId must be greater than or equal to 0 and less than or equal to %d", maxWorkerId)); } this.workerId = workerId; } public synchronized long nextId() { long ts = System.currentTimeMillis(); If (ts < lastTimestamp) {throw new RuntimeException(string. format(" system clock back %d ms ", (lastTimestamp))); } // At the same time, If (ts == lastTimestamp) {// Sequence overflow if (++sequence > maxSequence) {ts = tilNextMillis(lastTimestamp); sequence = 0L; }} else {// Timestamp changed, reset sequence = 0L; } lastTimestamp = ts; // 0-00000000 00000000 00000000 00000000 00000000 00000000 00000000 0-00000000 00-00000000 0000 The bitwise or operation is equivalent to binary concatenation // there is also a 0<< 63,0 is bitwise or itself with any number, So write not write the same return (ts - beginTs) < < timestampLeftOffset | workerId < < workerIdLeftOffset | sequence; } /** * block until next millisecond ** @param lastTimestamp * @return */ private long tilNextMillis(long lastTimestamp) {long ts = System.currentTimeMillis(); while (ts <= lastTimestamp) { ts = System.currentTimeMillis(); } return ts; }}Copy the code

supplement

To be computationally efficient, there are a lot of bits involved, which I’ll briefly describe. Rule: 1 is true, 0 is no, Boolean operation between the same bits.

Bitwise with: &

If it’s true, it’s true.

1 &1 = 1 1 & 0 = 0 0 and 1 = 0 0 & 0 = 0Copy the code

Bitwise or: |

Where there is a truth there is a truth.

1 | | 0 = 1 = 1 1 1 0 | 1 | = 1 0 0 = 0Copy the code

Xor: ^

Same is no, different is true.

1 1 = 0 1 ^ ^ 0 = 1 0 0 ^ ^ 1 = 1 0 = 0Copy the code

Left: < <

How many bits to move to the left? Add 0 in the lower position and delete the more bits directly.

Moves to the right: > >

How many bits to move to the right, delete the extra bits in the lower order, add 0 to the higher order, add 1 to the lower order.

Source, complement, and inverse in Java

The original code

The source code is the raw binary representation of a decimal number. For integers, the highest bit is a sign bit, with 1 representing a negative number and 0 representing a positive number. Use the 32-bit int integers 2 and -2 as an example. The original code of 2 is 00000000 00000000 00000000 00000010. The original code of 2 is 10000000 00000000 00000000 00000010

Radix-minus-one complement

The inverse of a positive number is its original code, and the inverse of a negative number is reversed except for the sign bit of the highest digit (0 changes to 1,1 to 0). 2’s inverse code: 00000000 00000000 00000000 00000010-2’s inverse code: 1111111111 11111111 11111101

complement

The complement of a positive number is its original code, and the complement of a negative number is its inverse plus 1. 2’s complement: 00000000 00000000 00000000 00000010-2’s inverse: 1111111111 11111111 11111111 11111101-2’s complement: 11111111 11111111 11111111 11111110