php雪花演算法SnowFlake生成唯一ID

點選進入“PHP開源社群”    

免費獲取進階面試、文件、影片資源

這個演算法的好處很簡單可以在每秒產生約400W個不同的16位數字ID(10進位制)

一、雪花演算法原理解析

1. 分散式ID常見生成策略：

分散式ID生成策略常見的有如下幾種：

• 資料庫自增ID。

• UUID生成。

• Redis的原子自增方式。

• 資料庫水平拆分，設定初始值和相同的自增步長。

• 批量申請自增ID。

• 雪花演算法。

• 百度UidGenerator演算法(基於雪花演算法實現自定義時間戳)。

• 美團Leaf演算法(依賴於資料庫，ZK)。

本文主要介紹SnowFlake 演算法，是 Twitter 開源的分散式 id 生成演算法。

其核心思想就是：使用一個 64 bit 的 long 型的數字作為全域性唯一 id。在分散式系統中的應用十分廣泛，且ID 引入了時間戳，保持自增性且不重複。

2. 雪花演算法的結構：

主要分為以下幾個部分：

• 是 1 個 bit：0，這個是無意義的。

• 是 41 個 bit：表示的是時間戳。

• 是 10 個 bit：表示的是機房 id，0000000000，因為我傳進去的就是0。

• 是 12 個 bit：表示的序號，就是某個機房某臺機器上這一毫秒內同時生成的 id 的序號，0000 0000 0000。

我們分別 解釋一下四個部分：

• 1 bit，是無意義的：

  因為二進位制裡第一個 bit 為如果是 1，那麼都是負數，但是我們生成的 id 都是正數，所以第一個 bit 統一都是 0。

• 41 bit：表示的是時間戳，單位是毫秒。

  41 bit 可以表示的數字多達 2^41 - 1，也就是可以標識 2 ^ 41 - 1 個毫秒值，換算成年就是表示 69 年的時間。

• 10 bit：記錄工作機器 id，代表的是這個服務最多可以部署在 2^10 臺機器上，也就是 1024 臺機器。

  但是 10 bit 裡 5 個 bit 代表機房 id，5 個 bit 代表機器 id。意思就是最多代表 2 ^ 5 個機房（32 個機房），每個機房裡可以代表 2 ^ 5 個機器（32 臺機器），這裡可以隨意拆分，比如拿出4位標識業務號，其他6位作為機器號。可以隨意組合。

• 12 bit：這個是用來記錄同一個毫秒內產生的不同 id。

  12 bit 可以代表的最大正整數是 2 ^ 12 - 1 = 4096，也就是說可以用這個 12 bit 代表的數字來區分同一個毫秒內的 4096 個不同的 id。也就是同一毫秒內同一臺機器所生成的最大ID數量為4096

簡單來說，你的某個服務假設要生成一個全域性唯一 id，那麼就可以傳送一個請求給部署了 SnowFlake 演算法的系統，由這個 SnowFlake 算法系統來生成唯一 id。這個 SnowFlake 算法系統首先肯定是知道自己所在的機器號，（這裡姑且講10bit全部作為工作機器ID）接著 SnowFlake 算法系統接收到這個請求之後，首先就會用二進位制位運算的方式生成一個 64 bit 的 long 型 id，64 個 bit 中的第一個 bit 是無意義的。接著用當前時間戳（單位到毫秒）佔用41 個 bit，然後接著 10 個 bit 設定機器 id。最後再判斷一下，當前這臺機房的這臺機器上這一毫秒內，這是第幾個請求，給這次生成 id 的請求累加一個序號，作為最後的 12 個 bit。

二、PHP原始碼實現案例

1.demo1:

<?php
 
/**
 * 雪花演算法類
 * @package app\helpers
 */
class SnowFlake
{
    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;
    }
}

2. demo2:

<?php
 public function createID(){
        //假設一個機器id
        $machineId = 1234567890;
 
        //41bit timestamp(毫秒)
        $time = floor(microtime(true) * 1000);
 
        //0bit 未使用
        $suffix = 0;
 
        //datacenterId  新增資料的時間
        $base = decbin(pow(2,40) - 1 + $time);
 
        //workerId  機器ID
        $machineid = decbin(pow(2,9) - 1 + $machineId);
 
        //毫秒類的計數
        $random = mt_rand(1, pow(2,11)-1);
 
        $random = decbin(pow(2,11)-1 + $random);
        //拼裝所有資料
        $base64 = $suffix.$base.$machineid.$random;
        //將二進位制轉換int
        $base64 = bindec($base64);
 
        $id = sprintf('%.0f', $base64);
 
        return $id;
    }

SnowFlake的優點是，整體上按照時間自增排序，並且整個分散式系統內不會產生ID碰撞(由資料中心ID和機器ID作區分)，效率較高。但是依賴與系統時間的一致性，如果系統時間被回撥，或者改變，可能會造成id衝突或者重複。實際中我們的機房並沒有那麼多，我們可以改進改演算法，將10bit的機器id優化，成業務表或者和我們系統相關的業務。

*宣告：本文於網路整理，版權歸原作者所有，如來源資訊有誤或侵犯權益，請聯絡我們刪除或授權事宜。

END

點選“檢視原文”獲取更多