Blog:分布式系统 ID 生成

来自WHY42

ID生成一直是一个老生常谈的问题，个人不习惯使用ID自增的方式，从0开始...每次递增，原因是因为low...最近研究了一下ID生成的算法，主要用来给我们的订单系统用。首先说一下背景：我们的系统提供给很多经销商使用，每个经销商登录到我们的系统，发生业务、产生订单。

设计原则

  • **唯一性**：保证生成的ID不会出现重复，需要考虑分布式部署情况下的唯一性
  • **安全性**：不会通过订单号泄露流水信息（比如别人通过订单号知道你一天大概多少交易量）
  • **长度**：长度未明确要求，在满足其他需要的情况下应该尽量短
  • **字符集**：字符未明确要求，按允许数字 + 英文字母（大写）设计
  • **性能要求**：如果按500家商家上线，每家每天1000次订单生成，其中高峰期每分钟10单，系统能支持运行10年的指标来计算，每天的订单数为500 * 1000 = 50W，高峰期每分钟为500 * 10 = 5000单，10年为 500 * 1000 * 365 * 10 = 1825000000单
  • **易读性**：如果使用英文字母，则可以考虑去除掉容易混淆的字母：O I S Z 等

Option 1：Snowflake算法

参考twitter的snowflake 64bit ID生成算法，设计如下的ID规则：

0 00000000 00000000 00000000 00000000 00000000 0 00000000 00 00000000 0000

  • 1 bit 符号位，固定为0，不使用
  • 41bit时间戳，即当前时间到某一开始时间的毫秒数
  • 10bit 商家标识，可根据其上线时间递增
  • 12bit 序列号，每一毫秒内从0开始，如果超过最大值则等待下一毫秒

其中41bit时间戳最大可支持的时间： (2^41) / (365 × 24 × 60 × 60 × 1000) = 2199023255552 / 31536000000 ≈ 69.7(年)

10bit 标识 最大支持的商家数为： 2^10 = 1024

12bit 序列号最大支持为每秒： 2^12 = 4096

生成的ID大概像这样： 

274432
...
278501
278502
278503
278504
...
109996123808346299
109996123808346300
109996123808346301
….
2647243359755833344
2647243359755833345
2647243359755833346

如果需要支持分布式部署，则可考虑将商家标识的10位中插入机器标识，根据最大可能的机器节点数来选取位数。比如分配3位，就可以支持2^3=8台机器。同样，时间戳可以浮动，一般的系统根本不需要考虑超过5年以上的情况，能用两年就不错了...当然我倾向于支持10年，10年后如果世界末日不到，系统还在用，那就再想办法吧。

Option 2 : 时间戳 + 商家标识 + 随机数

时间（6位）+ 商家标识 （4位） + 随机数（4位）

170911 0001 8774

其中，商家标识和随机数取值范围为[0-9A-Z]即 T = 26 + 10 = 36(种)

其中，商家标识最大支持的商家数为： T × T × T × T = T^ 4 = 1679616

随机数支持范围同商家标识。因时间精确到天，因此随机数每日不能重复，每天最大支持的订单数（每个商家）即为： T^ 4 = 1679616

时间（3位）+ 商家标识 （2位） + 随机数（2位）

79A 0A F1

其中年、月、日各占一位，其中年可以取年份-2017年的差值，超过9则用字母表示，例如2017年9月25日，可表示为： 09M

这是简短的方案，年份只取一位则最多只可以使用T = 36年，否则会出现重复

其中商家标识最大支持： T ^ 2 = 1296

每天每一个商家标识最多只能支持T^ 2 = 1296笔订单号，若不能满足业务需求则可以将随机数扩展为3-4位

时间（8位）+ 商家标识 （2位） + 序列号（2位）

65DEF7BE AF 35 65DEF7BE （16进制）= 1709111230（10进制）

因时间精确到分钟，随机数按照每分钟递增，因此每分钟可以支持订单数： T ^ 2 = 1296 每天可支持的订单数为： 24 × 60 × T^ 2 = 1866240

Option 3 : 时间戳 + 随机数

时间戳（6位） + 随机数（4位） 170911 9527

使用4位数字则每日最大只能9999单，使用字母则可以有 T^ 4 = 1679616 单 若按500家商家算平均每个商家每天有3359单

Option 4 : 渠道号 + 时间戳 +（流水号 +用户标识+随机数）

R 79A 0011 9527 34

其中，流水号按用户按天生成，用户标识取用户ID后四位，例如： 流水号（4位） + 用户标识（4位） + 随机数（2位） 0011 9527 34

取自“https://riguz.com/index.php?title=Blog:分布式系统_ID_生成&oldid=2652”