すべてのUUIDをリストアップして検索できる「Every UUID V4」、そして直面した技術的課題とは？

2026年05月23日 12時00分 ウェブアプリ

UUID(Universally Unique Identifier)はプログラム中でオブジェクトを一意に識別するために使用される128ビットの数値であり、記事作成時点で使用されているUUIDには乱数のみで構成される「バージョン4」とミリ秒単位のUNIX時間＋乱数で構成される「バージョン7」があります。ゲームプログラマーの Nolen Royalty氏はすべてのUUIDバージョン4(UUID v4)をリスト管理したいという衝動に駆られウェブアプリ化しましたが、実現までに直面した技術的課題について自身のブログにて語っていました。

Every UUID V4

https://everyuuid.com/

Writing down (and searching through) every UUID · eieio.games https://eieio.games/blog/writing-down-every-uuid/#toc:missing-features-and-wrapping-up

◆レンダリング

「Every UUID V4」はウェブアプリとして実装されたためブラウザの制約がそのままアプリの制約に結びつく場合があります。膨大な数のUUIDを表示する方法として当初Nolen氏が検討していたのは「長大なdiv要素を作成してそこにUUIDを配置し、画面に表示する分のみをレンダリングする」というものでした。ただ残念ながらブラウザが把握できるスクロール位置には上限があり、一部のブラウザでは32ビット整数で保持されるため全く不十分であり、たとえスクロール位置を64ビットで保持できかつ1つのUUIDを表示する領域を1ピクセルに制限したとしても桁違いに多くのスクロール領域を保持する必要があることが判明しました。ChatGPTに解決策を尋ねても「無理」と返されたとのこと。

最終的な解決策としてNolen氏はブラウザ内でスクロールさせるのをあきらめ、代わりに画面の高さをブラウザの高さに固定し「仮想スクロール位置」をBigInt型で管理することにしました。代償として、本来であればブラウザ任せにできたであろうスクロール処理をすべて管理する必要が生じました。つまり、ユーザーがマウスホイール・タッチイベント・ホットキーなどのスクロール操作を行うたびに仮想スクロール位置を更新してUUIDをレンダリングしなければならず、さらにはカスタムスクロールバーの実装やスクロールのアニメーション処理などといったブラウザの機能の多くを再実装しなければなりませんでした。

◆順序付け

レンダリングの問題が解決してUUIDのリストを実際に確認できるようになると今度は「UUIDが興味深さの順に並ばない」という新たな問題が浮上しました。「興味深さの順」という表現はわかりにくいですが、Nolen氏の言葉を引用すれば「bb166283-2e09-4b72-ba32-70a43521c70eといったUUIDを見たいのであって決して00000000-0000-4000-8000-000000000000なんかを見たいわけではない」ということになります。Nolen氏が考えた順序付けの制約は以下の通りです。 ・UUIDの並び順に識別可能なパターンがあってはならない ・すべてのUUIDを一度だけ表示する ・UUIDを常に一貫した順序で表示する 上記の制約をプログラミングのレベルに落とし込むと、「整数インデックスをUUIDに『興味深い方法で』マッピングする必要がある」ということになります。

初めに検討されたのは線形合同法(LCG)を利用した疑似乱数生成でした。ただし、低位ビットのランダム性に問題があることと、何よりも大きな定数では中間ステップが非常に大きくなるため「ステップをスキップ」させる計算が困難であることが判明し採用は見送られました。 次に検討されたのが「エントロピーと全単射性」という概念でした。制約にある「すべてのUUIDを一度だけ表示する」は数学的に捉えると全単射写像、つまり各インデックスがただ一つのUUIDに対応しその逆も成り立つことを保証する写像です。Nolen氏は全単射性について考察を深めていくうちに、「エントロピーを加える操作が可逆であれば全単射性は維持される」ことに気付きました。得られた知見を元に考え出されたアプローチは以下の通りです。 ・入力データは122ビット(UUID v4のバージョン番号とバリアントビットを除いたビット数) ・以下の条件を満たしていればビットに対してエントロピーを増やすために何をしてもよい 　・最終的に、UUIDを作成するために必要なビット数である122ビットが正確に得られる 　・最終的に得られる122ビットから元の122ビットを復元できる

