创建一个基于redis的id生成器

Myth丶恋晨 2023-02-12 05:55 2阅读 0赞

参考文章：

*  https://blog.csdn.net/hengyunabc/article/details/44244951
 *  https://www.jianshu.com/p/955909e1bd71
 *  https://tech.meituan.com/2017/04/21/mt-leaf.html

参考项目：https://github.com/hengyunabc/redis-id-generator值。  
evalsha教程：https://www.runoob.com/redis/scripting-evalsha.html  
eval教程：https://www.runoob.com/redis/scripting-eval.html

--------------------

### 一、分布式id生成器需要满足的要求 ###

#### 1.全局唯一 ####

#### 2.尽可能保证id的递增 ####

> 因为在查询的时候经常会有例如分页以及排序之类的需求，这个时候如果主键的id本身能够体现出时许效率会更加好。而对于常见的排序还有分页，我们解决办法有两种：
> 
> 1.  在数据表中添加一个时间字段，对其创建一个普通索引。
> 2.  id本生就是按照时间大致有序的。

因为常见的普通索引的访问效率是比聚集索引要慢的，所以我们尽可能使用第二种解决方案

#### 3.其他的一些要求 ####

1.  id要尽可能的短，这样可以减少存储的空间以及增加查询的效率。
2.  要有足够数量的id可以使用，不然当数据量非常大时，id耗尽就不行了
3.  要考虑不同机器之间的时间不一致问题
4.  QPS尽量要高，这样就可以，否则例如像类SNOWFLAKE算法会在64位ID中利用部分位数（如12）表示单位时间内生成的ID序号，这部分序号用完了，这个单位时间就不能再生成序号了

--------------------

### 二、常见的id生成器方案： ###

#### 1.利用mysql数据库的自增主键特性 ####

##### 优点： #####

*  简单，代码方便，性能还行
 *  数字的id是递增的，方便进行分页和排序

##### 缺点： #####

*  不同的数据库语法和实现不同，实现数据迁移或者多数据库版本的时候可能会出现一些问题
 *  我们常见的是一主多从数据库，这会产生单点故障，以及性能瓶颈
 *  数据量大时需要考虑分库分表

##### 优化方案： #####

*  使用多个master，对每个master设置的初始id不同，步长不同，例如有四个master，我们可以让master1生成（1，5，9），master2生成（2，6，10），master3生成（3，7，11），master4生成（4，8，12），这样可以降低单个数据库的压力

--------------------

#### 2.UUID ####

> 常见的一种分布式id生成器，可以利用数据库也可以利用代码。

##### 优点： #####

*  简单，方便
 *  生成id的性能好，基本上不会有性能问题
 *  全球唯一，对于数据库合并，迁移等问题不会存在冲突

##### 缺点 #####

*  不是有序的
 *  UUID的字符串长度较长，查询效率不高，且消耗存储空间比较大，如果是海量数据库就需要考虑存储量的问题了
 *  可读性差

--------------------

#### 3.redis生成id ####

> redis的大致原理和普通数据库的生成原理是大致相同的，只不过redis不是使用自增组件，而是使用原子操作 INCR和INCRBY来实现。

##### 优点： #####

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

##### 缺点： #####

*  如果系统中没有Redis，还需要引入新的组件，增加系统复杂度。
 *  需要编码和配置的工作量比较大。

--------------------

#### 4.snowflake算法 ####

> 1.  一个ID由64位生成
> 2.  41bit作为时间戳，记录当前时间到标记的起始时间（如到2018.1.1）差，精确到毫秒，那么服务可用时长为(1<<41)/(1000\* 60 \* 60 \* 24 \* 365) = 69.73年
> 3.  10bit作为机器ID，也就是可以有1024台机器
> 4.  12bit作为序列号，代表单位时间（这里是毫秒）内允许生成的ID总数，也就是1ms内允许生成4096个ID

##### 优点： #####

