BT

你的观点很重要! 快来参与InfoQ调研吧!

UUID简史

| 作者 Rick Branson 关注 0 他的粉丝 ,译者 大愚若智 关注 5 他的粉丝 发布于 2017年8月14日. 估计阅读时间: 34 分钟 | ArchSummit社交架构图谱:Facebook、Snapchat、Tumblr等背后的核心技术

A note to our readers: As per your request we have developed a set of features that allow you to reduce the noise, while not losing sight of anything that is important. Get email and web notifications by choosing the topics you are interested in.

本文最初发布于Segment官方博客,原作者:Rick Branson。经授权由InfoQ中文站翻译并分享。阅读英文原文:A Brief History of the UUID

今天,我们发布了KSUID,一款用于生成唯一ID的Golang库。该产品借鉴了目前广泛使用的UUID标准一些核心理念,增加了基于时间的排序功能,可提供更友好的表现格式。在针对该产品进行调研的过程中,我们发现UUID的背后其实还有一个极富吸引力的故事,想要借助本文分享给大家。

自从两台甚至更多计算机可以通过网络交换信息那天起,它们就需要一种能够体现唯一性的“身份”。

第一个符合目前我们所知这种定义的“网络”,是1870年代建立的全球首个电话交换网。在此之前,电话线路完全是一种点对点链路。尽管在当时这有着划时代的意义,但这种网络很昂贵,不灵活,也不可靠。甚至导致各大主要城市街头形成了电线交织而成的“蜘蛛网”。

(点击放大图像)

当时哪怕电报也只能被政府和企业用于传递重要信息,电话就更是一种奢侈品了。考虑到电报的速度,专门架设昂贵的电线来更快速的“聊天”,似乎是一种很夸张的做法。不过随后的一个重要创新:可创建交换电路的电话总机,让电话变得更实用。此时电话才真正深入寻常百姓家。而电话总机也为电话网络引入了首个具备唯一性的身份:电话号码。

几十年后,计算机网络出现了。突然之间,身份的粒度有了数量级的提升。

当时,通过电话线路传输数据是一种短暂执行的操作,网络只起到管道作用。现在,按需存储和获取数据的做法已变得极为普遍,整个世界已淹没在数量爆发式增长的数据海洋中。在这些新能力影响下,网络身份对应的主体已由传统计算机实体变为组成数据的逻辑片段。

这样的网络需要通过某种具备唯一性的方式对数据片段寻址,电话网络时代那种需要集中控制的系统已无法满足需求。从数学的角度来看,这种问题是不可避免的,毕竟网络存储和检索数据的能力以及数据的规模都在线性增长着。这样的规模在一定程度上还产生了些许混乱:各种故障和暂存的计算机也已经从牦牛剪毛(译注:牦牛剪毛,Yak shaving,是指为了间接实现一个目标而做的次要,并且与目标无关的工作)问题变得稀疏平常。数据不再只安于一地,而是会在整个网络内自由移动。

计算领域迎来网络化时代

很快到了1980年代,当时使用计算机共享数据实际上意味着要共享整个实体计算机。各大机构会使用微型计算机,以及连接了几百上千台哑终端的高性能大型机交换信息。

换句话说,当时数据本身与计算工作是共存的。虽然个人计算机提供了革命性的计算能力,但由于缺乏网络功能,当时的个人计算机实际上只是一种奢侈的计算器。

成立于1980年的Apollo Computer,曾是步入当时新兴工作站市场的首批公司之一。工作站才是真正意义上的第一种可联网计算机,使用“工作站”这个词描述这种计算机听起来似乎有点滑稽,但别忘了,目前我们习以为常的各种网络技术在当时还处于萌芽状态。与大型机相比,数据和计算功能分散在很多相互连接的计算机中,而此时“分布式计算”这个词也开始进入主流视野。

(点击放大图像)

与同时代的Sun Microsystems类似,Apollo的产品也是全栈的。一切都需要从零开始来开发,因为当时软硬件在设计方面与他们构想的用例还有些差异。网络的异步性以及这些任务的本质需求需要功能更丰富的计算机。多任务、安全控制、网络,以及海量存储等特征对当时的个人计算机来说要么过于昂贵,要么不够现实。不过在工作站的未来构想中,这些特征已成为了“标配”。

