Varobj

2019-08-19

雪花算法 - PHP版本(基于信号量)的实现



雪花算法在上一篇文章中实现了一个简单的,在单机并发 1k 左右能保证生成 ID 的唯一性,但是如果单机要求生成 ID 的数量更高,甚至每秒达到上万请求时,之前的方法在多进程的情况会出现大量的重复 ID ,因为上篇实现的雪花算法的随机码,分布在最低 12 位,也就是 4096 种可能,用随机数生成,当冲突时,无法及时发现并纠正,所以多进程中使用,且并发大于预期的 1K 的情况下,算法就基本失效了。上文分析过,雪花算法的主要在于,分布式唯一 ID 的发生冲突的可能性,被机器ID 分割成各个独立单机的冲突问题解决上,只要解决了单机不同进程/线程生成 ID 的冲突问题,就解决了整个分布式唯一 ID 生成的问题。那么多个进程如何生成唯一 ID 呢?这种问题一般可以用锁来解决,比如有个变量 a,每个进程只有先获取变量 a的锁,才能对 a 进行累加。

锁的方式,常见的有文件锁Redis 锁、或者内存实现加锁。由于生成雪花算法的特殊性,就是要求同一毫秒时间内保证随机码不同,所以超过一毫秒后才获取锁也没有意义,所以文件锁有 IO 限制、Redis 锁有 Socket 通信限制,在此处都不适用。鸟哥的 yac 内存缓存速度很快,但是无锁的内存结构,每个进程都可以同时对同一个 key 进行读写操作,所以也不能用。最终选择使用 PHPsysvshm(共享内存)和sysvsem (信号量)扩展来完成多进程加锁并获取累加计数,然后生成唯一的累加 ID 。这两个扩展不是 PHP 默认的,需要编译安装时,参数加上 --enable-sysvshm, --enable-sysvsem

具体使用文档参见 PHP 官网文档,下面列举将要使用的函数:

创建并打开一个共享内存段

key 必须整形,一般使用 ftok(__FILE__, 'p') 生成;

shm_attach ($key, $memsize = null, $perm = 0666);

共享内存中获取值,添加值

shm_get_var ($shm_identifier, $variable_key);
shm_put_var ($shm_identifier, $variable_key, $variable);

获取信号量ID

sem_get ($key, $max_acquire = 1, $perm = 0666, $auto_release = 1);

请求信号量(获取锁)

sem_acquire ($sem_identifier, $nowait = false);

示例代码


// 多进程获取每毫秒数的唯一ID(每次累加) 经测试,1h1g 服务器,每毫秒生成平均大约 50-60 个,也就是每秒能生成5、6万个ID
function getMuxUid(int $timestamp)
{
    $key = ftok(__FILE__, 'p');
    // 先获取 100kb 的共享内存段
    $shmKey = shm_attach($key, 102400);
    // 保存当前累计计数,方便统计使用多少次,然后删除共享内存,防止内存满了
    shm_put_var($shmKey, 1, (@shm_get_var($shmKey, 1) ?: 0) + 1);
    // 获取信号量ID
    $semKey = sem_get($key);
    // 加锁:请求信号量ID,其他进程默认会阻塞
    if (sem_acquire($semKey)) {
        // 当前毫秒的key 是否有值,否则为 1
        if (shm_has_var($shmKey, $timestamp)) {
            $id = shm_get_var($shmKey, $timestamp);
            $id++;
        } else {
            $id = 1;
        }
        // 更新当前毫秒的key
        shm_put_var($shmKey, $timestamp, $id);
        if (shm_get_var($shmKey, 1) > 1000) {
            // 大于1000次就删除共享内存
            shm_remove($shmKey);
        } else {
            shm_detach($shmKey);
        }
        return $id;
    }
    return 0;
}

只需要把之前算法中的 randId 替换成 getMuxUid() 即可

具体代码

function genUUID(int $workId = 0, array $options = [])
{
    $workId < 0 and $workId = 0;
    // 高中低三部分占位
    $hw = 42;
    $cw = 12;
    $lw = 10;
    // 偏移时间戳,默认0,hw 为生成毫秒数
    $offset = 0;
    !empty($options['hw']) and $hw = (int)$options['hw'];
    !empty($options['cw']) and $cw = (int)$options['cw'];
    !empty($options['lw']) and $lw = (int)$options['lw'];
    if ($hw + $cw + $lw !== 64) {
        throw new \RuntimeException('配置有误');
    }
    // 毫秒时间戳占据高位,
    $timestamp = microtime(true) * 1000;
    // 假设当前时间,偏移量为0时不可用了
    // $timestamp = strtotime('2039-09-08') * 1000;
    $timestamp = (int)$timestamp - $offset;
    if ($timestamp > 2 ** 41) {
        throw new \RuntimeException(sprintf('恭喜,代码从[%s]起,运行了[69]年+', date('Y-m-d', strtotime($offset)) ?: ''));
    }
    // 低位随机码
    try {
        $randId = (random_int(0, 2 ** $lw) * getmypid()) % (2 ** $lw);
    } catch (\Exception $e) {
        $randId = 100;
    }
    return ($timestamp << ($cw + $lw)) | ($workId << $lw) | $randId;
}