*  不依赖于数据库，灵活方便，且性能优于数据库。
 *  ID按照时间在单机上是递增的。

##### 缺点： #####

*  在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全局递增的情况。

--------------------

#### 5.类SNOWFLAKE算法 ####

> SNOWFLAKE给出的主要是一个思想，把ID划分为多个段，有不同的含义，可以结合自己的要求进行重新划分。按照个人理解，时间戳位数少了，机器位数多了，序列号位数多了。借鉴snowflake的思想，结合各公司的业务逻辑和并发量，可以实现自己的分布式ID生成算法。

##### 举例，假设某公司ID生成器服务的需求如下： #####

*  单机高峰并发量小于1W，预计未来5年单机高峰并发量小于10W
 *  有2个机房，预计未来5年机房数量小于4个
 *  每个机房机器数小于100台
 *  目前有5个业务线有ID生成需求，预计未来业务线数量小于10个

##### 分析过程如下： #####

*  高位取从2017年1月1日到现在的毫秒数（假设系统ID生成器服务在这个时间之后上线），假设系统至少运行10年，那至少需要10年 \* 365天 \* 24小时 \* 3600秒 \* 1000毫秒 = 320 \* 10 ^ 9，差不多预留39bit给毫秒数
 *  每秒的单机高峰并发量小于10W，即平均每毫秒的单机高峰并发量小于100，差不多预留7bit给每毫秒内序列号
 *  5年内机房数小于4个，预留2bit给机房标识
 *  每个机房小于100台机器，预留7bit给每个机房内的服务器标识
 *  业务线小于10个，预留4bit给业务线标识

##### 这样设计的64bit标识，可以保证： #####

*  每个业务线、每个机房、每个机器生成的ID都是不同的
 *  同一个机器，每个毫秒内生成的ID都是不同的
 *  同一个机器，同一个毫秒内，以序列号区区分保证生成的ID是不同的
 *  将毫秒数放在最高位，保证生成的ID是趋势递增的

##### 缺点： #####

*  由于“没有一个全局时钟”，每台服务器分配的ID是绝对递增的，但从全局看，生成的ID只是趋势递增的（有些服务器的时间早，有些服务器的时间晚）

--------------------

### 三、实现一个简易的redis的id生成器 ###

> 利用redis的lua脚本执行功能，在每个节点上通过lua脚本生成唯一id，其中使用的是雪花算法。  
> 生成的ID是64位的：
> 
>  *  使用41 bit来存放时间，精确到毫秒，可以使用41年。
>  *  使用12 bit来存放逻辑分片ID，最大分片ID是4095
>  *  使用10 bit来存放自增长ID，意味着每个节点，每毫秒最多可以生成1024个ID

比如GTM时间 `Fri Mar 13 10:00:00 CST 2015` ，它的距1970年的毫秒数是 1426212000000，假定分片ID是53，自增长序列是4，则生成的ID是：

// 左移22位，指代最前面14bit的存储信息，再左移10位表示中间存储分片信息的12bit
    5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 4

redis提供了TIME命令，可以取得redis服务器上的秒数和微秒数。因些lua脚本返回的是一个四元组。

second, microSecond, partition, seq

客户端要自己处理，生成最终ID。

