本文最初发布于Medium网站，经原作者授权由InfoQ中文站翻译并分享。

你可以信任大家的浏览器，并依靠它们来大规模生成全局唯一标识符吗？在Teads我们已经试过了，答案是肯定的，但也有几点需要注意。本文介绍了我们所做的实验以及在此过程中总结到的经验。

为什么我们需要客户端唯一标识符

在Web页面和电子商务站点上集成的第三方脚本普遍需要生成唯一标识符，用于分析、营销或广告目的。

只要这些脚本的使用规模够大，它们往往就会从CDN（内容交付网络）加载，从而尽量减少响应时间并减轻原始服务器的负载。

这意味着脚本是无法即时生成的。解决方法可以是（或曾经是）让CDN生成唯一标识符并将其存储在cookie中，但欧洲的GDPR和ePrivacy指令，或美国的CCPA等用户隐私法规要求用户明确同意后才能使用cookie。

识别广告体验的唯一性

作为一家在线广告公司，Teads会收集并存储关于每一种广告体验的数据。所谓广告体验，包括用户访问网页并加载广告脚本时发生的所有事件，从初始化广告播放器开始，还包括对广告服务器的请求和用户动作（例如点击）。要判断一组事件是否等同于相同的体验，我们就需要识别这种体验的唯一性，并且要从一开始（即在调用广告服务器之前）就识别出来。

直到今天，广告服务器一直在生成唯一标识符，并将其发送为广告响应的一部分。这是有问题的，因为响应之前的事件没有标识符，所以你需要交叉引用数据以找出属于一类的事件。服务端生成的标识符几乎可以保证是唯一的，并且在接触生产系统之前，我们必须确保浏览器也可以生成通用的唯一标识符。

通用唯一标识符

UUID（通用唯一标识符，也称为GUID—全局唯一标识符）是一个128位值，可以由一台计算机独立生成（即无需与其他计算机通信），并且有极高的概率具备唯一性。UUID被写为以破折号分隔的十六进制数字序列。

以下是RFC 4122定义的UUID第4版的示例：

UUID最初是为分布式计算设计的，它是网络计算系统（NCS）的一部分，迄今已用在了很多实用场景中。在Windows上，UUID的应用非常普遍，因为它们标识了所有COM类（CLSID）和接口，因此所有基于COM的Windows API和应用程序，以及许多OS对象（例如用户、安全策略等）都使用UUID。

实际上，除了上面展示的符合RFC的变体和保留的变体之外，可以指定的四个变体中，其他两个分别是：

NCS向后兼容（最高有效位是0，数值0到7）
Microsoft向后兼容（最高有效位是110，数值C和D）。

UUID的其他应用有文件系统，例如GUID分区表（UEFI的一部分），或在数据库中用于取代传统整数作为记录主键。在互联网广告的上下文中，它们经常用于唯一地标识在Web上查看广告的用户。例如，互动广告局（IAB）建议将UUID用于IDFA（广告标识符）/AAID（Android的Google Advertising ID），以唯一地标识移动用户。

选择你的版本

UUID版本1和2使用计算机MAC地址、100纳秒精度的当前UTC时间戳和一个用来增强唯一性的100ns间隔“时钟序列”（可单调递增或随机）来组合生成标识符。

带有网络控制器的设备都应该有唯一的48位MAC地址，于是不可能有两个设备生成相同的UUID。但这也是这些版本的弱点，因为这意味着此类UUID可用来确定用户的身份。请注意，在用户设备上生成UUID时才会出现这个问题，但服务器上则不会，例如MySQL就使用了UUID v1。

UUID版本3和5是通过对字符串进行哈希处理（v3使用MD5，v5使用SHA-1）来生成标识符的，并且由于哈希是确定性的，因此输出与输入都是唯一的。如果你想将URL用作唯一标识符，那么这种方法就会很有用，只是它们无法满足我们的需求。

最后，第4版中除变体和版本以外的所有位都是随机的，总计122个随机位。这样这些UUID就不会携带任何个人身份信息。需要注意的是，要获得UUID提供的唯一性和不可预测性保证，我们应该使用加密安全的随机数生成器（CSRNG）。

在浏览器中生成一个UUID

如前所见，只要我们有CSRNG，那么UUID第4版就是最佳选项。这样首先就排除掉了老字号的Math.random，因为其实现是与浏览器相关的，并且不能保证加密使用的安全性。在实践中，主流浏览器使用Xorshift伪随机数生成器的一个变体，它的性能在伪随机数生成器（PRNG）中算是很不错的。

