分布式ID雪花算法-解析 - Go语言中文社区

分布式ID雪花算法-解析

SnowFlake算法生成id的结果是一个64bit大小的整数，它的结构如下图：

图片描述

  • 1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0

  • 41位，用来记录时间戳（毫秒）。

    • 41位可以表示241−1个数字，
    • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 241−1，减1是因为可表示的数值范围是从0开始算的，而不是1。
    • 也就是说41位可以表示241−1个毫秒的值，转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年

  • 10位，用来记录工作机器id。

    • 可以部署在210=1024个节点，包括5位datacenterId和5位workerId
    • 5位（bit）可以表示的最大正整数是25−1=31，即可以用0、1、2、3、....31这32个数字，来表示不同的datecenterId或workerId

  • 12位，序列号，用来记录同毫秒内产生的不同id。

    • 12位（bit）可以表示的最大正整数是212−1=4095，即可以用0、1、2、3、....4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号

由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。

SnowFlake可以保证：

  • 所有生成的id按时间趋势递增
  • 整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）

Talk is cheap, show you the code

以下是Twitter官方原版的，用Scala写的，（我也不懂Scala，当成Java看即可）：

/** 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

/**
 * 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
  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)

  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) {
      sequence = (sequence + 1) & sequenceMask
      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
  }
}

Scala是一门可以编译成字节码的语言，简单理解是在Java语法基础上加上了很多语法糖，例如不用每条语句后写分号，可以使用动态类型等等。抱着试一试的心态，我把Scala版的代码“翻译”成Java版本的，对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

/**
 * 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,                            // |<--这部分改成Java的构造函数形式
    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
  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)

  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))                 //这
    // |-->改成：throw new IllegalArgumentException                                                                              //部
    //            (String.format("worker Id can't be greater than %d or less than 0",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))         //函
    // |-->改成：throw new IllegalArgumentException                                                                             //数
    //             (String.format("datacenter Id can't be greater than %d or less than 0",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)                                                 //   
  // |-->改成：System.out.printf("worker...%d...",timestampLeftShift,...);                                                      //
  //----------------------------------------------------------------------------------------------------------------------------//

  //-------------------------------------------------------------------//  
  //这个函数删除错误处理相关的代码后，剩下一行代码：val id = nextId()      //
  //所以我们直接调用nextId()函数可以了，所以在“翻译”时可以删除这个函数      //
  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   // |<--改成Java函数
  def get_timestamp() = System.currentTimeMillis // |

  protected[snowflake] def nextId(): Long = synchronized { // 改成Java函数
    var timestamp = timeGen()

    if (timestamp < lastTimestamp) {
      exceptionCounter.incr(1) // 错误处理相关，删
      log.error("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp); // 改成System.err.printf(...)
      throw new InvalidSystemClock("Clock moved backwards.  Refusing to generate id for %d milliseconds".format(
        lastTimestamp - timestamp)) // 改成RumTimeException
    }

    if (lastTimestamp == timestamp) {
      sequence = (sequence + 1) & sequenceMask
      if (sequence == 0) {
        timestamp = tilNextMillis(lastTimestamp)
      }
    } else {
      sequence = 0
    }

    lastTimestamp = timestamp
    ((timestamp - twepoch) << timestampLeftShift) | // |<--加上关键字return
      (datacenterId << datacenterIdShift) |         // |
      (workerId << workerIdShift) |                 // |
      sequence                                      // |
  }

  protected def tilNextMillis(lastTimestamp: Long): Long = { // 改成Java函数
    var timestamp = timeGen()
    while (timestamp <= lastTimestamp) {
      timestamp = timeGen()
    }
    timestamp // 加上关键字return
  }

  protected def timeGen(): Long = System.currentTimeMillis() // 改成Java函数

  val AgentParser = """([a-zA-Z][a-zA-Z-0-9]*)""".r                  // |
                                                                      // | 
  def validUseragent(useragent: String): Boolean = useragent match {  // |<--日志相关，删
    case AgentParser(_) => true                                       // |
    case _ => false                                                   
                            
                            版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。

                            原文链接：https://blog.csdn.net/cj2580/article/details/80980459

                            站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
  • 发表于 2020-03-07 10:57:07
  • 阅读 ( 1165 )
  • 分类：算法

你可能感兴趣的文章

精选的优质文章

0 条评论

请先 登录 后评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看

来源51CTO

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！