Hi!我是小小,我们又见面了,我们今天的话题是六种分布式ID生成算法。

分布式ID简介

什么是分布式ID

在数据量不大的时候,单库单表完全可以支撑现有业务,数据量再大一点搞个MySql主从同步也可以。
数据量增长,到后期,需要进行分库分表,显然,这个时候需要一个全局唯一ID,而这个订单号就是分布式ID。

需要满足的条件

  1. 全局唯一
  2. 高可用
  3. 高性能
  4. 简单可用

分布式ID | 这六种分布式ID生成方法,总有一款适合你插图

生成方案

UUID/GUID

通用唯一识别码,是用于计算机体系中以识别信息数目的一个128位标识符,通过16个字节来表示。
UUID,可以根据标准方法生成,不依赖中央机构的注册和分配,UUID具有唯一性,这与其他方案有所不同。
GUID有时专指微软对UUID标准的实现,通常表示成32个16进制的数字组成的字符串,实质上还是一个128位长的二进制整数。在windows生态中,经常使用。
UUID是由开放软件基金会标准化,作为分布式计算环境的一部分。
UUID的标准包含32个16进位数字,以连字号分为五段,形式为8-4-4-4-12的32个字元,范例550e8400-e29b-41d4-a716-446655440000
在其规范的文本表示中,UUID的16个8位字节表示为32个十六进制的数字,显示在由连字符分割的-的五个组中,8-4-4-4-12总共36个字符,例如

123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

四位数字 M表示 UUID 版本
版本为
1. “版本1” UUID 是根据时间和节点 ID(通常是MAC地址)生成;
2. “版本2” UUID是根据标识符(通常是组或用户ID)、时间和节点ID生成;
3. “版本3” 和 “版本5” 确定性UUID 通过散列 (hashing) 命名空间 (namespace) 标识符和名称生成;
4. “版本4” UUID 使用随机性或伪随机性生成。

优点

  1. 容易实现,产生快
  2. ID唯一
  3. 无需要中心化服务器
  4. 不会泄露商业机密

缺点

  1. 可读性过差
  2. 占用空间过多。
  3. 影响数据库性能

数据库递增

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

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

优点

  1. 容易产生
  2. 可读性好,容易记住
  3. 存储很小

缺点

  1. 需要中心化的服务器,并且需要处理单节点的问题,而且有性能瓶颈的问题。
  2. 如果ID暴露给公共访问,会泄露商业机密,通过减法获取每日单量
  3. 需要访问一次数据库获取ID

随机数

递增的整数可以用在内部的服务器中,在外部,可以使用随机数解决这个问题。
在递增的基础上产生伪随机数,例如skip32.

skip 32 https://github.com/dgryski/go-skip32

可以直接反解码,即,先使用skip32在随机数上再生成随机数,然后通过反解码,获取到原先的随机数。
另外还有一个方法,为hashid

https://hashids.org/ hashid

也可以实现混淆Id的方法

优点

  1. 可读性高
  2. 占用存储小,4个字节即可。
  3. 随机,不会泄露机密

缺点

  1. 需要中心化的服务
  2. 需要两步操作

随机字符串

另外一个产生随机ID方法是直接产生一个小的随机的字符串,比如短网址服务中的ID。
此方法有hash(MD5) + base62

优点

  1. 短。5个字节可以保存10亿个ID
  2. 可读性高
  3. 随机,不会泄露信息

缺点

  1. ID可能不唯一,需要检查和处理

基于雪花算法(Snowflake)模式

Twitter的snowflake分布式ID的算法是目前广泛使用的分布式ID算法,尽管有很多变种,比如位数的不同,时间片大小不同、node bit数放在最后等各种变种,但是主要思想还是来自于snowflake的思想。 同时访问方法也各种个样,比如提供memcached协议访问和Redis协议访问等等。
Twitter在2010年儿童节的时候在官方博客上介绍了snowflake算法
分布式ID | 这六种分布式ID生成方法,总有一款适合你插图(1)
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台机器。 你也可以把10bit分成两部分,一部分做数据中心的ID,一部分做机器的ID,比如55分的化,可以支持32个数据中心,每个数据中心最多可以支持32台机器。

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

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

优点

  1. 存储少,8个字节
  2. 可读性高
  3. 性能好,可以去中心化产生ID,也可以独立节点生成

缺点

  1. 时间回拨会产生重复ID
  2. ID生成有规律性,信息容易泄露

MongoDB ObjectID

MongoDB的主键类型ObjectID也是一种ID生成方案,比如5349b4ddd2781d08c09890f3,它看起来是一个包含24个字符的字符串,实际采用12个字节来存储。
分布式ID | 这六种分布式ID生成方法,总有一款适合你插图(2)

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

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

优点

  1. 可读性高
  2. 性能好,可以实现去中心化的产生ID,也可以独立节点完成生成。

缺点

  1. 占用存储过多。
  2. 时间回拨会产生重复ID
  3. ID生成有规律,信息容易泄露