对于单体系统来说,主键ID可能会常用主键自动的方式进行设置,这种ID生成方法在单体项目是可行的,但是对于分布式系统,分库分表之后,就不适应了,比如订单表数据量太大了,分成了多个库,如果还采用数据库主键自增的方式,就会出现在不同库id一致的情况,虽然是不符合业务的
UUID (Universally Unique Identifier),通用唯一识别码的缩写。UUID的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符,示例: 863e254b-ae34-4371-87da-204b71d46a7b
。UUID理论上的总数为1632=2128,约等于3.4 x 10^38。
在分布式环境也可以使用mysql的自增实现分布式ID的生成,如果分库分表了,当然不是简单的设置好auto_increment_increment
和 auto_increment_offset
即可,在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。比如有两台机器。设置步长step为2,Server1的初始值为1(1,3,5,7,9,11…)、Server2的初始值为2(2,4,6,8,10…)。这是Flickr团队在2010年撰文介绍的一种主键生成策略(Ticket Servers: Distributed Unique Primary Keys on the Cheap )
假设有N台机器,step就要设置为N,如图进行设置:
这种方案看起来是可行的,但是如果要扩容,步长step等要重新设置,假如只有一台机器,步长就是1,比如
1,2,3,4,5,6
,这时候如果要进行扩容,就要重新设置,机器2可以挑一个偶数的数字,这个数字在扩容时间内,数据库自增要达不到这个数的,然后步长就是2,机器1要重新设置step为2,然后还是以一个奇数开始进行自增。这个过程看起来不是很杂,但是,如果机器很多的话,那就要花很多时间去维护重新设置
这种实现的缺陷:
这种模式也是现在生成分布式ID的一种方法,实现思路是会从数据库获取一个号段范围,比如[1,1000],
生成1到1000的自增ID加载到内存中,建表结构如:
CREATE TABLE id_generator (
id int(10) NOT NULL,
max_id bigint(20) NOT NULL COMMENT '当前最大id',
step int(20) NOT NULL COMMENT '号段的布长',
biz_type int(20) NOT NULL COMMENT '业务类型',
version int(20) NOT NULL COMMENT '版本号',
PRIMARY KEY (`id`)
)
等ID都用了,再去数据库获取,然后更改最大值
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
Redis分布式ID实现主要是通过提供像INCR
和 INCRBY
这样的自增原子命令,由于Redis单线程的特点,可以保证ID的唯一性和有序性
这种实现方式,如果并发请求量上来后,就需要集群,不过集群后,又要和传统数据库一样,设置分段和步长
优缺点:
Snowflake,雪花算法是由Twitter开源的分布式ID生成算法,以划分命名空间的方式将 64-bit位分割成多个部分,每个部分代表不同的含义,64位,在java中Long类型是64位的,所以java程序中一般使用Long类型存储
百度的UidGenerator是百度开源基于Java语言实现的唯一ID生成器,是在雪花算法 snowflake 的基础上做了一些改进。 引用官网的解释:
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。 在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
Snowflake算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可生成一个64 bits的唯一ID(long)。默认采用上图字节分配方式:
详细的,可以参考官网解释,链接:https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
Leaf这个名字是来自德国哲学家、数学家莱布尼茨的一句话: >There are no two identical leaves in the world > “世界上没有两片相同的树叶”
Leaf 提供两种生成的ID的方式:号段模式(Leaf-segment)和snowflake模式(Leaf-snowflake)。你可以同时开启两种方式,也可以指定开启某种方式,默认两种方式为关闭状态。
第一种Leaf-segment方案,在使用数据库的方案上,做了如下改变: - 原方案每次获取ID都得读写一次数据库,造成数据库压力大。改为利用proxy server批量获取,每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段,可以大大的减轻数据库的压力。 - 各个业务不同的发号需求用biz_tag字段来区分,每个biz-tag的ID获取相互隔离,互不影响。如果以后有性能需求需要对数据库扩容,不需要上述描述的复杂的扩容操作,只需要对biz_tag分库分表就行
表结构设计:
>+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field | Type | Null | Key | Default | Extra |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag | varchar(128) | NO | PRI | | |
| max_id | bigint(20) | NO | | 1 | |
| step | int(11) | NO | | NULL | |
| desc | varchar(256) | YES | | NULL | |
| update_time | timestamp | NO | | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+
Leaf-snowflake方案完全沿用snowflake方案的bit位设计,即是“1+41+10+12”的方式组装ID号。对于workerID的分配,当服务集群数量较小的情况下,完全可以手动配置。Leaf服务规模较大,动手配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。Leaf-snowflake是按照下面几个步骤启动的:
这种方案解决了前面提到的雪花算法的缺陷,官网没解释,不过Leafsnowflake对其进行改进,官网的流程图
详细介绍请看官网:https://tech.meituan.com/2017/04/21/mt-leaf.html
Tinyid是用Java开发的一款分布式id生成系统,基于数据库号段算法实现。Tinyid扩展了leaf-segment算法,支持了多数据库和tinyid-client
Tinyid也是基于号段算法实现,系统实现图如下: