この記事は株式会社エス・エム・エス Advent Calendar 2023の2日目の記事です。
今年Webセキュリティで話題になったテーマとして、短縮URLが記憶に新しいという方も多くいらっしゃるのではないでしょうか。エス・エム・エスとしても短縮URLを業務で利用しているシーンがあり、私も個人的な関心を持っています。
一般に短縮URLの基本的なシステム構成は、入力された URL に対して一意の小さい符号を割り当て短縮URLを発行、短縮URLに対してのアクセスがあった場合はURLに含まれる符号をキーにしてデータベースに保存されているURLを取り出し、URLに対するリダイレクトを行うという構成が取られています。
私が構想を練っている短縮URLは強い制約がありますが、その代わりにデータベースを必要とせず、静的ファイル+Webブラウザ上のJavaScript だけで動作します。このシステムが持っている「強い制約」とは以下のようなものです
- 特定のサイトのsitemap.xml を読み込ませて動作します
- sitemap.xml に含まれていない URL には原則的に対応できません
- URL 発行時のsitemap.xml は保存しておく必要があります
- クエリパラメータなどは(まだ)追加できません
ちょっと制約が強すぎると思った方もいらっしゃると思いますが、細かいことは気にしないことにしましょう。運用コストが気になる短縮URLが静的ファイルだけで実現できるのであれば考えてみる価値があると思いませんか。
実装方式
基本コンセプト
このサービスのプログラムは sitemap.xml からURLを抽出し、URLからパトリシア木を構築
します。パトリシア木をご存知ない方も以下のツリーをみていただければどんなものかイメージがわくかと思います。画像は「apple、 applet、 banana、 band、 bandana」の5単語をパトリシア木にしたものです。
次にパトリシア木のエッジの各ラベルを1文字に(“ban” → “b” という具合に)切り詰めます。パトリシア木の先頭文字列は一致しないことが保証されているので、これにより圧縮された path を作成できます。たとえば、「apple、 applet、 banana、 band、 bandana」の5単語はそれぞれ左側のアドレスで表現できます。
| path | leaf |
|---|---|
| a | apple |
| at | applet |
| ba | banana |
| bd | band |
| bda | bandana |
一見、それほどの圧縮率に見えないかもしれませんが、これが特定のサイトのURLに対してはかなりの圧縮率になります。たとえば、https://ads.kaipoke.biz/sitemap.xml から抜き出した一部のURLに同等の処理を行ってみます。
この例では効果が出やすい文字列を恣意的に選んでいますが、都合のいいデータに対してはかなりの高い効果が発揮されることがお分かりいただけると思います。そしてWebサイトを運営する企業の業務においては実際にこの「都合のいいデータ」が使われがちであることが重要なポイントです。
そして、実装してみて気付いたことですが、短縮URLが非常に読みやすく、サイトの運営に関わっている方であれば短縮URLを見て転送先を認識しやすいというメリットもありそうです。
基本コンセプトの欠点を補正する追加のアイデア
ここまでの説明で以下のような疑問を持った方もいらっしゃるのではないでしょうか。
- sitemapがあるならsitemap 上の出現位置(例: 2番目のURLなど)をそのまま符号化するだけで十分に簡単な実装になるのでは？
- sitemapが更新されたらツリー構造が変化してしまうため、アクティブに運営されているWebサイトでは利用できないのでは？
前者の疑問は単なる自己満足と言ってしまえば深刻な課題ではないですが(1)、後者は確かに実用性に大きく影響しそうです。具体的には、「apple, applet, banana, band, bandana」で構成されたパトリシア木に新たに “apps”が追加された場合、”a” の符号を割り当てていたapple の符号は “al”に変更しなければなりません。これはsitemap が更新されるたびに古いバージョンの短縮URLが使えなくなることを意味しますが、これでは実用性に問題があります。
現在のところ短縮URL発行に関わる全ての期間の sitemap.xml を保存しておくという制約は避けては通れないようです。sitemap.xml にバージョン番号を割り当て、バージョン番号と一意に対応するパトリシア木をURLのエンコード・デコードに利用します。
振り返り
ここまでを振り返ってみますと、結局は過去の sitemap の履歴を保存し続ける必要があるという性質のおかげでそれほど質の高いソリューションにはならなかった感があります。ニーズの確かさと発想自体は悪くないと思うので、さらに改善して質のいいソリューションになるように改善したいと思います。
おそらく最終的に目指す方向性は、sitemap.xml を読み込んで圧縮の最適化に必要な語彙を学習するための辞書として読み込むものの、実際の圧縮はZstandardのような汎用のアルゴリズムに近い本格的な圧縮アルゴリズムを考える必要がありそうです。
実装 (基本コンセプトのみ)
ここまでの実装をコンセプトとして試すため、Pythonで基本部分を実装してみました。追加部分は時間の制約上、まだ実装しきれておりません。また最終的にはWebブラウザ上で動作するというのが嬉しい部分なので JavaScript にも移植する予定です。
class PatriciaNode:
def __init__(self, label="", full_string=None, is_root=False):
self.label = label
self.full_string = full_string if not is_root else None
self.children = {}
def insert(self, string, original_string=None):
if original_string is None:
original_string = string
i = 0
while i < min(len(self.label), len(string)) and self.label[i] == string[i]:
i += 1
if i == len(self.label):
if i < len(string):
next_char = string[i]
if next_char in self.children:
self.children[next_char].insert(string[i:], original_string)
else:
self.children[next_char] = PatriciaNode(string[i:], original_string)
else:
common_label = self.label[:i]
diff_label = self.label[i:]
new_node = PatriciaNode(diff_label, self.full_string)
new_node.children = self.children
self.label = common_label
self.full_string = None
self.children = {diff_label[0]: new_node}
if i < len(string):
self.children[string[i]] = PatriciaNode(string[i:], original_string)
def compress_labels(self):
if self.label:
self.label = self.label[0]
for child in self.children.values():
child.compress_labels()
def _display(self, indent=0):
display_string = f"{self.label}: {self.full_string}" if self.full_string else self.label
print(" " * indent + display_string)
for child in self.children.values():
child._display(indent + 4)
# デモ動作のためのパトリシア木を構築
root = PatriciaNode(is_root=True)
root.insert("apple")
root.insert("applet")
root.insert("banana")
root.insert("band")
root.insert("bandana")
# ラベルの圧縮
root.compress_labels()
# パトリシア木の内容を表示
root._display()
現在のデザインに至るまでの経緯
この着想にいたるまでの元々の発想は、短縮URLの作成を可逆圧縮で実装することは可能なのかという思考実験から始まりました。実際に計算してみたり、圧縮を試してみたりするとURLのような短い文字列を圧縮し base64 エンコードして、短縮URLとして機能させられるような高い圧縮率の可逆圧縮アルゴリズムは見つけることができませんでした。このアイデアを社内のSlackチャンネルで紹介したところ、エンジニアの原野さんよりサイトマップの利用のアイデアを提案してもらい実装してみました。
今後の課題
sitemapを全て保存しておくというのはかなり大きい制約になるので、sitemap に直接依存するのではなく、sitemapを圧縮時に辞書作成に利用するような圧縮アルゴリズムを作ることでsitemapの更新に対しても問題なく対応できるようになるのではと考えています。
現時点での実装における浅めの課題としては以下の課題があります。
- マーケティングキャンペーンなど短縮URLを利用するケースではクエリパラメータを使用することも多いのではないでしょうか。現在の実装では特にクエリパラメータについては考慮していませんが、サイトの運営方法によってクエリパラメータの利用パターンは異なるので、圧縮アルゴリズムもサイト単位で最適化する必要がありそうです。UTMパラメータなど頻出のパターンについては特化した最適化機構を作っておくのがよさそうです
- 実際に運用するにあたってはWebブラウザ上で動作するJavaScript版、URLを発行するためのWeb サイト (原理的には HTML + JavaScript だけで動作します)、sitemap.xml を保存して、発行用のWebサイトに反映させるビルドシステムなどが追加で必要です
-
現在のツリーを使った設計は、後述する将来見据えている最終的な設計にはURLの出現位置という発想からでは到達できないので、その方向性のための途中段階と位置付けています。 ↩