唯一性ID设计思想

唯一性ID设计思想

分布式ID的业务需求

在复杂的分布式系统中，往往需要对大量的数据和消息进行唯一标识。一个能够生成全局唯一ID的系统是非常必要的。

生成ID的硬性要求

1. 全局唯一：ID必须唯一，这是唯一标识的最基本要求。
2. 趋势递增：为了优化写入性能，尤其是在使用BTree数据结构存储索引数据的数据库引擎（如MySQL的InnoDB引擎）中，主键应尽量有序。
3. 单调递增：保证下一个ID一定大于上一个ID。这在事务版本号、IM增量消息、排序等场景中尤为重要。
4. 信息安全：ID不应是连续的，以防止恶意用户轻易猜测或下载特定URL，或竞争对手通过订单号了解业务数据量。因此，某些应用场景下需要生成无规则的ID。
5. 含时间戳：在开发中能够通过ID快速了解其生成时间，这一点非常有用。

可用性要求

1. 高可用：发一个获取分布式ID的请求，服务器就可以保证99.99%的情况下给我创建一个唯一的分布式id。
2. 低延迟：发一个获取分布式ID的请求，服务器响应速度要快。
3. 高QPS：假如并发10万个创建分布式ID请求，服务器要顶得住并能成功创建10万个唯一的分布式id。

唯一性ID策略

Java生成随机的字符串uuid

uuid性能非常高，本地生成，没有网络消耗，如果只考虑唯一性UUID是OK的，但是入数据库的性能较差。

为什么无序的uuid会导致数据库性能变差？

1. 无序：无法预测它的生成顺序，不能生成递增有序的数字。首先分布式id一般都会作为主键，uuid太长，占用存储空间比较大，（128位数字，通常表示为32个十六进制数字）如果是海量数据库，就需要考虑存储量的问题。
2. uuid往往是使用字符串存储：查询的效率比较低。传输数据量大，且不可读。
3. 索引，B+树索引的分裂：既然分布式id是主键，主键是包括索引的，然后mysql的索引是通过b+树来实现的，因为uuid数据是无序的，每一次新的uuid数据的插入，为了查询的优化，都会对索引“底层的B+树进行修改，这一点很不好。插入完全无序，不但会导致一些中间节点产生分裂，也会白白创造出很多不饱和的节点，这样大大降低了数据库插入的性能。

MySQL自增主键

数据库自增主键原理是：基于数据库自增id和MySQL数据库的replace into实现的，这里的replace into 跟insert功能类似，不同点在于replace into首先尝试把数据插入列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除再插入，否则直接插入新数据。

优点：

对于大多数使用场景，递增的主键可以提供更好的性能。这是因为递增的主键意味着数据物理上也是顺序存储的，这有助于减少页面分裂，提高插入和查询效率。

缺点：

DB单点存在宕机风险：无法扛住高并发场景

不适合做分布式ID：系统水平扩展比较困难如果是单机的话还可以，如果是分布式多台机子的话就很难实现了。数据库压力很大，每次获取ID都需要读取一次数据库，性能低。

MySQL集群主键自增

这个方案就是解决mysql的单点问题，在auto_increment基本上面，设置step步长

MySQL_1 配置：

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

MySQL_2 配置：

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

这样两个MySQL实例的自增ID分别就是：

1、3、5、7、9
2、4、6、8、10

那如果集群后的性能还是扛不住高并发咋办？就要进行MySQL扩容增加节点，这是一个比较麻烦的事。

增加第三台MySQL实例需要人工修改一、二两台MySQL实例的起始值和步长，把第三台机器的ID起始生成位置设定在比现有最大自增ID的位置远一些，但必须在一、二两台MySQL实例ID还没有增长到第三台MySQL实例的起始ID值的时候，否则自增ID就要出现重复了，必要时可能还需要停机修改。

优点：

• 解决DB单点问题

缺点：

• 不利于后续扩容，而且实际上单个数据库自身压力还是大，依旧无法满足高并发场景。
• 丧失了ID生成的“绝对递增性”：先访问DB 01生成0,3，再访问DB 02生成1，可能导致在非常短的时间内，ID生成不是绝对递增的

Redis的id生成策略

Redis是单线程的天生保证原子性，可以使用原子操作INCR和INCRBY来实现。

比较适合使用Redis来生成日切流水号。比如：订单号=日期+当日自增长号。可以每天在Redis中生成一个Key，使用INCR进行累加。

优点

• 不依赖于数据库，灵活方便，且性能优于数据库。
• 数字ID天然排序，对分页或者需要排序的结果很有帮助。

缺点

• 如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
• 需要编码和配置的工作量比较大。
• Redis单点故障，影响序列服务的可用性。

雪花算法

使用一个 64 bit 的 long 型的数字作为全局唯一 ID。

1）第一个部分，是 1 个 bit：0，这个是无意义的；二进制里第一个bit如果是1，那么都是负数，但是我们生成的id都是正数，所以第一个Bit统一都是0。1位sign标识位；

2）第二个部分，是 41 个 bit：表示的是时间戳；单位是毫秒。

3）第三个部分，是 5 个 bit：表示的是机房 ID，10001；5位数据中心id

4）第四个部分，是 5 个 bit：表示的是机器 ID，1 1001；5位工作机器id

5）第五个部分，是 12 个 bit：12位自增序列，就是某个机房某台机器上这一毫秒内同时生成的 ID 的序号，从0000 00000000开始计算。记录同一个毫秒内产生的不同id。

对于分布式系统来说雪花算法的优缺点：

（1）优点：

毫秒数在高位，自增序列在低位，整个id都是趋势递增的；

不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成id的性能也是非常高的；

可以根据自身业务特性分配bit位，非常灵活。

（2）缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

雪花算法id作为分片键会有什么问题？

12 bit自增序列号可以表示 2^12 = 4096 个 ID，所以理论上每毫秒（注意是每毫秒ms）的自增长序列(sequence)都从0开始，到4095为止。如果到了4095，则重新从0开始循环（毫秒值也进入下一毫秒）。

核心代码如下：

//如果是同一时间生成的，则进行毫秒内序列
if (lastTimestamp == timestamp) {
     sequence = (sequence + 1) & sequenceMask;
    //毫秒内序列溢出
    if (sequence == 0) {
        //阻塞到下一个毫秒,获得新的时间戳
        timestamp = tilNextMillis(lastTimestamp);
    }
}
//时间戳改变，毫秒内序列重置
else {
    sequence = 0L;
}

低并发下会有什么问题

低并发下的结果表现（高低并发怎么界定？TPS低于1000的都算吧，而其实很多业务系统的单机TPS是达不到1000的）。由于系统并发比较低，每次请求毫秒数几乎都不同，那么，sequence都是0，或者很小的数字。所以，就导致算法生成的id分表后基本集中在前几个下标小的分表里，导致数据倾斜。

解决方法

美团点评的实现里(核心类https://github.com/Meituan-Dianping/Leaf/blob/master/leaf-core/src/main/java/com/sankuai/inf/leaf/snowflake/SnowflakeIDGenImpl.java)其实有对这个问题做过优化，关键优化代码

sequence = RANDOM.nextInt(100);

就是对每毫秒起始的sequence取随值，美团的随机范围是0到100。最终的效果就是生成的id会均匀分布在tb_0到tb_100。而我们如果分表数是256，则需要改成

sequence = RANDOM.nextInt(256);