首頁 > 軟體

UUID簡史

2020-06-16 17:09:21

今天，我們發布了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, clock sequence, and node ID)
      back to the stable store.

   o  Release the global lock.

   o  Format a UUID from the current timestamp, clock sequence, 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活動源資料等不同來源與密碼學函數結合在一起。

然而在移動裝置上幾乎一切都不同了：移動裝置無法被信任。雖然大部分移動裝置也可以實現上文提到的技術，但實際上此類裝置的PRNG源並非徹底隨機的。由於無法對此類特徵提供保證或證明，因此對移動裝置PRNG的信賴無疑像是一場豪賭。信任度低的移動裝置生成的ID，這一話題正在受到學術界的關注，並已成為一個積極研究的領域[1]。

就算具備可信賴PRNG裝置的環境，具體實現方面的Bug也可能導致碰撞。例如曾經有這樣一個例子：OpenSLL在處理進程Fork過程中存在一個隱蔽的Bug，會導致純PHP的UUID庫產生較高碰撞率。雖然聽起來不太嚴重，但最好針對自己的UUID實現對各種明顯會造成碰撞的Bug進行測試，實際出現的概率可能遠超你想象。在系統層面上可以使用dieharder，這是一個非常著名的系統PRNG品質分析工具。

只要具備妥善的環境，碰撞風險就會無限降低，甚至趨近於不可能。為實現這樣的唯一性，必須使用足夠大的號碼空間，以確保其他極為罕見的事件能夠先於碰撞首先發生。

因為共包含122個隨機位，UUID的數量總規模高達PB級別（2^46），這也進一步將碰撞的可能性降低至大約五百億分之一。需要生成數十億個PB的UUID才有可能產生碰撞。

相比隨機碰撞，實現方面的Bug和錯誤的設定往往風險更高。對UUID碰撞有所顧慮的人，如果能使用妥善設定的系統，那麼完全不需要在這個問題上太過擔心，此時出現碰撞的概率甚至遠遠小於太陽耀斑爆發、熱核戰爭，以及外星人入侵等事件。請務必對系統進行妥善正確的設定。

時間問題還是由我們來考慮吧

某些情況下，第1版UUID的時間戳元件還是相當有用的。我在使用Apache Cassandra時第一次意識到這一點。該產品中，他們把它稱作“TimeUUID”。在Cassandra中，TimeUUID可按照時間戳排序，如果希望按照時間進行粗略排序，這個功能會比較有用。這種實現會對部分隨機位以及時間戳和主機識別符號進行互換。主機ID派生自節點IP地址，同時該IP地址還組成了Cassandra叢集所用的唯一識別符號。

如果通過時鐘偏差攻陷這種技術的唯一性，那麼這種實現方式也存在一些弱點（可參閱CASSANDRA-11991）。更重要的是，主機可辨識資訊已經嵌入在UUID中，但是從過去的經驗來看，這種做法並不怎麼好。就算這些ID是通過本地網路地址派生而來的，安全方面的最佳實踐也不推薦主動將此類資訊暴露給外界，哪怕是間接暴露。

那些古怪的友人們

按照時間對ID排序的能力可能是Twitter開發Snowflake的最大動機，正是Twitter的這項技術使得按照時間戳進行K-ordering排序的概念變得人盡皆知[2]。Twitter需要通過某種方式在無需進行全域性協調的情況下，按照建立時間對任意一批推文進行排序。通過在ID中嵌入時間戳，即可在不需要無謂地建立一個時間戳欄位的情況下獲得這種功能。

K-ordering是一種更精確的粗略排序方式。Snowflake中有大量設計是由將這些ID融入64位元號碼空間的需求推動的，例如需要通過專用的ID生成伺服器，使用一套單獨的強協調機制（ZooKeeper）分配主機ID並儲存序列檢查點。

受到Snowflake啟發的Boundary團隊在2012年初發布了Flake。該技術也使用了專用的ID生成伺服器進程，但不需要強協調機制。Flake與第1版UUID的相似之處在於，需要使用規模更大的128位元號碼空間，以及一個通過硬體地址派生而來的48位元主機識別符號，藉此預防分散式環境中出現的重疊問題。

該技術與第1版UUID的不同之處在於使用了不同的字典排序（Lexicographic ordering）構造。Flake ID的位會通過一種排列方式確保使用者無論寫入到那裡，都可以保證按時間戳排序。而Cassandra必須實現一種特定的順序邏輯才能對TimeUUID提供類似行為。

由於要將主機標識資訊嵌入到生成的ID中，導致Flake ID會將此類資訊暴露給終端使用者。雖然具體實現方面通過相應機制可防範時鐘偏差，但這種方式的唯一性嚴重依賴於時鐘走時。

Flake有個值得一提的特性：Base62編碼，該技術相比UUID能提供更“可移植”的表達（Representation）。UUID字串的表達是其最大的劣勢之一，雖然看起來可能並不重要，但由於使用了連字號（-）字元，導致UUID的適用性有所降低。例如當使用搜尋引擎對UUID建立索引時，連字號可能會被理解為分隔符。Base62編碼可避免這種問題，維持二進位制編碼的字典排序屬性。

兩者的強強聯合

Segment在實現一個內部系統的過程中，我們團隊最開始使用了第4版UUID來生成唯一識別符號。這種做法更簡單，不會造成額外的依賴性。

但在幾周後遇到了一個新需求，必須按照出現時間對這些識別符號進行排序。這個需求並不十分嚴格：最初目的只是為了方便將紀錄檔歸檔至Amazon S3，並在那裡根據訊息識別符號的範圍實現鍵控（Keyed）。現有的UUID會導致訊息隨機分布，無法自然地進行恰當分組。然而如果能充分利用時間箭頭（Arrow of time）功能，即可實現自然分組，並為S3中的物件編製更可行的號碼。

因此我們開發了KSUID。KSUID是K-Sortable Unique Identifier（可K排序的唯一識別符號）的縮寫，該技術將第4版UUID的簡化性和安全性與Flake K-ordering的字典屬性結合在了一起。KSUID通過一定的取捨實現了我們的目標，但我們認為這些取捨無論對自己還是別人來說，都是合理的。

(點選放大影象)

KSUID比UUID和Flake ID更大，共包含160位元。其中包含一個32位元時間戳和一個128位元隨機生成載荷。該技術的唯一性不依賴任何主機可辨識資訊或時鐘，而是與第4版UUID類似，依賴如此大規模號碼空間內出現隨機碰撞的不可能性。為了降低實現工作的複雜度，我們將122位的第4版UUID四捨五入至128位元，此舉也使其抗碰撞能力提升了64倍，而這還是在不考慮額外增加的32位元時間戳的情況下。

時間戳精度為1秒，我們認為這樣的精度對大部分用例已經足夠了。如果需要更高精度的時間戳，可將部分載荷位改為更長的時間戳位。雖然我們的實現並未對更高精度的時間戳提供支援，但提供了向後相容性。任何使用32位元時間戳的實現均可安全地通過KSUID使用更高精度的時間戳。

該技術使用了“自定義”的紀元（Epoch），確保可在上百年的時間裡始終有效。此外這個紀元還使用了偏移量（14e8），以確保更易記，同時對人眼來說也更易讀。

(點選放大影象)

KSUID提供了兩種定長編碼方式：一種20位元組的二進位制編碼，以及一種27字元的Base62編碼。通過使用大端位位元組排序（Big endian byte ordering）對時間戳進行編碼，可實現字典排序屬性。Base62編碼通過調整可將字元的字典排序與對應的ASCII排序進行對映。

定長編碼在實現方面更簡單也更安全。此外作為一個額外的“福利”，這種方式有時候也更高效，例如在SQL資料庫中，可變長度資料型別通常會造成額外的儲存開銷。無論選擇哪種格式，KSUID都可以按照時間進行字典排序，字串的表達完全基於字母數位（Alphanumeric），可避免UUID中連字元的標記化（Tokenized）問題。

我們的具體實現

今天，我們正式開源了自己的KSUID實現。KSUID使用Go語言開發，提供了符合主流習慣的介面，因此可輕鬆整合於現有程式碼庫，並配合其他Go語言庫使用。KSUID還包含了用於生成和檢查KSUID的命令列工具。

$ ksuid
0o5Fri5Ia34BTFurJmkOf9T6S1e
$ ksuid 0o5Fs0EELR0fUjHjbCnEtdUwQe3
REPRESENTATION:

  String: 0o5Fs0EELR0fUjHjbCnEtdUwQe3
     Raw: 05A95E21D7B6FE8CD7CFF211704D8E7B9421210B

COMPONENTS:

       Time: 2017-05-16 18:49:21 -0700 PDT
  Timestamp: 94985761
    Payload: D7B6FE8CD7CFF211704D8E7B9421210B

致謝

本文的撰寫得到了來自Bitsavers的幫助，他們收集並整理了有關Apollo Computing的素材。此外還要感謝Albert Strasheim、Calvin French-Owen、Evan Johnson、Peter Reinhardt，以及Tido Carriero提供的深度見解和反饋。

註腳

[1] P. Jesus, C. Baquero, and P. Almeida: ID Generation in Mobile Environments (2006)

[2] T. Altman, Y. Igarashi: Roughly sorting: sequential and parallel approach (1989)

本文最初發布於Segment官方部落格，原作者：Rick Branson。經授權由InfoQ中文站翻譯並分享。閱讀英文???文：A Brief History of the UUID。

本文永久更新連結地址：http://www.linuxidc.com/Linux/2017-08/146242.htm


相關文章
IT145.com E-mail:sddin#qq.com