0%

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

发表于 分类于
在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。这个时候如何创建连续不重复的就尤为重要了，下面我们就整理一下常见的id生成器以及使用redis去实现一个id生成器

参考文章：

参考项目：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是：

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

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

1
second, microSecond, partition, seq

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

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

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

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

节点2返回的seq是

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

节点3返回的seq是

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

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

下面我们直接看代码

项目主程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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生成器相关代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
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生成器就完成了