雪花算法java代码,雪花算法源码

雪花算法（SnowFlake）

解决方法：

目前成都创新互联公司已为上千余家的企业提供了网站建设、域名、网页空间、网站托管维护、企业网站设计、绥德网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

首先，SnowFlake的末尾12位是序列号，用来记录同一毫秒内产生的不同id，同一毫秒总共可以产生4096个id，每一毫秒的序列号都是从0这个基础序列号开始递增。假设我们的业务系统在单机上的QPS为3w/s，那么其实平均每毫秒只需要产生30个id即可，远没有达到设计的4096，也就是说通常情况下序列号的使用都是处在一个低水位，当发生时钟回拨的时候，这些尚未被使用的序号就可以派上用场了。

因此，可以对给定的基础序列号稍加修改，后面每发生一次时钟回拨就将基础序列号加上指定的步长，例如开始时是从0递增，发生一次时钟回拨后从1024开始递增，再发生一次时钟回拨则从2048递增，这样还能够满足3次的时钟回拨到同一时间点。

改变原来的末尾sequence生成方法：

snowflake算法给workerId预留了10位，即workId的取值范围为[0, 1023]，事实上实际生产环境不大可能需要部署1024个分布式ID服务，所以：将workerId取值范围缩小为[0, 511]，[512, 1023]这个范围的workerId当做备用workerId。workId为0的备用workerId是512，workId为1的备用workerId是513，以此类推……

如何保证数据库集群中id的唯一性，假设每秒钟并发20万次

用雪花算法的工具类,1秒内可以生成26万不重复的值,数据库的主键不要自增,手动设置

package entity;

import java.lang.management.ManagementFactory;

import java.net.InetAddress;

import java.net.NetworkInterface;

/**

* 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;

}

public static void main(String[] args) {

//推特  26万个不重复的ID

IdWorker idWorker = new IdWorker(0,0);

for (int i = 0; i 2600 ; i++) {

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

}

}

}

雪花算法源码

(1)开源ID:Twitter开源开源的分布式ID生成算法

(2)64 bit自增:使用一个64位的long型数字作为一个全局ID,且引入了时间戳概念,基本上保证自增的

(3)64位中,第一位是不用的,其中的41位作为毫秒数,10位(5+5)作为机房机器id,剩下的12位作为序列号

第一个部分，是 1 个 bit: 如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。

第二个部分是 41 个 bit: 表示的是时间戳。41 bit 可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。

第三个部分是 5 个 bit: 表示的是机房 id，10001。

第四个部分是 5 个 bit: 表示的是机器 id，11001。部署在 2^10 台机器上，也就是 1024 台机器。

第五个部分是 12 个 bit: 表示的序号，就是某个机房某台机器上这一毫秒内同时生成的 id 的序号，0000 0000 0000。记录同一个毫秒内产生的不同 id

(1)请求:某个微服务service需要生成一个全局唯一Id,那就可以给部署了snokeFlake算法的系统发送一个请求来生成唯一Id

(2)二进制生成:接着会用"二进制位运算"来生成一个64位的long型id,并且64位第一个bit无意义,算法系统当然知道当前的时间戳,自己的机房和机器

(3)毫秒内累加序号:最后在判断下这是这个毫秒下的第几个请求,给这次生成的Id的请求累加一个序号,作为最后的12个bit

(4)算法保证唯一:在同一毫秒下,同一个机房下的一台机器,生成一个唯一的id(12位=4096个), 如果一毫秒生成的Id数量超过了4095,就知会等待下一个毫秒在生成!但是估计没有请求能有这么频繁!