轉載自?漫畫：什么是SnowFlake算法

方法一：UUID

UUID是通用唯一識別碼 (Universally Unique Identifier)，在其他語言中也叫GUID，可以生成一個長度32位的全局唯一識別碼。

String uuid = UUID.randomUUID().toString()

結果示例：

046b6c7f-0b8a-43b9-b35d-6489e6daee91

為什么無序的UUID會導致入庫性能變差呢？

這就涉及到?B+樹索引的分裂：

眾所周知，關系型數據庫的索引大都是B+樹的結構，拿ID字段來舉例，索引樹的每一個節點都存儲著若干個ID。

如果我們的ID按遞增的順序來插入，比如陸續插入8，9，10，新的ID都只會插入到最后一個節點當中。當最后一個節點滿了，會裂變出新的節點。這樣的插入是性能比較高的插入，因為這樣節點的分裂次數最少，而且充分利用了每一個節點的空間。

但是，如果我們的插入完全無序，不但會導致一些中間節點產生分裂，也會白白創造出很多不飽和的節點，這樣大大降低了數據庫插入的性能。

方法二：數據庫自增主鍵

假設名為table的表有如下結構：

id????????feild

35????????a

每一次生成ID的時候，訪問數據庫，執行下面的語句：

begin;

REPLACE INTO table ( feild )? VALUES ( 'a' );

SELECT LAST_INSERT_ID();

commit;

REPLACE INTO 的含義是插入一條記錄，如果表中唯一索引的值遇到沖突，則替換老數據。

這樣一來，每次都可以得到一個遞增的ID。

為了提高性能，在分布式系統中可以用DB proxy請求不同的分庫，每個分庫設置不同的初始值，步長和分庫數量相等：

這樣一來，DB1生成的ID是1,4,7,10,13....，DB2生成的ID是2,5,8,11,14.....

————————————

初識SnowFlake

snowflake算法所生成的ID結構是什么樣子呢？我們來看看下圖：

SnowFlake所生成的ID一共分成四部分：

1.第一位

占用1bit，其值始終是0，沒有實際作用。

2.時間戳

占用41bit，精確到毫秒，總共可以容納約69?年的時間。

3.工作機器id

占用10bit，其中高位5bit是數據中心ID（datacenterId），低位5bit是工作節點ID（workerId），做多可以容納1024個節點。

4.序列號

占用12bit，這個值在同一毫秒同一節點上從0開始不斷累加，最多可以累加到4095。

SnowFlake算法在同一毫秒內最多可以生成多少個全局唯一ID呢？只需要做一個簡單的乘法：

同一毫秒的ID數量 = 1024 X 4096 =? 4194304

這個數字在絕大多數并發場景下都是夠用的。

SnowFlake的代碼實現

//初始時間截 (2017-01-01) private static final long INITIAL_TIME_STAMP = 1483200000000L;//機器id所占的位數 private static final long WORKER_ID_BITS = 5L;//數據標識id所占的位數 private static final long DATACENTER_ID_BITS = 5L;//支持的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數) private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);//支持的最大數據標識id，結果是31 private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS);//序列在id中占的位數 private final long SEQUENCE_BITS = 12L;//機器ID的偏移量(12) private final long WORKERID_OFFSET = SEQUENCE_BITS;//數據中心ID的偏移量(12+5) private final long DATACENTERID_OFFSET = SEQUENCE_BITS + SEQUENCE_BITS;//時間截的偏移量(5+5+12) private final long TIMESTAMP_OFFSET = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS;//生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095) private final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);//工作節點ID(0~31) private long workerId;//數據中心ID(0~31) private long datacenterId;//毫秒內序列(0~4095) private long sequence = 0L;//上次生成ID的時間截 private long lastTimestamp = -1L;/*** 構造函數** @param workerId 工作ID (0~31)* @param datacenterId 數據中心ID (0~31)*/ public SnowFlakeIdGenerator(long workerId, long datacenterId) {if (workerId > MAX_WORKER_ID || workerId < 0) {throw new IllegalArgumentException(String.format("WorkerID 不能大于 %d 或小于 0", MAX_WORKER_ID));}if (datacenterId > MAX_DATACENTER_ID || datacenterId < 0) {throw new IllegalArgumentException(String.format("DataCenterID 不能大于 %d 或小于 0", MAX_DATACENTER_ID));}this.workerId = workerId;this.datacenterId = datacenterId; }/*** 獲得下一個ID (用同步鎖保證線程安全)** @return SnowflakeId*/ public synchronized long nextId() {long timestamp = System.currentTimeMillis();//如果當前時間小于上一次ID生成的時間戳，說明系統時鐘回退過這個時候應當拋出異常if (timestamp < lastTimestamp) {throw new RuntimeException("當前時間小于上一次記錄的時間戳！");}//如果是同一時間生成的，則進行毫秒內序列if (lastTimestamp == timestamp) {sequence = (sequence + 1) & SEQUENCE_MASK;//sequence等于0說明毫秒內序列已經增長到最大值if (sequence == 0) {//阻塞到下一個毫秒,獲得新的時間戳timestamp = tilNextMillis(lastTimestamp);}}//時間戳改變，毫秒內序列重置else {sequence = 0L;}//上次生成ID的時間截lastTimestamp = timestamp;//移位并通過或運算拼到一起組成64位的IDreturn ((timestamp - INITIAL_TIME_STAMP) << TIMESTAMP_OFFSET)| (datacenterId << DATACENTERID_OFFSET)| (workerId << WORKERID_OFFSET)| sequence; }/*** 阻塞到下一個毫秒，直到獲得新的時間戳** @param lastTimestamp 上次生成ID的時間截* @return 當前時間戳*/ protected long tilNextMillis(long lastTimestamp) {long timestamp = System.currentTimeMillis();while (timestamp <= lastTimestamp) {timestamp = System.currentTimeMillis();}return timestamp; }public static void main(String[] args) {final SnowFlakeIdGenerator idGenerator = new SnowFlakeIdGenerator(1, 1);//線程池并行執行10000次ID生成ExecutorService executorService = Executors.newCachedThreadPool();;for (int i = 0; i < 10000; i++) {executorService.execute(new Runnable() {@Overridepublic void run() {long id = idGenerator.nextId();System.out.println(id);}});}executorService.shutdown(); }

這段代碼改寫自網上的SnowFlake算法實現，有幾點需要解釋一下：

1.獲得單一機器的下一個序列號，使用Synchronized控制并發，而非CAS的方式，是因為CAS不適合并發量非常高的場景。

2.如果當前毫秒在一臺機器的序列號已經增長到最大值4095，則使用while循環等待直到下一毫秒。

3.如果當前時間小于記錄的上一個毫秒值，則說明這臺機器的時間回撥了，拋出異常。但如果這臺機器的系統時間在啟動之前回撥過，那么有可能出現ID重復的危險。

SnowFlake的優勢和劣勢

SnowFlake算法的優點：

1.生成ID時不依賴于DB，完全在內存生成，高性能高可用。

2.ID呈趨勢遞增，后續插入索引樹的時候性能較好。

SnowFlake算法的缺點：

依賴于系統時鐘的一致性。如果某臺機器的系統時鐘回撥，有可能造成ID沖突，或者ID亂序。

總結

以上是生活随笔為你收集整理的漫画：什么是SnowFlake算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。