当前位置 : 首页 » 文章分类 :  开发  »  Snowflake 雪花分布式ID生成算法

Snowflake 雪花分布式ID生成算法

Snowflake全局唯一id算法相关笔记


Snowflake唯一ID算法

Snowflake是Twitter提出来的一个算法,其目的是生成一个64bit的整数:


  • 1bit:一般是符号位,不做处理
  • 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年
  • 10bit:10bit用来记录机器ID,总共可以记录1024台机器,一般用前位代表数据中心,后面5位是某个数据中心的机器ID
  • 12bit:循环位,用来对同一个毫秒之内产生不同的ID,12位可以最多记录4095个,也就是在同一个机器同一毫秒最多记录4095个,多余的需要进行等待下毫秒。

具体实现时,可以根据不同业务的具体场景来划分。

优点:
毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。
不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
可以根据自身业务特性分配bit位,非常灵活。

缺点:
强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。

分布式唯一id:snowflake算法思考
https://juejin.im/post/5a7f9176f265da4e721c73a8


时钟回拨问题

服务器有时会发生时钟回拨,比如 服务器校时服务修正了系统时间 导致时钟回拨。

snowflake 是强依赖 机器时钟 的,如果时间发生回拨,有可能会生成重复的ID

处理方法:
1、如果时间回拨时间较短,比如配置5ms以内,那么可以直接等待一定的时间,让机器的时间追上来。
2、如果时间的回拨时间较长,我们不能接受这么长的阻塞等待,那么又有两个策略:
2.1、直接拒绝,抛出异常,打日志,通知RD时钟回滚。
2.2、利用扩展位,当时间回拨比较长的时候,不需要等待,直接在扩展位加1。2位的扩展位允许我们有3次大的时钟回拨,一般来说就够了,如果其超过三次我们还是选择抛出异常,打日志。

//判断是否发生了时间回退,如果发生则判断是否小于5ms内,小于5ms则等待获取最新的时间戳,否则抛出异常。
if (timestamp < this.lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            // 时间偏差大小小于5ms,则等待两倍时间
            wait(offset << 1);
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                logger.error("Clock moved backwards.Refusing to generate id for {} milliseconds", (this.lastTimestamp - timestamp));
                throw new UDSSnowFlakeRuntimeException(
                        String.format("Clock moved backwards.Refusing to generate id for %d milliseconds",
                                (this.lastTimestamp - timestamp)));
            }
        } catch (InterruptedException e) {
            logger.error("Method nextId encounter InterruptedException:", e.getMessage());
            throw e;
        }
    } else {
        logger.error("Clock moved backwards.Refusing to generate id for {} milliseconds", (this.lastTimestamp - timestamp));
        throw new UDSSnowFlakeRuntimeException(String.format("Clock moved backwards.Refusing to generate id for %d milliseconds",
                (this.lastTimestamp - timestamp)));
    }
}

如果再有人问你分布式 ID,这篇文章丢给他
https://juejin.im/post/5bb0217ef265da0ac2567b42


短地址生成

短 URL 系统是怎么设计的?
https://www.zhihu.com/question/29270034

Java工具类-基于SnowFlake的短地址生成器
https://www.twblogs.net/a/5c30961fbd9eee35b3a4d657/zh-cn

徐刘根 / Java—-工具类—-进制转换工具
https://gitee.com/xuliugen/codes/df8zhk263os7nebglruwq50

短地址算法:如何将一个长URL转换为一个短URL?
https://zhuanlan.zhihu.com/p/36030941


上一篇 Spring-Cloud-Sleuth

下一篇 Spring-Cloud

阅读
评论
855
阅读预计3分钟
创建日期 2019-03-09
修改日期 2020-03-16
类别
标签

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论