雪花算法原理介绍及基于php的雪花算法(snowflake)

shawsun 2020-06-21

原理介绍(摘自极客时间):

Snowflake的核心思想是将64bit的二进制数字分成若干部分,每一部分都存储有特定含义的数据,比如说时间戳、机器ID、序列号等等,最终生成全局唯一的有序ID。它的标准算法是这样的:

雪花算法原理介绍及基于php的雪花算法(snowflake)

从上面这张图中我们可以看到,41位的时间戳大概可以支撑pow(2,41)/1000/60/60/24/365年,约等于69年,对于一个系统是足够了。

如果你的系统部署在多个机房,那么10位的机器ID可以继续划分为2~3位的IDC标示(可以支撑4个或者8个IDC机房)和7~8位的机器ID(支持128-256台机器);12位的序列号代表着每个节点每毫秒最多可以生成4096的ID。

不同公司也会依据自身业务的特点对Snowflake算法做一些改造,比如说减少序列号的位数增加机器ID的位数以支持单IDC更多的机器,也可以在其中加入业务ID字段来区分不同的业务。比方说我现在使用的发号器的组成规则就是:1位兼容位恒为0 + 41位时间信息 + 6位IDC信息(支持64个IDC)+ 6位业务信息(支持64个业务)+ 10位自增信息(每毫秒支持1024个号)

我选择这个组成规则,主要是因为我在单机房只部署一个发号器的节点,并且使用KeepAlive保证可用性。业务信息指的是项目中哪个业务模块使用,比如用户模块生成的ID,内容模块生成的ID,把它加入进来,一是希望不同业务发出来的ID可以不同,二是因为在出现问题时可以反解ID,知道是哪一个业务发出来的ID。

那么了解了Snowflake算法的原理之后,我们如何把它工程化,来为业务生成全局唯一的ID呢?一般来说我们会有两种算法的实现方式:

一种是嵌入到业务代码里,也就是分布在业务服务器中。这种方案的好处是业务代码在使用的时候不需要跨网络调用,性能上会好一些,但是就需要更多的机器ID位数来支持更多的业务服务器。另外,由于业务服务器的数量很多,我们很难保证机器ID的唯一性,所以就需要引入ZooKeeper等分布式一致性组件来保证每次机器重启时都能获得唯一的机器ID。

另外一个部署方式是作为独立的服务部署,这也就是我们常说的发号器服务。业务在使用发号器的时候就需要多一次的网络调用,但是内网的调用对于性能的损耗有限,却可以减少机器ID的位数,如果发号器以主备方式部署,同时运行的只有一个发号器,那么机器ID可以省略,这样可以留更多的位数给最后的自增信息位。即使需要机器ID,因为发号器部署实例数有限,那么就可以把机器ID写在发号器的配置文件里,这样即可以保证机器ID唯一性,也无需引入第三方组件了。微博和美图都是使用独立服务的方式来部署发号器的,性能上单实例单CPU可以达到两万每秒。

Snowflake算法设计的非常简单且巧妙,性能上也足够高效,同时也能够生成具有全局唯一性、单调递增性和有业务含义的ID,但是它也有一些缺点,其中最大的缺点就是它依赖于系统的时间戳,一旦系统时间不准,就有可能生成重复的ID。所以如果我们发现系统时钟不准,就可以让发号器暂时拒绝发号,直到时钟准确为止。

另外,如果请求发号器的QPS不高,比如说发号器每毫秒只发一个ID,就会造成生成ID的末位永远是1,那么在分库分表时如果使用ID作为分区键就会造成库表分配的不均匀。这一点,也是我在实际项目中踩过的坑,而解决办法主要有两个:

1.时间戳不记录毫秒而是记录秒,这样在一个时间区间里可以多发出几个号,避免出现分库分表时数据分配不均。

2.生成的序列号的起始号可以做一下随机,这一秒是21,下一秒是30,这样就会尽量的均衡了。

我在开头提到,自己的实际项目中采用的是变种的Snowflake算法,也就是说对Snowflake算法进行了一定的改造,从上面的内容中你可以看出,这些改造:一是要让算法中的ID生成规则符合自己业务的特点;二是为了解决诸如时间回拨等问题。

