分布式系统生成唯一id常见方案

柔情只为你懂 2022-01-16 12:07 363阅读 0赞

分布式系统中全局唯一id是我们经常用到的，生成全局id方法由很多，我们选择的时候也比较纠结。每种方式都有各自的使用场景，如果我们熟悉各种方式及优缺点，使用的时候才会更方便。下面我们就一起来看一下常见的生成全局唯一id的方法

## 本文主要讨论 ##

常见的生成全局唯一id有哪些？  
他们各有什么优缺点？

## 1. 使用数据库自动增长序列实现 ##

使用数据库的自动增长来实现，算是常见最简单的解决方案，数据库内部可以确保生成id的唯一性。

**优点：**  
1）实现简单  
2）id是有序的，对于有排序需求的比较有利

**缺点：**  
1）依赖于数据库数据插入，性能比较低  
2）对数据库有依赖，每种数据库可能实现不一样，数据库切换时候，涉及到代码的修改，不利于扩展

## 2. 使用UUID实现 ##

也是比较常见的解决方案，uuid全球唯一。

**优点：**  
1）代码简单  
2）性能比较好  
3）对其他无依赖，方便扩展

**缺点：**  
1）uuid是一段很长的字符，没有排序的，无法保证按顺序递增  
2）uuid比较长，存储在数据库中占用的空间也比较大，不利于检索和排序  
3）生成的数据比较长，数据量大的情况下，对传输效率也会有影响

## 3. 使用redis实现 ##

我们可以使用redis的原子操作 **INCR**和**INCRBY**来实现，redis性能也比较高，若单机存在性能瓶颈，无法满足业务需求，可以采用集群的方式来实现。

多个集群之间增加步长来避免生成id重复的问题，**如有5台redis：**  
第1台生成：1、6、11、16  
第2台生成：2、7、12、17  
第3台生成：3、8、13、18  
第4台生成：4、9、14、19  
第5台生成：5、10、15、20

redis重启的时候，数据可能会丢失，可以在生成的id前面加上一个时间戳来做到唯一性。

**优点：**  
1）性能比较高  
2）生成的数据是有序的，对排序业务有利

**缺点：**  
1）依赖于redis，需要系统引进redis组件，增加了系统的复杂性

## 4. 使用Twitter的snowflake算法实现 ##

这个是twitter的一个全局唯一id生成器，结果是一个long型的ID。其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。具体实现的代码可以参看https://github.com/twitter/snowflake

直接上代码：

