分布式系统中我们一般会对一些数据量大的业务进行拆分，如:订单表，用户表。因为数据量巨大一张表无法承载。就会对其进行分库分表。
但一旦涉及到分库分表，就会引申出分布式系统中唯一主键ID的生成问题，永不迁移数据和避免热点的文章中要求需要唯一ID的特性。

分布式id生成算法的有很多种，Twitter的SnowFlake就是其中经典的一种。

概述

SnowFlake算法(简称雪花算法)生成64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：

• 1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0

• 41位，用来记录时间戳（毫秒）。

  • 41位可以表示$2^{41}-1$个数字，
  • 如果只用来表示正整数（计算机中正数包含0），可以表示的数值范围是：0 至 $2^{41}-1$，减1是因为可表示的数值范围是从0开始算的，而不是1。
  • 也就是说41位可以表示$2^{41}-1$个毫秒的值，转化成单位年则是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年

• 10位，用来记录工作机器id。

  • 可以部署在$2^{10} = 1024$个节点，包括5位datacenterId和5位workerId
  • 5位（bit）可以表示的最大正整数是$2^{5}-1 = 31$，即可以用0、1、2、3、....31这32个数字，来表示不同的datecenterId或workerId

• 12位，序列号，用来记录同毫秒内产生的不同id。

  • 12位（bit）可以表示的最大正整数是$2^{12}-1 = 4095$，即可以用0、1、2、3、....4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号

优点

1、此方案每秒能够产生409.6万个ID，性能快
2、时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增
3、灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求

缺点

1、依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成

SnowFlake可以保证：

所有生成的id按时间趋势递增
整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）

代码实现(PHP)

/**
 * SnowFlake ID Generator
 * Based on Twitter Snowflake to generate unique ID across multiple
 * datacenters and databases without having duplicates.
 *
 *
 * SnowFlake Layout
 *
 * 1 sign bit -- 0 is positive, 1 is negative
 * 41 bits -- milliseconds since epoch
 * 5 bits -- dataCenter ID
 * 5 bits -- machine ID
 * 12 bits -- sequence number
 *
 * Total 64 bit integer/string
 */

class SnowFlake
{
    /**
     * Offset from Unix Epoch
     * Unix Epoch : January 1 1970 00:00:00 GMT
     * Epoch Offset : January 1 2000 00:00:00 GMT
     */
    const EPOCH_OFFSET = 1483200000000;
    const SIGN_BITS = 1;
    const TIMESTAMP_BITS = 41;
    const DATACENTER_BITS = 5;
    const MACHINE_ID_BITS = 5;
    const SEQUENCE_BITS = 12;

    /**
     * @var mixed
     */
    protected $datacenter_id;

    /**
     * @var mixed
     */
    protected $machine_id;

    /**
     * @var null|int
     */
    protected $lastTimestamp = null;

    /**
     * @var int
     */
    protected $sequence = 1;
    protected $signLeftShift = self::TIMESTAMP_BITS + self::DATACENTER_BITS + self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    protected $timestampLeftShift = self::DATACENTER_BITS + self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    protected $dataCenterLeftShift = self::MACHINE_ID_BITS + self::SEQUENCE_BITS;
    protected $machineLeftShift = self::SEQUENCE_BITS;
    protected $maxSequenceId = -1 ^ (-1 << self::SEQUENCE_BITS);
    protected $maxMachineId = -1 ^ (-1 << self::MACHINE_ID_BITS);
    protected $maxDataCenterId = -1 ^ (-1 << self::DATACENTER_BITS);

    /**
     * Constructor to set required paremeters
     *
     * @param mixed $dataCenter_id Unique ID for datacenter (if multiple locations are used)
     * @param mixed $machine_id Unique ID for machine (if multiple machines are used)
     * @throws \Exception
     */
    public function __construct($dataCenter_id, $machine_id)
    {
        if ($dataCenter_id > $this->maxDataCenterId) {
            throw new \Exception('dataCenter id should between 0 and ' . $this->maxDataCenterId);
        }
        if ($machine_id > $this->maxMachineId) {
            throw new \Exception('machine id should between 0 and ' . $this->maxMachineId);
        }
        $this->datacenter_id = $dataCenter_id;
        $this->machine_id = $machine_id;
    }

    /**
     * Generate an unique ID based on SnowFlake
     * @return string
     * @throws \Exception
     */
    public function generateID()
    {
        $sign = 0; // default 0
        $timestamp = $this->getUnixTimestamp();
        if ($timestamp < $this->lastTimestamp) {
            throw new \Exception('"Clock moved backwards!');
        }
        if ($timestamp == $this->lastTimestamp) { //与上次时间戳相等，需要生成序列号
            $sequence = ++$this->sequence;
            if ($sequence == $this->maxSequenceId) { //如果序列号超限，则需要重新获取时间
                $timestamp = $this->getUnixTimestamp();
                while ($timestamp <= $this->lastTimestamp) {
                    $timestamp = $this->getUnixTimestamp();
                }
                $this->sequence = 0;
                $sequence = ++$this->sequence;
            }
        } else {
            $this->sequence = 0;
            $sequence = ++$this->sequence;
        }
        $this->lastTimestamp = $timestamp;
        $time = (int)($timestamp - self::EPOCH_OFFSET);
        $id = ($sign << $this->signLeftShift) | ($time << $this->timestampLeftShift) | ($this->datacenter_id << $this->dataCenterLeftShift) | ($this->machine_id << $this->machineLeftShift) | $sequence;
        return (string)$id;
    }

    /**
     * Get UNIX timestamp in microseconds
     *
     * @return int  Timestamp in microseconds
     */
    private function getUnixTimestamp()
    {
        return floor(microtime(true) * 1000);
    }
}