对于本文分布式id生成方案主要介绍Snowflake算法和现有互联网公司的开源的分布式id系统,例如美团left、百度uid-generator
Snowflake算法#
github:Snowflake算法-golang实现
snowflake雪花算法是twitter公司内部分布式项目采用的ID生成算法。
这种方案巧妙地把64位分别划分成多段,分开表示时间戳、机器标识和随机序列,先以此生成一个64位地二进制正整数,
然后再转换成十进制进行存储
说明:
- 第一个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-generator
是snowflake
算法基础上进行了改造。如图:
这个算法的时间戳是秒级的,并且workId
是由系统生成的。workerID的生成基于mysql
。在初始化的时候,
会此work二机器的信息插入到数据库,再将数据库的id作为workID。也就意味着只能使用一台数据库或者是一个读写分离的系统,
不能使用分布式数据库
美团left#
GitHub:美团left
美团技术团队:Leaf——美团点评分布式ID生成系统
美团left的系统也是基于Snowflake算法实现的。left系统基于zookeeper开发的(注:workid的生成基于zookeeper)
Leaf中workId是基于ZooKeeper的有序节点来生成的。
总之,系统生成workId减少了手动配置的问题,但是既然是基于Snowflake算法,那就不能避免避免时钟回拨的问题。
只能通过其他方式优化这个问题。
但是一般情况下,只要不影响工作,不会进行时钟回拨。毕竟,本系统使用时间是因为时间顺序性,而不是进行记时和校对时间的。