package com.yjd.comm.util;/**
 * Created by pc on 2017/8/16 0016.
 */
 
 /**
 * Twitter_Snowflake 
 * SnowFlake的结构如下(每部分用-分开): 
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0 
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69 
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId 
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号 
 * 加起来刚好64位，为一个Long型。 
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
 public class SnowflakeIdWorker {
 
 // ==============================Fields===========================================
 /**
 * 开始时间截 (2015-01-01)
 */
 private final long twepoch = 1420041600000L;
 
 /**
 * 机器id所占的位数
 */
 private final long workerIdBits = 5L;
 
 /**
 * 数据标识id所占的位数
 */
 private final long datacenterIdBits = 5L;
 
 /**
 * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
 */
 private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
 /**
 * 支持的最大数据标识id，结果是31
 */
 private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 
 /**
 * 序列在id中占的位数
 */
 private final long sequenceBits = 12L;
 
 /**
 * 机器ID向左移12位
 */
 private final long workerIdShift = sequenceBits;
 
 /**
 * 数据标识id向左移17位(12+5)
 */
 private final long datacenterIdShift = sequenceBits + workerIdBits;
 
 /**
 * 时间截向左移22位(5+5+12)
 */
 private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 
 /**
 * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
 */
 private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
 /**
 * 工作机器ID(0~31)
 */
 private long workerId;
 
 /**
 * 数据中心ID(0~31)
 */
 private long datacenterId;
 
 /**
 * 毫秒内序列(0~4095)
 */
 private long sequence = 0L;
 
 /**
 * 上次生成ID的时间截
 */
 private long lastTimestamp = -1L;
 
 //==============================Constructors=====================================
 
 /**
 * 构造函数
 *
 * @param workerId 工作ID (0~31)
 * @param datacenterId 数据中心ID (0~31)
 */
 public SnowflakeIdWorker(long workerId, long datacenterId) {
 if (workerId > maxWorkerId || workerId < 0) {
 throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
 }
 if (datacenterId > maxDatacenterId || datacenterId < 0) {
 throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
 }
 this.workerId = workerId;
 this.datacenterId = datacenterId;
 }
 
 // ==============================Methods==========================================
 
 /**
 * 获得下一个ID (该方法是线程安全的)
 *
 * @return SnowflakeId
 */
 public synchronized long nextId() {
 long timestamp = timeGen();
 
 //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
 if (timestamp < lastTimestamp) {
 throw new RuntimeException(
 String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
 }
 
 //如果是同一时间生成的，则进行毫秒内序列
 if (lastTimestamp == timestamp) {
 sequence = (sequence + 1) & sequenceMask;
 //毫秒内序列溢出
 if (sequence == 0) {
 //阻塞到下一个毫秒,获得新的时间戳
 timestamp = tilNextMillis(lastTimestamp);
 }
 }
 //时间戳改变，毫秒内序列重置
 else {
 sequence = 0L;
 }
 
 //上次生成ID的时间截
 lastTimestamp = timestamp;
 
 //移位并通过或运算拼到一起组成64位的ID
 return ((timestamp - twepoch) << timestampLeftShift) //
 | (datacenterId << datacenterIdShift) //
 | (workerId << workerIdShift) //
 | sequence;
 }
 
 /**
 * 阻塞到下一个毫秒，直到获得新的时间戳
 *
 * @param lastTimestamp 上次生成ID的时间截
 * @return 当前时间戳
 */
 protected long tilNextMillis(long lastTimestamp) {
 long timestamp = timeGen();
 while (timestamp <= lastTimestamp) {
 timestamp = timeGen();
 }
 return timestamp;
 }
 
 /**
 * 返回以毫秒为单位的当前时间
 *
 * @return 当前时间(毫秒)
 */
 protected long timeGen() {
 return System.currentTimeMillis();
 }
 
 //==============================Test=============================================
 
 /**
 * 测试
 */
 public static void main(String[] args) {
 SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 1);
 long startime = System.currentTimeMillis();
 for (int i = 0; i < 4000000; i++) {
 long id = idWorker.nextId();
 // System.out.println(Long.toBinaryString(id));
 // System.out.println(id);
 }
 System.out.println(System.currentTimeMillis() - startime);
 }
 }

## 5. 使用数据库+本地缓存实现 ##

数据库中存储一个数字类型的字段cur\_value，初始化为0，我们每次可以申请n个数字，过程：  
1）创建表

