Analysis of distributed ID generation scheme

This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

In the case of high concurrency, the self-added ID of the database may be repeated, causing the new ID to fail. The solution is to use distributed ids

The distributed ID can be generated in the following ways

• UUID
• The database length increases asynchronously
• Snowflakes algorithm
• redis
• By Didi (TinyID)
• Baidu (Uidgenerator)
• Meituan (Leaf)

UUID

Generate a unique ID, the simplest of which is the UUID, which is unique, but the result is too long and stored in the database, which will cause the index to be too large and consume too much.

The ID of the database is incremented asynchronously

If you set the start value and the increment step, you can ensure that the unique ID is increment orderly and will not be repeated. The disadvantage is that it is not conducive to capacity expansion and increases maintenance costs.

• Mysql > select * from ‘mysql’;

set @@auto_increment_offset = 1;     Starting values -
set @@auto_increment_increment = 2;  - step
Copy the code

• Mysql 2

set @@auto_increment_offset = 2;     Starting values -
set @@auto_increment_increment = 2;  - step
Copy the code

Snowflake algorithm

Snowflake is the ID generation algorithm used by Twitter for internal distributed projects. Theoretically, a single machine can generate up to 4.1 billion ids per second

• advantages
  • ID trend increasing
  • High generation efficiency, 400W+ per second per machine
  • Support for linear scaling
  • High stability, independent of DB services
• disadvantages

  • It depends on the server time. If the server time is dialed back, duplicate ids may be generated

  • It is incremented on a single machine, but because of the distributed environment, the clocks on each machine may not be fully synchronized, and sometimes it may not be globally incremented

Redis generated ID

Redis can be used as a centralized ID generator, as well as the last assigned ID recorded in the table of the database. The ID generator currently in use combines these two and implements the following:

• Redis accumulator

public int getId(a) {
    // get the redis accumulator to get the id
    int id = 1;
    // Check whether the key exists
    if (stringRedisLettuceTemplate.hasKey("message:id")) {
        // If there is a key, add it directly
        id = Integer.valueOf(stringRedisLettuceTemplate.boundValueOps("message:id").get());
        stringRedisLettuceTemplate.opsForValue().increment("message:id".1);
    } else {
        // If not, query the last item in the database and get +1
        id = userDao.getLastId() + 1;
		// Save to redis after +1
        stringRedisLettuceTemplate.opsForValue().set("message:id", String.valueOf(id + 1));
    }
    return id;
}
Copy the code

• The database

<select id="getLastId" resultType="java.lang.Integer">
    SELECT IFNULL(id, 0) AS id
    FROM user
    ORDER BY id desc 
	limit 1
</select>
Copy the code

reference

• Distributed unique ID generator
• Distributed ID generator