Architecture design - ID generator "suggestions collection"

Hello everyone , I meet you again , I'm your friend, Quan Jun .

One 、 Distributed ID The transmitter

The requirements are very clear ： Different machines generate different at the same time ip; The same machine generates different at different times IP;

So according to the demand , The optional variables are ： machine （ network card 、IP）+ Time , random number

Two 、Why not UUID？

UUID The implementation of the ： The core idea of the algorithm is to combine the network card of the machine 、 Local time 、 A random number to generate UUID.

advantage ： Guarantee uniqueness ; Local call , Unwanted rpc

UUID The defects of ：

1.UUID longer , Take up memory space ; It's often represented as a string , It is inefficient to build index as primary key , The common optimization scheme is “ Into two uint64 Integer storage ” perhaps “ Half storage ”（ Half can't guarantee uniqueness ）

2. There is no order , Increasing trend cannot be guaranteed

3、 ... and 、 rely on DB Is self augmentation feasible ？

Realization ： Self increasing + Set the step size ;8 Service nodes 8 An example （ Similar mold taking ）;

defects ：

1. It is not conducive to the expansion of service nodes ; The service node is fixed , Fixed step size , It is difficult to expand horizontal service nodes .

2. rely on DB, Put extra pressure on the database

Four . Globally unique ID How the generator Design ？ What are the considerations

1. Globally unique ; Orderliness （ Not necessarily continuous , But the trend is increasing ）; Reversible information ;

2. Business performance requirements ： High performance 、 High availability

3. Access mode ： The embedded 、 Central service release 、rest Release pattern

Design one ：ID data structure

64 position

1. machine ID 10 position ;2 Of 10 The power can support at most 1k+ Taiwan machine ; If every machine TPS by 1W/s,10 Servers can have 10W/s Of TPS, Basically meet most business requirements .

2. Serial number 10 Bit or 20 position ; Empathy , Calculation 2 Of 20 Power , An average of one million can be generated per second ID

3. Time stamp 30 or 40 position （ Corresponding to the second level 、 millisecond ）- Time ensures that the trend increases

Others can be based on business characteristics , Plus different customized production methods （pom、rest） Or version information

Design 2 Concurrent

To support a large number of concurrent network requests ,ID Generating services generally adopts multithreading support , For competition Time and sequence （time sequence） use juc in ReentrantLock or synchronized or atomic Variables support （ recommend ）.

Realization

1. Definition id Physical structure （ machine + Time + seeds （ Generate random number ））

// Time stamp 
private Long time;
// Serial number 
private Integer sequence;
// Seeds that generate random numbers 
private Integer seed;
// machine ip
private Integer clusterIp;

Copy

2. Get the corresponding request data according to the structure , Assemble entity data （ Get the timestamp （ Milliseconds or seconds ）os Get local ip、mac Data such as ）, Generate a non repeating id

//synch Ensure thread safety 
public synchronized long getId()

Copy

Calculation （ Move left to assemble ,）【 Time stamp - Initial time 】 Shift the cluster by two bits to the left ip-sequence

3. analysis ip, Get the corresponding machine ip、 Time stamp and other information , Then move the right finger to locate

5、 ... and 、Twitter Of snowflake Algorithm

Twitter utilize zookeeper To achieve a global ID Generated Services Snowflake：https://github.com/twitter-archive/snowflake

• 1 Bit sign bit ：

because long Type in the java Signed in , The highest bit is the sign bit , A positive number is 0, A negative number is 1, And used in the actual system ID Usually positive numbers , So the highest is 0.

• 41 A time stamp （ millisecond ）：

It's important to note that 41 Bit timestamps are not timestamps that store the current time , It's the difference between the stored timestamps （ Current timestamp – Start timestamp ）, The starting timestamp here is generally ID The timestamp that the generator started using , Specified by the program , therefore 41 Bit millisecond timestamps can be used up to (1 << 41) / (1000x60x60x24x365) = 69 year .

• 10 Bit data machine bit ：

Include 5 Bit data identifies bits and 5 Bit machine identification bit , this 10 Bits determine the maximum number of... That can be deployed in a distributed system 1 << 10 = 1024 s Nodes . More than that , Generated ID There may be conflict .

• 12 Sequence in bit milliseconds ：

this 12 Bit count supports per node per millisecond （ The same machine , At the same time ） Most generated 1 << 12 = 4096 individual ID

It just adds up to 64 position , For one Long type .

• advantage ： High performance , Low latency , In order of time , Generally, it will not cause ID Collision
• shortcoming ： Need independent development and deployment , Depends on the machine clock

Realization ：

public class IdWorker {
    /**
     *  Start timestamp  2017-04-01
     */
    private final long epoch = 1491004800000L;
    /**
     *  machine ID Number of digits occupied 
     */
    private final long workerIdBits = 5L;
    /**
     *  Data identification ID Number of digits occupied 
     */
    private final long dataCenterIdBits = 5L;
    /**
     *  The largest machine supported ID, The result is 31
     */
    private final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     *  Maximum data identification supported ID, The result is 31
     */
    private final long maxDataCenterId = ~(-1 << dataCenterIdBits);
    /**
     *  Within milliseconds, the sequence is id The number of digits in 
     */
    private final long sequenceBits = 12L;
    /**
     *  machine ID Moving to the left 12 position 
     */
    private final long workerIdShift = sequenceBits;
    /**
     *  Data identification ID Moving to the left 17(12+5) position 
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     *  The timestamp moves to the left 22(12+5+5) position 
     */
    private final long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     *  Mask to generate sequence , Here for 4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = ~(-1L << sequenceBits);
    /**
     *  Data identification ID（0～31）
     */
    private long dataCenterId;
    /**
     *  machine ID（0～31）
     */
    private long workerId;
    /**
     *  Sequence in milliseconds （0～4095）
     */
    private long sequence;
    /**
     *  Last generation ID The timestamp 
     */
    private long lastTimestamp = -1L;

    public IdWorker(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    /**
     *  Get the next ID ( This method is thread safe )
     * @return snowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        // If the current time is less than the last time ID Generated timestamp , It indicates that the system clock has gone back , It's time to throw an exception 
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        // If it's generated at the same time , Then sequence in milliseconds 
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            // Sequence overflow in milliseconds 
            if (sequence == 0) {
                // Blocking to the next millisecond , Get a new timestamp 
                timestamp = nextMillis(lastTimestamp);
            }
        } else {// Time stamp changes , Sequence reset in milliseconds 
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        // Shift and put together by bitwise OR operation 64 Bit ID
        return ((timestamp - epoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     *  Returns the current time in milliseconds 
     * @return  current time ( millisecond )
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     *  Blocking to the next millisecond , Until you get a new timestamp 
     * @param lastTimestamp  Last generation ID At the end of time 
     * @return  Current timestamp 
     */
    protected long nextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = lastTimestamp;
        }
        return timestamp;
    } 
}

Copy

Realize the attention points ：

1. Due to the existence of time correction ,snowflake The way for the algorithm to deal with clock callback is to throw an exception directly .

2. The second is 12 The problem of bit serial number overflow , namely 1ms Generated by internal request ID The number exceeds 2 Of 12 Power =4096 individual id.snowflake The algorithm does this , Wait until the next ms generating ID.

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/148260.html Link to the original text ：https://javaforall.cn