分布式自增ID解决方案研究

原创
2013/04/08 22:00
阅读数 4.5K

分布式ID生成方案(分布式数据库) 背景:在互联网应用中,应用需要为每一个用户分配一个id,在使用分布式数据库情况下,已经不能依靠自增主键来生成唯一性id了。。。

根据特定算法生成唯一ID 可重现的id生成方案:使用用户提供的特定的数据源(登录凭证),通过某种算法生成id,这个过程是可重现的,只要用户提供的数据源是唯一的,那么生成的id也是唯一的。 例如通过用户注册的email+salt,使用摘要算法(md5/sha)生成128bit的数据,然后通过混合因子转变为一个long类型的数据是64bit,有264 个可用数据,理论上冲突几率极低,优点:可用保证id固定的,每次通过email登录,直接能得到id,不需要访问数据库查询id。

不可重现的方案: 使用每个服务器环境中的如下参数:

  1. 服务器网卡MAC地址/IP地址(确保服务器之间不冲突)
  2. 每个生成ID的程序的唯一编号(确保同一服务器上的不同服务之间不冲突)
  3. 程序每次启动的唯一编号(确保程序的每次启停之间不冲突)
  4. 启动后内存里的序列号/系统当前时间(确保程序的一次运行期内不冲突)

以及其他的参数,混合生成id,保证多台服务器、多个线程生成的id不冲突。

例如:

UUID.randomUUID().toString() 生成的是length=32的16进制格式的字符串,如果回退为byte数组共16个byte元素,即UUID是一个128bit长的数字,一般用16进制表示。算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成UUID。从理论上讲,如果一台机器每秒产生10000000个GUID,则可以保证(概率意义上)3240年不重复

例如:Instagram 的ID生成策略链接地址是http://www.cnblogs.com/yjl49/archive/2012/04/16/2452210.html(OSCHINA的编辑器不太会用...)

Twitter的 Snowflake---一个使用Apache ZooKeeper来整合所有节点然后生成64bit唯一ID的简洁的服务 PHP版本(自己写的水平有限)

<?php class Idwork { public $workerId; static $twepoch = 1361810367218;//1361810367218 2013 2 26 0:40 static $sequence = 0; const workerIdBits = 4; static $maxWorkerId = 15; const sequenceBits = 10; static $workerIdShift = 10; static $timestampLeftShift = 12; static $sequenceMask = 1023; private $lastTimestamp = -1; private $timestramp; public function __construct($workId){ if($workId > self::$maxWorkerId || $workId< 0 ) { throw new Exception("worker Id can't be greater than 15 or less than 0"); } $this->workerId=$workId; echo 'logdebug->__construct()->self::$workerId:'.$this->workerId; echo '</br>'; } private function timeGen(){ //获得当前时间戳 $time = explode(' ', microtime()); $time2= substr($time[0], 2, 3); $timestramp = $time[1].$time2; echo 'logdebug->timeGen()->$timestramp:'.$timestramp; echo '</br>'; return $timestramp; } function tilNextMillis($lastTimestamp) { $timestamp = $this->timeGen(); echo 'logdebug->tilNextMillis()-> <= 111'; echo '</br>'; while ($this->timestamp <= $lastTimestamp) { $this->timestamp = $this->timeGen(); } echo 'logdebug->tilNextMillis()->$timestamp:'.$this->timestamp; echo '</br>'; return $this->timestamp; } function nextId() { $this->timestamp=$this->timeGen(); echo 'logdebug->nextId()->self::$lastTimestamp1:'.$this->lastTimestamp; echo '</br>'; if($this->lastTimestamp == $this->timestamp) { self::$sequence = (self::$sequence + 1) & self::$sequenceMask; if (self::$sequence == 0) { echo "###########".self::$sequenceMask; $this->timestamp = $this->tilNextMillis($this->lastTimestamp); echo 'logdebug->nextId()->self::$lastTimestamp2:'.$this->lastTimestamp; echo '</br>'; } } else { self::$sequence = 0; echo 'logdebug->nextId()->self::$sequence:'.self::$sequence; echo '</br>'; } if ($this->timestamp < $this->lastTimestamp) { throw new Excwption("Clock moved backwards. Refusing to generate id for ".($this->lastTimestamp-$this->timestamp)." milliseconds"); } $this->lastTimestamp = $this->timestamp; echo 'logdebug->nextId()->self::$lastTimestamp3:'.$this->lastTimestamp; echo '</br>'; echo 'logdebug->nextId()->(($timestamp - self::$twepoch )):'.((sprintf('%.0f', $this->timestamp) - sprintf('%.0f', self::$twepoch) )); echo '</br>'; echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):'.((sprintf('%.0f', $this->timestamp) - sprintf('%.0f', self::$twepoch)<< self::$timestampLeftShift )); echo '</br>'; echo $tmp1 = $this->timestamp-self::$twepoch; echo '--'; echo $tmp1 << self::$timestampLeftShift; $nextId = ($tmp1 << self::$timestampLeftShift ) | ( $this->workerId << self::$workerIdShift ) | self::$sequence; echo 'timestamp:'.$this->timestamp.'-----'; echo 'twepoch:'.sprintf('%.0f', self::$twepoch).'-----'; echo 'timestampLeftShift ='.self::$timestampLeftShift.'-----'; echo 'nextId:'.$nextId.'----'; echo 'workId:'.$this->workerId.'-----'; echo 'workerIdShift:'.self::$workerIdShift.'-----'; echo 'sequence:'.self::$sequence.'-----'; return $nextId; } } $Idwork1 = new Idwork(1); $Idwork2 = new Idwork(3); $a= $Idwork1->nextId(); $a= $Idwork1->nextId(); $a2= $Idwork2->nextId(); ?>

Twitter的 Snowflake JAVA实现方案 是由(时间+应用的workId+应用的内存的sequence)生成 public class IdWorker { private final long workerId; private final static long twepoch = 1288834974657L; private long sequence = 0L; private final static long workerIdBits = 4L; public final static long maxWorkerId = -1L ^ -1L << workerIdBits; private final static long sequenceBits = 10L;

private final static long workerIdShift = sequenceBits;
private final static long timestampLeftShift = sequenceBits + workerIdBits;
public final static long sequenceMask = -1L ^ -1L << sequenceBits;

private long lastTimestamp = -1L;

public IdWorker(final long workerId) {
	super();
	if (workerId > this.maxWorkerId || workerId < 0) {
		throw new IllegalArgumentException(String.format(
				"worker Id can't be greater than %d or less than 0",
				this.maxWorkerId));
	}
	this.workerId = workerId;
}

public synchronized long nextId() {
	long timestamp = this.timeGen();
	if (this.lastTimestamp == timestamp) {
		this.sequence = (this.sequence + 1) & this.sequenceMask;
		if (this.sequence == 0) {
			System.out.println("###########" + sequenceMask);
			timestamp = this.tilNextMillis(this.lastTimestamp);
		}
	} else {
		this.sequence = 0;
	}
	if (timestamp < this.lastTimestamp) {
		try {
			throw new Exception(
					String.format(
							"Clock moved backwards.  Refusing to generate id for %d milliseconds",
							this.lastTimestamp - timestamp));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	this.lastTimestamp = timestamp;
	long nextId = ((timestamp - twepoch << timestampLeftShift))
			| (this.workerId << this.workerIdShift) | (this.sequence);
	System.out.println("timestamp:" + timestamp + ",timestampLeftShift:"
			+ timestampLeftShift + ",nextId:" + nextId + ",workerId:"
			+ workerId + ",sequence:" + sequence);
	return nextId;
}

private long tilNextMillis(final long lastTimestamp) {
	long timestamp = this.timeGen();
	while (timestamp <= lastTimestamp) {
		timestamp = this.timeGen();
	}
	return timestamp;
}

private long timeGen() {
	return System.currentTimeMillis();
}


public static void main(String[] args){
	IdWorker worker2 = new IdWorker(2);
	System.out.println(worker2.nextId());
}

}

展开阅读全文
打赏
0
20 收藏
分享
加载中
PHP 版的生成结果,重复有点严重。。。
2015/09/04 15:50
回复
举报
更多评论
打赏
1 评论
20 收藏
0
分享
返回顶部
顶部