Generating Unique id Code Implementation for Distributed Deployment

In our work, we need to generate unique id in many scenarios, such as order number, coupon code, etc. This article will show you how to use java to generate unique id.

First, it is customary to post GitHub addresses, which can be downloaded directly from GitHub and run: https://github.com/whiteBX/IDGenerator

The Core of Unique ID

  1. Efficient. id generators are generally used as basic services, which need good performance assurance and can not make the business perceive obvious delay.
  2. Support distributed deployment. Nowadays, the mainstream is distributed environment, so the sender must support distributed deployment to avoid the bottleneck of single-machine disk IO and so on.
  3. Partially ordered. As an order number and other business, it is better to be orderly.
  4. It can be reversed. Order number is best to directly reverse the core information, so that when we investigate the problem, we can directly take the order number to reverse the information needed to use.

Key Design Points of Unique ID
In this example, we use a long type to store our id, that is, 64 bits, which can be converted to decimal or 32 bits according to the needs of our business. The following is an explanation of the composition of id:

Version number 2 bit + second time 30 bit + serial number 20 bit + machine ID 5 bit = 57 bit binary

Explain in detail:
Version Number 2: Represents the use of two bit s to store version numbers, which can be used when large business changes occur, so as to visually distinguish which version of the business is.
Second-level time 30 bits: using the current timestamp minus the fixed time of a system on-line to store, 30 bits can be used for more than 30 years. If it is not enough, it can be expanded.
Sequence number 20 bits: 2 ^ 20 - 1 can be generated per second, that is, millions of non-repetitive serial numbers, if not enough, can be expanded.
Machine ID 5 bits: can support 2 ^ 5 - 1 = 31 machine deployment, not enough to expand.
Since our storage is long, there are still seven bits left to expand freely, such as increasing the number of bits occupied by serial numbers or the number occupied by machine id s.

Specific realization
The core of this code is actually two points:

  1. Supporting multi-machine deployment - configuring each machine with a separate id through the machine id ensures that the id is not duplicated by deploying the same piece of code on multiple machines
  2. Sequence Number Generation - Non-repetition of Sequence Numbers can be achieved by locking or cas

The code is as follows:

The sequence number is not duplicated by locking:

public class LockSequenceGenerator extends SequenceGenerator {

    private ReentrantLock lock = new ReentrantLock();

    /**
     * By locking
     * @param generateInfo
     * @param generateProperties
     */
    public void generate(IdGenerateInfo generateInfo, GenerateProperties generateProperties) {
        lock.lock();
        try {
            long time = TimeGenerator.generateTime(generateProperties.getBeginEpoch());
            if (time == timestamp) {
                sequence++;
            }else {
                sequence = 0;
                timestamp = time;
            }
            generateInfo.setSequence(sequence);
            generateInfo.setTime(time);
        }finally {
            lock.unlock();
        }
    }
}

The serial number is not duplicated by cas:

public class CasGenerator extends SequenceGenerator {

    private AtomicReference<SequenceInfo> sequenceInfo = new AtomicReference<SequenceInfo>(new SequenceInfo());

    public void generate(IdGenerateInfo generateInfo, GenerateProperties generateProperties) {
        while (true) {
            long time = TimeGenerator.generateTime(generateProperties.getBeginEpoch());
            SequenceInfo oldSequenceInfo = sequenceInfo.get();
            SequenceInfo newSequenceInfo = new SequenceInfo();
            if (time == oldSequenceInfo.getTimestamp()) {
                newSequenceInfo.setTimestamp(time);
                newSequenceInfo.setSequence(oldSequenceInfo.getSequence() + 1);
            } else {
                newSequenceInfo.setTimestamp(time);
            }
            if (sequenceInfo.compareAndSet(oldSequenceInfo, newSequenceInfo)) {
                generateInfo.setTime(newSequenceInfo.getTimestamp());
                generateInfo.setSequence(newSequenceInfo.getSequence());
                break;
            }
        }
    }


    class SequenceInfo {
        private int sequence;
        private long timestamp;

        public int getSequence() {
            return sequence;
        }

        public void setSequence(int sequence) {
            this.sequence = sequence;
        }

        public long getTimestamp() {
            return timestamp;
        }

        public void setTimestamp(long timestamp) {
            this.timestamp = timestamp;
        }
    }
}

After solving the problem of no repetition of serial numbers, all that remains is to get the configuration version number and machine id to assemble our id.

// Read the configuration files through spring's Property Source to make them all configurable freely. Default values are assigned to all of them.
@Component
@PropertySource("classpath:generate.properties")
public class GenerateProperties {
    /**
     * Version number, default 2 bits, that is, binary 00, when major version changes configuration, need to be expanded to synchronize changes to version Length
     */
    private int version = 0;

    private int versionLength = 2;
    /**
     * Sequence number occupies bytes, default 20 bits, that is, 2 ^ 20 sequences per second, on-demand configuration
     */
    private Integer sequenceLength = 20;
    /**
     * Machine ID, which is 5 bits by default, i.e. binary 00000, can support 32 servers. If you need to expand, you need to change machineId Length synchronously.
     */
    private int machineId = 0;

    private int machineIdLength = 5;
    /**
     * start time
     */
    private Long beginEpoch = 1533686888L;
}

Assemble id according to configuration:

    /**
     * Generate ID 1 | 0 = 1, or all 1
     */
    public static long genearte(IdGenerateInfo info, GenerateProperties generateProperties) {
        long id = 0;
        id |= info.getMachineId();
        id |= info.getSequence() << generateProperties.getMachineIdLength();
        id |= info.getTime() << (generateProperties.getMachineIdLength() + generateProperties.getSequenceLength());
        id |= info.getVersion() << (generateProperties.getMachineIdLength() + generateProperties.getSequenceLength() + 30);
        return id;
    }

The reverse solution here does not write code examples, you can realize it by yourself, that is, according to the id binary code corresponding to the right shift of a specified number of digits can be solved in which machine, which time and other information.

performance testing
Running my machine has opened ten threads. The result of the measurement is that it takes about 10 seconds to generate 10 million IDs for each thread, and a single id is less than 1 millisecond. We can see that the efficiency is enough.

Of course, some of the examples are not perfect yet. Readers can improve themselves, such as prompting errors when the number of IDs generated in one second exceeds the maximum limit or waiting for the next point to be regenerated.

Tags: github Java Spring less

Posted on Tue, 03 Sep 2019 06:10:29 -0700 by kelas