vlambda博客
学习文章列表

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

今天一定要努力工作

绝对不会浪费时间

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他
饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他
饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他
饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他
饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他


在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识。比如我们所熟知的美团、饿了么，携程、飞猪等app，它们的支付订单、餐饮、酒店、代金券等产品系统中，随着数据日渐增长，就会产生分表、分库的需求，这样也就需要一个唯一的ID来标识一条数据或消息，数据库的自增ID显然不能满足需求。


分布式系统唯一ID的特点

  1. 全局唯一性：不能出现重复的ID号

  2. 趋势递增：在MySQL InnoDB引擎中使用的是聚集索引，由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能

  3. 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。

  4. 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

上述123对应三类不同的场景，3和4需求还是互斥的，无法使用同一个方案满足。同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高。


由此一个ID生成系统应该做到如下几点：

  1. 平均延迟和TP999延迟都要尽可能低；

  2. 可用性5个9；

  3. 高QPS。


常见解决方案有UUID，Snowflake，Flicker，Redis，Zookeeper，Leaf等。



1.UUID

UUID 是 通用唯一识别码（Universally Unique Identifier）的缩写，是一种软件建构的标准。其目的，是让分布式系统中的所有元素，都能有唯一的辨识信息，而不需要通过中央控制端来做辨识信息的指定。如此一来，每个人都可以创建不与其它人冲突的UUID。在这样的情况下，就不需考虑数据库创建时的名称重复问题。常见的为一个32位16进制字符串（16字节的128位数据，通常以32位长度的字符串表示）


组成：

  1. 当前日期和时间:UUID的第一个部分与时间有关，如果你在生成一个UUID之后，过几秒又生成一个UUID，则第一个部分不同，其余相同;

  2. 时钟序列;

  4. 在 hibernate（Java orm框架）中， 采用 IP-JVM启动时间-当前时间右移32位-当前时间-内部计数（8-8-4-8-4）来组成UUID


优点：

  1. 性能非常高：本地生成，没有网络消耗；

  2. 不需要提前商定，各自为政，但绝对不会冲突；

  3. 不需要考虑性能瓶颈；

  4. 可以做到全球唯一，在遇到数据迁移、系统数据合并或者数据库变更时，可以从容应对。


缺点：

  1. 不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用；

  3. 无法保证趋势增长；

  4. ID作为主键时在特定的环境会存在一些问题，比如做DB主键的场景下，UUID就非常不适用；

我们所熟知的MySQL官方有明确的建议主键要尽量越短越好,并且如果作为数据库主键，在InnoDB引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。


适用场景：

不需要考虑空间占用，不需要生成有递增趋势的ID，且不在MySQL中存储，或者不需要用UUID做排序的情况。


2.Snowflake

这种方案大致来说是一种以划分命名空间（UUID也算，由于比较常见，所以单独分析）来生成ID的一种算法。是Twitter开源的分布式ID生成算法，结果是一个long型的ID。这种方案把64-bit分别划分成多段，分开来标示机器、时间等，比如在Snowflake中的 64-bit 分别表示如下图（图片来自网络）所示：

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他


组成：

  1. 首位符号位：因为ID一般为正数，该值为0；

  2. 41位时间戳（毫秒级）：时间戳并不是当前时间戳，而是存储时间戳的差值（当前时间戳-起始时间戳（起始时间戳需要程序指定），理论可以适用(1<<41)/(1000x60x60x24x365)，69年；

  3. 10位数据机器位（说白了就是逻辑分片ID，具体实现和机器本身无关系）：包括5位数据标识位和5位机器标识位（比如5位机房ID，5位机器ID），理论最多可以部署节点位1<<10=1024；

  4. 12位毫秒内的序列：同一节点，同一时刻（同一毫秒内）最多生成ID数1<<12=4096。


优点：

  1. 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的；

  2. 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的；

  3. 可以根据自身业务特性分配bit位，非常灵活；


缺点：

1.强依赖机器时钟。分布式环境，每台机器上的时钟不可能完全同步，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。


本来想看看推特怎么写的，结果github上面写着项目不维护了，这是忧伤

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

不过它留了一个scala的项目压缩包，可以看看。

下面是模拟这个结构写的一份Snowflake的Java版本代码，仅供参考：

