UUID，她有什么作用呢? uuidw

今天聊点不一样的东西，有点不起眼却很重要的小玩意：UUID (或是微软的 GUID)。

不管在什么系统中，资料最终都要写入到储存装置中，不论是用 RDBMS、 NoSQL，或是直接写入档案，都需要一个 ID 识别，以便事后需要时能取回单一笔资料，为了避免衝突 (多笔资料使用同一 ID)，怎么产生唯一的 ID？

学资料库时可能会学到

(1) 用在现实社会中唯一的 ID (例如：身份证字号或是 email)，这类的方法比较适合用来辨别使用者，对于更大层级的资料量 (订单、讯息) 就不适合了；

(2) 使用 RDBMS 提供的 auto increment primary key，比较简单方便，而且产生的结果可以用来排序。

没错，能排序在资料库应用中很重要，想象一下，若做一个 IM 系统，每次开啟都取回上次更新过后的讯息，直觉的想法会是取回 x 时间点之后的所有讯息，多数的 IM 后台 (有兴趣可以参考 Openfire 的 XMPP 实作) 都会储存讯息的时间戳记 (timestamp) 作为排序之用，但也因为要排序，需要对时间戳记的栏位进行索引 (indexing)，然而过多的索引不但不会提高搜寻的速度，有时甚至对效能是有害的。若 ID 本身是有顺序性的，那上述的问题就会变成取回 ID 是 n 以后的所有讯息。

个人曾搜寻过 UUID 是否是有顺序性的，答案等等再说，在搜寻的过程中找到一篇有趣的文章《细聊分散式 ID 生成方式》，裡面探讨到如何有效率地产生有顺序性的全域唯一 ID，以及一些目前既有方式的优缺点，像是 auto increment primary key 只能依赖唯一一个 RDBMS instance，无法扩展，成为效能的瓶颈；若以时间戳记为 ID，系统时间的颗粒度 (一般来说 Java 的 System.currentTimeMillis()颗粒度只到 10~20 ms) 会影响到短时间大量产生的 ID 是否唯一，此外，在分散式节点的情况下重复的可能性更高。

回到 UUID，当初搜寻时是想知道 UUID 是否有顺序性，而该篇文章中提到 UUID 的缺点有二个：

(1) 无法保证趋势递增

(2) 长度过长 (128 bit，超过一般程式语言int或是long的长度，CPU 运算上较难最佳化，若以字串处理，效能不如int或long等资料型态)，但 UUID 实际上是有一个版本是在特定时间区间内是有顺序性的。

若看 Wikipedia 上对 UUID 的描述可以知道 UUID 目前有 5 个版本，详细的产生方式可以在 RFC 4122 文件的第四节找到，其中版本 3 和版本 5 比较特殊，是以名字产生 UUID，差别是以 MD5 演算法或 SHA-1 进行 hash，在特定条件下，每次产生的 UUID 都应该是一样的 (用以识别是否为相同节点)，比较不适合用在我们讨论的情境中。

版本 4 是全部以乱数组成，若在 Java 使用UUID.randomUUID()产生 UUID，可能会得到像这样的字串04060e46-a46c-4165–9afb-0352bc2aabd8，其中4165的4代表的正是版本 4，若看原始码，会看到 Java 用较安全的SecureRandom产生 16 bytes 的乱数后，设定 version 和 variant 就完成了，效率相当好，但也就不用期待有顺序性了。

public static UUID randomUUID() {
    SecureRandom ng = Holder.numberGenerator;
    byte[] randomBytes = new byte[16];
    ng.nextBytes(randomBytes);
    randomBytes[6] &= 0x0f; /* clear version */
    randomBytes[6] |= 0x40; /* set to version 4 */
    randomBytes[8] &= 0x3f; /* clear variant */
    randomBytes[8] |= 0x80; /* set to IETF variant */
    return new UUID(randomBytes);
}

