6 种常见分布式唯一ID生成策略及它们的优缺点对比
大局仅有的 ID 几乎是一切体系都会遇到的刚需。这个 id 在查找, 存储数据, 加快检索速度 等等很多方面都有着重要的意义。有多种战略来获取这个大局仅有的id，针对常见的几种场景，我在这儿进行简略的总结和对比。
简略剖析一下需求
所谓大局仅有的 id 其实往往对应是生成仅有记载标识的事务需求 。
这个 id 常常是数据库的主键，数据库上会树立集合索引（cluster index），即在物理存储上以这个字段排序。这个记载标识上的查询，往往又有分页或许排序的事务需求。所以往往要有一个time字段，而且在time字段上树立一般索引（non-cluster index）。
一般索引存储的是实践记载的指针，其拜访效率会比集合索引慢，假如记载标识在生成时能够基本依照时刻有序，则能够省去这个time字段的索引查询。
这就引出了记载标识生成的两大中心需求：
- 大局仅有
- 趋势有序
常见生成战略的优缺陷对比
办法一: 用数据库的 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 也能够进行水平扩展，以处理上述缺陷，但会引发一致性问题。
办法三：uuid / guid
不管是经过数据库，仍是经过服务来生成ID，事务方Application都需求进行一次长途调用，比较耗时。uuid是一种常见的本地生成ID的办法。
UUID uuid = UUID.randomUUID();
长处：
- 本地生成ID，不需求进行长途调用，时延低
- 扩展性好，基本能够以为没有功能上限
缺陷：
- 无法确保趋势递加
- uuid过长，往往用字符串表明，作为主键树立索引查询效率低，常见优化计划为“转化为两个uint64整数存储”或许“减半存储”（减半后不能确保仅有性）
办法四：取当时毫秒数
uuid是一个本地算法，生成功能高，但无法确保趋势递加，且作为字符串ID检索效率低，有没有一种能确保递加的本地算法呢？- 取当时毫秒数是一种常见计划。
长处：
- 本地生成ID，不需求进行长途调用，时延低
- 生成的ID趋势递加
- 生成的ID是整数，树立索引后查询效率高
缺陷：
- 假如并发量超越1000，会生成重复的ID
- 这个缺陷要了命了，不能确保ID的仅有性。当然，运用微秒能够下降冲突概率，但每秒最多只能生成1000000个ID，再多的话就一定会冲突了，所以运用微秒并不从根本上处理问题。
办法五：运用 Redis 来生成 id
当运用数据库来生成ID功能不行要求的时候，咱们能够尝试运用Redis来生成ID。这主要依赖于Redis是单线程的，所以也能够用生成大局仅有的ID。能够用Redis的原子操作 INCR 和 INCRBY 来完成。
长处：
- 依赖于数据库，灵活方便，且功能优于数据库。
- 数字ID天然排序，对分页或许需求排序的结果很有协助。
缺陷：
- 假如体系中没有Redis，还需求引进新的组件，增加体系复杂度。
- 需求编码和配置的作业量比较大。
办法六：Twitter 开源的 Snowflake 算法
snowflake 是 twitter 开源的分布式ID生成算法，其中心思想为，一个long型的ID：
- 41 bit 作为毫秒数 - 41位的长度能够运用69年
- 10 bit 作为机器编号 （5个bit是数据中心，5个bit的机器ID） - 10位的长度最多支撑布置1024个节点
- 12 bit 作为毫秒内序列号 - 12位的计数顺序号支撑每个节点每毫秒发生4096个ID序号
算法单机每秒内理论上最多能够生成1000*(2^12)，也就是400W的ID，完全能满足事务的需求。
该算法 java 版本的完成代码如下：
package com; public class SnowflakeIdGenerator { //================================================Algorithm's Parameter============================================= // 体系开端时刻截 (UTC 2017-06-28 00:00:00) private final long startTime = 1498608000000L; // 机器id所占的位数 private final long workerIdBits = 5L; // 数据标识id所占的位数 private final long dataCenterIdBits = 5L; // 支撑的最大机器id(十进制)，结果是31 (这个移位算法能够很快的计算出几位二进制数所能表明的最大十进制数) // -1L 左移 5位 (worker id 所占位数) 即 5位二进制所能取得的最大十进制数 - 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 (即末 sequence 所占用的位数) private final long workerIdMoveBits = sequenceBits; // 数据标识id 左移位数 - 17(12+5) private final long dataCenterIdMoveBits = sequenceBits + workerIdBits; // 时刻截向 左移位数 - 22(5+5+12) private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits; // 生成序列的掩码(12位所对应的最大整数值)，这儿为4095 (0b111111111111=0xfff=4095) private final long sequenceMask = -1L ^ (-1L << sequenceBits); //=================================================Works's Parameter================================================ /** * 作业机器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 SnowflakeIdGenerator(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 的办法 public synchronized long nextId() { long timestamp = currentTime(); //假如当时时刻小于上一次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; //毫秒内序列溢出 即 序列 > 4095 if (sequence == 0) { //阻塞到下一个毫秒,取得新的时刻戳 timestamp = blockTillNextMillis(lastTimestamp); } } //时刻戳改动，毫秒内序列重置 else { sequence = 0L; } //前次生成ID的时刻截 lastTimestamp = timestamp; //移位并经过或运算拼到一起组成64位的ID return ((timestamp - startTime) << timestampMoveBits) // | (dataCenterId << dataCenterIdMoveBits) // | (workerId << workerIdMoveBits) // | sequence; } // 阻塞到下一个毫秒 即 直到取得新的时刻戳 protected long blockTillNextMillis(long lastTimestamp) { long timestamp = currentTime(); while (timestamp <= lastTimestamp) { timestamp = currentTime(); } return timestamp; } // 取得以毫秒为单位的当时时刻 protected long currentTime() { return System.currentTimeMillis(); } //====================================================Test Case===================================================== public static void main(String[] args) { SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0); for (int i = 0; i < 100; i++) { long id = idWorker.nextId(); //System.out.println(Long.toBinaryString(id)); System.out.println(id); } } }