搞懂分布式技术12:分布式ID生成方案

  1. 云栖社区>
  2. 博客>
  3. 正文

搞懂分布式技术12:分布式ID生成方案

黄小斜 2018-06-23 16:19:21 浏览598
展开阅读全文

分布式ID生成器 | 架构师之路

原创: 58沈剑 架构师之路 2017-06-25

一、需求缘起

几乎所有的业务系统,都有生成一个唯一记录标识的需求,例如:

  • 消息标识:message-id

  • 订单标识:order-id

  • 帖子标识:tiezi-id

 

这个记录标识往往就是数据库中的主键,数据库上会建立聚集索引(cluster index),即在物理存储上以这个字段排序。

 

这个记录标识上的查询,往往又有分页或者排序的业务需求,例如:

  • 拉取最新的一页消息

    select message-id/ order by time/ limit 100

  • 拉取最新的一页订单

    select order-id/ order by time/ limit 100

  • 拉取最新的一页帖子

    select tiezi-id/ order by time/ limit 100

 

所以往往要有一个time字段,并且在time字段上建立普通索引(non-cluster index)。

 

普通索引存储的是实际记录的指针,其访问效率会比聚集索引慢,如果记录标识在生成时能够基本按照时间有序,则可以省去这个time字段的索引查询:

select message-id/ (order by message-id)/limit 100

 

强调,能这么做的前提是,message-id的生成基本是趋势时间递增的

 

这就引出了记录标识生成(也就是上文提到的三个XXX-id)的两大核心需求:

  • 全局唯一

  • 趋势有序

这也是本文要讨论的核心问题:如何高效生成趋势有序的全局唯一ID。

 

二、常见方法、不足与优化

方法一:使用数据库的 auto_increment 来生成全局唯一递增ID

 

优点:

  • 简单,使用数据库已有的功能

  • 能够保证唯一性

  • 能够保证递增性

  • 步长固定

 

缺点:

  • 可用性难以保证:数据库常见架构是一主多从+读写分离,生成自增ID是写请求,主库挂了就玩不转了

  • 扩展性差,性能有上限:因为写入是单点,数据库主库的写性能决定ID的生成性能上限,并且难以扩展

 

改进方法:

  • 冗余主库,避免写入单点

  • 数据水平切分,保证各主库生成的ID不重复


