preface

In today’s Internet applications, the amount of data is increasing, resulting in a table may occupy a large physical storage space, in order to solve the problem, the use of database sharding technology. Split a database into multiple identical tables, connected through database middleware. If the table in the database uses the ID increment policy, duplicate ids may be generated. In this case, the distributed ID generation policy should be used to generate ids.

The basic principle of

The basic requirements of distributed ID are as follows:

  • Globally unique this is best understood, as a unique identifier, must not be repeated, this is the most basic requirement.

  • Because our distributed ID is used to identify data uniqueness, most of the time it is defined as a primary key or a unique index. In most cases, we use MySQL database, storage engine is InnoDB, innoDB default index structure is B tree, for BTree index, if data is written in the order of increment, the structure of B +tree will not be constantly disrupted and reshaped, access efficiency is the highest. In the primary key selection we should try to use ordered primary keys to ensure write performance.

  • Monotonically increasing guarantees that the next ID will be greater than the previous ID. For example, there are special requirements such as transaction version number, IM incremental message, and sorting.

  • Information security

As the data is incremental, malicious users can guess the next one according to the current ID, which is very dangerous. Therefore, our distributed ID is as hard as possible to be cracked. If the ID is continuous, malicious user pickpocket work is very easy to do, directly in order to download the specified URL; If it is the order number, it is even more dangerous, the competitor can directly know our daily order. Therefore, in some application scenarios, irregular and irregular ids are required.

  • Including a timestamp makes it easy to quickly know when this ID was generated during development.

Availability requirements

A distributed ID generation strategy requires not only a few basic principles, but also a strong requirement for availability.

  • High availability sends a request to generate an ID, and the server is guaranteed to create a usable distributed ID 99.9999% of the time. For example, in a business scenario, the insert operation cannot be completely unavailable because the ID cannot be generated.

  • Low latency

Sending a request to generate an ID returns the ID quickly, not in seconds.

  • High QPS

For example, if you have an event where 100,000 people are ordering at the same time, the server is under pressure to create 100,000 ids at the same time.

With these hard and fast requirements for distributed ids in mind, here are some strategies for generating distributed ids.

UUID

The UUID consists of the following parts:

  • The current date and time, the first part of the UUID depends on the time, if you generate a UUID after a few seconds, the first part is different, the rest is the same.
  • Clock sequence.
  • Globally unique IEEE machine id. If a nic exists, it is obtained from the MAC address of the NIC. If no NIC exists, it is obtained by other means.

A string consisting of 36 characters from 8-4-4-12, for example, 3DB1064B-2356-4a95-9429-3CC477879bd3.

  • Advantages:

    • Local generation, no network consumption.

  • Disadvantages:

    • First, the distributed ID is generally used as the primary key, but the mysql installation official recommended as short as possible primary key, UUID each is very long, so not recommended.
    • Since the distributed ID is the primary key, and the primary key contains the index, the mysql index is implemented through the B + tree. Every time a new UUID data is inserted, the underlying B + tree of the index is modified to optimize the query because the UUID data is unordered. So every insert of UUID data makes a big change to the B + tree of the primary key city, which is bad.
    • Information insecurity: The algorithm that generates UUids based on MAC addresses can cause MAC addresses to leak, a vulnerability that was used to find the creator of Melissa’s virus.

Database increment

When a service uses a single-table database, you can use the multi-master schema to generate globally unique increment ids using auto_INCREMENT of the database.

Set the starting values and compensation for both servers for id generation.

  • Advantages:
    • Simple, without any program additional operations
    • Maintain incremental booking
  • Disadvantages:
    • Performance is poor with high concurrency, and the upper limit of performance generated by primary keys is the maximum for a single database server
    • Horizontal expansion is difficult, heavily dependent on the database, expansion requires downtime

redis

Redis is single-threaded, so the operation is atomic. Atomization by incr/incrby generates a unique increment ID.

For example, there are five Redis in a cluster. You can initialize each Redis with a value of 1,2,3,4,5 and a step of 5.

