twitter snow flake 雪花算法

时间:2021-11-22 09:37:32

Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同。

Snowflake算法核心

时间戳工作机器id序列号组合在一起。

 

twitter snow flake 雪花算法

 

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



结构为:

0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---0000000000 00

在上面的字符串中,第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。

这样的好处是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。


**
 * ID 生成策略
 * 毫秒级时间41位+机器ID 10位+毫秒内序列12位。
 * 0           41     51     64
+-----------+------+------+
|time       |pc    |inc   |
+-----------+------+------+
 * 最高位bit标记为不可用
 *  前41bits是以微秒为单位的timestamp。
 *  接着10bits是事先配置好的机器ID。
 *  最后12bits是累加计数器。
 *  macheine id(10bits)标明最多只能有1024台机器同时产生ID,sequence number(12bits)也标明1台机器1ms中最多产生4096个ID,
 *
 */
class SnowFlake{
    private static $epoch = 1462264156000;


    public function createID($machineId){
        /*
        * Time - 41 bits
        */
        $time = floor(microtime(true) * 1000);


        /*
        * Substract custom epoch from current time
        */
        $time -= SnowFlake::$epoch;
        
        /*
        * flag number - 1 bits - can not change, beacause is shoule be a positive number
        */
        $suffix = 0;
        
        /*
        * Create a base and add time to it
        */
        $base = decbin(pow(2,40) - 1 + $time);
  //$base = sprintf("%041s", decbin($time));
        /*
        * Configured machine id - 10 bits - up to 512 machines
        */
        $machineid = decbin(pow(2,9) - 1 + $machineId);
//$machineid = sprintf("%010s", decbin($machineId));
        /*
        * sequence number - 12 bits - up to 2048 random numbers per machine
        */
        $random = mt_rand(1, pow(2,11)-1);
        $random = decbin(pow(2,11)-1 + $random);
//$random = mt_rand(1, pow(2, 12) - 1);
        //$random = sprintf("%012s", decbin($random));
        
        /*
        * 拼装$base
        */
        $base = $suffix.$base.$machineid.$random;
        /*
        * 讲二进制的base转换成long
        */
        $base = bindec($base);


        $id = sprintf('%.0f', $base);


        return $id;
    }
}


我这里的PHP代码序列号是随机产生的,因为我们的业务还不达不到需要有序生成的必要, 而且对于PHP来说要序列化生成必须把这个序列存储到缓存里面去。

详细代码可参考:https://github.com/twitter/snowflake