文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录 博客园版 为您奉上珍贵的学习资源 :
免费赠送 :《尼恩Java面试宝典》 持续更新+ 史上最全 + 面试必备 2000页+ 面试必备 + 大厂必备 +涨薪必备
免费赠送 :《尼恩技术圣经+高并发系列PDF》 ,帮你 实现技术自由,完成职业升级, 薪酬猛涨!加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷1)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷2)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程(卷3)加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 资源宝库: Java 必备 百度网盘资源大合集 价值>10000元 加尼恩领取
《分布式ID学习圣经: 1000w级qps高并发ID如何生成》
背景:
在40岁老架构师尼恩的读者社群(50+)中,很多小伙伴拿不到offer,或者拿不到好的offer。
尼恩经常给大家 优化项目,优化简历,挖掘技术亮点。在指导简历的过程中, 高并发、分布式核心组件是一项很重要的指导。
在所有的高并发、分布式核心组件:分布式ID 是核心中的核心、重点中的重点。
分布式ID 组件,是整个系统 黄金链路上的关键组件、黄金组件,
如果分布式ID 组件出现问题,整个黄金链路上关键动作都无法执行,这就会带来一场灾难,一定是P0级大灾难。
对于架构师、高级开发来说, 分布式ID的方案和架构,是重点中的重点, 更是内功中的内功。
分布式ID,也是面试的重点和高频点。比如,近段时间尼恩社群中有很多小伙伴在面试滴滴、美团、网易等大厂时候,就遇到很多类似问题:
(1) 一个分布式ID生成系统,如何实现?
(2) 分布式ID系统,如何实现高并发?
(3) 分布式ID系统,如何实现高可用?
等等等等.....
尼恩团队结合资深架构经验和行业案例,给大家梳理一个体系化、系统化的参考答案,
并且组成一个电子书《分布式ID学习圣经:1000w级qps高并发ID如何生成》PDF 电子书,帮助大家顺利通过面试,拿到心仪的offer
并且最终顺利转型 三栖架构师。
最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩 面试宝典》 的PDF文件,请到公号【技术自由圈】获取
![](/i/ll/?i=e4aa01b7805c4ae799f17449c8d4054f.png)
本文目录
目录- 《分布式ID学习圣经: 1000w级qps高并发ID如何生成》
一:超高并发、超高性能分布式ID生成系统的要求
在复杂的超高并发、分布式系统中,往往需要对大量的数据和消息进行唯一标识。
如在高并发、分布式的金融、支付、餐饮、酒店、电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一个唯一ID来标识一条数据或消息,数据库的自增ID显然不能满足需求;特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识。
此时一个能够生成全局唯一ID的系统是非常必要的。
概括下来,那业务系统对ID号的要求有哪些呢?
主要有四点:
- 全局唯一性:不能出现重复的ID号,既然是唯一标识,这是最基本的要求。
- 趋势递增:在MySQL InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用B-tree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
- 单调递增:保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
- 信息安全:如果ID是连续的,恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;如果是订单号就更危险了,竞对可以直接知道我们一天的单量。所以在一些应用场景下,会需要ID无规则、不规则。
注意,上述1234对应不同的场景,
特别注意:3和4需求还是互斥的,无法使用同一个方案满足。
同时除了对ID号码自身的要求,业务还对ID号生成系统的可用性要求极高,并且处于业务的黄金链路上,
想象一下,如果ID生成系统瘫痪,整个系统黄金链路上关键动作都无法执行,这就会带来一场灾难。
超高并发、超高性能分布式ID生成系统三个超高
由此总结下一个ID生成系统应该做到如下三个超高:
-
超低延迟:平均延迟和TP999延迟都要尽可能低;
-
超高可用:可用性5个9;
-
超高并发: 高QPS。
超高并发, 最好是100Wqps以上,比如滴滴的tinyid,就达到千万QPS, 具体见后文
按照尼恩的架构哲学,咱们从最为基础的原理讲起,来看看 一个基本的问题:
-
什么是本地ID生成器?
-
什么是分布式ID生成器?
二:什么是本地ID生成器、分布式ID生成器
本地ID生成器是指在本地环境中生成唯一标识符(ID)的工具或算法。
本地ID生成器是相对于 分布式ID生成器而言的。二者的区分不是ID的用途,而是生产ID是否存在 网络IO开销:
- 本地ID生成器在本地生产ID,没有网络IO开销;
- 分布式ID生成器 需要进行远程调用生产ID,有网络IO开销;
总之,本地ID生成器所生产的ID并不是仅仅用于本地,也会用于分布式系统,拥有分布式系统中唯一标识实体或资源,例如数据库记录、消息、文件等。
在设计本地ID生成器时,需要考虑以下几个方面:
- 唯一性:生成的ID必须在整个系统中是唯一的,以避免冲突。
- 可排序性:生成的ID应该具有可排序性,以便根据ID的顺序进行查询和排序操作。
- 性能:ID生成的过程应该高效,不应该成为系统的瓶颈。
- 可读性:生成的ID可以是可读的,便于调试和理解。
- 分布式支持:如果系统是分布式的,需要确保在多个节点上生成的ID也是唯一的。
常见的本地ID生成器算法包括:
- 自增ID:使用一个计数器,在每次生成ID时递增。这种方式简单高效,但在分布式环境中需要额外的考虑,以避免冲突。
- UUID(Universally Unique Identifier):使用标准的UUID算法生成唯一的128位标识符。UUID可以使用时间戳、MAC地址等信息来保证唯一性,但不具备可排序性。
- 雪花算法(Snowflake):雪花算法是Twitter开源的一种分布式ID生成算法。它使用一个64位的整数,结合时间戳、机器ID和序列号来生成唯一的ID。雪花算法具备可排序性和高性能,适用于分布式环境。
常见的分布式ID生成器算法包括:
- 数据库自增id,如Mysql 生产ID
- Redis生成ID
- Mongdb 生产ID
- zookeeper 生产ID
- 其他的分布式生产ID
- 分布式雪花算法
- 分布式号段算法
三:详解:常见的本地ID生成器算法
(一)uuid
UUID是一种本地生成ID的方式,
UUID(Universally Unique Identifier)的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的36个字符。
UUID的优点是:性能非常高,本地生成,没有网络消耗;
UUID的缺点是:不易于存储,信息不安全
uuid有两种包:
-
github.com/google/uuid ,仅支持V1和V4版本。
-
github.com/gofrs/uuid ,支持全部五个版本。
下面简单说下五种版本的区别:
- Version 1,基于mac地址、时间戳。
- Version 2,based on timestamp,MAC address and POSIX UID/GID (DCE 1.1)
- Version 3,Hash获取入参并对结果进行MD5。
- Version 4,纯随机数。
- Version 5,based on SHA-1 hashing of a named value。
特点
- 5个版本可供选择。
- 定长36字节,偏长。
- 无序。
参考案例:
特别说明: 尼恩社区强调 JAVA+GO+BIGDATA 三栖架构, 后面的案例,会混用go和java两种语言。
下面是go版本的uuid 算法实现。
package mian
import (
"github.com/gofrs/uuid"
"fmt"
)
func main() {
// Version 1:时间+Mac地址
id, err := uuid.NewV1()
if err != nil {
fmt.Printf("uuid NewUUID err:%+v", err)
}
// id: f0629b9a-0cee-11ed-8d44-784f435f60a4 length: 36
fmt.Println("id:", id.String(), "length:", len(id.String()))
// Version 4:是纯随机数,error会在内部报panic
id, err = uuid.NewV4()
if err != nil {
fmt.Printf("uuid NewUUID err:%+v", err)
}
// id: 3b4d1268-9150-447c-a0b7-bbf8c271f6a7 length: 36
fmt.Println("id:", id.String(), "length:", len(id.String()))
}
(二)shortuuid
-
初始值基于uuid Version4;
-
第二步根据alphabet变量长度(定长57)计算id长度(定长22);
-
第三步依次用DivMod(欧几里得除法和模)返回值与alphabet做映射,合并生成id。
特点
- 基于uuid,但比uuid的长度短,定长22字节。
特别说明: 尼恩社区强调 JAVA+GO+BIGDATA 三栖架构, 后面的案例,会混用go和java两种语言。
下面是go版本的shortuuid算法实现。
package mian
import (
"github.com/lithammer/shortuuid/v4"
"fmt"
)
func main() {
id := shortuuid.New()
// id: iDeUtXY5JymyMSGXqsqLYX length: 22
fmt.Println("id:", id, "length:", len(id))
// V22s2vag9bQEZCWcyv5SzL 固定不变
id = shortuuid.NewWithNamespace("http://127.0.0.1.com")
// id: K7pnGHAp7WLKUSducPeCXq length: 22
fmt.Println("id:", id, "length:", len(id))
// NewWithAlphabet函数可以用于自定义的基础字符串,字符串要求不重复、定长57
str := "12345#$%^&*67890qwerty/;'~!@uiopasdfghjklzxcvbnm,.()_+·><"
id = shortuuid.NewWithAlphabet(str)
// id: q7!o_+y('@;_&dyhk_in9/ length: 22
fmt.Println("id:", id, "length:", len(id))
}
(三)xid
XID(eXtended Identifier)是一个用于生成全局唯一标识符(GUID)的库。它是一个基于时间的、分布式的ID生成算法,旨在提供高性能和唯一性。
XID生成的ID是一个64位的整数,由以下部分组成:
- 时间戳(40位):使用40位存储纳秒级的时间戳,可以支持约34年的时间范围。与雪花算法不同,XID使用纳秒级时间戳,因此具有更高的时间分辨率。
- 机器ID(16位):使用16位表示机器的唯一标识符。每个机器在分布式系统中应具有唯一的机器ID,可以手动配置或通过自动分配获得。
- 序列号(8位):使用8位表示在同一纳秒内生成的序列号。如果在同一纳秒内生成的ID数量超过了8位能够表示的范围,那么会等待下一纳秒再生成ID。
xid是由时间戳、进程id、Mac地址、随机数组成。
有序性来源于对随机数部分的原子+1。
XID特点
-
长度短。
-
有序。
-
不重复。
-
时间戳这个随机数原子+1操作,避免了时钟回拨的问题。
XID生成的ID是趋势递增、唯一且可排序的,适用于分布式环境下的ID生成需求。与雪花算法相比,XID具有更高的时间分辨率,但在唯一性方面稍微弱一些,因为它使用了较短的机器ID和序列号。
XID库提供了生成ID、解析ID和验证ID的功能。
以下是使用Go语言中的XID库生成ID的示例代码:
package main
import (
"fmt"
"github.com/rs/xid"
)
func main() {
// 生成一个新的XID
id := xid.New()
// 打印生成的ID
fmt.Println(id.String())
}
上述代码导入了XID库,并使用xid.New()
函数生成一个新的XID。通过调用String()
方法,可以将XID转换为字符串形式进行打印输出。
总之,XID是一个用于生成全局唯一标识符的库,基于时间和机器ID生成唯一的ID。
(四)ksuid
KSUID(K-Sortable Unique Identifier)是一种用于生成全局唯一标识符(GUID)的算法和格式。它是由Segment.io开发的一种分布式ID生成方案,旨在提供高性能、唯一性和可排序性。
KSUID生成的ID是一个全局唯一的字符串,由以下部分组成:
- 时间戳(32位):使用32位存储秒级的时间戳,表示自协调世界时(UTC)1970年1月1日以来的秒数。与传统的UNIX时间戳相比,KSUID使用了更长的时间戳,可以支持更长的时间范围。
- 随机字节(16位):使用16位随机生成的字节,用于增加ID的唯一性。
- 附加信息(可选):在KSUID的格式中,还可以包含附加的信息,例如节点ID或其他标识符。这部分是可选的,可以根据需要进行使用。
KSUID生成的ID是按照时间顺序排序的,因此可以方便地按照生成的顺序进行排序和比较。它具有全局唯一性,并且不依赖于任何中央化的ID生成服务。
以下是使用Go语言中的github.com/segmentio/ksuid
库生成KSUID的示例代码:
package main
import (
"fmt"
"github.com/segmentio/ksuid"
)
func main() {
// 生成一个新的KSUID
id := ksuid.New()
// 打印生成的ID
fmt.Println(id.String())
}
上述代码导入了github.com/segmentio/ksuid
库,并使用ksuid.New()
函数生成一个新的KSUID。通过调用String()
方法,可以将KSUID转换为字符串形式进行打印输出。
总之,KSUID是一种用于生成全局唯一标识符的算法和格式。它具有高性能、唯一性和可排序性的特点,适用于分布式系统中的ID生成需求。通过使用github.com/segmentio/ksuid
库,可以方便地生成和操作KSUID。
(五)ulid
随机数和时间戳组成
package mian
import (
"github.com/oklog/ulid"
"fmt"
)
func main() {
t := time.Now().UTC()
entropy := rand.New(rand.NewSource(t.UnixNano()))
id := ulid.MustNew(ulid.Timestamp(t), entropy)
// id: 01G902ZSM96WV5D5DC5WFHF8WY length: 26
fmt.Println("id:", id.String(), "length:", len(id.String()))
}
(六)snowflake
大名鼎鼎的雪花算法,重点介绍。
Snowflake是Twitter开源的一种分布式ID生成算法,用于在分布式系统中生成全局唯一的ID。它的设计目标是高性能、低延迟和趋势递增的ID生成。
Snowflake生成的ID是一个64位的整数,由以下部分组成:
- 时间戳(41位):使用41位存储毫秒级的时间戳,表示自定义的起始时间(Epoch)到生成ID的时间之间的毫秒数。
- 节点ID(10位):用于标识不同的节点或机器。在分布式系统中,每个节点应具有唯一的节点ID。
- 序列号(12位):在同一毫秒内生成的序列号。如果在同一毫秒内生成的ID数量超过了12位能够表示的范围,那么会等待下一毫秒再生成ID。
Snowflake生成的ID具有趋势递增的特点,因为高位部分是基于时间戳生成的。这样设计的目的是为了在数据库索引中提供更好的性能,使新生成的ID更容易被插入到索引的末尾,减少索引的分裂和碎片化。
以下是一个使用Go语言实现Snowflake算法的简单示例:
package main
import (
"fmt"
"sync"
"time"
)
const (
epoch = int64(1609459200000) // 起始时间戳,这里使用2021年1月1日的时间戳
nodeBits = 10 // 节点ID的位数
sequenceBits = 12 // 序列号的位数
)
// Snowflake 结构体
type Snowflake struct {
mu sync.Mutex
timestamp int64
nodeID int64
sequence int64
}
// NewSnowflake 创建一个新的Snowflake实例
func NewSnowflake(nodeID int64) *Snowflake {
return &Snowflake{
timestamp: 0,
nodeID: nodeID,
sequence: 0,
}
}
// Generate 生成一个新的ID
func (sf *Snowflake) Generate() int64 {
sf.mu.Lock()
defer sf.mu.Unlock()
now := time.Now().UnixNano() / 1e6
if now < sf.timestamp {
panic("Invalid system clock")
}
if now == sf.timestamp {
sf.sequence = (sf.sequence + 1) & ((1 << sequenceBits) - 1)
if sf.sequence == 0 {
// 序列号用尽,等待下一毫秒
for now <= sf.timestamp {
now = time.Now().UnixNano() / 1e6
}
}
} else {
sf.sequence = 0
}
sf.timestamp = now
id := (now-epoch)<<nodeBits | sf.nodeID<<sequenceBits | sf.sequence
return id
}
func main() {
// 创建一个Snowflake实例,传入节点ID
sf := NewSnowflake(1)
// 生成ID并打印
id := sf.Generate()
fmt.Println(id)
}
上述示例代码实现了一个简单的Snowflake算法,通过调用Generate()
方法生成一个新的ID。在示例中,我们使用当前时间戳作为时间基准,并传入节点ID作为参数。
总之,Snowflake是一种分布式ID生成算法,用于在分布式系统中生成全局唯一的ID。它具有高性能、低延迟和趋势递增的特点,适用于需要在分布式环境下生成唯一ID的场景。
相对于UUID来说,雪花算法不会暴露MAC地址更安全、生成的ID也不会过于冗余。
雪花的一部分ID序列是基于时间戳的,那么时钟回拨的问题就来了。
snowflake 存在一个很大的问题:时钟回拨 问题
什么是 时钟回拨问题
服务器上的时间突然倒退回之前的时间:
- 可能是人为的调整时间;
- 也可能是服务器之间的时间校对。
具体来说,时钟回拨(Clock Drift)指的是系统时钟在某个时刻向回调整,即时间向过去移动。时钟回拨可能发生在分布式系统中的某个节点上,这可能是由于时钟同步问题、时钟漂移或其他原因导致的。
时钟回拨可能对系统造成一些问题,特别是对于依赖于时间顺序的应用程序或算法。
在分布式系统中,时钟回拨可能导致以下问题:
- ID冲突:如果系统使用基于时间的算法生成唯一ID(如雪花算法),时钟回拨可能导致生成的ID与之前生成的ID冲突,破坏了唯一性。
- 数据不一致:时钟回拨可能导致不同节点之间的时间戳不一致,这可能影响到分布式系统中的时间相关操作,如事件排序、超时判断等。数据的一致性可能会受到影响。
- 缓存失效:时钟回拨可能导致缓存中的过期时间计算错误,使得缓存项在实际过期之前被错误地认为是过期的,从而导致缓存失效。
为了应对时钟回拨问题,可以采取以下措施:
- 使用时钟同步服务:通过使用网络时间协议(NTP)等时钟同步服务,可以将节点的时钟与参考时钟进行同步,减少时钟回拨的可能性。
- 引入时钟漂移校正:在分布式系统中,可以通过周期性地校正节点的时钟漂移,使其保持与其他节点的时间同步。
- 容忍时钟回拨:某些应用场景下,可以容忍一定范围的时钟回拨。在设计应用程序时,可以考虑引入一些容错机制,以适应时钟回拨带来的影响。
总之,时钟回拨是分布式系统中需要关注的一个问题,可能对系统的时间相关操作、数据一致性和唯一ID生成等方面产生影响。
通过使用时钟同步服务、时钟漂移校正和容忍机制等方法,可以减少时钟回拨带来的问题。
关于时钟回拨, 咱们在 《10Wqps 推送中台架构与实操》中,做了一个非常细致、详尽的介绍,这里不做赘述。
四、分布式ID:数据库自增ID
这里常规是指数据库主键自增索引。
特点如下:
-
架构简单容易实现。
-
ID有序递增,IO写入连续性好。
-
INT和BIGINT类型占用空间较小。
-
由于有序递增,易暴露业务量。
-
受到数据库性能限制,对高并发场景不友好。
-
bigint最大是2^64-1,但是数据库单表肯定放不了这么多,那么就涉及到分表。如果业务量真的太大了,主键的自增id涨到头了,会发生什么?报错:主键冲突。
五、分布式ID:Redis生成ID
通过redis的原子操作INCR和INCRBY获得id。
相比数据库自增ID,redis性能更好、更加灵活。
不过架构强依赖redis,redis在整个架构中会产生单点问题。
在流量较大的场景下,网络耗时也可能成为瓶颈。
六、分布式ID:ZooKeeper唯一ID
ZooKeeper是使用了Znode结构中的Zxid实现顺序增ID。
Zookeeper类似一个文件系统,每个节点都有唯一路径名(Znode),Zxid是个全局事务计数器,每个节点发生变化都会记录响应的版本(Zxid),这个版本号是全局唯一且顺序递增的。
这种架构还是出现了ZooKeeper的单点问题。
七、分布式雪花算法
虽然Snowflake 可以很容易扩展成为分布式架构
- Snowflake + 机器固定编号
- Snowflake +zookeeper 自增编号
- Snowflake + 数据库 自增编号
- ....
分布式雪花算法的代表作:百度的 UidGenerator
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。
UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。
在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
40岁老架构师尼恩提示:有关百度的 UidGenerator的底层原理、具体使用,
稍后一点详细介绍。
7.1 分布式雪花ID方案1: 600万qps的百度 UidGenerator
UidGenerator是Java实现的, 基于Snowflake算法的唯一ID生成器。
UidGenerator以组件形式工作在应用项目中, 支持自定义workerId位数和初始化策略, 从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。
在实现上, UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐,避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
依赖版本:
回顾Snowflake算法
Snowflake算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可生成一个64 bits的唯一ID(long)。
默认采用上图字节分配方式:
- sign(1bit)
固定1bit符号标识,即生成的UID为正数。
- delta seconds (28 bits)
当前时间,相对于时间基点"2016-05-20"的增量值,单位:秒,最多可支持约8.7年 - worker id (22 bits)
机器id,最多可支持约420w次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。 - sequence (13 bits)
每秒下的并发序列,13 bits可支持每秒8192个并发。
以上参数均可通过Spring进行自定义
CachedUidGenerator
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
CachedUidGenerator采用了双RingBuffer,Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)
由于数组元素在内存中是连续分配的,可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题,为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine补齐方式。
RingBuffer填充时机
- 初始化预填充
RingBuffer初始化时,预先填充满整个RingBuffer. - 即时填充
Take消费时,即时检查剩余可用slot量(tail
-cursor
),如小于设定阈值,则补全空闲slots。阈值可通过paddingFactor
来进行配置,请参考Quick Start中CachedUidGenerator配置 - 周期填充
通过Schedule线程,定时补全空闲slots。可通过scheduleInterval
配置,以应用定时填充功能,并指定Schedule时间间隔
UidGeneratorQuick Start
这里介绍如何在基于Spring的项目中使用UidGenerator, 具体流程如下:
步骤1: 安装依赖
设置环境变量
maven无须安装, 设置好MAVEN_HOME即可. 可像下述脚本这样设置JAVA_HOME和MAVEN_HOME, 如已设置请忽略.
export MAVEN_HOME=/xxx/xxx/software/maven/apache-maven-3.3.9
export PATH=$MAVEN_HOME/bin:$PATH
JAVA_HOME="/Library/Java/JavaVirtualMachines/jdk1.8.0_91.jdk/Contents/Home";
export JAVA_HOME;
步骤2: 创建表WORKER_NODE
运行sql脚本以导入表WORKER_NODE, 脚本如下:
DROP DATABASE IF EXISTS `xxxx`;
CREATE DATABASE `xxxx` ;
use `xxxx`;
DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
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 TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
)
COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;
修改mysql.properties配置中, jdbc.url, jdbc.username和jdbc.password, 确保库地址, 名称, 端口号, 用户名和密码正确.
步骤3: 修改Spring配置
提供了两种生成器: DefaultUidGenerator、CachedUidGenerator。
如对UID生成性能有要求, 请使用CachedUidGenerator
对应Spring配置分别为: https://github.com/baidu/uid-generator/blob/master/default-uid-spring.xml、cached-uid-spring.xml
DefaultUidGenerator配置
<!-- DefaultUidGenerator -->
<bean id="defaultUidGenerator" class="com.baidu.fsg.uid.impl.DefaultUidGenerator" lazy-init="false">
<property name="workerIdAssigner" ref="disposableWorkerIdAssigner"/>
<!-- Specified bits & epoch as your demand. No specified the default value will be used -->
<property name="timeBits" value="29"/>
<property name="workerBits" value="21"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>
</bean>
<!-- 用完即弃的WorkerIdAssigner,依赖DB操作 -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />
CachedUidGenerator配置
<!-- CachedUidGenerator -->
<bean id="cachedUidGenerator" class="com.baidu.fsg.uid.impl.CachedUidGenerator">
<property name="workerIdAssigner" ref="disposableWorkerIdAssigner" />
<!-- 以下为可选配置, 如未指定将采用默认值 -->
<!-- Specified bits & epoch as your demand. No specified the default value will be used -->
<property name="timeBits" value="29"/>
<property name="workerBits" value="21"/>
<property name="seqBits" value="13"/>
<property name="epochStr" value="2016-09-20"/>
<!-- RingBuffer size扩容参数, 可提高UID生成的吞吐量. -->
<!-- 默认:3, 原bufferSize=8192, 扩容后bufferSize= 8192 << 3 = 65536 -->
<property name="boostPower" value="3"></property>
<!-- 指定何时向RingBuffer中填充UID, 取值为百分比(0, 100), 默认为50 -->
<!-- 举例: bufferSize=1024, paddingFactor=50 -> threshold=1024 * 50 / 100 = 512. -->
<!-- 当环上可用UID数量 < 512时, 将自动对RingBuffer进行填充补全 -->
<property name="paddingFactor" value="50"></property>
<!-- 另外一种RingBuffer填充时机, 在Schedule线程中, 周期性检查填充 -->
<!-- 默认:不配置此项, 即不实用Schedule线程. 如需使用, 请指定Schedule线程时间间隔, 单位:秒 -->
<property name="scheduleInterval" value="60"></property>
<!-- 拒绝策略: 当环已满, 无法继续填充时 -->
<!-- 默认无需指定, 将丢弃Put操作, 仅日志记录. 如有特殊需求, 请实现RejectedPutBufferHandler接口(支持Lambda表达式) -->
<property name="rejectedPutBufferHandler" ref="XxxxYourPutRejectPolicy"></property>
<!-- 拒绝策略: 当环已空, 无法继续获取时 -->
<!-- 默认无需指定, 将记录日志, 并抛出UidGenerateException异常. 如有特殊需求, 请实现RejectedTakeBufferHandler接口(支持Lambda表达式) -->
<property name="rejectedTakeBufferHandler" ref="XxxxYourTakeRejectPolicy"></property>
</bean>
<!-- 用完即弃的WorkerIdAssigner, 依赖DB操作 -->
<bean id="disposableWorkerIdAssigner" class="com.baidu.fsg.uid.worker.DisposableWorkerIdAssigner" />
Mybatis配置
mybatis-spring.xml配置说明如下:
<!-- Spring annotation扫描 -->
<context:component-scan base-package="com.baidu.fsg.uid" />
<bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">
<property name="dataSource" ref="dataSource" />
<property name="mapperLocations" value="classpath:/META-INF/mybatis/mapper/M_WORKER*.xml" />
</bean>
<!-- 事务相关配置 -->
<tx:annotation-driven transaction-manager="transactionManager" order="1" />
<bean id="transactionManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager">
<property name="dataSource" ref="dataSource" />
</bean>
<!-- Mybatis Mapper扫描 -->
<bean class="org.mybatis.spring.mapper.MapperScannerConfigurer">
<property name="annotationClass" value="org.springframework.stereotype.Repository" />
<property name="basePackage" value="com.baidu.fsg.uid.worker.dao" />
<property name="sqlSessionFactoryBeanName" value="sqlSessionFactory" />
</bean>
<!-- 数据源配置 -->
<bean id="dataSource" parent="abstractDataSource">
<property name="driverClassName" value="${mysql.driver}" />
<property name="maxActive" value="${jdbc.maxActive}" />
<property name="url" value="${jdbc.url}" />
<property name="username" value="${jdbc.username}" />
<property name="password" value="${jdbc.password}" />
</bean>
<bean id="abstractDataSource" class="com.alibaba.druid.pool.DruidDataSource" destroy-method="close">
<property name="filters" value="${datasource.filters}" />
<property name="defaultAutoCommit" value="${datasource.defaultAutoCommit}" />
<property name="initialSize" value="${datasource.initialSize}" />
<property name="minIdle" value="${datasource.minIdle}" />
<property name="maxWait" value="${datasource.maxWait}" />
<property name="testWhileIdle" value="${datasource.testWhileIdle}" />
<property name="testOnBorrow" value="${datasource.testOnBorrow}" />
<property name="testOnReturn" value="${datasource.testOnReturn}" />
<property name="validationQuery" value="${datasource.validationQuery}" />
<property name="timeBetweenEvictionRunsMillis" value="${datasource.timeBetweenEvictionRunsMillis}" />
<property name="minEvictableIdleTimeMillis" value="${datasource.minEvictableIdleTimeMillis}" />
<property name="logAbandoned" value="${datasource.logAbandoned}" />
<property name="removeAbandoned" value="${datasource.removeAbandoned}" />
<property name="removeAbandonedTimeout" value="${datasource.removeAbandonedTimeout}" />
</bean>
<bean id="batchSqlSession" class="org.mybatis.spring.SqlSessionTemplate">
<constructor-arg index="0" ref="sqlSessionFactory" />
<constructor-arg index="1" value="BATCH" />
</bean>
步骤4: 运行示例单测
运行单测CachedUidGeneratorTest, 展示UID生成、解析等功能
@Resource
private UidGenerator uidGenerator;
@Test
public void testSerialGenerate() {
// Generate UID
long uid = uidGenerator.getUID();
// Parse UID into [Timestamp, WorkerId, Sequence]
// {"UID":"180363646902239241","parsed":{ "timestamp":"2017-01-19 12:15:46", "workerId":"4", "sequence":"9" }}
System.out.println(uidGenerator.parseUID(uid));
}
7.2 分布式雪花ID方案2:美团 Leaf-snowflake
美团 Leaf-snowflake方案,属于 Snowflake +zookeeper 自增编号 的类型。
美团 Leaf-snowflake架构
-
用Zookeeper顺序增、全局唯一的节点版本号,替换了原有的机器地址。
-
强依赖ZooKeeper的缺点:强依赖ZooKeeper、大流量下的网络下,存在网络瓶颈。
-
解决了时钟回拨的问题。运行时运行时,时差小于5ms会等待时差两倍时间,如果时差大于5ms报警并停止启动。
-
通过缓存一个ZooKeeper文件夹,提高可用性。
Leaf-snowflake方案完全沿用snowflake方案的bit位设计,即是“1+41+10+12”的方式组装ID号。
对于workerID的分配,当服务集群数量较小的情况下,完全可以手动配置。Leaf服务规模较大,动手配置成本太高。
所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。
Leaf-snowflake是按照下面几个步骤启动的:
- 启动Leaf-snowflake服务,连接Zookeeper,在leaf_forever父节点下检查自己是否已经注册过(是否有该顺序子节点)。
- 如果有注册过直接取回自己的workerID(zk顺序节点生成的int类型ID号),启动服务。
- 如果没有注册过,就在该父节点下面创建一个持久顺序节点,创建成功后取回顺序号当做自己的workerID号,启动服务。
从强依赖ZooKeeper优化为弱依赖ZooKeeper
除了每次会去ZK拿数据以外,也会在本机文件系统上缓存一个workerID文件。
当ZooKeeper出现问题,恰好机器出现问题需要重启时,能保证服务能够正常启动。
这样做到了对三方组件的弱依赖。
一定程度上提高了 系统的可用性。
解决时钟问题
因为这种方案依赖时间,如果机器的时钟发生了回拨,那么就会有可能生成重复的ID号,需要解决时钟回退的问题。
参见上图整个启动流程图,服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点:
- 若写过,则用自身系统时间与
leaf_forever/${self}
节点记录时间做比较,若小于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}
。
由于强依赖时钟,对时间的要求比较敏感,在机器工作时NTP同步也会造成秒级别的回退,建议可以直接关闭NTP同步。
要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE,等时钟追上即可。
或者做一层重试,然后上报报警系统,更或者是发现有时钟回拨之后自动摘除本身节点并报警,如下:
//发生了回拨,此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
//时间偏差大小小于5ms,则等待两倍时间
wait(offset << 1);//wait
timestamp = timeGen();
if (timestamp < lastTimestamp) {
//还是小于,抛异常并上报
throwClockBackwardsEx(timestamp);
}
} catch (InterruptedException e) {
throw e;
}
} else {
//throw
throwClockBackwardsEx(timestamp);
}
}
//分配ID
从上线情况来看,在2017年闰秒出现那一次出现过部分机器回拨,由于Leaf-snowflake的策略保证,成功避免了对业务造成的影响。
八、分布式ID:号段模式
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
(一)Leaf-segment(叶段模式)
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
(二)增强版Leaf-segment
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
(三)滴滴 Tinyid 号段模式
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
8.1 美团Leaf-segment
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
Leaf-segment数据库方案
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
双buffer优化
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
Leaf高可用容灾
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
8.2 Tinyid:滴滴1000W级qps的分布式ID生成器
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
运行Tinyid
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
1. 导入SQL
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
2. mysql依赖
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
3. 修改配置
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
4. 启动tinyid
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
5. 获取唯一ID
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
Client集成
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
tinyid原理
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
优化手段一:号段
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
优化手段二:双缓存
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
优化手段三:多db支持
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
优化手段四:分布式部署
由于字数限制,具体请参见 完整版PDF: 《分布式ID学习圣经: 1000w级qps高并发ID如何生成?》
说在最后
分布式ID,也是面试的重点和高频点。
(1) 一个分布式ID生成系统,如何实现?
(2) 分布式ID系统,如何实现高并发?
(3) 分布式ID系统,如何实现高可用?
等等等等.....
参照上文的答案,如果大家能对答如流,最终,让面试官爱到 “不能自已、口水直流”。 offer, 也就来了。
完整版PDF,请到公号【技术自由圈】获取。
作者介绍:
本文1作: Andy,资深架构师, 《Java 高并发核心编程 加强版》作者之1 。
本文2作: 尼恩,41岁资深老架构师, 《Java 高并发核心编程 加强版 卷1、卷2、卷3》创世作者, 著名博主 。 《K8S学习圣经》《Docker学习圣经》《Go学习圣经》等11个PDF 圣经的作者。 也是一个超级 架构转化 导师, 已经指导了大量小伙伴成功 转型架构师, 指导的最高年薪近100W。
技术自由的实现路径 PDF:
实现你的 响应式 自由:
这是老版本 《Flux、Mono、Reactor 实战(史上最全)》
实现你的 spring cloud 自由:
《Spring cloud Alibaba 学习圣经》 PDF
《分库分表 Sharding-JDBC 底层原理、核心实战(史上最全)》
《一文搞定:SpringBoot、SLF4j、Log4j、Logback、Netty之间混乱关系(史上最全)》
实现你的 linux 自由:
实现你的 网络 自由:
《网络三张表:ARP表, MAC表, 路由表,实现你的网络自由!!》
实现你的 分布式锁 自由:
实现你的 王者组件 自由:
《队列之王: Disruptor 原理、架构、源码 一文穿透》
《缓存之王:Caffeine 源码、架构、原理(史上最全,10W字 超级长文)》
《Java Agent 探针、字节码增强 ByteBuddy(史上最全)》