可逆なスクランブル処理とエントロピーの追加を実現するためにFeistel構造による暗号化が採用されました。Feistel構造は入力を半分に分割して2つのチャンクとし、一方のチャンクにラウンド関数を適用して他方のチャンクとXORすることで新たなチャンクを作成するプロセスを繰り返す構造を持ちます。Feistel構造の特筆すべき点はラウンド関数が純粋関数でさえあればどんな関数であっても可逆的であるということです。

Feistel構造を用いた暗号化でスクランブルされたビットをUUID v4のフォーマットにマッピングする作業は非常に困難な部分となりました。UUID v4は仕様上バージョンビット・バリアントビットを含むため下記のフォーマットを取ります。

UUID V4 format. Values:
X: any 4 bits
4: these 4 bits must be 0100 (4)
V: the top two bits here are 10; valid values are 8, 9, A, B

XXXXXXXX-XXXX-4XXX-VXXX-XXXXXXXXXXXX

全てのビットが仕様通りとなるようにするには、Feistel構造からの61ビットの左右チャンクをUUID構造に必要なビットに慎重にマッピングする必要がありました。「ビットいじり」はバグが発生しやすく困難を極めたものの最終的には期待通りの「一見ランダムに見えるものの一貫した順序でUUIDが並んだ非常によいリスト」が得られました。

◆検索 「UUIDを興味深さの順に並べる」という目標は達成しましたが、今度は別の問題が発生しました。UUIDが見た目上ランダムに順序付けられているため膨大なリストから目的のUUIDを見つけるのが困難になってしまいました。ミキシング関数は可逆であるため、特定のUUIDを検索する機能を追加するのであればUUIDからインデックスを逆算してインデックスが示す位置にジャンプするだけであり簡単に実装できました。しかしながら部分文字列による検索をしたいという要望にも対応するとなると話が変わってきます。表示領域に含まれるUUID程度であれば問題はないのですが、すべてのUUIDを対象にする場合は何兆件ものアイテムをメモリに置かなければならないため現実的ではありません。 最初のアプローチはUUID内の検索文字列が配置可能なパターン、つまりハイフン・バージョン番号・バリアントビットを考慮したパターンを生成することを試みました。

# valid patterns for "4AAA-"
XXXX4AAA-XXXX-4XXX-VXXX-XXXXXXXXXXXX
XXXXXXXX-4AAA-4XXX-VXXX-XXXXXXXXXXXX
XXXXXXXX-XXXX-4AAA-VXXX-XXXXXXXXXXXX

その後、配置可能なパターンを生成するためには入力インデックスのどのビットを設定する必要があるのかを決定しようとしました。しかしながらこの手法では暗号化により出力されるビットの依存関係があまりに複雑すぎるため挫折してしまいました。 最終的に実装された妥協策は以下のようなものとなりました。 ・検索文字列パターンに基づいて有効なUUIDを複数生成する ・生成したUUIDからインデックスを得る ・インデックスをもとに現在位置から最も近いUUIDを選択する この手法は完璧なものとは言えないながらも、ユーザーは部分文字列が一致するUUIDを順次辿っていくことが可能です。

◆今後の展望

Nolen氏はすべてのUUIDを「Every UUID V4」に集約することができ満足していますが、ソーシャル機能(友人による「いいね」機能・UUIDの共有機能・今人気のある「トレンドUUID」紹介機能など)をもっと充実させるべきだと考えています。それと同時に、ランダムな順序で並んだUUIDに対するより効率的な検索方法を探求することに興味を持っているとのこと。「Every UUID V4」の開発は膨大な数のUUIDにアクセスし検索する上での課題を浮き彫りにしたといえます。