分布式ID生成器的剖析与设计

2022-01-24 22:58:38

ID是身份标识，你所涉及的每类业务都会有一个，身份证，手机号， QQ号。那么问题来了，如何设计一个算法，能快速生成ID又能有效地避免冲突。
往小了说，在存储领域每一行数据都会有一个ID，关系型数据库有 auto increment，非关系型数据库，如mongodb有自己的objectID 算法。
对于各种ID我们可以简化为2类：
1.去中心化，统一长度，规则占坑类， mongodb属于这一类， guid 属于这类类。
2.中心化，ID自增，auto increment属于这一类。

mongodb id

mongodb的ID规则

长度(byte)	含义
4	unix epoch到当前的秒数
3	机器标识
2	进程标识
3	扩展计数

机器标识可以防止不同机器出现相同ID，进程标识则可以在同一台机器上防止出现冲突。
对于这种设计，我想说 good! 无论是单机还是分布式都可以很有效地解决冲突的问题。

即使同一时刻有很多请求，不同机器也不会产生相同的ID，达到了去中心化的ID生成能力。

类似的设计还有twitter snowflake:

长度(bit)	含义
41	unix epoch到当前的毫秒数
10	节点ID
12	sequence

也做到了不同节点去重，不同时间有序，只是把节点ID的制定交给了使用者。

mysql auto seq
相信大部分研发同学都使用过mysql，auto increment可以有效地解决ID生成。

CREATE TABLE animals (
     id MEDIUMINT NOT NULL AUTO_INCREMENT,
     name CHAR(30) NOT NULL,
     PRIMARY KEY (id)
);

id会从1开始自增，所以单台Server的情况下是不会有冲突的可能的。

这样的设计一度非常常见于各种前端技术，用过LAMP技术栈的同学应该记得，目前仍被mysql, redis等广泛使用。

引申

第一种方案是于空间时间相关的，类似于身份证

把坑给你空好，生成机制设计好，生成ID就变成了按机制生成数字填坑，只要时间不停摆，人口不会短时间内爆增，这个ID就很难重复。

等于把冲突保障交给了系统。

第二种方案与时空无关，只要生成器还在，就可以一直生产数据，冲突由生成器保障。

问题抛出

系统不可靠

以mongodb为例

长度(byte)	含义	依赖
4	unix	epoch到当前的秒数	系统时间
3	机器标识
2	进程标识
3	扩展计数

如果因为操作不当，人为把机器的当前时间修改成过去某个时间，其新生成ID的时间部分就有可能冲突。

举例来说，某一年的公历出现了润8月（不可能出现），则8月出生的小朋友就要身份证重号了，现终于知道为什么身份证不使用农历了吧，哟呵呵。

自增的瓶颈

自增形式的生成器很可能成为瓶颈，争对单点的问题业界已经有一些方案，比如分片自增

有3个节点 p1, p2, p3, 生成的ID规则：

p1: 1,4,7,10,13,16,19,22

p2: 2,5,8,11,14,17,20,23

p3:3,6,9,12,15,18,21,24

既使节点A崩溃了，只要有一个节点还在，系统就能工作。

但是不太好扩展，如果一开始只分配了3台机器，后面系统达到瓶颈了添加机器，就比较麻烦了。

ID的意义

在分布式系统中，ID往往有很多意义，比如散列，如何精确地的把按ID的查询散列到某台机器上去，因此在一些场景下ID需要包含机器信息，第一类去中心化ID生成器很好的解决了此类问题。

另外，有时候需要从ID知道系统的数据规模，自增的ID能较好的解决此类问题。

从安全角度上看，不同场景下ID应该有不同的表述，避免被外部猜测。比如微信号在第三方服务中是不能被直接使用的，而是一个64字节不具备查询意义的open id。

能不能有一个ID机器既能满足散列，又能反映数据规模呢，我想是可以的。

本来只想分享一下现行的生成规则，作为文章的附加，我简单设计了一个有效的ID生成器。

分布式ID的设计

设计方向

快速生成，不冲突。

既使系统时间被重置，也不会冲突。

能从最新的ID拿到当前的数据规模。

支持不同场景不同表述。

结构设计

长度(byte)	含义	意义
4	unix epoch到当前的秒数	去中心化
3	机器标识
2	进程标识
3	扩展计数
8	统一分配全局ID	中心化

设计思想

设计上将中心化与去中心化结合，对外展示去中心化的ID，对内展示全部，对统计展示中心化ID。

分配架构

全局ID统一分配器设计

作为中心化的瓶颈，必须由机器保障其功能可靠。

各个节点从全局ID分配器批量获取ID作为预分配资源，当节点剩余预留ID低于阈值时再次申请。

节点分配设计

void Pot::onRequest(long& conID, long& reqID){
    
    uint64_t  id = cache.incr();     //预留ID自增
    if(id <= 0){                     //预留ID不够
        cache.distribute([this, &conID, &reqID](uint64_t id, uint32_t err){                            //请求后端申请全局分配预留片，并设置好回调
                        this->response(conID, reqID, id);
                });                //向全局请求分本书
        return;
    }

    if(cache.shouldDistribute()){                //检查预留池是否达到申请阈值 
        cache.distribute();                        //向后端申请全局分配预留片
    }

    response(conID, reqID, id);       //返回
}

全局分配器工作原理

工作原理也是一样简单

void Distribute::onRequest(long& conID, long& reqID){
    uint64_t  minID, maxID, err;
    uint32_t flag = db.pre(minID, maxID, err);     //预分配ID片
    if(flag <= 0){                       //是否出错
        response(conID, reqID, err);    //返回
        return;
    }
 
    response(conID, reqID, minID, maxID);       //返回ID片
}

崩溃处理机制

单节点崩溃，其他节点仍能崩溃，这个比较简单。

全局分配器的崩溃处理需要在设计上保障，可以同时并存几个全局生成器，且并不缓存当前最大分配ID，该值由数据库来存储。

全局分配的请求是个低频处理器。

假设工作节点数为N，系统每秒处理并发为Concurrent, 全局分配器的请求频次F，每次分配ID片长度为P, 全局分配器个数为M，则有下列公式：

F=Concurrent/(NPM)

假设每秒并发数为100万（1秒产生100万个ID，1秒新增100万个用户，实际不可能），有5个工作节点，全局分配器个数为4，每次申请ID片为10000。

F=1000,000 / (5 100004) ＝5.

100万每秒的分配也只有每秒几次的请求，而且P的值可以灵活修改，假设P＝100,000(每片10万个ID），则每秒1个请求都没有了。

这种情况下对全局分配的安全只需要对数据主从热备就行了。

理论退化
将上面的规则重新审视一下：

字段	长度(byte)		备注
time	4	unix epoch到当前的秒数	去中心化
machine	3	机器标识
process	2	进程标识
count	3	扩展计数
center id	8	统一分配全局ID	中心化

如果只有前4个，去掉center 只退化成了mongodb的去中心化ID生成器。

如果去掉前四项，保留center id,则退化成了具备分布式功能的中心化ID生成器。

在一些简单的业务里，可以只需要在这2者中选一个就可以满足分布式业务的处理。

码农公寓