分布式 ID 生成方案


不管我们是不是有身份的人,我们一定是有身份证的人,身份证上面的号码就是我们的 ID,理论上这个 ID 是全国唯一的,而且通过这个号码,我们还可以得到一些个人信息,比如前两位可以确定我们第一次申请身份证的时候所在的省份、接下来的四位可以确定我们所在的区县,然后还可以知道我们出生的年月以及性别。

在我们的计算机应用中,也处处存在的ID, 比如订单编号、商品 ID、微博 ID、微信消息 ID、书的 ISDN 号、商品条码等等。通过 ID,可以迅速定位到对象实体、为对象之间建立关联、跟踪对象在不同服务之间的流转等等。

有的 ID 是无意义的唯一的标识,有的ID还能提供额外的信息,比如时间和机房信息等等。为了确保唯一性,有的ID使用很长的字节数,比如 256 个字节,有的通过递增的 long 类型,只需要 8 个字节来表示。考虑到存储、信息包含量、性能、安全等因素,一个好的 ID 的设计至关重要。

介绍 ID 生成和分布式的方案的文章已经非常非常多了,比如文末中的参考资料中的文章,所以我在本文中简洁的汇总各个方案的优缺点,然后介绍一个分布式的ID生成器项目 rpcxio/did,它可以实现单节点百万级的节点生成。
1.png

ID 生成方案

UUID/GUID

通用唯一识别码(Universally Unique Identifier,缩写:UUID)是用于计算机体系中以识别信息数目的一个 128 位标识符,也就是可以通过 16 个字节来表示。

UUID 可以根据标准方法生成,不依赖中央机构的注册和分配,UUID 具有唯一性,这与其他大多数编号方案不同。重复 UUID 码概率接近零,可以忽略不计。

GUID 有时专指微软对 UUID 标准的实现(Globally Unique Identifier,缩写:GUID),通常表示成 32 个 16 进制数字(0-9,A-F)组成的字符串,如:{21EC2020-3AEA-1069-A2DD-08002B30309D},实质上还是是一个 128 位长的二进制整数,在 Windows 生态圈中常用。

UUID 由开放软件基金会(OSF)标准化,作为分布式计算环境(DCE)的一部分。

UUID 的标准型式包含 32 个 16 进位数字,以连字号分为五段,形式为 8-4-4-4-12 的 32 个字元。范例:550e8400-e29b-41d4-a716-446655440000。

在其规范的文本表示中,UUID 的 16 个 8 位字节表示为 32 个十六进制(基数16)数字,显示在由连字符分隔 '-' 的五个组中,"8-4-4-4-12" 总共 36 个字符(32 个字母数字字符和 4 个连字符)。例如:
123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

四位数字 M 表示 UUID 版本,数字 N 的一至三个最高有效位表示 UUID 变体。在例子中,M 是 1 而且 N 是 a(10xx),这意味着此 UUID 是 "变体1"、"版本 1" UUID;即基于时间的 DCE/RFC 4122 UUID。

对于 "变体(variants)1" 和 "变体 2",标准中定义了五个"版本(versions)",并且在特定用例中每个版本可能比其他版本更合适。

版本由 M 字符串中指示。
  • "版本 1" UUID 是根据时间和节点 ID(通常是MAC地址)生成;
  • "版本 2" UUID 是根据标识符(通常是组或用户 ID)、时间和节点 ID 生成;
  • "版本 3" 和 "版本 5" 确定性 UUID 通过散列(hashing)命名空间(namespace)标识符和名称生成;
  • "版本 4" UUID 使用随机性或伪随机性生成。


更详细的信息可以参考 wikipediaRFC 文档。

优点:
  • 容易实现,产生快
  • ID 唯一(几乎不会产生重复 ID)
  • 无需中心化的服务器
  • 不会泄漏商业机密


缺点:


递增的整数

可以通过关系型数据库的自增主键产生唯一的 ID,现在流行的商业数据库都支持自增主键的特性,比如 MySQL 等。