public class SnowflakeIdWorker {    // ==============================Fields===========================================
   /** 开始时间截 (2015-01-01) */
   private final long twepoch = 1420041600000L;    /** 机器id所占的位数 */
   private final long workerIdBits = 5L;    /** 数据标识id所占的位数 */
   private final long datacenterIdBits = 5L;    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
   private final long maxWorkerId = -1L ^ (-1L << workerIdBits);    /** 支持的最大数据标识id，结果是31 */
   private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);    /** 序列在id中占的位数 */
   private final long sequenceBits = 12L;    /** 机器ID向左移12位 */
   private final long workerIdShift = sequenceBits;    /** 数据标识id向左移17位(12+5) */
   private final long datacenterIdShift = sequenceBits + workerIdBits;    /** 时间截向左移22位(5+5+12) */
   private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;    /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
   private final long sequenceMask = -1L ^ (-1L << sequenceBits);    /** 工作机器ID(0~31) */
   private long workerId;    /** 数据中心ID(0~31) */
   private long datacenterId;    /** 毫秒内序列(0~4095) */
   private long sequence = 0L;    /** 上次生成ID的时间截 */
   private long lastTimestamp = -1L;    //==============================Constructors=====================================
   /**
    * 构造函数
    * @param workerId 工作ID (0~31)
    * @param datacenterId 数据中心ID (0~31)     */
   public SnowflakeIdWorker(long workerId, long datacenterId) {        if (workerId > maxWorkerId || workerId < 0) {            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
       }        if (datacenterId > maxDatacenterId || datacenterId < 0) {            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
       }        this.workerId = workerId;        this.datacenterId = datacenterId;
   }    // ==============================Methods==========================================
   /**
    * 获得下一个ID (该方法是线程安全的)
    * @return SnowflakeId     */
   public synchronized long nextId() {        long timestamp = timeGen();        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
       if (timestamp < lastTimestamp) {            throw new RuntimeException(
                   String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
       }        //如果是同一时间生成的，则进行毫秒内序列
       if (lastTimestamp == timestamp) {
           sequence = (sequence + 1) & sequenceMask;            //毫秒内序列溢出
           if (sequence == 0) {                //阻塞到下一个毫秒,获得新的时间戳
               timestamp = tilNextMillis(lastTimestamp);
           }
       }        //时间戳改变，毫秒内序列重置
       else {
           sequence = 0L;
       }        //上次生成ID的时间截
       lastTimestamp = timestamp;        //移位并通过或运算拼到一起组成64位的ID
       return ((timestamp - twepoch) << timestampLeftShift) //                | (datacenterId << datacenterIdShift) //                | (workerId << workerIdShift) //                | sequence;
   }    /**
    * 阻塞到下一个毫秒，直到获得新的时间戳
    * @param lastTimestamp 上次生成ID的时间截
    * @return 当前时间戳     */
   protected long tilNextMillis(long lastTimestamp) {        long timestamp = timeGen();        while (timestamp <= lastTimestamp) {
           timestamp = timeGen();
       }        return timestamp;
   }    /**
    * 返回以毫秒为单位的当前时间
    * @return 当前时间(毫秒)     */
   protected long timeGen() {        return System.currentTimeMillis();
   }    //==============================Test=============================================
   /** 测试 */
   public static void main(String[] args) {
       SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);        for (int i = 0; i < 1000; i++) {            long id = idWorker.nextId();
           System.out.println(Long.toBinaryString(id));
           System.out.println(id);
       }
   }
}


应用场景：

要求高性能，可以不连续，数据类型为long型。


思考：如何解决时间回拨的问题？


时间回拨产生的原因：分布式系统中，各机器同步服务器时间，一般每2小时同步一次，在 10ms 以内完成。


百度倒是做了一个简单的处理：

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

UidGenerator是百度开源的Java语言实现，基于 Snowflake 算法的唯一ID生成器。百度对这些组成部分稍微调整了一下：

传统的雪花算法实现都是通过 System.currentTimeMillis()来获取时间并与上一次时间进行比较，这样的实现严重依赖服务器的时间。而 UidGenerator 的时间类型是AtomicLong，且通过 incrementAndGet() 方法获取下一次的时间，从而脱离了对服务器时间的依赖，也就不会有时钟回拨的问题（这种做法也有一个小问题，即分布式ID中的时间信息可能并不是这个ID真正产生的时间点，例如：获取的某分布式ID的值为3200169789968523265，它的反解析结果为{"timestamp":"2019-05-02 23:26:39","workerId":"21","sequence":"1"}，但是这个ID可能并不是在"2019-05-02 23:26:39"这个时间产生的）。


