PHP利用雪花(SnowFlake)算法生成唯一ID
這個算法的好處很簡單可以在每秒產生約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優化,成業務表或者和我們系統相關的業務。
到此這篇關於PHP利用雪花(SnowFlake)算法生成唯一ID的文章就介紹到這瞭,更多相關PHP生成唯一ID內容請搜索LevelAH以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持LevelAH!