Snowflake snowflake algorithm

Summary

SnowFlake is an algorithm designed by Twitter to generate unique IDs in distributed systems. It can satisfy tens of thousands of requests for message ID allocation per second by Twitter. These message IDs are unique and have approximately incremental order.

 

principle

The ID generated by the SnowFlake algorithm is a 64-bit integer, structured as follows (each part is separated by a "-" symbol):

 

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

 

In the 1-bit identification part, in java, because the highest bit of long is the symbol bit, the positive number is 0, and the negative number is 1, the ID generated generally is positive, so it is 0.

In the 41-bit timestamp section, the current timestamp is not stored in milliseconds, but the difference of the timestamp (current time-fixed start time) so that the generated ID can start from a smaller value. The 41-bit timestamp can be used for 69 years, (1L < 41)/ (1000L * 60 * 24 * 365) = 69. Year;

In the 10-bit node part, the first five bits are used as data center identifier and the last five bits are used as machine identifier in Twitter implementation. 1024 nodes can be deployed.

In the 12-bit serial number section, 4096 ID s can be generated by the same node in the same millisecond.

 

The ID generated by SnowFlake algorithm is generally incremental in time. When used in distributed systems, it is necessary to pay attention to the unique identity of data center and machine, so that the ID generated by each node can be guaranteed to be unique. Maybe we don't need to use 5 bits as the data center identification and 5 bits as the machine identification as above. We can flexibly allocate the node parts according to the needs of our business. For example, if we don't need the data center, we can use all 10 bits as the machine identification; if there are not many data centers, we can use only 3 bits. As a data center, 7 bits are used as machine identification.

/**
* twitter Implementation of snowflake algorithm based on java
*
*/
public class SnowFlake {
  
    /**
    * Starting timestamp
    */
    private final static long START_STMP = 1480166465631L;
  
    /**
    * Number of digits occupied by each part
    */
    private final static long SEQUENCE_BIT = 12; //Number of digits occupied by serial number
    private final static long MACHINE_BIT = 5;  //Number of digits occupied by machine identification
    private final static long DATACENTER_BIT = 5;//Number of digits occupied by data center
  
    /**
    * Maximum of each part
    */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
  
    /**
    * Left displacement of each part
    */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
  
    private long datacenterId;  //Data Center
    private long machineId;    //Machine identification
    private long sequence = 0L; //serial number
    private long lastStmp = -1L;//Last timestamp
  
    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }
  
    /**
    * Generate the next ID
    *
    * @return
    */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }
  
        if (currStmp == lastStmp) {
            //In the same millisecond, the serial number increases by itself.
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //The number of sequences in the same millisecond has reached its maximum
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //In different milliseconds, the serial number is set to 0.
            sequence = 0L;
        }
  
        lastStmp = currStmp;
  
        return (currStmp - START_STMP) << TIMESTMP_LEFT //Timestamp section
                | datacenterId << DATACENTER_LEFT      //Data Center Section
                | machineId << MACHINE_LEFT            //Machine identification section
                | sequence;                            //Sequence Number Part
    }
  
    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }
  
    private long getNewstmp() {
        return System.currentTimeMillis();
    }
  
}
//Test code
public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);
        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }
  
    }

You can see that the generated ID s are incremental and unique.

Tags: Java less

Posted on Wed, 14 Aug 2019 00:01:07 -0700 by Joshua4550