初识SnowFlake

snowflake算法所生成的ID结构是什么样子呢？我们来看看下图：

SnowFlake所生成的ID一共分成四部分：
1.第一位
占用1bit，其值始终是0，没有实际作用。
2.时间戳
占用41bit，精确到毫秒，总共可以容纳约69年的时间。
3.工作机器id
占用10bit，其中高位5bit是数据中心ID（datacenterId），低位5bit是工作节点ID（workerId），做多可以容纳1024个节点。
4.序列号
占用12bit，这个值在同一毫秒同一节点上从0开始不断累加，最多可以累加到4095。

SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢？只需要做一个简单的乘法：

同一毫秒的ID数量 = 1024 X 4096 = 4194304

这个数字在绝大多数并发场景下都是够用的。
SnowFlake算法的优点：

1.生成ID时不依赖于DB，完全在内存生成，高性能高可用。

2.ID呈趋势递增，后续插入索引树的时候性能较好。

SnowFlake算法的缺点：

依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成ID冲突，或者ID乱序。
php代码实现如下：

<?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);
    }
}

$snowFlake = new SnowFlake(1, 1);
echo $snowFlake->generateID();