Twitter的分布式自增ID算法snowflake

Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

把时间戳，工作机器id，序列号组合在一起。

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

Snowflake – 时间戳

这里时间戳的细度是毫秒级，具体代码如下，建议使用64位linux系统机器，因为有vdso，gettimeofday()在用户态就可以完成操作，减少了进入内核态的损耗。

uint64_t generateStamp(){    timeval tv;    gettimeofday(&tv, 0);    return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;}

默认情况下有41个bit可以供使用，那么一共有T（1llu << 41）毫秒供你使用分配，年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用，那么根据同样的算法最后年份 = 17.4年。

Snowflake – 工作机器id

严格意义上来说这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程，可以使用自己编写一个简单进程来记录分配id，或者利用Mysql auto_increment机制也可以达到效果。

工作进程与工作id分配器只是在工作进程启动的时候交互一次，然后工作进程可以自行将分配的id数据落文件，下一次启动直接读取文件里的id使用。

PS：这个工作机器id的bit段也可以进一步拆分，比如用前5个bit标记进程id，后5个bit标记线程id之类:D

Snowflake – 序列号

序列号就是一系列的自增id（多线程建议使用atomic），为了处理在同一毫秒内需要给多条消息分配id，若同一毫秒把序列号用完了，则“等待至下一毫秒”。

uint64_t waitNextMs(uint64_t lastStamp){    uint64_t cur = 0;    do {        cur = generateStamp();    } while (cur <= lastStamp);    return cur;}

总体来说，是一个很高效很方便的GUID产生算法，一个int64_t字段就可以胜任，不像现在主流128bit的GUID算法，即使无法保证严格的id序列性，但是对于特定的业务，比如用做游戏服务器端的GUID产生会很方便。另外，在多线程的环境下，序列号使用atomic可以在代码实现上有效减少锁的密度。

在分布式系统中，需要生成全局UID的场合还是比较多的，twitter的snowflake解决了这种需求，实现也还是很简单的，除去配置信息，核心代码就是毫秒级时间41位+机器ID 10位+毫秒内序列12位。

核心代码为其IdWorker这个类实现，其原理结构如下，我分别用一个0表示一位，用—分割开部分的作用：

0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000

在上面的字符串中，第一位为未使用（实际上也可作为long的符号位），接下来的41位为毫秒级时间，然后5位datacenter标识位，5位机器ID（并不算标识符，实际是为线程标识），然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为一个Long型。

这样的好处是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和机器ID作区分），并且效率较高，经测试，snowflake每秒能够产生26万ID左右，完全满足需要。

且看其核心代码：

/** Copyright 2010-2012 Twitter, Inc.*/package com.twitter.service.snowflakeimport com.twitter.ostrich.stats.Statsimport com.twitter.service.snowflake.gen._import java.util.Randomimport com.twitter.logging.Logger/** * An object that generates IDs. * This is broken into a separate class in case * we ever want to support multiple worker threads * per process */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  val twepoch = 1288834974657L //机器标识位数  private[this] val workerIdBits = 5L//数据中心标识位数  private[this] val datacenterIdBits = 5L//机器ID最大值  private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits)//数据中心ID最大值  private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)//毫秒内自增位  private[this] val sequenceBits = 12L//机器ID偏左移12位  private[this] val workerIdShift = sequenceBits//数据中心ID左移17位  private[this] val datacenterIdShift = sequenceBits + workerIdBits//时间毫秒左移22位  private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits  private[this] val sequenceMask = -1L ^ (-1L << sequenceBits)  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)  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  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) {//当前毫秒内，则+1      sequence = (sequence + 1) & sequenceMask      if (sequence == 0) {//当前毫秒内计数满了，则等待下一秒        timestamp = tilNextMillis(lastTimestamp)      }    } else {      sequence = 0    }    lastTimestamp = timestamp//ID偏移组合生成最终的ID，并返回ID   ((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  }}

上述为twitter的实现，下面且看一个Java实现，貌似为淘宝的朋友写的。

