Distributed Primary Key
Motivation
In the development of traditional database software, the automatic sequence generation technology is a basic requirement. All kinds of databases have provided corresponding support for this requirement, such as MySQL auto-increment key, Oracle auto-increment sequence and so on. It is a tricky problem that there is only one sequence generated by different data nodes after sharding. Auto-increment keys in different physical tables in the same logic table can not perceive each other and thereby generate repeated sequences. It is possible to avoid clashes by restricting the initiative value and increasing the step of auto-increment key. But introducing extra operation rules can make the solution lack integrity and scalability.
Currently, there are many third-party solutions that can solve this problem perfectly, (such as UUID and others) relying on some particular algorithms to generate unrepeated keys or introducing sequence generation services. We have provided several built-in key generators, such as UUID, SNOWFLAKE. Besides, we have also extracted a key generator interface to make users implement self-defined key generator.
Built-In Key Generator
UUID
Use UUID.randomUUID() to generate the distributed key.
SNOWFLAKE
ShardingSphere provides flexible distributed sequence generation strategies. Users can configure the strategy of each table in sharding rule configuration module, with default snowflake algorithm generating 64bit long integral data.
As the distributed sequence generation algorithm published by Twitter, snowflake algorithm can ensure sequences of different processes do not repeat and those of the same process are ordered.
In the same process, it makes sure that IDs do not repeat through time, or through order if the time is identical. In the same time,with monotonously increasing time, if servers are generally synchronized, generated sequences are generally assumed to be ordered in a distributed environment. This can guarantee the effectiveness in index field insertion, like the sequence of MySQL Innodb storage engine.
In the sequence generated with snowflake algorithm, binary form has 4 parts, 1 bit sign, 41bit timestamp, 10bit work ID and 12bit sequence number from high to low.
- sign bit (1bit)
Reserved sign bit, constantly to be zero.
- timestamp bit (41bit)
41bit timestamp can contain 2 to the power of 41 milliseconds. One year can use 365 * 24 * 60 * 60 * 1000 milliseconds. We can see from the calculation:
Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);
The result is approximately equal to 69.73 years. ShardingSphere snowflake algorithm starts from November 1st, 2016, and can be used until 2086, which we believe can satisfy the requirement of most systems.
- work ID bit (10bit)
The sign is the only one in Java process. If applied in distributed deployment, each work ID should be different. The default value is 0 and can be set through properties.
- sequence number bit (12bit)
The sequence number is used to generate different IDs in a millisecond. If the number generated in that millisecond exceeds 4,096 (2 to the power of 12), the generator will wait till the next millisecond to continue.
Clock-Back
The clock-back of server can generate repeated sequence, so the default distributed sequence generator has provided a maximum clock-back millisecond. If the clock-back time has exceeded it, the program will report error. If it is within the tolerance range, the generator will wait till after the last generation time and then continue to work. The default maximum clock-back millisecond is 0 and can be set through properties.
Please refer to the following picture for the detailed structure of snowflake algorithm sequence.
LEAF
Before 5.0.0，We have referred Leaf, including Leaf-segment and Leaf-snowflake. Leaf-segment is implemented in the 4.0.0-RC2-release version and Leaf-snowflake is implemented in the 4.0.0-RC3-release version.
Since 5.0.0, the above implements have removed from ShardingSphere, and now we integrated a third party Leaf opensource implements and move into OpenSharding repository. For more details, please see project OpenSharding/sharding-keygen-leaf.