其实,大厂除了采取Snowflake算法之外,还会选用一些其他的方案,比如滴滴和美团都有提出基于数据库生成ID的方案。这些方法根植于公司的业务,同样能解决分布式环境下ID全局唯一性的问题。对你而言,可以多角度了解不同的方法,这样能够寻找到更适合自己业务目前场景的解决方案,不过我想说的是,方案不在多,而在精,方案没有最好,只有最适合,真正弄懂方法背后的原理,并将它落地,才是你最佳的选择。

第一种:

简介:

最高位是符号位,始终为0,不可用。
41位的时间序列,精确到毫秒级,41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。
10位的机器标识,10位的长度最多支持部署1024个节点。
12位的计数序列号,序列号即一系列的自增id,可以支持同一节点同一毫秒生成多个ID序号,12位的计数序列号支持每个节点每毫秒产生4096个ID序号。
看的出来,这个算法很简洁也很简单,但依旧是一个很好的ID生成策略。其中,10位器标识符一般是5位IDC+5位machine编号,唯一确定一台机器。

<?php
class lib_snowflake
{
    const TWEPOCH = 1488834974657; // 时间起始标记点,作为基准,一般取系统的最近时间(一旦确定不能变动)
 
    const WORKER_ID_BITS     = 5; // 机器标识位数
    const DATACENTER_ID_BITS = 5; // 数据中心标识位数
    const SEQUENCE_BITS      = 11; // 毫秒内自增位
 
    private $workerId; // 工作机器ID(0~31)
    private $datacenterId; // 数据中心ID(0~31)
    private $sequence; // 毫秒内序列(0~4095)
 
    private $maxWorkerId     = -1 ^ (-1 << self::WORKER_ID_BITS); // 机器ID最大值31
    private $maxDatacenterId = -1 ^ (-1 << self::DATACENTER_ID_BITS); // 数据中心ID最大值31
 
    private $workerIdShift      = self::SEQUENCE_BITS; // 机器ID偏左移11位
    private $datacenterIdShift  = self::SEQUENCE_BITS + self::WORKER_ID_BITS; // 数据中心ID左移16位
    private $timestampLeftShift = self::SEQUENCE_BITS + self::WORKER_ID_BITS + self::DATACENTER_ID_BITS; // 时间毫秒左移21位
    private $sequenceMask       = -1 ^ (-1 << self::SEQUENCE_BITS); // 生成序列的掩码4095
 
    private $lastTimestamp = -1; // 上次生产id时间戳
 
    public function __construct($workerId, $datacenterId, $sequence = 0)
    {
        if ($workerId > $this->maxWorkerId || $workerId < 0) {
            throw new Exception("worker Id can‘t be greater than {$this->maxWorkerId} or less than 0");
        }
 
        if ($datacenterId > $this->maxDatacenterId || $datacenterId < 0) {
            throw new Exception("datacenter Id can‘t be greater than {$this->maxDatacenterId} or less than 0");
        }
 
        $this->workerId     = $workerId;
        $this->datacenterId = $datacenterId;
        $this->sequence     = $sequence;
    }
 
    public function nextId()
    {
        $timestamp = $this->timeGen();
 
        if ($timestamp < $this->lastTimestamp) {
            $diffTimestamp = bcsub($this->lastTimestamp, $timestamp);
            throw new Exception("Clock moved backwards.  Refusing to generate id for {$diffTimestamp} milliseconds");
        }
 
        if ($this->lastTimestamp == $timestamp) {
            $this->sequence = ($this->sequence + 1) & $this->sequenceMask;
 
            if (0 == $this->sequence) {
                $timestamp = $this->tilNextMillis($this->lastTimestamp);
            }
        } else {
            $this->sequence = 0;
        }
 
        $this->lastTimestamp = $timestamp;
 
        $gmpTimestamp    = gmp_init($this->leftShift(bcsub($timestamp, self::TWEPOCH), $this->timestampLeftShift));
        $gmpDatacenterId = gmp_init($this->leftShift($this->datacenterId, $this->datacenterIdShift));
        $gmpWorkerId     = gmp_init($this->leftShift($this->workerId, $this->workerIdShift));
        $gmpSequence     = gmp_init($this->sequence);
        return gmp_strval(gmp_or(gmp_or(gmp_or($gmpTimestamp, $gmpDatacenterId), $gmpWorkerId), $gmpSequence));
    }
 
    protected function tilNextMillis($lastTimestamp)
    {
        $timestamp = $this->timeGen();
        while ($timestamp <= $lastTimestamp) {
            $timestamp = $this->timeGen();
        }
 
        return $timestamp;
    }
 