如上图所述,由1个写库变成3个写库,每个写库设置不同的auto_increment初始值,以及相同的增长步长,以保证每个数据库生成的ID是不同的(上图中库0生成0,3,6,9…,库1生成1,4,7,10,库2生成2,5,8,11…

 

改进后的架构保证了可用性,但缺点是:

  • 丧失了ID生成的“绝对递增性”:先访问库0生成0,3,再访问库1生成1,可能导致在非常短的时间内,ID生成不是绝对递增的(这个问题不大,目标是趋势递增,不是绝对递增)

  • 数据库的写压力依然很大,每次生成ID都要访问数据库

 

为了解决上述两个问题,引出了第二个常见的方案。

 

方法二:单点批量ID生成服务

 

分布式系统之所以难,很重要的原因之一是“没有一个全局时钟,难以保证绝对的时序”,要想保证绝对的时序,还是只能使用单点服务,用本地时钟保证“绝对时序”。

 

数据库写压力大,是因为每次生成ID都访问了数据库,可以使用批量的方式降低数据库写压力

 


如上图所述,数据库使用双master保证可用性,数据库中只存储当前ID的最大值,例如0。

 

ID生成服务假设每次批量拉取6个ID,服务访问数据库,将当前ID的最大值修改为5,这样应用访问ID生成服务索要ID,ID生成服务不需要每次访问数据库,就能依次派发0,1,2,3,4,5这些ID了。

 

当ID发完后,再将ID的最大值修改为11,就能再次派发6,7,8,9,10,11这些ID了,于是数据库的压力就降低到原来的1/6。

 

优点:

  • 保证了ID生成的绝对递增有序

  • 大大的降低了数据库的压力,ID生成可以做到每秒生成几万几十万个

 

缺点:

  • 服务仍然是单点

  • 如果服务挂了,服务重启起来之后,继续生成ID可能会不连续,中间出现空洞(服务内存是保存着0,1,2,3,4,5,数据库中max-id是5,分配到3时,服务重启了,下次会从6开始分配,4和5就成了空洞,不过这个问题也不大)

  • 虽然每秒可以生成几万几十万个ID,但毕竟还是有性能上限,无法进行水平扩展

 

改进方法:

单点服务的常用高可用优化方案是“备用服务”,也叫“影子服务”,所以我们能用以下方法优化上述缺点(1):


如上图,对外提供的服务是主服务,有一个影子服务时刻处于备用状态,当主服务挂了的时候影子服务顶上。

 

这个切换的过程对调用方是透明的,可以自动完成,常用的技术是vip+keepalived,具体就不在这里展开。

 

另外,ID-gen-service也可以实施水平扩展,以解决上述缺点(3),但会引发一致性问题,具体解决方案详见《浅谈CAS在分布式ID生成方案上的应用》。

 

方法三:uuid/guid

 

不管是通过数据库,还是通过服务来生成ID,业务方Application都需要进行一次远程调用,比较耗时。

 

有没有一种本地生成ID的方法,即高性能,又时延低呢?

 

uuid是一种常见的方案:

string ID =GenUUID();

 

优点:

  • 本地生成ID,不需要进行远程调用,时延低

  • 扩展性好,基本可以认为没有性能上限

 

缺点:

  • 无法保证趋势递增

  • uuid过长,往往用字符串表示,作为主键建立索引查询效率低,常见优化方案为“转化为两个uint64整数存储”或者“折半存储”(折半后不能保证唯一性)

 

方法四:取当前毫秒数

 

uuid是一个本地算法,生成性能高,但无法保证趋势递增,且作为字符串ID检索效率低,有没有一种能保证递增的本地算法呢

 

取当前毫秒数是一种常见方案:

uint64 ID = GenTimeMS();

 

优点:

  • 本地生成ID,不需要进行远程调用,时延低

  • 生成的ID趋势递增

  • 生成的ID是整数,建立索引后查询效率高

 

缺点:

  • 如果并发量超过1000,会生成重复的ID

 

这个缺点要了命了,不能保证ID的唯一性。当然,使用微秒可以降低冲突概率,但每秒最多只能生成1000000个ID,再多的话就一定会冲突了,所以使用微秒并不从根本上解决问题。

 

方法五:类snowflake算法

 

snowflake是twitter开源的分布式ID生成算法,其核心思想为,一个long型的ID:

  • 41bit作为毫秒数

  • 10bit作为机器编号

  • 12bit作为毫秒内序列号

 

算法单机每秒内理论上最多可以生成1000*(2^12),也就是400W的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来生成唯一Id

在之前的项目中需要用到一个自动增长的主键,该主键需要包含字母,所以没有办法用到数据库的自增主键。楼主要高手的指导下,发现Redis的RedisAtomicLong类可以解决这个麻烦。而且redis为单线程,不存在线程安全问题

那么,就让楼主来介绍一下RedisAtomicLong类吧~

RedisAtomicLong类的构造方法如下:

  • 构造方法一:

    1

    2

    public RedisAtomicLong(java.lang.String redisCounter,

                   RedisConnectionFactory factory)

      

该实例对应的自动增长的主键的key的名字为为redisCounter,如果redis中存在key的name为redisCounter的键值对,那么,则取其值;否则,将redisCounter对应的key值设置为0;

  • 构造方法二:

    1

    2

    3

    public RedisAtomicLong(java.lang.String redisCounter,

                   RedisConnectionFactory factory,

                   long initialValue)  

创建一个新的RedisAtomicLong实例,该实例对应的自动增长的主键的key的名字为为redisCounter,并将key name为redisCounter的值设置为initialValue;

RedisAtomicLong类有以下几个主要的方法:

  • 方法一:

    1

    public long get();//返回当前的值

      

  • 方法二:

    1

    public void set(long newValue);//设置当前实例的值为newValue

      

  • 方法三:

    1

    public long incrementAndGet();//将当前实例的key值加一并且返回

      

那么,我们如何获得一个RedisAtomicLong实例呢?楼主提供以下两个方法:

在获取实例之前,我们需要设置好jedis的配置。 
在application.xml文件中,加入以下配置:

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

<bean id="jedisPoolConfig" class="redis.clients.jedis.JedisPoolConfig">

    <property name="maxTotal" value="${redis.pool.maxTotal}" />

    <property name="maxIdle" value="${redis.pool.maxIdle}" />

    <property name="testOnBorrow" value="${redis.pool.testOnBorrow}" />

</bean>

 

<!-- jedis服务器配置 -->

<bean id="jedisShardInfo" class="redis.clients.jedis.JedisShardInfo">

    <constructor-arg index="0" value="${redis.ip}" />

    <constructor-arg index="1" value="${redis.port}" type="int" />

</bean>

 

<bean id="jedisConnFactory"       class="org.springframework.data.redis.connection.jedis.JedisConnectionFactory" 

        p:host-name="${redis.ip}" p:port="${redis.port}"p:password="${redis.pass}"  p:pool-config-ref="jedisPoolConfig"/>

 

 

<bean id="redisTemplate"class="org.springframework.data.redis.core.RedisTemplate">

    <property name="connectionFactory" ref="jedisConnFactory"/>

    <property name="keySerializer" ref="keySerializer"/>

    <property name="enableTransactionSupport" value="false"/>

</bean>

 

<!-- redis 序列化-->

<bean id="keySerializer"

    class="org.springframework.data.redis.serializer.StringRedisSerializer" />

  

方法一:直接在配置文件中配置

1

2

3

4

5

<!-- someKey为设置的自增长主键的key的名字-->

<bean id="redisAtomicLong"class="org.springframework.data.redis.support.atomic.RedisAtomicLong">

        <constructor-arg name="redisCounter" value="someKey"></constructor-arg>

        <constructor-arg name="factory" ref="jedisConnFactory"></constructor-arg>

</bean> 

在需要用到redisAtomicLong实例的类里面加入下面这段代码即可

1

2

@Resource

private RedisAtomicLong redisAtomicLong;

  

方法二:在代码中直接获得

1

RedisAtomicLong redisAtomicLong = newRedisAtomicLong("someKey",redisTemplate.getConnectionFactory());

  

好了,获得redisAtomicLong实例之后如何来获得自动增长的值呢?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

// 第一次,设置初始值

long original = 0L;

 

// 获取 code 值

original = redisAtomicLong.get();

System.out.println("*****************original:"+original);

 

// 第一次,设置初始值

if (original == 0L) {

    redisAtomicLong.set(5L);

}

//获得加1后的值

long now = redisAtomicLong.incrementAndGet();

System.out.println("*****************now:"+now);

 

 

 

输出值:

*****************original:0

*****************now:6

  

有人或许会问,如果我想要同时有两个自增长的主键怎么办?下面的这段代码就可以解决这个问题~

1

2

3

4

5

6

7

8

9

10

11

12

13

14

RedisAtomicLong atomicLong1 = new RedisAtomicLong("somekey1", redisTemplate.getConnectionFactory(),3L);//创建实例的时候就设置初始值为3

RedisAtomicLong atomicLong2 = new RedisAtomicLong("somekey2", redisTemplate.getConnectionFactory(),5L);//创建实例的时候就设置初始值为5

 

long now1 = atomicLong1.incrementAndGet();

long now2 = atomicLong2.incrementAndGet();

 

System.out.println("*****************now:"+now1);

System.out.println("*****************now:"+now2);

 

 

 

输出值:

*****************now:6

*****************now:7

二:redis集群部署生成全局id 

基于redis的分布式ID生成器

2015年03月13日 19:22:59

阅读数:29716

项目地址

https://github.com/hengyunabc/redis-id-generator

基于redis的分布式ID生成器。

准备

首先,要知道redis的EVAL,EVALSHA命令:

http://redis.readthedocs.org/en/latest/script/eval.html

http://redis.readthedocs.org/en/latest/script/evalsha.html

原理

利用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是:

5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 4
  • 1

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

second, microSecond, partition, seq
  • 1

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

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

集群实现原理

假定集群里有3个节点,则节点1返回的seq是:

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

节点2返回的seq是

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

节点3返回的seq是

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

这样每个节点返回的数据都是唯一的。

单个节点部署

下载redis-script-node1.lua,并把它load到redis上。

cd redis-directory/
wget https://raw.githubusercontent.com/hengyunabc/redis-id-generator/master/redis-script-node1.lua
./redis-cli script load "$(cat redis-script-node1.lua)" 
  • 1
  • 2
  • 3

获取lua脚本的sha1值,可能是:

fce3758b2e0af6cbf8fea4d42b379cd0dc374418
  • 1

在代码里,通过EVALSHA命令,传递这个sha1值,就可以得到生成的ID。

比如,通过命令行执行:

./redis-cli EVALSHA fce3758b2e0af6cbf8fea4d42b379cd0dc374418 2 test 123456789
  • 1

结果可能是:

1) (integer) 1426238286
2) (integer) 130532
3) (integer) 277
4) (integer) 4
  • 1
  • 2
  • 3
  • 4

