Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版-阿里云开发者社区

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

该项目地址为：https://github.com/twitter/snowflake是用Scala实现的。

python版详见开源项目https://github.com/erans/pysnowflake。

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

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

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

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

且看其核心代码：

 
       1 
       </pre> 
      
       2 
       /** Copyright 2010-2012 Twitter, Inc.*/ 
      
       3 
        package com.twitter.service.snowflake  
      
       4 
         
       5 
        import com.twitter.ostrich.stats.Stats  
      
       6 
        import com.twitter.service.snowflake.gen._  
      
       7 
        import java.util.Random  
      
       8 
        import com.twitter.logging.Logger  
      
       9 
         
       10 
       /** 
      
       11 
         * An object that generates IDs.  
      
       12 
         * This is broken into a separate class in case  
      
       13 
         * we ever want to support multiple worker threads  
      
       14 
         * per process  
      
       15 
         */  
      
       16 
        class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L)  
      
       17 
        extends Snowflake.Iface {  
      
       18 
          private[this] def genCounter(agent: String) = {  
      
       19 
            Stats.incr("ids_generated")  
      
       20 
            Stats.incr("ids_generated_%s".format(agent))  
      
       21 
          }  
      
       22 
          private[this] val exceptionCounter = Stats.getCounter("exceptions")  
      
       23 
          private[this] val log = Logger.get  
      
       24 
          private[this] val rand = new Random  
      
       25 
         
       26 
          val twepoch = 1288834974657L  
      
       27 
         
       28 
         //机器标识位数  
      
       29 
         
       30 
          private[this] val workerIdBits = 5L  
      
       31 
         
       32 
       //数据中心标识位数 
      
       33 
          private[this] val datacenterIdBits = 5L  
      
       34 
         
       35 
       //机器ID最大值 
      
       36 
          private[this] val maxWorkerId = -1L ^ (-1L << workerIdBits)  
      
       37 
         
       38 
       //数据中心ID最大值 
      
       39 
          private[this] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)  
      
       40 
         
       41 
       //毫秒内自增位 
      
       42 
          private[this] val sequenceBits = 12L  
      
       43 
         
       44 
       //机器ID偏左移12位 
      
       45 
         
       46 
          private[this] val workerIdShift = sequenceBits  
      
       47 
         
       48 
       //数据中心ID左移17位 
      
       49 
          private[this] val datacenterIdShift = sequenceBits + workerIdBits  
      
       50 
         
       51 
       //时间毫秒左移22位 
      
       52 
          private[this] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits  
      
       53 
          private[this] val sequenceMask = -1L ^ (-1L << sequenceBits)  
      
       54 
         
       55 
          private[this] var lastTimestamp = -1L  
      
       56 
         
       57 
          // sanity check for workerId  
      
       58 
          if (workerId > maxWorkerId || workerId < 0) {  
      
       59 
            exceptionCounter.incr(1)  
      
       60 
            throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId))  
      
       61 
          }  
      
       62 
         
       63 
          if (datacenterId > maxDatacenterId || datacenterId < 0) {  
      
       64 
            exceptionCounter.incr(1)  
      
       65 
            throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId))  
      
       66 
          }  
      
       67 
         
       68 
          log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",  
      
       69 
            timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)  
      
       70 
         
       71 
          def get_id(useragent: String): Long = {  
      
       72 
            if (!validUseragent(useragent)) {  
      
       73 
              exceptionCounter.incr(1)  
      
       74 
              throw new InvalidUserAgentError  
      
       75 
            }  
      
       76 
         
       77 
            val id = nextId()  
      
       78 
            genCounter(useragent)  
      
       79 
         
       80 
            reporter.report(new AuditLogEntry(id, useragent, rand.nextLong))  
      
       81 
            id  
      
       82 
          }  
      
       83 
         
       84 
          def get_worker_id(): Long = workerId  
      
       85 
          def get_datacenter_id(): Long = datacenterId  
      
       86 
          def get_timestamp() = System.currentTimeMillis  
      
       87 
         
       88 
          protected[snowflake] def nextId(): Long = synchronized {  
      
       89 
            var timestamp = timeGen()  
      
       90 
         
       91 
         //时间错误  
      
       92 
         
       93 
            if (timestamp < lastTimestamp) {  
      
       94 
              exceptionCounter.incr(1)  
      
       95 
              log.error("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);  
      
       96 
              throw new InvalidSystemClock("Clock moved backwards.  Refusing to generate id for %d milliseconds".format(  
      
       97 
                lastTimestamp - timestamp))  
      
       98 
            }  
      
       99 
         
       100 
            if (lastTimestamp == timestamp) {  
      
       101 
       //当前毫秒内，则+1 
      
       102 
              sequence = (sequence + 1) & sequenceMask  
      
       103 
              if (sequence == 0) {  
      
       104 
       //当前毫秒内计数满了，则等待下一秒 
      
       105 
                timestamp = tilNextMillis(lastTimestamp)  
      
       106 
              }  
      
       107 
            } else {  
      
       108 
              sequence = 0  
      
       109 
            }  
      
       110 
         
       111 
            lastTimestamp = timestamp  
      
       112 
       //ID偏移组合生成最终的ID，并返回ID    
      
       113 
         
       114 
       ((timestamp - twepoch) << timestampLeftShift) | 
      
       115 
              (datacenterId << datacenterIdShift) |  
      
       116 
              (workerId << workerIdShift) |  
      
       117 
              sequence  
      
       118 
          }  
      
       119 
         
       120 
       //等待下一个毫秒的到来  
      
       121 
         
       122 
        protected def tilNextMillis(lastTimestamp: Long): Long = {  
      
       123 
            var timestamp = timeGen()  
      
       124 
            while (timestamp <= lastTimestamp) {  
      
       125 
              timestamp = timeGen()  
      
       126 
            }  
      
       127 
            timestamp  
      
       128 
          }  
      
       129 
         
       130 
          protected def timeGen(): Long = System.currentTimeMillis()  
      
       131 
         
       132 
          val AgentParser = """([a-zA-Z][a-zA-Z\-0-9]*)""".r  
      
       133 
         
       134 
          def validUseragent(useragent: String): Boolean = useragent match {  
      
       135 
            case AgentParser(_) => true  
      
       136 
            case _ => false  
      
       137 
          }  
      
       138 
       } 
      
       139 
       <pre>

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

 
       1 
        public class IdWorker {  
      
       2 
         private final long workerId;  
      
       3 
         private final static long twepoch = 1361753741828L;  
      
       4 
         private long sequence = 0L;  
      
       5 
         private final static long workerIdBits = 4L;  
      
       6 
         public final static long maxWorkerId = -1L ^ -1L << workerIdBits;  
      
       7 
         private final static long sequenceBits = 10L;  
      
       8 
         
       9 
         private final static long workerIdShift = sequenceBits;  
      
       10 
         private final static long timestampLeftShift = sequenceBits + workerIdBits;  
      
       11 
         public final static long sequenceMask = -1L ^ -1L << sequenceBits;  
      
       12 
         
       13 
         private long lastTimestamp = -1L;  
      
       14 
         
       15 
         public IdWorker(final long workerId) {  
      
       16 
          super();  
      
       17 
          if (workerId > this.maxWorkerId || workerId < 0) {  
      
       18 
           throw new IllegalArgumentException(String.format(  
      
       19 
             "worker Id can't be greater than %d or less than 0",  
      
       20 
             this.maxWorkerId));  
      
       21 
          }  
      
       22 
          this.workerId = workerId;  
      
       23 
         }  
      
       24 
         
       25 
         public synchronized long nextId() {  
      
       26 
          long timestamp = this.timeGen();  
      
       27 
          if (this.lastTimestamp == timestamp) {  
      
       28 
           this.sequence = (this.sequence + 1) & this.sequenceMask;  
      
       29 
           if (this.sequence == 0) {  
      
       30 
            System.out.println("###########" + sequenceMask);  
      
       31 
            timestamp = this.tilNextMillis(this.lastTimestamp);  
      
       32 
           }  
      
       33 
          } else {  
      
       34 
           this.sequence = 0;  
      
       35 
          }  
      
       36 
          if (timestamp < this.lastTimestamp) {  
      
       37 
           try {  
      
       38 
            throw new Exception(  
      
       39 
              String.format(  
      
       40 
                "Clock moved backwards.  Refusing to generate id for %d milliseconds",  
      
       41 
                this.lastTimestamp - timestamp));  
      
       42 
           } catch (Exception e) {  
      
       43 
            e.printStackTrace();  
      
       44 
           }  
      
       45 
          }  
      
       46 
         
       47 
          this.lastTimestamp = timestamp;  
      
       48 
          long nextId = ((timestamp - twepoch << timestampLeftShift))  
      
       49 
            | (this.workerId << this.workerIdShift) | (this.sequence);  
      
       50 
       //  System.out.println("timestamp:" + timestamp + ",timestampLeftShift:" 
      
       51 
       //    + timestampLeftShift + ",nextId:" + nextId + ",workerId:" 
      
       52 
       //    + workerId + ",sequence:" + sequence); 
      
       53 
          return nextId;  
      
       54 
         }  
      
       55 
         
       56 
         private long tilNextMillis(final long lastTimestamp) {  
      
       57 
          long timestamp = this.timeGen();  
      
       58 
          while (timestamp <= lastTimestamp) {  
      
       59 
           timestamp = this.timeGen();  
      
       60 
          }  
      
       61 
          return timestamp;  
      
       62 
         }  
      
       63 
         
       64 
         private long timeGen() {  
      
       65 
          return System.currentTimeMillis();  
      
       66 
         }  
      
       67 
           
       68 
           
       69 
         public static void main(String[] args){  
      
       70 
          IdWorker worker2 = new IdWorker(2);  
      
       71 
          System.out.println(worker2.nextId());  
      
       72 
         
       73 
            
       74 
         }  
      
       75 
         
       76 
       }

