欣赏下几种 UID 的实现

啊~ UID，你比 ID 多一位，   
啊~ UID，你比 UUID 少一位。   
                                         --无名吹水师

我这几年工作中常常用到 UID ，虽有不少开源实现，但在不同场合使用哪种方案总免不了计较下。因此留篇水文做点浅薄介绍，以便向人解释思路时能从容些。

UID (Unique identifier) 顾名思义是“唯一性标识”，但区别于 GUID/UUID ，它只是有限范围内唯一。通常会在有上下文区分的前提下使用，比如在游戏项目中，玩家ID、物品ID、野怪ID、对局ID 等等可以分别选择不同的 UID 算法实现，只要保证相同类型对象 ID 唯一即可。

下面的代码展示了一个最原始的 UID 实现（别笑，高级算法也会用到计数器）。

var countor uint32
func NextId() uint32 {
  return atomic.AddUint32(&countor)
}

这个例子只保证进程内唯一，且进程重启后，计数器重置也会破坏唯一性。 然而多数场合下，我们期望的 UID 既需要跨进程唯一，也需要在计数器重置（进程重启）后保持唯一。具备这些特性的 UID，就叫做分布式 UID。

有两种改进思路：
一种是引入一个 borker 用来协调不同进程的 ID 分配范围，并将已分配出去的 ID 区间保存到数据库。就跟分蛋糕一样，你一口我一口，吃一口少一口。
参考下图：

这种方案维护成本较高，我个人不太感冒。

另一种则是在 UID 里加入节点 ID 和时间戳，其中节点 ID 用来保证跨进程唯一，而时间戳则保证计数器重置后不会破坏唯一性。但在同一个时间戳里是不能让计数器重置的，所以算法要确保单位时间内只能生成有限数量的 ID 来杜绝这种情况。
以下是实现参考。

• Snowflake
  最早由 Twitter 提出，是为全局有序（k-sorted）开发的 64bit UID 算法。
  https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake
  文中给出了 Scala实现， 也可参考 Wiki说明 :
   
  1 bit 保留
  41 bits 相对时间戳（毫秒），2^41 毫秒大约是 69 年，这之后会溢出导致重复。
  10 bits 节点 ID，最多 1024 个节点。
  12 bits 计数器。
  算法性能每毫秒 2^12 个 UID，大约是 409w/sec/每节点.

• Sonyflake
  索尼魔改版 Snowflake ，减少 UID 生成速率，增加节点数和使用寿命。
  https://github.com/sony/sonyflake
   
  1 bit 保留
  39 bits 相对时间戳（以10毫秒为单位），相当于 174年。
  8 bits 计数器。
  16 bits 节点 ID，最多 65536 个节点。
  算法性能每 10 毫秒 2^8 个 UID，大约是 2.5w/sec/每节点.

• MongoDB ObjectId
  96bit UID 算法，也即 12 个字节。
  https://www.mongodb.com/docs/manual/reference/method/ObjectId/
   
  4 字节 Unix 绝对时间戳（秒） + 5 字节随机数 + 3 字节计数器
  算法性能每秒 2^24 个 UID，就是 1600w/sec/每节点.
  但由于随机数的缘故，多进程环境下可能会有重复，理论上是 (进程数-1) / (2^40) 的概率，大约万亿分之几吧。
  此外该算法使用 4 字节绝对时间戳会有类似 The 2038 problem 的问题，好在比 signed int32 多用 1 个 bit，可续命 2^31 秒用到 2107 年。
   
  该算法还有一种早期版本。
  https://www.mongodb.com/docs/v3.2/reference/bson-types/#objectid
  参考这段 mgo 的 ObjectId 实现。
  其不同之处在于旧版的 5 字节随机数是由 3 字节主机名 hash + 2 字节进程 ID 组成，能保证同一台主机下多进程生成的 ID 绝对唯一。但在容器环境下，由于进程 ID 可能会重复，结果可能更杯具。

综上，这种基于时间戳 + 节点ID 的 UID 算法优缺点都有，也可以结合 borker 一起使用。

只要适当平衡下时间戳、节点 ID 、计数器的 bit 长度，控制在 64bit 内是完全可行的。
至于时间戳有限的问题，百年后留给后人解决吧，也许可以整一套 128bit 的软硬件。