Shulou(Shulou.com)05/31 Report--

This article mainly explains "how PHP uses the snowflake algorithm to generate a unique ID". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how PHP uses the snowflake algorithm to generate a unique ID".

1. Analysis of the principle of snowflake algorithm 1. Common generation strategies of distributed ID

The common strategies for distributed ID generation are as follows:

The database is self-increasing ID.

UUID generation.

The atomic self-increasing mode of Redis.

Split the database horizontally, setting the initial value and the same self-increasing step.

Self-adding ID for batch applications.

Snowflake algorithm.

Baidu UidGenerator algorithm (based on Snowflake algorithm to achieve custom timestamp).

Meituan Leaf algorithm (dependent on database, ZK).

This paper mainly introduces SnowFlake algorithm, which is an open source distributed id generation algorithm for Twitter.

The core idea is to use a 64 bit long number as the global unique id. It is widely used in distributed systems, and ID introduces timestamps to keep self-increasing and non-repetitive.

two。 The structure of Snowflake algorithm

It is mainly divided into the following parts:

It's a bit:0, and this is meaningless.

It's 41 bit: indicates a timestamp.

It's 10 bit: it means the id,0000000000 in the computer room, because what I passed in is 0.

It is the serial number of 12 bit: the serial number of the id generated simultaneously on a machine in a computer room in one millisecond, 0000 0000 0000.

Let's explain the four parts:

1 bit

Is meaningless:

Because the first bit in the binary is 1, then it is all negative, but the id we generate is all positive, so the first bit is all 0.

41 bit

Represents a timestamp in milliseconds.

41 bit can represent as many as 2 ^ 41-1, that is, it can identify 2 ^ 41-1 milliseconds, and the conversion to adulthood means 69 years.

10 bit

Recording the work machine id represents that this service can be deployed on a maximum of 2 machines, that is, 1024 machines.

But 5 bit in 10 bit represent computer room id,5 and bit represent machine id. It means a maximum of 2 ^ 5 computer rooms (32 computer rooms), each of which can represent 2 ^ 5 machines (32 machines), which can be split at will, such as 4 digits identifying business numbers and the other 6 digits as machine numbers. Can be combined at will.

12 bit

This is used to record different id generated in the same millisecond.

The largest positive integer 12 bit can represent is 2 ^ 12-1 = 4096, which means that the number represented by 12 bit can be used to distinguish 4096 different id in the same millisecond. That is, the maximum number of ID generated by the same machine in the same millisecond is 4096.

To put it simply, if a service assumes that you want to generate a globally unique id, you can send a request to the system that deploys the SnowFlake algorithm, which will generate the unique id. First of all, the SnowFlake algorithm system must know the machine number where it is located. (here, all 10bit is used as the working machine ID). Then after receiving this request, the SnowFlake algorithm system will first generate the first bit in a 64-bit long id,64 bit by binary operation. It then takes up 41 bit with the current timestamp (in milliseconds), and then sets the machine id with 10 bit. Finally, it is judged that within this millisecond on the machine in the current computer room, this is the number of requests. Add a sequence number to the request for generating id as the last 12 bit.

2. PHP source code implementation case 1.demo1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.