文档章节

Twitter的分布式自增ID算法snowflake (Java版)

满风
 满风
发布于 2017/09/05 11:14
字数 1023
阅读 113
收藏 1
/**
 * Twitter的分布式自增ID算法snowflake (Java版)
 * (分布式唯一ID生成器)
 *
 * @author dy
 *         JDK-version:  JDK1.7
 *         Twitter_Snowflake<br>
 *         SnowFlake的结构如下(每部分用-分开):<br>
 *         0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 *         1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
 *         41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
 *         得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 *         10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 *         12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 *         加起来刚好64位,为一个Long型。<br>
 *         SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 **/

public class SnowflakeIdWorker {

    /**
     * 开始时间截 (2015-01-01)
     */
    private final long twepoch = 1420041600000L;

    /**
     * 机器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;


    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(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 main(String[] args) {
        long start = System.currentTimeMillis();
        int count = 100000;
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < count; i++) {
            long id = idWorker.nextId();
//            System.out.println(Long.toBinaryString(id));
            System.out.println("ID = "+id);
        }
        System.out.println("it takes :"+(System.currentTimeMillis()-start) +" ms");
    }
}

© 著作权归作者所有

共有 人打赏支持
满风

满风

粉丝 85
博文 166
码字总数 175990
作品 0
杭州
技术主管
【死磕Sharding-jdbc】—–分布式ID

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7f0661ddd6dd 实现动机 传统数据库软件开发中,主键自动生成技术是基本需求。而各大数据库对于该需求也提供了相应的支持,比如M...

飞哥-Javaer
05/05
0
0
Twitter的分布式雪花算法 SnowFlake

原理 Twitter的雪花算法SnowFlake,使用Java语言实现。 SnowFlake算法产生的ID是一个64位的整型,结构如下(每一部分用“-”符号分隔): 1位标识部分,在java中由于long的最高位是符号位,正...

asdf08442a
03/14
0
0
Twitter的分布式自增ID算法snowflake(Java版)

概述 分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。 有些时候我们希望能使用一...

月下狼
08/08
0
0
雪花算法(Snowflake)C#版本 压测Id重复严重

不建议在生产环境中使用,压测重复id严重 不建议在生产环境中使用,压测重复id严重 不建议在生产环境中使用,压测重复id严重 压测工具 Jmeter 大名鼎鼎的 雪花算法 Twitter's Snowflake我就不...

123!
08/02
0
0
MySQL多数据源笔记5-ShardingJDBC实战

Sharding-JDBC集分库分表、读写分离、分布式主键、柔性事务和数据治理与一身,提供一站式的解决分布式关系型数据库的解决方案。 从2.x版本开始,Sharding-JDBC正式将包名、Maven坐标、码云仓...

狂小白
03/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SAP不同的产品是如何支持用户创建自定义字段的

我们从SAP CRM,Cloud for Customer(简称C4C)和S/4HANA这三个产品分别来看看。 SAP CRM 我们使用所谓的Application Enhancement Tool(AET)来创建扩展字段。首先在Personalize里将Configu...

JerryWang_SAP
22分钟前
3
0
Vue-Element-Upload

记录一下文件上传封装Js 代码示例 封装:uploadFile.vue <template> <el-upload v-model="attachment" ref="upload" class="upload-demo" :action="uploadUrl" ......

华山猛男
29分钟前
2
0
AWVS破解及使用手册

1.安装 因为是windows软件,比较简单,此部分略: 破解插件下载: 链接: https://pan.baidu.com/s/1x9LK9F3KvqDgTvXDjoSZnQ 提取码: 7k4u 2.创建扫描目标 2-1.Targets->Add Target 2-2.对话框...

硅谷课堂
31分钟前
1
0
Centos 7 安装Zabbix 3.4

Zabbix 3.4 支持Centos 7。貌似不支持6.9. 更多详细内容请参考官方说明文档,详细的安装要求不贴出来了。 https://www.zabbix.com/documentation/3.4/zh/manual/installation/requirements 虚...

linjin200
37分钟前
1
0
阿里云数据库HybridDB for PostgreSQL使用教程

云数据库HybridDB for PostgreSQL(ApsaraDB HybridDB for PostgreSQL)是一种在线MPP大规模并行处理数据仓库服务。云数据库HybridDB for PostgreSQL基于Greenplum Database开源数据库项目,...

mcy0425
46分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部