一些 NoSQL 数据库也提供类似特性,比如 Redis。

优点:
  • 容易产生
  • 可读性好,容易记住
  • 存储很小,比如 4 个字节


缺点:
  • 需要中心化的服务器,并且需要处理单点的问题,而且单点有性能瓶颈的问题。
  • 如果 ID 暴露给公共访问,可能会泄漏商业机密。比如最近浑水报告通过统计销售小票推断出某商业模式的每日单量。
  • 需要访问一次数据库获取 ID。


随机数

递增的整数可以用在内部的服务中,如果用在外部,可能会泄漏信息,所以如果能产生随机数就可以解决这个问题。

当然直接生成随机数可能比较困难,你可以在递增的整数上产生伪随机的整数,比如使用 skip32, 它还可以直接进行反解码,在内部反解出原来的递增的 ID,所以在一些场景的也有广泛的应用,比如在 PostgrepSQL中可以实现 skip32 function。

另外一个比较常用的加密递增 ID 方法是 hashid,它可以转换数字比如 347 为字符串 yr8,并且还可以反解出来,提供了很多语言的实现,比如 go-hashids、hashids-java、hashids.c等。

对于 64 bit 的整数,你可以使用 Block ciphers 实现加密。也有把 64 bit 整数分成两部分,分别应用 skip32 进行加密的。

优点:
  • 可读性高
  • 占用存储小,4 个字节就可以了
  • 随机,不会泄漏信息


缺点:
  • 同样需要中心化的服务,有单点问题和性能问题
  • 需要两步,先产生递增的ID,再进行随机加密


随机字符串

另外一个产生随机 ID 方法是直接产生一个小的随机的字符串,比如短网址服务中的 ID。 产生随机字符串的方法很多, 比图 tinyurl 和 bit.ly 使用的基于 62 字符的随机字符串,基于 hash(MD5)+base62 等,应用在 Bitcoin 地址上的可读性更好的 Base58。

优点:
  • 短,5 个字符(字节)就可以表示 10 亿个 ID。
  • 可读性高
  • 随机,不会泄漏信息


缺点:
  • ID 可能不唯一,需要检查和处理


Twitter的snowflake算法

Twitter 的 snowflake 分布式 ID 的算法是目前广泛使用的分布式 ID 算法,尽管有很多变种,比如位数的不同,时间片大小不同、node bit 数放在最后等各种变种,但是主要思想还是来自于 snowflake 的思想。 同时访问方法也各种个样,比如提供 memcached 协议访问和 Redis 协议访问等等。

Twitter 在 2010 年儿童节的时候在官方博客上介绍了 snowflake 算法,内部用来表示每一条 tweet,尽管这个项目已经不再维护了 snowflake-2010。
2.png

snowflake 算法采用 64bit 存储 ID,最高位备用,暂时不使用。接下来的 41 bit 做时间戳,最小时间单位为毫秒。再接下来的 10 bit 做机器 ID(worker id),然后最后 12 bit 在单位时间(毫秒)递增。

41 bit 表示时间戳大约可以使用 69 年(2^41 -1),为了尽可能的表示时间,时间戳可以从第一次部署的时候开始计算,比如 2020-02-02 00:00:00,这样 69 年内可以无虞。

10 bit 区分机器,所以可以支持 1024 台机器。 你也可以把 10 bit 分成两部分,一部分做数据中心的 ID,一部分做机器的 ID,比如 55 分的化,可以支持 32 个数据中心,每个数据中心最多可以支持 32 台机器。

12 bit 自增值可以表示 4096 的 ID,也就是说每台机器每以毫秒最多产生 4096 个 ID,这是它的最大性能。

正如前面所说,时间戳、机器 ID、自增 ID 所占的位数可以根据你实际的情况做调整。

snowflake 还有一个很好的特性就是基本保持顺序性,因为它的前几位是时间戳,可以对 ID 按照时间进行排序。 另外在微服务中直接使用 ID 就可以计算 sla。