((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;

seq对应的是集群中的节点值  
如集群里有3个节点，则节点1返回的seq是：

0, 3, 6, 9, 12 ...

节点2返回的seq是

1, 4, 7, 10, 13 ...

节点3返回的seq是

2, 5, 8, 11, 14 ...

我们可以将lua脚本转换成sha1值，然后通过EVALSHA指令传递这个

##### 下面我们直接看代码 #####

项目主程序

public class Main { 
    
    	public static void main(String[] args) { 
    		String tab = "order";
    		long userId = 123456789;
    
    		IdGenerator idGenerator = IdGenerator.builder()
    				.addHost("127.0.0.1", 6379, "c5809078fa6d652e0b0232d552a9d06d37fe819c")
    // .addHost("127.0.0.1", 7379, "accb7a987d4fb0fd85c57dc5a609529f80ec3722")
    // .addHost("127.0.0.1", 8379, "f55f781ca4a00a133728488e15a554c070b17255")
    				.build();
    
    		long id = idGenerator.next(tab, userId);
    
    		System.out.println("id:" + id);
    		List<Long> result = IdGenerator.parseId(id);
    
    		System.out.println("miliSeconds:" + result.get(0) + ", partition:"
    				+ result.get(1) + ", seq:" + result.get(2));
    	}
    }

##### id生成器相关代码 #####

public class IdGenerator { 
    
    	static final Logger logger = LoggerFactory.getLogger(IdGenerator.class);
    	/** * JedisPool, luaSha */
    	List<Pair<JedisPool, String>> jedisPoolList;
    	int retryTimes;
    
    	int index = 0;
    
    	private IdGenerator() { 
    
    	}
    
    	private IdGenerator(List<Pair<JedisPool, String>> jedisPoolList,
    			int retryTimes) { 
    		this.jedisPoolList = jedisPoolList;
    		this.retryTimes = retryTimes;
    	}
    
    	static public IdGeneratorBuilder builder() { 
    		return new IdGeneratorBuilder();
    	}
    
    	static class IdGeneratorBuilder { 
    		List<Pair<JedisPool, String>> jedisPoolList = new ArrayList();
    		int retryTimes = 5;
    
    		public IdGeneratorBuilder addHost(String host, int port, String luaSha) { 
    			jedisPoolList.add(Pair.of(new JedisPool(host, port), luaSha));
    			return this;
    		}
    
    		public IdGeneratorBuilder retryTimes(int retryTimes) { 
    			this.retryTimes = retryTimes;
    			return this;
    		}
    
    		public IdGenerator build() { 
    			return new IdGenerator(jedisPoolList, retryTimes);
    		}
    	}
    
    	public long next(String tab) { 
    		return next(tab, 0);
    	}
    
    	public long next(String tab, long shardId) { 
    		for (int i = 0; i < retryTimes; ++i) { 
    			Long id = innerNext(tab, shardId);
    			if (id != null) { 
    				return id;
    			}
    		}
    		throw new RuntimeException("Can not generate id!");
    	}
    
    	Long innerNext(String tab, long shardId) { 
    		index++;
    		Pair<JedisPool, String> pair = jedisPoolList.get(index
    				% jedisPoolList.size());
    		JedisPool jedisPool = pair.getLeft();
    
    		String luaSha = pair.getRight();
    		Jedis jedis = null;
    		try { 
    			jedis = jedisPool.getResource();
    			List<Long> result = (List<Long>) jedis.evalsha(luaSha, 2, tab, "" + shardId);
    			long id = buildId(result.get(0), result.get(1), result.get(2),
    					result.get(3));
    			return id;
    		} catch (JedisConnectionException e) { 
    			if (jedis != null) { 
    				jedisPool.returnBrokenResource(jedis);
    			}
    			logger.error("generate id error!", e);
    		} finally { 
    			if (jedis != null) { 
    				jedisPool.returnResource(jedis);
    			}
    		}
    		return null;
    	}
    
    	public static long buildId(long second, long microSecond, long shardId,
    			long seq) { 
    		long miliSecond = (second * 1000 + microSecond / 1000);
    		return (miliSecond << (12 + 10)) + (shardId << 10) + seq;
    	}
    
    	public static List<Long> parseId(long id) { 
    		long miliSecond = id >>> 22;
    		// 2 ^ 12 = 0xFFF
    		long shardId = (id & (0xFFF << 10)) >> 10;
    		long seq = id & 0x3FF;
    
    		List<Long> re = new ArrayList<Long>(4);
    		re.add(miliSecond);
    		re.add(shardId);
    		re.add(seq);
    		return re;
    	}
    }

> 至此我们的基于redis的id生成器就完成了