集群部署

假定集群是3个节点,则分别对三个节点执行:

./redis-cli -host node1 -p 6379 script load "$(cat redis-script-node1.lua)" 
./redis-cli -host node2 -p 7379 script load "$(cat redis-script-node2.lua)" 
./redis-cli -host node3 -p 8379 script load "$(cat redis-script-node3.lua)" 
  • 1
  • 2
  • 3

性能

redis默认配置。

单节点,单线程:
time:0:00:00.959
speed:10427.52867570386
单节点,20线程:
time:0:00:06.710
speed:29806.259314456034
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

结论: 
- 单节点,qps约3w 
- 可以线性扩展,3个结点足以满足绝大部分的应用

java客户端封装

在redis-id-generator-java目录下,有example和benchmark代码。

在调用时,要传入两个参数 
- tag,即为哪一类服务生成ID 
- shardId,即分片由哪个ID生成,比如一个用户的订单,则分片ID应该由userId来生成

public class Example {

    public static void main(String[] args) {
        String tab = "order";
        long userId = 123456789;

        IdGenerator idGenerator = IdGenerator.builder()
                .addHost("127.0.0.1", 6379, "fce3758b2e0af6cbf8fea4d42b379cd0dc374418")
//              .addHost("127.0.0.1", 7379, "1abc55928f37176cb934fc7a65069bf32282d817")
//              .addHost("127.0.0.1", 8379, "b056d20feb3f89483b10c81027440cbf6920f74f")
                .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));
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

