高并发分布式系统唯一ID生成

了解Paxos算法的同学应该知道，Paxos算法要求Proposal ID全局唯一（且递增）。而事实上，全局唯一ID（且递增）的生成本身是需要一些技术来保证的。生成全局唯一ID的方法其实有很多，但是满足高QPS、高可用以及低延迟这些要求其实并不简单。作为一个并没有机会参与高并发系统的菜鸟，我也只能通过大厂的分享来理解和学习了。开门见山的说，本文的内容就是总结三个大型公司的生产环境的唯一ID生成方案，对于不满足条件（高QPS、高可用以及低延迟）的方法这里就先略过了。此外，可能还有很多其他先进的方法，但是碍于我知识量有限并不知道。

1. Twitter的snowflake算法

snowflake算法其实是一种比较简单而常见的唯一ID生成算法。MongoDB内部的ID生成算法就和snowflake非常接近。snowflake生成64bit的id，程序中用long（JVM类语言）表示，其生成的ID结构如下图:

这里简单解释一下ID的结构，第一位是标识位，因为ID常常用long来表示，这一位是0，表示这是一个正数；接下来是41位的时间戳，时间的单位是毫秒，这个事件一般是相对时间；然后接下来的10bit用来表示不同的机器，5位代表数据中心，5位代表数据中心内的机器的id。接下来的12位是id的序列号，区别同一毫秒中同一机器生成的不同ID。

Twitter开源了snowflake算法，然而貌似现在已经不维护了。这里我截了一段IDWorker的代码，使用Scala的，但如果不懂Scala也不影响阅读。

/** Copyright 2010-2012 Twitter, Inc.*/
package com.twitter.service.snowflake

import com.twitter.ostrich.stats.Stats
import com.twitter.service.snowflake.gen._
import java.util.Random
import com.twitter.logging.Logger

class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L)
extends Snowflake.Iface {
  private[this] def genCounter(agent: String) = {
    Stats.incr("ids_generated")
    Stats.incr("ids_generated_%s".format(agent))
  }
  private[this] val exceptionCounter = Stats.getCounter("exceptions")
  private[this] val log = Logger.get
  private[this] val rand = new Random
  //开始生成ID的时间戳
  val twepoch = 1288834974657L
  //机器id或者是线程id所占用的位数
  private[this] val workerIdBits = 5L
  //数据中心所占用的位数
  private[this] val datacenterIdBits = 5L
  private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits)
  private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)
  private[this] val sequenceBits = 12L

  private[this] val workerIdShift = sequenceBits
  private[this] val datacenterIdShift = sequenceBits + workerIdBits
  private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
  private[this] val sequenceMask = -1L ^ (-1L << sequenceBits)
  //上一次生成ID的时间戳
  private[this] var lastTimestamp = -1L

  // sanity check for workerId
  if (workerId > maxWorkerId || workerId < 0) {
    exceptionCounter.incr(1)
    throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId))
  }

  if (datacenterId > maxDatacenterId || datacenterId < 0) {
    exceptionCounter.incr(1)
    throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))
  }

  log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
    timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
  //获取ID的方法
  def get_id(useragent: String): Long = {
    if (!validUseragent(useragent)) {
      exceptionCounter.incr(1)
      throw new InvalidUserAgentError
    }

    val id = nextId()
    genCounter(useragent)

    reporter.report(new AuditLogEntry(id, useragent, rand.nextLong))
    id
  }

  def get_worker_id(): Long = workerId
  def get_datacenter_id(): Long = datacenterId
  def get_timestamp() = System.currentTimeMillis

  //生成ID的方法
  protected[snowflake] def nextId(): Long = synchronized {
    var timestamp = timeGen()
    //时钟回拨，直接产生异常
    if (timestamp < lastTimestamp) {
      exceptionCounter.incr(1)
      log.error("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
      throw new InvalidSystemClock("Clock moved backwards.  Refusing to generate id for %d milliseconds".format(
        lastTimestamp - timestamp))
    }

    if (lastTimestamp == timestamp) {
      sequence = (sequence + 1) & sequenceMask
      //sequence在同1ms内溢出，则等待到下一ms再返回ID
      if (sequence == 0) {
        timestamp = tilNextMillis(lastTimestamp)
      }
    } else {
      sequence = 0
    }

    lastTimestamp = timestamp
    ((timestamp - twepoch) << timestampLeftShift) |
      (datacenterId << datacenterIdShift) |
      (workerId << workerIdShift) | 
      sequence
  }

  protected def tilNextMillis(lastTimestamp: Long): Long = {
    var timestamp = timeGen()
    while (timestamp <= lastTimestamp) {
      timestamp = timeGen()
    }
    timestamp
  }

  protected def timeGen(): Long = System.currentTimeMillis()

  val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r

  def validUseragent(useragent: String): Boolean = useragent match {
    case AgentParser(_) => true
    case _ => false
  }
}

