6/26/2017

UUIDの歴史

Segmentブログより

今日、我々はユニークなID生成のためのGo言語のライブラリksuidをリリースした。ユビキタスなUUID標準からコアなアイデアを借用し、時間ベースの順序付けとよりフレンドリーな表現形式を追加している。このライブラリを検討する研究を行うにあたり、我々は多くの読者と共有したい人を引き付けるストーリーを見出した。

2台以上のマシンがネットワーク上で情報交換をしてからずっと、一意にモノを識別する方法が必要だった。

我々の現代のアイデアと共通点のある最初のネットワークは1870年代の初の電話交換の構築で始まった。この重要な転換点の前に、電気通信線は完全にポイントツーポイントだった。当時は驚くことだったが、高価で柔軟性や信頼性がなかった。大都市の道路の上をジグザグに銅線がほとんど滑稽な急増をもたらした。

Asset 5vkTaUDD

電信は主に政府や企業の重要な通信に使われていたが、電話機は非常に贅沢だった。電信の速度と比較して、手っ取り早いおしゃべりのために高価な銅線を結ぶことは信じられない迷惑なことだった。大衆に電気通信をもたらした重要な発明は交換機で、交換の創意を可能にし、これらの回線の有用性を大幅に高めた。それはネットワークで最初の一意の識別子をもたらした。それが電話番号である。

ネットワーク化されたコンピュータが登場した数十年後に早送りする。突然、モノの粒度は桁違いに細かくなった。

この転換点まで、電信線を介して送られたデータは短命だった。ネットワークは単なる土管だった。今や、オンデマンドでデータを格納して検索することが日課となり、それから世界を氾濫させるほどのデータの巨大な爆発が起こった。これらの新しい機能が与えられ、ネットワーク上のモノは、物理マシンから論理的なデータの一部にシフトした。

これらのネットワークは、データの一部を一意に扱う方法が必要だった。テレコム時代の中央管理型の古いシステムはスケールしなかった。これはネットワークのストレージ容量や検索数の増加がサイズに比例して増加することで数学的に必然性があった。このスケールは少しカオスをもたらした - 失敗やマシンの短命性がyak shaving問題からルーティンに移行する。データはもはや1か所には存在せず、ネットワーク上を自由に流れる。

コンピューティングのためのネットワーク・イベント

これは1980年代に我々にもたらされた。この時点では、コンピュータを使用してデータを共有することは、実際には物理的コンピュータの共有を意味していた。研究機関は、数百あるいは数千のダム端末を持つミニコンピュータや強力なメインフレームを使って情報を交換していた。

言い換えると、データはコンピュータと一緒に配置された。PCは、コンピューティングに革命をもたらしたが、ネットワーク機能が欠けていたため、非常に豪華な電卓だった。

1980年代に設立されたApolloコンピュータは、初期のワークステーション市場に参入した最初の企業の一つだった。ワークステーションは実際に最初にネットワーク化されたコンピュータだった。この言葉を使用するのは馬鹿げているように聞こえるが、当時はネットワーク技術のほとんどがまだ開花してないことを考えることを述べる価値はある。また、メインフレームの世界とは全く対称的で、データや計算は多くの相互接続されたコンピュータに分散されていた。このため、分散コンピューティングという考え方が主流になった。

Asset A0dS46c0

同時代のSunマイクロシステムズのように、Apolloは本当にフルスタックだった。その時代のハードウェアとソフトウェアは想像するユースケース向けに設計されていなかったため、全てゼロから構築する必要があった。ネットワークの非同期性やこれらのタスクの厳しい機能要求は、非常に能力の高いコンピュータを必要とした。マルチタスク、セキュリティ制御、ネットワーキング、大容量ストレージは全て非常に高価で、その時点のPCを含めるには実用的ではなかった。しかし、ワークステーションのビジョンのテーブルステークスはよく考えられていた。

ワークステーション市場での素晴らしい技術的なブームにも関わらず、これらのベンダー全てが同じ壁にぶつかっていた。ほとんどの開発者はネットワークについて何も知らなかったのだ。高価なワークステーションのためのビジネスケースを作るためにはプログラミング環境が必要だった。開発者は、それぞれの製品のネットワーキング機能をフルに活用できるアプリケーションを簡単に作る方法を必要としていた。

Apolloの答えはネットワーク・コンピューティング・システム(NCS)だった。NCSはオブジェクト指向プログラミングの考えを借用し、リモート・プロシージャー・コール(RPC)を中心に構築された。今ではほとんど使われなくなったが、このアプローチはApolloが望んでいた最終結果に達した。開発者は関数の呼び出し方法を理解し、オブジェクト指向が今や最も重要なプログラミング・パラダイムとなった。

