UUIDとULIDについて深く掘り下げる

先日、HBチームがチャットをしていて、開発オペレーションマスターのBenが、特定のシステムにUUIDではなくULIDを使用したいと言っていました。

他のベテランエンジニアと同じように、私の反応は、コミットメントのないものをつぶやいてから、Googleに忍び寄って、ULIDが何であるかを理解しようとすることでした。

2時間後、私は千ヤードの凝視で現れ、一意の識別子の世界は想像以上に大きく、不思議であることに気づきました。

ULIDの使用を開始する前に、基本に戻ってUUIDとは何かについて説明しましょう。

「通常の」IDの問題は何ですか？

データベースを使用するほとんどのWebアプリケーションは、デフォルトで自動的に増加する数値IDになります。たとえば、Railsでは次のような動作が見られる場合があります：

p1 = Person.create!
p1.id
# => 1

p2 = Person.create!
p2.id
# => 2

データベースは、レコードの作成時に増分するカウンターを格納するため、シーケンシャルIDを生成できます。

このパターンは、データベースの外部でも見られます。 IDを手動で割り当てる必要がある場合があり、カスタムカウンターをRedisインスタンスに保存する場合があります。

シーケンシャルIDは、少量のユースケースでは簡単に実装できますが、ボリュームが増えると問題が大きくなります。

• 各挿入はIDを受け取るために並んで待機する必要があるため、レコードを同時に作成することはできません。
• シーケンシャルIDをリクエストすると、ネットワークのラウンドトリップが必要になり、パフォーマンスが低下する可能性があります。
• シーケンシャルIDを提供するデータストアをスケールアウトすることは困難です。異なるサーバーのカウンターが同期しなくなることを心配する必要があります。
• カウンターのあるノードが単一障害点になるのは簡単です。

シーケンシャルIDもデータを漏洩しますが、これは場合によっては問題になる可能性があります：

• 自分に属していない可能性のあるリソースのIDを簡単に推測できます。
• ユーザーを作成し、そのIDが20の場合、サービスには20人のユーザーがいることがわかります。

UUIDはWebスケールです

UUIDは、シーケンシャルIDとは少し異なります。これらは128ビットの数値であり、通常は32桁の16進数で表されます。

123e4567-e89b-12d3-a456-426655440000

UUIDは、RFC 4122で定義されている特定のアルゴリズムを使用して作成されます。これらは、シーケンシャルIDで発生する問題の多くを解決しようとします。

• ノード間の共有状態や調整なしで、任意の数のノードでUUIDを生成できます。
• シーケンシャルIDよりも推測が少し難しくなります（詳細は後で説明します）
• データセットのサイズを明かすことはありません。

問題は、2つのノードが独立して同じIDを生成する可能性がわずかにあることです。このイベントは「衝突」と呼ばれます。

UUIDの多くのフレーバー

RFC 4122で定義されているUUIDアルゴリズムには5つのタイプがあります。これらは、次の2つのカテゴリに分類されます。

• 時間とランダム性に基づく アルゴリズムは私たちが議論してきたものです。その結果、実行ごとに新しいUUIDが生成されます。
  • タイプ4 ：ランダムに生成されたID。おそらく、新しいコードに対する最善の策です。
  • タイプ1 ：IDには、ホストのMACアドレスと現在のタイムスタンプが含まれます。これらは推測が簡単すぎるため、非推奨になりました。
  • タイプ2 ：これらは珍しいようです。これらは、時代遅れのRPC用に設計されているようです。
• 名前ベースのアルゴリズム 少し違います。これらは、特定の入力セットに対して常に同じUUIDを生成します。
  • タイプ5 ：SHA-1ハッシュを使用してUUIDを生成します。推奨。
  • タイプ3 ：MD5ハッシュを使用しますが、MD5の安全性が低すぎるため、非推奨になりました。

Rubyでは、uuidtoolsを介してUUIDを生成できます。 宝石。謎のタイプ2を除くすべてのタイプをサポートします;

# Code stolen from the uuidtools readme. :)
require "uuidtools"

# Type 1
UUIDTools::UUID.timestamp_create
# => #<UUID:0x2adfdc UUID:64a5189c-25b3-11da-a97b-00c04fd430c8>

# Type 4
UUIDTools::UUID.random_create
# => #<UUID:0x19013a UUID:984265dc-4200-4f02-ae70-fe4f48964159>

# Type 3
UUIDTools::UUID.md5_create(UUIDTools::UUID_DNS_NAMESPACE, "www.widgets.com")
# => #<UUID:0x287576 UUID:3d813cbb-47fb-32ba-91df-831e1593ac29>

# Type 5
UUIDTools::UUID.sha1_create(UUIDTools::UUID_DNS_NAMESPACE, "www.widgets.com")
# => #<UUID:0x2a0116 UUID:21f7f8de-8051-5b89-8680-0195ef798b6a>

ULIDへの移行

注： このブログ投稿の元のバージョンでは、ULID仕様へのリンクを忘れていました。ここにあります。 Rubyや他の言語での実装へのリンクを提供します。

ULIDは、一意の識別子に対する便利な新しい考え方です。最も明らかな違いは、外観が少し異なることです。

01ARZ3NDEKTSV4RRFFQ69G5FAV

これらは、base32でエンコードされた2つの数値で構成されています。 UNIXタイムスタンプの後に乱数が続きます。仕様で定義されている構造は次のとおりです。

01AN4Z07BY      79KA1307SR9X4MV3

|----------|    |----------------|
 Timestamp          Randomness
   48bits             80bits

この構造は魅力的です！思い出してください。UUIDはタイムスタンプまたはランダム性のいずれかに依存していますが、ULIDはとの両方のタイムスタンプを使用します ランダム性。

その結果、ULIDにはいくつかの興味深い特性があります：

• 辞書式順序（つまり、アルファベット順）で並べ替えることができます。
• タイムスタンプはミリ秒単位で正確です
• UUIDよりもきれいです:)

これらはいくつかのクールな可能性を開きます：

• データベースを日付でパーティション化する場合は、ULIDに埋め込まれたタイムスタンプを使用して正しいパーティションを選択できます。
• ミリ秒の精度が許容できる場合は、個別のcreated_at列の代わりにULIDで並べ替えることができます。

考えられる欠点もいくつかあります：

• タイムスタンプを公開することがアプリケーションにとって悪い考えである場合、ULIDは最良のオプションではない可能性があります。
• sort by ulid サブミリ秒の精度が必要な場合、このアプローチは機能しない可能性があります。
• インターネットによると、一部のULID実装は防弾ではありません。