【拓展】686- 如何在 Web 上大規模生成 UUID

作者 | Matthieu Wipliez

譯者 | 王強

策劃 | 李俊辰

你可以信任大家的浏覽器，并依靠它們來大規模生成全局唯一辨別符嗎？在 Teads 我們已經試過了，答案是肯定的，但也有幾點需要注意。本文介紹了我們所做的實驗以及在此過程中總結到的經驗。

本文最初釋出于 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）。

在浏覽器中生成一個 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()”實作：

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 提供 V** 或公共代理。感覺有些不對勁，實際上這三個 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，沒有他就不會有這篇文章了。