如何实现一个64 bit ID Unique Generator
如何实现一个64 bit ID Unique Generator
Requirements
- 要求ID唯一但非自增长
- 高性能，节点/实例可以扩展 (Scability)
- 节点/实例重启后可以接着分配ID (Durability)
Scability 的考虑
要求可以多实例扩展，那就需要每个实例需要有唯一的Identity来参与生成 ID 的分段。
如果这个实例是无状态实例，那么这个实例被scale in 之后，该 identity 分段的ID 也不能就此废弃，等新的实例被scale out 出来后，需要重复利用这个分段的ID.
为什么不能使用有状态的实例, 使用实例自身状态的identity 来做分段呢？ 例如 POD-0, POD-1 之类的就用 0，1 之类的来标识分段。 因为这样的话，假如 0 标识的这个分段用完了，那 POD-0 就不能再 分配ID 了。
而如果无状态的POD, 而 Identity 是从其他地方获取的，和自身无关，那么这个identity 用完了，可以申请获取新的identity，然后又可以重新分配新的段的ID 了。
这里可以使用zookeeper 来分配 instance 的 identity.
Durability
当实例或者说pod 重启之后，client 重新申请ID 时，可以被分配到没有被使用的ID 或者是接着之前用的ID 段的新ID.
那就需要将这部分的已经分配了哪些 ID 的 信息/状态 保持到数据库中，以实现持久化。
实现
ID 的结构如下，其中每个worker 可用的位数是 40 bit, 如果按照1000 tps 来算，每个实例可以使用 34 年。计算公式如下 (2^40 -1 )/1000/31536000 = 34 years.
+--------+-----------+----------------+----------------------------------------+
| 63 | 62 - 56 | 55 - 40 | 39 - 0 |
+--------+-----------+----------------+----------------------------------------+
| sign | zone id | worker id | sequence |
| 1 bit | 7 bits | 16 bits | 40 bits |
+--------+-----------+----------------+----------------------------------------+sign：最高位（第63位），表示符号位（一般为0表示正数）。zone id：接下来的7位（62到56），代表逻辑区域或机房。worker id：16位（55到40），代表节点/实例/POD的 ID。sequence：剩下的40位（39到0），表示这个段内可用的 ID。这个ID Generator 的实现可以是一个lib，也可以是一个service.
以lib 的实现方式为例子, 需要提供一个接口来分配ID.
public long next();lib 也需要连接 zookeeper 去获取worker ID, 去 数据库 存放 当前这个worker ID 最大已经分配到那个ID 了。
还需要一些配置来定义是属于那个business 的, 以便在 zookeeper 创建对于的 属于这个 business 的 worker 节点。 例如 /idg/business-1/worker-- 这种znode.
而 parent znode /idg/business-1 是持久化的，而子节点 worker-N 这种节点就是 临时节点。 在parent 节点上的value 上持久化worker ID 和 instance/POD 的mapping关系。 例如
{"workerId2Node":{"2":"/idg/business-1/_w_-144807203059138568-0000000002","3":"/idg/business-1/_w_-144807203059138569-0000000003","0":"/idg/business-1/_w_-144807472447553536-0000000004","1":"/idg/business-1/_w_-144807472447553537-0000000005"}}
这样当POD 连接到zk 的时候，就可以通过子节点的名字就可以知道自己有没有已经分配到 worker ID 了，如果没有就新创建一个。 如果有，则可以通过读取worker-N 的这种临时节点的内容去获取worker ID.
另外一个问题是，假如一个pod 断开很久，临时节点已经消失了，那重新连接上ZK，那么之前旧的worker id mapping信息依然存在于parent 节点，但是其实际对应的临时节点已经消失了。 这个时候就可以重新读取parent 节点下所有的子节点list，然后比较parent节点的value来去掉value 中已经不存在的mapping信息对，并且排序查看那个worker ID对应的mapping 信息被去掉了，那就重新使用这个已经不存在mapping信息的 worker ID 来关联本session. 这样就可以达到复用 worker ID 的目标了。
另外一个就是lib 可以在申请ID 时，可以一段一段地申请。 例如一次申请1000 个ID 来允许 next() 接口使用。
当 next() 接口使用的ID 已经不够 500 了，就触发异步线程获取另外 1000 个ID 来备用。