分布式ID生成器-雪花算法

文章图片1

1. 雪花算法(Snowflake)

Twitter的Snowflake算法是在分布式系统中一种自增ID的算法,ID能够按照时间有序生成并且可以做到全局唯一。Twitter对雪花算法的需求:

性能

  • 每个进程每秒至少10k个id
  • 响应速率2ms(包括网络延迟)

协调

对于数据中心内部和跨数据中心的高可用性,生成id的机器无需进行集群协调。也就是说无需再每个服务之间进行通讯进行协调。

直接排序

无需加载整个对象ID就能排序(时间戳)

紧凑

生成的ID要紧凑,换句话说就是ID所占的长度需要适中在完成业务需要的基础上。

高可用

ID生成服务要高可用,例如:存储服务

Tips: Twitter的雪花算法的说明github.com/twitter-arc…

1.1 雪花算法的数据结构

雪花算法生产的ID所占8个字节64位,也就是长整型 long 的长度。

文章图片2

  • 首位bit位表示符号位,生成ID都是正数所以最高位就是0
  • 时间戳(41bit),毫秒级别时间戳。但是实际开发过程中使用的时间戳使用的是时间戳的差值。这个差值=当前时间戳 - 开发者设置的固定时间戳 ,那么41位的时间戳可以使用69年
  • (1L << 41) / (1000L * 60 * 60 * 24 * 365) 算出来差不多69年
  • 机器ID(10bit),一共可以配置1024台机器,如果有多个机房在10bit进行机房和机器好进行组合
  • 序列号(12bit),每一台机器1ms可以生成4096(如果一台机器一毫秒内生成超过4096需要进行保护)

1.2 系统时钟依赖

应该使用NTP来保持系统时钟的准确性。Snowflake 可以防止非单调时钟的影响,也就是时钟倒走。如果您的时钟运行得很快,并且NTP告诉它重复几毫秒,那么 Snowflake 将拒绝生成id,直到上次我们生成id之后的某个时间。在ntp不会让时钟倒转的模式下运行。

如果时间进行回拨那么生成的ID就有可能出现重复的情况。

2. 雪花算法Java实现

/** * @author mxsm * @date 2022/4/9 21:17 * @Since 1.0.0 */public class SnowflakeGenerator {    private static final long FIXED_TIMESTAMP = 1649491204306L;    private int machineId;    private int sequenceNumber = 0;    //最后一次生成ID时间    private volatile long lastTimestamp = -1L;    public SnowflakeGenerator(int machineId) {        this.machineId = machineId;    }    public synchronized long nextId() {        //获取当前时间        long currentTimestamp = System.currentTimeMillis();        //同一个毫秒内生成ID        if(currentTimestamp == lastTimestamp){            sequenceNumber += 1;            //处理一秒超过4096个            if(sequenceNumber > 4096){                while (currentTimestamp <= lastTimestamp){                    currentTimestamp = System.currentTimeMillis();                }                sequenceNumber = 0;            }        }else {            //重置序列号            sequenceNumber = 0;        }        lastTimestamp = currentTimestamp;        return ( (currentTimestamp - FIXED_TIMESTAMP) << 22) | (machineId << 12) | sequenceNumber;    }}

Tips: 代码地址
https://github.com/mxsm/distributed-id-generator/tree/main/generator-snowflake

以上代码是简单的实现。

3.优缺点

优点:

  • ID生成服务与服务之间没有协调。靠要单独进行工作。
  • 在ID生成服务本地生成没有网络的消耗效率高,高性能高可用:生成时不依赖于数据库,完全在内存中生成
  • 高吞吐:每秒钟能生成数百万的自增 ID

缺点:

  • 依赖与系统时间的一致性,如果系统时间被回调,或者改变,可能会造成 ID 冲突或者重复。

Tips: 在本人公司没有单独部署雪花算法的生产服务器,而是将生成器直接集成到了每个项目的代码中。机器ID是IP地址取模32后的值。所以在高并发下可能会出现小概率的重复情况。在可允许的范围内

4. 总结

雪花算法的服务集群没有服务之间的协调和同步。可以说是用单机组成的高可用分布式ID可用集群。雪花算法依赖时间戳,如果时间戳出现回拨的情况就有可能ID重复的情况。总体来说雪花算法相对于Redis实现 UUID 以及MySQL有更优。



作者:蚂蚁背大象
链接:
https://juejin.cn/post/7084624216074485774


低成本网站开发与高端网站开发的区别

网络经济时期,互联网营销和国际贸易变成传统式公司需要做到的挑选 。网站开发已变成公司形象推广、商品展示营销推广、顾客服务沟通交流的重要信息公路桥

Web前端:2022年最好的JavaScript框架是什么?

它用于创建 Web 应用程序和 REST API,它速度快,也是一个轻量级且可扩展的 Node.js Web 应用程序框架,提供了用于创建 We

到底是RWD(响应式网页设计)好还是AWD好?

没有RWD或AWD的网站到底会怎样?先讲结论,网站流量会暴跌,RWD跟AWD就是可移动端浏览的网站,而现在用移动设备上网的比例超过80%,而且搜索引擎已经以移动端网站表现为排名依据,简单来说没有移动版的网站等于宣告死刑,无法被搜索的网站有什么用?

在做网站SEO优化中robots的编写方法

robots.txt是搜索引擎中的一个协议,当你的网站有一些内容不想给蜘蛛爬取,那可以利用robots.txt来告诉蜘蛛不要去爬取这些页面,不爬取这些页面当然就不收录了。robots.txt是搜索引擎中访问网站的时候要查看的第一个文件。

HTML5新增了哪些结构标签?

在使用DIV+CSS布局时,我们需要通过为div命名的方式,来区分网页中不同的模块。在HTML5中布局方式有了新的变化,HTML5中增加了新的结构标签,如header标签、nav标签、article标签等,具体介绍如下。1.