一、交易订单号生成(雪花算法)
基本思路,int64 二进制64位。按位来划分业务字段。
从高位到地位:
几位 | 含义 | 解释 |
---|---|---|
1 | 符号位 | 默认是0,不使用。(0正1负) |
31 | 时间戳 | 存的是时间戳差值,当前时间-2020年初,现在是时间戳是31位。够用60多年。才会增长到32位。 |
15 | 本地机器计数位 | 2^15-1。32767。单机支持3W qps。最大是63台机器。所以最大支持200W+写。目前线上店铺单写qps大概是在700。 |
6 | 服务器id | 2^6-1。63。最大支持63台机器。 |
10 | sharding key | 2^10-1。1023。目前1001个分片。 |
1 | 版本位 | 一位。 |
总共:64位
事例代码:
func Test_IdGen(t *testing.T) {
// 机器id偏移量6
var serverIdLength int64 = 6
// 时间戳偏移量21
var counterLength int64 = 21
// step1: 获取时间戳
timestamp := time.Now().Unix()
t.Logf( 时间戳:%v , timestamp)
t.Logf(strconv.FormatInt(timestamp, 2))
// step2: 获取本地机器的计数。mock数据为5
counter := int64(5)
t.Logf( 本地机器技术器:%v , counter)
t.Logf(strconv.FormatInt(counter, 2))
// step3: 获取机器编号。mock数据为9
serverId := int64(9)
t.Logf( 机器编号:%v , serverId)
t.Logf(strconv.FormatInt(serverId, 2))
// step3: 生成id
id := timestamp << (counterLength) |
counter << serverIdLength |
serverId
t.Logf( %v,时间戳左移21位 , strconv.FormatInt(timestamp << (counterLength), 2))
t.Logf( %v,本地机器计数左移6位 , strconv.FormatInt(counter << serverIdLength, 2))
t.Logf( %v,id现在为时间戳本地机器计数机器编号。一共52位 , strconv.FormatInt(id, 2))
t.Log( 下面是shardingKey )
// 获取sharding key 10001分片。mock值为998
shardingKey := int64(998)
t.Logf( sharding key:%v , shardingKey)
t.Logf(strconv.FormatInt(shardingKey, 2))
// sharding key占10位
id = id << 10 | shardingKey
t.Logf( %v,左移10位加上shardingKey , strconv.FormatInt(id, 2))
// 版本标记为占一位 mock值为 1
version := int64(1)
id = id << 1 | version
t.Logf( %v,左移1位加上version , strconv.FormatInt(id, 2))
t.Logf( 最终生成的id:%v , id)
}
执行结果:
image如何保证服务器id唯一
依赖redis setNx
func allocServerId() (uint16, error) {
dc := env.IDC()
var i, j, id uint16
switch dc {
case env.UnknownIDC:
i, j = 0, 60 // 60 servers for CN
case env.TEST:
i, j = 60, 61 // 1 server for boe
}
for {
id = uint16(rand.Intn(int(j-i))) + i // 随机生成
logs.Info( trying serverId: %d , id)
resp := kvClient.Put(context.Background(),
kvTable,
[]byte(fmt.Sprintf( cn_%d , id)),
[]byte(nonce),
bytekv.WithIfNotExists()) // setNx
if resp.Err == nil {
serverId = id
return id, nil
}
time.Sleep(time.Millisecond * time.Duration(rand.Intn(1000)))
}
}
二、常见的ID生成器
名词解释:
-
趋势递增:分段递增。2,1,3,10,17,15
-
单调递增:本次获取的id一定要大于上一次获取的id
UUID
UUID 的十六个八位字节被表示为 32个十六进制数字,以连字号分隔的五组来显示,形式为 8-4-4-4-12,总共有 36个字符(即三十二个英数字母和四个连字号)。例如:
123e4567-e89b-12d3-a456-426655440000
目前UUID的规范有5个版本;各个版本的具体介绍如下所示:
version 1:0001。基于时间和 MAC 地址。由于使用了 MAC 地址,因此能够确保唯一性,但是同时也暴露了 MAC 地址,私密性不够好。
version 2:0010。DCE 安全的 UUID。该版本在规范中并没有仔细说明,因此并没有具体的实现。
version 3:0011。基于名字空间 (MD5)。用户指定一个名字空间和一个字符串,通过 MD5 散列,生成 UUID。字符串本身需要是唯一的。
version 4:0100。基于随机数。虽然是基于随机数,但是重复的可能性可以忽略不计,因此该版本也是被经常使用的版本。
version 5:0101。基于名字空间 (SHA1)。跟 Version 3 类似,但是散列函数编程了 SHA1。
优点:
- 本地生成,性能好,全球唯一,适用于生成token令牌等场景
缺点:
-
占用存储大,有16字节
-
由于无序,不适合mysql等id有序场景。
基于数据库自增字段
基于数据库的自增ID完全可以充当分布式ID,部署一个单独的MySQL实例用来生成ID,建表结构如下:
CREATE DATABASE `SEQ_ID`;
CREATE TABLE SEQID.SEQUENCE_ID (
id bigint(20) unsigned NOT NULL auto_increment,
value char(10) NOT NULL default '',
PRIMARY KEY (id),
) ENGINE=MyISAM;
当我们需要一个ID的时候,就向表中插入一条数据返回主键ID即可
insert into SEQUENCE_ID(value) VALUES ('values');
优点:数据库生成的id绝对有序。
缺点:单点瓶颈。
基于多主的数据库自增字段
之前的单点数据库会有可用性和性能问题,可以使用集群模式加以改进,部署多个实例各自生产自增ID,设置不同的起始值和自增步长来规避ID重复的问题。例如使用两个mysql实例,如下配置:
// mysql_1
set @@auto_increment_offset = 1; -- 起始值
set @@auto_increment_increment = 2; -- 步长
// mysql_2
set @@auto_increment_offset = 2; -- 起始值
set @@auto_increment_increment = 2; -- 步长
但是,如果还是扛不住高并发而需要扩容的时候,那就需要手动更改已有实例的起始值和步长,确保不会有重复ID,比较麻烦。
优点:解决单点数据库的性能、可用性问题
缺点:不利于后续扩容,而且实际上单个数据库自身压力还是大,依旧无法满足高并发场景
基于数据库的号段模式
号段模式是当下分布式ID生成器的主流实现方式之一,号段模式可以理解为从数据库批量的获取自增ID,每次从数据库取出一个号段范围,例如 (1,1000] 代表1000个ID,具体的业务服务将本号段,生成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`)
)
等这批号段用完,再向数据库申请新的号段,同时更新max_id字段,update成功表示获取新号段成功,新号段的范围是[max_id+1, max_id+step]
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = #{version} and biz_type = XXX
由于多业务端可能同时操作,所以采用版本号version乐观锁方式更新,这种生成方式不强依赖于数据库,不会频繁的访问数据库,对数据库的压力小很多。
优点:
-
方便线性扩展,性能完全能够支撑大多数业务场景
-
趋势递增
-
通过号段缓存,即使DB宕机,短时间内仍能正常对外提供服务
-
可以自定义max_id的大小,非常方便业务从原有的ID方式上迁移过来
缺点:
-
ID号码不够随机,能够泄露发号数量的信息,不太安全
-
号段用完还是会hang在更新数据库的I/O上
-
DB宕机会造成整个系统不可用
递增发号由server代码实现。
// 生产者
func (w *wrapper) fetch() {
for {
// db拿到max_id和step
max_id, step := getFromDb()
for i := max_id; i < max_id+step; i++ {
w.idChan <- i
}
}
}
// 消费者
func (w *wrapper) Get() (int64, error) {
select {
case newId := <-w.idChan:
return newId, nil
case <-time.After(time.Millisecond * 200):
return 0, errors.New( no id left )
}
}
基于redis incr
原理就是利用redis的 incr命令实现ID的原子性自增。
127.0.0.1:6379> set seq_id 1 // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id // 增加1,并返回递增后的数值
(integer) 2
用redis实现需要注意一点,要考虑到redis持久化的问题。redis有两种持久化方式RDB
和AOF
-
RDB
会定时打一个快照进行持久化,假如连续自增但redis没及时持久化,而这会Redis挂掉了,重启Redis后会出现ID重复的情况。
// 900秒内,对数据库进行了至少1次修改
save 900 1
// 300秒内,对数据库进行了至少10次修改
save 300 10
// 60秒内,对数据库进行了至少1万次修改
save 60 10000
-
AOF
会对每条写命令进行持久化,即使Redis挂掉了也不会出现ID重复的情况,但由于incr命令的特殊性,AOF是追加写,会导致Redis重启恢复的数据时间过长。
基于雪花算法
雪花算法(Snowflake)是twitter公司内部分布式项目采用的ID生成算法,开源后广受国内大厂的好评,在该算法影响下各大公司相继开发出各具特色的分布式生成器。
imageSnowflake生成的是Long类型的ID,一个Long类型占8个字节,每个字节占8比特,也就是说一个Long类型占64个比特。
Snowflake ID组成结构:正数位(占1比特)+ 时间戳(占41比特)+ 机器ID(占5比特)+ 数据中心(占5比特)+ 自增值(占12比特),总共64比特组成的一个Long类型。
-
第一个bit位(1bit):Java中long的最高位是符号位代表正负,正数是0,负数是1,一般生成ID都为正数,所以默认为0。
-
时间戳部分(41bit):毫秒级的时间,不建议存当前时间戳,而是用(当前时间戳 - 固定开始时间戳)的差值,可以使产生的ID从更小的值开始;41位的时间戳可以使用69年,(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
-
工作机器id(10bit):也被叫做workId,这个可以灵活配置,机房或者机器号组合都可以。
-
序列号部分(12bit),自增值支持同一毫秒内同一个节点可以生成4096个ID
可以看到,snowflake是不依赖于数据库的,所以性能高、不占带宽,而且按时间有序,可以根据业务需求灵活调整各部分的位数。并且无法根据ID算出一段时间内的ID数,是信息安全的。但是缺点也很明显,强依赖机器时钟,时钟回拨会产生重复ID。
基于mongodb的objectID
mongodb为每条记录自动生成一个12字节的objectID,由三部分组成:
-
4字节:时间戳,秒级
-
5字节:3.4版本以前这部分由3字节机器标识码和2字节进程号组成,3.4版本到现在这里用5字节随机数。这个字段在C++的mongo源码中叫做
InstanceUnique
,也就是用于区分不同进程实例。官方文档里并没有关于这个改动的说明,可能的原因如下:-
新做法的合理性:objectID重复的条件是“在同一秒内,两个进程实例产生了相同的 5 字节随机数,且刚巧这时候两个进程的自增计数器的值也是相同的”,这个概率是非常低的;另一方面,原来做法在时间回拨时可能产生重复ID,因为机器码+进程号是固定的,但是使用随机数就将这个概率降低很多了;安全性上,不会泄露主机与进程的信息
-
旧做法在云时代可能失效:机器识别码一般是hostname的哈希,而云主机里hostname一般都是哈希,否则容易重复;进程号的问题就更大了,一般容器内的进程拥有自己独立的进程空间,在这个空间里只用它自己这一个进程(以及它的子进程),所以它的进程号永远都是 1
-
-
3字节:自增计数器
优点:按时间大致有序,性能好
缺点:强依赖mongo
三、业界的实现
Log ID
IPv4版本:字符串类型,32字节,如 20170111104055010006131078058EAC,包含以下部分:
-
14位秒级时间:年月日时分秒,如 20170111104055
-
12位IP:010006131078
-
6位随机串:如058EAC
IPv6版本:字符串类型,53字节,如 02 1573726681239 ffffffffffffffffffffffffffffffff abcdef,其中:
-
版本号[2位]
-
时间戳(精确到毫秒)[13位]
-
IPv6[32位]
-
random[6位]
// GenLogID return a new logID string
func (l LogID) GenLogID() string {
ip := formatIP(net2.GetLocalIP())
r := l.rand.Intn(maxRandNum) + 1<<20
sb := strings.Builder{}
sb.Grow(length)
sb.WriteString(version)
sb.WriteString(strconv.FormatInt(getMSTimestamp(), 10))
sb.Write(ip)
sb.WriteString(strconv.FormatInt(int64(r), 16))
return sb.String()
}
订单号的另一种方式(雪花算法+号段模式)
image-
user_id域10bits,取UID中时间戳的后10bits,用户进行分片;
-
IDC域5bits,用于记录数据户口(当前数据户口和用户户口保持一致),表明数据产生于SG or VA机房;
-
counter-source域1bits,用于记录ID中counter的数据来源,e.g. Redis or MySQL;
-
counter域43bits,计数字段;2^43=8 7960 9302 2208约为8.79万亿;从redis或者mysql取的号段。
-
biz_id域4bits,用于区分不同业务线,e.g. 订单、履约等;接入时需要提前联系,要创建biz_id。
-
最高位 1bits, 符号位;写死0,要求都是正数;
1、发号器优先使用mysql,mysql使用增加半同步数量的方式,保障至少大于3个从库全都同步成功了才返回,用于保障数据不会丢
2、如果mysql整体不可用了(比如mysql proxy挂了之类的),降级到redis,使用redis做发号器(如果redis挂了,低概率会出现数据回拨的可能)
3、如果mysql和redis同时都挂了,发号器有内存级别的缓存,支持发号器仍然能正常工作10分钟,研发RD要在这10分钟内高优恢复mysql or redis.
4、等mvp结束后,业务进展稍缓的时候,作为技术项目安排人力基于ByteRaft开发一个强一致的发号器系统,替换掉redis,从根本上解决redis数据回拨的可能性。
美团Leaf
参考美团技术团队文章:https://tech.meituan.com/2017/04/21/mt-leaf.html
源码地址:https://github.com/Meituan-Dianping/Leaf
leaf-segment 基于号段模式
-
基于biz_type分表
-
双buffer优化
Leaf 取号段的时机是在号段消耗完的时候进行的,也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间,并且在这期间进来的请求也会因为DB号段没有取回来,导致线程阻塞。如果请求DB的网络和DB的性能稳定,这种情况对系统的影响是不大的,但是假如取DB的时候网络发生抖动,或者DB发生慢查询就会导致整个系统的响应时间变慢。
为此,我们希望DB取号段的过程能够做到无阻塞,不需要在DB取号段的时候阻塞请求线程,即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示:
image采用双buffer的方式,Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时,如果下一个号段未更新,则另启一个更新线程去更新下一个号段。当前号段全部下发完后,如果下个号段准备好了则切换到下个号段为当前segment接着下发,循环往复。
-
每个biz-tag都有消费速度监控,通常推荐segment长度设置为服务高峰期发号QPS的600倍(10分钟),这样即使DB宕机,Leaf仍能持续发号10-20分钟不受影响。
-
每次请求来临时都会判断下个号段的状态,从而更新此号段,所以偶尔的网络抖动不会影响下个号段的更新。
leaf-segment 基于雪花算法
完全沿用snowflake的“1+41+10+12”的方式组装ID号,主要在部署和时间回拨上有所改进。
-
worderID生成
-
防止时间回拨
worderID生成
Leaf-Snowflake是按照下面几个步骤启动的:
-
启动Leaf-snowflake服务,连接Zookeeper,在leaf_forever父节点下检查自己是否已经注册过(是否有该顺序子节点);
-
如果有注册过直接取回自己的workerID(zk顺序节点生成的int类型ID号),启动服务;
-
如果没有注册过,就在该父节点下面创建一个持久顺序节点,创建成功后取回顺序号当做自己的workerID号,启动服务;
防止时间回拨
问题可以通过在ZK中写入自身系统实际来解决,解决方案如下:
image参见上图整个启动流程图,服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点:
-
若写过,则用自身系统时间与leaf_forever/{self}时间则认为机器时间发生了大步长回拨,服务启动失败并报警。
-
若未写过,证明是新服务节点,直接创建持久节点leaf_forever/${self}并写入自身系统时间,接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确,具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP:Port,然后通过RPC请求得到所有节点的系统时间,计算sum(time)/nodeSize。
-
若abs( 系统时间-sum(time)/nodeSize ) < 阈值,认为当前系统时间准确,正常启动服务,同时写临时节点leaf_temporary/${self} 维持租约。
-
否则认为本机系统时间发生大步长偏移,启动失败并报警。
-
每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。
百度uid-generator(基于雪花算法)
参考博客文档:https://www.cnblogs.com/yeyang/p/10226284.html
源码地址:https://github.com/baidu/uid-generator
百度uid-generator基于snowflake实现,使用“未来时间”解决了时钟回拨问题。
uid-generator默认采用与snowflake不同的id拼装方案(可配置):1+28+22+13(snowflake和Leaf-snowflake都是1+41+10+12):
-
1位符号位,生成的uid是正数
-
28位时间戳:单位秒,最多持续 8.7年
-
22位workerID:最多支持1<<22=420W次机器启动,用后即弃,从而不会有workerID重复的问题
-
13位序列号:每秒最多支持1<<13=8192并发。这里是并发序列号。
支持两种generator:DefaultUIDGenerator和CachedUIDGenerator
DefaultUIDGenerator
这种实现与snowflake相同,发生时间回拨时报错。默认配置下QPS上限为8192。
如何生成的worker id
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE(
ID BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED DATETIME NOT NULL COMMENT 'modified time',
CREATED DATEIMTE NOT NULL COMMENT 'created time')
COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;
UidGenerator会在集成用它生成分布式ID的实例启动的时候,往这个表中插入一行数据,得到的id值就是准备赋给workerId的值。由于workerId默认22位,那么,集成UidGenerator生成分布式ID的所有实例重启次数是不允许超过4194303次(即2^22-1),否则会抛出异常。
CachedUIDGenerator
在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
workerId
CachedUidGenerator的workerId实现继承自它的父类DefaultUidGenerator,即实例启动时往表WORKER_NODE插入数据后得到的自增ID值。
序列号(发号器号段)
使用RingBuffer缓存生成的id。RingBuffer是个环形数组,默认大小为8192个,里面缓存着生成的id。
获取id
会从ringbuffer中拿一个id,支持并发获取
填充id
RingBuffer填充时机
-
程序启动时,将RingBuffer填充满,缓存着8192个id
-
在调用getUID()获取id时,检测到RingBuffer中的剩余id个数小于总个数的50%,将RingBuffer填充满,使其缓存8192个id
-
定时填充(可配置是否使用以及定时任务的周期)
【UidGenerator通过借用未来时间来解决sequence天然存在的并发限制】
为什么叫借助未来时间?
因为每秒最多生成8192个id,当1秒获取id数多于8192时,RingBuffer中的id很快消耗完毕,在填充RingBuffer时,生成的id的delta seconds 部分只能使用未来的时间。
(因为使用了未来的时间来生成id,所以上面说的是,【最多】可支持约8.7年)
RingBuffer环形数组,数组每个元素成为一个slot。RingBuffer容量,默认为Snowflake算法中sequence最大值,且为2^N。可通过boostPower
配置进行扩容,以提高RingBuffer 读写吞吐量。
Tail指针、Cursor指针用于环形数组上读写slot:
-
Tail指针:表示Producer生产的最大序号(此序号从0开始,持续递增)。Tail不能超过Cursor,即生产者不能覆盖未消费的slot。当Tail已赶上curosr,此时可通过
rejectedPutBufferHandler
指定PutRejectPolicy -
Cursor指针:表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail,即不能消费未生产的slot。当Cursor已赶上tail,此时可通过
rejectedTakeBufferHandler
指定TakeRejectPolicy
时间戳
时间递增:传统的雪花算法实现都是通过System.currentTimeMillis()来获取时间并与上一次时间进行比较,这样的实现严重依赖服务器的时间。而UidGenerator的时间类型是AtomicLong,且通过incrementAndGet()方法获取下一次的时间,从而脱离了对服务器时间的依赖,也就不会有时钟回拨的问题
滴滴TinyID(号段模式)
源码地址:https://github.com/didi/tinyid/wiki
基于号段模式,是Leaf-segment的扩展。主要在部署上做了如下改进,提高性能和可用性:
-
支持了多db(master)分机房部署
-
提供了java-client(sdk)使id生成本地化
但是由于id大部分是连续的,也是不安全的,因此也不适用与订单等ID需要保密的系统。
[图片上传中...(image-d70008-1646898579767-3)]
微信seqsvr(号段模式)
参考文档地址:
http://www.52im.net/thread-1998-1-1.html
http://www.52im.net/thread-1999-1-1.html
需求:如何保证聊天消息的唯一性判定和顺序判定?
要解决消息的唯一性、顺序性问题,可以将一个技术点分解成两个:即将原先每条消息一个自增且唯一的消息ID分拆成两个关键属性——消息ID(msgId)、消息序列号(seqId),即msgId只要保证唯一性而不需要兼顾顺序性(比如直接用UUID)、seqId只要保证顺序性而不需要兼顾唯一性。msgId的实现非常简单,下面主要看seqId如何保证顺序。
首先seqId并不是全局唯一的,而是在每个namespace中唯一(实际上是严格递增的),每个用户都是一个namespace。举个例子,小明当前申请的 sequence 为100,那么他下一次申请的 sequence ,可能为101,也可能是110,总之一定大于之前申请的100。而小红呢,她的 sequence 与小明的 sequence 是独立开的,假如她当前申请到的 sequence 为50,然后期间不管小明申请多少次 sequence 怎么折腾,都不会影响到她下一次申请到的值(很可能是51)。
最简单的实现:对每个用户空间记录当前发的号
image这种实现的问题是:每发出一个id就要持久化一次,IO压力过大
改进:每个用户发一个max_seq,不需要每次都持久化到磁盘
image加入max_seq,当cur_seq涨到max_seq的时候才去写一次磁盘。如果服务挂了,下一次直接从max_seq开始。这样仍能保证id是递增的,只是会不连续而已。
这里还有一个问题:每个用户对应一个max_seq,服务重启的时候还是会从磁盘加载很多数据(用户空间2^32,每个用户占8字节(64位),总共32G)。
再一次改进:相邻用户共享max_seq,减小存储量。
image
网友评论