簡(jiǎn)介

Snowflake 是 Twitter 提出一種的分布式唯一序列號(hào)生成算法，理論上單節(jié)點(diǎn) 1 毫秒可以生成 4096 個(gè)(每秒四百萬個(gè))唯一序列，這個(gè)序列是個(gè) long 類型的數(shù)字，在數(shù)據(jù)庫(kù)中的存儲(chǔ)和查詢也非常高效。其原理很簡(jiǎn)單，卻又很精妙。

原理

Snowflake 算法生成的序列號(hào)充分地利用了每一個(gè)比特位，需要占用 8bytes ( 64bits ) 空間，這 64 個(gè) bit 一共分成 4 部分：

0 | 00000000000000000000000000000000000000000 | 0000000000 | 000000000000

定值，1 位 | 時(shí)間戳(毫秒)，41 位 | 節(jié)點(diǎn)序號(hào)，10 位 | 自增序列，12 位

第一部分只有一位，固定為 0 ，可以理解成是有符號(hào)長(zhǎng)整型的正數(shù)；

第二部分占 41 位，用來存生成該序列號(hào)時(shí)的時(shí)間戳(毫秒)，默認(rèn)情況下可以用到 2039-09-07 23:47:35；

第三部分占 10 位，是機(jī)器節(jié)點(diǎn) id，取值范圍為 0~1023(2^10-1) ，即最大支持 1024 個(gè)計(jì)算節(jié)點(diǎn)；

第四部分占 12 位，自增序列，每生成一個(gè)序列號(hào)之后循環(huán)自增，取值范圍是 0~4095(2^12-1)

算法就是這么簡(jiǎn)單

實(shí)現(xiàn)

實(shí)現(xiàn)起來也非常簡(jiǎn)單，這里給一個(gè) PHP 的例子：

class Snowflake

{

// 41 位、10 位、 12 位的最大值，作為掩碼使用

const MAX41BITS = 2199023255551;

const MAX10BITS = 1023;

const MAX12BITS = 4095;

private $nodeId;

private $seq;

public function __construct($nodeId)

{

$this->nodeId = $nodeId;

$this->seq = 0;

}

public function next()

{

// 獲取當(dāng)前時(shí)間戳(毫秒)

list($microsec, $sec) = explode(" ", microtime());

$timestamp = $sec * 1000 + (int)($microsec * 1000);

// 生成 id

// 這里用到了位運(yùn)算，稍微解釋一下：

// 先將時(shí)間戳與 41 位的最大值做一次與運(yùn)算，保證其長(zhǎng)度不會(huì)超過 41 位；

// 再將節(jié)點(diǎn)號(hào)跟 10 位的最大值做與運(yùn)算，也是保證其長(zhǎng)度不會(huì)超過 10 位；

// 然后將時(shí)間戳左移 22 位、節(jié)點(diǎn)號(hào)左移 12 位，這樣就能使得時(shí)間戳在第 2 位到第 42 位、節(jié)點(diǎn)號(hào)在第 43 位到第 52 位；

// 最后再對(duì)時(shí)間戳、節(jié)點(diǎn)號(hào)、自增序列做一次或運(yùn)算，這樣三個(gè)數(shù)字就拼接在一起了

$id = ($timestamp & self::MAX41BITS) << 22 | ($this->nodeId & self::MAX10BITS) << 12 | $this->seq;

// id 生成好之后將自增序列加 1 同時(shí)與 12 位的最大值做與運(yùn)算，這樣就能達(dá)到循環(huán)滾動(dòng)的效果

$this->seq = (++$this->seq) & self::MAX12BITS;

return $id;

}

public function parse($id)

{

$timestamp = ($id >> 22);

$nodeId = ($id >> 12) & self::MAX10BITS;

$seq = $id & self::MAX12BITS;

return [$timestamp, $nodeId, $seq];

}

}

// 測(cè)試一下

$snowflake = new Snowflake(1);

for ($i = 0; $i < 1000; $i++)

