Distributed ID scheme

1. UUID(Unique Universal Identifier) (not recommended)

1. Use (In a distributed system, all elements do not need to pass the central control terminal to determine the uniqueness of data.)

UUID.randomUUID().toString().replaceAll(“-“,””);

Composition: current date + time + clock sequence + machine id (Mac address or other).

Format: 32 characters

2, strengths,

Simple generation, local generation without network consumption, unique

3 and disadvantages

A, unordered string, does not have the autoincrement feature

B. No specific business meaning

C, long too long, 16 bytes, 128 bits. MySQL uses 36-bit strings to store and query the database performance. It is recommended that the primary key be as short as possible. As the primary key of the database, the disorderly character of the UUID will lead to frequent changes in data location, which seriously affects the database performance.

Note: Both schemes 2 and 3 use databases

All relational databases implement database self-increment ID; MySQL is implemented by AUTO_INCREMENT and Oracle is implemented by Sequence. In the database cluster environment, different database nodes can set different starting values and phase synchronization length to achieve the generation of global unique and increasing IDS under the cluster.

_ Format: digits _

2. Add the ID of the database

1, use,

CREATE DATABASE`SEQ_ID`; 

CREATE TABLE SEQID.SEQUENCE_ID ( id bigint(20) unsignedNOT NULL auto_increment, value char(10) NOT NULL default”, PRIMARY KEY (id), ) ENGINE=MyISAM; 

 insert into SEQUENCE_ID(value) VALUES (‘values’);

2, strengths,

Simple implementation, ID monotonously increasing, the speed of numerical type query

3 and disadvantages

A. MySQL itself is the bottleneck of the system when the concurrency is high and the traffic volume surges

B. The DB single point has the risk of outage and cannot withstand high concurrency scenarios

3. Database multi-master mode

1, use,

For multi-machine situations, you need to avoid duplicate ID generation solutions: set the starting value and increment step size configuration: MySQL_1 configuration: set @@autoINCREmentoffSet = 1; Set @@autoincrementIncrement = 2; MySQL_2 config: set @@autoincrementoffSet = 2; Set @@autoincrementIncrement = 2; 2, 4, 6, 8, 10Copy the code

2, strengths,

Solve DB single point problems

3 and disadvantages

A. It is not conducive to subsequent capacity expansion. It will be troublesome to add machines after the starting value and self-increasing step of other cluster machines are determined

B. The pressure of a single database itself is still high, and the pressure of the database itself is still high in the case of high concurrency

Iv. Segment mode

1, use,

One of the current mainstream implementation methods is to batch obtain self-increasing ids from the database. Each time, a number range is fetched from the database, such as (1,1000), representing 1000 ids. The specific service loads this number segment into the memory for use. CREATE TABLE idgenerator ( id int(10) NOTNULL, Maxid Bigint (20) NOT NULL COMMENT 'Current maximum ID ',step int(20) NOT NULL COMMENT' Current maximum id', bizType int(20) NOT NULL COMMENT 'Service type ', version int(20) NOT NULL COMMENT' Version number ', PRIMARY KEY (ID)) bizType: indicates different service types max_id: indicates the largest available IDstep: Represents the length of the number segment version: Update maxID = MAXID + step. If the update is successful, it indicates that the new number segment is successfully obtained. The new number range is (maxID,max_id +step]. update idgenerator set maxid = #{maxid+step}, Version = version + 1 where version = # {version} and biztype = XXX Use the version = # {version} and biztype = XXX method to solve most problemsCopy the code

2, strengths,

Do not rely on the database, do not frequently access the database, the database pressure is relatively small

3,

Five, the Redis

1, use,

127.0.0.1:6379> set seq_id 1 // Set seq_id to 1ok127.0.0.1:6379 > incr seq_id // add 1, And returns the incremented value (integer) 2Copy the code

Format: 12 bits free combination

2, strengths,

Using clusters, solve the performance problem of database ID generation

3 and disadvantages

