This is my 22nd day of the August Genwen Challenge

The generation of globally unique ids in distributed systems is an old but very important topic. As the technology continues to mature, the distributed global unique ID design and generation scheme tends to trend increasing ID. This article will combine the ID in our system with the consideration of actual business scenarios, performance storage and readability, as well as the pros and cons of the choice, to make an in-depth analysis. The purpose of this article is not to analyze the best ID generator, but to analyze what needs to be considered when designing AN ID generator and how to design the best ID generator for your business.

Project address: github.com/JoJoTec/id-…

First, let’s put out our globally unique ID structure:

The unique ID generator is a plug-in that is placed in each microserver process. This is not an architecture that has a unique ID generation center:

  • It starts with a string formatted with a timestamp, showing the year, month, day, hour, minute, second, and millisecond. Since they are scattered in different processes, it is necessary to consider whether different microservice timestamps will cause the same ID problem.
  • Intermediate business field, a maximum of 4 characters.
  • And finally, the increment sequence. This autoincrement sequence was obtained by Redis, and decentralized pressure optimization and cluster Fallback optimization were performed at the same time, which will be analyzed in detail later.

The sequence number starts with a formatted string of time stamps. As the sequence number is distributed among different processes, the current time of different processes may vary. The difference may be in the level of milliseconds or seconds. So, consider whether the rest of the ID will produce the same sequence.

The increment sequence consists of two parts, the first part is Bucket, followed by the corresponding Bucket increment sequence obtained from Redis. The pseudo-code to obtain the increment sequence is:

1. Obtain the position of the current thread ThreadLocal. The initial value of position is a random number. 2. Position += 1, then mod the maximum Bucket size (2^ 8-1) to obtain the current Bucket. If the current Bucket is not disconnected, go to the next step. Otherwise, repeat 2. Redis: incr sequence_num_key: indicates the current Bucket value and obtains the returned value sequence 4. Sequence_num_lock: sequence_num_key: sequence_num_key: sequence_num_key: sequence_num_key: sequence_num_key: sequence_num_key: sequence_num_key: Then repeat step 3. Otherwise, return the sequence -- if a RedIS-related exception occurs at 3 and 4, add the current Bucket to the breaker and repeat Step 2Copy the code

Under this algorithm, even though each instance timestamp may be different, as long as the same business does not generate more entities than the Sequence limit within the maximum difference time, duplicate ids can be guaranteed.

At the same time, we designed buckets so that in the case of a Redis cluster, even if Redis is not available for some nodes, we would not be affected to generate ids.

At present, OLTP services cannot be separated from traditional databases. The most popular database is MySQL, and InnoDB is the most popular OLTP storage engine in MySQL. Considering service expansion and distributed database design, InnoDB’s primary key ID is generally generated through the global ID generator rather than the auto-increment ID. What performance impact does this ID have on MySQL InnoDB? We compare our primary key of type BigInt with our primary key of type string.

First, due to the indexing nature of B+ trees, the more strictly the primary key increases, the better the insert performance. The more chaotic, the worse the insertion performance. This is mainly because in B+ tree design, if the value is highly disorderly, data is stored discreetly, resulting in frequent page splitting operations of InnoDB, which seriously reduces the insertion performance. It can be seen from the comparison of the following two figures:

Insert order:

Insert disorder:

If the inserted primary key ID is discrete and unordered, then every insert may make fission modification to the previous B+ tree child nodes. Then, in any one period of time, every child branch of the entire B+ tree may be read and modified, resulting in poor memory efficiency. If the primary key is ordered (that is, the newly inserted ID is larger than the previous ID), only the children and nodes of the latest branch will be read and modified, which improves the overall insert efficiency.

The ID we designed, since it starts with the current timestamp, is trending upward across the board. Basically, the insertion of B+ tree nodes to be modified can be controlled in the latest B+ tree branch to prevent the whole tree scanning and modification.