正如代码表现出来的那样，snowflake的算法是很简单的。上面代码段有两个关键点需要注意，首先是时钟回拨的问题。由于存在对时操作和闰秒，snowflake算法应对时钟回拨的做法是直接抛出异常。其次是12位序列号溢出的问题，即1ms内请求生成的ID个数超过了4096个id。snowflake算法对此的做法是，等到下一ms再生成ID。

然而这种情况应该很难出现，按照每毫秒4096个ID的速度，单个ID生成服务器的理论能力可以达到3500亿/天。由于snowflake最大可以支持1024个部署实例。据微信团队的分享，微信序列号生成服务每天的调用次数是万亿级别。所以从QPS来说，snowflake算法是没什么问题的。

2. 美团点评的ID生成服务Leaf

据美团点评技术团队的分享，他们使用了名为Leaf的分布式ID生成系统。Leaf系统实现了两种方案，第一种名为Leaf-snowflake。这种方案和普通的Twitter snowflake没太多区别，其中leaf-snowflake使用了Zookeeper实现对机器id的配置，可以一定程度的提高系统的伸缩性和容错性。leaf-snowflake的架构图如下：

此外，Leaf-snowflake节点对ZooKeeper是弱依赖的，本地节点也会有一个备用的机器id。这可完全可以理解，因为注册中心对snowflake而言本来就不是必须的。个人认为，Zookeeper的最大作用还是方便上层管理和监听。

上面简单说了一下Leaf-snowflake，接下来我们看看Leaf-segment。Leaf-segment的核心思想其实很简单，就是“化零为整”。在Leaf-segment算法中，采用了集中式的数据库管理方式。在ID数据库的上层是多个proxy server，proxy server每次向数据库申请一段IDs，然后把这段IDs作为id池，为外部客户端提供ID。Leaf-segment的总体架构如下：

其实看到这个架构图，一切都一目了然了。这个系统的主要瓶颈在于db server的单点故障问题。为此，美团点评团队的做法是采用主被的数据库架构。slave db在master db宕掉之后继续服务，提高了可用性。主被db采用的binlog订阅的方式，可能存在不同步的问题，这是一个缺陷。倘若这里使用类似ZooKeeper这样的CP系统，又有可能存在QPS上不去的问题。这里明显就有一个明显的权衡。

此外，值得一提的是，Leaf-segment的proxy server使用了双缓冲的方式优化请求的最大延迟，和窗口系统的显示双缓冲非常类似。

3. 微信seqsvr

微信的seqsvr的作用也是序列号生成。但是微信作为一个IM应用，它的ID生成模式有一定的特殊性。个人理解微信很大的特点就是——它属于熟人社交。微信好像一直都有好友数目的限制，而且好友关系是相互的。因此关于用户的数据信息是可以比较简单的进行水平切分的，比如简单的按用户id进行切分。seqsvr的架构可以分为两层，即StoreSvr和AllocSvr（存储层和缓存中间层）。其总体架构如下：

从垂直方向看，AllocSvr负责直接为客户端分配sequence，而StoreSvr则负责当前最大sequence num的可靠存储（通过NRW实现）。这个角度看来，和美团点评的Leaf-segment是非常相似的。主要区别在于两点，第一是seqsvr产生的sequence是在UID（用户ID）之下的id，换言之——UID + sequence = 全局ID；第二点是seqsvr使用了NRW实现了数据存储的强一致性。

从水平方向看，seqsvr使用UID进行了水平切分，实现了负载均衡。对单一的一个set分析可知，AllocSvr可以完全以运行在内存中，而不用实现持久化。因为最恶劣的情况就是，AllocSvr中一部分id还没有被消费的情况下宕机了，重启之后又重新申请了一段id，所以有一部分id被跳过了。然而，微信的sequence num有64位，而且是位于UID之下的，所以跳过一段id完全可以接受。

所以，seqsvr的主要压力还是在StoreSvr，即使进行了Set切分，NRW存储模式依然还是要在吞吐量上付出代价。大概是经过了进一步的实验，seqsvr进行了进一步的优化——分段号共享存储。如下图所示，max_seq就是当前的最大序列号。一组用户共享一个max_seq，分组的方式依然是使用UID进行切分。这样一来，seqsvr中StoreSvr的压力变得更小了。举例来说，如果大家的操作频率是均等的，那么StoreSvr的写入压力降为切分之前的1 / N（N为分组内部用户的数目）。而且StoreSvr对数据的载入压力也降低为1 / N。

经过一番分析，可以发现微信的seqsvr的设计还是很优秀的，毕竟能做出这么成功的应用必然有很多幕后高手。此外，seqsvr还有很多容灾迁移的设计，这里我就不写了。

参考资料：

【1】微信序列号生成器架构设计及演变

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

【3】Twitter snowflake