Persistent problems. In RDB mode, the ID will be repeated after the system hangs up and restarts.

Snowflake algorithm

1, use,

Time stamp + work machine ID + serial number

TwitterSnowflake generates ids of type Long. One Long is 8 bytes, and each byte is 8 bits, which means that one Long is 64 bits. Snowflake ID is a 64-bit Long consisting of positive digits (1 bit), timestamp (41 bits), machine ID (5 bits), data center (5 bits), and auto-increment (12 bits). The first bit (1bit) : in Java, the highest bit of long is the sign bit, which represents positive and negative numbers. Positive numbers are 0 and negative numbers are 1. Timestamp part (41bit) : time in milliseconds. It is not recommended to save the current timestamp, but to use the difference (current timestamp - fixed start timestamp), which can make the generated ID from a smaller value; The 41-bit timestamp can be used for 69 years, (1L << 41)/(1000L * 60 * 60 * 24 * 365) = 69 years workmachine ID (10bit) : also known as workId, this can be flexibly configured, including machine room or machine number combination. Serial number part (12bit), self-value-added support the same node within the same millisecond can generate 4096 IDS according to the logic of this algorithm, just need to implement this algorithm in Java language, encapsulated as a tool method, then each business application can directly use the tool method to obtain distributed ID, Just ensure that each business application has its own work machine ID, rather than building a separate application to obtain a distributed ID. Java version of Snowflake algorithm implementation: /** * Twitter's SnowFlake algorithm uses the SnowFlake algorithm to generate an integer, And then converted into 62 base into a short URL address https://github.com/beyondfengyu/SnowFlake * * * / publicclass SnowFlakeShortUrl {/ * * * starting timestamp * / privatefinalstaticlong START_TIMESTAMP = 1480166465631L; Privatefinalstaticlong SEQUENCE_BIT = 12; Privatefinalstaticlong MACHINE_BIT = 5; Privatefinalstaticlong DATA_CENTER_BIT = 5; Privatefinalstaticlong MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); privateFinalStaticlong MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); privatefinalstaticlong MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); privatefinalstaticlong MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT); / privateFinalStaticlong MACHINE_LEFT = SEQUENCE_BIT; privatefinalstaticlong DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; privatefinalstaticlong TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; privatelong dataCenterId; // Data center privatelong machineId; Privatelong sequence = 0L; // privatelong lastTimeStamp = -1l; Private long getNextMill() {long mill = getNewTimeStamp(); while (mill <= lastTimeStamp) { mill = getNewTimeStamp(); } return mill; } private long getNewTimeStamp() { return System.currentTimeMillis(); } /** * generate the specified serial number based on the specified dataCenterId and machineId ** @param dataCenterId dataCenterId * @param machineId machineId */ public SnowFlakeShortUrl(long dataCenterId, long machineId) { if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) { thrownew IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0!" ); } if (machineId > MAX_MACHINE_NUM || machineId < 0) { thrownew IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0!" ); } this.dataCenterId = dataCenterId; this.machineId = machineId; Public synchronized long nextId() {long currTimeStamp = getNewTimeStamp(); if (currTimeStamp < lastTimeStamp) { thrownew RuntimeException("Clock moved backwards. Refusing to generate id"); } if (currTimeStamp == lastTimeStamp) {// In the same milliseconds, the sequence = (sequence + 1) &max_sequence; If (sequence == 0L) {currTimeStamp = getNextMill(); }} else {// In different milliseconds, set the sequence number to 0; } lastTimeStamp = currTimeStamp; Return (currTimeStamp - START_TIMESTAMP) < < TIMESTAMP_LEFT / / part timestamp | dataCenterId < < | DATA_CENTER_LEFT / / data center part MachineId < < MACHINE_LEFT / / machine identifier portion | sequence; } public static void main(String[] args) {SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3); for (int i = 0; i < (1 << 4); I++) {//10 base system.out.println (snowfla.nextid ()); }}}Copy the code

Format: 18 digits

Code implementation, follow-up supplement…