The generated ids are: A:1,6,11,16,21 B:2,7,12,17,22 C:3,8,13,18,23 D:4,9,14,19,24 E:5,10,15,20,25

  • Advantages:
    • The performance is good, and the generated ID increases automatically
  • Disadvantages:
    • Depending on Redis, horizontal capacity expansion is difficult and configuration is complex
    • Persistence needs to be considered

Twitter’s Snowflake algorithm

Snowflake is Twitter’s open source distributed ID generation algorithm that results in a long ID.

Below is the basic composition of Snowflake.

  • The highest bit is the sign bit, which is always 0 and is not available.
  • A 41-bit time series, accurate to the millisecond level, lasts 69 years. Another important function of the time bit is that it can be sorted by time.
  • A 10-bit machine ID supports a maximum of 1024 nodes.
  • The 12-bit serial number is a series of self-increasing ids that can generate multiple ID numbers for a node in a millisecond. The 12-bit serial number supports 4096 ID numbers for each node in a millisecond.

Specific source code address: github.com/beyondfengy…

Concrete implementation can use the IdUtil tool class in the HuTool toolkit to generate.

// Parameter 1 is the terminal ID
// Parameter 2 is the ID of the data center
Snowflake snowflake = IdUtil.createSnowflake(1.1);
long id = snowflake.nextId();
Copy the code
  • Advantages:
    • The number of milliseconds is high, the increment sequence is low, and the whole ID is trending upward.
    • It does not rely on third-party systems such as databases, and is deployed as a service, providing higher stability and high performance in id generation.
    • You can allocate bits according to your service characteristics, which is very flexible
  • Disadvantages:
    • It depends on the machine clock. If the machine clock is rolled back, duplicate ids will be generated
    • It is incremented on a single machine, but because it is designed for a distributed environment, the clocks on each machine cannot be fully synchronized, and sometimes it is not globally incremented

Meituan Leaf – segment

Meituan’s Leaf segment scheme is actually an improvement on the self-increasing DATABASE ID scheme introduced above. It can generate globally unique and globally ordered ids, which can be used in transaction version number, incremental messages in IM chat, global sorting and other services.

Meituan’s leaf-segment makes the following changes to the database auto-increment ID scheme:

  • The original scheme has to read and write the database every time to obtain the ID, causing the database pressure. Use proxy server to obtain the value of one segment at a time. After use, go to the database to obtain a new number segment, can greatly reduce the pressure of the database;
  • The biz_tag field is used to distinguish the number issuing requirements of each service. The biz-tag IDS are isolated from each other and do not affect each other. If you need to expand the database to meet performance requirements, you do not need to perform the complex capacity expansion operations described above. You only need to divide the biz_TAG database into different tables.

Database table design is as follows:

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT ' ' COMMENT 'Used to differentiate business',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT 'Represents the maximum number of ID segments currently allocated to this biz_tag',
  `step` int(11) NOT NULL COMMENT 'Represents the length of the number segment allocated each time',
  `description` varchar(256)  DEFAULT NULL COMMENT 'description',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'Modification time'.PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
Copy the code

Instead of writing to the database every time you get an ID, you just need to set step to a large enough size, such as 1000. The database will be read and written again only after 1000 numbers have been consumed.

The frequency of reading and writing to the database decreases from 1 to 1/step, as shown below:

  • Advantages:
    • Leaf services can easily scale linearly, and the performance is fully capable of supporting most business scenarios
    • The ID number is a 64-bit number of 8 bytes in ascending order, which meets the primary key requirements of the database
    • High DISASTER recovery: The Leaf service has an internal number segment cache. Even if the DB is down, the Leaf can still provide external services in a short period of time
    • You can customize the size of max_ID to facilitate service migration from the original ID
  • Disadvantages:
    • The ID number is not random enough to reveal the number of numbers, which is not secure
    • TP999 data fluctuates greatly. When the number segment is used up, it will still hang on the I/O update database, while TG999 data will have occasional spikes
    • When the DB is down, the entire system becomes unavailable
    • The leaf-segment scheme can generate ids with increasing trend and the ID number is computable, but it is not applicable to the scenario of order ID generation. For example, competitors place orders at 12 o ‘clock on two days, and the order quantity of the company can be roughly calculated by subtracting the order ID number, which is intolerable