3.MongoDB

官方文档ObjectID可以算作是和snowflake类似方法，通过“时间+机器码+pid+inc”共12个字节，通过4+3+2+3的方式最终标识成一个24长度的十六进制字符。


4.数据库生成

主要思路是涉及单独的库表，利用数据库的自增ID+replace_into，来生成全局ID。


replace into 跟 insert 功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经有此行数据（根据主键或唯一索引判断）则先删除，再插入。否则直接插入新数据。


扩展：为解决单点问题，启用多台服务器，如MySQL，利用给字段设置auto_increment_increment和auto_increment_offset来保证ID自增（如通过设置起始值与步长，生成奇偶数ID）


优点：

  1. 实现简单，充分利用了数据库系统的功能实现，成本小，有DBA专业维护；

  2. ID号单调自增，可以实现一些对ID有特殊要求的业务；


缺点：

  1. 强依赖DB，当DB异常时，整个系统不可用，属于致命问题（配置主从复制可以尽可能地增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能导致重复发号）；

  2. 水平扩展困难（定义好了起始值，步长和机器台数之后，如果要添加机器就比较麻烦；

  3. ID发号性能瓶颈限制在单台MySQL的读写性能；


适用场景：

数据量不大，并发量不大。


优化：

对于MySQL性能问题，可用如下方案解决：在分布式系统中我们可以多部署几台机器，每台机器设置不同的初始值，且步长和机器数相等。


比如有两台机器。设置步长step为2，TicketServer1 的初始值为1（1，3，5，7，9，11…）、TicketServer2 的初始值为2（2，4，6，8，10…）。这是Flickr团队在2010年撰文介绍的一种主键生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。如下所示，为了实现上述方案分别设置两台机器对应的参数，TicketServer1 从1开始发号， TicketServer2 从2开始发号，两台机器每次发号之后都递增2。


TicketServer1:

auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2


假设我们要部署N台机器，步长需设置为N，每台的初始值依次为0,1,2…N-1那么整个架构就变成了如下图所示：

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

这种架构貌似能够满足性能的需求，但有以下几个缺点：

  1. 系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是1,2,3,4,5（步长是1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如14（假设在扩容时间之内第一台不可能发到14），同时设置步长为2，那么这台机器下发的号码都是14以后的偶数。然后摘掉第一台，把ID值保留为奇数，比如7，然后修改第一台的步长为2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有100台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现。

  2. ID没有了单调递增的特性，只能趋势递增，这个缺点对于一般业务需求不是很重要，可以容忍

  3. 数据库压力还是很大，每次获取ID都得读写一次数据库，只能靠堆机器来提高性能。



5.Redis

由于 Redis 的所有命令是单线程的，所以可以利用Redis的原子操作 INCR 和 INCRBY ，来生成全局唯一的ID。

比较适合使用 Redis 来生成每天从0开始的流水号。比如订单号=日期+当日自增长号。可以每天在 Redis 中生成一个Key，使用 INCR 进行累加。


扩展：

可以通过集群来提升吞吐量（可以通过为不同Redis节点设置不同的初始值并统一步长，从而利用Redis生成唯一且趋势递增的ID）（其实这个方法和Flicker一致，只是利用到了Redis的一些特性，如原子操作，内存数据库读写快等）（Incrby:将key中储存的数字加上指定的增量值。这是一个“INCR AND GET”的原子操作，业务方可以定义一个自己的key值，通过INCR命令来获取对应的ID）


优点：

  1. 不依赖于数据库，灵活方便，且性能优于数据库；

  2. 数字ID天然排序，对分页或者需要排序的结果很有帮助；


缺点：

  1. 扩展性低，Redis集群需要设置号初始值与步长（与Flicker方案一样）；

  2. Redis宕机可能生成重复的ID；如果系统中没有Redis，还需要引入新的组件，增加系统复杂度；

  3. 需要编码和配置的工作量比较大；


适用场景：

Redis集群高可用，并发量高。


6.zookeeper生成唯一ID

通过其znode数据版本来生成序列号，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的序列号。


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


