为什么需要全局唯一ID
传统的单体应用架构时，我们基本是单库单业务表的数据结构，每个业务表的ID都是默认自增的，但是在分布式服务架构模式下我们会基于分库分表的设计，这种情况下根据数据库自增ID就无法确认业务主键的唯一性。
那么针对分布式系统如何做到业务主键的唯一性呢
分布式全局ID的特性
-
唯一性：确保生产的ID是全局唯一的。 -
高可用：确保任何时候都能正确生成ID。 -
时间：ID包含时间，看一眼就知道是哪天的。 -
有序递增性：确保生成的ID对于某个用户或者业务是按一定的数有序递增的。 -
信息安全：如果ID是连续的，存在信息风险，直接按照顺序下载指定URL即可；如果是订单号，容易泄露商业信息即每日订单量。所以在一些应用场景下，会需要ID不规则。
4和5需求还是互斥的，无法使用同一个方案同时满足。
技术选型
1.UUID
UUID(Universally Unique Identifier)，通用唯一识别码的缩写。UUID标准型含32个16进制数字，以连字号分五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000。UUID是由以下几部分的组合：
-
当前日期和时间，UUID的第一个部分与时间有关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同。 -
时钟序列。 -
全局唯一的IEEE机器识别号，如果有网卡，从网卡MAC地址获得，没有网卡以其他方式获得。通常在Microsoft创建的软件中也使用术语全球唯一标识符（GUID）。
优点：
-
生成方便； -
本地生成没有网络消耗；
缺点：
-
不易存储：UUID太长，通常需要36长度的字符串表示，占用过多的存储空间。 -
对MySQL索引不利：如果作为数据库主键，在InnoDB索引下，UUID的无序性可能会引擎索引位置频繁变动，影响性能。
2.Snowflake（雪花算法）
Snowflake，雪花算法是由Twitter开源的分布式ID生成算法，以划分命名空间的方式将64-bit位分割成四个部分，每个部分代表不同的含义。所以在Java中SnowFlake算法生成的ID是long类型来存储的。
Twitter 的 Snowflake 算法由下面几部分组成：
-
1位符号位：由于 long 类型在 java 中带符号的，最高位为符号位，正数为 0，负数为 1，且实际系统中所使用的ID一般都是正数，所以最高位为 0。 -
41位时间戳（毫秒级）：需要注意的是此处的 41 位时间戳并非存储当前时间的时间戳，而是存储时间戳的差值（当前时间戳 – 起始时间戳），这里的起始时间戳一般是ID生成器开始使用的时间戳，由程序来指定，所以41位毫秒时间戳最多可以使用 (1 << 41) / (1000x60x60x24x365) = 69年。 -
10位数据机器位：包括5位数据标识位和5位机器标识位，这10位决定了分布式系统中最多可以部署 1 << 10 = 1024 个节点。超过这个数量，生成的ID就有可能会冲突，但一般情况下我们不会部署那么多台机器。 -
12位毫秒内的序列：这 12 位计数支持每个节点每毫秒（同一台机器，同一时刻）最多生成 1 << 12 = 4096个ID数
优点：
-
雪花算法生成的ID是趋势递增的； -
不依赖数据库等第三方中间件； -
本地生成，性能好；
缺点：
-
依赖机器时钟，如果时间回调会存在重复。 -
1台机器每毫秒最多生成4096个（不过每秒也可以达到4百万，一般中大型公司完全够用）。
3.UidGenerator（百度）
UidGenerator是Java实现的，基于Snowflake算法的唯一ID生成器。UidGenerator以组件形式工作在应用项目中，支持自定义workerId位数和初始化策略，从而适用于docker等虚拟化环境下实例自动重启、漂移等场景。
在实现上，UidGenerator通过借用未来时间来解决sequence天然存在的并发限制，采用RingBuffer来缓存已生成的UID，并行化UID的生产和消费，同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题。最终单机QPS可达600万。
依赖版本：Java8及以上版本, MySQL(内置WorkerID分配器, 启动阶段通过DB进行分配; 如自定义实现, 则DB非必选依赖）
Snowflake算法
Snowflake算法描述：指定机器 & 同一时刻 & 某一并发序列，是唯一的。据此可生成一个64 bits的唯一ID（long)。默认采用上图字节分配方式：
-
sign(1bit) 固定1bit符号标识，即生成的UID为正数。 -
delta seconds (28 bits) 当前时间，相对于时间基点”2016-05-20″的增量值，单位：秒，最多可支持约8.7年 -
worker id (22 bits) 机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。 -
sequence (13 bits) 每秒下的并发序列，13 bits可支持每秒8192个并发。
优点：
-
解决了时间回拨的问题。 -
利用RingBuffer存储预生成的ID，提高吞吐量，可达到 6百万/s。
缺点：
-
有第三方依赖，依赖MySQL数据库存储workId； -
ID生成反解析的时间可能不是准确的时间；
4.Leaf（美团）
Leaf是美团基础研发平台推出的一个分布式ID生成服务，名字取自德国哲学家、数学家莱布尼茨的著名的一句话：“There are no two identical leaves in the world”，世间不可能存在两片相同的叶子。
Leaf 也提供了两种ID生成的方式，分别是 Leaf-segment 数据库方案和 Leaf-snowflake 方案。
Leaf-segment数据库方案
第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变：
-
原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大减轻数据库的压力。 -
各个业务不同的发号需求用biz_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。
数据库表设计如下：
CREATE TABLE `leaf_alloc` (
`biz_tag` varchar(128) NOT NULL DEFAULT '' COMMENT '业务key',
`max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',
`step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长',
`description` varchar(256) DEFAULT NULL COMMENT '业务key的描述',
`update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;
原来获取ID每次都需要写数据库，现在只需要把step设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step，大致架构如下图所示：
Leaf-snowflake方案
Leaf-snowflake方案完全沿用snowflake方案的bit位设计，即是“1+41+10+12”的方式组装ID号。对于workerID的分配，当服务集群数量较小的情况下，完全可以手动配置。Leaf服务规模较大，手动配置成本太高。所以使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID。
Leaf-snowflake是按照下面几个步骤启动的：
-
启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。 -
如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。 -
如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。
为了减少对 Zookeeper的依赖性，会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。
5.TinyId（滴滴）
Tinyid是用Java开发的一款分布式id生成系统，基于数据库号段算法实现，关于这个算法可以参考美团leaf或者tinyid原理介绍。
Tinyid扩展了leaf-segment算法，支持了多db(master)，同时提供了java-client(sdk)使id生成本地化，获得了更好的性能与可用性。
性能
-
http方式访问，性能取决于http server的能力，网络传输速度 -
java-client的方式，id为本地生成，号段长度(step)越长，qps越大，如果将号段设置足够大，则qps可达1000w+
可用性
-
依赖db，当db不可用时，因为server有缓存，所以还可以使用一段时间，如果配置了多个db，则只要有1个db存活，则服务可用。 -
使用tiny-client，只要server有一台存活，则理论上可用，server全挂，因为client有缓存，也可以继续使用一段时间。
Tinyid的特性
-
全局唯一的long型id -
趋势递增的id，即不保证下一个id一定比上一个大 -
非连续性 -
提供http和java client方式接入 -
支持批量获取id -
支持生成1,3,5,7,9…序列的id -
支持多个db的配置，无单点
总结
| 方案 | 公司 | 生成方式 | 规则 | 优点 | 缺点 |
|---|---|---|---|---|---|
| UUID | Oracle(sun) | 本地JDK | 32个16进制数，示例：550e8400-e29b-41d4-a716-446655440000 | 简单，性能高，利于信息安全 | 太长不易存储，不易索引 |
| Snowflake | 本地(依赖中间件分配workId) | 时间戳 + 机器标识 + 自增序列号（64 bits的唯一ID（long） | 性能高。灵活，可以根据自身业务特点分配bit位。 | 强依赖机器时钟 | |
| UidGenerator | Baidu | 类Snowflake | 类Snowflake | 性能高。灵活，可以根据自身业务特点分配bit位 | 强依赖机器时钟 |
| Leaf | Meituan | 数据库号段模式和类Snowflake | 号段模式与类Snowflake算法 | 号段模式支持按bizID划分、Snowflake解决时间回拨的问题 | 号段模式暴露业务增长 |
| TinyId | 滴滴 | 参考Leaf号段模式，增加client-sdk | 号段模式 | 趋势递增，支持client和http方式，支持多db | 容易被扫库、测算订单量 |
附录
-
美团Leaf 简介 https://github.com/Meituan-Dianping/Leaf/blob/master/README_CN.md -
tinyid原理介绍 https://github.com/didi/tinyid/wiki/tinyid -
uid-generator原理简介 https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md -
美团点评分布式ID生成系统 https://tech.meituan.com/2017/04/21/mt-leaf.html
原文始发于微信公众号（程序猿阿南）：分布式系统 – 全局唯一ID
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/22315.html