Meituan Leaf – a snowflake

Technically, the Leaf-Snowflake solution is a Twittersnowflake improvement that uses exactly the Same snowflake bit design (shown above) as the “1+41+10+12” assembly of ids.

The assignment of workerID can be manually configured when the number of service clusters is small. Leaf service scale, manual configuration cost is too high. So use the Zookeeper persistent sequential node feature to automatically configure wokerID for the Snowflake node.

Leaf-snowflake starts with the following steps:

  • Start the leaf-Snowflake service, connect to Zookeeper, and check whether you are registered under the parent node of Leaf_forever (whether there are children nodes in this order).
  • If you have registered your workerID (int ID generated by zK sequence node), start the service.
  • If not, create a persistent sequence node under the parent node, retrieve the sequence number as its own workerID, and start the service.

  • Weak dependence ZooKeeper

    • In addition to going to ZK for data each time, a workerID file is cached on the native file system. When ZooKeeper is faulty and the ZooKeeper needs to be restarted, the ZooKeeper service can be started properly. This allows for weak dependencies on tripartite components. Increased SLA to a certain extent

  • Solve the clock problem

    • Because this scheme is time-dependent, if the machine’s clock is rolled back, it is possible to generate duplicate ids that need to be addressed for clock rollback.

Detailed startup process:

See the whole startup flow chart above. When the service is started, it first checks whether it has written the ZooKeeper leaf_forever node:

  • If yes, the system time will be compared with the time recorded by leaf_forever/self node. If the time recorded by LeAfforever /{self} node is less than the time recorded by leaf_forever/self node for comparison, if the time recorded by leafforever/{self} node is less than the time recorded by leaf_forever/self node for comparison, If the time is less than LeAfforever /{self}, it is considered that the machine time has a long callback, the service fails to start and alarm;
  • Leaf_forever /${self} and write its own system time. Then comprehensively compare the system time of other Leaf nodes to determine whether its own system time is accurate. The specific method is to obtain the service IP address: Port of all temporary nodes (all leaf-Snowflake nodes in operation) under Leaf_TEMPORARY, then obtain the system time of all nodes through RPC request, and calculate sum(time)/nodeSize.
  • If abs(system time -sum(time)/nodeSize) is less than the threshold, the system time is correct and services are started normally. At the same time, write the temporary node leaf_TEMPORARY /${self} to maintain the lease.
  • Otherwise, it will be considered that the system time of the local machine has a long deviation, and startup failure will be reported.
  • At intervals (3s), the system time is reported to write leaf_forever/${self}.

Due to strong clock dependence, THE system is sensitive to time requirements, and NTP synchronization may cause a second-level rollback. You are advised to directly disable NTP synchronization. Otherwise, you can directly return to ERROR_CODE without providing the service during clock rollback and wait for the clock to catch up. Or do a layer of retry, and then report to the alarm system, or detect a clock back after the automatic removal of its node and alarm. As follows:

 // A callback occurred and the time is less than the last time
 if (timestamp < lastTimestamp) {
  			  
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                	// if the time deviation is less than 5ms, wait twice as long
                    wait(offset << 1);//wait
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                       // If the value is still smaller than the value, throw an exception and report itthrowClockBackwardsEx(timestamp); }}catch (InterruptedException e) {  
                   throwe; }}else {
                //throwthrowClockBackwardsEx(timestamp); }}ID / / distribution
Copy the code

summary

Snowflake, Meituan’s Leaf and Baidu’s UID-Generator, which is not mentioned in the article, are all commonly used solutions now. Most of them are optimized based on Snowflake. However, the specific solution needs to be selected according to the specific business, concurrency and so on. It is not reasonable to use Leaf or UID-generator without thinking. The project I am currently working on is also a generation strategy similar to Snowflake encapsulated by the company itself. Since the concurrency and data volume of the project are not as large as those of the Internet project, it is best to choose a plan suitable for my own project.

Finished!

I have seen it, click a like point a concern and then go ~

Reference:

Tech.meituan.com/2017/04/21/…