public class IdWorker { private final long workerId; private final static long twepoch = 1361753741828L; private long sequence = 0L; private final static long workerIdBits = 4L; public final static long maxWorkerId = -1L ^ -1L << workerIdBits; private final static long sequenceBits = 10L; private final static long workerIdShift = sequenceBits; private final static long timestampLeftShift = sequenceBits + workerIdBits; public final static long sequenceMask = -1L ^ -1L << sequenceBits; private long lastTimestamp = -1L; public IdWorker(final long workerId) {  super();  if (workerId > this.maxWorkerId || workerId < 0) {   throw new IllegalArgumentException(String.format(     "worker Id can't be greater than %d or less than 0",     this.maxWorkerId));  }  this.workerId = workerId; } public synchronized long nextId() {  long timestamp = this.timeGen();  if (this.lastTimestamp == timestamp) {   this.sequence = (this.sequence + 1) & this.sequenceMask;   if (this.sequence == 0) {    System.out.println("###########" + sequenceMask);    timestamp = this.tilNextMillis(this.lastTimestamp);   }  } else {   this.sequence = 0;  }  if (timestamp < this.lastTimestamp) {   try {    throw new Exception(      String.format(        "Clock moved backwards.  Refusing to generate id for %d milliseconds",        this.lastTimestamp - timestamp));   } catch (Exception e) {    e.printStackTrace();   }  }  this.lastTimestamp = timestamp;  long nextId = ((timestamp - twepoch << timestampLeftShift))    | (this.workerId << this.workerIdShift) | (this.sequence);//  System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"//    + timestampLeftShift + ",nextId:" + nextId + ",workerId:"//    + workerId + ",sequence:" + sequence);  return nextId; } private long tilNextMillis(final long lastTimestamp) {  long timestamp = this.timeGen();  while (timestamp <= lastTimestamp) {   timestamp = this.timeGen();  }  return timestamp; } private long timeGen() {  return System.currentTimeMillis(); }   public static void main(String[] args){  IdWorker worker2 = new IdWorker(2);  System.out.println(worker2.nextId());   }}

再来看一个php的实现

<?phpclass Idwork{const debug = 1;static $workerId;static $twepoch = 1361775855078;static $sequence = 0;const workerIdBits = 4;static $maxWorkerId = 15;const sequenceBits = 10;static $workerIdShift = 10;static $timestampLeftShift = 14;static $sequenceMask = 1023;private  static $lastTimestamp = -1;function __construct($workId){if($workId > self::$maxWorkerId || $workId< 0 ){throw new Exception("worker Id can't be greater than 15 or less than 0");}self::$workerId=$workId;echo 'logdebug->__construct()->self::$workerId:'.self::$workerId;echo '</br>';}function timeGen(){//获得当前时间戳$time = explode(' ', microtime());$time2= substr($time[0], 2, 3);$timestramp = $time[1].$time2;echo 'logdebug->timeGen()->$timestramp:'.$time[1].$time2;echo '</br>';return  $time[1].$time2;}function  tilNextMillis($lastTimestamp) {$timestamp = $this->timeGen();while ($timestamp <= $lastTimestamp) {$timestamp = $this->timeGen();}echo 'logdebug->tilNextMillis()->$timestamp:'.$timestamp;echo '</br>';return $timestamp;}function  nextId(){$timestamp=$this->timeGen();echo 'logdebug->nextId()->self::$lastTimestamp1:'.self::$lastTimestamp;echo '</br>';if(self::$lastTimestamp == $timestamp) {self::$sequence = (self::$sequence + 1) & self::$sequenceMask;if (self::$sequence == 0) {    echo "###########".self::$sequenceMask;    $timestamp = $this->tilNextMillis(self::$lastTimestamp);    echo 'logdebug->nextId()->self::$lastTimestamp2:'.self::$lastTimestamp;    echo '</br>';  }} else {self::$sequence  = 0;    echo 'logdebug->nextId()->self::$sequence:'.self::$sequence;    echo '</br>';}if ($timestamp < self::$lastTimestamp) {   throw new Excwption("Clock moved backwards.  Refusing to generate id for ".(self::$lastTimestamp-$timestamp)." milliseconds");   }self::$lastTimestamp  = $timestamp;echo 'logdebug->nextId()->self::$lastTimestamp3:'.self::$lastTimestamp;echo '</br>';echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):'.((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch) ));echo '</br>';$nextId = ((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch)  )) | ( self::$workerId << self::$workerIdShift ) | self::$sequence;echo 'timestamp:'.$timestamp.'-----';echo 'twepoch:'.sprintf('%.0f', self::$twepoch).'-----';echo 'timestampLeftShift ='.self::$timestampLeftShift.'-----';echo 'nextId:'.$nextId<mark>（本文来）源gaodaimacom搞#^代%!码&网(</mark><pre>搞gaodaima代码

.'—-';echo 'workId:'.self::$workerId.'—–';echo 'workerIdShift:'.self::$workerIdShift.'—–';return $nextId;}}$Idwork = new Idwork(1);$a= $Idwork->nextId();$Idwork = new Idwork(2);$a= $Idwork->nextId();?>

喜欢 (0)赏

[搞代码]

分享 (0)