twitter是什么意思

分布式场景ID⽣成算法--Twitter的SnowFlake雪花算法

分布式场景ID⽣成算法--Twitter的SnowFlake雪花算法

⼀、Twitter的雪花算法—SnowFlake

ake算法背景

Twitter-Snowflake算法产⽣的背景相当简单，为了满⾜Twitter每秒上万条消息的请求，每条消息都必须分配⼀条唯⼀的id，这些id还需要

⼀些⼤致的顺序（⽅便客户端排序），并且在分布式系统中不同机器产⽣的id必须不同。

rSnowflake算法的应⽤

TwitterSnowflake算法是⽤来在分布式场景下⽣成唯⼀ID的。

举个栗⼦：我们有10台分布式MySql服务器，我们的系统每秒能⽣成10W条数据插⼊到这10台机器⾥，现在我们需要为每⼀条数据⽣成⼀

个全局唯⼀的ID，并且这些ID有⼤致的顺序。

结构

SnowFlake算法核⼼：把时间戳，⼯作机器id，序列号组合在⼀起。

SnowFlake算法⽣成id的结果是⼀个64bit⼤⼩的整数，它的结构如下图：

如图：最后⽣成的ID是⼀个long类型，long占64bit，符号位占1位，剩下63位，我们将这63位拆分成4段，就可以表⽰：某⼀毫秒内的某

⼀集群内的某⼀机器的第⼏个ID。

可以分成5部分：1位+41位+10位+12位。

1位，未使⽤，固定为0。⼆进制中最⾼位为1表⽰负数，但是⽣成的id⼀般都使⽤正整数，所以这个最⾼位固定是0；正好作为64位id的最

⾼位，为0，即long类型值为正数；

41位，⽤来记录时间戳（毫秒）;41位表⽰的数字范围可以使⽤69年，也就是说41位可以表⽰毫秒值，转化成单位年则是69年；

10位，⽤来记录节点id；最多⽀持部署1024个节点，（节点⼀般是由5位数据中⼼编号datacenterId和5位机器编号workerId组成）；

5位（bit）可以表⽰的最⼤正整数是31，即可以⽤0、1、2、3、....31这32个数字，来表⽰不同的datecenterId或workerId；

12位，序列号，⽤来记录同毫秒内产⽣的不同id，意味着每个节点每毫秒可以产⽣4096个ID序号。

12位（bit）可以表⽰的最⼤正整数是，即可以⽤0、1、2、3、....4095这4096个数字，来表⽰同⼀机器同⼀时间截（毫秒)内产⽣的

4095个ID序号。

在上⾯的字符串中，第⼀位为未使⽤（实际上也可作为long的符号位），接下来的41位为毫秒级时间，然后5位datacenter标识位，5位机

器ID（并不算标识符，实际是为线程标识），然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为⼀个Long型。

这样的好处是，整体上按照时间⾃增排序，并且整个分布式系统内不会产⽣ID碰撞（由datacenter和机器ID作区分），并且效率较⾼，经测

试，snowflake每秒能够产⽣26万ID左右，完全满⾜需要。

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法⽣成的id就是long来存储的。

ake可以保证：

所有⽣成的id按时间趋势递增；

整个分布式系统内不会产⽣重复id（因为有datacenterId和workerId来做区分）；

⽣成策略

*毫秒级时间41位+机器ID10位+毫秒内序列12位。

*0415164

+-----------+------+------+

|time|pc|q|

+-----------+------+------+

*最⾼位bit标记为不可⽤

*前41bits是以微秒为单位的timestamp。

*接着10bits是事先配置好的机器ID。

*最后12bits是累加计数器。

*macheineid(10bits)标明最多只能有1024台机器同时产⽣ID，quencenumber(12bits)也标明1台机器1ms中最多产⽣4096个

ID。

6.问题：Q&A

问题1：有⼈会问：为什么时间戳要占41位？quence要占12位？⽽其他两个要各占5位？

答：这是根据具体需求来分的，你也可以⾃⼰再去将这63为重新拆分。例如：quence占12位就可以在同⼀毫秒内的同⼀集群的同⼀机

器上同时有2^12-1个线程。

2.问题2：twepoch为什么要等于57L⽽不等于其他数？

答：57是(Thu,04Nov201001:42:54GMT)这⼀时刻到1970-01-0100:00:00时刻所经过的毫秒数。当前时刻

减去57的值刚好在2^41⾥，因此占41位。所以这个数是为了让时间戳占41位才特地算出来的。

