《算法 - 雪花算法》

时间:2022-06-01 20:57:43

一:概述

  - SnowFlake 算法

    - 是 Twitter 开源的分布式 id 生成算法

 

  - 应用场景

    - 高性能的产生不重复ID,支持集群的横向扩展。

 

二:原理

  - 其核心思想就是:

    - 使用一个 64 bit 的 long 型的数字作为全局唯一 id。

    - 在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的。 

 

  - 产生公式

    -  | 0(最高位预留) | 时间戳(41位) | 机器ID(10位) | 随机序列(12位) |

    - 形成 64位bit

 

三:实现解析

  - 0(最高位预留) 

    - 因为二进制里第一个 bit 为如果是 1,那么都是负数,但是我们生成的 id 都是正数,所以第一个 bit 统一都是 0

 

  - 时间戳(41位) 

    - 41 bits 的 Timestamp,每次要生成一个新 ID 的时候,都会获取一下当前的 Timestamp,保证每个timestamp都是不同的

 

  - 机器ID(10位)

    - 10 bits 的机器号, 在 ID 分配 Worker 启动的时候,从一个 集群获取 (保证所有的 Worker 不会有重复的机器号)。

 

  - 随机序列(12位)

    - 12 bit 随机数。

 

  - 组成 64 位 bits,成为 10 进制的 16 位 unique Id

 

四:代码简单实现

  • <?php
    /**
     * 雪花算法
     *    其核心思想就是:
     *    使用一个 64 bit 的 long 型的数字作为全局唯一 id。
     *    在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的。
     * 产生公式
     *    | 0(最高位预留) | 时间戳(41位) | 机器ID(10位) | 随机序列(12位) |
     */
    class IdCreate
    {
        const max12bit = 4095;
    
        public static function createOnlyId()
        {
            // 获取微秒时间戳(42位),截取并转化为 41位二进制
            $microtime = decbin(floor(microtime(true) * 1000));
    
            // 10bit 的机器号,由集群产出
            $machineId = self::machine();
    
            // 12bit 的随机数
            $random = str_pad(decbin(mt_rand(0, self::max12bit)), 12, "0", STR_PAD_LEFT);
    
            // 拼接
            $base = '0' . $microtime . $machineId . $random;
    
            // 十进制 返回
            return bindec($base);
        }
    
        /**
         * 集群
         * @param int $machineId
         * @return string
         */
        public static function machine($machineId = 0)
        {
            return str_pad($machineId, 10, "0", STR_PAD_LEFT);
        }
    }
    
    $cast_id = IdCreate::createOnlyId();
    var_dump($cast_id);