Home  >  Article  >  Backend Development  >  Detailed explanation of SnowFlake algorithm for generating unique ID in PHP

Detailed explanation of SnowFlake algorithm for generating unique ID in PHP

墨辰丷
墨辰丷Original
2018-05-29 15:01:401673browse

What is the snowflake algorithm? First, let me ask a question, how to generate a unique ID in a distributed system and keep the ID roughly increasing by itself? This is the most important business scenario in Twitter, so Twitter launched a snowflake algorithm.

Foreword: I recently needed to build a CMS system. Since the functions are relatively single and the requirements are flexible, I gave up a mature system like WP and built a relatively simple one myself. The article details page URL wants to be made into a pseudo-static URL format, that is, xxx.html. xxx has considered using an auto-incremented primary key directly, but I feel that this would expose the number of articles. Some students said that the initial value can be set higher, but it is still possible. The number of articles within a period of time is calculated based on the ID difference, so an algorithm that can generate unique IDs is needed.

The methods considered are

  1. Use the timestamp directly, or a series of methods derived from it

  2. Mysql comes with uuid

Both of the above two methods can be found, so I won’t explain too much

In the end, I chose Twitter’s SnowFlake algorithm

The advantage of this algorithm is very simple. It can generate about 4 million different 16-digit IDs (decimal) per second.

The principle is very simple.

ID consists of 64bit Composition

The first bit is vacant

41bit is used to store millisecond timestamp

10bit is used to store machine id

12bit is used to store self Add ID

Except for the highest bit marked as unavailable, the remaining three groups of bit positions can be floated, depending on specific business requirements. By default, the 41-bit timestamp can support the use of this algorithm until 2082, the 10-bit working machine ID can support 1023 machines, and the serial number supports 1 millisecond to generate 4095 auto-incrementing sequence IDs.
The following is the PHP source code

<?php
namespace App\Services;

abstract class Particle {
  const EPOCH = 1479533469598;
  const max12bit = 4095;
  const max41bit = 1099511627775;

  static $machineId = null;

  public static function machineId($mId = 0) {
    self::$machineId = $mId;
  }

  public static function generateParticle() {
    /*
    * Time - 42 bits
    */
    $time = floor(microtime(true) * 1000);

    /*
    * Substract custom epoch from current time
    */
    $time -= self::EPOCH;

    /*
    * Create a base and add time to it
    */
    $base = decbin(self::max41bit + $time);


    /*
    * Configured machine id - 10 bits - up to 1024 machines
    */
    if(!self::$machineId) {
      $machineid = self::$machineId;
    } else {
      $machineid = str_pad(decbin(self::$machineId), 10, "0", STR_PAD_LEFT);
    }
    
    /*
    * sequence number - 12 bits - up to 4096 random numbers per machine
    */
    $random = str_pad(decbin(mt_rand(0, self::max12bit)), 12, "0", STR_PAD_LEFT);

    /*
    * Pack
    */
    $base = $base.$machineid.$random;

    /*
    * Return unique time id no
    */
    return bindec($base);
  }

  public static function timeFromParticle($particle) {
    /*
    * Return time
    */
    return bindec(substr(decbin($particle),0,41)) - self::max41bit + self::EPOCH;
  }
}

?>

The calling method is as follows

Particle::generateParticle($machineId);//生成ID
Particle::timeFromParticle($particle);//反向计算时间戳

Here I am Improvements have been made. If the machine ID is passed as 0, these 10 bits will be removed because sometimes we may not use so many IDs

The above is the entire content of this article, I hope it will be helpful to everyone's learning. help.


Related recommendations:

php unique numberid method summary, php generates into idsummary

##[php]mysql globalID Scheme, phpmysql globalid

php Detailed explanation of how to become the only id

The above is the detailed content of Detailed explanation of SnowFlake algorithm for generating unique ID in PHP. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn