标识与唯一标识概览 @ 王延炯 · 观世界

ZooKeeper的强一致性，是由Paxos协议保证的；Consul的一致性，官方用subtle(微妙的)来形容。它既采用了Gossip管理集群Membership，也采用了Raft管理Service Catalog。Consul的写一致性通过Raft保证，但Consul的读一致性有三种模式，default / consistent / stale，其中consistent是强一致的。

在步长累计型生成算法中，最核心的就是保持一个累计值在整个集群中的「强一致性」。同时，这也会为唯一性标识的生成带来新的形成瓶颈。

基于服务内置生成

似乎对于分布式的ID生成，以Twitter Snowflake为代表的， Flake 系列算法，经常可以被搜索引擎找到，但似乎MongoDB的ObjectId算法，更早地采用了这种思路。MongoDB 1.0 是在2009年8月27日发布的，并且0.9.10(2009年8月24日发布)和1.0两个版本没有差异。

在StackOverflow上，最早的一个关于ObjectId的问题，时间是2010年1月27日。不知道Twitter的同学，是不是受此启发呢？

MongoDB ObjectId

12-byte MongoDB ObjectId 的结构是：

a 4-byte value representing the seconds since the Unix epoch,
a 3-byte machine identifier,
a 2-byte process id, and
a 3-byte counter, starting with a random value.

可以看出，这个方案所支持的最小划分粒度是「秒 * 进程实例」，单进程实例的每秒容量是 3-byte (24-bit)，也就是接近16777216个ID。

有兴趣的，还可以进一步看代码（MonogoDB 3.3.x Java Driver）研究：Timestamp, Machine Identifier、Process Identifier、计数器的初始值分别是如何获得的:

Timestamp

private static int dateToTimestampSeconds(final Date time) {
      return (int) (time.getTime() / 1000);
}

Machine Identifier

StringBuilder sb = new StringBuilder();
Enumeration<NetworkInterface> e = NetworkInterface.getNetworkInterfaces();
while (e.hasMoreElements()) {
    NetworkInterface ni = e.nextElement();
    sb.append(ni.toString());
    byte[] mac = ni.getHardwareAddress();
    if (mac != null) {
        ByteBuffer bb = ByteBuffer.wrap(mac);
        try {
            sb.append(bb.getChar());
            sb.append(bb.getChar());
            sb.append(bb.getChar());
        } catch (BufferUnderflowException shortHardwareAddressException) { //NOPMD
            // mac with less than 6 bytes. continue
        }
    }
}
machinePiece = sb.toString().hashCode();

Process ID

try {
    String processName = java.lang.management.ManagementFactory.getRuntimeMXBean().getName();
    if (processName.contains("@")) {
        processId = (short) Integer.parseInt(processName.substring(0, processName.indexOf('@')));
    } else {
        processId = (short) java.lang.management.ManagementFactory.getRuntimeMXBean().getName().hashCode();
    }

} catch (Throwable t) {
    processId = (short) new SecureRandom().nextInt();
    LOGGER.log(Level.WARNING, "Failed to get process identifier from JMX, using random number instead", t);
}

COUNTER

private static final AtomicInteger NEXT_COUNTER = new AtomicInteger(new SecureRandom().nextInt());

此处需要注意的是MongoDB的 NEXT_COUNTER 其初始值是一个随机数，这是有利于分库分表的。因为在小并发的条件下，非随机数的初始值，容易产生 偏库偏表，不均匀的现象。

Twitter Snowflake

Twitter在2010年6月1日（在Flickr那篇文章发布不到4个月之后），Ryan King 在Twitter的Blog 撰文写道：

Ticket Servers方案缺乏顺序的保证
考虑过采用UUID，不过128-bit太长了
也考虑过采用ZooKeeper的 Seq 所提供的 *Unique Naming* uence Nodes 所提供的 Unique Naming 特性，但是性能不能满足。(个人认为，Sequence Nodes的设计目标是解决分布式锁的问题，但不解决性能要求极高的ID生成问题，直接应用是一种Hack行为)

在这种情况下，Twitter给出了 64-bit 长的 Snowflake ，它的结构是：

1-bit reserved
41-bit timestamp
10-bit machine id
12-bit sequence

在过了不到4年，2014年的5月31日，Twitter 更新了 Snowflake 的 README，其中陈述了两个容易被忽视的事实:

"We have retired the initial release of Snowflake ..."
"... heavily relies on existing infrastructure at Twitter to run. "

可以看出，这个方案所支持的最小划分粒度是「毫秒 * 线程」，单线程（Snowflake 里对应的概念是 Worker）的每秒容量是12-bit，也就是接近4096。

翻一下Snowflake的归档代码 (Scala)，可以看到：

关于初始化Sequence的处理

if (lastTimestamp == timestamp) {
  sequence = (sequence + 1) & sequenceMask
  if (sequence == 0) {
    timestamp = tilNextMillis(lastTimestamp)
  }
} else {
  sequence = 0
}

可以看到此处Snowflake对于 sequence``的赋值为 ``0。

关于每秒超过4096个ID生成请求的处理

protected def tilNextMillis(lastTimestamp: Long): Long = {
  var timestamp = timeGen()
  while (timestamp <= lastTimestamp) {
    timestamp = timeGen()
  }
  timestamp
}

protected def timeGen(): Long = System.currentTimeMillis()

noeqd

2011年11月23日，用Go语言实现的，基于Snowflake的 neoqd 出现了。

它的特点是，除了使用Go语言进行了实现，更是把ID生成做成了一个网络服务。支持客户端向ID生成服务申请ID。它还支持：

简单预共享Token的客户端身份证认证（只是加强了那么一点点的安全性，可以忽略）
支持批量获取ID，最多256个（因为使用一个byte表示申请个数）

同时，作者还建议使用 Doozerd 一个用Go语言写的 -- a highly-available, completely consistent store for small amounts of extremely important data. 进行Machine ID的分配。

(关于 ZooKeeper / Etcd / Consul / Doozerd 的比较，也是可以期待下)

Boundary Flake

2012年1月， Boundary Flake 同样的，用Erlang语言把Snowflake，变成了一个网络服务，提供128-bit长的ID生成服务。

不过，根据其RoadMap的描述，这个项目并没100%完成。例如，批量的ID生成，HTTP 接口，客户端Library都列在里面待实现。

CruftFlake

2012年7月， CruftFlake 更显然的，是想以一个PHP变种身份出现。

它在结构上与Snowflake基本一致，存在两个区别：

在timestamp上的取值略有区别
可以自行决定是否采用ZooKeeper作为协调器

LableOrg/java-uniqueid

2014年7月18日，LableOrg 写了一个通过ZooKeeper进行协调的，128-bit长的算法 java-uniqueid。其结构组成依然十分相似：

Timestamp
Sequence counter
Generator IDs
Cluster IDs

前台浏览器生成

这里的前台，主要是指以「浏览器」为代表的客户端。

2015年2月16日，Sudhanshu Yadav (看面相像印度人)，用Javascript写了Flake的又一个变种实现 FlakeId 。其核心代码是：

if (this.lastTime == time) {
    this.seq++;

    if (this.seq > 4095) {
        this.seq = 0;

        //make system wait till time is been shifted by one milisecond
        while (Date.now() <= time) {};
    }
} else {
    this.seq = 0;
}

它的Machine Identifier则是作为构造函数的选项参数 options.mid 传入。

function FlakeId(options) {
  options = options || {};
  this.seq = 0;
  this.mid = (options.mid || 1) % 1023;
  this.timeOffset = options.timeOffset || 0;
  this.lastTime = 0;
}

全自主随机生成

可以说，成熟的、全自主生成方案，可能只有 128-bit UUID 一种，具体的说，是UUID Version 4。另外，微软对它实现，称之为 GUID 。

一般的，使用的最多的是UUID Version 4，很大程度上是因为其依赖的其他服务最少。

这里，通过python (2.5+) 对UUID的实现，体验一下UUID的生成效果：