{

$id = $snowflake->next();

echo $id . " ";

list($timestamp, $nodeId, $seq) = $snowflake->parse($id);

echo $timestamp . " " . $nodeId . " " . $seq . PHP_EOL;

}

在我的機(jī)器上(MacBook Pro 2017 13inch i5/8G)，一毫秒大概能生成 40 個(gè)左右 id，只達(dá)到了理論值一毫秒 4096 個(gè)的百分之一，所以不用擔(dān)心并發(fā)太大會(huì)導(dǎo)致生成了重復(fù)的 id(還沒有用完 4096 個(gè)自增序列，時(shí)間位就已經(jīng)加一啦)，而且，在更大并發(fā)的情況下，相信你也不會(huì)只用一個(gè)計(jì)算節(jié)點(diǎn)來抗~

改進(jìn)

上面介紹的是 Snowflake 的常規(guī)版本，因?yàn)榉浅：?jiǎn)單，所以在實(shí)際項(xiàng)目中，我們可以根據(jù)業(yè)務(wù)來做一些改進(jìn)，這里舉幾個(gè)改進(jìn)點(diǎn)

時(shí)間戳

前面說到，時(shí)間戳位默認(rèn)情況下可以用到 2039-09-07 23:47:35 ，這是因?yàn)槲覀兪菑?1970-01-01 08:00:00 (UTC+8) 作為時(shí)間原點(diǎn)的，而從 UNIX 時(shí)間零點(diǎn)到我們的項(xiàng)目上線這里有個(gè)四十多年的時(shí)間，因此我們可以設(shè)置一個(gè)新的時(shí)間零點(diǎn)，使得算法可以用更長(zhǎng)時(shí)間。

例如我們可以新增一個(gè) 紀(jì)元常量 ，可以取新項(xiàng)目上線第一天的 0:00

const EPOCH = 1535731200000; // 2018-09-01 0:00:00.000

那么在 next() 里的位運(yùn)算前，我們就需要將時(shí)間戳做一次減法：

$timestamp -= self::EPOCH;

同樣的，在 parse() 里需要將 self::EPOCH 加回去。只要保證同一個(gè)項(xiàng)目(或者同一個(gè)團(tuán)隊(duì))用同一個(gè)“時(shí)間零點(diǎn)”，就能夠?qū)?id 還原出原有的信息

節(jié)點(diǎn)位、自增序列位

在實(shí)際項(xiàng)目中，我們往往不會(huì)/不需要部署 1024 個(gè)那么多的 snowflake 服務(wù)，所以我們可以將節(jié)點(diǎn)位由 10 位改成 5 位(最大支持 32 個(gè)節(jié)點(diǎn))甚至是 4 位(最大支持 16 個(gè)節(jié)點(diǎn))，這樣就能多出來 5~6 位，可以拿來做什么呢？

可以存儲(chǔ)一些業(yè)務(wù)信息，比如說 user_id 、 order_id 等等都是用 snowflake 來生成的時(shí)候，我們可以將多出來的那幾位作為一個(gè) 業(yè)務(wù)編號(hào)位 ，通過這樣改進(jìn)之后，一個(gè) id 攜帶的信息就多了一些，拿到一個(gè) id 之后也可以判斷出這個(gè) id 是什么業(yè)務(wù)的，數(shù)據(jù)庫(kù)查詢的時(shí)候就能知道該查哪張表。

同樣的，自增序列位也可以按需縮減到 11 位或者是 10 位。

gRPC 服務(wù)

我們可以將 Snowflake 做成一個(gè) RPC 服務(wù)，提供給不同的項(xiàng)目調(diào)用，這里我寫了一個(gè)簡(jiǎn)單的 gRPC 的例子，用 Golang 寫的服務(wù)端(截止本文撰寫日，PHP 還不支持寫 gRPC 服務(wù)，只能寫客戶端)，PHP 寫的客戶端

總結(jié)

以上是生活随笔為你收集整理的snowflake算法 php,Snowflake —— 分布式全局唯一 id 生成算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。