需求

几乎所有的业务系统，都有生成一个唯一记录标识的需求。

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

  1. 全局唯一

  2. 趋势有序

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

UUID

策略

UUID/GUID 生成的唯一标识。

优缺点

  • 优点

本地调用，全局唯一。

  • 缺点

无法保证趋势有序，太长。

不利于阅读。

优化

  • 太长

UUID 可以移除掉所有 -，变为 32 位。

  • 可读性
/// <summary>
/// 根据GUID获取唯一数字序列
/// </summary>
public static long GuidToInt64()
{
    byte[] bytes = Guid.NewGuid().ToByteArray();
    return BitConverter.ToInt64(bytes, 0);
}
  • 无序性

为了解决UUID无序的问题，NHibernate在其主键生成方式中提供了Comb算法（combined guid/timestamp）。

保留GUID的10个字节，用另6个字节表示GUID生成的时间（DateTime）。

/// <summary> 
/// Generate a new <see cref="Guid"/> using the comb algorithm. 
/// </summary> 
private Guid GenerateComb()
{
    byte[] guidArray = Guid.NewGuid().ToByteArray();
 
    DateTime baseDate = new DateTime(1900, 1, 1);
    DateTime now = DateTime.Now;
 
    // Get the days and milliseconds which will be used to build    
    //the byte string    
    TimeSpan days = new TimeSpan(now.Ticks - baseDate.Ticks);
    TimeSpan msecs = now.TimeOfDay;
 
    // Convert to a byte array        
    // Note that SQL Server is accurate to 1/300th of a    
    // millisecond so we divide by 3.333333    
    byte[] daysArray = BitConverter.GetBytes(days.Days);
    byte[] msecsArray = BitConverter.GetBytes((long)
      (msecs.TotalMilliseconds / 3.333333));
 
    // Reverse the bytes to match SQL Servers ordering    
    Array.Reverse(daysArray);
    Array.Reverse(msecsArray);
 
    // Copy the bytes into the guid    
    Array.Copy(daysArray, daysArray.Length - 2, guidArray,
      guidArray.Length - 6, 2);
    Array.Copy(msecsArray, msecsArray.Length - 4, guidArray,
      guidArray.Length - 4, 4);
 
    return new Guid(guidArray);
}

当前时间

策略

取当前毫秒数 yyyyMMddHHmmssSSS 17 位

优缺点

  • 优点

本地调用，趋势有序。

  • 缺点

无法保证唯一性。

优化

17 位 + 15 位随机数字。基本保证不会冲突。

时间可以精确到 java.nanoTime() 之类的，可以很精确+随机数。只是不太利于阅读。

数据库

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，但毕竟还是有性能上限，无法进行水平扩展

备用服务

单点服务的常用高可用优化方案是“备用服务”，也叫“影子服务”。

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

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

redis

使用时间戳 + Redis 的形式。

比如一天为周期，或者一个小时为周期。

实现较为简单，基本可以满足常见的业务需求。

优点

实现简单

性能较好

缺点

依赖于 redis 服务。

snowflake

官方源码

思想

使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是 0。

snowflak-id

实现

TODO:

时间回拨问题

由于存在时间回拨问题，但是他又是那么快和简单，我们思考下是否可以解决呢？

美团解决时钟问题

Leaf——美团点评分布式ID生成系统 非常优秀，但是并没有对应的解决方案。

解决时钟问题

时间回拨的原因

第一：人物操作，在真实环境一般不会有那个傻逼干这种事情，所以基本可以排除。

第二：由于有些业务等需要，机器需要同步时间服务器（在这个过程中可能会存在时间回拨，查了下我们服务器一般在10ms以内（2小时同步一次））。

解决方法

由于是分布在各各机器自己上面，如果要几台集中的机器（并且不做时间同步），那么就基本上就不存在回拨可能性了（曲线救国也是救国，哈哈），但是也的确带来了新问题，各各结点需要访问集中机器，要保证性能，百度的 uid-generator 产生就是基于这种情况做的（每次取一批回来，很好的思想，性能也非常不错）。

时间问题回拨的解决方法：

