用户您好!请先登录!

分布式系统中的唯一id生成策略及实现

分布式系统中的唯一id生成策略及实现

系统唯一ID是我们在设计一个系统的时候常常会遇见的问题,也常常为这个问题而纠结。生成ID的方法有很多,适应不同的场景、需求以及性能要求。所以有些比较复杂的系统会有多个ID生成的策略。

简单分析一下需求

所谓全局唯一的 id 其实往往对应是生成唯一记录标识的业务需求

这个 id 常常是数据库的主键,数据库上会建立聚集索引(cluster index),即在物理存储上以这个字段排序。这个记录标识上的查询,往往又有分页或者排序的业务需求。所以往往要有一个time字段,并且在time字段上建立普通索引(non-cluster index)。普通索引存储的是实际记录的指针,其访问效率会比聚集索引慢,如果记录标识在生成时能够基本按照时间有序,则可以省去这个time字段的索引查询。

这就引出了记录标识生成的两大核心需求:

  • 全局唯一
  • 趋势有序

平常应用中方式很多:

  1. 数据库自增长序列或字段
  2. UUID
  3. uuid的变种
  4. redis生成
  5. Twitter的snowflake算法

1. 数据库自增长序列或字段

方法一: 用数据库的 auto_increment 来生成

优点:

  • 此方法使用数据库原有的功能,所以相对简单
  • 能够保证唯一性
  • 能够保证递增性
  • id 之间的步长是固定且可自定义的

缺点:

  • 可用性难以保证:数据库常见架构是 一主多从 + 读写分离,生成自增ID是写请求 主库挂了就玩不转了
  • 扩展性差,性能有上限:因为写入是单点,数据库主库的写性能决定ID的生成性能上限,并且 难以扩展
