tyltr技术窝

对于本文分布式id生成方案主要介绍Snowflake算法和现有互联网公司的开源的分布式id系统,例如美团left、百度uid-generator

Snowflake算法#

github:Snowflake算法-golang实现

snowflake雪花算法是twitter公司内部分布式项目采用的ID生成算法。
这种方案巧妙地把64位分别划分成多段,分开表示时间戳、机器标识和随机序列,先以此生成一个64位地二进制正整数,
然后再转换成十进制进行存储

Snowflake算法

说明:

  • 第一个bit位是标识部分,在计算机中,正数是0,负数是1,一般生成的ID为正数,所以固定为0。
    时间戳部分占41bit,这个是毫秒级的时间,一般实现上不会存储当前的时间戳,而是时间戳的差值(当前时间 - 固定的开始时间),
  • 这样可以使产生的ID从更小值开始;41位的时间戳可以使用 (1 << 41) / (1000 * 60 * 60 * 24 * 365) = 69.7 年。
  • 工作机器id占10bit,这里比较灵活,可根据个人需求进行划分。
    比如,可以使用前5位作为数据中心机房标识,后5位作为单机房机器标识,可以部署1024个节点。下面的算法示例也是按照这种方式划分的。
  • 序列号部分占12bit,支持同一毫秒内同一个节点可以生成 2^12 = 4096个ID

优点:

  • 整个ID是趋势递增,可以避免uuid无序问题
  • 每秒能够生成百万个不同的ID,性能佳

缺点:

  • 时钟回拨问题。因为太依赖时钟了,针对一个机器进行时钟回拨,那会产生相同的id。所以一般基于此的算法发现时钟回拨,
    都会抛异常处理,阻止ID生成,这可能导致服务不可用。
    Snowflake算法也采用时钟回拨即抛异常的方式

在大厂里,其实并没有直接使用snowflake,而是进行了改造,因为snowflake算法中最难实践的就是工作机器id
原始的snowflake算法需要人工去为每台机器去指定一个机器id,并配置在某个地方从而让snowflake从此处获取机器id。
机器是很多的,人力成本太大且容易出错,所以大厂对snowflake进行了改造。

百度uid-generator#

GitHub:UidGenerator

百度uid-generatorsnowflake算法基础上进行了改造。如图:
uid-generator生成的ID

这个算法的时间戳是秒级的,并且workId是由系统生成的。workerID的生成基于mysql。在初始化的时候,
会此work二机器的信息插入到数据库,再将数据库的id作为workID。也就意味着只能使用一台数据库或者是一个读写分离的系统,
不能使用分布式数据库

美团left#

GitHub:美团left
美团技术团队:Leaf——美团点评分布式ID生成系统

美团left的系统也是基于Snowflake算法实现的。left系统基于zookeeper开发的(注:workid的生成基于zookeeper)
Leaf中workId是基于ZooKeeper的有序节点来生成的。

总之,系统生成workId减少了手动配置的问题,但是既然是基于Snowflake算法,那就不能避免避免时钟回拨的问题。
只能通过其他方式优化这个问题。

但是一般情况下,只要不影响工作,不会进行时钟回拨。毕竟,本系统使用时间是因为时间顺序性,而不是进行记时和校对时间的。