当回拨时间小于15ms，就等时间追上来之后继续生成。

当时间大于15ms时间我们通过更换 workid 来产生之前都没有产生过的来解决回拨问题。

调整 workid 段位

Snowflake 算法稍微调整下位段：

  • sign(1bit)

固定1bit符号标识，即生成的畅途分布式唯一id为正数。

  • delta seconds (38 bits)

当前时间，相对于时间基点”2017-12-21”的增量值，单位：毫秒，最多可支持约8.716年

  • worker id (15 bits)

机器id，最多可支持约3.28万个节点。

  • sequence (10 bits)

每秒下的并发序列，10 bits，这个算法单机每秒内理论上最多可以生成1000*(2^10)，也就是100W的ID，完全能满足业务的需求。

关键

下面到了关键了：

现在我把3万多个workid放到一个队列中（基于redis），由于需要一个集中的地方来管理workId，每当节点启动时候，（先在本地某个地方看看是否有 借鉴弱依赖zk 本地先保存），如果有那么值就作为workid，如果不存在，就在队列中取一个当workid来使用（队列取走了就没了 ），当发现时间回拨太多的时候，我们就再去队列取一个来当新的workid使用，把刚刚那个使用回拨的情况的workid存到队列里面（队列我们每次都是从头取，从尾部进行插入，这样避免刚刚a机器使用又被b机器获取的可能性）。

思考

如果引入了redis为啥不用redis下发id？（查看分布式系统唯一ID生成方案汇总会获得答案，我们这里仅仅是用来一致性队列的，能做一致性队列的基本都可以)。

引入redis就意味着引入其他第三方的架构，做基础框架最好是不要引用（越简单越好，目前还在学习提高）。

redis一致性怎么保证？（redis挂了怎么办，怎么同步，的确值得商榷。可能会引入会引入很多新的小问题）。

MongoDB ObjectId

MongoDB ObjectId 和snowflake算法类似。

它设计成轻量型的，不同的机器都能用全局唯一的同种方法方便地生成它。MongoDB 从一开始就设计用来作为分布式数据库，处理多个节点是一个核心要求。

使其在分片环境中要容易生成得多。

思路

前 4 个字节是从标准纪元开始的时间戳，单位为秒。时间戳，与随后的5 个字节组合起来，提供了秒级别的唯一性。

由于时间戳在前，这意味着ObjectId 大致会按照插入的顺序排列。这对于某些方面很有用，如将其作为索引提高效率。

这 4 个字节也隐含了文档创建的时间。绝大多数客户端类库都会公开一个方法从 ObjectId 获取这个信息。

接下来的 3 字节是所在主机的唯一标识符。通常是机器主机名的散列值。这样就可以确保不同主机生成不同的 ObjectId，不产生冲突。

为 了确保在同一台机器上并发的多个进程产生的ObjectId 是唯一的，接下来的两字节来自产生ObjectId 的进程标识符（PID）。

前 9 字节保证了同一秒钟不同机器不同进程产生的 ObjectId 是唯一的。

后 3 字节就是一个自动增加的计数器，确保相同进程同一秒产生的 ObjectId 也是不一样的。

同一秒钟最多允许每个进程拥有 2563（16 777 216）个不同的ObjectId。

Zookeeper

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

很少会使用 Zookeeper 来生成唯一ID。主要是由于需要依赖zookeeper，并且是多步调用API，如果在竞争较大的情况下，需要考虑使用分布式锁。

因此，性能在高并发的分布式环境下，也不甚理想。

拓展阅读

二进制

java 二进制学习

参考资料

Leaf——美团点评分布式ID生成系统

分布式系统唯一ID生成方案汇总

浅谈CAS在分布式ID生成方案上的应用

CAS下ABA问题及优化方案

分布式ID生成器

  • snowflake

https://juejin.im/post/5a7f9176f265da4e721c73a8

原理讲解

  • snowflake 源码实现

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

Twitter的雪花算法SnowFlake，使用Java语言实现

UidGenerator：百度出品的基于 Snowflake 算法的唯一 ID 生成器（Java）

UC 实现版本

  • uuid

guid-uuid-timebased