问题3：类似这种longmaxWorkerId=-1L^(-1L<

答：-1L^(-1L<

注意：计算机存放数字都是存放数字的补码，正数的原码、补码、反码都⼀样，负数的补码是其反码加⼀。符号位做取反操作时不变，做逻

辑与、或、⾮、异或操作时要参与运算。

再来个栗⼦：

-1L原码:10000001

-1L反码:11111110

-1L补码:11111111

-1L<<5:11100000

11111111^11100000:00011111

00011111是正数，所以补码、反码、原码都⼀样，所以00011111是31

4.问题4：((timestamp-twepoch)<

quence是什么意思？

答：我只发图不说话

7.扩展

在理解了这个算法之后，其实还有⼀些扩展的事情可以做：

根据⾃⼰业务修改每个位段存储的信息。算法是通⽤的，可以根据⾃⼰需求适当调整每段的⼤⼩以及存储的信息。

解密id，由于id的每段都保存了特定的信息，所以拿到⼀个id，应该可以尝试反推出原始的每个段的信息。反推出的信息可以帮助我们分

析。⽐如作为订单，可以知道该订单的⽣成⽇期，负责处理的数据中⼼等等。

8.重要代码解析

使⽤mask的⽬的是：防⽌溢出。

quence=(quence+1)&quenceMask;//防⽌溢出

privatelongmaxWorkerId=-1L^(-1L<

return((timestamp-twepoch)<

(datacenterId<

(workerId<

quence;//利⽤左移运算得到最终的ID

负数的补码：⽅法1：补码=反码+1；<反码=补码-1>

⽅法2：补码=（原码-1）再取反码。

ake算法的Java代码

publicclassSnowFlakeAlgorithm{

/**

*Twitter的雪花算法SnowFlake

*DateTime:2018-12-1822:23:00

*1bit+41bit+5bit+5bit+12bit

*

*时间戳(毫秒数)是根据当前时间获取的，datacenterId和workerId都是节点固定的值，

*因此，只需要确定quence即可。

*这⾥最重要的就是序列号quence的⽣成：需要判断是否为同⼀毫秒内；

*（1）、若为同⼀毫秒，则quence加⼀即可，若溢出(变为0)，需要等待下⼀毫秒的到来；

*（2）、若不为同⼀毫秒，quence置0即可。

*

*代码实现原理：

*ID由四部分组成，确定四部分即可。

*⾸先定义各个部分占⽤的⽐特位数和组合时需要左移的位数；

*核⼼⽅法:nextId

*/

privatelongtwepoch=57L;

privatelongworkerIdBits=5L;//机器编号5位

privatelongdatacenterIdBits=5L;//数据中⼼编号5位

privatelongmaxWorkerId=-1L^(-1L<

privatelongmaxDatacenterId=-1L^(-1L<

//需要左移的位数

privatelongquenceBits=12L;//序列号12位

privatelongworkerIdShift=quenceBits;

privatelongdatacenterIdShift=quenceBits+workerIdBits;

privatelongtimestampLeftShift=quenceBits+workerIdBits+datacenterIdBits;

//序列号

privatelongquenceMask=-1L^(-1L<

//4部分：41bit+5bit+5bit+12bit

privatelonglastTimestamp=-1L;

privatelongworkerId;//机器编号

privatelongdatacenterId;//数据中⼼编号

privatelongquence;//序列号

/**

*构造⽅法

*

*@paramworkerId

*@paramdatacenterId

*@paramquence

*/

publicSnowFlakeAlgorithm(longworkerId,longdatacenterId,longquence){

//sanitycheckforworkerId

if(workerId>maxWorkerId||workerId<0){

thrownewIllegalArgumentException(("workerIdcan'tbegreaterthan%dorlessthan0",

maxWorkerId));

}

if(datacenterId>maxDatacenterId||datacenterId<0){

thrownewIllegalArgumentException(("datacenterIdcan'tbegreaterthan%dorlessthan0",

maxDatacenterId));

}

("ampleftshift%d,datacenteridbits%d,workeridbits%d,quencebits%d,

workerid%d.",

timestampLeftShift,datacenterIdBits,workerIdBits,quenceBits,workerId);

n();//换⾏

Id=workerId;

nterId=datacenterId;

ce=quence;

}

/**

*核⼼⽅法：获取下⼀个Id

*

*@returnId

*/

publicsynchronizedlongnextId(){

longtimestamp=timeGen();

if(timestamp

("ingrequestsuntil%d.",lastTimestamp);

thrownewRuntimeException(("ngtogenerateidfor%dmilliconds",

lastTimestamp-timestamp));

}

if(lastTimestamp==timestamp){//同⼀个毫秒内，利⽤序列号区别

quence=(quence+1)&quenceMask;//防⽌溢出

if(quence==0){

timestamp=tilNextMillis(lastTimestamp);

}

}el{//不是⼀个毫秒数，则序列号置0

quence=0;

}

lastTimestamp=timestamp;//更新上⼀个时间戳

return((timestamp-twepoch)<

(datacenterId<

(workerId<

quence;//利⽤左移运算得到最终的ID

}

/**

*直到下⼀毫秒到来

*通过while循环实现

*@paramlastTimestamp

*@return

*/

privatelongtilNextMillis(longlastTimestamp){

longtimestamp=timeGen();

while(timestamp<=lastTimestamp){//确保下⼀毫秒的到来

timestamp=timeGen();

}

returntimestamp;

}

privatelongtimeGen(){

tTimeMillis();//当前系统的毫秒值

}

//---------------测试---------------

publicstaticvoidmain(String[]args){

SnowFlakeAlgorithmsnowFlake=newSnowFlakeAlgorithm(1,1,1);

for(inti=0;i<30;i++){

n(());

}

}

}

结果：

ampleftshift22,datacenteridbits5,workeridbits5,quencebits12,workerid1.

1647040

1647041

1647042

1647043

1647044

1647045

1647046

1647047

1647048

1647049

1647050

1647051

1647052

1647053

1647054

1647055

1647056

1647057

1647058

1647059

1647060

1647061

1647062

1647063

1647064

1647065

1647066

1647067

1647068

1647069

Processfinishedwithexitcode0