Snowflake —— 分布式全局唯一 id 生成算法

栏目: 后端 · 发布时间: 6年前

内容简介：Snowflake 是 Twitter 提出一种的分布式唯一序列号生成算法，理论上单节点 1 毫秒可以生成 4096 个（每秒四百万个）唯一序列，这个序列是个Snowflake 算法生成的序列号充分地利用了每一个比特位，需要占用第一部分只有一位，固定为

简介

Snowflake 是 Twitter 提出一种的分布式唯一序列号生成算法，理论上单节点 1 毫秒可以生成 4096 个（每秒四百万个）唯一序列，这个序列是个 long 类型的数字，在数据库中的存储和查询也非常高效。其原理很简单，却又很精妙。

原理

Snowflake 算法生成的序列号充分地利用了每一个比特位，需要占用 8bytes ( 64bits ) 空间，这 64 个 bit 一共分成 4 部分：

0         | 00000000000000000000000000000000000000000 | 0000000000    | 000000000000
定值，1 位 | 时间戳（毫秒），41 位                        | 节点序号，10 位 | 自增序列，12 位

第一部分只有一位，固定为 0 ，可以理解成是有符号长整型的正数；

第二部分占 41 位，用来存生成该序列号时的时间戳（毫秒），默认情况下可以用到 2039-09-07 23:47:35；

第三部分占 10 位，是机器节点 id，取值范围为 0~1023(2^10-1) ，即最大支持 1024 个计算节点；

第四部分占 12 位，自增序列，每生成一个序列号之后循环自增，取值范围是 0~4095(2^12-1)

算法就是这么简单

实现

实现起来也非常简单，这里给一个 PHP 的例子：

<?php

class Snowflake
{
    // 41 位、10 位、 12 位的最大值，作为掩码使用
    const MAX41BITS = 2199023255551;
    const MAX10BITS = 1023;
    const MAX12BITS = 4095;

    private $nodeId;

    private $seq;

    public function __construct($nodeId)
    {
        $this->nodeId = $nodeId;
        $this->seq = 0;
    }

    public function next()
    {
        // 获取当前时间戳（毫秒）
        list($microsec, $sec) = explode(" ", microtime());
        $timestamp = $sec * 1000 + (int)($microsec * 1000);

        // 生成 id
        // 这里用到了位运算，稍微解释一下：
        // 先将时间戳与 41 位的最大值做一次与运算，保证其长度不会超过 41 位；
        // 再将节点号跟 10 位的最大值做与运算，也是保证其长度不会超过 10 位；
        // 然后将时间戳左移 22 位、节点号左移 12 位，这样就能使得时间戳在第 2 位到第 42 位、节点号在第 43 位到第 52 位；
        // 最后再对时间戳、节点号、自增序列做一次或运算，这样三个数字就拼接在一起了
        $id = ($timestamp & self::MAX41BITS) << 22 | ($this->nodeId & self::MAX10BITS) << 12 | $this->seq;

        // id 生成好之后将自增序列加 1 同时与 12 位的最大值做与运算，这样就能达到循环滚动的效果
        $this->seq = (++$this->seq) & self::MAX12BITS;

        return $id;
    }

    public function parse($id)
    {
        $timestamp = ($id >> 22);
        $nodeId = ($id >> 12) & self::MAX10BITS;
        $seq = $id & self::MAX12BITS;
        return [$timestamp, $nodeId, $seq];
    }
}


// 测试一下
$snowflake = new Snowflake(1);
for ($i = 0; $i < 1000; $i++)
{
    $id = $snowflake->next();
    echo $id . "  ";
    list($timestamp, $nodeId, $seq) = $snowflake->parse($id);
    echo $timestamp . " " . $nodeId . " " . $seq . PHP_EOL;
}

在我的机器上（MacBook Pro 2017 13inch i5/8G），一毫秒大概能生成 40 个左右 id，只达到了理论值一毫秒 4096 个的百分之一，所以不用担心并发太大会导致生成了重复的 id（还没有用完 4096 个自增序列，时间位就已经加一啦），而且，在更大并发的情况下，相信你也不会只用一个计算节点来抗~

改进

上面介绍的是 Snowflake 的常规版本，因为非常简单，所以在实际项目中，我们可以根据业务来做一些改进，这里举几个改进点

时间戳

前面说到，时间戳位默认情况下可以用到 2039-09-07 23:47:35 ，这是因为我们是从 1970-01-01 08:00:00 (UTC+8) 作为时间原点的，而从 UNIX 时间零点到我们的项目上线这里有个四十多年的时间，因此我们可以设置一个新的时间零点，使得算法可以用更长时间。

例如我们可以新增一个 纪元常量 ，可以取新项目上线第一天的 0:00

const EPOCH = 1535731200000; // 2018-09-01 0:00:00.000

那么在 next() 里的位运算前，我们就需要将时间戳做一次减法：

$timestamp -= self::EPOCH;

同样的，在 parse() 里需要将 self::EPOCH 加回去。只要保证同一个项目（或者同一个团队）用同一个“时间零点”，就能够将 id 还原出原有的信息

节点位、自增序列位

在实际项目中，我们往往不会/不需要部署 1024 个那么多的 snowflake 服务，所以我们可以将节点位由 10 位改成 5 位（最大支持 32 个节点）甚至是 4 位（最大支持 16 个节点），这样就能多出来 5~6 位，可以拿来做什么呢？

可以存储一些业务信息，比如说 user_id 、 order_id 等等都是用 snowflake 来生成的时候，我们可以将多出来的那几位作为一个 业务编号位 ，通过这样改进之后，一个 id 携带的信息就多了一些，拿到一个 id 之后也可以判断出这个 id 是什么业务的，数据库查询的时候就能知道该查哪张表。

同样的，自增序列位也可以按需缩减到 11 位或者是 10 位。