理解分布式id生成算法--雪花算法（SnowFlake）

分布式ID生成算法的有很多种，Twitter的SnowFlake就是其中经典的一种。

注：

1B就是1个字节。

Byte、KB、B、MB、GB之间的关系是：

Bit——比特 ； B ——字节；KB——千字节；MB——兆字节；GB——吉字节；TB——太字节

1bit=0.125b；1B=8 Bit ；1KB＝1024B 1MB＝1024KB；1GB＝1024MB；1TB=1024GB

1位，不用。二进制中最高位为1的都是负数，但是我们生成的ID一般都使用整数，所以这个最高位固定是0.

41位，用来记录时间戳（毫秒）

41位可以表示正整数（计算机中整数包含0），可以表示的数值范围是：0至$2^{41}-1$,

减1是因为可表示的的数值范围是从0开始算的，而不是1.

也就是说41位可以表示$2^{41}-1$个毫秒的值，转化成单位年则是$2^({41}-1)/(1000*60*60*24*365)=69$年

10位,用来记录工作机器ID。

可以部署在$2^{10}=1024$个字节。包括5位datacenterId和5位workerId。

5位（bit）可以表示的最大正整数是$2^{5}-1=31$,即可以用0,1,2,3....31这32个数字，来表示不同的datacenterId

或者workerId.

12位，序列号，用来记录同毫秒内产生的不同Id。

12位（bit）可以表示的最大整数是$2^{12}-1=4095$,即可以用0、1、2、3....4094这4095个数字，来表示同一机器

同一时间戳（毫秒）内产生的4095个ID序号。

由于在java中64bit的整数是long类型，所以在java中SnowFlake算法生产的ID就是longKauai存储的，

SnowFlake可以保证：

所有生成ID按时间趋势递增。

整个分布式系统内不会产生重复ID（因为datacenterID和wokerID来做区分）

java代码工具类：

package suanfa;

/**

* ### 雪花算法：

SnowFlake算法用来生成64位的ID，刚好可以用long整型存储，能够用于分布式系统中生产唯一的ID， 并且生成的ID有大致的顺序。 在这次实现中，生成的64位ID可以分成5个部分：

`0 - 41位时间戳 - 5位数据中心标识 - 5位机器标识 - 12位序列号`

````java

* twitter的snowflake算法 -- java实现

*

* @author beyond

* @date /11/26

*/

public class SnowFlake {

/**

* 起始的时间戳

*/

private final static long START_STMP = 1480166465631L;

/**

* 每一部分占用的位数

*/

private final static long SEQUENCE_BIT = 12; //序列号占用的位数

private final static long MACHINE_BIT = 5; //机器标识占用的位数

private final static long DATACENTER_BIT = 5;//数据中心占用的位数

/**

* 每一部分的最大值

*/

//最大支持数据中心节点数0~31，一共32个

private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);

//最大支持机器节点数0~31，一共32个

private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);

//序列号0~12,一共12个

private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

/**

* 每一部分向左的位移

*/

//机器节点左移12位

private final static long MACHINE_LEFT = SEQUENCE_BIT;

//数据中心节点左移17位

private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;

//时间毫秒数左移22位

private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

private long datacenterId; //数据中心

private long machineId; //机器标识

private long sequence = 0L; //序列号

private long lastStmp = -1L;//上一次时间戳 //最大为4095

public SnowFlake(long datacenterId, long machineId) {

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

throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");

}

if (machineId > MAX_MACHINE_NUM || machineId < 0) {

throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");

}

this.datacenterId = datacenterId;

this.machineId = machineId;

}

/**

* 产生下一个ID

*

* @return

*/

public synchronized long nextId() {

long currStmp = getNewstmp();

if (currStmp < lastStmp) {

throw new RuntimeException("Clock moved backwards. Refusing to generate id");

}

if (currStmp == lastStmp) {

//相同毫秒内，序列号自增

sequence = (sequence + 1) & MAX_SEQUENCE;

//同一毫秒的序列数已经达到最大

if (sequence == 0L) {

currStmp = getNextMill();

}

} else {

//不同毫秒内，序列号置为0

sequence = 0L;

}

lastStmp = currStmp;

return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分

| datacenterId << DATACENTER_LEFT //数据中心部分

| machineId << MACHINE_LEFT //机器标识部分

| sequence; //序列号部分

}

private long getNextMill() {

long mill = getNewstmp();

while (mill <= lastStmp) {

mill = getNewstmp();

}

return mill;

}

private long getNewstmp() {

return System.currentTimeMillis();

}

public static void main(String[] args) {

//数据中心id,机器标识id

SnowFlake snowFlake = new SnowFlake(2, 3);

System.out.println(snowFlake.nextId());

}

}