分布式ID系列(5)——Twitter的雪法算法Snowflake适合做分布式ID吗

介绍Snowflake算法

SnowFlake算法是国际大公司Twitter的采用的一种生成分布式自增id的策略,这个算法产生的分布式id是足够我们我们中小公司在日常里面的使用了。我也是比较推荐这一种算法产生的分布式id的。

算法snowflake的生成的分布式id结构组成部分

算法snowflake生成id的结果是一个64bit大小的整数,它的结构如下图,

分布式ID系列(5)——Twitter的雪法算法Snowflake适合做分布式ID吗

这里我么来讲一下这个结构:首先因为window是64位的,然后整数的时候第一位必须是0,所以最大的数值就是63位的111111111111111111111111111111111111111111111111111111111111111,然后呢Snowflake算法分出来41位作为毫秒值,然后10位作为redis节点的数量,然后12位做成redis节点在每一毫秒的自增序列值

41位的二进制11111111111111111111111111111111111111111转换成10进制的毫秒就是2199023255551,然后我们把 2199023255551转换成时间就是2039-09-07,也就是说可以用20年的(这里在网上会有很多说是可以使用69年的,他们说69年的也对,因为1970年+69年的结果就是2039年,但是如果从今年2019年来说,也就只能用20年了)

然后10位作为节点,所以最多就是12位的1111111111,也就是最多可以支持1023个节点,

然后10位表示每一个节点自增序列值,这里最多就是10位的111111111111,也就是说每一个节点可以每一毫秒可以最多生成4059个不重复id值

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

Java实现Snowflake算法的源码

Snowflake算法的源码如下所示(这个是我从网上找到的),这里我进行了测试了一波,结果如下所示

package com.hello; import java.text.SimpleDateFormat; import java.util.Date; public class Test { /** * 开始时间截 (1970-01-01) */ private final long twepoch = 0L; /** * 机器id所占的位数 */ private final long workerIdBits = 5L; /** * 数据标识id所占的位数 */ private final long datacenterIdBits = 5L; /** * 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */ private final long maxWorkerId = -1L ^ (-1L << workerIdBits); /** * 支持的最大数据标识id,结果是31 */ private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); /** * 序列在id中占的位数 */ private final long sequenceBits = 12L; /** * 机器ID向左移12位 */ private final long workerIdShift = sequenceBits; /** * 数据标识id向左移17位(12+5) */ private final long datacenterIdShift = sequenceBits + workerIdBits; /** * 时间截向左移22位(5+5+12) */ private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; /** * 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */ private final long sequenceMask = -1L ^ (-1L << sequenceBits); /** * 工作机器ID(0~31) */ private long workerId; /** * 数据中心ID(0~31) */ private long datacenterId; /** * 毫秒内序列(0~4095) */ private long sequence = 0L; /** * 上次生成ID的时间截 */ private long lastTimestamp = -1L; public Test(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 SnowflakeId */ public synchronized long nextId() { long timestamp = timeGen(); //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常 if (timestamp < 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 = 0L; } //上次生成ID的时间截 lastTimestamp = timestamp; //移位并通过或运算拼到一起组成64位的ID return ((timestamp - twepoch) << timestampLeftShift) // | (datacenterId << datacenterIdShift) // | (workerId << workerIdShift) // | sequence; } /** * 阻塞到下一个毫秒,直到获得新的时间戳 * * @param lastTimestamp 上次生成ID的时间截 * @return 当前时间戳 */ protected long tilNextMillis(long lastTimestamp) { long timestamp = timeGen(); while (timestamp <= lastTimestamp) { timestamp = timeGen(); } return timestamp; } /** * 返回以毫秒为单位的当前时间 * * @return 当前时间(毫秒) */ protected long timeGen() { return System.currentTimeMillis(); } public static void parseId(long id) { long miliSecond = id >>> 22; long shardId = (id & (0xFFF << 10)) >> 10; System.err.println("分布式id-"+id+"生成的时间是:"+new SimpleDateFormat("yyyy-MM-dd").format(new Date(miliSecond))); } public static void main(String[] args) { Test idWorker = new Test(0, 0); for (int i = 0; i < 10; i++) { long id = idWorker.nextId(); System.out.println(id); parseId(id); } } }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjjyx.html