再来看一个php的实现

 
       1 
       <?php 
      
       2 
        class Idwork  
      
       3 
       { 
      
       4 
        const debug = 1;  
      
       5 
        static $workerId;  
      
       6 
        static $twepoch = 1361775855078;  
      
       7 
        static $sequence = 0;  
      
       8 
        const workerIdBits = 4;  
      
       9 
        static $maxWorkerId = 15;  
      
       10 
        const sequenceBits = 10;  
      
       11 
        static $workerIdShift = 10;  
      
       12 
        static $timestampLeftShift = 14;  
      
       13 
        static $sequenceMask = 1023;  
      
       14 
        private  static $lastTimestamp = -1;  
      
       15 
         
       16 
        function __construct($workId){  
      
       17 
        if($workId > self::$maxWorkerId || $workId< 0 )  
      
       18 
       { 
      
       19 
        throw new Exception("worker Id can't be greater than 15 or less than 0");  
      
       20 
       } 
      
       21 
        self::$workerId=$workId;  
      
       22 
         
       23 
        echo 'logdebug->__construct()->self::$workerId:'.self::$workerId;  
      
       24 
        echo '</br>';  
      
       25 
         
       26 
       } 
      
       27 
         
       28 
        function timeGen(){  
      
       29 
       //获得当前时间戳 
      
       30 
        $time = explode(' ', microtime());  
      
       31 
        $time2= substr($time[0], 2, 3);  
      
       32 
        $timestramp = $time[1].$time2;  
      
       33 
        echo 'logdebug->timeGen()->$timestramp:'.$time[1].$time2;  
      
       34 
        echo '</br>';  
      
       35 
        return  $time[1].$time2;  
      
       36 
       } 
      
       37 
        function  tilNextMillis($lastTimestamp) {  
      
       38 
        $timestamp = $this->timeGen();  
      
       39 
        while ($timestamp <= $lastTimestamp) {  
      
       40 
        $timestamp = $this->timeGen();  
      
       41 
       } 
      
       42 
         
       43 
        echo 'logdebug->tilNextMillis()->$timestamp:'.$timestamp;  
      
       44 
        echo '</br>';  
      
       45 
        return $timestamp;  
      
       46 
       } 
      
       47 
         
       48 
        function  nextId()  
      
       49 
       { 
      
       50 
        $timestamp=$this->timeGen();  
      
       51 
        echo 'logdebug->nextId()->self::$lastTimestamp1:'.self::$lastTimestamp;  
      
       52 
        echo '</br>';  
      
       53 
        if(self::$lastTimestamp == $timestamp) {  
      
       54 
        self::$sequence = (self::$sequence + 1) & self::$sequenceMask;  
      
       55 
        if (self::$sequence == 0) {  
      
       56 
            echo "###########".self::$sequenceMask;  
      
       57 
            $timestamp = $this->tilNextMillis(self::$lastTimestamp);  
      
       58 
            echo 'logdebug->nextId()->self::$lastTimestamp2:'.self::$lastTimestamp;  
      
       59 
            echo '</br>';  
      
       60 
          }  
      
       61 
        } else {  
      
       62 
        self::$sequence  = 0;  
      
       63 
            echo 'logdebug->nextId()->self::$sequence:'.self::$sequence;  
      
       64 
            echo '</br>';  
      
       65 
       } 
      
       66 
        if ($timestamp < self::$lastTimestamp) {  
      
       67 
           throw new Excwption("Clock moved backwards.  Refusing to generate id for ".(self::$lastTimestamp-$timestamp)." milliseconds");  
      
       68 
           }  
      
       69 
        self::$lastTimestamp  = $timestamp;  
      
       70 
        echo 'logdebug->nextId()->self::$lastTimestamp3:'.self::$lastTimestamp;  
      
       71 
        echo '</br>';  
      
       72 
         
       73 
        echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):'.((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch) ));  
      
       74 
        echo '</br>';  
      
       75 
        $nextId = ((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch)  )) | ( self::$workerId << self::$workerIdShift ) | self::$sequence;  
      
       76 
        echo 'timestamp:'.$timestamp.'-----';  
      
       77 
        echo 'twepoch:'.sprintf('%.0f', self::$twepoch).'-----';  
      
       78 
        echo 'timestampLeftShift ='.self::$timestampLeftShift.'-----';  
      
       79 
        echo 'nextId:'.$nextId.'----';  
      
       80 
        echo 'workId:'.self::$workerId.'-----';  
      
       81 
        echo 'workerIdShift:'.self::$workerIdShift.'-----';  
      
       82 
        return $nextId;  
      
       83 
       } 
      
       84 
         
       85 
       } 
      
       86 
        $Idwork = new Idwork(1);  
      
       87 
        $a= $Idwork->nextId();  
      
       88 
        $Idwork = new Idwork(2);  
      
       89 
        $a= $Idwork->nextId();  
      
       90 
       ?>

Twitter的分布式自增ID算法Snowflake实现分析及其Java、Php和Python版

热门文章

最新文章

相关课程

相关电子书

推荐镜像

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站