分布式系列-分布式ID
一、数据库自增（单实例）
1、方案描述
基于数据库自增ID（auto_increment）利用其来充当分布式ID。实现方式就是用一张表来充当ID生成器，当我们需要ID时，向表中插入一条记录返回主键ID。
CREATE TABLE identity_table(
`id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '主键id',
`value` VARCHAR(50) NOT NULL DEFAULT '' COMMENT 'value',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='ID信息表';
<insert id="insertAndGetId" useGeneratedKeys="true" keyProperty="id">
insert into identity_table(value)
values(#{value})
</insert>
2、优点
（1）通过数据库保证唯一性，实现简单；
（2）数字ID，具备有序性。
3、缺点
（1）存在单点宕机风险；
（2）无法抗住高并发场景。
二、数据库集群模式
1、方案描述
基于多实例数据库主键自增，通过横向扩展机器，解决单点数据库的压力。实现方式就是在自增ID（auto_increment）的基础上，设置step增长步长，使得不同实例中的ID不会发生碰撞。
set @@auto_increment_offset = 0; -- 起始值
set @@auto_increment_increment = 3; -- 步长
2、优点
（1）利用水平扩展机器，解决单点问题；
3、缺点
（1）扩展实例，需要修改步长，操作复杂；
（2）产生ID需要依赖数据库，数据库的性能依然是瓶颈。
三、Redis
当使用数据库来生成ID性能不够要求的时候，我们可以尝试使用Redis来生成ID。通过Redis的原子操作 INCR和INCRBY来实现。
可以使用Redis集群来获取更高的吞吐量。假如一个集群中有3台Redis。可以初始化每台Redis的值分别是0，1，2，然后步长都是3。
优点
（1）不依赖于数据库，性能优于数据库；
（2）ID是有序的。
缺点
（1）强依赖于Redis，Redis宕机也会有风险；
（2）有I/O操作，网络抖动会影响服务响应速度。
四、UUID
UUID 是由一组32位数的16进制数字所构成，是故 UUID 理论上的总数为16^32=2^128，约等于3.4 x 10123。也就是说若每纳秒产生1百万个 UUID，要花100亿年才会将所有 UUID 用完。
UUID生成版本：
version 1, date-time & MAC address
version 2, date-time & group/user id
version 3, MD5 hash & namespace
version 4, pseudo-random number
version 5, SHA-1 hash & namespace
Java实现：
/**
Static factory to retrieve a type 4 (pseudo randomly generated) UUID.
The {@code UUID} is generated using a cryptographically strong pseudo
random number generator.
@return A randomly generated {@code UUID}
/
public static UUID randomUUID() {
SecureRandom ng = Holder.numberGenerator;
byte[] randomBytes = new byte[16];
ng.nextBytes(randomBytes);
randomBytes[6] &= 0x0f; / clear version /
randomBytes[6] |= 0x40; / set to version 4 /
randomBytes[8] &= 0x3f; / clear variant /
randomBytes[8] |= 0x80; / set to IETF variant */
return new UUID(randomBytes);
}
碰撞概率：
Java中的UUID使用的是版本4进行实现，128bit中有122bit是随机产生的，产生的UUID重复概率非常低，所以在使用时可以不考虑此问题。
最终生成UUID：
123e4567-e89b-12d3-a456-426655440000
索引问题：
导致索引重排。
对于B+树的结构：
（1）孩子数和key的数目相同
优点
（1）实现简单；
（2）本地生成，无性能瓶颈；
（3）具备唯一性。
缺点
（1）ID是无序的；
（2）ID无特定含义；
（3）UUID是字符串且长度较长，存储与查询效率慢。
五、号段模式
号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。
CREATE TABLE id_generator (
id int(10) NOT NULL,
max_id bigint(20) NOT NULL COMMENT '当前最大id',
step int(20) NOT NULL COMMENT '号段的布长',
biz_type int(20) NOT NULL COMMENT '业务类型',
version int(20) NOT NULL COMMENT '版本号',
PRIMARY KEY (`id`)
)
a. biz_type ：代表不同业务类型
b. max_id ：当前最大的可用id
c. step ：代表号段的长度
d. version ：是一个乐观锁，每次都更新version，保证并发时数据的正确性
等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。
架构图：
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
由于多业务端可能同时操作，所以采用版本号version乐观锁方式更新，这种分布式ID生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多，查询频率减小到1/step。
优点
（1）ID号码是趋势递增的，满足数据库存储和查询性能要求
（2）可用性高，即使ID生成服务器不可用，也能够使得业务在短时间内可用。
（3）可以自定义max_id的大小，方便业务迁移，方便机器横向扩张
缺点
（1）ID号码不够随机，完整的顺序递增可能带来安全问题；
（2）DB宕机可能导致整个系统不可用，仍然存在这种风险，因为号段只能撑一段时间。
六、雪花算法（SnowFlake）
SnowFlake算法是Twitter开源的分布式ID生成算法。生成长度为64bit的long型的数字作为全局唯一ID。
a. 1bit
第一个bit是符号位，生成的ID是正数，所以第一个bit是0。
**b. 41bit
**41bit可以表示2^41个毫秒值，相当于69年。
c. 10bit
10bit可以表示工作机器，5bit表示（2^5=32个）机房，剩余5bit表示（2^5=32台）机器。表示最多可以标识（2^10=1024台）机器
d. 12bit
用来标识同一毫秒内的（2^12 – 1 = 4095个）不同的id
优点
（1）高性能高可用：生成时不依赖于数据库，完全在内存中生成；
（2）容量大：每秒中能生成数百万的自增ID；
（3）ID自增：存入数据库中，索引效率高。
缺点
（1）依赖系统时钟，如果时间回调或改变，会造成ID冲突。
七、Leaf
号段模式优化
数据库的I/O操作（更新、查询）会是瓶颈，所以需要对此进行优化。
如果在号段消费完之后才从数据库获取新的号段，就会存在2个问题：
（1）查询DB过程出现网络抖动或慢查询会导致系统响应时间变长；
（2）DB的I/O操作本身耗时，如果请求进来但号段未取回就会造成阻塞。
双Buffer
为了能做到DB取号过程能做到无阻塞，当号段消费到某个点时异步吧下一个号段加载到内存中。异步更新，通过双Buffer的方式，保证在DB服务出现问题时，仍然能够有一个Buffer号段能够使用。
详细实现如下图：
采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。
解决时钟问题
因为这种方案依赖时间，如果机器的时钟发生了回拨，那么就会有可能生成重复的ID号，需要解决时钟回退的问题。
参见上图整个启动流程图
（1）服务启动时首先检查自己是否写过ZooKeeper leaf_forever节点：
（2）若写过，则用自身系统时间与leaf_forever/{self}时间则认为机器时间发生了大步长回拨，服务启动失败并报警；
（3）若未写过，证明是新服务节点，直接创建持久节点leaf_forever/
（4）若abs( 系统时间-sum(time)/nodeSize ) < 阈值，认为当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/{self} 维持租约；
（5）否则认为本机系统时间发生大步长偏移，启动失败并报警；
（6）每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}；
参考
[1] B+树简历过程（https://www.jianshu.com/p/08fe11a5fbb9）
[2] 美团Leaf源码分析（https://www.jianshu.com/p/92d34144dcb7）
[3] 美团点评分布式ID生成系统（https://tech.meituan.com/2017/04/21/mt-leaf.html）
[4] 美团分布式ID生成服务开源（https://tech.meituan.com/2019/03/07/open-source-project-leaf.html）