引言

SnowFlake 算法，是 Twitter 开源的分布式 id 生成算法。其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛，且ID 引入了时间戳，基本上保持自增的。

这个算法的好处很简单可以在每秒产生约400W个不同的16位数字ID(10进制)。

参考文献

twitter的snowflake： https://github.com/twitter-archive/snowflake

原理

snowflake算法的核心原理是把一个64位的整数分为3个部分，如下图：
image

构成说明

ID由64bit组成，其中 第一个bit空缺

  • 41bit用于存放毫秒级时间戳
  • 10bit用于存放机器id
  • 12bit用于存放自增ID

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id

如图所示，高端的第一位不使用，接着的41位字节用于存储毫秒级的时间戳，紧跟着时间戳的10位作为机器ID，而最后12位为序列号。
对于不同的机器来说，可以为每一台机器分配一个唯一的机器ID，这样就可以保证每台机器锁生成的ID不会重复。
对于同一台机器，如果同一时刻多个客户端并发请求，那么可以通过增加序列号来保证ID唯一性。

PHP实现snowflake雪花算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
abstract class Particle {    
    const EPOCH = 1479533469598;    
    const max12bit = 4095;    
    const max41bit = 1099511627775;    
    static $machineId = null;    
    public static function machineId($mId) {    
        self::$machineId = $mId;    
    }    
    public static function generateParticle() {    
        /*    
        * Time - 42 bits    
        */    
        $time = floor(microtime(true) * 1000);    
        /*    
        * Substract custom epoch from current time    
        */    
        $time -= self::EPOCH;    
        /*    
        * Create a base and add time to it    
        */    
        $base = decbin(self::max41bit + $time);    
        /*    
        * Configured machine id - 10 bits - up to 1024 machines    
        */    
        $machineid = str_pad(decbin(self::$machineId), 10, "0", STR_PAD_LEFT);    
        /*    
        * sequence number - 12 bits - up to 4096 random numbers per machine    
        */    
        $random = str_pad(decbin(mt_rand(0, self::max12bit)), 12, "0", STR_PAD_LEFT);    
        /*    
        * Pack    
        */    
        $base = $base.$machineid.$random;    
        /*    
        * Return unique time id no    
        */    
        return bindec($base);    
    }    
    public static function timeFromParticle($particle) {    
        /*    
        * Return time    
        */    
        return bindec(substr(decbin($particle),0,41)) - self::max41bit + self::EPOCH;    
    }    
}
1
2
3
4
5
6
7
$machineID = 0; // Machine ID (aka Server ID no.)
Particle::generateParticle($machineID);

## 输出示例
5190075640165958205
5190075733132707771
5190075762421530692