摘要:分布式生成算法的有很多種,的就是其中經(jīng)典的一種。負(fù)數(shù)的二進(jìn)制表示在計(jì)算機(jī)中,負(fù)數(shù)的二進(jìn)制是用補(bǔ)碼來(lái)表示的。
分布式id生成算法的有很多種,Twitter的SnowFlake就是其中經(jīng)典的一種。概述
SnowFlake算法生成id的結(jié)果是一個(gè)64bit大小的整數(shù),它的結(jié)構(gòu)如下圖:
1位,不用。二進(jìn)制中最高位為1的都是負(fù)數(shù),但是我們生成的id一般都使用整數(shù),所以這個(gè)最高位固定是0
41位,用來(lái)記錄時(shí)間戳(毫秒)。
41位可以表示$2^{41}-1$個(gè)數(shù)字,
如果只用來(lái)表示正整數(shù)(計(jì)算機(jī)中正數(shù)包含0),可以表示的數(shù)值范圍是:0 至 $2^{41}-1$,減1是因?yàn)榭杀硎镜臄?shù)值范圍是從0開(kāi)始算的,而不是1。
也就是說(shuō)41位可以表示$2^{41}-1$個(gè)毫秒的值,轉(zhuǎn)化成單位年則是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
10位,用來(lái)記錄工作機(jī)器id。
可以部署在$2^{10} = 1024$個(gè)節(jié)點(diǎn),包括5位datacenterId和5位workerId
5位(bit)可以表示的最大正整數(shù)是$2^{5}-1 = 31$,即可以用0、1、2、3、....31這32個(gè)數(shù)字,來(lái)表示不同的datecenterId或workerId
12位,序列號(hào),用來(lái)記錄同毫秒內(nèi)產(chǎn)生的不同id。
12位(bit)可以表示的最大正整數(shù)是$2^{12}-1 = 4095$,即可以用0、1、2、3、....4094這4095個(gè)數(shù)字,來(lái)表示同一機(jī)器同一時(shí)間截(毫秒)內(nèi)產(chǎn)生的4095個(gè)ID序號(hào)
由于在Java中64bit的整數(shù)是long類(lèi)型,所以在Java中SnowFlake算法生成的id就是long來(lái)存儲(chǔ)的。
SnowFlake可以保證:
所有生成的id按時(shí)間趨勢(shì)遞增
整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生重復(fù)id(因?yàn)橛衐atacenterId和workerId來(lái)做區(qū)分)
Talk is cheap, show you the code以下是Twitter官方原版的,用Scala寫(xiě)的,(我也不懂Scala,當(dāng)成Java看即可):
/** Copyright 2010-2012 Twitter, Inc.*/ package com.twitter.service.snowflake import com.twitter.ostrich.stats.Stats import com.twitter.service.snowflake.gen._ import java.util.Random import com.twitter.logging.Logger /** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */ class IdWorker( val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L) extends Snowflake.Iface { private[this] def genCounter(agent: String) = { Stats.incr("ids_generated") Stats.incr("ids_generated_%s".format(agent)) } private[this] val exceptionCounter = Stats.getCounter("exceptions") private[this] val log = Logger.get private[this] val rand = new Random val twepoch = 1288834974657L private[this] val workerIdBits = 5L private[this] val datacenterIdBits = 5L private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits) private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) private[this] val sequenceBits = 12L private[this] val workerIdShift = sequenceBits private[this] val datacenterIdShift = sequenceBits + workerIdBits private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits private[this] val sequenceMask = -1L ^ (-1L << sequenceBits) private[this] var lastTimestamp = -1L // sanity check for workerId if (workerId > maxWorkerId || workerId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("worker Id can"t be greater than %d or less than 0".format(maxWorkerId)) } if (datacenterId > maxDatacenterId || datacenterId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("datacenter Id can"t be greater than %d or less than 0".format(maxDatacenterId)) } log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId) def get_id(useragent: String): Long = { if (!validUseragent(useragent)) { exceptionCounter.incr(1) throw new InvalidUserAgentError } val id = nextId() genCounter(useragent) reporter.report(new AuditLogEntry(id, useragent, rand.nextLong)) id } def get_worker_id(): Long = workerId def get_datacenter_id(): Long = datacenterId def get_timestamp() = System.currentTimeMillis protected[snowflake] def nextId(): Long = synchronized { var timestamp = timeGen() if (timestamp < lastTimestamp) { exceptionCounter.incr(1) log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format( lastTimestamp - timestamp)) } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } lastTimestamp = timestamp ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence } protected def tilNextMillis(lastTimestamp: Long): Long = { var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp } protected def timeGen(): Long = System.currentTimeMillis() val AgentParser = """([a-zA-Z][a-zA-Z-0-9]*)""".r def validUseragent(useragent: String): Boolean = useragent match { case AgentParser(_) => true case _ => false } }
Scala是一門(mén)可以編譯成字節(jié)碼的語(yǔ)言,簡(jiǎn)單理解是在Java語(yǔ)法基礎(chǔ)上加上了很多語(yǔ)法糖,例如不用每條語(yǔ)句后寫(xiě)分號(hào),可以使用動(dòng)態(tài)類(lèi)型等等。抱著試一試的心態(tài),我把Scala版的代碼“翻譯”成Java版本的,對(duì)scala代碼改動(dòng)的地方如下:
/** Copyright 2010-2012 Twitter, Inc.*/ package com.twitter.service.snowflake import com.twitter.ostrich.stats.Stats import com.twitter.service.snowflake.gen._ import java.util.Random import com.twitter.logging.Logger /** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */ class IdWorker( // | val workerId: Long, // | val datacenterId: Long, // |<--這部分改成Java的構(gòu)造函數(shù)形式 private val reporter: Reporter,//日志相關(guān),刪 // | var sequence: Long = 0L) // | extends Snowflake.Iface { //接口找不到,刪 // | private[this] def genCounter(agent: String) = { // | Stats.incr("ids_generated") // | Stats.incr("ids_generated_%s".format(agent)) // |<--錯(cuò)誤、日志處理相關(guān),刪 } // | private[this] val exceptionCounter = Stats.getCounter("exceptions") // | private[this] val log = Logger.get // | private[this] val rand = new Random // | val twepoch = 1288834974657L private[this] val workerIdBits = 5L private[this] val datacenterIdBits = 5L private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits) private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) private[this] val sequenceBits = 12L private[this] val workerIdShift = sequenceBits private[this] val datacenterIdShift = sequenceBits + workerIdBits private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits private[this] val sequenceMask = -1L ^ (-1L << sequenceBits) private[this] var lastTimestamp = -1L //----------------------------------------------------------------------------------------------------------------------------// // sanity check for workerId // if (workerId > maxWorkerId || workerId < 0) { // exceptionCounter.incr(1) //<--錯(cuò)誤處理相關(guān),刪 // throw new IllegalArgumentException("worker Id can"t be greater than %d or less than 0".format(maxWorkerId)) //這 // |-->改成:throw new IllegalArgumentException //部 // (String.format("worker Id can"t be greater than %d or less than 0",maxWorkerId)) //分 } //放 //到 if (datacenterId > maxDatacenterId || datacenterId < 0) { //構(gòu) exceptionCounter.incr(1) //<--錯(cuò)誤處理相關(guān),刪 //造 throw new IllegalArgumentException("datacenter Id can"t be greater than %d or less than 0".format(maxDatacenterId)) //函 // |-->改成:throw new IllegalArgumentException //數(shù) // (String.format("datacenter Id can"t be greater than %d or less than 0",maxDatacenterId)) //中 } // // log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", // timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId) // // |-->改成:System.out.printf("worker...%d...",timestampLeftShift,...); // //----------------------------------------------------------------------------------------------------------------------------// //-------------------------------------------------------------------// //這個(gè)函數(shù)刪除錯(cuò)誤處理相關(guān)的代碼后,剩下一行代碼:val id = nextId() // //所以我們直接調(diào)用nextId()函數(shù)可以了,所以在“翻譯”時(shí)可以刪除這個(gè)函數(shù) // def get_id(useragent: String): Long = { // if (!validUseragent(useragent)) { // exceptionCounter.incr(1) // throw new InvalidUserAgentError //刪 } //除 // val id = nextId() // genCounter(useragent) // // reporter.report(new AuditLogEntry(id, useragent, rand.nextLong)) // id // } // //-------------------------------------------------------------------// def get_worker_id(): Long = workerId // | def get_datacenter_id(): Long = datacenterId // |<--改成Java函數(shù) def get_timestamp() = System.currentTimeMillis // | protected[snowflake] def nextId(): Long = synchronized { // 改成Java函數(shù) var timestamp = timeGen() if (timestamp < lastTimestamp) { exceptionCounter.incr(1) // 錯(cuò)誤處理相關(guān),刪 log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); // 改成System.err.printf(...) throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format( lastTimestamp - timestamp)) // 改成RumTimeException } if (lastTimestamp == timestamp) { sequence = (sequence + 1) & sequenceMask if (sequence == 0) { timestamp = tilNextMillis(lastTimestamp) } } else { sequence = 0 } lastTimestamp = timestamp ((timestamp - twepoch) << timestampLeftShift) | // |<--加上關(guān)鍵字return (datacenterId << datacenterIdShift) | // | (workerId << workerIdShift) | // | sequence // | } protected def tilNextMillis(lastTimestamp: Long): Long = { // 改成Java函數(shù) var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp // 加上關(guān)鍵字return } protected def timeGen(): Long = System.currentTimeMillis() // 改成Java函數(shù) val AgentParser = """([a-zA-Z][a-zA-Z-0-9]*)""".r // | // | def validUseragent(useragent: String): Boolean = useragent match { // |<--日志相關(guān),刪 case AgentParser(_) => true // | case _ => false // | } // | }
改出來(lái)的Java版:
public class IdWorker{ private long workerId; private long datacenterId; private long sequence; public IdWorker(long workerId, long datacenterId, long sequence){ // sanity check for workerId 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)); } System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId); this.workerId = workerId; this.datacenterId = datacenterId; this.sequence = sequence; } private long twepoch = 1288834974657L; private long workerIdBits = 5L; private long datacenterIdBits = 5L; private long maxWorkerId = -1L ^ (-1L << workerIdBits); private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); private long sequenceBits = 12L; private long workerIdShift = sequenceBits; private long datacenterIdShift = sequenceBits + workerIdBits; private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private long sequenceMask = -1L ^ (-1L << sequenceBits); private long lastTimestamp = -1L; public long getWorkerId(){ return workerId; } public long getDatacenterId(){ return datacenterId; } public long getTimestamp(){ return System.currentTimeMillis(); } public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { System.err.printf("clock is moving backwards. Rejecting requests until %d.", 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 = 0; } lastTimestamp = timestamp; return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; } private long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } private long timeGen(){ return System.currentTimeMillis(); } //---------------測(cè)試--------------- public static void main(String[] args) { IdWorker worker = new IdWorker(1,1,1); for (int i = 0; i < 30; i++) { System.out.println(worker.nextId()); } } }代碼理解
上面的代碼中,有部分位運(yùn)算的代碼,如:
sequence = (sequence + 1) & sequenceMask; private long maxWorkerId = -1L ^ (-1L << workerIdBits); return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
為了能更好理解,我對(duì)相關(guān)知識(shí)研究了一下。
負(fù)數(shù)的二進(jìn)制表示在計(jì)算機(jī)中,負(fù)數(shù)的二進(jìn)制是用補(bǔ)碼來(lái)表示的。
假設(shè)我是用Java中的int類(lèi)型來(lái)存儲(chǔ)數(shù)字的,
int類(lèi)型的大小是32個(gè)二進(jìn)制位(bit),即4個(gè)字節(jié)(byte)。(1 byte = 8 bit)
那么十進(jìn)制數(shù)字3在二進(jìn)制中的表示應(yīng)該是這樣的:
00000000 00000000 00000000 00000011 // 3的二進(jìn)制表示,就是原碼
那數(shù)字-3在二進(jìn)制中應(yīng)該如何表示?
我們可以反過(guò)來(lái)想想,因?yàn)?3+3=0,
在二進(jìn)制運(yùn)算中把-3的二進(jìn)制看成未知數(shù)x來(lái)求解,
求解算式的二進(jìn)制表示如下:
00000000 00000000 00000000 00000011 //3,原碼 + xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx //-3,補(bǔ)碼 ----------------------------------------------- 00000000 00000000 00000000 00000000
反推x的值,3的二進(jìn)制加上什么值才使結(jié)果變成00000000 00000000 00000000 00000000?:
00000000 00000000 00000000 00000011 //3,原碼 + 11111111 11111111 11111111 11111101 //-3,補(bǔ)碼 ----------------------------------------------- 1 00000000 00000000 00000000 00000000
反推的思路是3的二進(jìn)制數(shù)從最低位開(kāi)始逐位加1,使溢出的1不斷向高位溢出,直到溢出到第33位。然后由于int類(lèi)型最多只能保存32個(gè)二進(jìn)制位,所以最高位的1溢出了,剩下的32位就成了(十進(jìn)制的)0。
補(bǔ)碼的意義就是可以拿補(bǔ)碼和原碼(3的二進(jìn)制)相加,最終加出一個(gè)“溢出的0”
以上是理解的過(guò)程,實(shí)際中記住公式就很容易算出來(lái):
補(bǔ)碼 = 反碼 + 1
補(bǔ)碼 = (原碼 - 1)再取反碼
因此-1的二進(jìn)制應(yīng)該這樣算:
00000000 00000000 00000000 00000001 //原碼:1的二進(jìn)制 11111111 11111111 11111111 11111110 //取反碼:1的二進(jìn)制的反碼 11111111 11111111 11111111 11111111 //加1:-1的二進(jìn)制表示(補(bǔ)碼)用位運(yùn)算計(jì)算n個(gè)bit能表示的最大數(shù)值
比如這樣一行代碼:
private long workerIdBits = 5L; private long maxWorkerId = -1L ^ (-1L << workerIdBits);
上面代碼換成這樣看方便一點(diǎn):
long maxWorkerId = -1L ^ (-1L << 5L)
咋一看真的看不準(zhǔn)哪個(gè)部分先計(jì)算,于是查了一下Java運(yùn)算符的優(yōu)先級(jí)表:
所以上面那行代碼中,運(yùn)行順序是:
-1 左移 5,得結(jié)果a
-1 異或 a
long maxWorkerId = -1L ^ (-1L << 5L)的二進(jìn)制運(yùn)算過(guò)程如下:
-1 左移 5,得結(jié)果a :
11111111 11111111 11111111 11111111 //-1的二進(jìn)制表示(補(bǔ)碼) 11111 11111111 11111111 11111111 11100000 //高位溢出的不要,低位補(bǔ)0 11111111 11111111 11111111 11100000 //結(jié)果a
-1 異或 a :
11111111 11111111 11111111 11111111 //-1的二進(jìn)制表示(補(bǔ)碼) ^ 11111111 11111111 11111111 11100000 //兩個(gè)操作數(shù)的位中,相同則為0,不同則為1 --------------------------------------------------------------------------- 00000000 00000000 00000000 00011111 //最終結(jié)果31
最終結(jié)果是31,二進(jìn)制00000000 00000000 00000000 00011111轉(zhuǎn)十進(jìn)制可以這么算:
$$ 2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 16 + 8 + 4 + 2 + 1 =31 $$
那既然現(xiàn)在知道算出來(lái)long maxWorkerId = -1L ^ (-1L << 5L)中的maxWorkerId = 31,有什么含義?為什么要用左移5來(lái)算?如果你看過(guò)概述部分,請(qǐng)找到這段內(nèi)容看看:
5位(bit)可以表示的最大正整數(shù)是$2^{5}-1 = 31$,即可以用0、1、2、3、....31這32個(gè)數(shù)字,來(lái)表示不同的datecenterId或workerId
-1L ^ (-1L << 5L)結(jié)果是31,$2^{5}-1$的結(jié)果也是31,所以在代碼中,-1L ^ (-1L << 5L)的寫(xiě)法是利用位運(yùn)算計(jì)算出5位能表示的最大正整數(shù)是多少
用mask防止溢出有一段有趣的代碼:
sequence = (sequence + 1) & sequenceMask;
分別用不同的值測(cè)試一下,你就知道它怎么有趣了:
long seqMask = -1L ^ (-1L << 12L); //計(jì)算12位能耐存儲(chǔ)的最大正整數(shù),相當(dāng)于:2^12-1 = 4095 System.out.println("seqMask: "+seqMask); System.out.println(1L & seqMask); System.out.println(2L & seqMask); System.out.println(3L & seqMask); System.out.println(4L & seqMask); System.out.println(4095L & seqMask); System.out.println(4096L & seqMask); System.out.println(4097L & seqMask); System.out.println(4098L & seqMask); /** seqMask: 4095 1 2 3 4 4095 0 1 2 */
這段代碼通過(guò)位與運(yùn)算保證計(jì)算的結(jié)果范圍始終是 0-4095 !
用位運(yùn)算匯總結(jié)果還有另外一段詭異的代碼:
return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
為了弄清楚這段代碼,
首先 需要計(jì)算一下相關(guān)的值:
private long twepoch = 1288834974657L; //起始時(shí)間戳,用于用當(dāng)前時(shí)間戳減去這個(gè)時(shí)間戳,算出偏移量 private long workerIdBits = 5L; //workerId占用的位數(shù):5 private long datacenterIdBits = 5L; //datacenterId占用的位數(shù):5 private long maxWorkerId = -1L ^ (-1L << workerIdBits); // workerId可以使用的最大數(shù)值:31 private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // datacenterId可以使用的最大數(shù)值:31 private long sequenceBits = 12L;//序列號(hào)占用的位數(shù):12 private long workerIdShift = sequenceBits; // 12 private long datacenterIdShift = sequenceBits + workerIdBits; // 12+5 = 17 private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; // 12+5+5 = 22 private long sequenceMask = -1L ^ (-1L << sequenceBits);//4095 private long lastTimestamp = -1L;
其次 寫(xiě)個(gè)測(cè)試,把參數(shù)都寫(xiě)死,并運(yùn)行打印信息,方便后面來(lái)核對(duì)計(jì)算結(jié)果:
//---------------測(cè)試--------------- public static void main(String[] args) { long timestamp = 1505914988849L; long twepoch = 1288834974657L; long datacenterId = 17L; long workerId = 25L; long sequence = 0L; System.out.printf(" timestamp: %d ",timestamp); System.out.printf("twepoch: %d ",twepoch); System.out.printf("datacenterId: %d ",datacenterId); System.out.printf("workerId: %d ",workerId); System.out.printf("sequence: %d ",sequence); System.out.println(); System.out.printf("(timestamp - twepoch): %d ",(timestamp - twepoch)); System.out.printf("((timestamp - twepoch) << 22L): %d ",((timestamp - twepoch) << 22L)); System.out.printf("(datacenterId << 17L): %d " ,(datacenterId << 17L)); System.out.printf("(workerId << 12L): %d ",(workerId << 12L)); System.out.printf("sequence: %d ",sequence); long result = ((timestamp - twepoch) << 22L) | (datacenterId << 17L) | (workerId << 12L) | sequence; System.out.println(result); } /** 打印信息: timestamp: 1505914988849 twepoch: 1288834974657 datacenterId: 17 workerId: 25 sequence: 0 (timestamp - twepoch): 217080014192 ((timestamp - twepoch) << 22L): 910499571845562368 (datacenterId << 17L): 2228224 (workerId << 12L): 102400 sequence: 0 910499571847892992 */
代入位移的值得之后,就是這樣:
return ((timestamp - 1288834974657) << 22) | (datacenterId << 17) | (workerId << 12) | sequence;
對(duì)于尚未知道的值,我們可以先看看概述 中對(duì)SnowFlake結(jié)構(gòu)的解釋?zhuān)俅朐诤戏ǚ秶闹?windows系統(tǒng)可以用計(jì)算器方便計(jì)算這些值的二進(jìn)制),來(lái)了解計(jì)算的過(guò)程。
當(dāng)然,由于我的測(cè)試代碼已經(jīng)把這些值寫(xiě)死了,那直接用這些值來(lái)手工驗(yàn)證計(jì)算結(jié)果即可:
long timestamp = 1505914988849L; long twepoch = 1288834974657L; long datacenterId = 17L; long workerId = 25L; long sequence = 0L;
設(shè):timestamp = 1505914988849,twepoch = 1288834974657 1505914988849 - 1288834974657 = 217080014192 (timestamp相對(duì)于起始時(shí)間的毫秒偏移量),其(a)二進(jìn)制左移22位計(jì)算過(guò)程如下: |<--這里開(kāi)始左右22位 ? 00000000 00000000 000000|00 00110010 10001010 11111010 00100101 01110000 // a = 217080014192 00001100 10100010 10111110 10001001 01011100 00|000000 00000000 00000000 // a左移22位后的值(la) |<--這里后面的位補(bǔ)0
設(shè):datacenterId = 17,其(b)二進(jìn)制左移17位計(jì)算過(guò)程如下: |<--這里開(kāi)始左移17位 00000000 00000000 0|0000000 ?00000000 00000000 00000000 00000000 00010001 // b = 17 0000000?0 00000000 00000000 00000000 00000000 0010001|0 00000000 00000000 // b左移17位后的值(lb) |<--這里后面的位補(bǔ)0
設(shè):workerId = 25,其(c)二進(jìn)制左移12位計(jì)算過(guò)程如下: |<--這里開(kāi)始左移12位 ?00000000 0000|0000 00000000 00000000 00000000 00000000 00000000 00011001? // c = 25 00000000 00000000 00000000 00000000 00000000 00000001 1001|0000 00000000? // c左移12位后的值(lc) |<--這里后面的位補(bǔ)0
設(shè):sequence = 0,其二進(jìn)制如下: 00000000 00000000 00000000 00000000 00000000 00000000 0000?0000 00000000? // sequence = 0
現(xiàn)在知道了每個(gè)部分左移后的值(la,lb,lc),代碼可以簡(jiǎn)化成下面這樣去理解:
return ((timestamp - 1288834974657) << 22) | (datacenterId << 17) | (workerId << 12) | sequence; ----------------------------- | |簡(jiǎn)化 |/ ----------------------------- return (la) | (lb) | (lc) | sequence;
上面的管道符號(hào)|在Java中也是一個(gè)位運(yùn)算符。其含義是:
x的第n位和y的第n位 只要有一個(gè)是1,則結(jié)果的第n位也為1,否則為0,因此,我們對(duì)四個(gè)數(shù)的位或運(yùn)算如下:
1 | 41 | 5 | 5 | 12 0|0001100 10100010 10111110 10001001 01011100 00|00000|0 0000|0000 00000000 //la 0|000000?0 00000000 00000000 00000000 00000000 00|10001|0 0000|0000 00000000 //lb 0|0000000 00000000 00000000 00000000 00000000 00|00000|1 1001|0000 00000000 //lc or 0|0000000 00000000 00000000 00000000 00000000 00|00000|0 0000|?0000 00000000? //sequence ------------------------------------------------------------------------------------------ 0|0001100 10100010 10111110 10001001 01011100 00|10001|1 1001|?0000 00000000? //結(jié)果:910499571847892992
結(jié)果計(jì)算過(guò)程:
1) 從至左列出1出現(xiàn)的下標(biāo)(從0開(kāi)始算):
0000 1 1 00 1 0 1 000 1 0 1 0 1 1 1 1 1 0 1 000 1 00 1 0 1 0 1 1 1 0000 1 000 1 1 1 00 1? 0000 0000 0000 59 58 55 53 49 47 45 44 43 42 41 39 35 32 30 28 27 26 21 17 16 15 12
2) 各個(gè)下標(biāo)作為2的冪數(shù)來(lái)計(jì)算,并相加:
$ 2^{59}+2^{58}+2^{55}+2^{53}+2^{49}+2^{47}+2^{45}+2^{44}+2^{43}+
2^{42}+2^{41}+2^{39}+2^{35}+2^{32}+2^{30}+2^{28}+2^{27}+2^{26}+
2^{21}+2^{17}+2^{16}+2^{15}+2^{2} $
2^59} : 576460752303423488 2^58} : 288230376151711744 2^55} : 36028797018963968 2^53} : 9007199254740992 2^49} : 562949953421312 2^47} : 140737488355328 2^45} : 35184372088832 2^44} : 17592186044416 2^43} : 8796093022208 2^42} : 4398046511104 2^41} : 2199023255552 2^39} : 549755813888 2^35} : 34359738368 2^32} : 4294967296 2^30} : 1073741824 2^28} : 268435456 2^27} : 134217728 2^26} : 67108864 2^21} : 2097152 2^17} : 131072 2^16} : 65536 2^15} : 32768 + 2^12} : 4096 ---------------------------------------- 910499571847892992
計(jì)算截圖:
跟測(cè)試程序打印出來(lái)的結(jié)果一樣,手工驗(yàn)證完畢!
觀察1 | 41 | 5 | 5 | 12 0|0001100 10100010 10111110 10001001 01011100 00| | | //la 0| |10001| | //lb 0| | |1 1001| //lc or 0| | | |?0000 00000000? //sequence ------------------------------------------------------------------------------------------ 0|0001100 10100010 10111110 10001001 01011100 00|10001|1 1001|?0000 00000000? //結(jié)果:910499571847892992
上面的64位我按1、41、5、5、12的位數(shù)截開(kāi)了,方便觀察。
縱向觀察發(fā)現(xiàn):
在41位那一段,除了la一行有值,其它行(lb、lc、sequence)都是0,(我爸其它)
在左起第一個(gè)5位那一段,除了lb一行有值,其它行都是0
在左起第二個(gè)5位那一段,除了lc一行有值,其它行都是0
按照這規(guī)律,如果sequence是0以外的其它值,12位那段也會(huì)有值的,其它行都是0
橫向觀察發(fā)現(xiàn):
在la行,由于左移了5+5+12位,5、5、12這三段都補(bǔ)0了,所以la行除了41那段外,其它肯定都是0
同理,lb、lc、sequnece行也以此類(lèi)推
正因?yàn)樽笠频牟僮?,使四個(gè)不同的值移到了SnowFlake理論上相應(yīng)的位置,然后四行做位或運(yùn)算(只要有1結(jié)果就是1),就把4段的二進(jìn)制數(shù)合并成一個(gè)二進(jìn)制數(shù)。
結(jié)論:
所以,在這段代碼中
return ((timestamp - 1288834974657) << 22) | (datacenterId << 17) | (workerId << 12) | sequence;
左移運(yùn)算是為了將數(shù)值移動(dòng)到對(duì)應(yīng)的段(41、5、5,12那段因?yàn)楸緛?lái)就在最右,因此不用左移)。
然后對(duì)每個(gè)左移后的值(la、lb、lc、sequence)做位或運(yùn)算,是為了把各個(gè)短的數(shù)據(jù)合并起來(lái),合并成一個(gè)二進(jìn)制數(shù)。
最后轉(zhuǎn)換成10進(jìn)制,就是最終生成的id
擴(kuò)展在理解了這個(gè)算法之后,其實(shí)還有一些擴(kuò)展的事情可以做:
根據(jù)自己業(yè)務(wù)修改每個(gè)位段存儲(chǔ)的信息。算法是通用的,可以根據(jù)自己需求適當(dāng)調(diào)整每段的大小以及存儲(chǔ)的信息。
解密id,由于id的每段都保存了特定的信息,所以拿到一個(gè)id,應(yīng)該可以嘗試反推出原始的每個(gè)段的信息。反推出的信息可以幫助我們分析。比如作為訂單,可以知道該訂單的生成日期,負(fù)責(zé)處理的數(shù)據(jù)中心等等。
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/70491.html
摘要:所以就誕生了這個(gè)項(xiàng)目,以下為線(xiàn)程安全版本和非線(xiàn)程安全版本差別。非線(xiàn)程安全版本線(xiàn)程安全版本安裝示例注意區(qū)間在超出范圍將會(huì)報(bào)告一個(gè)致命錯(cuò)誤協(xié)議版權(quán)歸屬于請(qǐng)遵守協(xié)議 php_snowflake 項(xiàng)目地址 什么是 php_snowflake? 推特分布式id生成算法SnowFlake PHP 的實(shí)現(xiàn) 需求 PHP >= 5.6 (5.5以下的自行測(cè)試) 不支持windows 說(shuō)明 純PH...
摘要:原理的雪花算法,使用語(yǔ)言實(shí)現(xiàn)。生成的整體上按照時(shí)間自增排序,并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生碰撞由和作區(qū)分,并且效率較高。據(jù)說(shuō)每秒能夠產(chǎn)生萬(wàn)個(gè)。 分布式系統(tǒng)中,有一些需要使用全局唯一ID的場(chǎng)景,這種時(shí)候?yàn)榱朔乐笽D沖突可以使用36位的UUID,但是UUID有一些缺點(diǎn),首先他相對(duì)比較長(zhǎng),另外UUID一般是無(wú)序的。 有些時(shí)候我們希望能使用一種簡(jiǎn)單一些的ID,并且希望ID能夠按照時(shí)間有序生成。 ...
摘要:序本文主要來(lái)聊聊分布式的生成方案。分布式的生成,以為代表的,系列算法采用的就是劃分命名空間并行生成的思路。 序 本文主要來(lái)聊聊分布式id的生成方案。 目標(biāo) 業(yè)務(wù)系統(tǒng)需要什么樣的ID生成器中提出了幾點(diǎn)目標(biāo): 唯一性 時(shí)間相關(guān) 粗略有序 可反解 可制造 主要思路 對(duì)于每個(gè)標(biāo)識(shí),都需要有一個(gè)命名空間(namespace),來(lái)保證其相對(duì)唯一性。分布式的ID生成,以Twitter Snowf...
摘要:有些時(shí)候我們希望能使用一種簡(jiǎn)單一些的,并且希望能夠按照時(shí)間有序生成。轉(zhuǎn)換成字符串后長(zhǎng)度最多生成的整體上按照時(shí)間自增排序,并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生碰撞由和作區(qū)分,并且效率較高。經(jīng)測(cè)試每秒能夠產(chǎn)生萬(wàn)個(gè)。 概述 分布式系統(tǒng)中,有一些需要使用全局唯一ID的場(chǎng)景,這種時(shí)候?yàn)榱朔乐笽D沖突可以使用36位的UUID,但是UUID有一些缺點(diǎn),首先他相對(duì)比較長(zhǎng),另外UUID一般是無(wú)序的。 有些時(shí)候我...
閱讀 1682·2019-08-30 15:54
閱讀 3332·2019-08-26 17:15
閱讀 3522·2019-08-26 13:49
閱讀 2582·2019-08-26 13:38
閱讀 2291·2019-08-26 12:08
閱讀 3035·2019-08-26 10:41
閱讀 1368·2019-08-26 10:24
閱讀 3376·2019-08-23 18:35