Compare that to the long numbers generated by SnowFlake, which are called bigint in the database: Bigint, which takes up 8 bytes in either format in the InnoDB engine row record store. Our ID, of type char, is latin1 (because there are only letters and numbers) and takes 27 bytes, about three times more than Bigint.

  • If the primary key is larger than the primary key, the space occupied by a single row is larger. In other words, branches of the B+ tree and leaf nodes take up more space. There will be less data to read and manipulate on a page. If the table field has only one primary key, then MySQL can load the number of rows processed on a single page (regardless of various headers such as page headers, row headers, table headers, etc.). Bigint is more than 3 times the number of rows processed by our primary key. However, data tables generally do not have only primary key fields, but also many other fields, and the more space other fields take up, the less this impact.
  • MySQL secondary index, leaf node value is primary key, so the same, single page load of leaf nodes, bigint type is more than 3 times our primary key. In fact, the main performance bottleneck of secondary index search is not here. This three-fold effect may be less than millisecond optimization improvement for most queries. This is trivial compared to the readability and convenience of the primary key that we designed.

In business, there are many scenarios that need to be sorted by creation time. For example, if you want to query a user’s order for today, and you want to query the order in reverse order, then the SQL would be:

Select count(1) from t_order where user_id = "userid" and create_time > date(now()); Select * from t_order where user_id = "userid" and create_time > date(now()) order by create_time limit 0, 10;Copy the code

The order table will definitely have the user_id index, but as the business grows and the order volume increases, the two SQL will become slower and slower, so we have two options:

  1. Create a combined index of user_id and create_time to reduce scans, but adding additional indexes to a large table can take up more space and overlap with existing indexes can sometimes lead to errors in SQL optimization.
  2. Filter directly using our primary key index:
select count(1) from t_order where user_id = "userid" and id > "210821";
select * from t_order where user_id = "userid" and id > "210821" order by id desc limit 0, 10;
Copy the code

Select * from user_id; select * from create_time; select * from user_id; select * from create_time; select * from user_id; That is, most users’ orders on the day are dozens and hundreds of this level, so there is basically no problem, this step will not consume a lot. Otherwise, create a combined index of user_id and create_time to reduce scans.

If there’s no sorting involved, just filtering, this is basically fine.

We don’t want the user to know the size of our business by ID. For example, IF I get an ID on the next order now, and then I get an ID on the next order after a certain period of time, I can compare the two ids to figure out how many orders there are in that period of time.

The ID we designed does not have this problem at all, because the final serial number:

  1. All services share the same set of serial numbers. When an ID is generated for each service, the sequence in the Bucket increases.
  2. The sequence number can be used by different threads at the same time in different buckets, and the result is a bit operation, so it’s hard to tell which part is the sequence number and which part is the Bucket.

From the ID we designed, we can intuitively see when the business entity was created:

  • General customer service to accept the problem, get the ID will be able to see the time, directly to the background system corresponding time to retrieve the user’s relevant operation records. Simplify operations.
  • The general business has alarm system, and the general alarm information will contain ID. From the ID we designed, we can see the creation time and which business it belongs to.
  • Generally, the logs are collected together. All the logs of the microservice system are collected into the system such as ELK. The information searched from the search engine can be seen directly from the ID of the business and creation time.

In the unit test of the given project source address, we tested the performance of initiating a single thread of local REDis through embedded- Redis, 200 threads to obtain ID, and compared the performance of only operating Redis, only obtaining sequence and obtaining ID, my broken computer results are as follows:

Single thread BaseLine(only Redis): 200000 in: 28018ms Sequence generate: 200000 in: 28459ms ID generate: 200000 in: 28459ms: 29055ms 200 Thread BaseLine(only redis): 200000 in: 3450ms Sequence generate: 200000 in: 3562ms ID generate: 200000 in: 3562ms ID generate: 200000 in: 3610msCopy the code