在分布式系统中，需要生成全局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 |
?> |