除了上述三个外，版本 1 和版本 2 都是以时间为基础产生的，版本 2 是 DCE 专属，不去管它。版本 1 将时间戳记 (和一般 UNIX 时间戳记有点不一样，是 1582 年 10 月 15 至今每 100 奈秒为一次的计数，简单说是取得奈秒后除以 100) 及该节点的 MAC address (若没有 MAC address 可以用 48-bits 的乱数取代) 以指定的方式排列。若时间戳记以 unsigned 表示，大概可以用到西元 5236 年，每个节点平均每秒可以产生 163 百万个 UUID。

版本 1 的 UUID 可到这裡看，每更新画面一次，会发现最后面的 12 个字母(92361f002671) 都是固定的 (照标准是该伺服器的 MAC address，但实作上可能会 hash 过)，而最前面的 8 个字母会一直跳动且是有顺序性的，下一个 4 字母组合则大概每 7 分钟 (232 * 100 奈秒) 会变动一次，下一个 4 字母中，第一个字母1代表这个 UUID 是 version 1，后续三个字母则大概每 10 个月(2?? * 100 奈秒) 跳动一次。

那不就好棒棒！有顺序性又有唯一性，但如果真的要进行排序，您会发现有问题，如果看 Java 在 UUID 的compareTo实作，先比较最高的 64 bits (正好是long长度，比对可以优化)，相同才比最低的 64 bits，也就是说第n+8分钟产生的 UUID 可能在排序时排在第n分钟之前，因为前 8 个字母代表的是时间戳记中最低的 32 bits，也就是说大概每 7 分钟，就可能从0重新开始计数，但却放在最高的 32 bits 中，让该一直递增的数会週期性变小后再递增。

public int compareTo(UUID val) {
    // The ordering is intentionally set up so that the UUIDs
    // can simply be numerically compared as two numbers
    return  (this.mostSigBits < val.mostSigBits ? -1 :
            (this.mostSigBits > val.mostSigBits ? 1 :
            (this.leastSigBits < val.leastSigBits ? -1 :
            (this.leastSigBits > val.leastSigBits ? 1 :
            0))));
}

那怎么办？在 RFC 4122 文件中，其实有保留改变数字排列 (layout) 解读的方式，也就是 variant bits，视情况 1 ~ 3 bits，一般 UUID 的实作是10x(x表示0或1皆可)，110则是微软保留，0xx则是 NCS 保留，111则是尚未使用，透过设定不同的 variant 是可以让解读的人知道您产生的 UUID 并不是照目前的标准排列，但若没有将您的排列方式送交 RFC 或其他标准化单位，也不会有人知道该怎么解读您的 UUID。

另外，也可以自订新的 version 达到相同的目的，例如将版本 1 的 UUID：12adde00-f100–11e6-bc64–92361f002671调整排列顺序，并将其中的版本改为 6，同时将 variant 改为 7 就会得到1e6f1001–2add-6e00-fc64–92361f002671，若将这 UUID 交给 Java，是可以解读出对的版本与 variant，而且这个 UUID 在排序时，会是依时间递增的。

UUID uuidv6 = UUID.fromString("1e6f1001-2add-6e00-fc64-92361f002671");
System.out.println("version: " + uuidv6.version()); // got 6
System.out.println("variant: " + uuidv6.variant()); // got 7

有顺序的 UUID 除了排序时方便，在当作 MySQL 的主键 (primary key)，也有很好的 performance 表现，在《Store UUID in an optimized way》可以看到量测的数据，在 insert 的时间上，与 auto increment 是差不多的，而产生的资料大小也与 auto increment 相近，索引的资料大小则是最小的，重点是都比版本 1 的 UUID 要好，当然这量测数据会因为使用的引擎有所差异，但这裡只是想表示 ID 的产生方法确实会影响效能。

然而有顺序的 UUID 不见得适用在所有的情境上，例如在 AWS S3 反而建议 object key 的前四个字元越是乱数分佈越好，根据《AWS S3 Performance Tuning》的说法，AWS S3 是用前四个字元作为档案分配到哪台机器的重要指标，若以我们修改的 UUID 来说，前四个字元在相当长的一段时间内都会是一样的12ad，这导致所有的档案都被丢到同一台机器，让 AWS S3 分散式架构的好处无法发挥出来。

