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

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

1. Twitter的snowflake算法

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

snow_flake

这里简单解释一下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

此外,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的总体架构如下:

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(存储层和缓存中间层)。其总体架构如下:

seqsrv

从垂直方向看,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。

seqsrv-segment

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

 

参考资料:

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

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

【3】Twitter snowflake

发表评论