【拓展】686- 如何在 Web 上大规模生成 UUID
本文最初发布于 Medium 网站，经原作者授权由 InfoQ 中文站翻译并分享。
在 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）。
如前所见，只要我们有 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.getRandomValues(new Uint8Array(16))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。
我们实现了一项功能，它可以使用 Crypto 生成 UUID（可以回退到 Math.random）并将其发送到我们的服务器，然后设置 A/B 测试。这样我们就能检查大多数浏览器是否确实支持 Crypto，并且确保我们的代码没有任何问题，这个过程中不会影响大多数用户。这个功能的 A/B 测试是在当前帧运行的，可以的话会运行在 Web Worker 中。
对于已激活“uuid worker”功能的用户，我们测量出其中有 50％的设备实例化一个 worker 需要花费 200 毫秒以上的时间。在我们的案例中，因为我们想在这一过程中首先生成 UUID，所以这么大的延迟是不可接受的。然后，我们切换到了基于 File API 的实现，使用 Crypto 作为回退，并使用 Math.random 作为最后的手段。
我们发现的第一个问题是 每千个请求中有将近 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()”实现：
https://github.com/segmentio/analytics.js/issues/459
还有一个问题也提到了重复的事件标识符：
https://github.com/snowplow/snowplow-javascript-tracker/issues/499#issuecomment-263868850
虽然没有声明，但托管在山景城的 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
回复“加群”与大佬们一起交流学习~