多语言客户端

只要支持redis evalsha命令就可以了。

其它

之前写的一个blog:分片(Sharding)的全局ID生成

使用zookeeper生成全局id

  Session是Zookeeper中的会话实体,代表了一个客户端会话。SessionID用来唯一标识一个会话,因此Zookeeper必须保证sessionID的全局唯一性,在每次客户端向服务端发起"会话创建"请求时,服务端都会为其分配一个sessionID。那么Zookeeper是如何实现的呢?

在SessionTracker初始化的时候,会调用initializeNextSession方法来生成一个初始化的sessionID,之后在Zookeeper的正常运行过程中,会在该sessionID的基础上为每个会话进行分配。

Java代码 

 收藏代码

  1. /** 
  2.     * Generates an initial sessionId. High order byte is serverId, next 5 
  3.     * 5 bytes are from timestamp, and low order 2 bytes are 0s. 
  4.     */  
  5.    public static long initializeNextSession(long id) {  
  6.      long nextSid = 0;  
  7.        nextSid = (System.currentTimeMillis() << 24) >>> 8; //这里的版本是3.4.6  
  8.        nextSid =  nextSid | (id <<56);  
  9.        return nextSid;  
  10.    }  

 

上面这个方法就是Zookeeper初始化的算法。可以看出sessionID的生成可以分为以下5个步骤:

  1. 获取当前时间的毫秒表示。我们假设System.currentTimeMillis()取出的值是1380895182327,其64位二进制表示是:0000000000000000000000010100000110000011110001000100110111110111 其中红色部分表示高24位,下划线部分表示低40位。
  2. 左移24位。将步骤1中的数值左移24位,得到如下二进制表示的数值:0100000110000011110001000100110111110111000000000000000000000000
  3. 无符号右移8位。再将步骤2中的数值无符号右移8位,得到如下二进制表示的数值:0000000001000001100000111100010001001101111101110000000000000000
  4. 添加机器标识SID.在initializeNextSession方法中,出现了一个id变量,该变量就是当前Zookeeper服务器的SID值.SID就是当时配置在myid文件中的值,该值通常是一个整数。我们以2为例子。2的64位表示如下:0000000000000000000000000000000000000000000000000000000000000010。高56位都是0,将其左移56位,可以得到如下二进制表示的数值:0000001000000000000000000000000000000000000000000000000000000000
  5. 将步骤3和步骤4得到的64位数值进行“|”操作:0000001001000001100000111100010001001101111101110000000000000000。这样就完成了一个sessioID的初始化。我们就可以得到一个单机唯一的序列号。算法概括为:高8位确定了所在机器,后56位使用当前时间的毫秒表示进行随机。

