In distributed environment, we may often encounter the need for a globally unique ID, the common scheme SnowFlake algorithm we should also be very familiar with, today to share a distributed ID generator design ideas, code for company reasons, will not be posted

Let’s look at the application scenarios of distributed ID generators

1. Primary key after database table and database

  • After a service database is divided into databases and tables due to a magnitude problem, a distributed primary key ID is required to generate primary keys to ensure that the primary key IDS of data are unique
  • In this scenario, it is recommended that the generated iD be based on the time increment, because clustered indexes are generally used as primary keys. The time increment primary key can avoid low database write performance caused by random I/OS

2. TraceId of the service invocation link tracing

  • In the current situation of popular micro-service architecture, many distributed tracing schemes are applied to trace and monitor the entire service invocation link, troubleshoot problems or check the response time of each node of the link. In many schemes, a unique ID will be generated as traceId to trace the entire service invocation chain
  • In this scenario, in addition to being unique, the generated iD is required to be efficient and high-throughput because every call is logged and tracked

Let’s talk about the background of our design

We design the background for distributed ID generators

  • 1. With the rapid development of business, we have more and more callers for a service, so horizontal expansion is needed to improve service throughput;
  • 2. In this service, the distributed ID generation logic is coupled in the service logic code. At present, the distributed ID generation scheme is based on snowflake algorithm.
  • 3. For the long type with 64-bit ID, the algorithm only uses 3 bit bits as machine code, so it can only be extended to 8 nodes, seriously restricting the horizontal expansion ability of our service;
  • 4. And each machine is in the configuration file is stored in the node, lead to each version online, all need according to the node to launch, modify the configuration files of the machine code, caused the services process trouble, especially the potential risk is very big, and there is no way to realize automatic expansion (because the new node, to modify the machine in the configuration file)

Based on this background, we established the goal of the design

  • 1. The distributed ID generator is isolated and decoupled from business services. It is used as a common tool to support the distributed ID generation requirements of multiple services
  • 2. Modify the algorithm for generating ids to limit node capacity expansion
  • 3. Machine code configuration is extracted from the local configuration file to a distributed configuration center to simplify the online process and reduce risks during online capacity expansion.

Distributed ID technology selection

Talk about the common technology selection for distributed ids

UUID

Standard format description:
  • The UUID is a 128-bit array of bits formatted as a 36-bit string
  • Use its 8-4-4-4-12 format to split 32 hexadecimal strings
  • So far, the industry has a total of 5 ways to generate UUID, here is not detailed, interested friends can check
advantages
  • Local algorithm generation, no extra network request overhead, good performance
  • It can be the only one in time and space, and the access cost is low
Disadvantages:
  • If you use a string of 36 lengths as the primary key of the database, it takes up physical space and a lot of storage space for index pages (clustered indexes, secondary indexes)
  • When the UUID is used as the primary key, the GENERATED ids are discrete, resulting in random I/OS and low database write performance
Usage scenarios
  • This parameter is applicable to non-database primary key scenarios, such as idempotent ids, link traceId, and log ids

Based on mysql, Redis and other storage of the self-increasing sequence

  • Oracle has sequences, but I’ve barely used Oracle, so I’ll take mysql as an example
Mysql implementation:
  • Mysql implementation, mainly use auto_increment primary key to implement, generate global unique ID
  • In a distributed system, a common database is used to create a table
  • The primary key of a table is an increment primary key
  • Each time a globally unique ID is required, an entry is inserted into the table and the primary key of the successfully inserted data is returned as the globally unique ID
Redis implementation
  • The redis implementation, which relies on redis single threads, uses the redis atomic command INCr to generate a globally unique ID
  • In distributed systems, a common redis is used and a common primary key is used to generate keys
  • Each time the incr command is used, a globally unique ID is generated
advantages
  • There is no comparison between mysql implementation and Redis implementation
  • Simple to implement, using the characteristics of storage can be achieved, access cost is small
  • Moreover, primary keys are guaranteed to be globally unique and strictly self-increasing
disadvantages
  • The disadvantages of using data storage systems are similar
  • The performance is severely restricted by the performance of the storage system. Take the storage performance of our company as an example. The healthy QPS of mysql and Redis are around 8,000 and 80,000 respectively
  • Poor scalability, it is difficult to achieve expansion through data sharding
Optimization scheme
  • Realize data slice, add multiple master nodes, by designing different numbers between each node increment; To ensure that no duplicate ids can be generated between masters
  • Each node can obtain multiple ids in batches to reduce interaction with the database and improve performance
  • However, multiple master nodes consume too much resources and few people use the solution (I have seen a toB project use it).

Implemented based on ZooKeeper

Realization Idea 1
  • The zNode data version is used to generate the serial number, and the 32-bit and 64-bit data versions are generated
  • The client uses this version number as its unique serial number
  • The version number of datSpanning will increase by 1 whenever node data changes, which can generate a globally unique 32-bit ID
  • Whenever data is modified, the corresponding MzxID (modify transaction ID) is also incremented, generating a globally unique 64-bit ID
Realization Idea 2
  • Creating a persistent node whose data is the value of the counter ensures that the counters across multiple nodes can generate globally unique ids
advantages
  • Low access cost
  • The ID ensures strict global uniqueness
  • The whole system can take advantage of zK’s high reliability
disadvantages
  • Zk performance is not as good as the redis implementation

sonwflake

  • In the process of migrating storage system from Mysql to Cassandra, Since Cassandra has no sequential ID generation mechanism, Twitter developed a set of globally unique ID generation algorithm called Snowflake algorithm by itself. According to The business requirements of Twitter, The Sonwflake system generates a 64-bit ID consisting of the following three parts:
  • 41 bit timestamp (accurate to millisecond, 41 bit length can last 69 years)
  • 10-bit machine code (10-bit length can support deployment of up to 1024 nodes)
  • 12-bit count sequence number (12-bit counter sequence number supports 4096 sequence numbers per millisecond per node)

advantages
  • Because it is implemented locally, there is no extra network overhead, so the performance is high
  • The timestamp is high, and the auto-increment sequence number is low, ensuring that it is unique while ensuring that it is strictly incremental based on time
  • Does not depend on the external storage system, there is no limitation of external dependence
disadvantages
  • Because the high level is a timestamp, the process of generating the timestamp depends on the clock system of the local service
  • If clock rollback occurs on the server, the timestamp obtained by the local clock-based system may cause duplicate ids

Finally, we adopted sonwflake algorithm and made some changes based on our business background to realize a distributed ID service for the business within the team. Here are the key changes

To solve the problem of machine code local configuration file storage, we introduced ZK to maintain machine code for each node of the entire distributed ID service

  • When each node is started, the machine ID is first obtained and zK is connected
  • Check whether the node is newly added
  • If it is a new node, a unique machine code is generated
  • And persist to ZK
  • The unique machine code is returned to the service node, which persists locally to the service
  • If it is a registered node (node restart)
  • The generated machine code is directly obtained and returned to the service node, which persists to the service local

In order to reduce the impact of clock callback, zK is used to implement a time checker

  • Check the clock periodically
  • The service node connects to ZK, synchronizes its current timestamp to ZK, and then obtains other nodes for comparison
  • If there is abnormal, directly alarm processing