改进方案:
  • 冗余主库,避免写入单点
  • 数据水平切分,保证各主库生成的ID不重复方法一改进方案的结构图

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

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

  • 丧失了ID生成的“绝对递增性”:先访问DB 01生成0,3,再访问DB 02生成1,可能导致在非常短的时间内,ID生成不是绝对递增的(这个问题不大,目标是趋势递增,不是绝对递增
  • 数据库的写压力依然很大,每次生成ID都要访问数据库

为了解决这些问题,引出了以下方法:

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

分布式系统之所以难,很重要的原因之一是“没有一个全局时钟,难以保证绝对的时序”,要想保证绝对的时序,还是只能使用单点服务,用本地时钟保证“绝对时序”。
数据库写压力大,是因为每次生成ID都访问了数据库,可以使用批量的方式降低数据库写压力
方法二的结构图

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

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

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

优点:

  • 保证了ID生成的绝对递增有序
  • 大大的降低了数据库的压力,ID生成可以做到每秒生成几万几十万个

缺点:

  • 服务仍然是单点
  • 如果服务挂了,服务重启起来之后,继续生成ID可能会不连续,中间出现空洞(服务内存是保存着0,1,2,3,4,数据库中max-id是4,分配到3时,服务重启了,下次会从5开始分配,3和4就成了空洞,不过这个问题也不大)
  • 虽然每秒可以生成几万几十万个ID,但毕竟还是有性能上限,无法进行水平扩展
改进方案

单点服务的常用高可用优化方案是“备用服务”,也叫“影子服务”,所以我们能用以下方法优化上述缺点:
方法二改进方案的结构图

如上图,对外提供的服务是主服务,有一个影子服务时刻处于备用状态,当主服务挂了的时候影子服务顶上。这个切换的过程对调用方是透明的,可以自动完成,常用的技术是 vip+keepalived。另外,id generate service 也可以进行水平扩展,以解决上述缺点,但会引发一致性问题。

2. UUID

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

UUID uuid = UUID.randomUUID();

优点:

  • 本地生成ID,不需要进行远程调用,时延低
  • 扩展性好,基本可以认为没有性能上限

缺点:

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

3. uuid的变种:取当前毫秒数

uuid是一个本地算法,生成性能高,但无法保证趋势递增,且作为字符串ID检索效率低,有没有一种能保证递增的本地算法呢? – 取当前毫秒数是一种常见方案。

优点:

  • 本地生成ID,不需要进行远程调用,时延低
  • 生成的ID趋势递增
  • 生成的ID是整数,建立索引后查询效率高

缺点:

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

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

4.  redis 生成

当使用数据库来生成ID性能不够要求的时候,我们可以尝试使用Redis来生成ID。这主要依赖于Redis是单线程的,所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR 和 INCRBY 来实现。

优点:

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

缺点:

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

5. Twitter的snowflake算法

snowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号(意味着每个节点在每毫秒可以产生 4096 个 ID),最后还有一个符号位,永远是0。

下面是snowflake算法的实现代码解析:

  1 /**
  2  * Twitter_Snowflake<br>
  3  * SnowFlake的结构如下(每部分用-分开):<br>
  4  * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
  5  * 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
  6  * 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
  7  * 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的
  8  startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
  9  * 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
 10  * 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
 11  * 加起来刚好64位,为一个Long型。<br>
 12  * SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。
 13  */
 14 public class SnowflakeIdWorker {
 15 
 16     // ==============================Fields===========================================
 17     /** 开始时间截 (2015-01-01) */
 18     private final long twepoch = 1420041600000L;
 19 
 20     /** 机器id所占的位数 */
 21     private final long workerIdBits = 5L;
 22 
 23     /** 数据标识id所占的位数 */
 24     private final long datacenterIdBits = 5L;
 25 
 26     /** 支持的最大机器id,结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
 27     private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 28 
 29     /** 支持的最大数据标识id,结果是31 */
 30     private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 31 
 32     /** 序列在id中占的位数 */
 33     private final long sequenceBits = 12L;
 34 
 35     /** 机器ID向左移12位 */
 36     private final long workerIdShift = sequenceBits;
 37 
 38     /** 数据标识id向左移17位(12+5) */
 39     private final long datacenterIdShift = sequenceBits + workerIdBits;
 40 
 41     /** 时间截向左移22位(5+5+12) */
 42     private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 43 
 44     /** 生成序列的掩码,这里为4095 (0b111111111111=0xfff=4095) */
 45     private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 46 
 47     /** 工作机器ID(0~31) */
 48     private long workerId;
 49 
 50     /** 数据中心ID(0~31) */
 51     private long datacenterId;
 52 
 53     /** 毫秒内序列(0~4095) */
 54     private long sequence = 0L;
 55 
 56     /** 上次生成ID的时间截 */
 57     private long lastTimestamp = -1L;
 58 
 59     //==============================Constructors=====================================
 60     /**
 61      * 构造函数
 62      * @param workerId 工作ID (0~31)
 63      * @param datacenterId 数据中心ID (0~31)
 64      */
 65     public SnowflakeIdWorker(long workerId, long datacenterId) {
 66         if (workerId > maxWorkerId || workerId < 0) {
 67             throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
 68         }
 69         if (datacenterId > maxDatacenterId || datacenterId < 0) {
 70             throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
 71         }
 72         this.workerId = workerId;
 73         this.datacenterId = datacenterId;
 74     }
 75 
 76     // ==============================Methods==========================================
 77     /**
 78      * 获得下一个ID (该方法是线程安全的)
 79      * @return SnowflakeId
 80      */
 81     public synchronized long nextId() {
 82         long timestamp = timeGen();
 83 
 84         //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常
 85         if (timestamp < lastTimestamp) {
 86             throw new RuntimeException(
 87                     String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
 88         }
 89 
 90         //如果是同一时间生成的,则进行毫秒内序列
 91         if (lastTimestamp == timestamp) {
 92             sequence = (sequence + 1) & sequenceMask;
 93             //毫秒内序列溢出
 94             if (sequence == 0) {
 95                 //阻塞到下一个毫秒,获得新的时间戳
 96                 timestamp = tilNextMillis(lastTimestamp);
 97             }
 98         }
 99         //时间戳改变,毫秒内序列重置
100         else {
101             sequence = 0L;
102         }
103 
104         //上次生成ID的时间截
105         lastTimestamp = timestamp;
106 
107         //移位并通过或运算拼到一起组成64位的ID
108         return ((timestamp - twepoch) << timestampLeftShift) //
109                 | (datacenterId << datacenterIdShift) //
110                 | (workerId << workerIdShift) //
111                 | sequence;
112     }
113 
114     /**
115      * 阻塞到下一个毫秒,直到获得新的时间戳
116      * @param lastTimestamp 上次生成ID的时间截
117      * @return 当前时间戳
118      */
119     protected long tilNextMillis(long lastTimestamp) {
120         long timestamp = timeGen();
121         while (timestamp <= lastTimestamp) {
122             timestamp = timeGen();
123         }
124         return timestamp;
125     }
126 
127     /**
128      * 返回以毫秒为单位的当前时间
129      * @return 当前时间(毫秒)
130      */
131     protected long timeGen() {
132         return System.currentTimeMillis();
133     }
134 
135     //==============================Test=============================================
136     /** 测试 */
137     public static void main(String[] args) {
138 //        System.out.println(Long.toBinaryString(5));
139         SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1, 1);
140         for (int i = 0; i < 1000; i++) {
141             long id = idWorker.nextId();
142             System.out.println(Long.toBinaryString(id));
143             System.out.println(id);
144         }
145     }
146 }

附带有直接的测试方法,建议动手可以敲一下看一下其中的原理。

行走的code
行走的code

目前为止有一条评论

乞力马扎罗的鱼
乞力马扎罗的鱼 发布于10:06 上午 - 9月 3, 2019

除了上述谈及的几种生成唯一ID的方法之外,还有另外两种方式:

1、利用zookeeper生成唯一ID
zookeeper主要通过其znode数据版本来生成序列号,可以生成32位和64位的数据版本号,客户端可以使用这个版本号来作为唯一的序列号。

很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper,并且是多步调用API,如果在竞争较大的情况下,需要考虑使用分布式锁。因此,性能在高并发的分布式环境下,也不甚理想。

2、MongoDB的ObjectId
MongoDB的ObjectId和snowflake算法类似。它设计成轻量型的,不同的机器都能用全局唯一的同种方法方便地生成它。MongoDB 从一开始就设计用来作为分布式数据库,处理多个节点是一个核心要求。使其在分片环境中要容易生成得多。

MongoDB 中我们经常会接触到一个自动生成的字段:”_id”,类型为ObjectId。

之前我们使用MySQL等关系型数据库时,主键都是设置成自增的。但在分布式环境下,这种方法就不可行了,会产生冲突。为此,mongodb采用了一个称之为ObjectId的类型来做主键。ObjectId是一个12字节的 BSON 类型字符串。按照字节顺序,依次代表:
4字节:UNIX时间戳
3字节:表示运行MongoDB的机器
2字节:表示生成此_id的进程
3字节:由一个随机数开始的计数器生成的值
为了确保在同一台机器上并发的多个进程产生的ObjectId 是唯一的,接下来的两字节来自产生ObjectId 的进程标识符(PID)。

前9 字节保证了同一秒钟不同机器不同进程产生的ObjectId 是唯一的。后3 字节就是一个自动增加的计数器,确保相同进程同一秒产生的ObjectId 也是不一样的。同一秒钟最多允许每个进程拥有2563(16777216)个不同的ObjectId。

要发表评论,您必须先登录

%d 博主赞过: