這個(gè)算法的好處很簡(jiǎn)單可以在每秒產(chǎn)生約400W個(gè)不同的16位數(shù)字ID(10進(jìn)制)

一、雪花算法原理解析

1. 分布式ID常見(jiàn)生成策略

分布式ID生成策略常見(jiàn)的有如下幾種：

• 數(shù)據(jù)庫(kù)自增ID。
• UUID生成。
• Redis的原子自增方式。
• 數(shù)據(jù)庫(kù)水平拆分，設(shè)置初始值和相同的自增步長(zhǎng)。
• 批量申請(qǐng)自增ID。
• 雪花算法。
• 百度UidGenerator算法(基于雪花算法實(shí)現(xiàn)自定義時(shí)間戳)。
• 美團(tuán)Leaf算法(依賴(lài)于數(shù)據(jù)庫(kù)，ZK)。

本文主要介紹SnowFlake 算法，是 Twitter 開(kāi)源的分布式 id 生成算法。

其核心思想就是：使用一個(gè) 64 bit 的 long 型的數(shù)字作為全局唯一 id。在分布式系統(tǒng)中的應(yīng)用十分廣泛，且ID 引入了時(shí)間戳，保持自增性且不重復(fù)。

2. 雪花算法的結(jié)構(gòu)

主要分為以下幾個(gè)部分：

• 是 1 個(gè) bit：0，這個(gè)是無(wú)意義的。
• 是 41 個(gè) bit：表示的是時(shí)間戳。
• 是 10 個(gè) bit：表示的是機(jī)房 id，0000000000，因?yàn)槲覀鬟M(jìn)去的就是0。
• 是 12 個(gè) bit：表示的序號(hào)，就是某個(gè)機(jī)房某臺(tái)機(jī)器上這一毫秒內(nèi)同時(shí)生成的 id 的序號(hào)，0000 0000 0000。

我們分別解釋一下四個(gè)部分：

1 bit

是無(wú)意義的：

因?yàn)槎M(jìn)制里第一個(gè) bit 為如果是 1，那么都是負(fù)數(shù)，但是我們生成的 id 都是正數(shù)，所以第一個(gè) bit 統(tǒng)一都是 0。

41 bit

表示的是時(shí)間戳，單位是毫秒。

41 bit 可以表示的數(shù)字多達(dá) 2^41 - 1，也就是可以標(biāo)識(shí) 2 ^ 41 - 1 個(gè)毫秒值，換算成年就是表示 69 年的時(shí)間。

10 bit

記錄工作機(jī)器 id，代表的是這個(gè)服務(wù)最多可以部署在 2^10 臺(tái)機(jī)器上，也就是 1024 臺(tái)機(jī)器。

但是 10 bit 里 5 個(gè) bit 代表機(jī)房 id，5 個(gè) bit 代表機(jī)器 id。意思就是最多代表 2 ^ 5 個(gè)機(jī)房（32 個(gè)機(jī)房），每個(gè)機(jī)房里可以代表 2 ^ 5 個(gè)機(jī)器（32 臺(tái)機(jī)器），這里可以隨意拆分，比如拿出4位標(biāo)識(shí)業(yè)務(wù)號(hào)，其他6位作為機(jī)器號(hào)?？梢噪S意組合。

12 bit

這個(gè)是用來(lái)記錄同一個(gè)毫秒內(nèi)產(chǎn)生的不同 id。

12 bit 可以代表的最大正整數(shù)是 2 ^ 12 - 1 = 4096，也就是說(shuō)可以用這個(gè) 12 bit 代表的數(shù)字來(lái)區(qū)分同一個(gè)毫秒內(nèi)的 4096 個(gè)不同的 id。也就是同一毫秒內(nèi)同一臺(tái)機(jī)器所生成的最大ID數(shù)量為4096

簡(jiǎn)單來(lái)說(shuō)，你的某個(gè)服務(wù)假設(shè)要生成一個(gè)全局唯一 id，那么就可以發(fā)送一個(gè)請(qǐng)求給部署了 SnowFlake 算法的系統(tǒng)，由這個(gè) SnowFlake 算法系統(tǒng)來(lái)生成唯一 id。這個(gè) SnowFlake 算法系統(tǒng)首先肯定是知道自己所在的機(jī)器號(hào)，（這里姑且講10bit全部作為工作機(jī)器ID）接著 SnowFlake 算法系統(tǒng)接收到這個(gè)請(qǐng)求之后，首先就會(huì)用二進(jìn)制位運(yùn)算的方式生成一個(gè) 64 bit 的 long 型 id，64 個(gè) bit 中的第一個(gè) bit 是無(wú)意義的。接著用當(dāng)前時(shí)間戳（單位到毫秒）占用41 個(gè) bit，然后接著 10 個(gè) bit 設(shè)置機(jī)器 id。最后再判斷一下，當(dāng)前這臺(tái)機(jī)房的這臺(tái)機(jī)器上這一毫秒內(nèi)，這是第幾個(gè)請(qǐng)求，給這次生成 id 的請(qǐng)求累加一個(gè)序號(hào)，作為最后的 12 個(gè) bit。

二、PHP源碼實(shí)現(xiàn)案例

1.demo1

<?php
 
/**
 * 雪花算法類(lèi)
 * @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(){
        //假設(shè)一個(gè)機(jī)器id
        $machineId = 1234567890;
 
        //41bit timestamp(毫秒)
        $time = floor(microtime(true) * 1000);
 
        //0bit 未使用
        $suffix = 0;
 
        //datacenterId  添加數(shù)據(jù)的時(shí)間
        $base = decbin(pow(2,40) - 1 + $time);
 
        //workerId  機(jī)器ID
        $machineid = decbin(pow(2,9) - 1 + $machineId);
 
        //毫秒類(lèi)的計(jì)數(shù)
        $random = mt_rand(1, pow(2,11)-1);
 
        $random = decbin(pow(2,11)-1 + $random);
        //拼裝所有數(shù)據(jù)
        $base64 = $suffix.$base.$machineid.$random;
        //將二進(jìn)制轉(zhuǎn)換int
        $base64 = bindec($base64);
 
        $id = sprintf('%.0f', $base64);
 
        return $id;
    }

SnowFlake的優(yōu)點(diǎn)是，整體上按照時(shí)間自增排序，并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)，效率較高。但是依賴(lài)與系統(tǒng)時(shí)間的一致性，如果系統(tǒng)時(shí)間被回調(diào)，或者改變，可能會(huì)造成id沖突或者重復(fù)。實(shí)際中我們的機(jī)房并沒(méi)有那么多，我們可以改進(jìn)改算法，將10bit的機(jī)器id優(yōu)化，成業(yè)務(wù)表或者和我們系統(tǒng)相關(guān)的業(yè)務(wù)。

到此這篇關(guān)于PHP利用雪花(SnowFlake)算法生成唯一ID的文章就介紹到這了,更多相關(guān)PHP生成唯一ID內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論