1989年にRPCに関するNetwork Worldに掲載された記事では、Burlington Coat FactoryのMISディレクターが顕著な見解を述べている:「RPCを使って分散アプリケーションを作る方法を学ぶことは優れたプログラマなら一日あれば良い。」カチャカチャ・チーン。その年、Apolloはヒューレット・パッカードに約4億7600万ドル(インフレ調整でほぼ10億ドル)で売却された。

NCS用語でモノ(オブジェクト、インタフェース、オペレーション手法など)やエンティティは全て、ネットワーク環境で対処するために固有の識別子が必要である。標準的なフォンノイマン。アーキテクチャではこれは自明である: メモリまたは大容量ストレージのアドレスはこの目的に簡単に役に立つ。多くのコンピュータが独立して運用できる分散コンピューティング・モデルでは、これは自明ではなくなる。このユースケースの規模は、ネットワーク全体の調整は提案されていなかったことを意味する。それが遅過ぎて失敗する傾向にあった。

NCSは、UID(Universal Identifier)の概念を導入し、これがエンティティの固有の基本(primary)識別子として機能した。UIDは、全てのワークステーションのハードウェアに永久に埋め込まれた一意のホストIDとモノトニック・クロックを組み合わせた64ビットの数値である。このスキームでは、各ホストは1秒に何千回も識別子を生成することができ、スケーリングにはボトルネックがなく、常に世界で一意の識別子を保持できる。調整の唯一のポイントはApolloの工場だった。マシンはそれぞれの識別子でブランド化されていた。

初のUUID

Apolloがネットワーク・コンピューティング・アーキテクチャ(NCA)として、NCAの原則を標準化するアプローチを始めた時、既存のUIDのデザインが不十分であることが明らかになった。Apolloは全てのワークステーション・ベンダーがNCAで標準化する事を望んでおり、ワークステーションにホストIDを全て埋め込む限り、ビットサイズはベンダ毎に異なってしまう。

Apolloは20ビット使用し、百万大規模では十分だった。今日の規模では使い果たしてしまうが、Apolloは100億ドル以上のハードウェアを販売しなければならず、市場は桁違いに小さかった。

NCAはUIDデザインを元に作られたUUIDを導入したが、128ビットの番号空間に拡張する事で幅広いベンダーに対応した。そうして、UUIDが誕生した。この概念は非常に有用であり、NCAが遠い記憶になり、RPCが流行らなくなった後も、UUIDは依然として残り、最終的にはISOIETFITUによって標準化された。

Asset A4WDXnNV

読者はUUIDに多少精通しているとしても、今日もっとも使われる一般的なUUIDバージョン4とは内容が少し異なると認識するだろう。NCA UUIDには、48ビットのタイムスタンプ、16ビットの予約ビット、8ビットのネットワーク・アドレスファミリーのインジケータ、56ビットのホストIDがあった。現在のIETF標準で定義されているバージョン1の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/OS"オペレーティング・システムの一部としてApolloが導入した"Domain C"と呼ばれる言語を使っていることが分かる。Bitsaversのおかげで、私はPDF形式の1988年のリファレンス・マニュアルを見付けることができた。Domain Cは、いくつかの点でANSI Cを拡張している。最も重要な点は、\$が任意の識別子の最初の文字の後に現れることだ。

現時点で、ドル記号はダサいプログラミング言語の変数のシンタックス、通貨、自ら美化する音楽家によって使われている。それらの実際の目的を理解するため、まだ残っているコードとマニュアルを掘り下げてみた。

発見されたものを熟読した後、むしろ拍子抜けの結論に達した。明示的に述べてはいないが、これは単なるコーディング規約であると思われる。たとえ何が_\$の前に来ても特定のモジュールを識別する。_\$tは上記使われるuuid_\$tのようなデフォルトタイプを識別する。また、Apolloのプログラミング・スタイルに従ったライブラリの一部である識別子を簡単に特定する方法としても役立ったようだ。Apolloが特定のコーディング・スタイルに適用するためだけでCを拡張するので少し混乱した。

本題から逸れた。

NCA UUIDは標準化されたバージョン1のUUIDの基礎となった。これまでの繰り返し: 高精度なタイムスタンプとハードウェアベースの一意のホストIDが含まれていた。クロックスキューやタイムスタンプの繰り返しが発生する可能性があるため、システムクロックを使用して一意のシーケンス番号を確実に生成する事はできない。Apolloは、グローバルファイル(文字通り/tmp/last_uuid)を使って、プロセス間を調整する事でこれに対処した。

