在協助開發一個電商平台有遇到ID之類的問題或者是單號可以說是或者是手機有他的UUID…這文章重點是如何產生一組不重複的ID方法總整理。
不管我们是不是有身份的人，我们一定是有身份证的人，身份证上面的号码就是我们的ID，理论上这个ID是全国唯一的，而且通过这个号码，我们还可以得到一些个人信息，比如前两位可以确定我们第一次申请身份证的时候所在的省份、接下来的四位可以确定我们所在的区县，然后还可以知道我们出生的年月以及性别。
在我们的计算机应用中，也处处存在的ID， 比如订单编号、商品ID、微博ID、微信消息ID、书的ISDN号、商品条码等等。通过ID，可以迅速定位到对象实体、为对象之间建立关联、跟踪对象在不同服务之间的流转等等。
有的ID是无意义的唯一的标识，有的ID还能提供额外的信息，比如时间和机房信息等等。为了确保唯一性，有的ID使用很长的字节数，比如256个字节，有的通过递增的long类型，只需要8个字节来表示。考虑到存储、信息包含量、性能、安全等因素，一个好的ID的设计至关重要。
介绍ID生成和分布式的方案的文章已经非常非常多了，比如文末中的参考资料中的文章，所以我在本文中简洁的汇总各个方案的优缺点，然后介绍一个分布式的ID生成器项目rpcxio/did,它可以实现单节点百万级的ID生成。
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 使用随机性或伪随机性生成。
更详细的信息可以参考wikipedia和RFC文档。
“版本2” UUID是根据标识符（通常是组或用户ID）、时间和节点ID生成;
“版本3” 和 “版本5” 确定性UUID 通过散列 (hashing) 命名空间 (namespace) 标识符和名称生成;
“版本4” UUID 使用随机性或伪随机性生成。
更详细的信息可以参考wikipedia和RFC文档。
优点
容易实现，产生快
ID唯一(几乎不会产生重复id)
无需中心化的服务器
不会泄漏商业机密
缺点
ID唯一(几乎不会产生重复id)
无需中心化的服务器
不会泄漏商业机密
缺点
可读性差
占用空间太多(16个字节)
影响数据库的性能, 比如UUID or GUID as Primary Keys? Be Careful!
占用空间太多(16个字节)
影响数据库的性能, 比如UUID or GUID as Primary Keys? Be Careful!
遞增整數
可以通过关系型数据库的自增主键产生唯一的ID，现在流行的商业数据库都支持自增主键的特性，比如mysql等。
一些nosql数据库也提供类似特性，比如Redis。
优点
容易产生
可读性好，容易记住
存储很小，比如4个字节
缺点
可读性好，容易记住
存储很小，比如4个字节
缺点
需要中心化的服务器，并且需要处理单点的问题，而且单点有性能瓶颈的问题。
如果ID暴露给公共访问，可能会泄漏商业机密。比如最近浑水报告通过统计销售小票推断出某商业模式的每日单量。
需要访问一次数据库获取ID
如果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个字节就可以了
随机，不会泄漏信息
缺点
占用存储小，4个字节就可以了
随机，不会泄漏信息
缺点
同样需要中心化的服务，有单点问题和性能问题
需要两步，先产生递增的ID,再进行随机加密
需要两步，先产生递增的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。
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所占的位数可以根据你实际的情况做调整。
snowflake还有一个很好的特性就是基本保持顺序性，因为它的前几位是时间戳，可以对ID按照时间进行排序。 另外在微服务中直接使用ID就可以计算sla。
优点
存储少, 8个字节
可读性高
性能好，可以中心化的产生ID,也可以独立节点生成
缺点
可读性高
性能好，可以中心化的产生ID,也可以独立节点生成
缺点
时间回拨会重复产生ID
ID生成有规律性,信息容易泄漏
ID生成有规律性,信息容易泄漏
MongoDB ObjectID
MongoDB的主键类型ObjectID也是一种ID生成方案，比如5349b4ddd2781d08c09890f3,它看起来是一个包含24个字符的字符串，实际采用12个字节来存储。
它使用4个字节代表时间戳，3个字节代表机器ID,2个字节代表机器进程ID,然后3个字节代表自增值。
相对于snowflake,它采用了更多的存储(多了四个字节),可以容纳更多的信息
优点
可读性高
性能好，可以中心化的产生ID,也可以独立节点生成
缺点
性能好，可以中心化的产生ID,也可以独立节点生成
缺点
占用存储较多
时间回拨会重复产生ID
ID生成有规律性,信息容易泄漏
分布式ID生成器服务 did
前面是一些ID生成的背景知识的介绍，这里介绍一个分布式ID生成器rpcxio/did)，它基于snowflake的算法，但是提供了可以定制的算法，支持初始化设置worker id和自增值的bit数。
时间回拨会重复产生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
Flicker
Flicker 方案主要思路是设计单独的库表，利用数据库的自增 ID 来生成全局 ID。
CREATE TABLE ticket_center (
id bigint(20) unsigned NOT NULL auto_increment,
stub char(1) NOT NULL default '',
PRIMARY KEY (id),
UNIQUE KEY unq_stub (stub)
)ENGINE=MyISAM;
stub: 票根，对应需要生成 Id 的业务方编码，可以是项目名、表名甚至是服务器 IP 地址。
MyISAM：默认表类型，基于传统的 ISAM 类型。ISAM是 Indexed Sequential Access Method (有索引的顺序访问方法) 的缩写，它是存储记录和文件的标准方法。不是事务安全的，而且不支持外键。如果执行大量的 select，MySql 存储引擎选用 MyISAM 比较适合。
可以使用下面的SQL 获取 ID:
REPLACE INTO ticket_center (stub) VALUES ('test');
SELECT LAST_INSERT_ID();
Replace into 先尝试插入数据到表中，如果发现表中已经有此行数据（根据主键或者唯一索引判断）则先删除此行数据，然后插入新的数据， 否则直接插入新数据
为了解决单点故障问题：Flicker 方案启用了两台数据库服务器来生成 ID，通过区分 auto_increment 的起始值和步长来生成奇偶数的 ID。（也可以根据情况部署多台服务器）
优点
充分利用了数据库自增 ID 机制，生成的 ID 有序递增。
充分利用了数据库自增 ID 机制，生成的 ID 有序递增。
缺点
依赖于数据库，可用性低
依赖于数据库，可用性低
水平扩展困难：定义好了起始值、步长和机器台数之后，如果要添加机器就比较麻烦了。
适用场景：数据量不多，并发量不大。
Redis
因为 Redis 中的所有命令都是单线程的，可以利用 Incrby命令来模拟 ID 的递增。并且可以通过使用集群来提升吞吐量。我们可以为不同的 Redis 节点设置不同的初始值并统一步长，这样就能利用 Redis 生成唯一且趋势递增的 ID 了。例如有 3 个 Redis 节点，分别设置初始值为 1、2、3 ，这时步长就应该定为 3 。这样每个节点不会生成重复的 ID。
Incrby ：将 key 中储存的数字加上指定的增量值。这是一个 "INCR AND GET” 的原子操作, 业务方可以定义一个自己的 key 值，通过 INCR 命令来获取对应的 ID。
优点：
不依赖数据库，且性能优于依赖数据库的 Flicker 方案。
不依赖数据库，且性能优于依赖数据库的 Flicker 方案。
缺点：
扩展性低，Redis 集群需要设置好初始值与步长。
扩展性低，Redis 集群需要设置好初始值与步长。
Reids 宕机可能会生成重复的Id。
适用场景：Redis 集群高可用，并发量高。
Leaf
上面提到的这些常见的 ID 生成策略，有时并不能完全满足实际生产中的需求，在实际项目中会对其做一些改造和优化。
美团的 Leaf 分布式 ID 生成系统 ，在 Flicker 策略 与 Snowflake 算法的基础上做了两套优化的方案。下文会简单介绍一下 Leaf 方案做的一些优化，并不会深入分析。详细方案大家可以查看这里：《Leaf 分布式 ID 生成系统 》
Leaf-segment 数据库方案
相比于 Flicker 方案每次都需要读取数据库，Leaf-segment 改为了利用 proxy server 批量获取，且做了双 buffer 的优化。设计图如下：
相比于 Flicker 方案每次都需要读取数据库，Leaf-segment 改为了利用 proxy server 批量获取，且做了双 buffer 的优化。设计图如下：
双 buffer：ID 分号段加载，且当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。
Leaf-snowflake 方案
主要是针对时钟回拨问题做了特殊处理。 若发生时钟回拨则拒绝发号，并进行告警。
适用场景：服务规模较大，调用频繁。
總結
关于分布式 ID 的生成策略暂且介绍到这里。其实还有一些优秀的解决方案，比如百度的 uid-generator，微信的 SEQSVR。基本上都是都上面一些方案的优化，这里就不做详细介绍了。在实际使用中，需要根据自身业务场景来选取合适的方案，也并非大而全的方案就是好的方案。
策略應用場景
参考资料
https://mp.weixin.qq.com/s/qVN75AeN_5x-rn-wvgnBHg
https://colobu.com/2020/02/21/ID-generator/?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
https://semlinker.com/uuid-snowflake/?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
https://mp.weixin.qq.com/s/qVN75AeN_5x-rn-wvgnBHg
https://colobu.com/2020/02/21/ID-generator/?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
https://semlinker.com/uuid-snowflake/?hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io
https://www.simpleorientedarchitecture.com/7-strategies-for-assigning-ids/
https://www.callicoder.com/distributed-unique-id-sequence-number-generator/
https://juejin.im/post/5b3a23746fb9a024e15cad79
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://i6448038.github.io/2019/09/28/snowflake/
https://soulmachine.gitbooks.io/system-design/content/cn/distributed-id-generator.html
https://juejin.im/post/5bb0217ef265da0ac2567b42
https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-01-dist-id.html
https://zh.wikipedia.org/zh-hans/通用唯一识别码
https://zhuanlan.zhihu.com/p/46404167
https://www.callicoder.com/distributed-unique-id-sequence-number-generator/
https://juejin.im/post/5b3a23746fb9a024e15cad79
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://i6448038.github.io/2019/09/28/snowflake/
https://soulmachine.gitbooks.io/system-design/content/cn/distributed-id-generator.html
https://juejin.im/post/5bb0217ef265da0ac2567b42
https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-01-dist-id.html
https://zh.wikipedia.org/zh-hans/通用唯一识别码
https://zhuanlan.zhihu.com/p/46404167
