snowflake分布式唯一算法

序幕

ID一般用来作为数据库表的主键，需要保证唯一性，通常情况下可以有以下几种方式实现：

1.UUID（Universally Unique Identifier）：

UUID是由一组32位数的16进制数字所构成的通用唯一识别码，可以保证ID的全局唯一性，但由于数据库或者文件系统的索引一般是由B+树构成的，而UUID插入完全无序，经常会导致一些中间节点合并和分裂，大大降低了数据库插入性能。

1
2
3

import uuid
print(uuid.uuid1())
12725082-acaa-11ea-98eb-e86a64ddceb7

2.自增ID：

现在很多数据库引擎都支持自增ID，自增ID最大的好处是每次插入都在末尾，这样可以很大程度的减少节点的合并和分裂。而且自增ID所占空间也比UUID要小。但是自增ID只能保证一个库中一张表的ID唯一，往往不能保证多个库多张表的ID唯一，这样多个库之间合并的时候会因为主键冲突而失败。

3.自增ID+哈希取模：

如果数据量比较大，可以用n台机器存储。每台机器设置不同的起始值，所有机器的步长和机器数量相同。相当于自增ID与机器数量哈希取模。比如有3台机器，第一台设置1,4,7……；第二台设置2,5,8……；第三台设置3,6,9……但是这样的话，ID的生成对数据库严重依赖，一旦数据库挂掉，服务将变得不可用。

4.SnowFlake：

snowflake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。

分布式情况下SnowFlake是一种生成ID比较好的算法。

这种方案大致来说是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法，这种方案把64-bit分别划分成多段，分开来标示机器、时间等。

snowflake

组成

其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号，最后还有一个符号位，永远是0。

使用

首先安装库
1
pip3 install pysnowflake
接下来在本地启动snowflake服务
1
snowflake_start_server --worker=1
这里值得说下的是可以通过定义端口号来实现运行多个服务
然后使用setup指定ip与端口
之后就是对snowflake生成的id进行分析

有人就会问，假设我搭建了上千个节点的分布式系统，此时接口接到参数id,我怎么判断该id的订单信息存储在那个节点中呢？
其实很容易就可以判断，从SnowFlake的算法结构入手，本身就是二进制转换十进制的整形，现在我们反着进行解析即可。
1
2
3
4
#首先将其转换为二进制
print(bin(4369145685749010433))
#打印结果
0b11110010100010010100101101101000111011000000000001000000000001
之前我们说第一位是标识符，此后是41位的时间戳，紧接着10位的节点标识码，最后12位的递增序列，从后面数12位是：000000000001，再数5位是：00001 这5位就是某个节点的存储标识，我们就二进制的00001转换为十进制
1
2
3
4
5
6
7
8
# 节点标识
a = bin(4369049307706298369)[47:52]
print('节点标识二进制%s'%a)
# 强转十进制
print(int(a,2))
#打印结果
节点标识二进制00001
1
可以看到，转换结果显示该id存储在节点1的数据库中

总结

其实关于分布式唯一id的解决方案，也不仅仅只有uuid或者snowflake，像redis的incr原子性操作自增，亦或者Mongodb极具特色的_objectid的生成方式，专为分布式而设计的ID生成方案。都是可以参考的解决方案，但是方案总归是方案，总有其自身的特点和缺陷，这就需要根据实际应用场景而具体问题进行具体分析了。