/*
 * C H E C K _ U U I D
 *
 * システム全体で、渡されたUUIDが前に生成されたUUIDと同じか古いかを確認する。
 * そうであれば、少し新しいものにする事。いずれにしても、UUIDを"最新のUUID"
 * ストレージに描き戻す。ストレージとしてファイルを使用しているシステムの場合、
 * ストレージに安全にアクセスできない場合は"プロセス毎"にチェックする事。
 */

ファイルは、全てのユーザやグローバルに書き込み可能な必要があった。特に安全ではないが、Apolloは幾分信頼できるネットワーク上で使用されるエンドユーザ向けワークステーションを販売していた。そして、少なくともそれは幾分妥当な決定だった。この技術は、IETF仕様のUUIDに引き継がれている。

私が見つける事ができたDCEの実装のためのソースコードは、Appleによって意外にも配布されている。Active DirectoryやWindowsベースのファイルサーバなどMicrosoftシステムとの通信に使用されているようだ。この実装は、Open Software Foundationが著作権を持ち、実際にUUID_NONVOLATILE_CLOCKと呼ばれるプリプロセッサ・フラグの後ろのステーブルストアで働くよう配置している。

#ifdef UUID_NONVOLATILE_CLOCK
    *clkseq = uuid__read_clock();     /* 不揮発性クロックを読む */
    if (*clkseq == 0)                 /* まだinit'dしていない??? */
    {
         *clkseq = true_random();     /* yes, ランダム設定 */
    }
#else
    /*
     * 揮発性クロックで、常に乱数を初期化する
     */
    *clkseq = true_random();
#endif

DCE RPCのUUID生成の不揮発性クロックを実際に実装するコードは、インターネット上には見付からなかった。しかし、ほとんどのLinuxディストリビューションのパッケージ・リポリジトリに含まれるlibuuidには、検証可能な不揮発性のUUIDクロック実装が含まれている。NCSと同じように、モノトニック性のためにファイルを利用するが、より賢明な/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に含める事はプライバシーやセキュリティへの脅威をもたらす。その不透明な性質を考えると、開発者はUUIDにマシンの識別情報が付いている可能性があることに自覚がない傾向にある。90年代後半にWindowsに影響を与えたメリッサ・ウィルスの作成者は、ウィルスのコードで見付かったUUIDのMACアドレスで特定された。信頼できないインターネットが支配的なネットワーキング・プラットフォームとなったため、信頼に依存するUUIDの生成は時代遅れとなった。これらの全ての懸念事項から、UUIDのハードウェア識別子を活用する事を断念している。

/*
 * これはuuid_generate_randomとuuid_generate_timeの一般的なフロント
 * エンドである。/dev/urandomが利用可能な場合にのみ、uuid_generate_random
 * を使用する。そうしないと、高品質なランダム性が得られない。
 */
void uuid_generate(uuid_t out)
{
    if (have_random_source())
        uuid_generate_random(out);
    else
        uuid_generate_time(out);
}

実際、libuuidのデフォルトパスは、1990年代に普及したUnixの亜種上で利用可能な/dev/(u?)randomでブロックデバイスを生成する擬似乱数を提供するシステム上で、時間ベースのUUIDを避けている。これはUUIDバージョン4の登場の要因となっている。これは、ランダムデータ(122ビット)のみを含んでいる。実装の単純さから広くあちこちに行き渡るようになった。

世界が衝突する時

私は最初にこれらのランダムなバージョン4 UUIDに出くわした時、衝突の脅威を心配していた。衝突がセキュリティ上の脅威を引き起こすような方法で使うべきではないが、開発者として私は、自分のシステムがそれらでつまづく事はないという信頼度が欲しい。

衝突への安全性の重要な側面はエントロピーのソース(源)である。信頼できるクラウド・コンピューティング環境に導入された現代のLinuxと、信頼できないモバイルデバイスの2つの一般的なケースを考えてみる。クラウドのLinuxのケースでは、/dev/urandomの形式で暗号的に安全な擬似乱数生成器(PRNG)が提供されている。これは暗号学者が承認し、エントロピーのソースはノンブロッキングである。

しかし、モバイルデバイスではほぼ何でもありの状態である: モバイルデバイスは信頼できない、ほとんどは上記シナリオで利用可能なものと同じくらいいいものはあるが、これらのデバイスのPRNGソースはあまりランダムではない。これらの品質を証明する方法がない事を考えると、モバイルPRNGに賭ける事は大きなギャンプルである。信頼性の低いモバイルデバイス上でのID生成は、興味深く、学術研究[1]の活発な分野である。ハードウェア割り込みによって生成されるノイズや暗号関数でのI/Oアクティビティのメタデータのようないくつかの発生源が混ぜ合わされる。