    protected function timeGen()
    {
        return floor(microtime(true) * 1000);
    }
 
    // 左移 <<
    protected function leftShift($a, $b)
    {
        return bcmul($a, bcpow(2, $b));
    }
}

第二种:

<?php
class SnowFlake
{
    const TWEPOCH = 1288834974657; // 时间起始标记点,作为基准,一般取系统的最近时间(一旦确定不能变动)
 
    const WORKER_ID_BITS     = 5; // 机器标识位数
    const DATACENTER_ID_BITS = 5; // 数据中心标识位数
    const SEQUENCE_BITS      = 12; // 毫秒内自增位
 
    private $workerId; // 工作机器ID
    private $datacenterId; // 数据中心ID
    private $sequence; // 毫秒内序列
 
    private $maxWorkerId     = -1 ^ (-1 << self::WORKER_ID_BITS); // 机器ID最大值
    private $maxDatacenterId = -1 ^ (-1 << self::DATACENTER_ID_BITS); // 数据中心ID最大值
 
    private $workerIdShift      = self::SEQUENCE_BITS; // 机器ID偏左移位数
    private $datacenterIdShift  = self::SEQUENCE_BITS + self::WORKER_ID_BITS; // 数据中心ID左移位数
    private $timestampLeftShift = self::SEQUENCE_BITS + self::WORKER_ID_BITS + self::DATACENTER_ID_BITS; // 时间毫秒左移位数
    private $sequenceMask       = -1 ^ (-1 << self::SEQUENCE_BITS); // 生成序列的掩码
 
    private $lastTimestamp = -1; // 上次生产id时间戳
 
    public function __construct($workerId, $datacenterId, $sequence = 0)
    {
        if ($workerId > $this->maxWorkerId || $workerId < 0) {
            throw new Exception("worker Id can‘t be greater than {$this->maxWorkerId} or less than 0");
        }
 
        if ($datacenterId > $this->maxDatacenterId || $datacenterId < 0) {
            throw new Exception("datacenter Id can‘t be greater than {$this->maxDatacenterId} or less than 0");
        }
 
        $this->workerId     = $workerId;
        $this->datacenterId = $datacenterId;
        $this->sequence     = $sequence;
    }
 
    public function nextId()
    {
        $timestamp = $this->timeGen();
 
        if ($timestamp < $this->lastTimestamp) {
            $diffTimestamp = bcsub($this->lastTimestamp, $timestamp);
            throw new Exception("Clock moved backwards.  Refusing to generate id for {$diffTimestamp} milliseconds");
        }
 
        if ($this->lastTimestamp == $timestamp) {
            $this->sequence = ($this->sequence + 1) & $this->sequenceMask;
 
            if (0 == $this->sequence) {
                $timestamp = $this->tilNextMillis($this->lastTimestamp);
            }
        } else {
            $this->sequence = 0;
        }
 
        $this->lastTimestamp = $timestamp;
 
        /*$gmpTimestamp    = gmp_init($this->leftShift(bcsub($timestamp, self::TWEPOCH), $this->timestampLeftShift));
        $gmpDatacenterId = gmp_init($this->leftShift($this->datacenterId, $this->datacenterIdShift));
        $gmpWorkerId     = gmp_init($this->leftShift($this->workerId, $this->workerIdShift));
        $gmpSequence     = gmp_init($this->sequence);
        return gmp_strval(gmp_or(gmp_or(gmp_or($gmpTimestamp, $gmpDatacenterId), $gmpWorkerId), $gmpSequence));*/
 
        return (($timestamp - self::TWEPOCH) << $this->timestampLeftShift) |
        ($this->datacenterId << $this->datacenterIdShift) |
        ($this->workerId << $this->workerIdShift) |
        $this->sequence;
    }
 
    protected function tilNextMillis($lastTimestamp)
    {
        $timestamp = $this->timeGen();
        while ($timestamp <= $lastTimestamp) {
            $timestamp = $this->timeGen();
        }
 
        return $timestamp;
    }
 
    protected function timeGen()
    {
        return floor(microtime(true) * 1000);
    }
 
    // 左移 <<
    protected function leftShift($a, $b)
    {
        return bcmul($a, bcpow(2, $b));
    }
}

相关推荐

优化算法 / 0评论 2020-11-13