7.Leaf-segment数据库方案

拓展自第4种方法，因为原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用 proxy server 批量获取，每次获取一个 segment ( step 决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。 各个业务不同的发号需求用 biz_tag 字段来区分，每个 biz-tag 的 ID 获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对 biz_tag分库分表就行。数据库表设计如下

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

biz_tag 用来区分业务，max_id 表示该 biz_tag 目前所被分配的ID号段的最大值，step 表示每次分配的号段长度。

原来获取ID每次都需要写数据库，现在只需要把 step 设置得足够大，比如1000。那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从1减小到了1/step，大致架构如下图所示：

饿了么面试官问我如何在分布式系统中创建唯一ID，我这么说怼翻他

test_tag 在第一台 Leaf 机器上是1~1000的号段，当这个号段用完时，会去加载另一个长度为step=1000的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是3001~4000。同时数据库对应的 biz_tag 这条数据的 max_id 会从3000被更新成4000，更新号段的SQL语句如下：

Begin

UPDATE table SET max_id=max_id+step WHERE biz_tag=xxxSELECT tag, max_id, step FROM table WHERE biz_tag=xxx

Commit


优点：

  1. Leaf 服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。

  2. ID号码是趋势递增的8 byte 的64位数字，满足上述数据库存储的主键要求。

  3. 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内 Leaf 仍能正常对外提供服务

  4. 可以自定义 max_id 的大小，非常方便业务从原有的ID方式上迁移过来。


缺点：

  1. ID号码不够随机，能够泄露发号数量的信息，不太安全

  2. TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺

  3. DB宕机会造成整个系统不可用。


8.双buffer优化

对于第二个缺点，Leaf-segment 做了一些优化，简单的说就是：

Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的 ID 下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取 DB 的时候网络发生抖动，或者 DB 发生慢查询就会导致整个系统的响应时间变慢。

为此，我们希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中。而不需要等到号段用尽的时候才去更新号段。这样做就可以很大程度上的降低系统的TP999指标。详细实现如下图所示：


采用 双buffer 的方式，Leaf 服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前 segment 接着下发，循环往复。

每个 biz-tag 都有消费速度监控，通常推荐 segment 长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf 仍能持续发号10-20分钟不受影响。

每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。



理论总结：

其实除了上述方案外，还有ins等的方案，但总的来看，方案主要分为两种：第一有中心（如数据库，包括 MySQL，Redis 等），其中可以会利用事先的预约来实现集群（起始步长）。第二种就是无中心，通过生成足够散落的数据，来确保无冲突（如UUID等）。站在这两个方向上，来看上述方案的利弊就方便多了。


中心化方案：

优点：

  1. 数据长度相对小一些；

  2. 数据可以实现自增趋势等

缺点：

  1. 并发瓶颈处理;

  2. 集群需要实现约定；

  3. 横向扩展困难;


非中心化方案：

优点：

  1. 实现简单（因为不需要与其他节点存在这方面的约定，耦合）

  2. 不会出现中心节点带来的性能瓶颈

  3. 扩展性较高（扩展的局限往往集中于数据的离散问题）

缺点：

  1. 数据长度较长（毕竟就是通过这一特性来实现无冲突的）

  2. 无法实现数据的自增长（毕竟是随机的）

  3. 依赖数据生成方案的优劣（数据生成方案的优劣会全盘接收，但可以推陈出新）


体悟：

技术是无穷无尽的，我们不仅需要看到其中体现的思想与原则，在学习新技术或方案时，需要明确其中一些特性，优缺点的来源，从而进行有效的总结归纳。

应用角度来说，完全应该根据当前业务场景来选择，毕竟业务场景在当前是确定的。如果业务变动较大（比如发展初期，业务增长很快），那就需要考虑扩展性，便于日后进行该模块的更新与技术方案的替换实现。


本文参考：

https://tech.meituan.com/2017/04/21/mt-leaf.html

https://www.cnblogs.com/Tiancheng-Duan/p/10962704.html

https://youzhixueyuan.com/how-to-generate-distributed-unique-id.html

https://www.cnblogs.com/relucent/p/4955340.html



长按关注

升职加薪，不要走丢~

推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
看了 B 站上的这些Java视频，我飘了！ 看了 B 站上的这些Java视频，我飘了！

相关文章