雪花算法
雪花算法（snowflake）是Twitter开源的分布式id算法。
组成结构
雪花算法生成的id共64bit，组成结构如下
- 符号位，固定为0，表示是正数
- 时间戳部分，使用系统当前毫秒减去一个开始时间（可以是上线时间）
- 服务中心id和机器id部分，用于区分不同机器，视具体部署架构而定，常见的有“服务中心取机房名or集群名，机器id取ip处理结果”、“服务中心取ip处理结果，机器id取port处理结果”等等
-
序列号，从0开始自增，用于在同一时间戳内产生不同id
image.png
这个组成结构，并非固定不变，可以根据实际情况改变。
比如，如果实际情况只有1个服务中心，并且未来不会有多个，那么可以不区分服务中心id和机器id。
雪花算法是严格全局有序吗
应用层生成id到真正入库，中间有时间差，有可能早生成的id更晚入库，因此，最终数据库的id是否有序无法保证。
在此讨论的“有序”，是指“生成id动作”的有序，更早生成的id，更小。
雪花算法生成的id是否严格有序，分2个场景来回答
相同进程
在同一个进程内，生成的id可以保证严格有序，原因如下
- 相同的时间戳内，通过序列号自增保证有序
- 不同时间戳，通过时间戳递增保证有序
不同进程
不同的进程，不能保证严格有序，原因如下
- 不同进程如果位于不同服务器，时钟不一定完全同步
- 不同进程如果位于不同服务器，同一时间戳内，服务中心id、机器id更小的机器，生成的id更小，即使另一台机器在这个时间戳内更早生成id
如何解决时钟回拨问题
时钟回拨问题: 比如第1-5秒，已经生成了一些id，然后时钟回拨到1秒，又从第1秒开始生成id。如果没有额外处理，会导致重复id生成
image.png
生成的十进制id的位数
64bit中，除去第一个有效位，实际有效的部分是63bit，支持的最大值是2^62。
2^62的十进制是19位，因此按上面的组成结构，生成的十进制id最多是19位。
实际业务中，时间戳一般不会占用41bit那么多，跟时间戳部分的计算方式，和系统运行时长有关，最终生成的十进制id不一定会到19位。
另外，上面的组成结构不是固定的，如果是另外的组成结构，算出来十进制id位数也不同。
雪花算法重复问题
雪花算法生成的id是有可能重复的，比如以下实现方式
image.png
数据中心id为ip处理结果%32，
机器id为port处理结果%32，
%32是为了控制只占用5个二进制位。
port的枚举范围在0~65535，%32是很有可能冲突的，
ip同理，冲突概率取决于处理方式。
处理ip时，需要根据项目实际情况决定处理方式，
比如一个项目有10个实例，这10个实例处于同一网段，ip都是10.244.xxx.xxx，前2个部分是一样的，
那么使用ip计算雪花算法时，可以只把后2个部分拿出来计算，减小冲突概率。
另外，雪花算法的4个组成部分，每个部分占用的位数，也可以根据实际情况调整。
比如，序列号为12号，表示同一个时间戳最多可以生成4096个id，
如果一个项目达不到4096/ms的并发量，那就可以把序列号的位数分几位给其他部分，最终达到减小冲突概率的目的。
再比如时间戳部分，如果存的是系统运行时的时间戳（毫秒级别），需要41个bit，但是如果存的是系统运行时间 - 系统上线时间，38bit就够了，可以把时间戳部分出3bit给其他部分。
// 2^40
1099511627776
// 2^41
2199023255552
// begin, 2019-01-01，需要40bit
1546272000000
// end, 2024-05-31，需要40bit
1717121767697
// end - begin，需要40bit
170849767697