上面的算法就算完美吗?

答案是否定的,在zookeeper3.5.0以上的版本中对这个方法进行的修改。3.5.0版本的方法如下:

Java代码 

 收藏代码

  1. /** 
  2.     * Generates an initial sessionId. High order byte is serverId, next 5 
  3.     * 5 bytes are from timestamp, and low order 2 bytes are 0s. 
  4.     */  
  5.    public static long initializeNextSession(long id) {  
  6.        long nextSid;  
  7.        nextSid = (<span style="color: #ff0000;">Time.currentElapsedTime()</span> << 24) >>> 8;  
  8.        nextSid =  nextSid | (id <<56);  
  9.        return nextSid;  
  10.    }  

 

currentTimeMillis方法换成了另外一个方法。那么这个方法是什么呢?

Java代码 

 收藏代码

  1. /** 
  2.      * Returns time in milliseconds as does System.currentTimeMillis(), 
  3.      * but uses elapsed time from an arbitrary epoch more like System.nanoTime(). 
  4.      * The difference is that if somebody changes the system clock, 
  5.      * Time.currentElapsedTime will change but nanoTime won't. On the other hand, 
  6.      * all of ZK assumes that time is measured in milliseconds. 
  7.      * @return  The time in milliseconds from some arbitrary point in time. 
  8.      */  
  9.     public static long currentElapsedTime() {  
  10.         return System.nanoTime() / 1000000;  
  11.     }  

 使用了System.nanoTime()方法。原因是如果一些人去主动修改系统的时间,这样可能会出现问题。

 

 

Zookeeper使用了2行代码完成了生成全局唯一值的方法。然而我们直接使用jdk1.5以上自带的UUID不是也能生成全局唯一的值吗?

下面我们看看UUID和Zookeeper自己实现方法的一些比较:

  • 根据UUID类的注释,A UUID represents a 128-bit value.一个UUID代表一个128位的值。然而Zookeeper使用64就产生了一个全局唯一的值。从资源占用上节省了一半。
  • 从代码复杂程度上看,UUID的生成是严格按照国际标准实现的。算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成。代码的复杂程度要比Zookeeper自身实现的高。复杂度高意味着在执行过程中需要消耗的资源就会增多。
  • UUID的生成不需要外界因素的参与。直观的将就是不需要传递任何参数就可以完成。而Zookeeper自身实现的方法需要一个id,这个id就是我们在Zookeeper中配置的myid值。它的生成时需要条件的。

总结:

  • 没有最好只有适合。适合自身的需要并且能够考虑到性能、资源的使用等方面才能设计出好的策略。
  • 底层的运算使用位运算比较理想。很多地方都是这样运用的。毕竟位运算的速度是最快的。

 


微信公众号【黄小斜】大厂程序员,互联网行业新知,终身学习践行者。关注后回复「Java」、「Python」、「C++」、「大数据」、「机器学习」、「算法」、「AI」、「Android」、「前端」、「iOS」、「考研」、「BAT」、「校招」、「笔试」、「面试」、「面经」、「计算机基础」、「LeetCode」 等关键字可以获取对应的免费学习资料。 


                     wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

网友评论

登录后评论
0/500
评论
黄小斜
+ 关注