发号器的常用解决方案及应用

什么是发号器

发号器，通常被叫做ID生成器，是为业务元素生成唯一标示的一组方法或功能。

常见使用场景

通过发号器生成的ID特点

  • ID位数可定制
  • 支持多IDC部署
  • 单机或多机粗略有序
  • 增长步长不固定
  • 可反解
  • 可制造

常用发号器的实现方式

实现发号器，有几种思路

  • 数据库自增id
  • UUID
  • Snowflake服务
  • Flicker的发号器方案

前两种比较常见，下边着重梳理后边两种，这两种方案的实现涉及到一些二进制的存储、运算和转换，用习惯了高级编程语言，二进制运算可能都还给老师了，在看下边之前可以先回顾下二进制相关知识。

Snowflake服务

Snowflake服务生成的ID由四部分二进制编码组成:

  • 最高位是符号位，始终为0
  • 41位的时间序列（精确到毫秒，41位的长度可以使用69年，1970年～2039年）
  • 10位的机器标识（10位的长度最多支持部署1024个节点）
  • 12位的计数顺序号（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）

分别获取每部分的值并转为二进制:

  • 符号位：0 -> 0
  • 时间：1470126882000 -> 10101011001001010011000111111110011010000
  • 机器码：102 -> 1100110
  • 随机码：2289 -> 100011110001

最终获得ID: 770769882710436081

Flicker的发号器方案

首先创建一个数据库表:

CREATE TABLE Tickets64 (
    id bigint(20) unsigned NOT NULL auto_increment,
    stub char(1) NOT NULL default '',
    PRIMARY KEY  (id),
    UNIQUE KEY stub (stub)
) ENGINE=MyISAM;

在应用中，把如下sql放到一个事务里提交，就能拿到不断增长且不重复的ID了：

REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();

如上，只是在单台数据库上生成ID，从高可用角度考虑，接下来就要解决单点故障问题: Flicker启用了两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。 在应用中，轮训两台数据库服务器就可以了。

发号器的PHP实现

方案一

<?php
/**
 * Long ID Generator
 * 
 * 生成长id，比如订单id、帖子id
 * 
 * @author 小黑
 * 
 * 特点：
 * 参照Snowflake service from Twitter。
 * id粗略有序。
 * 可反解。
 * 时间相关。
 * 可制造。
 * 不能保证绝对唯一，但重复的几率微乎其微，在可容忍范围内。
 * 多机器部署灵活、方便。
 * 
 * 四部分组成：
 * 最高位是符号位，始终为0
 * 41位的时间序列(精确到毫秒，41位的长度可以使用69年)
 * 10位的机器标识(包括数据中心5位 + 机器编号5位)（10位的长度最多支持部署1024个节点)
 * 12位的毫秒内随机数（理论上12位支持每个节点每毫秒产生4096个ID序号)
 * 
 * 缺点：
 * 毫秒内产生相同随机数会造成重复，虽然几率很小！因为id一般作为主键，写DB时如果有重复会写入失败，
 * 建议因为id重复写表失败的，重新生成新id重试写表一次（为了防止死循环，建议只重试一次，重试失败即抛错)。
 */
class Api_Longid
{
    // ID开始时间(毫秒) 2015-06-15 00:00:00
    const INIT_TIME = 1434297600000;
    
    //const time_bits       = 41;
    const datacenter_bits = 5;
    const machine_bits    = 5;
    const sequence_bits   = 12;
    
    /**
     * 生成ID
     * @author 小黑
     * 
     * @param  int $machine 机器编号
     * @param  int $datacenter IDC编号
     * @return int
     */
    public static function generate($machine, $datacenter = 0)
    {
        if ($machine - intval($machine) != 0 || $datacenter - intval($datacenter) != 0)
        {
            return false;
        }
        
        $datacenter_max = -1 ^ (-1 << self::datacenter_bits);
        $machine_max    = -1 ^ (-1 << self::machine_bits);
        if ($machine < 0 || $machine > $machine_max
            || $datacenter < 0 || $datacenter > $datacenter_max)
        {
            return false;
        }
        
        $time_shift       = self::sequence_bits + self::machine_bits + self::datacenter_bits;
        $datacenter_shift = self::sequence_bits + self::machine_bits;
        $machine_shift    = self::sequence_bits;
        $sequence_max     = -1 ^ (-1 << self::sequence_bits);
        
        $time = floor(microtime(true) * 1000);
        
        $long_id = (($time - self::INIT_TIME) << $time_shift)
                    | ($datacenter << $datacenter_shift)
                    | ($machine << $machine_shift)
                    | mt_rand(0, $sequence_max);
        
        Api_Log::id_generate_log('long', $long_id, $time);

        return $long_id;
    }
    
    /**
     * 根据ID，反解获得时间
     * @author 小黑
     * 
     * @param  int $id
     * @return int
     */
    public static function get_time($id)
    {
        return ($id >> self::sequence_bits + self::machine_bits + self::datacenter_bits) + self::INIT_TIME;
    }
    
    /**
     * 根据ID，反解获得IDC编号
     * @author 小黑
     * 
     * @param  int $id
     * @return int
     */
    public static function get_datacenter($id)
    {
        $shift = self::sequence_bits + self::machine_bits + self::datacenter_bits;
        return (($id >> $shift << $shift ^ $id) >> self::sequence_bits + self::machine_bits);
    }
    
    /**
     * 根据ID，反解获得机器编号
     * @author 小黑
     * 
     * @param  int $id
     * @return int
     */
    public static function get_machine($id)
    {
        $shift = self::sequence_bits + self::machine_bits;
        return (($id >> $shift << $shift ^ $id) >> self::sequence_bits);
    }
    
}

方案二

<?php
/**
 * User ID Generator
 * 
 * 生成用户id
 * 
 * @author 小黑
 * 
 * 特点：
 * id存储长度不超过32bit，以无符号int类型存储。
 * id表现长度为8~10位。
 * 支持扩展到8台机器。
 * id自增，步长随机。
 * 单机有序。
 * 可反解。
 * 时间不相关。
 * 不可制造。
 * 绝对唯一。
 * 多机器部署，需要多个数据库表支持，一机一表，一一对应。
 * 
 * 三部分组成：
 * 1. msyql自增id：占19~27bit，单机支持(133,890,046 = 134217727 - 327681)个id
 * 2. 随机数：占2bit，相邻两个id的自增步长随机
 * 3. 机器编号：占3bit，支持扩展到8台机器
 * 
 * 单机取值范围：
 * 最小值：1010000000000000001-00-001          (10485793)
 * 最大值：111111111111111111111111111-00-001  (4294967265)
 * 说明：1010000000000000001为最小值，是为了保证10进制id最短8位
 * 
 * id自增表：
 * CREATE TABLE generate_uid_x (
 *     id int(10) unsigned NOT NULL auto_increment,
 *     stub char(1) NOT NULL default '',
 *     PRIMARY KEY  (id),
 *     UNIQUE KEY stub (stub)
 * ) ENGINE=MyISAM DEFAULT CHARSET=utf8;
 * 
 * SQL：
 * REPLACE INTO generate_uid_x (stub) VALUES ('a');
 * SELECT LAST_INSERT_ID();
 * 
 * 扩展性：
 * 假如id超过上限，只需修改用户id存储字段的数据类型为long型。
 */
class Api_Uid
{
    // ID基数
    const UID_BASE_NUM = 327680;
    
    //const mysqlid_bits = 27;
    const random_bits  = 2;
    const machine_bits = 3;
    
    /**
     * 生成ID
     * @author 小黑
     * 
     * @param  int $type    用户类型 （1.普通 2.会员）
     * @param  int $machine 机器编号 （0-7）
     * @return int
     */
    public static function generate($type, $machine = 0)
    {
        if ($type - intval($type) != 0 || $machine - intval($machine) != 0)
        {
            return false;
        }
        
        $machine_max = -1 ^ (-1 << self::machine_bits);
        if ($machine < 0 || $machine > $machine_max)
        {
            return false;
        }
        
        if ($type == 1)
        {
            $table = 'generate_uid_' . $machine;
            $log_type = 'user';
        }
        elseif ($type == 2)
        {
            $table = 'generate_did_' . $machine;
            $log_type = 'doctor';
        }
        else
        {
            return false;
        }
        
        $sql = 'replace into ' . $table . " (stub) values ('a')";
        $query = DB::query(Database::INSERT, $sql);
        list($insert_id, $affect) = $query -> execute();
        if (! is_numeric($insert_id) || $insert_id < 1)
        {
            return false;
        }
        
        $mysqlid_shift = self::random_bits + self::machine_bits;
        $random_shift  = self::machine_bits;
        $random_max    = -1 ^ (-1 << self::random_bits);
        
        $uid = (self::UID_BASE_NUM + $insert_id) << $mysqlid_shift
                | mt_rand(0, $random_max) << $random_shift
                | $machine;
        
        Api_Log::id_generate_log($log_type, $uid, $insert_id);
        
        return $uid;
    }
    
    /**
     * 根据ID，反解获得数据库自增ID
     * @author 小黑
     * 
     * @param  int $uid
     * @return int
     */
    public static function get_mysqlid($uid)
    {
        return ($uid >> self::random_bits + self::machine_bits) - self::UID_BASE_NUM;
    }

    /**
     * 根据ID，反解获得机器编号
     * @author 小黑
     *
     * @param  int $uid
     * @return int
     */
    public static function get_machine($uid)
    {
        return $uid >> self::machine_bits << self::machine_bits ^ $uid;
    }
    
}