Twitter 的 snowflake 在分布式生成唯一 UUID 应用还是蛮广泛的，基于 snowflake 的一些变种的算法网上也有不少。使用 snowflake 生成 UUID 很多都是在分布式场景下使用，我看了下网上有其中有几篇 PHP 实现的都没有考虑到线程安全，现在 PHP 有了 Swoole 的锁和协程的加持，对于我们开发线程安全和高并发模拟还是很方便的，这里用 PHP 结合 Swoole 来学习下实现最简单的 snowflake。

先来看以下 snowflake 的结构：

生成的数值是 64 位，分成 4 个部分：

第一个 bit 为符号位，最高位为 0 表示正数

第二部分 41 个 bit 用于记录生成 ID 时候的时间戳，单位为毫秒，所以该部分表示的数值范围为 2^41 - 1（69 年），它是相对于某一时间的偏移量

第三部分的 10 个 bit 表示工作节点的 ID，表示数值范围为 2^10 - 1，相当于支持 1024 个节点

第四部分 12 个 bit 表示每个工作节点没毫秒生成的循环自增 id，最多可以生成 2^12 -1 个 id，超出归零等待下一毫秒重新自增。

1. <?php 
2.  
3. class Snowflake 
4. { 
5.   const EPOCH = 1543223810238;  // 起始时间戳，毫秒 
6.  
7.   const SEQUENCE_BITS = 12;  //序号部分12位 
8.   const SEQUENCE_MAX = -1 ^ (-1 << self::SEQUENCE_BITS); // 序号最大值 
9.  
10.   const WORKER_BITS = 10; // 节点部分10位 
11.   const WORKER_MAX = -1 ^ (-1 << self::WORKER_BITS); // 节点最大数值 
12.  
13.   const TIME_SHIFT = self::WORKER_BITS + self::SEQUENCE_BITS; // 时间戳部分左偏移量 
14.   const WORKER_SHIFT = self::SEQUENCE_BITS;  // 节点部分左偏移量 
15.  
16.   protected $timestamp;  // 上次ID生成时间戳 
17.   protected $workerId;  // 节点ID 
18.   protected $sequence;  // 序号 
19.   protected $lock;    // Swoole 互斥锁 
20.  
21.   public function __construct($workerId) 
22.   { 
23.     if ($workerId < 0 || $workerId > self::WORKER_MAX) { 
24.       trigger_error("Worker ID 超出范围"); 
25.       exit(0); 
26.     } 
27.  
28.     $this->timestamp = 0; 
29.     $this->workerId = $workerId; 
30.     $this->sequence = 0; 
31.     $this->lock = new swoole_lock(SWOOLE_MUTEX); 
32.   } 
33.  
34.   /** 
35.    * 生成ID 
36.    * @return int 
37.    */ 
38.   public function getId() 
39.   { 
40.     $this->lock->lock();  // 这里一定要记得加锁 
41.     $now = $this->now(); 
42.     if ($this->timestamp == $now) { 
43.       $this->sequence++; 
44.  
45.       if ($this->sequence > self::SEQUENCE_MAX) { 
46.         // 当前毫秒内生成的序号已经超出最大范围，等待下一毫秒重新生成 
47.         while ($now <= $this->timestamp) { 
48.           $now = $this->now(); 
49.         } 
50.       } 
51.     } else { 
52.       $this->sequence = 0; 
53.     } 
54.  
55.     $this->timestamp = $now;  // 更新ID生时间戳 
56.  
57.     $id = (($now - self::EPOCH) << self::TIME_SHIFT) | ($this->workerId << self::WORKER_SHIFT) | $this->sequence; 
58.     $this->lock->unlock(); //解锁 
59.  
60.     return $id; 
61.   } 
62.  
63.   /** 
64.    * 获取当前毫秒 
65.    * @return string 
66.    */ 
67.   public function now() 
68.   { 
69.     return sprintf("%.0f", microtime(true) * 1000); 
70.   } 
71.  
72. } 

其实逻辑并不复杂，解释一下代码中的位运算：

-1 ^ (-1 << self::SEQUENCE_BITS)

就是-1的二进制表示为1的补码,其实等同于 :

2**self::SEQUENCE_BITS - 1

最后部分左移后或运算：

(($now - self::EPOCH) << self::TIME_SHIFT) | ($this->workerId << self::WORKER_SHIFT) | $this->sequence;

这里主要是对除了第一位符号位以外的三个部分进行左移相应的偏移量使其归位，并通过或运算重新整合成上面 snowflake 的结构，比如我们用 3 部分 4 位来演示一下该归并操作:

0000 0000 0010  --左移0位--> 0000 0000 0010

0000 0000 0100  --左移4位--> 0000 0100 0000 --或操作-->1000 0100 0010

0000 0000 1000  --左移8位--> 1000 0000 0000

Tags: Snowflake PHP唯一ID

分享到：