0%

创建一个基于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生成器就完成了