优点:
  • 存储少,8 个字节
  • 可读性高
  • 性能好,可以中心化的产生ID,也可以独立节点生成


缺点:
  • 时间回拨会重复产生 ID
  • ID 生成有规律性,信息容易泄漏


MongoDB ObjectID

MongoDB 的主键类型 ObjectID 也是一种 ID 生成方案,比如:5349b4ddd2781d08c09890f3,它看起来是一个包含 24 个字符的字符串,实际采用 12 个字节来存储。
3.png

它使用 4 个字节代表时间戳,3 个字节代表机器 ID,2 个字节代表机器进程 ID,然后 3 个字节代表自增值。

相对于 snowflake,它采用了更多的存储(多了四个字节),可以容纳更多的信息。

优点:
  • 可读性高
  • 性能好,可以中心化的产生 ID,也可以独立节点生成


缺点:
  • 占用存储较多
  • 时间回拨会重复产生 ID
  • ID生成有规律性,信息容易泄漏


分布式 ID 生成器服务 did

前面是一些 ID 生成的背景知识的介绍,这里介绍一个分布式 ID 生成器(rpcxio/did),它基于 snowflake 的算法,但是提供了可以定制的算法,支持初始化设置 worker id 和自增值的 bit 数。

因为它是一个中心化的 ID 生成器服务,所以每次获取 ID 都有额外的网络开销,所以最好一次申请一批数据,然后 client 在本地使用,用不了丢掉即可,所以 did 服务还提供批量获取 ID 的方法。

安装 did 的服务需要定时的和时间服务器进行同步,这个短时间的回拨不会影响 ID 的产生。 重启服务一般也没有问题,因为各个节点和时间服务器的误差在毫秒左右,而重启至少是秒级的操作,所以不会有重复的 ID 产生。 唯一怕的时候手工将时间回拨一个很长的时间(几个小时、几天),然后这个时候再重启服务,一般生产环境中也不会这么去做。

因为可以部署多个 did 服务做集群,所以可以提供容错机制,少量 did 节点宕机不会影响 ID 生成服务的访问。

因为 snowflake 算法性能优异,所以 ID 生成服务部署的节点不需要很多,每个机房只需要几台机器就可以了,所以你可以压缩 worker id 占用的 bit 数,扩大自增值占用的 bit 数。

测试中,单个节点可以提供 12 万 ID/秒的产生速度,而如果采用批量获取 100ID 的话,可以取得接近三百万 ID/秒的性能。
1、256 个 client 并发,每次只获取 1 个 ID,ID 的产生速度是 12 万个 ID/秒。
./bclient -addr 192.168.15.225:8972 -n 100000
total IDs: 25600000, duration: 3m31.581592489s, id/s: 120993
2、如果采用批量获取,尽量减少网络消耗,256 个 client 并发,每次只获取 100 个 ID,ID 的产生速度是 297 万个 ID/秒。
./bclient -addr 192.168.15.225:8972 -n 1000000 -b 100
total IDs: 256000000, duration: 1m26.178942509s, id/s: 2970563


参考资料:
  1. https://www.simpleorientedarch ... -ids/
  2. https://www.callicoder.com/dis ... ator/
  3. https://juejin.im/post/5b3a23746fb9a024e15cad79
  4. https://tech.meituan.com/2017/04/21/mt-leaf.html
  5. https://i6448038.github.io/2019/09/28/snowflake/
  6. https://soulmachine.gitbooks.i ... .html
  7. https://juejin.im/post/5bb0217ef265da0ac2567b42
  8. https://chai2010.cn/advanced-g ... .html
  9. https://zh.wikipedia.org/zh-ha ... %2581
  10. https://zhuanlan.zhihu.com/p/46404167


原文链接:https://colobu.com/2020/02/21/ID-generator/

0 个评论

要回复文章请先登录注册