ハクソク

世界を動かす技術を、日本語で。

すべてのGitHubオブジェクトには2つのIDがあります

93日前原文(www.greptile.com)

概要

  • GitHubのAPIには2種類のIDシステムが存在
  • GraphQLのnode IDとWeb URL用のdatabase IDの違い
  • node IDからdatabase IDを簡単に抽出する方法の発見
  • MessagePackによる新IDフォーマットの解読
  • GitHub内部のID管理の複雑さと移行の歴史

GitHubのIDシステム：GraphQL node IDとdatabase IDの違い

  • Greptileの新機能開発中、GitHub PRコメントへのリンク生成に苦戦
  • GraphQL APIが返す**node ID（例：PRRC_kwDOL4aMSs6Tkzl8）**を利用
  • Web上のURLは**database ID（整数値、例：2475899260）**を要求
  • node IDとdatabase IDは異なるID体系で管理
  • 既存データの大規模な移行やバックフィルが現実的でない課題

node IDからdatabase IDの抽出方法

  • node IDはbase64エンコードされた値
  • PRRC_の後ろ部分をbase64デコードし、96ビット整数に変換
  • 下位32ビットがdatabase IDと一致することを発見
    • Python例：decoded & ((1 << 32) - 1)
  • これによりマイグレーション不要でdatabase IDを取得可能に

node IDの構造と64ビット部分の謎

  • 96ビット中、上位64ビットの用途が不明
  • node IDはグローバルIDとしてオブジェクト種別や所有リソース情報を含む可能性
  • 他のリポジトリやオブジェクトでフォーマットを調査

GitHubのレガシーIDフォーマット

  • 古いリポジトリ（例：torvalds/linux）は異なるbase64フォーマットを使用
    • 例：MDEwOlJlcG9zaXRvcnkyMzI1Mjk4 → 010:Repository2325298
  • 構造：[タイプ番号]:[タイプ名][database ID]
  • tree等のgitオブジェクトはSHA情報も含む
  • 新旧IDフォーマットの混在が確認できた

新旧IDフォーマットの使い分け

  • 新しいリポジトリやオブジェクトは新フォーマット
  • 古いリポジトリや一部オブジェクト（例：User）はレガシーIDを維持
  • オブジェクト生成日によってどちらのIDが使われるか決まる場合も

新フォーマットの詳細：MessagePackによるエンコード

  • 新node IDはMessagePackで配列としてエンコード
  • 例：decode_new_node_id("PRRC_kwDOL4aMSs6Tkzl8") → [0, 47954445, 2475899260]
    • 1番目：バージョン識別子（推測）
    • 2番目：リポジトリのdatabase ID
    • 3番目：オブジェクトのdatabase ID
  • オブジェクト種別によって配列長が異なるケースあり
  • database IDは常に配列の最後の要素

実用的なdatabase ID抽出コード

  • Pythonでの抽出例：

    import base64
import msgpack

def node_id_to_database_id(node_id):
    prefix, encoded = node_id.split('_')
    packed = base64.b64decode(encoded)
    array = msgpack.unpackb(packed)
    return array[-1]

  • これでpull requestコメント等のdatabase IDを簡単に取得可能

GitHubのIDシステム運用の所感

  • IDの扱いは「不透明な文字列」として推奨されるが、実際には内部構造あり
  • MessagePackやbitmaskでの解析・抽出が可能
  • GitHubエンジニアも2つのIDシステムのサポートに苦労していると推測

まとめ

  • node IDとdatabase IDの違いを理解し、簡単な変換手法を発見
  • MessagePackによる新IDフォーマットの仕組みを解明
  • GitHubのID管理の歴史的背景と現状の複雑さを把握
  • 開発現場での実践的な知見として活用可能

Hackerたちの意見

> あのリポジトリID（010:Repository2325298）は、構造がはっきりしてるよね。010は何かのタイプの列挙、コロンの後に「Repository」、その後にデータベースIDの2325298が続く。クラシックな長さプレフィックスだね。Repositoryは10文字、Treeは4文字。
└
ほぼURNだね。
└
BitTorrentプロトコルを思い出させるね。
Opus 4.5はこのトリックを知ってて、GitHubのAPIを使ってるときはIDをデコードするコードを書いてくれるんだよね、笑
データベース設計では、通常は不透明な自然キーを使うことが推奨されてて、単調に増加する整数IDは秘密にして内部で使うべきだよ。
└
そうかもね。でも、自然キーが変わることもあるからね。結構頻繁に。意味のない代理キーや生成キーを公開するのは賢明な気がする。例えば、YouTubeは全ての動画にインデックス番号を持ってるかもしれないけど、消費者にはあまり意味のないコード化された値を見せてるんじゃないかな。
└
これは二つの本当の理由からベストプラクティスだよ： 1. 第三者にオブジェクトの数を知られたくない 2. IDをインクリメントして各オブジェクトを列挙できるようにしたくない でも、こんな複合IDがあるなら、関係ないよね。リポジトリに属するすべてのオブジェクトには、そのリポジトリIDが含まれてる。IDをインクリメントすると、同じリポジトリのオブジェクトが増える。リポジトリIDをインクリメントすると…ランダムなオブジェクトか、何も得られない。もしIDに少しエントロピーやタイムスタンプが含まれてたら、悪用しようとしてる人を効果的に足止めできるよ。
こんなふうにはデコードしない方がいいよ、脆弱だし、グローバルノードIDはGraphQLでは不透明であるべきだから。GitHubが多くのタイプ（例えばPullRequest）で`databaseId`フィールドを公開してるのは知ってる？[1] ほとんどのGraphQL APIは、Nodeインターフェースを実装しているオブジェクトに対して、タイプ名とデータベースIDをbase-64エンコードしてるけど、それが常にそうだとは思わない方がいいよ。GraphQLのグローバルIDについては、[2]の仕様を読んでみてね。[1] https://docs.github.com/en/graphql/reference/objects#pullreq... [2] https://graphql.org/learn/global-object-identification/
└
それに、下でも指摘されてるけど、GitHubのGraphQLタイプには`permalink`や`url`（それに`UniformResourceLocatable`みたいなインターフェース）も含まれてて、自分で構築する必要がないかもしれないよ。
新しいグローバルノードID（'X-Github-Next-Global-ID'ヘッダーで強制できるやつね[1]）は、アンダースコアで区切られた「タイプ」を示すプレフィックスがあって、その後にbase64エンコードされたmsgpackペイロードが続く。ほとんどのオブジェクトには、バージョン（0から始まる）と数字の「databaseId」フィールドが含まれてるけど、もっと複雑なものもあるよ。例えば、私のGitHubユーザー[2]のノードIDは「U_kgDOAAhEkg」なんだ。ユーザーは「U_」で、その後のデータは[0, 541842]にデコードされて、REST APIで受け入れられる私のユーザーの数字IDと一致するんだ[3]。もちろん、これらの実装に頼るべきじゃないから、必要なところではGraphQL APIから直接「databaseId」フィールドをクエリしてね。そして逆に、REST APIはGraphQL APIの「node_id」フィールドを返すよ。これに興味がある人には、GitHubのREST APIのETag実装について詳しく書かれた[4]もおすすめだよ。[1] https://docs.github.com/en/graphql/guides/migrating-graphql-... [2] https://api.github.com/user/541842 [3] https://gchq.github.io/CyberChef/#recipe=Find_/_Replace(%7B'... [4] https://github.com/bored-engineer/github-conditional-http-tr...
GitHubのノードIDは見たことあるけど、使ったりデコードしようとしたことはなかったな。REST APIだけ使ってたから、ノードIDは報告されるけど入力には使わないんだよね。でも、ノードIDについての説明はいい感じだと思う。ただ、他のコメントにもあるように、ノードIDのフォーマットに頼るのはやめた方がいいよ。
1. 「スコープ」のリストは、そのリソースを持つオブジェクトの階層を示してる。これで、リソースがどのシャードにあるべきか分かるんだ。同じリポジトリのリソースは同じシャードに置きたいよね。そうしないと、単にIDをハッシュしただけで、シャードがダウンするとサービスの大部分が影響を受けちゃうから。 2. オブジェクト識別子は最後にあるべきで、これは厳密に増加するはずだから、同じスコープのリソースはDB内で順序付けられる。これがuuid7の利点の一つだね。 3. 最初の要素はほぼ確実にバージョンだよ。こんな移行をするなら、再度やる可能性を排除したくないよね。ビットを詰め込む場合、識別子なしではデータの中身を知るのはほぼ不可能だから、バージョンがないとIDが新しいのか古いのか分からなくなるかも。別のコメントでも、データを暗号化すべきだって言ってたけど、無理無理！各IDを復号化するのはb64デコードよりも明らかに遅いし、IDをバラバラにするのは自分のために作られたインターフェースに頼ることになる。そこに敏感な情報はないし、将来的に痛い目に遭う可能性が高いよ。GitHubは自分の足を撃つのを止める必要はないし、IDの内容を暗号化するとランダムにソートされちゃうから、これは避けた方がいい。似たようなオブジェクトが近くに保存されないことになるし、データに対して簡単な範囲スキャンもできなくなる。IDを入ってくるときに復号化して、暗号化されたバージョンと未暗号化のバージョンをDBに保存することもできるけど、なんで？それじゃあ複雑さや労力、リソースが増えるだけで、ネットのランダムな人たちが内部の非敏感なデータフォーマットに頼るのを防ぐためにやることじゃないよ。古いIDがまだ出てくるのは、ほぼ確実に： 1. 自分のIDでシャーディングされてる（つまり、ユーザーはユーザーIDでシャーディングされてて、リポジトリIDではないから）、追加情報は必要ない。シャードを選ぶのにランデブーハッシングみたいなのを使って。 2. 新しいIDフォーマットが開発される前にシャーディングされてて、変更するのは面倒だから。
└
AESは現代のCPUではbase64よりも速いよ、特に小さなメッセージの場合はね。
お客さんがあなたが明示的に頼るなって言った行動に依存してることにイライラしたら、この話を思い出してね。何かを解明することができるなら、お客さんは最終的にそれを理解して依存するようになるから。
└
システムに十分な数のユーザーがいると、ドキュメントや契約で「明示的に」約束したことはもはや重要じゃなくなる。ヒルムの法則：システムのすべての観察可能な挙動は、最終的に誰かに依存されることになる。特定の副作用に頼るなって言っても、ユーザーがそれを発見して便利だと思ったら、その挙動はシステムのインターフェースの暗黙の部分になる。結果として、エンジニアは「どんな変更も誰かのワークフローを壊す」と感じることが多い。たとえその変更が技術的にはバグ修正やパフォーマンス向上であってもね。約束されていない挙動への依存は、クランツの法則（またはスクラッピーの法則*）としても知られていて、物事は最終的にその本質的な特性や効果のために使われることを主張している。意図された目的に関係なく。「私はBSDのためにSIGUSR1とSIGUSR2が発明されるべきだと主張した。人々はIPCのために必要な意味を持たせるためにシステムシグナルを奪っていたから、例えばセグフォルトするプログラムがSIGSEGVをハイジャックされたためにコアダンプしないように。この一般的な原則は、あなたが作るツールを奪われないように設計するか、きれいに奪われるように設計する必要があるということだ。それがあなたの唯一の選択肢だ。」 — ケン・アーノルド『The Art Of Unix Programming』
GitHubのスタッフは、シャーディングや複数データベースのサポートを拡張するために、最近数百のRailsへの貢献を積み重ねてきたんだ。これでその理由が分かるね。
コメントの中には、GraphQL APIがスキーマ内でデータベースのIDやオブジェクトへのURLを直接公開しているって指摘してる人もいたけど、著者はそれを知らずにID生成ロジックを逆アセンブルしちゃったんだよね。これがGraphQLがダメな理由の一つだよ。開発者はドキュメントを読むのを避けるためなら何でもするから。REST APIだと、developerIdやurlフィールドはAPIのレスポンスを見れば簡単にわかるのに、GraphQLでは全フィールドを取得する方法がないんだ。ドキュメントからフィールドのリストを取得して、明示的にリクエストしないといけないんだよね。