URL短縮サイトを実装する場合、
たとえ人気のないサイトでも、何千万件以上のURLが登録されることが考えられます。
例えば、
- 「ABC -> https://google.com 」
- 「ABD -> https://www.yahoo.co.jp/ 」
といった情報が、何千万件と保存されるわけです。
この何千万件の情報を比較するだけであれば、そこまで膨大な時間はかからないかもしれません。
しかし、URL短縮サイトは「速度」が命だと私は考えています。
動作の遅いURL短縮サイトは、それだけでユーザー離れにつながるでしょう。
そこで今回は、
「何千万件からでも高速に検索できる仕組み」について、妄想してみようと思います！
前提条件
簡単のため、今回は短縮URLに Base62 を使用すると仮定します。
Base62とは、以下の文字を使うものです。
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
まずは「1ファイル末尾追記方式」を考える
最初に、「1つのファイルにすべてのURL情報を追記していく」方法を考えます。
仮に、1URLあたり平均30文字とすると、
何千万件登録されれば、約10億文字になります。
大半（99%以上）が1バイト文字なので、ファイルサイズは概ね1GB程度でしょう。
また、StreamReaderなどで1行ずつ読み込めば、
メモリを大量に消費することなく、比較作業が可能です。
この方法では、単純に何千万回比較することになりますが、
それでも実際にはそこまで時間はかからないと推測されます。
基本的な実装としては問題ないでしょう。
ただし、さらに高速化できないか？
とはいえ、
URL短縮サイトでは、さらに高速なレスポンスが求められると考えます。
そこで、
「比較回数をさらに減らす方法」を妄想してみます。
1文字目ごとにファイルを分ける
検索対象の短縮URL（検索部分）は、Base62文字列です。
そこで、検索部分の1文字目ごとにファイルを分割する方法を考えます。
例えば、次のようにします。
- 「ABC -> https://google.com 」という登録があれば
- 「A.txt」に「BC -> https://google.com 」を書き込む
つまり、先頭文字別に振り分けるのです。
検索時は、まず先頭1文字で対応するファイルを選び、
その中で残りの文字列を検索します。
これにより、
検索対象は理論上62分の1に減少します。
多少ファイルアクセスコストは増えますが、
十分効果的な最適化と言えるでしょう。
さらに 1〜2文字目ごとにファイルを分ける
さらに踏み込んで、
検索部分の1文字目＋2文字目でファイルを分ける方法も考えられます。
この場合、
- 「ABC -> https://google.com 」という登録なら
- 「AB.txt」に「C -> https://google.com 」を書き込む
という形になります。
これにより、ファイル数は 62² = 3844個 になりますが、
比較対象は理論上 62²分の1 にまで減少します。
フォルダ構成の工夫
ファイル数が増えるので、
「1文字目ごとにフォルダを作り、その中に2文字目ごとのファイルを置く」
という構成にするのも一つの手でしょう。
例：
- 「ABC -> https://google.com 」という登録なら
- 「A/B.txt」に「C -> https://google.com 」を書き込む
これにより、
ファイルシステムの負荷分散も期待できます。
（このあたりは、検索アルゴリズムやファイルシステムの特性にも依存するでしょう）
まとめ
以上、
URL短縮サイトにおける検索高速化についての妄想をまとめました。
なお、実際の運用では、
-
https://を別文字に置換したり -
https://から始まるURLのみ許可したり - 使用する文字として 0 と O を省いたり
などの工夫もあり得るでしょうが、
今回は検索速度に特化して考えてみました。
もし、実際の短縮URLサービスで使われているアルゴリズムについて
ご存じの方がいらっしゃいましたら、
ぜひコメントいただけると嬉しいです！
最後までお読みいただき、ありがとうございました！
追記
投稿後に文章を ChatGPT に添削頂きました。
AI で添削した文章が
好みではない方には申し訳ありませんが
この添削後の文章で容赦頂きますようお願いします。