LINUX实战：UUID简史
|
《LINUX实战：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依然维持着活力,并最终被ISO、IETF,以及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,and node ID)
back to the stable store.
o Release the global lock.
o Format a UUID from the current timestamp,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活动源数据等不同来源与密码学函数结合在一起. 更多LINUX教程，尽在编程之家PHP学院专栏。欢迎交流《LINUX实战：UUID简史》！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