尽管工作站市场上的各类技术经历了让人印象深刻的爆发式增长,但当时的所有供应商都面临一个共同障碍:缺乏精通网络技术的开发者。为了给自己价格昂贵的工作站塑造一个切实可行的商业案例,他们需要一种编程环境。借此,开发者才能通过某种方式,轻松构建能帮助各家产品将网络功能完全发挥出来的应用程序。

对此,Apollo提出了网络计算系统(NCS)的概念。NCS借鉴了面向对象编程的某些思路,围绕远程过程调用(RPC)的概念构建。虽然这种方式目前已面临淘汰,但在当时至少满足了Apollo的需求:任何开发者都可以了解如何调用某一函数,并以面向对象的编程范式为主要特色。

在Network World杂志1989年发布的一篇有关RPC的文章中,Burlington Coat Factory的一位MIS总监提出了自己的观点:“训练有素的程序员只需要一天左右时间就能学会使用RPC构建分布式应用程序”。同样是那一年,Apollo作价4.76亿美元卖给了HP,考虑到通货膨胀,这一价格约等于今天的10亿美元。

NCS术语中所谓的“物件”(对象、接口、操作[方法]等)也就是“实体”,必须能在网络化的环境中通过具备唯一性的身份进行寻址。在标准的冯·诺伊曼体系结构中这一点并不重要:内存或大容量存储设备的地址即可承担这一用途。但在分布式计算模型中,由于多台计算机可以分别独立运作,这就很重要了。考虑到具体用例的实际规模,跨越网络进行协调的方式并不现实,因为速度太慢,并且非常容易出错。

NCS引入了UID(Universal IDentifier,全局标识符)的概念,并使用UID作为实体身份主要且唯一的标识符。UID是一种64位数值,结合单调(Monotonic)时钟与工作站硬件嵌入的永久性唯一主机ID生成。通过这种方式,每台主机每秒钟可以完成数千次标识符生成操作,并在所有时间内确保全局唯一性,在规模方面也不存在瓶颈。这种机制唯一需要进行的协调工作可以在Apollo的工厂中进行,只需为每台计算机嵌入一个永久ID即可。

第一个UUID

当Apollo开始通过网络计算架构(NCA)践行自己标准化的NCS构想时,很快发现,只使用现有的UID还不够。Apollo希望所有工作站供应商通过NCA实现标准化,都在自己的工作站中嵌入主机ID,而具体位长可由供应商自行决定。

Apollo使用了20位长度,很适合计算机总数约为100万台的情况。以今天的视角来看,这样的规模实在是很可笑,但在当时,Apollo需要在整个体量小很多的市场中卖出总价值超过100亿美元的硬件才能达成这样的规模。

NCA引入了UUID的概念,UUID源自UID的设计基础,但将地址空间扩展到128位,这样就可以有更多供应商分别打造自己的产品。UUID就此诞生。这个概念是如此有用,以至于在NCA成为历史,RPC逐渐退流行的今天,UUID依然维持着活力,并最终被ISOIETF,以及ITU确定为标准。

(点击放大图像)

对UUID有所了解的读者会发现,这个概念与目前广泛使用的第4版UUID有些许差异。NCA UUID包含一个48位时间戳,16位预留位,一个8位网络地址族指示符和一个56位主机ID。这些结合在一起,其实与目前成为IETF标准的第1版UUID概念极为类似。

这些历史事件不禁让我好奇UUID的具体实现,并有幸在网上找到了一些Apollo NCS源代码。如果你和我有着类似想法,不妨一起读读这些几十年前写的源代码。我在这些代码中发现的第一个奇怪之处是:这种标识也像变量和函数名那样使用了美元符号($)。

