雪花算法（Twitter_Snowflake）

我們知道，分布式全局唯一id的生成，一般是以下幾種：

基于雪花算法生成

基于數(shù)據(jù)庫

基于redis

基于zookeeper

本文說下雪花算法，后面附源碼以及測試代碼。

如下圖：

如上圖：雪花算法生成的id，總共64位
第一位作為保留位，默認(rèn)0
中間41位用來存放時間戳，是當(dāng)前時間與初始時間的差值，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
后10位是機(jī)器id，可滿足同時(1L << 10) = 1024個機(jī)器同時生成id
最后12位作為隨機(jī)序列，每個機(jī)器，每毫秒可生成(1L << 12) = 4096個不同的值

改進(jìn)：

其實雪花算法就是把id按位打散，然后再分成上面這幾塊，用位來表示狀態(tài)，這其實就是一種思想。
所以咱們實際在用的時候，也不必非得按照上面這種分割，只需保證總位數(shù)在64位即可

如果你的業(yè)務(wù)不需要69年這么長，或者需要更長時間
用42位存儲時間戳，(1L << 42) / (1000L * 60 * 60 * 24 * 365) = 139年
用41位存儲時間戳，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
用40位存儲時間戳，(1L << 40) / (1000L * 60 * 60 * 24 * 365) = 34年
用39位存儲時間戳，(1L << 39) / (1000L * 60 * 60 * 24 * 365) = 17年
用38位存儲時間戳，(1L << 38) / (1000L * 60 * 60 * 24 * 365) = 8年
用37位存儲時間戳，(1L << 37) / (1000L * 60 * 60 * 24 * 365) = 4年

如果你的機(jī)器沒有那么1024個這么多，或者比1024還多
用7位存儲機(jī)器id，(1L << 7) = 128
用8位存儲機(jī)器id，(1L << 8) = 256
用9位存儲機(jī)器id，(1L << 9) = 512
用10位存儲機(jī)器id，(1L << 10) = 1024
用11位存儲機(jī)器id，(1L << 11) = 2048
用12位存儲機(jī)器id，(1L << 12) = 4096
用13位存儲機(jī)器id，(1L << 13) = 8192

如果你的業(yè)務(wù)，每個機(jī)器，每毫秒最多也不會4096個id要生成，或者比這個還多
用8位存儲隨機(jī)序列，(1L << 8) = 256
用9位存儲隨機(jī)序列，(1L << 9) = 512
用10位存儲隨機(jī)序列，(1L << 10) = 1024
用11位存儲隨機(jī)序列，(1L << 11) = 2048
用12位存儲隨機(jī)序列，(1L << 12) = 4096
用13位存儲隨機(jī)序列，(1L << 13) = 8192
用14位存儲隨機(jī)序列，(1L << 14) = 16384
用15位存儲隨機(jī)序列，(1L << 15) = 32768
注意，隨機(jī)序列建議不要太大，一般業(yè)務(wù)，每毫秒要是能產(chǎn)生這么多id，建議在機(jī)器id上增加位

如果你的業(yè)務(wù)量很小，比如一般情況下每毫秒生成不到1個id，此時可以將隨機(jī)序列設(shè)置成隨機(jī)開始自增
比如從0到48隨機(jī)開始自增，算是一種優(yōu)化建議

如果你有多個業(yè)務(wù)，也可以拿出來幾位來表示業(yè)務(wù)，比如用最后4位，支持16種業(yè)務(wù)的區(qū)分

如果你的業(yè)務(wù)特別復(fù)雜，可以考慮128位存儲，不過這樣的話，也可以考慮使用uuid了，但uuid無序，這個有序

如果你的業(yè)務(wù)很簡單，甚至可以考慮32位存儲，時間戳改成秒為單位…

總結(jié)：

合理的根據(jù)自己的實際情況去設(shè)計各個唯一條件的組合，雪花算法只是提供了一種相對合理的方式。

雪花算法這種用位來表示狀態(tài)的，我們還可以用在其他方面，比如數(shù)據(jù)庫存儲，可以用更小的空間去表示不同的狀態(tài)位
包括各種底層的比如序列化，也是有用到拆解位，充分利用存儲

源碼：