$ python
Python 2.7.12 (default, Jun 29 2016, 14:05:02)
[GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import uuid
>>> uuid.uuid1()
UUID('d17c4397-830d-11e6-b62d-985aeb899615')
>>> uuid.uuid3(uuid.NAMESPACE_DNS, 'yanjiong.wang')
UUID('363053e8-e02d-3b9d-b18b-83da99d5a684')
>>> uuid.uuid4()
UUID('59cfe861-a6b1-45ff-9522-2e780adf491a')
>>> uuid.uuid5(uuid.NAMESPACE_DNS, 'yanjiong.wang')
UUID('25d4e194-0404-5c64-8695-c547f98ccde1')

另外，我们看一下网卡的MAC地址

$ ifconfig
lo0: flags=8049<UP,LOOPBACK,RUNNING,MULTICAST> mtu 16384
      options=1203<RXCSUM,TXCSUM,TXSTATUS,SW_TIMESTAMP>
      inet 127.0.0.1 netmask 0xff000000
      inet6 ::1 prefixlen 128
      inet6 fe80::1%lo0 prefixlen 64 scopeid 0x1
      nd6 options=201<PERFORMNUD,DAD>
gif0: flags=8010<POINTOPOINT,MULTICAST> mtu 1280
stf0: flags=0<> mtu 1280
en1: flags=8863<UP,BROADCAST,SMART,RUNNING,SIMPLEX,MULTICAST> mtu 1500
      ether 98:5a:eb:89:96:15
      inet6 fe80::8d7:fea6:2ec2:ea55%en1 prefixlen 64 secured scopeid 0x4
      inet 10.0.3.22 netmask 0xffffff00 broadcast 10.0.3.255
      nd6 options=201<PERFORMNUD,DAD>
      media: autoselect
      status: active

(因为UUID Version 1会泄露网卡的MAC地址，所以我对MAC地址做了下小手术)

可以看到UUID Version 1 最后一组数值 985aeb899615 与网卡的 MAC地址是一样一样的 98:5a:eb:89:96:15。

个人一直认为，采用UUID Version 4是一种偷懒的，缺乏必要设计的做法。

一方面，它是依据概率确保无碰撞的，计算的过程与概率上的「生日问题」是一样的，不再展开。

另一方面，从使用的角度，UUID还有以下缺点：

太长，即便是转换成36个字符，不利于输入
过于随机，没有规律，在开发调试、线上故障定位，都容易看花眼。
如果作为数据库主键，对索引不利。

小结

人工生成的标识，在相同的命名空间里，需要后续唯一性验证才能保证唯一
由计算机生成，在低并发的场景下，适合通过一个服务集中生成，并保障此服务的高可用性
由计算机生成，在高并发的场景下，适合通过一个保障命名空间独立的命名规范下，由多个服务并行生成。
采用步长和增长相结合的生成算法，本质上都是对某个状态进行累积的结果。
对于取模进行分库分表的场景，初始化值随机有利于均匀分布。
（MongoDB 的 ObjectId 更是Flake系列算法的鼻祖，并在初始值上进行了随机化处理）

设计一个「合适」的标识

区分实体和关系

实体是点，而关系是线。

一般而言，面向实体的标识生成速度，要小于面向关系的生成速度。

具体的例子，以电商为例：买家、卖家、商品这些实体的录入速度，要远比订单生成小的多。也因此，主数据要比交易数据稳定的多。

并且，关系还可能包含层次关系，进而体现为一个依赖树。

面向实体的标识

面向实体的标识，更多的与概念相关（名称）、与形态相关（型号），有很多的人为因素参与，随机因素有限，命名的主体也来自于人。

对于实体制造，为任意一个产品进行标识，大致会分为六个方面：品牌、品类、品名，型号、批号、产品序列号。

对于前四者，更多的是人为的进行命名。

例如，给定中文，找到对应英文，再进行缩写。

对于批号，则会增加一些时间因素，以关联到产品的生产时间。

例如，采用20160925表示具体某一天，或者采用201640表示具体某一周。（一般来说，同一个批号的产品，所使用的原材料是也是同一批。）

对于产品序列号，最简单的是采用自然数法进行编号。

这一类的标识，在分布式系统下，在系统并发量小，集群规模小的情况下，可以采用基于数据库或者协调器的生成方案。

面向关系的标识

自然的，关系源于两个或两个以上的实体之间所进行的某一个活动，并且具有一定的时效性。

常见的关系的表现形式有：交易流水号，会话标识等等。

这一类的标识，在分布式系统下，在系统并发量大，应当采用基于服务的内置生成方案。唯一依赖的是在实例部署时、启动前，为期分配唯一的Machine Identifier。这个Machine Identifier可以交由以强一致性保证的协调器完成。

当然，在系统并发量小的情况下，任然可以采用基于数据库的生成方案，因为没有协调器集群的参与，系统整体的复杂度更低，更利于维护。

标识的容量

任何采用文字所表达的标识，最终在计算机里，都会根据一定的格式，被转换为字节byte进行处理，这个过程称之为「序列化」。这种序列化方式，本质上是一种编码方式。

变长编码

一般来说，采用变长的编码方式，主要的目的是为了应对不可预期大小的信息量。

常见的有 TLV(Type-Length-Value) 方式。 Google的 Protocol Buffers 非常有意思地采用了 Base 128 Varints 的编码方式。

本质上，一个 URI 也是对一个标识，它可以标识一个功能，也可以标识一个虚拟实体。

RESTful是对此类命名方式的一种实践方式，也是对 URI和HTTP协议组合之后，「表征力」的一个深入挖掘。

定长编码

在回顾一下前文所提到的IPv4地址，它似乎、可能、或许会在2019年完全枯竭，因为它只有32-bit。相比之下，MAC地址有48-bit，IPv6有128-bit。即便是它们都没那么容易枯竭，但也不代表由于人为因素，导致无法有效使用。

再回想下，每个人的身份证、手机号码，都是采用定长的形式进行编码。

选择定长有利于预先分配计算机资源，不管是内存、文件系统，还是数据库。同时，对于人的心理来说，可预期性大大增强了。

标识的命名空间

命名空间有三个层面：

异构切分：对于不同的场景和视角，以树形进行层次划分。
同构切分：对于异构切分的结果，切分出不同的分片。
时间切分：对于同一个分片，在不同时间点上的状态。

一般地：

首先，采用并行无状态的生成算法，一般都采用时间作为首要的命名空间，并且此命名空间的实效性小于生成者的重启时间
其次，采用生成器实例自身的标识作为次要命名空间，以保证各个生成器的时间即便是不同步也不会产生重复标识

同时，需要注意的是，这可能导致唯一标识产生，大段跳跃，原因有：

单位时间的并发量远小于子命名空间的容量
生成器重启

标识的冗余

不管标识是在运行时的内存出现，还是记录到数据库中或者文件里，它都需要占用硬件资源。

还是拿身份证举例，一方面，一个18个字符长度的身份证，那么需要18个字节进行存储。18个字节意味着144-bit，比IPv6的128bit还长。

如果简单的标识全世界每个人，以目前全地球60亿人口的总量，那么33个bit就足够了。

采用这种冗余设计的原因，一方面是「半集中，半自主」和现实的行政、地域结构对齐，另一方面是实现关联信息的集成。

小结

标识编码后的长度，则决定了一个标识方案的整体容量。
在一个统一的命名空间内，有多个标识生成者并行生成时，需要划分独立的子命名空间，以保证生成的标识在整个命名空间内唯一。
单个命名空间的标识，承载的信息量有限，在标识的使用过程中，需要扩展与包含一些其他视角的信息以进行冗余。

标识的文本兼容

和人工取名字不一样，自动生成ID的主体，是计算机本身，但使用这个ID的主体，有两个：人和计算机。

对于计算机，最擅长处理的是结构化数组、条形码或者二维码；而对人，最擅长使用的是文本、图形或者视频。

一般而言，在大量的RESTful设计的应用，其URI中会包含大量的ID，用来标识用户、商品、订单等等，它们经常会出现在URI中。

以ASCII编码为基础的各种文本化编码算法，从Base16开始，正常的有Base32，Base64，Base58，Base85等等，不太正常的，在本文最后的扩展阅读里有列举。

其中，Base16是最为「字节友好」的，因为不需要进行任何Padding操作，就可以以把 4-bit/half-byte 转换为 [0-9a-f] 这十六个字符，因此Base16还有别名：Hex。另外对于键盘输入，这16个英文字母，又是相对纯数字之外，最方便的。

而Base32, Base64等等，都需要Padding。因为Base32是每 5-bit 进行分组编码，Base64则是 6-bit ，都无法直接对齐一个 byte(8-bit)。

另外，Base16还对 URI 友好，不需要进行任何的 URLEncode/Decode操作。

以64-bit长的ID为例，它既可以转化为 long，也可以Base16成为16个字符的``HexString``，同时它大小写不敏感。

相比之下，如果采用Base64的文本化方案，其长度虽然少了5个字符，为11个，但其大小写敏感，不利于人机交互的输入，还会包含URI不友好，还会被转义为「 %3D」的符号「=」。

一个精巧的标识文本化算法，并不应该简单的把一个二进制值转为HexString。在日志里，应该有相应的解码算法，解析出符合人类阅读的字符，比如：精确到秒、且带格式时间，生成改标识的主体，等等。

标识的安全性

标识的信息泄露

采用连续，或者固定步长的标识，容易从一个标识猜测其他标识的存在性。

常见的例子有： * 通过局域网扫描工具，扫描某个子网的活动的IP地址 * 通过端口扫描工具，扫描一个目标主机开放的端口，以初步确定主机操作系统类型

另外，在物联网领域，如果采用的EPC编码，那么很容易通过连续编码，估计某个产品的具体产量。

标识的自校验能力

还是使用身份证号这个例子，根据国家标准（GB11643-1999），身份证号的前17位为本体码，最后1位为校验码。也就是说，它是通过前17位进行数学公式计算之后获得，主要目的是用于检验录入过程是否产生差错。

这样设计的好处是，每当输入完18位身份证号后，可以直接判断一个身份证号，是否在逻辑上是「合规的」，对于系统而言不用查询数据库，可以减少IO操作。不过，这不代表这个身份证号是有效的，也有可能是一个无效，但符合校验规则的身份证号。

由于标识的长度有限，能够加入的冗余信息较少，一般的基于公钥密码体制的签名机制，都难以在一个短标识中嵌入。

扩展阅读

更新历史

2016-11-02 13:34, 更新基于协调器生成的内容

目录

标识与唯一标识概览