背景
数据日渐增长，在分布式系统中非常需要对数据和消息进行唯一标识。
业务系统关于ID的要求：
1、全局唯一：不能出现重复的ID号，既然是唯一标识，这是最基本的要求；
2、趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，B-tree的数据结构，尽量使用有序的主键保证写入性能；
3、单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求；
4、信息安全：有时需要ID无规则、不规则，否则容易被恶意扒取，或者泄露订单总数等。
ID 生成服务的要求:
1、低延迟
2、高QPS
3、高可用性
唯一ID介绍
数据库自增ID
MySQL 中可以使用 auto_increment_increment 和 auto_increment_offset 来保证ID自增
优点：
实现过程非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护；
ID号单调自增，可以实现一些对ID有特殊要求的业务；
数字ID天然排序，对分页或者需要排序的结果很有帮助。
缺点：
可用性弱：单点故障风险，强依赖DB，异常时整个系统不可用，属于致命问题；
一致性弱：主从复制可以尽可能的增加可用性，但主从切换时的不一致可能会导致重复发号；
性能瓶颈：ID发号性能瓶颈限制在单台MySQL的读写性能；
可扩展性：分表分库的时候比较难处理。
分布式方案：多部署几台机器，每台机器设置不同的初始值，且步长和机器数相等。
比如部署N台机器，步长需设置为N，每台的初始值依次为0,1,2...N-1。
优点: 多台数据库提高性能，保持ID趋势递增；
缺点: 系统水平扩展比较困难，ID没有了单调递增的特性，数据库依然是瓶颈。
UUID
Universally Unique Identifier，标准形式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，示例：550e8400-e29b-41d4-a716-446655440000
优点: 生成ID的性能非常高，本地生成，没有网络消耗；全球唯一，重复率很低。
缺点：
没有排序，无法保证趋势递增；
可读性差，不能从ID中直接获取业务信息；
不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用;；
信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露(曾经被用来梅丽莎病毒的制作者位置)；
UUID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，就非常不适用：
1、MySQL官方有明确的建议主键要尽量越短越好，36个字符长度的UUID不符合要求；
2、对MySQL索引不利：在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。
Redis生成ID
可以利用Redis的原子操作 INCR和INCRBY来生成ID 如果单台Redis 服务不满足要求，可以使用多台机器
优点：
不依赖于数据库，灵活方便，且性能优于数据库；
数字ID天然排序，对分页或者需要排序的结果很有帮助；
Redis 集群可以提高可用性，降低单点故障风险；
缺点: 如果系统中没有Redis，还需要引入新的组件，增加系统复杂度; 需要编码和配置的工作量比较大; 需要提前制定好初始值和步长，水平扩展能力弱。
ZooKeeper生成ID
ZooKeeper 主要通过其znode数据版本来生成序列号，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的ID。
优点：ID唯一
缺点：强依赖 ZooKeeper 性能弱:多步调用API，需要使用分布式锁，性能在高并发的分布式环境下，不甚理想。
MongoDB生成ObjectID
MongoDB的ObjectId和SnowFlake算法类似
MongoDB 开始就设计用来作为分布式数据库，处理多个节点是一个核心要求，使其在分片环境中要容易生成得多。
12字节的ObjectId值包括：
4字节：秒级单位的时间戳值；
5字节：随机值；
3字节：递增计数器，初始化为随机值
优点：
轻量型类 SnowFlake 算法的实现；
生成及使用方法简单，具有部分业务意义；
时间戳为前缀，趋势递增。
缺点：
如果系统中没有MongoDB，还需要引入新的组件，增加系统复杂度；
DB 强依赖性。
SnowFlake算法
SnowFlake是Twitter开源的分布式ID生成算法，结果是一个long型的ID。 其核心思想是以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法。
优点：
毫秒数在高位，自增序列在低位，整个ID都是趋势递增的；
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的；
可以根据自身业务特性分配bit位，非常灵活。
缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
常见几种实现
Tinyid(滴滴)
采用数据库号段方式生成ID
▪ 支持http和Java client
▪ 支持批量获取ID
▪ 支持多DB，无单点(但扩容困难)
表设计升级
DB直接存储一个范围(start_id,end_id]，当这批id使用完毕后，做一次update操作：update start_id=2000(end_id), end_id=3000(end_id+1000)， update成功了，则说明获取到了下一个id范围。
biz_type 这个代表业务类型，不同的业务的id隔离；
max_id 代表当前最大的可用id；
step 代表号段的长度，可以根据每个业务的qps来设置一个合理的长度；
version 是一个乐观锁，每次更新都加上version，能够保证并发更新的正确性；
delta: 代表id每次的增量；
remainder：代表余数；
那么我们可以通过如下几个步骤来获取一个可用的号段，
1、查询:select id, biz_type, max_id, step, version from tiny_id_info where biz_type='test';
2、计算:new_max_id = max_id + step;
3、更新:update tiny_id_info set max_id=#{new_max_id} , verison=version+1 where id=#{id} and max_id=#{max_id} and version=#{version} D.如果更新成功，则可用号段获取成功，新的可用号段为(max_id, new_max_id] E.如果更新失败，则号段可能被其他线程获取，回到步骤A，进行重试。
通过 delta 和 remainder 我们可以灵活设计db个数 同时也可以为使用方提供只生产类似奇数的id序 列。
双号段缓存优化
因为号段用完需要访问db，容易因DB性能导致波动。 在号段用到一定程度的时候，就去异步加载下一个号段，保证内存中始终有可用号段，则可避免性能波动。
tinyid提供http和tinyid-client两种方式接入 tinyid-server内部缓存两个号段 号段基于db生成，具有原子性 db支持多个，tinyid-server内置easy-router选择db
UidGenerator(百度)
采用类似SnowFlake算法生成ID
▪ 采用双RingBuffer，提高了整体吞吐
▪ 解决了时钟回退的问题
▪ 存在单号浪费
UidGenerator 是Java实现的, 基于Snowflake算法的唯一ID生成器。
UidGenerator以组件形式, 支持自定义workerId位数和初始化策略, 适用于docker虚拟化环境下自动重启、漂移等场景。
UidGenerator通过借用未来时间来解决sequence天然存在的并发限制; 采用RingBuffer来缓存已生成的UID, 并行化UID的生产和消费, 同时对CacheLine补齐，避免了由RingBuffer带来的硬件级「伪共享」问题. 最终单机QPS可达600万。
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个并发。
DeFaultUidGenerator源码实现
1、delta seconds(28 bits)：
当前时间与epoch时间的时间差，且单位为秒。 epoch时间就是指集成DefaultUidGenerator生成分布式ID服务第一次上线的时间，可配置， 也一定要根据你的上线时间进行配置，因为默认的epoch时间可是2016-09-20，会浪费好几年的可用时间。
2、worker id(22bits)：
实例启动的时候，表中插入一行数据，id值就是workerId的值。
由于workerId默认22位，实例重启次数是不允许超过4194303次(即2^22-1)，否则会抛出异常。
3、sequence(13bits)：
a. synchronized保证线程安全；
b. 如果时间有任何的回拨，那么直接抛出异常；
c. 如果当前时间和上一次是同一秒时间，那么sequence自增；
d. 如果同一秒内自增值超过2^13-1，那么就会自旋等待下一秒(getNextSecond); e. 如果是新的一秒，那么sequence重新从0开始。
Leaf (美团)
采用数据库号段和 SnowFlake 算法两种方式生成ID
▪ 多种单号生成方式
▪ 高可用(解决DB单点，时钟回退)
▪ 高性能
Leaf-segment数据库方案
Tinyid 就是参考 Leaf-segment 数据库方案实现的
1、双buffer优化
2、容灾高可用
Leaf-SnowFlake方案
Leaf-SnowFlake 的实现与 UidGenerator 类似:：
1、workID使用ZooKeeper实现；
2、未解决时钟回拨问题
整个启动流程图如下，服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点：
若写过，则用自身系统时间与leaf_forever/${self}节点记录时间做比较，若小于leaf_forever/${self}时间则认为机器时间发生了大步长回拨，服务启动失败并报警。
若未写过，证明是新服务节点，直接创建持久节点leaf_forever/${self}并写入自身系统时间，接下来综合对比其余Leaf节点的系统时间来判断自身系统时间是否准确，具体做法是取leaf_temporary下的所有临时节点(所有运行中的Leaf-snowflake节点)的服务IP：Port，然后通过RPC请求得到所有节点的系统时间，计算sum(time)/nodeSize。
若abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/${self} 维持租约。
否则认为本机系统时间发生大步长偏移，启动失败并报警。
每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。
参考资料
