在分布式系统中,需要生成全局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 --- 0000000000 00
|
在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。
这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。
且看其核心代码:
2 |
/** Copyright 2010-2012 Twitter, Inc.*/ |
3 |
package com.twitter.service.snowflake
|
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
|
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
|
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))
|
22 |
private [ this ] val exceptionCounter = Stats.getCounter( "exceptions" )
|
23 |
private [ this ] val log = Logger.get
|
24 |
private [ this ] val rand = new Random
|
26 |
val twepoch = 1288834974657L
|
30 |
private [ this ] val workerIdBits = 5L
|
33 |
private [ this ] val datacenterIdBits = 5L
|
36 |
private [ this ] val maxWorkerId = -1L ^ (-1L << workerIdBits)
|
39 |
private [ this ] val maxDatacenterId = -1L ^ (-1L << datacenterIdBits)
|
42 |
private [ this ] val sequenceBits = 12L
|
46 |
private [ this ] val workerIdShift = sequenceBits
|
49 |
private [ this ] val datacenterIdShift = sequenceBits + workerIdBits
|
52 |
private [ this ] val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits
|
53 |
private [ this ] val sequenceMask = -1L ^ (-1L << sequenceBits)
|
55 |
private [ this ] var lastTimestamp = -1L
|
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))
|
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))
|
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)
|
71 |
def get_id(useragent: String): Long = {
|
72 |
if (!validUseragent(useragent)) {
|
73 |
exceptionCounter.incr( 1 )
|
74 |
throw new InvalidUserAgentError
|
80 |
reporter.report( new AuditLogEntry(id, useragent, rand.nextLong))
|
84 |
def get_worker_id(): Long = workerId
|
85 |
def get_datacenter_id(): Long = datacenterId
|
86 |
def get_timestamp() = System.currentTimeMillis
|
88 |
protected [snowflake] def nextId(): Long = synchronized {
|
89 |
var timestamp = timeGen()
|
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))
|
100 |
if (lastTimestamp == timestamp) {
|
102 |
sequence = (sequence + 1 ) & sequenceMask
|
105 |
timestamp = tilNextMillis(lastTimestamp)
|
111 |
lastTimestamp = timestamp
|
114 |
((timestamp - twepoch) << timestampLeftShift) | |
115 |
(datacenterId << datacenterIdShift) |
|
116 |
(workerId << workerIdShift) |
|
122 |
protected def tilNextMillis(lastTimestamp: Long): Long = {
|
123 |
var timestamp = timeGen()
|
124 |
while (timestamp <= lastTimestamp) {
|
125 |
timestamp = timeGen()
|
130 |
protected def timeGen(): Long = System.currentTimeMillis()
|
132 |
val AgentParser = "" "([a-zA-Z][a-zA-Z\-0-9]*)" "" .r
|
134 |
def validUseragent(useragent: String): Boolean = useragent match {
|
135 |
case AgentParser(_) => true
|
上述为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;
|
9 |
private final static long workerIdShift = sequenceBits;
|
10 |
private final static long timestampLeftShift = sequenceBits + workerIdBits;
|
11 |
public final static long sequenceMask = -1L ^ -1L << sequenceBits;
|
13 |
private long lastTimestamp = -1L;
|
15 |
public IdWorker( final long workerId) {
|
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" ,
|
22 |
this .workerId = workerId;
|
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);
|
36 |
if (timestamp < this .lastTimestamp) {
|
40 |
"Clock moved backwards. Refusing to generate id for %d milliseconds" ,
|
41 |
this .lastTimestamp - timestamp));
|
42 |
} catch (Exception e) {
|
47 |
this .lastTimestamp = timestamp;
|
48 |
long nextId = ((timestamp - twepoch << timestampLeftShift))
|
49 |
| ( this .workerId << this .workerIdShift) | ( this .sequence);
|
56 |
private long tilNextMillis( final long lastTimestamp) {
|
57 |
long timestamp = this .timeGen();
|
58 |
while (timestamp <= lastTimestamp) {
|
59 |
timestamp = this .timeGen();
|
64 |
private long timeGen() {
|
65 |
return System.currentTimeMillis();
|
69 |
public static void main(String[] args){
|
70 |
IdWorker worker2 = new IdWorker( 2 );
|
71 |
System.out.println(worker2.nextId());
|
再来看一个php的实现
6 |
static $twepoch = 1361775855078;
|
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;
|
16 |
function __construct( $workId ){
|
17 |
if ( $workId > self:: $maxWorkerId || $workId < 0 )
|
19 |
throw new Exception( "worker Id can't be greater than 15 or less than 0" );
|
21 |
self:: $workerId = $workId ;
|
23 |
echo 'logdebug->__construct()->self::$workerId:' .self:: $workerId ;
|
30 |
$time = explode ( ' ' , microtime());
|
31 |
$time2 = substr ( $time [0], 2, 3);
|
32 |
$timestramp = $time [1]. $time2 ;
|
33 |
echo 'logdebug->timeGen()->$timestramp:' . $time [1]. $time2 ;
|
35 |
return $time [1]. $time2 ;
|
37 |
function tilNextMillis( $lastTimestamp ) {
|
38 |
$timestamp = $this ->timeGen();
|
39 |
while ( $timestamp <= $lastTimestamp ) {
|
40 |
$timestamp = $this ->timeGen();
|
43 |
echo 'logdebug->tilNextMillis()->$timestamp:' . $timestamp ;
|
50 |
$timestamp = $this ->timeGen();
|
51 |
echo 'logdebug->nextId()->self::$lastTimestamp1:' .self:: $lastTimestamp ;
|
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 ;
|
63 |
echo 'logdebug->nextId()->self::$sequence:' .self:: $sequence ;
|
66 |
if ( $timestamp < self:: $lastTimestamp ) {
|
67 |
throw new Excwption( "Clock moved backwards. Refusing to generate id for " .(self:: $lastTimestamp - $timestamp ). " milliseconds" );
|
69 |
self:: $lastTimestamp = $timestamp ;
|
70 |
echo 'logdebug->nextId()->self::$lastTimestamp3:' .self:: $lastTimestamp ;
|
73 |
echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):' .((sprintf( '%.0f' , $timestamp ) - sprintf( '%.0f' , self:: $twepoch ) ));
|
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 . '-----' ;
|
86 |
$Idwork = new Idwork(1);
|
87 |
$a = $Idwork ->nextId();
|
88 |
$Idwork = new Idwork(2);
|
89 |
$a = $Idwork ->nextId();
|