面试总被问分布式ID怎么办？ 甩给他

给他"/>

面试总被问分布式ID怎么办？ 甩给他

个人网站：

ID是数据的唯一标识，传统的做法是利用UUID和数据库的自增ID，在互联网企业中，大部分公司使用的都是MySQL，并且因为需要事务支持，所以通常会使用Innodb存储引擎，UUID太长以及无序，所以并不适合在Innodb中来作为主键，自增ID比较合适，但是随着公司的业务发展，数据量将越来越大，需要对数据进行分表，而分表后，每个表中的数据都会按自己的节奏进行自增，很有可能出现ID冲突。这时就需要一个单独的机制来负责生成唯一ID，生成出来的ID也可以叫做分布式ID，或全局ID。

数据库主键为什么要用递增的序列？

顺序的ID占用的空间比随机ID占用的空间小。
原因是数据库主键和索引索引使用B+树的数据结构进行存储，顺序ID数据存储在最后一个节点的最后的位置，前面的节点数据都是满的。随机ID存储时可能会出现节点分裂，导致节点多了，但是每个节点的数据量少了，存储到文件系统中时，无论节点中数据是不是满的都会占用一页的空间。所以所导致空间占用较大。

UUID为什么不适合做主键？

UUID值由本机Mac地址和时间戳等因素决定，UUID出现重复概率极几乎可以忽略不计。

如果需求是只保证唯一性，那么UUID也是可以使用的，但是按照上面的分布式id的要求， UUID其实是不能做成分布式id的，原因如下：

1. 首先分布式id一般都会作为主键，但是mysql官方推荐主键要尽量越短越好，UUID每一个都很长，所以不是很推荐
2. 既然分布式id是主键，然后主键是包含索引的，然后mysql的索引是通过b+树来实现的，每一次新的UUID数据的插入，为了查询的优化，都会对索引底层的b+树进行修改，因为UUID数据是无序的，所以每一次UUID数据的插入都会对主键地城的b+树进行很大的修改，这一点很不好
3. 信息不安全：基于MAC地址生成UUID的算法可能会造成MAC地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。

Java实现UUID

package com.one.util;
import java.util.UUID;
public class Test {public static void main(String[] args) {String uuid= UUID.randomUUID().toString().replace("-", "").toLowerCase();System.out.println("UUID的值是:"+uuid);}
}

作为主键的要求

1. 顺序
2. 唯一
3. 能短则短，减少空间占用

自增的ID可以满足大部分业务场景，但是在一些特殊场景中并不合适，只举部分例子

1. 分布式系统中
2. 分库分表的数据库设计
3. 存在一些安全问题，对于一些敏感信息比如数据量容易被推测。

常见ID解决方案的对比

流行的分布式ID解决方案

雪花算法（snowflake）

雪花算法是由符号位+时间戳+工作机器id+序列号组成

解释

1. 符号位为0，0表示正数，ID为正数。

2. 时间戳位不用多说，用来存放时间戳，单位是ms。

3. 工作机器id位用来存放机器的id，通常分为5个区域位+5个服务器标识位。

Twitter 的 Snowflake算法 Java实现

public class SnowflakeIdWorker {private static SnowflakeIdWorker instance = new SnowflakeIdWorker(0,0);/*** 开始时间截 (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;/*** 构造函数* @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;}/*** 获得下一个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位的IDreturn ((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();}public static SnowflakeIdWorker getInstance(){return instance;}public static void main(String[] args) throws InterruptedException {SnowflakeIdWorker idWorker = SnowflakeIdWorker.getInstance();for (int i = 0; i < 10; i++) {long id = idWorker.nextId();Thread.sleep(1);System.out.println(id);}}
}

号段模式

号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。表结构如下：

CREATE TABLE id_generator (id int(10) NOT NULL,max_id bigint(20) NOT NULL COMMENT '当前最大id',step int(20) NOT NULL COMMENT '号段的布长',biz_type	int(20) NOT NULL COMMENT '业务类型',version int(20) NOT NULL COMMENT '版本号',PRIMARY KEY (`id`)
) 

• biz_type ：代表不同业务类型

• max_id ：当前最大的可用id

• step ：代表号段的长度

• version ：是一个乐观锁，每次都更新version，保证并发时数据的正确性

等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

由于多业务端可能同时操作，所以采用版本号version乐观锁方式更新，这种分布式ID生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。

其他解决方案

1. 滴滴出品（TinyID）Github地址：
2. 百度 （Uidgenerator）GitHub地址：
3. 美团（Leaf）github地址：