Accident review: We duplicated the order ID!

[[428490]]

introduce

In many business systems, we often encounter the need to generate globally unique distributed IDs, such as IM systems, order systems, etc. So what are the methods for generating globally unique distributed IDs?

UUID

 // 3eece1c6-5b57-4bce-a306-6c49e44a1f90
 UUID.randomUUID().toString()

"Local generation, fast generation speed, but poor recognition and no order"

Can be used to identify pictures, etc., but cannot be used as a database primary key

Database auto-increment primary key

"When we first started working on the IM system, we created a separate table to obtain the auto-increment ID as the message ID." Creating a separate table to obtain the auto-increment ID will not affect the message sub-library and sub-table

Zookeeper

"Every time you want to generate a new ID, create a persistent sequential node, create the node number returned by the operation, which is the new ID, and then delete the node that is smaller than your own node."

This method can generate fewer IDs because there are fewer digits.

Redis

「This can be achieved using the incr command」

Set a key to userId with a value of 0. Each time you get userId, add 1 to it and get it again.

 set userId 0
 incr usrId //Return 1

Each time you get an ID, there will be a network interaction process with redis, so it can be improved to the following form

Directly obtain the maximum value of a userId, cache it locally and slowly accumulate it. When the maximum value of the userId is almost reached, obtain another segment. If a user service crashes, at most a small segment of the userId will not be used.

 set userId 0
 incr usrId //Return 1
 incrby userId 1000 //Return 10001

Snowflake Algorithm

"The snowflake algorithm is the most common solution, which satisfies global uniqueness and increasing trend, so it can be used as the database primary key."

The Snowflake algorithm is a distributed primary key generation algorithm published by Twitter. It can ensure the non-duplication of primary keys of different processes and the orderliness of primary keys of the same process.

In the same process, it is first guaranteed to be non-repetitive through the time bit, and if the time is the same, it is guaranteed through the sequence bit. At the same time, because the time bit is monotonically increasing, and if each server is roughly synchronized, the generated primary key can be considered to be generally ordered in a distributed environment, which ensures the efficiency of inserting index fields. For example, the primary key of MySQL's Innodb storage engine.

The primary key generated by the snowflake algorithm has four parts in binary representation, which are divided into 1-bit sign bit, 41-bit timestamp bit, 10-bit work process bit and 12-bit sequence number bit from high to low.

「Sign bit (1 bit)」

The reserved sign bit is always zero.

「Timestamp bit (41bit)」

The number of milliseconds that a 41-bit timestamp can hold is 2 to the 41th power. The number of milliseconds used in a year is: 365 * 24 * 60 * 60 * 1000. By calculation, we know that:

 Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);

The result is approximately equal to 69.73 years. The time epoch of ShardingSphere's snowflake algorithm starts at 0:00 on November 1, 2016, and can be used until 2086. I believe it can meet the requirements of most systems.

「Work process bit (10bit)」

This flag is unique within a Java process. If it is a distributed application deployment, the id of each working process should be different. The default value is 0 and can be set through properties.

"Generally, these 10 bits will be split into two 5-bit segments."

The first 5 bits represent the computer room ID, which can represent up to 2^5 computer rooms (32 computer rooms). The last 5 bits represent the machine ID, which can represent 2^5 machines (32 machines) in each computer room.

"Therefore, this service can be deployed on a maximum of 2^10 machines, or 1024 machines."

「Serial number bit (12 bits)」

This sequence is used to generate different IDs in the same millisecond. If the number generated in this millisecond exceeds 4096 (2 to the power of 12), the generator will wait until the next millisecond to continue generating.

Now that we understand the implementation idea, let's implement the algorithm again

 public class SnowFlake { 
 
 /**
 * Starting timestamp
 */
    private final static long START_STMP = 1480166465631L; 
 
 /**
 * The number of bits each part occupies
 */
 private final static long SEQUENCE_BIT = 12; //Number of digits occupied by the sequence number
 private final static long MACHINE_BIT = 5; //Number of bits used by the machine ID
 private final static long DATACENTER_BIT = 5; //The number of bits occupied by the data center 
 
 /**
 * The maximum value 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); 
 
 /**
 * The displacement of each part to the left
 */
    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 ID
 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();
 // Clock callback occurs
        if (currStmp < lastStmp) {
            throw new RuntimeException( "Clock moved backwards. Refusing to generate id" );
 } 
 
        if (currStmp == lastStmp) {
 //In the same millisecond, the serial number increases automatically
 sequence = ( sequence + 1) & MAX_SEQUENCE;
 //The number of sequences in the same millisecond has reached the maximum
            if ( sequence == 0L) {
                currStmp = getNextMill();
 }
 } else {
 //In different milliseconds, the sequence number is set to 0
 sequence = 0L;
 } 
 
 lastStmp = currStmp; 
 
 return (currStmp - START_STMP) << TIMESTMP_LEFT //Timestamp part
 | datacenterId << DATACENTER_LEFT //Data center part
 | machineId << MACHINE_LEFT //machine identification part
 | sequence ; //sequence number part
 } 
 
    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
 }
 return mill;
 } 
 
    private long getNewstmp() {
 return System.currentTimeMillis();
 } 
 
 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());
 } 
 
 }
 }

"This code divides the workerid into datacenterid and machineid. If we don't need to make a distinction in our business, we can just use the 10-digit workerid."

WorkerID generation

We can use Zookeeper's ordered nodes to ensure the global uniqueness of the id. For example, I create a permanent ordered node with the following command:

 # Create a root node
 create /test ''  
 # Create a permanent ordered node
 create -s /test/ip-port- ''  
 # Return Created /test/ip-port-0000000000

"The IP and port can be the IP and port of the application. You set the rules. Just don't repeat them."

The 0000000000 in /test/ip-port-0000000000 is our workerid

Let me tell you about a workerid duplication problem we encountered in our original production environment. The way to generate workid is very concise.

 // uid is an ordered persistent node in zookeeper
 List<String> pidListNode = zkClient.getChildren( "uid" );
 String workerId = String.valueOf(pidListNode. size ());
 zkClient.create ( "uid" , new byte[0], CreateMode.PERSISTENT_SEQUENTIAL);

"Can you see why this code causes duplicate workids?"

It uses the number of uid child nodes as the workid. When two applications execute the first line of code at the same time, the number of child nodes is the same, and the obtained workerId will be repeated.

What’s interesting is that this code ran fine for several years until the operation and maintenance team improved the application release efficiency a little bit, and then the online version started to report errors. This is because the application was initially released in serial, but later changed to parallel release.

"When using the snowflake algorithm, clock rollback may occur. It is recommended to use an open source framework, such as Meituan's Leaf."

The snowflake algorithm has been used in many middlewares, such as Seata, to generate a globally unique transaction ID.

This article is reprinted from the WeChat public account "Java Knowledge Hall", written by Li Limin. Please contact the Java Knowledge Hall public account to reprint this article.