Twitter的分布式自增ID算法Snowflake
- - 企业架构 - ITeye博客Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳， 工作机器id， 序列号组合在一起.
Twitter的分布式自增ID算法Snowflake
标签：
twitter
分布
id
| 发表时间：2016-01-21 21: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
4
5import com.twitter.ostrich.stats.Stats
6import com.twitter.service.snowflake.gen._
7import java.util.Random
8import com.twitter.logging.Logger
9
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] 推荐：
分布式高可用id服务器设计实现
- - C++博客-首页原创精华区服务端/后台开发中如何生成id是每个开发者都会遇到的问题，在电商、游戏领域尤其突出. 如何保证生成id的唯一性、可靠性、高可用性，如何组织id的格式，在不同的应用场景和限制下实现方式也不尽相同. 我们的应用场景类似电商，在一个订单的生命周期内，有多个逻辑需要生成各自的id，还要考虑到可读性和灵活性，我们决定实现一个独立的id服务.
Leaf——美团点评分布式ID生成系统
- - 美团点评技术团队在复杂分布式系统中，往往需要对大量的数据和消息进行唯一标识. 如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中，数据日渐增长，对数据分库分表后需要有一个唯一ID来标识一条数据或消息，数据库的自增ID显然不能满足需求；特别一点的如订单、骑手、优惠券也都需要有唯一ID做标识. 此时一个能够生成全局唯一ID的系统是非常必要的.
SnowFlake 分布式ID生成算法Java实现
- - ITeye博客SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质，不像基于ZK，Redis等，每次用完一个区间还得通过网络去获取下一个区间，效率较低，基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字，其中42位时间戳，接下来10位是自定义的数，其作用就是区分集群中的所有机器，最后12位是毫秒内序列，集群内每个机器能够在1毫秒内生成2^12 - 1个ID.
分布式系统中唯一 ID 的生成方法
- - 文章 – 伯乐在线本文主要介绍在一个分布式系统中, 怎么样生成全局唯一的 ID. 在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现..
分布式系统中, 怎么样生成全局唯一的 ID
- - zzm在分布式系统存在多个 Shard 的场景中, 同时在各个 Shard 插入数据时, 怎么给这些数据生成全局的 unique ID?. 在单机系统中 (例如一个 MySQL 实例), unique ID 的生成是非常简单的, 直接利用 MySQL 自带的自增 ID 功能就可以实现.. 但在一个存在多个 Shards 的分布式系统 (例如多个 MySQL 实例组成一个集群, 在这个集群中插入数据), 这个问题会变得复杂, 所生成的全局的 unique ID 要满足以下需求:.
产生Id
- - 研发管理 - ITeye博客// worker编号最大值，决定支持的部署节点数量. // 毫秒内自增位数，每毫秒最大序号支持65535. // worker编号偏移量. // 毫秒基线：2015-01-01 00:00:00. * 从环境变量中获取worker编号，每个部署环境编号不能重复. * 每个部署环境编号不能重复. * @param workerId Worker编号.
id Software发布《狂怒（Rage）》
- ArmadilloCommander - Solidotid Software发布了容量为21GB的第一人称射击游戏《狂怒（Rage）》. 游戏基于id Tech 5引擎，背景是世界末日后的未来. 目前对它的评价好坏参半，媒体综合评分80左右，玩家评分相似或更低. 在游戏中，玩家将扮演一位小行星Apophis撞击地球后的幸存者. 在灾难发生前，全世界展开合作将包括科学家在内的精英冰冻在地下，以在灾难后重建地球.
小米手机ID简介
- miyizs - Billwang 工业设计 小米手机是小米公司（全称北京小米科技有限责任公司）专为发烧友级手机控打造的 一款高品质智能手机. 下面我们将对其做一个简单的介绍. 小米手机的外观设计走的是简约内敛路线，直板加圆润的边角让其显得简单清爽. 小米手机配置了，1.5GHz双核处理器、1G RAM、4英寸夏普屏、800万像素摄像头以及大容量电池.