package com.zs.common;/*** Twitter_Snowflake<br>* SnowFlake的結(jié)構(gòu)如下(每部分用-分開):<br>* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>* 1位標(biāo)識，由于long基本類型在Java中是帶符號的，最高位是符號位，正數(shù)是0，負(fù)數(shù)是1，所以id一般是正數(shù)，最高位是0<br>* 41位時間截(毫秒級)，注意，41位時間截不是存儲當(dāng)前時間的時間截，而是存儲時間截的差值（當(dāng)前時間截 - 開始時間截)* 得到的值），這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。41位的時間截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>* 10位的數(shù)據(jù)機(jī)器位，可以部署在1024個節(jié)點，包括5位datacenterId和5位workerId<br>* 12位序列，毫秒內(nèi)的計數(shù)，12位的計數(shù)順序號支持每個節(jié)點每毫秒(同一機(jī)器，同一時間截)產(chǎn)生4096個ID序號<br>* 加起來剛好64位，為一個Long型。<br>* SnowFlake的優(yōu)點是，整體上按照時間自增排序，并且整個分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)，并且效率較高，經(jīng)測試，SnowFlake每秒能夠產(chǎn)生26萬ID左右。*/ public class SnowflakeIdWorker {// ==============================Fields===========================================/*** 開始時間截 (2015-01-01)*/private final long twepoch = 1420041600000L;/*** 機(jī)器id所占的位數(shù)*/private final long workerIdBits = 5L;/*** 數(shù)據(jù)標(biāo)識id所占的位數(shù)*/private final long datacenterIdBits = 5L;/*** 支持的最大機(jī)器id，結(jié)果是31 (這個移位算法可以很快的計算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))*/private final long maxWorkerId = -1L ^ (-1L << workerIdBits);/*** 支持的最大數(shù)據(jù)標(biāo)識id，結(jié)果是31*/private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);/*** 序列在id中占的位數(shù)*/private final long sequenceBits = 12L;/*** 機(jī)器ID向左移12位*/private final long workerIdShift = sequenceBits;/*** 數(shù)據(jù)標(biāo)識id向左移17位(12+5)*/private final long datacenterIdShift = sequenceBits + workerIdBits;/*** 時間截向左移22位(5+5+12)*/private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;/*** 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095)*/private final long sequenceMask = -1L ^ (-1L << sequenceBits);/*** 工作機(jī)器ID(0~31)*/private long workerId;/*** 數(shù)據(jù)中心ID(0~31)*/private long datacenterId;/*** 毫秒內(nèi)序列(0~4095)*/private long sequence = 0L;/*** 上次生成ID的時間截*/private long lastTimestamp = -1L;//==============================Constructors=====================================/*** 構(gòu)造函數(shù)** @param workerId 工作ID (0~31)* @param datacenterId 數(shù)據(jù)中心ID (0~31)*/public SnowflakeIdWorker(long workerId, long datacenterId) {if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));}if (datacenterId > maxDatacenterId || datacenterId < 0) {throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));}this.workerId = workerId;this.datacenterId = datacenterId;}// ==============================Methods==========================================/*** 獲得下一個ID (該方法是線程安全的)** @return SnowflakeId*/public synchronized long nextId() {long timestamp = timeGen();//如果當(dāng)前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常if (timestamp < lastTimestamp) {throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));}//如果是同一時間生成的，則進(jìn)行毫秒內(nèi)序列if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;//毫秒內(nèi)序列溢出if (sequence == 0) {//阻塞到下一個毫秒,獲得新的時間戳timestamp = tilNextMillis(lastTimestamp);}}//時間戳改變，毫秒內(nèi)序列重置else {sequence = 0L;}//上次生成ID的時間截lastTimestamp = timestamp;//移位并通過或運(yùn)算拼到一起組成64位的IDreturn ((timestamp - twepoch) << timestampLeftShift) //| (datacenterId << datacenterIdShift) //| (workerId << workerIdShift) //| sequence;}/*** 阻塞到下一個毫秒，直到獲得新的時間戳** @param lastTimestamp 上次生成ID的時間截* @return 當(dāng)前時間戳*/protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}/*** 返回以毫秒為單位的當(dāng)前時間** @return 當(dāng)前時間(毫秒)*/protected long timeGen() {return System.currentTimeMillis();}//==============================Test=============================================/*** 測試*/public static void main(String[] args) {long start = System.currentTimeMillis();SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 3);for (int i = 0; i < 50; i++) {long id = idWorker.nextId();System.out.println(Long.toBinaryString(id));System.out.println(id);}long end = System.currentTimeMillis();System.out.println(end - start);} }

總結(jié)

以上是生活随笔為你收集整理的[分布式] ------ 全局唯一id生成之雪花算法（Twitter_Snowflake）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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