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

简介

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 位。

gRPC 服务

我们可以将 Snowflake 做成一个 RPC 服务，提供给不同的项目调用，这里我写了一个简单的 gRPC 的例子，用 Golang 写的服务端（截止本文撰写日，PHP 还不支持写 gRPC 服务，只能写客户端），PHP 写的客户端

https://github.com/YianAndCode/snowflake-grpc