void uuid_$gen(uuid)
uuid_$t *uuid;
{
#ifdef apollo

    std_$call void uid_$gen();
    struct uid_t uid;

    uid_$gen(uid);
    uuid_$from_uid((uid_$t *) &uid, uuid);

原来NCS使用了一种名为“Domain C”的语言,这种语言由Apollo开发,包含在他们的“Domain/OS”操作系统中。在Bitsavers的帮助下,我找到了一份1988年发布的PDF版参考手册。Domain C通过多种方式对ANSI C进行了扩展,最重要的是可支持在任何标识符的首个字符之后使用$。

在当时,美元符号主要被一些不怎么时髦的编程语言充当一种变量语法,经济领域用它代表货币单位,或者用它形容那些自我膨胀的音乐家。为了理解这个符号在现已灭绝的Apollo Computer世界中的实际用途,还需要继续深入挖掘更多代码和文档。

在进一步展示我的发现之前,首先要说说自己发现的一个虎头蛇尾的结论:虽然并没有明说,但这似乎只是一种写代码的习惯。_$之前的任何内容实际上代表某个特定模块,_$t代表“默认类型”,例如上文出现的uuid_$t。此外借此也可以很方便地判断哪些标识符隶属于符合Apollo编程风格的库。仅仅为了适应某种具体的编码风格就对C进行扩展,Apollo的这种做法还是让人感觉有些困惑的。

但我不同意。

NCA UUID最终成为了标准化后第1版UUID的基础。需要重申一点:其中包含了一个高精度时间戳以及基于硬件的唯一主机标识符。毫无疑问,无法仅通过系统时钟以可靠的方式生成具备唯一性的序列号,因为时钟有可能不准确,甚至可能导致生成重复的时间戳。为此Apollo使用了一个全局文件(位于/tmp/last_uuid)对不同进程进行协调。

/*
 * C H E C K _ U U I D
 *
 * On a system wide basis, check to see if the passed UUID is the
 * same or older than the previously generated one. If it is, make sure
 * it becomes a little newer.  Write the UUID back to the "last UUID"
 * storage in any case. In the case of systems using a file as
 * the storage, fall back to "per process" checking in the event of
 * the inability to safely access the storage.
 */

该文件可被任何用户全局写入,虽然并非特别安全,但Apollo向最终用户销售的工作站有些也被用在某些高可信网络中,因此也可以将其理解为一种合理的决策。这种技术在UUID的IETF规范中也得到了进一步完善:

   The following algorithm is simple, correct, and inefficient:

   o  Obtain a system-wide global lock

   o  From a system-wide shared stable store (e.g., a file), read the
      UUID generator state: the values of the timestamp, clock sequence,
      and node ID used to generate the last UUID.

   o  Get the current time as a 60-bit count of 100-nanosecond intervals
      since 00:00:00.00, 15 October 1582.

   o  Get the current node ID.

   o  If the state was unavailable (e.g., non-existent or corrupted), or
      the saved node ID is different than the current node ID, generate
      a random clock sequence value.

   o  If the state was available, but the saved timestamp is later than
      the current timestamp, increment the clock sequence value.

   o  Save the state (current timestamp, clock sequence, and node ID)
      back to the stable store.

   o  Release the global lock.

   o  Format a UUID from the current timestamp, clock sequence, and node
      ID values according to the steps in Section 4.2.2.

出乎意料的是,我找到的有关DCE的一个实现,具体源代码竟然来自Apple。Apple似乎主要使用这种技术与微软系统,如Active Directory和Windows文件服务器通信。这个实现包含开源软件基金会的版权,并将实际的功能隐藏在一个名为UUID_NONVOLATILE_CLOCK的预处理器标记之后。

#ifdef UUID_NONVOLATILE_CLOCK
        *clkseq = uuid__read_clock();           /* read nonvolatile clock */
        if (*clkseq == 0)                       /* still not init'd ???   */
        {
            *clkseq = true_random();      /* yes, set random        */
        }
#else
        /*
         * with a volatile clock, we always init to a random number
         */
        *clkseq = true_random();
#endif

我在网上没找到任何可用于为DCE RPC的UUID生成过程实现非易失时钟的代码。然而大部分Linux发行版的程序包中提供的libuuid确实包含了一个可供使用的非易失UUID时钟实现。与NCS类似,它会使用文件实现单调性(Monotonicity),但会将该文件放在更合理的/var/lib/libuuid/clock.txt中。虽然该技术会试图通过略微更全面一些的方式来管理权限,但依然面临相同的安全问题。

NCS和libuuid实现都需要针对状态文件获得所需的锁,但这种做法很容易造成各种讨厌的问题。

                while (flock(state_fd, LOCK_EX) < 0) {
                        if ((errno == EAGAIN) || (errno == EINTR))
                                continue;

libuuid实际上是一种守护进程,但令人费解地使用了uuidd这样的名字,目的主要是为了提供一定程度的安全性。uuidd可以强有力地保证一切都符合自己的规则。通过将其与假定唯一的以太网MAC地址配合使用,即可在分布式系统内提供相当强的担保。

然而在实践中依然有很多问题需要考虑。基于文件的同步会因为各种问题导致同步失败,基于守护进程的解决方案略好一些,但似乎从未得以普遍运用。而直接使用拆箱即用的系统,不进行任何额外的配置,这样的做法就更为罕见了。

另外MAC地址也并非真正全局唯一的,因为用户可以修改。因此UUID包含MAC地址,这种做法也可能威胁到隐私和安全。考虑到不透明这一本质,开发者开始趋向于不认为UUID可以包含用于识别具体机器的信息。九十年代末期影响大量Windows计算机的Melissa病毒的创作者,就是因为从病毒代码中发现的UUID中包含了MAC地址而被确定身份的。随着不可信赖的互联网逐渐成为处于支配地位的网络平台,基于信任关系生成UUID的做法已经显得落伍。所有这些顾虑最终导致人们放弃考虑在UUID中使用硬件标识符。

/*
 * This is the generic front-end to uuid_generate_random and
 * uuid_generate_time.  It uses uuid_generate_random only if
 * /dev/urandom is available, since otherwise we won't have
 * high-quality randomness.
 */
void uuid_generate(uuid_t out)
{
        if (have_random_source())
                uuid_generate_random(out);
        else
                uuid_generate_time(out);
}

实际上,libuuid的默认路径会避免在能够通过/dev/(u?)random提供伪随机数生成块设备(Block device)的任何系统上使用基于时间的UUID,而自从1990年代起各大主流UNIX变体就已支持这种做法了。这也直接推动了第4版UUID的形成,该版本只包含随机数据,共122位。简化后的实现过程使得该技术也开始得以广泛运用。

当两个世界碰撞之后

当我首次遇到这些随机的第4版UUID时,曾担心过因为碰撞可能产生的威胁。虽然UUID的使用场景不应该由于碰撞造成安全威胁,但作为开发者,我希望能够确信自己的系统不会在这方面遇到问题。糟糕的是,UUID的生成依然需要依赖一定程度的“信任”。

防碰撞方面最重要的一点在于熵的来源。请考虑这两种常见情况:在可信赖的云环境中部署了一个现代化版本的Linux,以及一个不可信赖的移动设备。在云端的Linux方面,我们可以通过/dev/urandom获得一个从密码学角度来说较为安全的伪随机数生成器(PRNG),这就是所谓的获得“密码学认可”且无阻塞的“熵的来源”。这种方式可将诸如硬件中断生成的“噪音”以及I/O活动源数据等不同来源与密码学函数结合在一起。

然而在移动设备上几乎一切都不同了:移动设备无法被信任。虽然大部分移动设备也可以实现上文提到的技术,但实际上此类设备的PRNG源并非彻底随机的。由于无法对此类特征提供保证或证明,因此对移动设备PRNG的信赖无疑像是一场豪赌。信任度低的移动设备生成的ID,这一话题正在受到学术界的关注,并已成为一个积极研究的领域[1]

就算具备可信赖PRNG设备的环境,具体实现方面的Bug也可能导致碰撞。例如曾经有这样一个例子:OpenSLL在处理进程Fork过程中存在一个隐蔽的Bug,会导致纯PHP的UUID库产生较高碰撞率。虽然听起来不太严重,但最好针对自己的UUID实现对各种明显会造成碰撞的Bug进行测试,实际出现的概率可能远超你想象。在系统层面上可以使用dieharder,这是一个非常著名的系统PRNG质量分析工具。

只要具备妥善的环境,碰撞风险就会无限降低,甚至趋近于不可能。为实现这样的唯一性,必须使用足够大的号码空间,以确保其他极为罕见的事件能够先于碰撞首先发生。

因为共包含122个随机位,UUID的数量总规模高达PB级别(2^46),这也进一步将碰撞的可能性降低至大约五百亿分之一。需要生成数十亿个PB的UUID才有可能产生碰撞。

相比随机碰撞,实现方面的Bug和错误的配置往往风险更高。对UUID碰撞有所顾虑的人,如果能使用妥善配置的系统,那么完全不需要在这个问题上太过担心,此时出现碰撞的概率甚至远远小于太阳耀斑爆发、热核战争,以及外星人入侵等事件。请务必对系统进行妥善正确的配置。

时间问题还是由我们来考虑吧

某些情况下,第1版UUID的时间戳组件还是相当有用的。我在使用Apache Cassandra时第一次意识到这一点。该产品中,他们把它称作“TimeUUID”。在Cassandra中,TimeUUID可按照时间戳排序,如果希望按照时间进行粗略排序,这个功能会比较有用。这种实现会对部分随机位以及时间戳和主机标识符进行互换。主机ID派生自节点IP地址,同时该IP地址还组成了Cassandra集群所用的唯一标识符。

如果通过时钟偏差攻陷这种技术的唯一性,那么这种实现方式也存在一些弱点(可参阅CASSANDRA-11991)。更重要的是,主机可辨识信息已经嵌入在UUID中,但是从过去的经验来看,这种做法并不怎么好。就算这些ID是通过本地网络地址派生而来的,安全方面的最佳实践也不推荐主动将此类信息暴露给外界,哪怕是间接暴露。

那些古怪的友人们

按照时间对ID排序的能力可能是Twitter开发Snowflake的最大动机,正是Twitter的这项技术使得按照时间戳进行K-ordering排序的概念变得人尽皆知[2]。Twitter需要通过某种方式在无需进行全局协调的情况下,按照创建时间对任意一批推文进行排序。通过在ID中嵌入时间戳,即可在不需要无谓地创建一个时间戳字段的情况下获得这种功能。

K-ordering是一种更精确的粗略排序方式。Snowflake中有大量设计是由将这些ID融入64位号码空间的需求推动的,例如需要通过专用的ID生成服务器,使用一套单独的强协调机制(ZooKeeper)分配主机ID并存储序列检查点。

受到Snowflake启发的Boundary团队在2012年初发布了Flake。该技术也使用了专用的ID生成服务器进程,但不需要强协调机制。Flake与第1版UUID的相似之处在于,需要使用规模更大的128位号码空间,以及一个通过硬件地址派生而来的48位主机标识符,借此预防分布式环境中出现的重叠问题。

该技术与第1版UUID的不同之处在于使用了不同的字典排序(Lexicographic ordering)构造。Flake ID的位会通过一种排列方式确保用户无论写入到那里,都可以保证按时间戳排序。而Cassandra必须实现一种特定的顺序逻辑才能对TimeUUID提供类似行为。

由于要将主机标识信息嵌入到生成的ID中,导致Flake ID会将此类信息暴露给最终用户。虽然具体实现方面通过相应机制可防范时钟偏差,但这种方式的唯一性严重依赖于时钟走时。

Flake有个值得一提的特性:Base62编码,该技术相比UUID能提供更“可移植”的表达(Representation)。UUID字符串的表达是其最大的劣势之一,虽然看起来可能并不重要,但由于使用了连字号(-)字符,导致UUID的适用性有所降低。例如当使用搜索引擎对UUID创建索引时,连字号可能会被理解为分隔符。Base62编码可避免这种问题,维持二进制编码的字典排序属性。

两者的强强联合

Segment在实现一个内部系统的过程中,我们团队最开始使用了第4版UUID来生成唯一标识符。这种做法更简单,不会造成额外的依赖性。

但在几周后遇到了一个新需求,必须按照出现时间对这些标识符进行排序。这个需求并不十分严格:最初目的只是为了方便将日志归档至Amazon S3,并在那里根据消息标识符的范围实现键控(Keyed)。现有的UUID会导致消息随机分布,无法自然地进行恰当分组。然而如果能充分利用时间箭头(Arrow of time)功能,即可实现自然分组,并为S3中的对象编制更可行的号码。

因此我们开发了KSUID。KSUID是K-Sortable Unique Identifier(可K排序的唯一标识符)的缩写,该技术将第4版UUID的简化性和安全性与Flake K-ordering的字典属性结合在了一起。KSUID通过一定的取舍实现了我们的目标,但我们认为这些取舍无论对自己还是别人来说,都是合理的。

(点击放大图像)

KSUID比UUID和Flake ID更大,共包含160位。其中包含一个32位时间戳和一个128位随机生成载荷。该技术的唯一性不依赖任何主机可辨识信息或时钟,而是与第4版UUID类似,依赖如此大规模号码空间内出现随机碰撞的不可能性。为了降低实现工作的复杂度,我们将122位的第4版UUID四舍五入至128位,此举也使其抗碰撞能力提升了64倍,而这还是在不考虑额外增加的32位时间戳的情况下。

时间戳精度为1秒,我们认为这样的精度对大部分用例已经足够了。如果需要更高精度的时间戳,可将部分载荷位改为更长的时间戳位。虽然我们的实现并未对更高精度的时间戳提供支持,但提供了向后兼容性。任何使用32位时间戳的实现均可安全地通过KSUID使用更高精度的时间戳。

该技术使用了“自定义”的纪元(Epoch),确保可在上百年的时间里始终有效。此外这个纪元还使用了偏移量(14e8),以确保更易记,同时对人眼来说也更易读。

(点击放大图像)

KSUID提供了两种定长编码方式:一种20字节的二进制编码,以及一种27字符的Base62编码。通过使用大端位字节排序(Big endian byte ordering)对时间戳进行编码,可实现字典排序属性。Base62编码通过调整可将字符的字典排序与对应的ASCII排序进行映射。

定长编码在实现方面更简单也更安全。此外作为一个额外的“福利”,这种方式有时候也更高效,例如在SQL数据库中,可变长度数据类型通常会造成额外的存储开销。无论选择哪种格式,KSUID都可以按照时间进行字典排序,字符串的表达完全基于字母数字(Alphanumeric),可避免UUID中连字符的标记化(Tokenized)问题。

我们的具体实现

今天,我们正式开源了自己的KSUID实现。KSUID使用Go语言开发,提供了符合主流习惯的接口,因此可轻松集成于现有代码库,并配合其他Go语言库使用。KSUID还包含了用于生成和检查KSUID的命令行工具。

$ ksuid
0o5Fri5Ia34BTFurJmkOf9T6S1e
$ ksuid 0o5Fs0EELR0fUjHjbCnEtdUwQe3
REPRESENTATION:

  String: 0o5Fs0EELR0fUjHjbCnEtdUwQe3
     Raw: 05A95E21D7B6FE8CD7CFF211704D8E7B9421210B

COMPONENTS:

       Time: 2017-05-16 18:49:21 -0700 PDT
  Timestamp: 94985761
    Payload: D7B6FE8CD7CFF211704D8E7B9421210B

致谢

本文的撰写得到了来自Bitsavers的帮助,他们收集并整理了有关Apollo Computing的素材。此外还要感谢Albert Strasheim、Calvin French-Owen、Evan Johnson、Peter Reinhardt,以及Tido Carriero提供的深度见解和反馈。

脚注

[1] P. Jesus, C. Baquero, and P. Almeida: ID Generation in Mobile Environments (2006)

[2] T. Altman, Y. Igarashi: Roughly sorting: sequential and parallel approach (1989)

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

熟悉了uuid的历史 by 松松 熊

很赞的文章,讲述了uuid的来龙去脉。

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

1 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT