snowflake是一种分布是唯一id生成算法,简单而又强大。但其依赖实体主机作为标识,而导致了唯一id的组成部分中关于mechine的部分需要实体主机的标识符来映射对应的二进制数值才能正常提供服务(其算法的本意)。而本程序改进如下,借用redis的string类型的key来代替这部分`mechine部分二进制数值`,当一个snowflake唯一id生成器服务进程启动时,会先随机获取一个mechine_center_id:mechine_id(随机生成)的key(视为某主机集群下的某主机),即使用incr指令返回自增数seq,用作id中的seq部分的值。snowflake的强大在于,当且仅当mechine_center_id:mechine_id并且seq重复的情况下, 才可能产生重复的id,然而如果seq的二进制位数为14位,也就是一秒( 之所以说1秒而不用更小的单位,因为现在的timestamp只有32位,要支持id唯一生成服务的可扩展和可维护必须分配多余32位的二进制bit给timestamp部分保证在未来10或者20年内服务的正确行)内可以产生16383个id,当然可以增加seq部分的二进制位数来成倍增加sid/ps。但是更重要的是,如果当redis服务崩溃了(可以使用master/slave分布式集群减少这样的情况,但是维护成本也增加了),但是有补偿措施(比如将key备份到数据库,incr使用replace+last_insert_id()代替等待);当然当服务增长,seq也必须要跟着增长,才能保证服务的稳定和可用。
以上是主要思想,如下为一个简单实例:
<?php
namespace sequence;
use Exception;
//在二进制的是补码表示,所以只有当第一位为0时,得到的唯一id才是一个正整数
/**
* @author doraMi
*/
class sequence
{
const TIMESTAMP_OFFSET = 2199023255551; //41bit的最大时间戳
const SIGN_BITS = 1; //二进制符号位数
const TIMESTAMP_BITS = 41; //时间戳所占位数
const MECHINE_CENTER_BITS = 4; //机器集群所占位数
const MECHINE_BITS = 4; //机器节点所占位数
const SEQUENCE_BITS = 14; //自增序列所占位数
const SEQUENCE_MASK = 16383; //最大自然数
//表示开始bit位置offset
const OFFSET_SIGN = self::TIMESTAMP_BITS+self::MECHINE_CENTER_BITS+self::MECHINE_BITS+self::SEQUENCE_BITS;
const OFFSET_TIMESTAMP = self::MECHINE_CENTER_BITS + self::MECHINE_BITS + self::SEQUENCE_BITS;
const OFFSET_MECHINE_CENTER = self::MECHINE_BITS + self::SEQUENCE_BITS;
const OFFSET_MECHINE = self::SEQUENCE_BITS;
protected $sign; //标志位
protected $timestamp; //时间戳
protected $mechine_center_id; //机器集群id
protected $mechine_id; //机器id
protected $sequence_id; //自增数值
protected $max_mechine_id = -1 ^ (-1 << self::MECHINE_BITS);
protected $max_mechine_center_id = -1 ^ (-1 << self::MECHINE_CENTER_BITS);
public function __construct($sign, $timestamp, $mechine_center_id, $mechine_id, $sequence)
{
if(
$timestamp < 0
|| $mechine_center_id > $this->max_mechine_center_id
|| $mechine_id > $this->max_mechine_id
) {
throw new Exception('wrong params!');
}
$this->sign = $sign;
$this->timestamp = $timestamp;
$this->mechine_center_id = $mechine_center_id;
$this->mechine_id = $mechine_id;
$this->sequence_id = $sequence & self::SEQUENCE_MASK;
}
/**
* 生成一个唯一id
*/
public function getSequence()
{
return ($this->sign << self::OFFSET_SIGN)
| ($this->timestamp << self::OFFSET_TIMESTAMP)
| ($this->mechine_center_id << self::OFFSET_MECHINE_CENTER)
| ($this->mechine_id << self::OFFSET_MECHINE)
| ($this->sequence_id);
}
}