信頼性の高いRPNGデバイスを持つ環境でも、実装上のバグが衝突を招く可能性がある。ある特定のケースだが、OpenSSLがプロセスフォークをどのように扱うかの曖昧なバグが、純粋なPHP UUIDライブラリの衝突率を高くしている。これは少し大げさに聞こえるかも知れないが、明らかに衝突を作成するバグで、UUID実装でテストする価値がある。あなたが考えるよりも一般的である。システムレベルでは、DieharderはシステムのPRNGの品質を分析するために高く評価されたツールの一つである。

適切な環境が与えられれば、衝突リスクを無視できるほど低く、実行不可能に近い。この一意性に依存できるためには、十分大きなネームスペースを使って、他の非常に珍しいイベントが衝突よりもずっと早く起こるように可能性を大幅に高くする必要がある。

122個のランダムビットで、実行不可能な領域に衝突の可能性を持っていくためには、UUID(246)のペタサイズのパイルが必要である。その確率は約500億分の1である。それを可能にするには、数十億ペタバイトのUUIDが必要である。

実装のバグや設定ミスの脅威は、ランダムな衝突の脅威よりもはるかに重大である。適切に構成されたシステムのUUID衝突に関心のある人たちは、太陽フレア、熱核戦争、宇宙人の侵略のようなはるかの可能性の高い出来事を考えるのに費やす時間をたくさん取るだろう。念のため、システムがプロパティ設定されていることを確認してほしい。

時間は我々の味方である

場合によっては、UUIDバージョン1のタイムスタンプ部分は実際に非常に有益である。私がこれに初めて出くわしたのは、Apache Cassandraで"TimeUUID"と呼ばれるものだった。Cassandraの中で、TimeUUIDはタイムスタンプでソート可能で、大まかに時間順に並べ換える必要がある時に非常に有益だった。実装は、タイムスタンプとホストIDで一部のランダムビットをスワップする。ホストIDは、ノードのIPアドレスから導き出され、Cassandraクラスタ内でユニークな識別子を形成する。

実装はクロックスキュー(CASSANDRA-11991参照)の面で、一意性を侵害しようとすると、弱点に悩まされる。更に重大なのは、ホスト識別子情報がUUIDの中に埋め込まれていることで、我々が過去に何かを学んだのなら、それは素晴らしい考えではない。たとえ、これらのIDがローカル・ネットワーク・アドレスから生成されたとしても、セキュリティのベスト・プラクティスは間接的であっても、外部にこの情報を積極的に公開することを妨げる。

頼りない友人

時間別にIDをソートする能力は、タイムスタンプによるK-orderingの概念を大きく普及させたTwitterのSnowflakeの背後にある動機が大きかった[2]。Twitterはグローバルな調整なしに、作成時間で任意のツイートを並び替える方法が必要だった。IDの中にタイムスタンプを埋め込むことは、追加のタインムスタンプ・フィールドのオーバヘッド無しでこの機能を提供する。

K-orderingは大雑把にソートするよりも正確な方法である。Snowflakeでは、これらのIDを64ビットの数値空間に収める必要性によって、大量の構造が推進された。これはホストIDを割り当てるため、独立した強力な調整メカニズム(ZooKeeper)を使用し、シーケンスのチェックポイントを拡張する専用のID生成システムが必要である。

SnowflakeにインスパイアされたBoundaryのチームは2012年始めにFlakeをリリースした。専用ID生成サーバプロセスは使用するが、強力な調整メカニズムは必要ない。分散環境での重複を防ぐため、ハードウェア・アドレスから導き出された大きな128ビット番号空間と48ビットのホスト識別子を使用するという点で、FlakeはUUIDバージョン1に似ている。

辞書順に整理されているという点で、もともとUUIDバージョン1とは異なる。Flake IDのビットは、ユーザは書き込まれた場所に関係なくタイムスタンプで順序付けされると期待する方法で用意される。対照的に、CassandraはTimeUUIDから同じ動作を得るために、特定の照合ロジックを実装しなければならない。

残念ながら、Flake IDはこの情報が生成されたIDの中に埋め込まれるため、ホスト識別子情報をエンドユーザに後悔する可能性があるらしい。提供された実装は、クロックスキューの状況に対して防御するが、それらの一意性の特性は時計の進み具合に大きく依存する。

