滴滴太狠：分布式ID，如何达到1000Wqps？

架构师尼恩 12-14 1943

前言：

此刻我们对“java使用ulid”大体比较关怀，朋友们都需要分析一些“java使用ulid”的相关资讯。那么小编在网摘上搜集了一些关于“java使用ulid””的相关内容，希望我们能喜欢，咱们快快来了解一下吧！

▌背景：

在40岁老架构师尼恩的读者社区（50+）中，很多小伙伴拿不到offer，或者拿不到好的offer。

尼恩经常给大家优化项目，优化简历，挖掘技术亮点。在指导简历的过程中，高并发、分布式核心组件是一项很重要的指导。

在所有的高并发、分布式核心组件：分布式ID 是核心中的核心、重点中的重点。

分布式ID 组件，是整个系统黄金链路上的关键组件、黄金组件，

如果分布式ID 组件出现问题，整个黄金链路上关键动作都无法执行，这就会带来一场灾难，一定是P0级大灾难。

对于架构师、高级开发来说，分布式ID的方案和架构，是重点中的重点，更是内功中的内功。

分布式ID，也是面试的重点和高频点。比如，近段时间尼恩社区中有很多小伙伴在面试滴滴、美团、网易等大厂时候，就遇到很多类似问题：

(1) 一个分布式ID生成系统，如何实现？

(2) 分布式ID系统，如何实现高并发？

(3) 分布式ID系统，如何实现高可用？

等等等等.....

尼恩团队结合资深架构经验和行业案例，给大家梳理一个体系化、系统化的参考答案，

并且组成一个电子书《分布式ID学习圣经：1000w级qps高并发ID如何生成》PDF 电子书，帮助大家顺利通过面试，拿到心仪的offer，

并且最终顺利转型三栖架构师。

《尼恩架构笔记》《尼恩高并发三部曲》《尼恩面试宝典》的PDF文件，请到公号【技术自由圈】取

▌本文目录：

- 背景：- 一：超高并发、超高性能分布式ID生成系统的要求  - 超高并发、超高性能分布式ID生成系统三个超高- 二：什么是本地ID生成器、分布式ID生成器  - 常见的本地ID生成器算法包括  - 常见的分布式ID生成器算法包括- 三：详解：常见的本地ID生成器算法  - （一）uuid  - （二）shortuuid  - （三）xid  - （四）ksuid  - （五）ulid  - （六）snowflake- 四、分布式ID：数据库自增ID- 五、分布式ID：Redis生成ID- 六、分布式ID：ZooKeeper唯一ID- 七、分布式雪花算法- 7.1 分布式雪花ID方案1： 600万qps的百度 UidGenerator  - 回顾Snowflake算法  - CachedUidGenerator    - RingBuffer填充时机  - UidGeneratorQuick Start    - 步骤1: 安装依赖    - 步骤2: 创建表WORKER_NODE    - 步骤3: 修改Spring配置    - 步骤4: 运行示例单测  - 7.2 分布式雪花ID方案2：美团 Leaf-snowflake    - 美团 Leaf-snowflake架构    - 从强依赖ZooKeeper优化为弱依赖ZooKeeper    - 解决时钟问题- 八、分布式ID：号段模式  - （一）Leaf-segment（叶段模式）  - （二）增强版Leaf-segment  - （三）滴滴 Tinyid 号段模式- 8.1 美团Leaf-segment  - Leaf-segment数据库方案  - 双buffer优化  - Leaf高可用容灾- 8.2 Tinyid：滴滴1000W级qps的分布式ID生成器  - 运行Tinyid  - 1. 导入SQL  - 2. mysql依赖  - 3. 修改配置  - 4. 启动tinyid  - 5. 获取唯一ID  - Client集成  - tinyid原理    - 优化手段一：号段    - 优化手段二：双缓存    - 优化手段三：多db支持    - 优化手段四：分布式部署- 说在最后- 作者介绍- 11个技术圣经 PDF

▌一：超高并发、超高性能分布式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 生产IDRedis生成IDMongdb 生产IDzookeeper 生产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 mianimport (    "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(";)    // 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 mainimport ( "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 mainimport ( "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 mainimport ( "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 生成一个新的IDfunc (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等虚拟化环境下实例自动重启、漂移等场景。

依赖版本：

Java8 及以上版本,MySQL (内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）

▌回顾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指定PutRejectPolicyCursor指针

表示Consumer消费到的最小序号(序号序列与Producer序列相同)。Cursor不能超过Tail，即不能消费未生产的slot。当Cursor已赶上tail，此时可通过rejectedTakeBufferHandler指定TakeRejectPolicy

RingBuffer

CachedUidGenerator采用了双RingBuffer，Uid-RingBuffer用于存储Uid、Flag-RingBuffer用于存储Uid状态(是否可填充、是否可消费)

由于数组元素在内存中是连续分配的，可最大程度利用CPU cache以提升性能。但同时会带来「伪共享」FalseSharing问题，为此在Tail、Cursor指针、Flag-RingBuffer中采用了CacheLine补齐方式。

FalseSharing

▌RingBuffer填充时机

初始化预填充

RingBuffer初始化时，预先填充满整个RingBuffer.即时填充

Take消费时，即时检查剩余可用slot量(tail - cursor)，如小于设定阈值，则补全空闲slots。阈值可通过paddingFactor来进行配置，请参考Quick Start中CachedUidGenerator配置周期填充

通过Schedule线程，定时补全空闲slots。可通过scheduleInterval配置，以应用定时填充功能，并指定Schedule时间间隔

▌UidGeneratorQuick Start

这里介绍如何在基于Spring的项目中使用UidGenerator, 具体流程如下:

▌步骤1: 安装依赖

先下载Java8 、 MySQL 和 Maven

◆设置环境变量

maven无须安装，设置好MAVEN_HOME即可。可像下述脚本这样设置JAVA_HOME和MAVEN_HOME，如已设置请忽略.

export MAVEN_HOME=/xxx/xxx/software/maven/apache-maven-3.3.9export PATH=$MAVEN_HOME/bin:$PATHJAVA_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配置分别为: 、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生成、解析等功能

@Resourceprivate UidGenerator uidGenerator;@Testpublic 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的分配，当服务cluster数量较小的情况下，完全可以手动配置。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：号段模式