为什么UUID＃compareTo与RFC 4122不兼容？

Question

概述

Java的UUID类实现了Comparable接口，但是它实现的顺序似乎与RFC 4122中给出的规范不兼容。

特别地，它与其字符串表示所暗示的自然顺序不一致（uuid1.toString().compareTo(uuid2.toString())），而该顺序与RFC相符合。

---

示例

您可以使用以下代码复现并观察问题：

UUID uuid1 = UUID.randomUUID();
UUID uuid2 = UUID.randomUUID();

Assert.assertEquals(
        Math.signum((int) uuid1.compareTo(uuid2)),
        Math.signum((int) uuid1.toString().compareTo(uuid2.toString())));

---

详情

我的主要问题是，几乎所有其他工具和语言似乎都与RFC 4122一致且兼容，但Java却不是。

在我的特定情况下，我正在使用postgresql 13并按包含UUID的列进行排序，例如myColumnd::UUID或myColumnd::text（使用uuid_v4），但是通过这种方式获得的顺序与Java获得的顺序不同。

- Pedro Borges

---

不是很重要，但你使用的Java版本是什么？ - OneCricketeer

你想如何排序UUID？按创建时间？随机数生成器种子？还是节点ID？ - kofemann

Javadoc说：如果两个UUID最显著的不同字段在第一个UUID中比第二个UUID大，则第一个UUID大于第二个UUID。 - kofemann

@PedroBorges 我只是想在质量方面让你的问题更好。要求人们在能够真正帮助你之前先运行你的代码并不会使得帮助你变得更容易。 - Zabuzard

JDK-Bug 7025832 - 解决方案为 Won't Fix :-( （说明：该Bug的问题将不会得到修复） - user16320675

Answer 1

好的，一个情况是比较UUIDs，另一个情况是按字典顺序比较两个字符串。

根据Javadoc:

如果两个UUID在最高有效字段上不同，则第一个UUID大于第二个UUID。

- kofemann

---

十六进制字符串表示的词法顺序等于数值顺序，即使不相同，数据库为什么会做出不同的处理呢？ - Pedro Borges

数据库通常将UUID视为字符串，但UUID不是字符串，而可以表示为字符串。 - kofemann

说实话，我们在数据库中使用uuid作为主键。但是我们并不希望它们有任何特定的顺序。 - kofemann

@PedroBorges 你必须向这个类的实际作者询问为什么他们使UUID#compareTo与其字符串表示的顺序不兼容。 - Zabuzard

顺便说一句，PostgreSQL原生支持UUID，它们不是文本 - https://www.postgresonline.com/article_pfriendly/179.html GUID/UUID在PostgreSQL或SQL Server系统中都不是文本。 - Pedro Borges

Answer 2

问题原因

你所看到的是一个已知的bug，这个bug不会被修复以保持向后兼容性。

详情请见JDK-7025832：

虽然这个bug确实存在，compareTo方法的实现与其他实现不一致，但Java的UUID.compareTo()方法必须保持一致。 compareTo()函数主要用于排序，UUID的排序顺序必须在Java版本之间保持稳定。

---

有符号比较

根本问题在于Java的long类型是有符号类型，但来自RFC 4122的参考实现和其他工具和语言中的实现使用无符号类型进行计算。

由于数字溢出/下溢点不同，结果的排序略有不同。例如，Long.MAX_NUMBER大于LONG.MAX_NUMBER + 1，但对于它们的无符号对应物则不然。

Java实现的问题被发现得太晚，现在我们必须接受这种不兼容性。

---

实现附录

这里是RFC 4122的正确参考实现：

/* uuid_compare --  Compare two UUID's "lexically" and return */
#define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1;
int uuid_compare(uuid_t *u1, uuid_t *u2)
{
    int i;

    CHECK(u1->time_low, u2->time_low);
    CHECK(u1->time_mid, u2->time_mid);
    CHECK(u1->time_hi_and_version, u2->time_hi_and_version);
    CHECK(u1->clock_seq_hi_and_reserved, u2->clock_seq_hi_and_reserved);
    CHECK(u1->clock_seq_low, u2->clock_seq_low)

    for (i = 0; i < 6; i++) {
        if (u1->node[i] < u2->node[i])
            return -1;
        if (u1->node[i] > u2->node[i])
            return 1;
    }
    return 0;
}
#undef CHECK

定义在结构体上

typedef struct {
    unsigned32  time_low;
    unsigned16  time_mid;
    unsigned16  time_hi_and_version;
    unsigned8   clock_seq_hi_and_reserved;
    unsigned8   clock_seq_low;
    byte        node[6];
} uuid_t;

如您所见，他们逐个比较节点（按正确顺序），这些节点是byte。

而Java的实现方式则是：

@Override
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))));
}

基于两个（有符号）长整型：

private final long mostSigBits;
private final long leastSigBits;

- Zabuzard

---

感觉这里有两个不同的问题，一个是你提到的溢出，在结果中会产生小差异。另一个则是我所指出的，它总是发生。否则所有我尝试的随机UUID都不会出现不同的顺序。 - Pedro Borges

顺便感谢您对问题的修改，现在更清晰了。 - Pedro Borges

Answer 3

这是因为Java没有无符号类型，而UUID是通过比较两对有符号的long来进行比较的。这真令人沮丧。

- chrylis -cautiouslyoptimistic-

---

这是一个已知的10年老漏洞[7025832]（https://bugs.openjdk.java.net/browse/JDK-7025832） :-( - user16320675

@chrylis-cautiouslyoptimistic- 您的答案并不是错误的，但它是针对完全不同问题的答案。OP正在问为什么Java作者以一种与String#compareTo不兼容的方式实现了UUID#compareTo（请参见评论）。这与UUID在第一眼中使用两个有符号长整型表示无关。他们也可以将compareTo实现为return toString().compareTo(other.toString());。或者以一种使输出顺序与词典字符串顺序兼容的方式比较长整型，这只是巧合。 - Zabuzard

@user16320675 给这个答案增加了非常必要的背景信息。你应该自己添加并详细阐述，这样人们就不会对答案进行负评了。 - Zabuzard