一、為何要用雪花算法

1、問題產生的背景

現如今越來越多的公司都在用分布式、微服務，那么對應的就會針對不同的服務進行數據庫拆分，然后當數據量上來的時候也會進行分表，那么隨之而來的就是分表以后id的問題。

例如之前單體項目中一個表中的數據主鍵id都是自增的，mysql是利用autoincrement來實現自增，而oracle是利用序列來實現的，但是當單表數據量上來以后就要進行水平分表，阿里java開發建議是單表大于500w的時候就要分表，但是具體還是得看業務，如果索引用的號的話，單表千萬的數據也是可以的。水平分表就是將一張表的數據分成多張表，那么問題就來了如果還是按照以前的自增來做主鍵id，那么就會出現id重復，這個時候就得考慮用什么方案來解決分布式id的問題了。

2、解決方案

2.1、數據庫表

可以在某個庫中專門維護一張表，然后每次無論哪個表需要自增id的時候都去查這個表的記錄，然后用for update鎖表，然后取到的值加一，然后返回以后把再把值記錄到表中，但是這個方法適合并發量比較小的項目，因此每次都得鎖表。

2.2、redis

因為redis是單線程的，可以在redis中維護一個鍵值對，然后哪個表需要直接去redis中取值然后加一，但是這個跟上面一樣由于單線程都是對高并發的支持不高，只適合并發量小的項目。

2.3、uuid

可以使用uuid作為不重復主鍵id，但是uuid有個問題就是其是無序的字符串，如果使用uuid當做主鍵，那么主鍵索引就會失效。

2.4、雪花算法

雪花算法是解決分布式id的一個高效的方案，大部分互聯網公司都在使用雪花算法，當然還有公司自己實現其他的方案。

二、雪花算法

1、原理

雪花算法就是使用64位long類型的數據存儲id，最高位一位存儲0或者1,0代表整數，1代表負數，一般都是0，所以最高位不變，41位存儲毫秒級時間戳，10位存儲機器碼（包括5位datacenterId和5位workerId），12存儲序列號。這樣最大2的10次方的機器，也就是1024臺機器，最多每毫秒每臺機器產生2的12次方也就是4096個id。（下面有代碼實現）

但是一般我們沒有那么多臺機器，所以我們也可以使用53位來存儲id。為什么要用53位？

因為我們幾乎都是跟web頁面打交道，就需要跟js打交道，js支持最大的整型范圍為53位，超過這個范圍就會丟失精度，53之內可以直接由js讀取，超過53位就需要轉換成字符串才能保證js處理正確。53存儲的話，32位存儲秒級時間戳，5位存儲機器碼，16位存儲序列化，這樣每臺機器每秒可以生產65536個不重復的id。

2、缺點

由于雪花算法嚴重依賴時間，所以當發生服務器時鐘回撥的問題是會導致可能產生重復的id。當然幾乎沒有公司會修改服務器時間，修改以后會導致各種問題，公司寧愿新加一臺服務器也不愿意修改服務器時間，但是不排除特殊情況。

如何解決時鐘回撥的問題？可以對序列化的初始值設置步長，每次觸發時鐘回撥事件，則其初始步長就加1w，可以在下面代碼的第85行來實現，將sequence的初始值設置為10000。

三、代碼實現

64位的代碼實現：

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

補充知識：雪花算法實現分布式自增長ID

我就廢話不多說了，大家還是直接看代碼吧~

/** * <p>名稱：IdWorker.java</p> * <p>描述：分布式自增長ID</p> * <pre> * Twitter的 Snowflake　JAVA實現方案 * </pre> * 核心代碼為其IdWorker這個類實現，其原理結構如下，我分別用一個0表示一位，用—分割開部分的作用： * 1||0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000 * 在上面的字符串中，第一位為未使用（實際上也可作為long的符號位），接下來的41位為毫秒級時間， * 然后5位datacenter標識位，5位機器ID（并不算標識符，實際是為線程標識）， * 然后12位該毫秒內的當前毫秒內的計數，加起來剛好64位，為一個Long型。 * 這樣的好處是，整體上按照時間自增排序，并且整個分布式系統內不會產生ID碰撞（由datacenter和機器ID作區分）， * 并且效率較高，經測試，snowflake每秒能夠產生26萬ID左右，完全滿足需要。 * <p> * 64位ID (42(毫秒)+5(機器ID)+5(業務編碼)+12(重復累加)) * * @author Polim */public class IdWorker { // 時間起始標記點，作為基準，一般取系統的最近時間（一旦確定不能變動） private final static long twepoch = 1288834974657L; // 機器標識位數 private final static long workerIdBits = 5L; // 數據中心標識位數 private final static long datacenterIdBits = 5L; // 機器ID最大值 private final static long maxWorkerId = -1L ^ (-1L << workerIdBits); // 數據中心ID最大值 private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 毫秒內自增位 private final static long sequenceBits = 12L; // 機器ID偏左移12位 private final static long workerIdShift = sequenceBits; // 數據中心ID左移17位 private final static long datacenterIdShift = sequenceBits + workerIdBits; // 時間毫秒左移22位 private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private final static long sequenceMask = -1L ^ (-1L << sequenceBits); /* 上次生產id時間戳 */ private static long lastTimestamp = -1L; // 0，并發控制 private long sequence = 0L; private final long workerId; // 數據標識id部分 private final long datacenterId; public IdWorker(){ this.datacenterId = getDatacenterId(maxDatacenterId); this.workerId = getMaxWorkerId(datacenterId, maxWorkerId); } /** * @param workerId * 工作機器ID * @param datacenterId * 序列號 */ public IdWorker(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; } /** * 獲取下一個ID * * @return */ public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { throw new RuntimeException(String.format('Clock moved backwards. Refusing to generate id for %d milliseconds', lastTimestamp - timestamp)); } if (lastTimestamp == timestamp) { // 當前毫秒內，則+1 sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { // 當前毫秒內計數滿了，則等待下一秒 timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; // ID偏移組合生成最終的ID，并返回ID long nextId = ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; return nextId; } private long tilNextMillis(final long lastTimestamp) { long timestamp = this.timeGen(); while (timestamp <= lastTimestamp) { timestamp = this.timeGen(); } return timestamp; } private long timeGen() { return System.currentTimeMillis(); } /** * <p> * 獲取 maxWorkerId * </p> */ protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) { StringBuffer mpid = new StringBuffer(); mpid.append(datacenterId); String name = ManagementFactory.getRuntimeMXBean().getName(); if (!name.isEmpty()) { /* * GET jvmPid */ mpid.append(name.split('@')[0]); } /* * MAC + PID 的 hashcode 獲取16個低位 */ return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1); } /** * <p> * 數據標識id部分 * </p> */ protected static long getDatacenterId(long maxDatacenterId) { long id = 0L; try { InetAddress ip = InetAddress.getLocalHost(); NetworkInterface network = NetworkInterface.getByInetAddress(ip); if (network == null) { id = 1L; } else { byte[] mac = network.getHardwareAddress(); id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6; id = id % (maxDatacenterId + 1); } } catch (Exception e) { System.out.println(' getDatacenterId: ' + e.getMessage()); } return id; }}

以上這篇利用mysql實現的雪花算法案例就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持好吧啦網。