【相關(guān)學(xué)習(xí)推薦:mysql視頻教程】
一、為何要用雪花算法
1、問(wèn)題產(chǎn)生的背景
現(xiàn)如今越來(lái)越多的公司都在用分布式、微服務(wù),那么對(duì)應(yīng)的就會(huì)針對(duì)不同的服務(wù)進(jìn)行數(shù)據(jù)庫(kù)拆分,然后當(dāng)數(shù)據(jù)量上來(lái)的時(shí)候也會(huì)進(jìn)行分表,那么隨之而來(lái)的就是分表以后id的問(wèn)題。
例如之前單體項(xiàng)目中一個(gè)表中的數(shù)據(jù)主鍵id都是自增的,mysql是利用autoincrement來(lái)實(shí)現(xiàn)自增,而oracle是利用序列來(lái)實(shí)現(xiàn)的,但是當(dāng)單表數(shù)據(jù)量上來(lái)以后就要進(jìn)行水平分表,阿里java開(kāi)發(fā)建議是單表大于500w的時(shí)候就要分表,但是具體還是得看業(yè)務(wù),如果索引用的號(hào)的話,單表千萬(wàn)的數(shù)據(jù)也是可以的。水平分表就是將一張表的數(shù)據(jù)分成多張表,那么問(wèn)題就來(lái)了如果還是按照以前的自增來(lái)做主鍵id,那么就會(huì)出現(xiàn)id重復(fù),這個(gè)時(shí)候就得考慮用什么方案來(lái)解決分布式id的問(wèn)題了。
2、解決方案
2.1、數(shù)據(jù)庫(kù)表
可以在某個(gè)庫(kù)中專門維護(hù)一張表,然后每次無(wú)論哪個(gè)表需要自增id的時(shí)候都去查這個(gè)表的記錄,然后用for update鎖表,然后取到的值加一,然后返回以后把再把值記錄到表中,但是這個(gè)方法適合并發(fā)量比較小的項(xiàng)目,因此每次都得鎖表。
2.2、redis
因?yàn)閞edis是單線程的,可以在redis中維護(hù)一個(gè)鍵值對(duì),然后哪個(gè)表需要直接去redis中取值然后加一,但是這個(gè)跟上面一樣由于單線程都是對(duì)高并發(fā)的支持不高,只適合并發(fā)量小的項(xiàng)目。
2.3、uuid
可以使用uuid作為不重復(fù)主鍵id,但是uuid有個(gè)問(wèn)題就是其是無(wú)序的字符串,如果使用uuid當(dāng)做主鍵,那么主鍵索引就會(huì)失效。
2.4、雪花算法
雪花算法是解決分布式id的一個(gè)高效的方案,大部分互聯(lián)網(wǎng)公司都在使用雪花算法,當(dāng)然還有公司自己實(shí)現(xiàn)其他的方案。
二、雪花算法
1、原理
雪花算法就是使用64位long類型的數(shù)據(jù)存儲(chǔ)id,最高位一位存儲(chǔ)0或者1,0代表整數(shù),1代表負(fù)數(shù),一般都是0,所以最高位不變,41位存儲(chǔ)毫秒級(jí)時(shí)間戳,10位存儲(chǔ)機(jī)器碼(包括5位datacenterId和5位workerId),12存儲(chǔ)序列號(hào)。這樣最大2的10次方的機(jī)器,也就是1024臺(tái)機(jī)器,最多每毫秒每臺(tái)機(jī)器產(chǎn)生2的12次方也就是4096個(gè)id。(下面有代碼實(shí)現(xiàn))
但是一般我們沒(méi)有那么多臺(tái)機(jī)器,所以我們也可以使用53位來(lái)存儲(chǔ)id。為什么要用53位?
因?yàn)槲覀儙缀醵际歉鷚eb頁(yè)面打交道,就需要跟js打交道,js支持最大的整型范圍為53位,超過(guò)這個(gè)范圍就會(huì)丟失精度,53之內(nèi)可以直接由js讀取,超過(guò)53位就需要轉(zhuǎn)換成字符串才能保證js處理正確。53存儲(chǔ)的話,32位存儲(chǔ)秒級(jí)時(shí)間戳,5位存儲(chǔ)機(jī)器碼,16位存儲(chǔ)序列化,這樣每臺(tái)機(jī)器每秒可以生產(chǎn)65536個(gè)不重復(fù)的id。
2、缺點(diǎn)
由于雪花算法嚴(yán)重依賴時(shí)間,所以當(dāng)發(fā)生服務(wù)器時(shí)鐘回?fù)艿膯?wèn)題是會(huì)導(dǎo)致可能產(chǎn)生重復(fù)的id。當(dāng)然幾乎沒(méi)有公司會(huì)修改服務(wù)器時(shí)間,修改以后會(huì)導(dǎo)致各種問(wèn)題,公司寧愿新加一臺(tái)服務(wù)器也不愿意修改服務(wù)器時(shí)間,但是不排除特殊情況。
如何解決時(shí)鐘回?fù)艿膯?wèn)題?可以對(duì)序列化的初始值設(shè)置步長(zhǎng),每次觸發(fā)時(shí)鐘回?fù)苁录瑒t其初始步長(zhǎng)就加1w,可以在下面代碼的第85行來(lái)實(shí)現(xiàn),將sequence的初始值設(shè)置為10000。
三、代碼實(shí)現(xiàn)
64位的代碼實(shí)現(xiàn):
package com.yl.common; /** * Twitter_Snowflake<br> * SnowFlake的結(jié)構(gòu)如下(每部分用-分開(kāi)):<br> * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br> * 1位標(biāo)識(shí),由于long基本類型在Java中是帶符號(hào)的,最高位是符號(hào)位,正數(shù)是0,負(fù)數(shù)是1,所以id一般是正數(shù),最高位是0<br> * 41位時(shí)間截(毫秒級(jí)),注意,41位時(shí)間截不是存儲(chǔ)當(dāng)前時(shí)間的時(shí)間截,而是存儲(chǔ)時(shí)間截的差值(當(dāng)前時(shí)間截 - 開(kāi)始時(shí)間截) * 得到的值),這里的的開(kāi)始時(shí)間截,一般是我們的id生成器開(kāi)始使用的時(shí)間,由我們程序來(lái)指定的(如下下面程序IdWorker類的startTime屬性)。41位的時(shí)間截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br> * 10位的數(shù)據(jù)機(jī)器位,可以部署在1024個(gè)節(jié)點(diǎn),包括5位datacenterId和5位workerId<br> * 12位序列,毫秒內(nèi)的計(jì)數(shù),12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器,同一時(shí)間截)產(chǎn)生4096個(gè)ID序號(hào)<br> * 加起來(lái)剛好64位,為一個(gè)Long型。<br> * SnowFlake的優(yōu)點(diǎn)是,整體上按照時(shí)間自增排序,并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分),并且效率較高,經(jīng)測(cè)試,SnowFlake每秒能夠產(chǎn)生26萬(wàn)ID左右。 */ public class SnowflakeIdWorker { // ==============================Fields=========================================== /** 開(kāi)始時(shí)間截 (2020-01-01) */ private final long twepoch = 1577808000000L; /** 機(jī)器id所占的位數(shù) */ private final long workerIdBits = 5L; /** 數(shù)據(jù)標(biāo)識(shí)id所占的位數(shù) */ private final long datacenterIdBits = 5L; /** 支持的最大機(jī)器id,結(jié)果是31 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù)) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** 支持的最大數(shù)據(jù)標(biāo)識(shí)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)識(shí)id向左移17位(12+5) */ private final long datacenterIdShift = sequenceBits + workerIdBits; /** 時(shí)間截向左移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的時(shí)間截 */ 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========================================== /** * 獲得下一個(gè)ID (該方法是線程安全的) * @return SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳,說(shuō)明系統(tǒng)時(shí)鐘回退過(guò)這個(gè)時(shí)候應(yīng)當(dāng)拋出異常 if (timestamp < lastTimestamp) { throw new RuntimeException( String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } //如果是同一時(shí)間生成的,則進(jìn)行毫秒內(nèi)序列 if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask; //毫秒內(nèi)序列溢出 if (sequence == 0) { //阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳 timestamp = tilNextMillis(lastTimestamp); } } //時(shí)間戳改變,毫秒內(nèi)序列重置 else { sequence = 0L; } //上次生成ID的時(shí)間截 lastTimestamp = timestamp; //移位并通過(guò)或運(yùn)算拼到一起組成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一個(gè)毫秒,直到獲得新的時(shí)間戳 * @param lastTimestamp 上次生成ID的時(shí)間截 * @return 當(dāng)前時(shí)間戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒為單位的當(dāng)前時(shí)間 * @return 當(dāng)前時(shí)間(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } //==============================Test============================================= /** 測(cè)試 */ 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); } } }
補(bǔ)充知識(shí):雪花算法實(shí)現(xiàn)分布式自增長(zhǎng)ID
我就廢話不多說(shuō)了,大家還是直接看代碼吧~
/** * <p>名稱:IdWorker.java</p> * <p>描述:分布式自增長(zhǎng)ID</p> * <pre> * Twitter的 Snowflake JAVA實(shí)現(xiàn)方案 * </pre> * 核心代碼為其IdWorker這個(gè)類實(shí)現(xiàn),其原理結(jié)構(gòu)如下,我分別用一個(gè)0表示一位,用—分割開(kāi)部分的作用: * 1||0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000 * 在上面的字符串中,第一位為未使用(實(shí)際上也可作為long的符號(hào)位),接下來(lái)的41位為毫秒級(jí)時(shí)間, * 然后5位datacenter標(biāo)識(shí)位,5位機(jī)器ID(并不算標(biāo)識(shí)符,實(shí)際是為線程標(biāo)識(shí)), * 然后12位該毫秒內(nèi)的當(dāng)前毫秒內(nèi)的計(jì)數(shù),加起來(lái)剛好64位,為一個(gè)Long型。 * 這樣的好處是,整體上按照時(shí)間自增排序,并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由datacenter和機(jī)器ID作區(qū)分), * 并且效率較高,經(jīng)測(cè)試,snowflake每秒能夠產(chǎn)生26萬(wàn)ID左右,完全滿足需要。 * <p> * 64位ID (42(毫秒)+5(機(jī)器ID)+5(業(yè)務(wù)編碼)+12(重復(fù)累加)) * * @author Polim */ public class IdWorker { // 時(shí)間起始標(biāo)記點(diǎn),作為基準(zhǔn),一般取系統(tǒng)的最近時(shí)間(一旦確定不能變動(dòng)) private final static long twepoch = 1288834974657L; // 機(jī)器標(biāo)識(shí)位數(shù) private final static long workerIdBits = 5L; // 數(shù)據(jù)中心標(biāo)識(shí)位數(shù) private final static long datacenterIdBits = 5L; // 機(jī)器ID最大值 private final static long maxWorkerId = -1L ^ (-1L << workerIdBits); // 數(shù)據(jù)中心ID最大值 private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 毫秒內(nèi)自增位 private final static long sequenceBits = 12L; // 機(jī)器ID偏左移12位 private final static long workerIdShift = sequenceBits; // 數(shù)據(jù)中心ID左移17位 private final static long datacenterIdShift = sequenceBits + workerIdBits; // 時(shí)間毫秒左移22位 private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private final static long sequenceMask = -1L ^ (-1L << sequenceBits); /* 上次生產(chǎn)id時(shí)間戳 */ private static long lastTimestamp = -1L; // 0,并發(fā)控制 private long sequence = 0L; private final long workerId; // 數(shù)據(jù)標(biāo)識(shí)id部分 private final long datacenterId; public IdWorker(){ this.datacenterId = getDatacenterId(maxDatacenterId); this.workerId = getMaxWorkerId(datacenterId, maxWorkerId); } /** * @param workerId * 工作機(jī)器ID * @param datacenterId * 序列號(hào) */ 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; } /** * 獲取下一個(gè)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) { // 當(dāng)前毫秒內(nèi),則+1 sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { // 當(dāng)前毫秒內(nèi)計(jì)數(shù)滿了,則等待下一秒 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個(gè)低位 */ return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1); } /** * <p> * 數(shù)據(jù)標(biāo)識(shí)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; } }