分布式唯一 ID 生成算法也就那么几种，我也不过多解释，想了解可以看美团的这篇文章 https://tech.meituan.com/2017/04/21/mt-leaf.html

我今天要讲的算法类似美团的 Leaf-segment 的数据库方案，简要说就是各个节点都去唯一的数据库取一个 ID 段，然后自己分配。

这套算法在老东家的时候就见过，没啥稀奇的，之前是用于生成游戏玩家 ID 的。现在分享的这个实现也是参考现在老大写的代码（其实就是抄的）。

如果不做预生成处理，同样也会出现 Leaf-segment 里说的 TP999 指标问题（TP999 就是满足千分之九百九十九的网络请求所需要的最低耗时），所以也做了快要消耗完 ID 段时就去申请一个新的 ID 出来。

数据库结构

数据库的表结构是这样的，给 idtype 设置唯一索引：

• idtype 用来区分业务的，比如我这里的 uid 用来表示角色 ID 申请的号段，teamid 用来表示队伍 ID 申请的号段。
• nextid 用来表示下一次申请的 ID 的最小值。

数据库是单点，所以需要做集群，比如 MySQL 的主从， MongoDB 的分片集群。

为啥只需要一个 nextid 就可以了？不用保存 step 吗？因为 step 配置到代码里就行了的，就没必要入库了。

预生产池子

直接贴 Lua 的数据结构吧，就不画图了。

{
   [idtype] = {
     blocks = {
        [start_idx] = len,  -- 有效数据, 表示从某段开始, 长度为len, 使用时段内自减
     },
     cur_idx = 0,  -- 记录当前在使用的段ID, 优先使用低段位
     step = step,  -- 每次从 db 取的 id 数量
     ids_cnt = 0,  -- 当前ID总数，当总数不足 step/10 时, 自动申请
   }
}

• start_idx表示分段的起点，对应的 len 就是这个段的长度，len 是逐步递减到 1 就删除这个号段的，所以分配的第一个 ID 是 start_idx + len，最后分配的一个是 start_idx + 1。
• cur_idx 记录的是当前使用的段ID，是 blocks 里最小的 start_idx。
• step 是一个配置的每次从 db 取的 id 数量
• ids_cnt 用来维护池子的大小

从 db 取一段 ID

local function new_db_id(idtype, step)
    local ret = tbl_guid:findAndModify({query = {idtype = idtype}, update = {["$inc"] = {nextid = step}}, upsert = true})

    local result = math.floor(ret.ok)
    if result ~= 1 then
        skynet.error("new_db_id not ret. idtype:", idtype, ",step:", step, ",msg:", ret.errmsg)
        return
    end

    if not ret.value.nextid then
        skynet.error("new_db_id failed. ignore first step. idtype:", idtype, ",step:", step)
        return
    end

    return ret.value.nextid
end

用了 MongoDB 数据库的 findAndModify 和 $inc 指令。这里有个取巧，首次初始化数据库时会进入 "new_db_id failed" 逻辑，从而达到忽略第一段 ID，相当于 step 是步长也是最小值。

为了实现这个初始化目的，还用了个取巧的地方，进程启动的时候，如果是首次初始化数据库，会执行 2 次生成函数，从而达到调用 2 次 new_db_id 函数。

我这样做的目的就是因为 MongoDB 的 upsert 不能做指定的初始值。当然也有其他方法实现，就是不用 upsert，手动 insert。

算法用到的理论点到这就讲完了，具体的实现就去看代码吧。这个库是专门给 skynet 使用的，所以用到了许多 skynet 特有的接口。

忘记贴代码地址了，代码在这里 https://github.com/hanxi/skynet-demo/blob/master/service/guidd.lua

鉴于有些时候还是需要用到时间是大致递增的情况，可以考虑配合时间戳来生成 ID