Twitter的分布式自增ID算法Snowflake

标签: twitter id 算法 | 发表时间:2016-01-21 13:00 | 作者:newboy2004
出处:http://www.iteye.com

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

 

10---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
3package com.twitter.service.snowflake
5import com.twitter.ostrich.stats.Stats
6import com.twitter.service.snowflake.gen._
7import java.util.Random
8import com.twitter.logging.Logger
10
16class IdWorker(val workerId: Long, val datacenterId: Long, private val reporter: Reporter, var sequence: Long = 0L)
17extends 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 
122protected 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}
 
 
转载自: http://blog.sina.com.cn/s/blog_6b7c2e660102vbi2.html#userconsent#


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [twitter id 算法] 推荐:

Twitter的分布式自增ID算法Snowflake

- - 企业架构 - ITeye博客
Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳, 工作机器id, 序列号组合在一起.

SnowFlake 分布式ID生成算法Java实现

- - ITeye博客
SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID.

产生Id

- - 研发管理 - ITeye博客
// worker编号最大值,决定支持的部署节点数量. // 毫秒内自增位数,每毫秒最大序号支持65535. // worker编号偏移量. // 毫秒基线:2015-01-01 00:00:00. * 从环境变量中获取worker编号,每个部署环境编号不能重复. * 每个部署环境编号不能重复. * @param workerId Worker编号.

语言学家开发出算法识别Twitter用户性别

- geek2live - Solidot
网民多以假名掩盖身份,雌雄难辩,男扮女女扮男屡见不鲜,然而他们的言语和喜好会暴露他们的身份. Mitre公司的语言学研究人员,在苏格兰举行的自然语言处理实证方法会议上公布了一篇论文(PDF),称他们开发出一种算法能根据Twitter用户的帖子内容识别出其性别,他们的依据是女性所用语言和男性存在相当大的差异.

小米手机ID简介

- miyizs - Billwang 工业设计
      小米手机是小米公司(全称北京小米科技有限责任公司)专为发烧友级手机控打造的 一款高品质智能手机. 下面我们将对其做一个简单的介绍.       小米手机的外观设计走的是简约内敛路线,直板加圆润的边角让其显得简单清爽. 小米手机配置了,1.5GHz双核处理器、1G RAM、4英寸夏普屏、800万像素摄像头以及大容量电池.

id Software发布《狂怒(Rage)》

- ArmadilloCommander - Solidot
id Software发布了容量为21GB的第一人称射击游戏《狂怒(Rage)》. 游戏基于id Tech 5引擎,背景是世界末日后的未来. 目前对它的评价好坏参半,媒体综合评分80左右,玩家评分相似或更低. 在游戏中,玩家将扮演一位小行星Apophis撞击地球后的幸存者. 在灾难发生前,全世界展开合作将包括科学家在内的精英冰冻在地下,以在灾难后重建地球.

标签?ID?还是CLASS?

- - 前端观察
想谈一下几个基本的HTML问题,都是围绕着应该怎样使用HTML. 多用有语义的标签,少用div和span,避免使用没有class的div和span. 设想一下HTML的世界最初只有div和span这两个标签,其实网页依然可以写得出来. 更多标签的出现,其实是为了替代利用率高但不好书写的  <div class="{tagname}"> 和 <span class="{tagname}"> 来的.

Linuxer:制作自己的Linux ID Card吧

- rex - Wow! Ubuntu
Super Boot Manager的作者Alessandro Lanave,又为Linuxer带来了一个web程序,制作Linux ID Card ,Card效果如图. 可以把ID Card做为论坛签名,博客签名,任何你需要的地方. 当然,如果觉得没有自己喜欢的发行版的模板,可以向Alessandro Lanave提交哦,.

两个 Apple ID 是很有必要的

- 闷闲居士 - Page to Page
刚买iPad的时候注册的是中国区的Apple ID,绑定了自己的信用卡. 可当搜索下载Kindle for iPad的时候才觉得,注册一个美国区的Apple ID还是很有必要的,否则很多中国区没有的App无法下载. 大致学习了2篇注册美国区ID的帖子,赶紧动手,可是还是因为疏忽产生了问题,提示我说“我的邮箱地址已经注册了”.