Java生成随机的字符串uuid & 数据库自增主键 & redis的id生成策略 & 雪花算法 & 百度的UidGenerator算法

 

一、分布式ID的业务需求

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

 

二、生成id的硬性要求

1. 全局唯一：不能出现重复的id号，既然是唯一标识，这是最基本的要求。
2. 趋势递增：在mysql的innoDB引擎中使用的是聚集索引，由于多数RDBMS使用BTree的数据结构来存储索引数据。因此在主键的选择上我们应该尽量使用有序的主键保证写入性能。
3. 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号，IM增量消息、排序等特殊需求。
4. 信息安全：如果id是连续的，恶意获取用户工作就非常容易做了，直接按照顺序下载指定的URL即可；如果是订单号就更危险了，竞争对手可以直接知道我们一天的单量，所以在一些应用场景下，需要无规则的id。
5. 含时间戳：这样能够在开发中快速了解分布式id的生成时间。

 

三、id生成系统的可用性要求

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

 

四、Java生成随机的字符串uuid

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

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

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

 

五、数据库自增主键

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

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

 

六、redis的id生成策略

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

但是缺点同上面的mysql一样，不利于平行扩容。同时key一定要设置有效期，不过可以使用redis集群来获取更高的吞吐量。

假如一个集群中有5台Redis,可以初始化每台Redis的值分别是1,2,3,4,5,然后步长都是5
各个Redis生成的ID为:
A: 1,6,11,16,21
B: 2,7,12,17,22
C:3.8.13.18.23
D: 4,9,14,19,24
E: 5,10,15,20,25

七、雪花算法

使用一个 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：表示的序号，就是某个机房某台机器上这一毫秒内同时生成的 ID 的序号，0000 00000000。记录同一个毫秒内产生的不同id。12位自增序列

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

（1）优点：

1. 毫秒数在高位，自增序列在低位，整个id都是趋势递增的；
2. 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成id的性能也是非常高的；
3. 可以根据自身业务特性分配bit位，非常灵活。

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

 

 雪花算法生成唯一id的demo示例:

导入依赖：

<!--hutool 测试雪花算法-->
        <dependency>
            <groupId>cn.hutool</groupId>
            <artifactId>hutool-captcha</artifactId>
            <version>5.2.0</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.16.18</version>
        </dependency>
        <!-- https://mvnrepository.com/artifact/org.slf4j/slf4j-api -->
        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-api</artifactId>
            <version>1.7.25</version>
        </dependency>

import cn.hutool.core.lang.Snowflake;
import cn.hutool.core.net.NetUtil;
import cn.hutool.core.util.IdUtil;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Component;

/**
 * 雪花算法生成UUID，测试demo
 */
@Slf4j
@Component
public class IdGeneratorSnowFlake {

    private long workerId = 0;
    private long datacenterId = 1;
    private Snowflake snowflake = IdUtil.createSnowflake(workerId,datacenterId);

    public void init() {
        try{
            workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
            log.info("当前机器得workerId:{}",workerId);
        } catch (Exception e) {
            log.info("当前机器的workerId获取失败",e);
            workerId = NetUtil.getLocalhostStr().hashCode();
            log.info("当前机器workId:{}",workerId);
        }
    }

    public synchronized long snowflakeId() {
        return snowflake.nextId();
    }

    public synchronized long snowflakeId (long workerId,long datacenterId) {
        snowflake = IdUtil.createSnowflake(workerId,datacenterId);
        return snowflake.nextId();
    }

    public static void main(String[] args) {
        //1440603845439913984
        //1440603918894759936
        System.out.println(new IdGeneratorSnowFlake().snowflakeId());
    }
}

 

八、UidGenerator算法

UidGenerator算法是对雪花算法的改进。

UidGenerator的组成：sign（1bit）+ delta seconds (28bits) + worker node id (22bits) + sequence (13bits)

UidGenerator能保证“指定机器&同一时刻&某一并发序列”，是唯一，并据此生成一个64bits的唯一id（long),且默认采用上图字节分配方式。

UidGenerator与原版的雪花算法不同，UidGenerator还支持自定义时间戳、工作机器id和序列号等各部位的位数，以应用于不同场景。

• 1）sign(1bit)：固定1bit符号标识，即生成的UID为正数。
• 2）delta seconds (28 bits)：当前时间，相对于时间基点"2016-05-20"的增量值，单位：秒，最多可支持约8.7年（注意：(a)这里的单位是秒，而不是毫秒！ (b)注意这里的用词，是“最多”可支持8.7年）。
• 3）worker id (22 bits)：机器id，最多可支持约420w次机器启动。内置实现为在启动时由数据库分配，默认分配策略为用后即弃，后续可提供复用策略。
• 4）sequence (13 bits)：每秒下的并发序列，13 bits可支持每秒8192个并发（注意下这个地方，默认支持qps最大为8192个）。

UidGenerator的两种实现方式：

（1）DefaultUidGenerator 

通过DefaultUidGenerator 实现，对时钟回拨的处理比较简单粗暴，另外如果使用DefaultUidGenerator 方式生成分布式id，一定要根据你的业务的情况和特点，调整各个字段占用的位数。

（2）CachedUidGenerator

CachedUidGenerator是在DefaultUidGenerator 的基础上进行了改进，它的核心是利用了RingBuffer，本质上是一个数组，数组中每个项被称为slot，CachedUidGenerator设计了两个RingBuffer,一个保存唯一id，一个保存flag，RingBuffer的尺寸是2^n，n必须是正整数。

CachedUidGenerator主要通过采取如下一些措施和方案规避了时钟回拨的问题和增强唯一性：

• 自增列：CachedUidGenerator的workerid在实例每次重启时初始化，且就是数据库的自增id，从而完美的实现每个实例获取到的workerid不会有任何冲突；
• RingBuffer：CachedUidGenerator不再在每次取ID时都实时计算分布式ID，而是利用RingBuffer数据结构预先生成若干个分布式ID并保存；
• 时间递增：传统的SnowFlake算法实现都是通过System.currentTimeMillis()来获取时间并与上一次时间进行比较，这样的实现严重依赖服务器的时间。而CachedUidGenerator的时间类型是AtomicLong，且通过incrementAndGet()方法获取下一次的时间，从而脱离了对服务器时间的依赖，也就不会有时钟回拨的问题（这种做法也有一个小问题，即分布式ID中的时间信息可能并不是这个ID真正产生的时间点，例如：获取的某分布式ID的值为3200169789968523265，它的反解析结果为{"timestamp":"2019-05-02 23:26:39","workerId":"21","sequence":"1"}，但是这个ID可能并不是在"2019-05-02 23:26:39"这个时间产生的）。

CachedUidGenerator通过缓存的方式预先生成一批唯一ID列表，可以解决唯一ID获取时候的耗时。但这种方式也有不好点，一方面需要耗费内存来缓存这部分数据，另外如果访问量不大的情况下，提前生成的UID中的时间戳可能是很早之前的。而对于大部分的场景来说，DefaultUidGenerator 就可以满足相关的需求了，没必要来凑CachedUidGenerator这个热闹。

CachedUidGenerator测试：

不管如何配置, CachedUidGenerator总能提供600万/s的稳定吞吐量，只是使用年限会有所减少。