Leaf分布式ID

系统对Id号的要求

1、业务

1）全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求

2）趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能

3）单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求

• 数据自增id

4）信息安全：如果ID是连续的， 竞对在两天中午12点分别下单，通过订单id号相减就能大致计算出公司一天的订单量 。所以在一些应用场景下，会需要ID无规则

• UUID或雪花算法

2、可靠性

• 平均延迟和TP999延迟都要尽可能低
• 可用性5个9
• 高QPS

UUID

1、定义

36个字符，示例：550e8400-e29b-41d4-a716-446655440000

public class IdUtil {/** 返回使用ThreadLocalRandom的UUID，比默认的UUID性能更优*/public static UUID fastUUID() {ThreadLocalRandom random = ThreadLocalRandom.current();return new UUID(random.nextLong(), random.nextLong());}
}

2、缺点

• 太长，不易于存储
• 无序性，如果作为数据库主键，可能会引起数据页位置频繁变动，严重影响性能
• 信息不安全，基于MAC地址生成UUID的算法可能会造成MAC地址泄露

snowflake

1、结构

Long型64位的整数，如图1所示

• 41-bit的时间戳

  可以表示（1L<<41）/(1000L360024*365)=69年的时间

• 10-bit 数据中心ID和机器

  5bit数据中心id，5bit机器id，一般使用ZK分配

• 12个自增序列号

  在同一毫秒内生成2^12个唯一的ID

理论上snowflake方案的QPS约为409.6w/s，可以保证在任何一个IDC、任何一台机器、在任意毫秒内、生成的ID都是不同的

2、问题

41-bit时间戳部分，强依赖机器时钟，如果机器上时钟回拨，会导致发号重复

Leaf

使用参考：Leaf生成单据号

Leaf-snowflake

1、适合场景：生成的ID需要无规则

2、解决机器时钟回拨问题

1）要求当前时间戳，必须 > 机器创建时间

2）同时

• 对比其余Leaf节点的系统时间，来判断自身系统时间是否准确
• RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize < 阈值，则认为正确

阈值 = 5ms

因为理论上5ms内无法，完全使用完成后12个自增序列号，所以不会重复

否则直接报错自动摘除本身节点并报警

Leaf-segment

1、适合场景：生成的ID单调递增

2、实现：基于MySQL的自增主键

MySQL自增主键

1、获取ID方式

使用下列SQL读写MySQL得到ID号

begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;

• Tickets64：表
• stub：列

实现方式类似：

useGeneratedKeys=“true“ keyProperty=“id“

• int insert(XxxDO xxxDo)时，先将DO内容写入db
• insert成功后，再将JDBC自增主键值AUTO_INCREMENT，回写到DO的id属性字段
• 后续可能会从DO中获取此id值进行查询数据、编辑数据

2、存在问题

因为每次都是都需要写，读MySQL才能获取ID值，单台MySQL的读写性能是瓶颈

3、解决-集群

• 在分布式系统中多部署几台机器

• 每台机器设置不同的初始值，且步长和机器数相等

  比如有两台机器。设置步长step为2，TicketServer1的初始值为1（1，3，5，7，9，11…）

  TicketServer2的初始值为2（2，4，6，8，10…）

• 假设部署N台机器，步长需设置为N，每台的初始值依次为0,1,2…N-1 ，则整个Leaf架构如图2
  

4、存在问题

• 数据库压力还是很大，每次获取ID都得读写一次数据库，只能靠堆机器来提高性能
• 系统水平扩展比较困难，定义好了步长和机器台数之后，如果要添加机器不好做

5、解决- 批量分段（segment）获取

---

segment

1、实现，如图3所示

1）db表设计

+-------------+--------------+------+-----+-------------------+-------------------------
| 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 

• biz_tag用来区分业务（外卖、支付）
• max_id表示该biz_tag目前所被分配的ID号段的最大值

UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx

• step表示每次分配的号段长度

2）系统架构

3） ID值趋势递增

eg：test_tag业务

• Leaf Server 1：从DB加载号段[1，1000]。
• Leaf Server 2：从DB加载号段[1001，2000]。
• Leaf Server 3：从DB加载号段[2001，3000]。

用户通过Round-robin的方式调用Leaf Server的各个服务，通过CAS获取ID，所以某一个Client获取到的ID序列

可能是：1，1001，2001，2，1002，2002……

也可能是：1，2，1001，2001，2002，2003，3，4…

当某个Leaf Server号段用完之后，下一次请求就会从DB中加载新的号段，这样保证了每次加载的号段是递增

2、解决-读写性能

• 原来获取一个ID值，都需要读写一次数据库

• 现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次

  读写数据库的频率从1减小到了1/step

• test_tag业务，在第一台Leaf机器上是1~1000的号段，当这个号段用完时

• 会去加载另一个长度为step=1000的号段

• 假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001~4000

• 同时数据库对应的biz_tag = test_tag 这条数据的max_id会从3000被更新成4000

3、 解决-扩容操作

只需要对biz_tag分库分表

4、问题

• 在号段消耗完的时候进行取号段时，还是会夯在更新数据库的I/O上

• 假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢

5、解决-双buffer

---

双buffer

1、解决-双buffer

• 当其中一个Buffer中的号段消费到某个点（90%）时，就启异步线程的把下一个号段加载到内存中的另一个Buffer

2、 容灾

分库分表

4、问题

• 在号段消耗完的时候进行取号段时，还是会夯在更新数据库的I/O上

• 假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