CSRNG和PRNG之间的区别在于PRNG使用单个种子，因此具有完全确定性，无法根据先前生成的数字预测CSRNG的输出。

2017年发布的Web Cryptography API（或称Crypto API）定义了getRandomValues函数。根据caniuse的说法，有96.6％的用户使用的浏览器支持Crypto。在我们的用户中这一支持率甚至接近99.9％，换句话说Crypto API几乎可以用在任何地方（甚至包括边缘设备，例如PS Vita）。这是一个重要的考虑因素：我们拥有15亿用户，意味着存在超过一百万种OSx浏览器x浏览器版本x设备的组合，因此我们必须确信所有用户都可以毫无问题地运行我们的代码。

使用Crypto API生成128位（16字节）随机数是非常简单的：

crypto.getRandomValues(new Uint8Array(16))

要将这些随机字节转换为RFC兼容的UUID v4，需要设置变体和版本位，然后将数据转换为以破折号分隔的十六进制数字。
另一种方法是将File API与URL.createObjectURL函数结合，以获得包含UUID的Blob URL。URL.createObjectURL的受支持水平和Crypto类似，都有99.9%。

const url = URL.createObjectURL(new Blob()) 
url.substring(url.lastIndexOf('/') + 1)

File API并未指定应使用哪个版本的UUID或如何生成它们。实际上，基于Chromium的浏览器（Chrome和Edge）和WebKit会使用Crypto实现来生成随机数字，然后设置/清除一些位来创建v4版的UUID。Firefox会调用OS级函数（如果存在，在Windows上为CoCreateGuid，在macOS上为CFUUIDCreate），否则会回退使用Chromium和WebKit所用的Crypto。
最后，浏览器依赖OS直接提供随机数，或收集熵并定期馈送到PRNG来实现Crypto.getRandomValues，从而实现加密安全性（CSPRNG）。

注意事项

我们的脚本已集成在了数以千计的网站上，这些网站往往会包括其他第三方脚本，并且每个脚本都可以重新定义/超载大多数JavaScript函数。我们发现有些脚本正在超载Math.random函数以始终返回相同的值，而另一些脚本正在重新定义window.URL属性以返回当前页面的URL。

有两种方法可以在不受第三方脚本影响的上下文中运行脚本：iframe和Web Worker。相比之下Web Workers更好用，因为它们实例化更快，毕竟它们仅创建新的JavaScript执行上下文，而不是完整的DOM。

UUID生成的实验

我们实现了一项功能，它可以使用Crypto生成UUID（可以回退到Math.random）并将其发送到我们的服务器，然后设置A/B测试。这样我们就能检查大多数浏览器是否确实支持Crypto，并且确保我们的代码没有任何问题，这个过程中不会影响大多数用户。这个功能的A/B测试是在当前帧运行的，可以的话会运行在Web Worker中。

对于已激活“uuid worker”功能的用户，我们测量出其中有50％的设备实例化一个worker需要花费200毫秒以上的时间。在我们的案例中，因为我们想在这一过程中首先生成UUID，所以这么大的延迟是不可接受的。然后，我们切换到了基于File API的实现，使用Crypto作为回退，并使用Math.random作为最后的手段。

分析生成的UUID

我们发现的第一个问题是 每千个请求中有将近2个请求带有重复的UUID 。这可不是什么小事情

从理论上讲，如果你连续85年每秒产生10亿个UUID，就有50％的机会发生一次碰撞。以我们的情况来说，我们每天才生成约10亿个UUID，因此理论上应该可以安全使用约700万年。

差异来自何处？

不同之处在于 我们正在查看的是重复的请求 ，而不是碰撞的标识符。重复的请求来自同一客户端，并被发送到服务器一次或多次，如下所示。这背后可能有多种原因，我们发现这些重复请求中绝大多数都是由第三方脚本中的错误引起的。

另一方面，当一个以上的客户端使用给定的标识符时，发生的才是碰撞。在下面的模式中，客户端1和3之间发生了碰撞，因为它们都生成了以“0a87341d”开头的相同（红色）UUID。请记住，从理论上讲，每天生成十亿个UUID，则“每700万年才会发生一次”这种事件。

碰撞

在我们删除了重复的请求（来自相同的User-Agent、IP地址哈希、引用等）后， 具有碰撞UUID的请求数量大约是每10,000个请求中有2个 。但这还不是全部。当查看标识符的数量时，我们在 每百万个标识符中能遇到5个非唯一的 。