Flakeに含まれる特筆すべき機能の一つがBase62エンコードで、UUIDより非常にポータブル(移植が容易)な表現を提供する。UUIDの文字列表現は良いことが特徴の一つである。これは些細なことのように見えるかも知れないが、ダッシュ(-)文字の組み入れは、それらを使いにくくしてしまう。この例は、UUIDが検索エンジンでインデックス化される際、ダッシュがトークンの区切り文字として解釈される可能性が高い。Base62エンコードはこの落とし穴を回避し、バイナリ・エンコーディングの辞書順配列プロパティを保持する。

両方の長所をいかす

セグメントで内部システムを実装する際、チームはユニークな識別子を生成するためにUUIDバージョン4を使用し始めた。シンプルで、追加の依存性は必要なかった。

数週間後、これらの識別子の時間順に並べるという案件が浮上した。この要件は厳密ではなかった。初期の目的は、メッセージ識別子の範囲でキーが設定されているAmazon S3へのログアーカイブを有効にすることだった。既存のUUIDは、自然なグルーピング・プロパティではないメッセージのランダムな分散をもたらした。しかし、時間の矢をうまく利用するなら、S3で自然なグルーピングや実現可能なオブジェクト数という結果になる。

こうして、KSUIDが生まれた。KSUIDは、K-Sortable Unique IDentifierの略である。UUIDバージョン4のシンプルさとセキュリティをFlakeの辞書順列K-orderingプロパティと組み合わせたものである。KSUIDはこれらの目標を達成するためのいくつかの妥協している点があるが、我々のユースケースと他の多くのケースの両方で合理的だと考えている。

Asset XKt0hlkZ

KSUIDはUUIDとFlake IDよりも大きく、160ビット長である。32ビットのタイムスタンプと128ビットのランダムに生成されたペイロードで構成されている。一意性プロパティはホストの識別可能情報や時計に依存しない。その代わり、UUIDバージョン4のように大きな番号スペースでのランダムな衝突の不可能性に依存する。実装の複雑さを軽減するため、UUIDバージョン4の122ビットは128ビットに切り上げられ、追加の32ビット・タイムスタンプが考慮されていなくても、ボーナスとして64倍の衝突耐性を持つ。

タイムスタンプは1秒の解像度を提供し、これは幅広いユースケースで受け入れられていることが分かった。より高い解像度のタイムスタンプが望ましい場合、ペイロード・ビットがタイムスタンプ・ビットに置き換えることができる。高解像度のタイムスタンプのサポートは実装に含まれていないが、下位互換性がある。32ビットのタイムスタンプを使う実装は、より解像度が高いタインムスタンプを利用するKSUIDで安全に動作する。

100年以上の耐用年数を保証するカスタム・エポックが使われている。エポック・オフセット(14e8)こ人の目で素早く思い出し、素早く選び出されるよう簡単に選択できる。

Asset ZMiKWCG5

KSUIDは2つの固定長エンコーディング: 20バイトのバイナリ・エンコーディングと27文字のBase62エンコーディングがある。辞書順列順序付けプロパティはビッグエンディアンのバイトオーダーを使用してタイムスタンプをエンコードすることで提供される。Base62エンコーディングは、ASCII順の観点から辞書順列順序付けにマップするよう調整されている。

固定長エンコーディングは、より簡単でより安全な実装をもたらす。小さなボーナスとして、可変長データ型が追加のストレージ・オーバーヘッドにつながる。SQLデータベースなどでより効率的な場合がある。選択された形式に関わらず、KSUIDは時間で辞書順列順並び替えができる。文字列表現は完全に英数字であるため、UUIDのトークン化されたダッシュ問題を回避できる。

我々の実装

今日、我々はGoで書かれたKSUID実装をオープンソースで公開している。これは一般的な自然なインタフェースで実装されており、既存のコードベースへの統合や他のGoライブラリとの結合を容易にしている。KSUIDの生成と検査のためのコマンドラインツールが付属している。

$ ksuid
0o5Fri5Ia34BTFurJmkOf9T6S1e
$ ksuid 0o5Fs0EELR0fUjHjbCnEtdUwQe3

REPRESENTATION:

  String: 0o5Fs0EELR0fUjHjbCnEtdUwQe3
     Raw: 05A95E21D7B6FE8CD7CFF211704D8E7B9421210B

COMPONENTS:

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

謝辞

この投稿は、Apolloコンピュータに関する資料を集めてアーカイブしたBitsaversの努力なしには可能ではなかった。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)

Hacker News