从上述两个例子可以发现 UUID 是可以视需求，选择用版本 1 或版本 4，甚至是像上面的例子修改 UUID 版本 1 的产生方式，要产生类版本 1 的 UUID 还有二个问题要处理，也就是 clock sequence 与 node 如何产生，先看 clock sequence，假设不与标准衝突 (避开被保留的0、2与6)，暂时将 variant 设为 7 也就是111，那 clock sequence 就会是 13 bits 长度 (如下图，粗黑框线是连字号 hyphen 的位置)，可以参考版本 4 直接用乱数，算是比较简单。

而 node 的 48 bits，在 server 上相对容易，而且在多节点环境还更有利于避免产生的 UUID 会重复，也就是直接取得 MAC address，但要注意，基于安全考量，不希望暴露实际的 MAC address 的话，是可以加上 salt 后用 MD5 或 SHA-1 进行 hash 取出其中的 48 bits，如此相同的节点就会有相同的 48 bits node。

但在 client 上就不见得能取得 MAC address， 像是开发 iOS App，基于安全考量，SDK 并没有提供取得 MAC address 的 API，虽然说也是可以参考版本 4 用乱数取代，但这会导致即使相同的装置，产生出来的 48 bits node 都不一样，这是否是个问题要视应用而定，若想识别是哪个装置产生的，那就不适合用这方式。在这情况下，可以用 server 配发的帐号 ID (又是一个 UUID 也没关係) 再次 hash 过取出 48 bits 也是一种方法。

最后总结，UUID 是蛮常见的 ID 生成方法，像是 MongoDB 也支援 UUID 作为 ID，在不同应用下，也可以客製化 UUID 的演算法，不过要注意的是，UUID 还是有可能重复，只是机率非常非常的低，比中乐透还低 (详细的机率请参考 Wikipedia)，任何的客製化都可能会影响到重复的机率，在设计时要多加考虑。然后，不论使用标准的 UUID 或是客製的 UUID，都避免不掉它 128 bits 长度所带来的缺点，使用前，需衡量是否必要，或是使用其他像是 snowflake 等方案。

同场加映 (2017/2/13 更新)

前面有提到 UUID 若以字串的方式做比较，效能会比较差，但实际上到底会差多少？用想的不如就做实验吧，下面的 Java 程式用迴圈，对 1,000,000 个 UUID 物件阵列或是 UUID 字串阵列进行排序，重复 100 次，每次都会重新产生新的 1,000,000 个 UUID 物件或 UUID 字串。

public static void sortUUIDs(boolean asString) {
    int totalTimes = 1_00;
    int sizePerTime = 1_000_000;
    for (int time = 0; time < totalTimes; time++) {
        // Initialize the array
        Object[] uuids = new Object[sizePerTime];
        for (int index = 0; index < sizePerTime; index++) {
            uuids[index] = asString? UUID.randomUUID().toString() : UUID.randomUUID();
        }

        long sortStart = System.currentTimeMillis();
        Arrays.sort(uuids);
        long sortEnd = System.currentTimeMillis();
        System.out.print((sortEnd - sortStart) + ", ");
    }
}

每次执行结果以逗号分隔，再将结果贴到 Excel 绘製图表，水平轴是执行的次数，垂直轴是该次所花的时间，单位是 ms，以平均来看，排序 1,000,000 个 UUID 对象需要 352 ms，而排序 1,000,000 个 UUID 字串则是 679 ms，我想这差距应该十分明显了。

所以若选择 UUID 作为 ID，记得要从该资料库系统支援的资料格式中，选择合适的格式储存 UUID。

The 212? Ways to Ensure Unique Identifiers 介绍 Firebase 如何产生唯一且递增的 ID，Firebase 的 ID 不是 UUID，长度为 120 bits，由 48 bits 的时间戳记，加上 72 bits 的乱数，并用调整过的 Base 64 编码让编出来的字元数更短，并保证递增性 (ordered lexicographically)