40倍的差距。这是非常出乎意料的：就算能遇到碰撞，你也会认为是两个非常不走运的用户才能撞在一起，是极为罕见的事情；但实际上，在一天之内 全世界有成千上万个不同的客户端在生成相同的UUID 。请记住，浏览器提供的CSPRNG本质上与服务器上用的是同样的水平。那么这里到底发生了什么？

如果我们接收所有带有碰撞UUID的请求，然后深入观察浏览器的User-Agent，就会看到：

这些请求中 有差不多三分之一是由Chrome Mobile 41.0生成的 。这太让人惊讶了，毕竟Chrome Mobile 41已有5年以上的历史。这些请求的另一个共同点是发出请求的城市IP：将近 三分之二来自山景城 。Chrome Mobile 41.0发出的所有请求（100％）均来自山景城（Mountain View）。你能想起来一家总部设在那里的公司吗？

并不是只有我们观察到了这个结果：在有关浏览器中UUID生成的StackOverflow问题中，其中一个答案提到Googlebot是碰撞的主要来源。在这个问题中还提到Googlebot具有“伪”Math.random和“newDate()”实现，这个问题也提到了重复的事件标识符。虽然没有声明，但托管在山景城的Chrome Mobile 41实际上是Googlebot或其他Google服务。这种事情应该不会再发生了，因为Google在2019年12月宣布将开始更新Googlebot，以在桌面和移动设备上使用最新版本的Chrome。

但这还不是全部。 与在山景城中生成的标识符关联的请求占UUID碰撞的92% 。生成剩余8％请求的浏览器User-Agent图像如下所示：

EvoPdf、WnvPdf和HiQPdf是.NET的HTML到PDF转换库，很可能它们在爬取带有我们脚本的页面时多次重复使用了相同的标识符。PS Vita浏览器生成的UUID碰撞似乎是合法的（与欺诈活动无关），并且很可能是由于加密实现不佳所致：没有浏览器生成的UUID会与PS Vita生成的相碰撞。可能他们的Crypto是一个弱PRNG。

最后，Internet Explorer的情况不太像是Crypto实现水平不足，而更像是被恶意脚本滥用了。UUID碰撞的请求中有75％来自3个ISP：

Nobis科技集团
PSINet Inc.，
和“m247 europe srl”（显然是标记错误了，应为“PrivateInternetAccess”）。

简单查了下发现这些ISP提供VPN或公共代理。感觉有些不对劲，实际上这三个ISP仅占我们全球流量的0.1％，与我们在这里看到的75％相比差太多了。

深入探究发现，我们的脚本每加载30000次时，在32％的情况下，脚本由于网络错误而无法与广告服务器联系；而在可以联系的情况下，服务器阻止了98％以上的欺诈嫌疑请求（由DoubleVerify检查）。

结论

绝大多数浏览器（99.9％）提供了使用URL.createObjectURL或crypto.getRandomValues生成随机UUID（v4）所需的API 。从主流浏览器的源代码中可以看到，这些函数的实现与服务器上的实现具有相似的质量。因此 它们竟然能生成那么多碰撞（每百万标识符中5个非唯一的），实在令人惊讶 。

仔细观察发现，这些API并不存在问题， 碰撞似乎主要（92％）归因于Googlebot 和其他一些与Google相关的服务。其余的碰撞（8％）来自边缘浏览器（PS Vita）、自动浏览器代理（HTML到PDF转换器）或与欺诈活动相关联，后者最有可能是来自中间人代理/proxy。

对于我们的用例，每百万中5个非唯一标识符的碰撞率是可以接受的，况且我们已经分析出了它们的成因。为了避免在系统中出现这种“噪音”，我们正在设置一个过滤器来过滤一组重复的UUID，阻止它们进入请求列表中。

致谢

感谢所有为本文及文中涉及到的工作做出贡献的人们！首先，Nicolas Crovatti相信我们可以在浏览器中生成唯一的标识符，相信我可以深入浅出写下这篇文章；Thomas Azemard帮助我分析了数据（尤其是Chrome Mobile 41和PS Vita！）；我的Format团队的同事们审阅了我的代码（特别感谢Benoit Ruiz审阅了它的无数次迭代！）和文章；我在SSP和Analytics（分析）团队中的同事们帮助完成了生产环境的实现；最后是Benjamin Davy，没有他就不会有这篇文章了。

原文链接 ：

https://medium.com/teads-engineering/generating-uuids-at-scale-on-the-web-2877f529d2a2

创作场景

如何在 Web 上大规模生成 UUID