CREATE TABLE `yjd_id_generator` (
      `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '编号',
      `code` varchar(64) NOT NULL DEFAULT '' COMMENT '编码',
      `cur_value` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前值',
      `description` varchar(128) NOT NULL DEFAULT '' COMMENT '说明',
      PRIMARY KEY (`id`),
      UNIQUE KEY `idx_uq_code` (`code`)
    ) ENGINE=InnoDB AUTO_INCREMENT=24 DEFAULT CHARSET=utf8 COMMENT='id生成器，cur_value每次递增一定的范围'

cur\_value记录当前已申请到的最大值。

2) 通过code查询表yjd\_id\_generator中的记录，将cur\_value更新为cur\_value+n，更新成功，表示(cur\_value,n\]范围内的数字我们申请成功，可以使用。存在一个并发问题，需要避免多个线程同时更新的问题，我们可以通过使用cur\_value作为条件进行更新，即采用乐观锁的方式进行更新，如果更新成功，表示申请成功，假如查询的cur\_value值为100，那么在cur\_value上递增100，此时cur\_value = 200，执行如下更新操作:

update yjd_id_generator set cur_value = 200 where code = '业务编码’ and cur_value = 100;

若上面的sql执行成功，表示更新成功，上面通过乐观锁保证了并发情况下只有一个请求会执行成功。如果更新失败，表示cur\_value被其他线程更新了，需要重复获取记录继续执行更新操作，类似于java中的cas操作。

4) 把生成好的id放在本地内存缓存队列中给系统使用；效率也是非常高的。

代码如下：

public class IdGeneratorUtil {
 public interface ICode {
 String code();
 }
 
 private static Logger logger = Logger.getLogger(IdGeneratorUtil.class);
 private static final String SERVICE = "idGeneratorService";
 private static Long stepValue = 100L;
 
 /**
 * 禁止直接访问该list的值,通过getAllDicts()来访问
 */
 private volatile static Map<String, IdGenerator> idMap = FrameUtil.newHashMap();
 private volatile static Object idMapLock = new Object();
 
 public static IIdGeneratorService getService() {
 return ServiceHolder.getService(IIdGeneratorService.class, SERVICE, RpmServiceKeyEnum.RPM_PUBLIC_KEY_E.getDubboFileName(), true);
 }
 
 /**
 * 获取id
 *
 * @param code
 * @return
 * @throws Exception
 */
 public static long getId0(ICode code) throws Exception {
 return getId(code.code());
 }
 
 /**
 * 获取id
 *
 * @param code
 * @return
 * @throws Exception
 */
 public static long getId(String code) throws Exception {
 IdGenerator idGenerator = idMap.get(code);
 if (idGenerator == null) {
 synchronized (idMapLock) {
 idGenerator = idMap.get(code);
 if (idGenerator == null) {
 Range range = getDbId(code);
 idGenerator = new IdGenerator(range, new AtomicLong(range.getLeft()));
 idMap.put(code, idGenerator);
 }
 }
 }
 long value = idGenerator.getIdValue().getAndIncrement();
 if (value > idGenerator.getRange().getRight()) {
 synchronized (idMapLock) {
 idMap.remove(code);
 }
 value = getId(code);
 }
 return value;
 
 }
 
 private static class IdGenerator {
 private Range range;
 private AtomicLong idValue;
 
 public IdGenerator() {
 }
 
 public IdGenerator(Range range, AtomicLong idValue) {
 this.range = range;
 this.idValue = idValue;
 }
 
 public Range getRange() {
 return range;
 }
 
 public void setRange(Range range) {
 this.range = range;
 }
 
 public AtomicLong getIdValue() {
 return idValue;
 }
 
 public void setIdValue(AtomicLong idValue) {
 this.idValue = idValue;
 }
 }
 
 private static class Range {
 private long left;
 private long right;
 
 private Range(Builder builder) {
 setLeft(builder.left);
 setRight(builder.right);
 }
 
 public static Builder newBuilder() {
 return new Builder();
 }
 
 public long getLeft() {
 return left;
 }
 
 public void setLeft(long left) {
 this.left = left;
 }
 
 public long getRight() {
 return right;
 }
 
 public void setRight(long right) {
 this.right = right;
 }
 
 public static final class Builder {
 private long left;
 private long right;
 
 private Builder() {
 }
 
 public Builder left(long val) {
 left = val;
 return this;
 }
 
 public Builder right(long val) {
 right = val;
 return this;
 }
 
 public Range build() {
 return new Range(this);
 }
 }
 }
 
 private static Range getDbId(String code) throws Exception {
 IIdGeneratorService service = getService();
 IdGeneratorModel model = service.getModelOne(FrameUtil.newHashMap("code", code), DbWREnums.WRITE);
 long left = 0, right = 0;
 if (model == null) {
 left = 1;
 right = left + stepValue - 1;
 model = new IdGeneratorModel();
 model.setCode(code);
 model.setCur_value(right);
 service.insert(model);
 } else {
 while (true) {
 Long cur_value = model.getCur_value();
 left = cur_value + 1;
 right = left + stepValue - 1;
 long where_cur_value = cur_value;
 if (service.updateByMap(FrameUtil.newHashMap("id", model.getId(), "cur_value", right, "where_cur_value", where_cur_value)) == 1) {
 break;
 }
 model = service.getModelOne(FrameUtil.newHashMap("code", code), DbWREnums.WRITE);
 }
 }
 return Range.newBuilder().left(left).right(right).build();
 }
 }

**优点：**  
1）性能比较高  
2）生成的数据是有序的，对排序业务有利

**缺点：**  
1）依赖于数据库

## 总结 ##

本文介绍了5中方式供大家选择，大家如果有其他方式可以分享交流。

转载于:https://blog.51cto.com/4217431/2397834