【拓展】686- 如何在 Web 上大規(guī)模生成 UUID
本文最初發(fā)布于 Medium 網(wǎng)站，經(jīng)原作者授權(quán)由 InfoQ 中文站翻譯并分享。
在 Web 頁面和電子商務(wù)站點上集成的第三方腳本普遍需要生成唯一標(biāo)識符，用于分析、營銷或廣告目的。
只要這些腳本的使用規(guī)模夠大，它們往往就會從 CDN（內(nèi)容交付網(wǎng)絡(luò)）加載，從而盡量減少響應(yīng)時間并減輕原始服務(wù)器的負(fù)載。
這意味著腳本是無法即時生成的。解決方法可以是（或曾經(jīng)是）讓 CDN 生成唯一標(biāo)識符并將其存儲在 cookie 中，但歐洲的 GDPR 和 ePrivacy 指令，或美國的 CCPA 等用戶隱私法規(guī)要求用戶明確同意后才能使用 cookie。
作為一家在線廣告公司，Teads 會收集并存儲關(guān)于每一種廣告體驗的數(shù)據(jù)。所謂廣告體驗，包括用戶訪問網(wǎng)頁并加載廣告腳本時發(fā)生的所有事件，從初始化廣告播放器開始，還包括對廣告服務(wù)器的請求和用戶動作（例如點擊）。要判斷一組事件是否等同于相同的體驗，我們就需要識別這種體驗的唯一性，并且要從一開始（即在調(diào)用廣告服務(wù)器之前）就識別出來。
直到今天，廣告服務(wù)器一直在生成唯一標(biāo)識符，并將其發(fā)送為廣告響應(yīng)的一部分。這是有問題的，因為響應(yīng)之前的事件沒有標(biāo)識符，所以你需要交叉引用數(shù)據(jù)以找出屬于一類的事件。服務(wù)端生成的標(biāo)識符幾乎可以保證是唯一的，并且在接觸生產(chǎn)系統(tǒng)之前，我們必須確保瀏覽器也可以生成通用的唯一標(biāo)識符。
UUID（通用唯一標(biāo)識符，也稱為 GUID—全局唯一標(biāo)識符）是一個 128 位值，可以由一臺計算機(jī)獨立生成（即無需與其他計算機(jī)通信），并且有極高的概率具備唯一性。UUID 被寫為以破折號分隔的十六進(jìn)制數(shù)字序列。
以下是 RFC 4122 定義的 UUID 第 4 版的示例：
UUID 最初是為分布式計算設(shè)計的，它是網(wǎng)絡(luò)計算系統(tǒng)（NCS）的一部分，迄今已用在了很多實用場景中。在 Windows 上，UUID 的應(yīng)用非常普遍，因為它們標(biāo)識了所有 COM 類（CLSID）和接口，因此所有基于 COM 的 Windows API 和應(yīng)用程序，以及許多 OS 對象（例如用戶、安全策略等）都使用 UUID。
實際上，除了上面展示的符合 RFC 的變體和保留的變體之外，可以指定的四個變體中，其他兩個分別是：
NCS 向后兼容（最高有效位是 0，數(shù)值 0 到 7）
Microsoft 向后兼容（最高有效位是 110，數(shù)值 C 和 D）。
UUID 的其他應(yīng)用有文件系統(tǒng)，例如 GUID 分區(qū)表（UEFI 的一部分），或在數(shù)據(jù)庫中用于取代傳統(tǒng)整數(shù)作為記錄主鍵。在互聯(lián)網(wǎng)廣告的上下文中，它們經(jīng)常用于唯一地標(biāo)識在 Web 上查看廣告的用戶。例如，互動廣告局（IAB）建議將 UUID 用于 IDFA（廣告標(biāo)識符）/AAID（Android 的 Google Advertising ID），以唯一地標(biāo)識移動用戶。
UUID 版本 1 和 2 使用計算機(jī) MAC 地址、100 納秒精度的當(dāng)前 UTC 時間戳和一個用來增強(qiáng)唯一性的 100ns 間隔“時鐘序列”（可單調(diào)遞增或隨機(jī)）來組合生成標(biāo)識符
帶有網(wǎng)絡(luò)控制器的設(shè)備都應(yīng)該有唯一的 48 位 MAC 地址，于是不可能有兩個設(shè)備生成相同的 UUID。但這也是這些版本的弱點，因為這意味著此類 UUID 可用來確定用戶的身份。請注意，在用戶設(shè)備上生成 UUID 時才會出現(xiàn)這個問題，但服務(wù)器上則不會，例如 MySQL 就使用了 UUID v1。
UUID 版本 3 和 5 是通過對字符串進(jìn)行哈希處理（v3 使用 MD5，v5 使用 SHA-1）來生成標(biāo)識符的，并且由于哈希是確定性的，因此輸出與輸入都是唯一的。如果你想將 URL 用作唯一標(biāo)識符，那么這種方法就會很有用，只是它們無法滿足我們的需求。
最后，第 4 版中除變體和版本以外的所有位都是隨機(jī)的，總計 122 個隨機(jī)位。這樣這些 UUID 就不會攜帶任何個人身份信息。需要注意的是，要獲得 UUID 提供的唯一性和不可預(yù)測性保證，我們應(yīng)該使用加密安全的隨機(jī)數(shù)生成器（CSRNG）。
如前所見，只要我們有 CSRNG，那么 UUID 第 4 版就是最佳選項。這樣首先就排除掉了老字號的 Math.random，因為其實現(xiàn)是與瀏覽器相關(guān)的，并且不能保證加密使用的安全性。在實踐中，主流瀏覽器使用 Xorshift 偽隨機(jī)數(shù)生成器的一個變體，它的性能在偽隨機(jī)數(shù)生成器（PRNG）中算是很不錯的。
CSRNG 和 PRNG 之間的區(qū)別在于 PRNG 使用單個種子，因此具有完全確定性，無法根據(jù)先前生成的數(shù)字預(yù)測 CSRNG 的輸出。
2017 年發(fā)布的 Web Cryptography API（或稱 Crypto API）定義了 getRandomValues 函數(shù)。根據(jù) caniuse 的說法，有 96.6％的用戶使用的瀏覽器支持 Crypto。在我們的用戶中這一支持率甚至接近 99.9％，換句話說 Crypto API 幾乎可以用在任何地方（甚至包括邊緣設(shè)備，例如 PS Vita）。這是一個重要的考慮因素：我們擁有 15 億用戶，意味著存在超過一百萬種 OSx 瀏覽器 x 瀏覽器版本 x 設(shè)備的組合，因此我們必須確信所有用戶都可以毫無問題地運(yùn)行我們的代碼。
crypto.getRandomValues(new?Uint8Array(16))const?url = URL.createObjectURL(new?Blob())
url.substring(url.lastIndexOf('/') + 1)File API 并未指定應(yīng)使用哪個版本的 UUID 或如何生成它們。實際上，基于 Chromium 的瀏覽器（Chrome 和 Edge）和 WebKit 會使用 Crypto 實現(xiàn)來生成隨機(jī)數(shù)字，然后設(shè)置 / 清除一些位來創(chuàng)建 v4 版的 UUID。Firefox 會調(diào)用 OS 級函數(shù)（如果存在，在 Windows 上為 CoCreateGuid，在 macOS 上為 CFUUIDCreate），否則會回退使用 Chromium 和 WebKit 所用的 Crypto。最后，瀏覽器依賴 OS 直接提供隨機(jī)數(shù)，或收集熵并定期饋送到 PRNG 來實現(xiàn) Crypto.getRandomValues，從而實現(xiàn)加密安全性（CSPRNG）。
我們的腳本已集成在了數(shù)以千計的網(wǎng)站上，這些網(wǎng)站往往會包括其他第三方腳本，并且每個腳本都可以重新定義 / 超載大多數(shù) JavaScript 函數(shù)。我們發(fā)現(xiàn)有些腳本正在超載 Math.random 函數(shù)以始終返回相同的值，而另一些腳本正在重新定義 window.URL 屬性以返回當(dāng)前頁面的 URL。
有兩種方法可以在不受第三方腳本影響的上下文中運(yùn)行腳本：iframe 和 Web Worker。相比之下 Web Workers 更好用，因為它們實例化更快，畢竟它們僅創(chuàng)建新的 JavaScript 執(zhí)行上下文，而不是完整的 DOM。
我們實現(xiàn)了一項功能，它可以使用 Crypto 生成 UUID（可以回退到 Math.random）并將其發(fā)送到我們的服務(wù)器，然后設(shè)置 A/B 測試。這樣我們就能檢查大多數(shù)瀏覽器是否確實支持 Crypto，并且確保我們的代碼沒有任何問題，這個過程中不會影響大多數(shù)用戶。這個功能的 A/B 測試是在當(dāng)前幀運(yùn)行的，可以的話會運(yùn)行在 Web Worker 中。
對于已激活“uuid worker”功能的用戶，我們測量出其中有 50％的設(shè)備實例化一個 worker 需要花費 200 毫秒以上的時間。在我們的案例中，因為我們想在這一過程中首先生成 UUID，所以這么大的延遲是不可接受的。然后，我們切換到了基于 File API 的實現(xiàn)，使用 Crypto 作為回退，并使用 Math.random 作為最后的手段。
我們發(fā)現(xiàn)的第一個問題是 每千個請求中有將近 2 個請求帶有重復(fù)的 UUID 。這可不是什么小事情
從理論上講，如果你連續(xù) 85 年每秒產(chǎn)生 10 億個 UUID，就有 50％的機(jī)會發(fā)生一次碰撞。以我們的情況來說，我們每天才生成約 10 億個 UUID，因此理論上應(yīng)該可以安全使用約 700 萬年。
差異來自何處？
不同之處在于 我們正在查看的是重復(fù)的請求 ，而不是碰撞的標(biāo)識符。重復(fù)的請求來自同一客戶端，并被發(fā)送到服務(wù)器一次或多次，如下所示。這背后可能有多種原因，我們發(fā)現(xiàn)這些重復(fù)請求中絕大多數(shù)都是由第三方腳本中的錯誤引起的。
另一方面，當(dāng)一個以上的客戶端使用給定的標(biāo)識符時，發(fā)生的才是 碰撞 。在下面的模式中，客戶端 1 和 3 之間發(fā)生了碰撞，因為它們都生成了以“0a87341d”開頭的相同（紅色）UUID。請記住，從理論上講，每天生成十億個 UUID，則“每 700 萬年才會發(fā)生一次”這種事件。
在我們刪除了重復(fù)的請求（來自相同的 User-Agent、IP 地址哈希、引用等）后， 具有碰撞 UUID 的請求數(shù)量大約是每 10,000 個請求中有 2 個 。但這還不是全部。當(dāng)查看標(biāo)識符的數(shù)量時，我們在 每百萬個標(biāo)識符中能遇到 5 個非唯一的 。
40 倍的差距。這是非常出乎意料的：就算能遇到碰撞，你也會認(rèn)為是兩個非常不走運(yùn)的用戶才能撞在一起，是極為罕見的事情；但實際上，在一天之內(nèi) 全世界有成千上萬個不同的客戶端在生成相同的 UUID 。請記住，瀏覽器提供的 CSPRNG 本質(zhì)上與服務(wù)器上用的是同樣的水平。那么這里到底發(fā)生了什么？
如果我們接收所有帶有碰撞 UUID 的請求，然后深入觀察瀏覽器的 User-Agent，就會看到：
這些請求中 有差不多三分之一是由 Chrome Mobile 41.0 生成的 。這太讓人驚訝了，畢竟 Chrome Mobile 41 已有 5 年以上的歷史。這些請求的另一個共同點是發(fā)出請求的城市 IP：將近 三分之二來自山景城 。Chrome Mobile 41.0 發(fā)出的所有請求（100％）均來自山景城（Mountain View）。你能想起來一家總部設(shè)在那里的公司嗎？
并不是只有我們觀察到了這個結(jié)果：在有關(guān)瀏覽器中 UUID 生成的 StackOverflow 問題中，其中一個答案提到 Googlebot 是碰撞的主要來源。其中一個問題提到 Googlebot 具有“偽”Math.random 和“newDate()”實現(xiàn)：
https://github.com/segmentio/analytics.js/issues/459
還有一個問題也提到了重復(fù)的事件標(biāo)識符：
https://github.com/snowplow/snowplow-javascript-tracker/issues/499#issuecomment-263868850
雖然沒有聲明，但托管在山景城的 Chrome Mobile 41 實際上是 Googlebot 或其他 Google 服務(wù)。這種事情應(yīng)該不會再發(fā)生了，因為 Google 在 2019 年 12 月宣布將開始更新 Googlebot，以在桌面和移動設(shè)備上使用最新版本的 Chrome。
但這還不是全部。與在山景城中生成的標(biāo)識符關(guān)聯(lián)的請求占 UUID 碰撞的 92% 。生成剩余 8％請求的瀏覽器 User-Agent 圖像如下所示：
EvoPdf、WnvPdf 和 HiQPdf 是.NET 的 HTML 到 PDF 轉(zhuǎn)換庫，很可能它們在爬取帶有我們腳本的頁面時多次重復(fù)使用了相同的標(biāo)識符。PS Vita 瀏覽器生成的 UUID 碰撞似乎是合法的（與欺詐活動無關(guān)），并且很可能是由于加密實現(xiàn)不佳所致：沒有瀏覽器生成的 UUID 會與 PS Vita 生成的相碰撞。可能他們的 Crypto 是一個弱 PRNG。
最后，Internet Explorer 的情況不太像是 Crypto 實現(xiàn)水平不足，而更像是被惡意腳本濫用了。UUID 碰撞的請求中有 75％來自 3 個 ISP：
Nobis 科技集團(tuán)
PSINet Inc.，
和“m247 europe srl”（顯然是標(biāo)記錯誤了，應(yīng)為“PrivateInternetAccess”）。
簡單查了下發(fā)現(xiàn)這些 ISP 提供 VPN 或公共代理。感覺有些不對勁，實際上這三個 ISP 僅占我們?nèi)蛄髁康?0.1％，與我們在這里看到的 75％相比差太多了。
深入探究發(fā)現(xiàn)，我們的腳本每加載 30000 次時，在 32％的情況下，腳本由于網(wǎng)絡(luò)錯誤而無法與廣告服務(wù)器聯(lián)系；而在可以聯(lián)系的情況下，服務(wù)器阻止了 98％以上的欺詐嫌疑請求（由 DoubleVerify 檢查）。
絕大多數(shù)瀏覽器（99.9％）提供了使用 URL.createObjectURL 或 crypto.getRandomValues 生成隨機(jī) UUID（v4）所需的 API 。從主流瀏覽器的源代碼中可以看到，這些函數(shù)的實現(xiàn)與服務(wù)器上的實現(xiàn)具有相似的質(zhì)量。因此 它們竟然能生成那么多碰撞（每百萬標(biāo)識符中 5 個非唯一的），實在令人驚訝 。
仔細(xì)觀察發(fā)現(xiàn)，這些 API 并不存在問題， 碰撞似乎主要（92％）歸因于 Googlebot 和其他一些與 Google 相關(guān)的服務(wù)。其余的碰撞（8％）來自邊緣瀏覽器（PS Vita）、自動瀏覽器代理（HTML 到 PDF 轉(zhuǎn)換器）或與欺詐活動相關(guān)聯(lián)，后者最有可能是來自中間人代理 /proxy。
對于我們的用例，每百萬中 5 個非唯一標(biāo)識符的碰撞率是可以接受的，況且我們已經(jīng)分析出了它們的成因。為了避免在系統(tǒng)中出現(xiàn)這種“噪音”，我們正在設(shè)置一個過濾器來過濾一組重復(fù)的 UUID，阻止它們進(jìn)入請求列表中。
感謝所有為本文及文中涉及到的工作做出貢獻(xiàn)的人們！首先，Nicolas Crovatti 相信我們可以在瀏覽器中生成唯一的標(biāo)識符，相信我可以深入淺出寫下這篇文章；Thomas Azemard 幫助我分析了數(shù)據(jù)（尤其是 Chrome Mobile 41 和 PS Vita！）；我的 Format 團(tuán)隊的同事們審閱了我的代碼（特別感謝 Benoit Ruiz 審閱了它的無數(shù)次迭代！）和文章；我在 SSP 和 Analytics（分析）團(tuán)隊中的同事們幫助完成了生產(chǎn)環(huán)境的實現(xiàn)；最后是 Benjamin Davy，沒有他就不會有這篇文章了。
https://medium.com/teads-engineering/generating-uuids-at-scale-on-the-web-2877f529d2a2
回復(fù)“加群”與大佬們一起交流學(xué)習(xí)~
