前言
随着业务的发展，单一数据库的自增ID已经不能满足我们的需求，使用全局唯一ID的场景必然会出现，比如海量的订单号，档案号等等。我们初始可能会选择使用36位的UUID，配合机器id和时间戳，基本可以满足需求。
但是UUID的缺点也很明显，由于其完全无序，对MySQL的B+树结构特别不友好。另外UUID的长度也会造成数据库索引空间的浪费。
由此产生的需求
- 全局唯一：不能重复，这是最基本的要求。
- 趋势递增：生成的ID是有序递增的，这样数据库存储索引数据时可以保证写入性能。
- 信息安全：生成的ID不能是简单连续递增的，必须是大致递增。如果是连续的，那么恶意用户可以很简单地爬取我们的数据；而对于订单号这种敏感的数据，竞争对手更是可以轻松推算出我们一天的单量。
解决方案：雪花算法
雪花算法（Snowflake）是Twitter开源的一种生成分布式全局唯一ID的算法，产生的背景是为了满足Twitter每秒上万条消息的请求，这些消息为了不重复必须有一个全局唯一的ID，并且还需要有大致的顺序，以满足存储性能要求及客户端排序。
其默认生成结果是一个64bit的long型数值，组成部分包含时间戳，并且保持了大致递增。
雪花算法核心结构
image
如图所示，组成一共包含4个部分：
- 不使用：1bit，最高位bit默认为0，不使用；
- 时间戳：41bit，毫秒级的时间戳，可以支持该算法使用到2082年；建议使用64位Linux系统机器，通过vdso，gettimeofday()在用户态就可以完成操作，减少了进入内核态的损耗。
- 机器标识：10bit可以支持1024台机器，通常会将其拆分为两部分，5bit代表数据中心ID，5bit代表工作机器ID。
- 序列号：12bit递增序列号，就是一系列的自增id，每秒最多生成4096个不重复的ID。
通过这4部分，雪花算法可以在1秒内生成约409万个ID，已经基本满足绝大部分的业务需求。
由于雪花算法生成的ID是大致递增的，非常契合MySQL中B+树的结构，应用到数据库的主键时，可以极大的提升插入效率。
另外由于其是大致递增，而不是顺序递增，直接将生成结果作为如订单号这样的业务字段也没问题，可以保证第三方无法推断出真实的订单量。
雪花算法生成ID重复的问题及解决方案
虽然雪花算法通过不同的组成尽量避免了ID重复，但是在某些极限情况下，依然无法排除ID重复的发生。
- 情况1：时钟回拨，雪花算法强依赖机器时钟，如果机器上时钟回拨，会造成发号重复。
- 情况2：在某一毫秒内，某些节点上的机器标识一致，并且产生了同一个序列号。
针对情况1，我们可以维护一个上次生产ID的时间戳lastTimestamp，每次发号后更新lastTimestamp，发号前则对比当前时间戳和lastTimestamp，当前时间戳比lastTimestamp小，就强制等待两者时间差后再发号，但这会造成发号服务处于不可用的状态。
针对情况2，既然时间戳和序列号我们无法保证不重复，那就从机器标识下手。只要机器标识不重复，生成的ID自然也不会重复了。如果我们的项目部署是机器级别，即一台机器上部署一套服务，那以机器MAC地址作为机器标识就可以。如果是进程级别，即一台机器上部署多套相同的服务，仅仅是PID不同，这种情况下可以通过引入Redis、Zookeeper或者MySQL来保证机器标识位的唯一性。
国内开源的分布式ID框架
对于雪花算法可能重复的问题，国内也有一些开源的框架作为替代，比如MT的leaf、BD的Uid。
总得来说，雪花算法已经可以满足绝大部分场景，如果没有十分必要的话，还是不建议引入开源方案，毕竟会大大增加我们系统的复杂度。
总结
本文主要讲解了什么是雪花算法，雪花算法适用的场景以及如何解决雪花算法冲突的问题。
当然雪花算法也不是万能的，不能适用所有的场景，建议大家根据实际的业务进行评估，然后选择合适的方案。
�
学习技术，分享技术，期待与大家共同进步，也感谢您的点赞与关注。
网友评论