近期十大热点新闻,锦州网站优化,公司品牌推广方案范文,个人电脑建网站Snowflake#xff0c;雪花算法是由Twitter开源的分布式ID生成算法#xff0c;以划分命名空间的方式将 64-bit位分割成多个部分#xff0c;每个部分代表不同的含义。这种就是将64位划分为不同的段#xff0c;每段代表不同的涵义#xff0c;基本就是时间戳、机器ID和序列数。…Snowflake雪花算法是由Twitter开源的分布式ID生成算法以划分命名空间的方式将 64-bit位分割成多个部分每个部分代表不同的含义。这种就是将64位划分为不同的段每段代表不同的涵义基本就是时间戳、机器ID和序列数。为什么如此重要因为它提供了一种ID生成及生成的思路当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。雪花算法-SnowflakeSnowflake雪花算法是由Twitter开源的分布式ID生成算法以划分命名空间的方式将 64-bit位分割成多个部分每个部分代表不同的含义。而 Java中64bit的整数是Long类型所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。第1位占用1bit其值始终是0可看做是符号位不使用。第2位开始的41位是时间戳41-bit位可表示2^41个数每个数代表毫秒那么雪花算法可用的时间年限是(1L41)/(1000L360024*365)69 年的时间。中间的10-bit位可表示机器数即2^10 1024台机器但是一般情况下我们不会部署这么台机器。如果我们对IDC互联网数据中心有需求还可以将 10-bit 分 5-bit 给 IDC分5-bit给工作机器。这样就可以表示32个IDC每个IDC下可以有32台机器具体的划分可以根据自身需求定义。最后12-bit位是自增序列可表示2^12 4096个数。这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID。但是我们 IDC 和机器数肯定不止一个所以毫秒内能生成的有序ID数是翻倍的。Snowflake 的Twitter官方原版是用Scala写的对Scala语言有研究的同学可以去阅读下以下是 Java 版本的写法。package com.jajian.demo.distribute;/*** Twitter_Snowflakebr* SnowFlake的结构如下(每部分用-分开):br* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 br* 1位标识由于long基本类型在Java中是带符号的最高位是符号位正数是0负数是1所以id一般是正数最高位是0br* 41位时间截(毫秒级)注意41位时间截不是存储当前时间的时间截而是存储时间截的差值当前时间截 - 开始时间截)* 得到的值这里的的开始时间截一般是我们的id生成器开始使用的时间由我们程序来指定的如下下面程序IdWorker类的startTime属性。41位的时间截可以使用69年年T (1L 41) / (1000L * 60 * 60 * 24 * 365) 69br* 10位的数据机器位可以部署在1024个节点包括5位datacenterId和5位workerIdbr* 12位序列毫秒内的计数12位的计数顺序号支持每个节点每毫秒(同一机器同一时间截)产生4096个ID序号br* 加起来刚好64位为一个Long型。br* SnowFlake的优点是整体上按照时间自增排序并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)并且效率较高经测试SnowFlake每秒能够产生26万ID左右。*/
public class SnowflakeDistributeId {// Fields/*** 开始时间截 (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位(125)*/private final long datacenterIdShift sequenceBits workerIdBits;/*** 时间截向左移22位(5512)*/private final long timestampLeftShift sequenceBits workerIdBits datacenterIdBits;/*** 生成序列的掩码这里为4095 (0b1111111111110xfff4095)*/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;//Constructors/*** 构造函数** param workerId 工作ID (0~31)* param datacenterId 数据中心ID (0~31)*/public SnowflakeDistributeId(long workerId, long datacenterId) {if (workerId maxWorkerId || workerId 0) {throw new IllegalArgumentException(String.format(worker Id cant be greater than %d or less than 0, maxWorkerId));}if (datacenterId maxDatacenterId || datacenterId 0) {throw new IllegalArgumentException(String.format(datacenter Id cant be greater than %d or less than 0, maxDatacenterId));}this.workerId workerId;this.datacenterId datacenterId;}// Methods/*** 获得下一个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位的IDreturn ((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) {SnowflakeDistributeId idWorker new SnowflakeDistributeId(0, 0);for (int i 0; i 1000; i) {long id idWorker.nextId();
// System.out.println(Long.toBinaryString(id));System.out.println(id);}
}雪花算法提供了一个很好的设计思想雪花算法生成的ID是趋势递增不依赖数据库等第三方系统以服务的方式部署稳定性更高生成ID的性能也是非常高的而且可以根据自身业务特性分配bit位非常灵活。但是雪花算法强依赖机器时钟如果机器上时钟回拨会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID而时间回退后生成的ID就有可能重复。官方对于此并没有给出解决方案而是简单的抛错处理这样会造成在时间被追回之前的这段时间服务不可用。很多其他类雪花算法也是在此思想上的设计然后改进规避它的缺陷后面介绍的百度 UidGenerator 和 美团分布式ID生成系统 Leaf 中snowflake模式都是在 snowflake 的基础上演进出来的。其它相关算法在如下文章中已经包含了所有主流的全局唯一ID实现方案分布式系统 - 全局唯一ID实现方案这里给出相关的链接为什么需要全局唯一IDUUID数据库生成使用redis实现雪花算法-Snowflake百度-UidGeneratorDefaultUidGenerator 实现CachedUidGenerator 实现美团LeafLeaf-segment 数据库方案Leaf-snowflake方案Mist 薄雾算法整理好的Java面试资料推荐阅读下载最全的java面试题库Java核心知识点整理
