「短縮URL」って枯渇しないのですか?

たとえば htn.to のだとアルファベット(大文字、小文字)+数字で [a-zA-Z0-9]^6 で 56,800,235,584 通り??(←そもそもこれであってます?)
また、一度使われた短縮URL って以前使われてないかとかってチェックされてるのでしょうか?
すでに、10億通りの短縮URL が使われてたとして、一瞬で 10億ものチェックをしてるのかな、と。
ちょっと疑問に思いました。

回答の条件
  • 1人5回まで
  • 登録:
  • 終了:2012/01/11 22:00:03
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

ベストアンサー

id:a-kuma3 No.4

回答回数4971ベストアンサー獲得回数2153

ポイント17pt

URL 短縮サービスの実装を見たことはありませんが、ハッシュを使ってるはずです。

ハッシュ関数 (ハッシュかんすう、hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。


URL から求められたハッシュ値が、短縮URL の可変な部分に相当します。

ハッシュ関数は、ハッシュ値が、なるべくユニークな値を取るように設計されます。
それでも、元の文字列の長さ (情報量) が限定されていない場合には、衝突することがあります (違う URL なのに、同じハッシュ値になる)。
回避方法は幾つかあるのですが、そのひとつが、次の値をハッシュ値とすることです。

「次の値が使われているかもしれないじゃないか」というのは、その通りですが、ハッシュ関数というのは、似たようなデータが入力されても、なるべく値が散らばるように設計されるので、衝突したときに、その次の値が空いていることが多い (ように設計される) です。

短縮URL の作成する場合には、以下のような処理になります。

  1. URL を表す文字列から、6桁の 62進数 (56,800,235,584) に収まるハッシュ値を作成する
  2. ハッシュ値と URL を列にもつテーブルに登録する (ハッシュ値の列がプライマリキー)
  3. 既にテーブルに登録されている場合には、
    1. 既に登録済みの URL であれば、そのハッシュ値を採用する
    2. 登録されていなければ、ハッシュ値をひとつ増やして、登録を試みる

短縮URL から実際の URL を取得する場合には、テーブルから探すだけです。
RDB はプライマリキーからレコードを特定する処理が早くなるように設計されています (ここでもハッシュが使われることが多い)。
10億通りのチェックをしているわけではありません。


登録テーブルの空いているところを探しながら処理をするので、56,800,235,584 をすべて使い切るまでは枯渇はしないのですが、ハッシュの衝突が多くなると性能が落ちます。
ただ、この「性能」は、短縮URL の登録時にかかわってくるだけで、検索時には全く影響が無いので、サービスの性質上 560億通りの組合せを使いきるまでは、枯渇した状態にはなりません。

もし、枯渇したとしても、使える文字を一文字増やしたり、桁をひとつ増やすだけで対応できる数は格段に増えますので、実質、枯渇することは無いということになります。


trini さんは、62 の 6乗を正しく計算できる方のようなので、ある程度、情報処理の基礎を持っている方だと想像し、かなり説明を端折りました。
意味が分からないところがあれば、補足します。

その他の回答5件)

id:nattow No.1

回答回数102ベストアンサー獲得回数27

ポイント17pt

使用済み url の検索については、正しくデータが管理されていれば問題ありません。具体的には使用済みの url をソートした状態で持っておけば検索は一瞬ででき
ます。

枯渇問題は、ちょっと自信がないですが、桁数を増やせば指数関数的にオーダーが増えていきますし、ドメイン自体を複数用意すればそれが何倍にもなりますので、今すぐに枯渇する心配はないかと思います。

id:windofjuly No.2

回答回数2625ベストアンサー獲得回数1149

ポイント17pt

最近のパソコンなら1秒かからずに一瞬でチェックできますし、
数台でカバーすれば、さらに安定して高速な処理が可能です

もう少し詳しく知るには、
まず、パソコンのメモリの量について知る必要があります
1KB 1,024 千
1MB 1,048,576 百万
1GB 1,073,741,824 十億

単純に、URL1つに1KBが必要だったとしても、
最近のパソコンのようにメモリが8GBもあれば、
800万もの変換情報をメモリ上だけで高速処理できますので、
直前に登録されたり使われたものをメモリに置いておくことで、
1秒間に数百万回の変換だって可能になるわけです

今のところは、
インターネットの速度のほうがはるかに遅いので、
サーバー側の検索スピードが負けることはまず無いです

枯渇しそうになれば、桁数を7に増やすか、
サーバーのアドレスを新たに用意すればいいだけなので、
心配するほどの問題ではないでしょう

id:kodairabase No.3

回答回数661ベストアンサー獲得回数80

ポイント17pt

>56,800,235,584 通り??(←そもそもこれであってます?)
合っています。

>一度使われた短縮URL って以前使われてないかとかってチェックされてるのでしょうか?
ちゃんとデータベースで管理されています。

ただし、英数字6文字とは限定されていません。将来的に7文字や8文字になるかもしれません。

id:a-kuma3 No.4

回答回数4971ベストアンサー獲得回数2153ここでベストアンサー

ポイント17pt

URL 短縮サービスの実装を見たことはありませんが、ハッシュを使ってるはずです。

ハッシュ関数 (ハッシュかんすう、hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。


URL から求められたハッシュ値が、短縮URL の可変な部分に相当します。

ハッシュ関数は、ハッシュ値が、なるべくユニークな値を取るように設計されます。
それでも、元の文字列の長さ (情報量) が限定されていない場合には、衝突することがあります (違う URL なのに、同じハッシュ値になる)。
回避方法は幾つかあるのですが、そのひとつが、次の値をハッシュ値とすることです。

「次の値が使われているかもしれないじゃないか」というのは、その通りですが、ハッシュ関数というのは、似たようなデータが入力されても、なるべく値が散らばるように設計されるので、衝突したときに、その次の値が空いていることが多い (ように設計される) です。

短縮URL の作成する場合には、以下のような処理になります。

  1. URL を表す文字列から、6桁の 62進数 (56,800,235,584) に収まるハッシュ値を作成する
  2. ハッシュ値と URL を列にもつテーブルに登録する (ハッシュ値の列がプライマリキー)
  3. 既にテーブルに登録されている場合には、
    1. 既に登録済みの URL であれば、そのハッシュ値を採用する
    2. 登録されていなければ、ハッシュ値をひとつ増やして、登録を試みる

短縮URL から実際の URL を取得する場合には、テーブルから探すだけです。
RDB はプライマリキーからレコードを特定する処理が早くなるように設計されています (ここでもハッシュが使われることが多い)。
10億通りのチェックをしているわけではありません。


登録テーブルの空いているところを探しながら処理をするので、56,800,235,584 をすべて使い切るまでは枯渇はしないのですが、ハッシュの衝突が多くなると性能が落ちます。
ただ、この「性能」は、短縮URL の登録時にかかわってくるだけで、検索時には全く影響が無いので、サービスの性質上 560億通りの組合せを使いきるまでは、枯渇した状態にはなりません。

もし、枯渇したとしても、使える文字を一文字増やしたり、桁をひとつ増やすだけで対応できる数は格段に増えますので、実質、枯渇することは無いということになります。


trini さんは、62 の 6乗を正しく計算できる方のようなので、ある程度、情報処理の基礎を持っている方だと想像し、かなり説明を端折りました。
意味が分からないところがあれば、補足します。

id:pretaroe No.5

回答回数531ベストアンサー獲得回数75

ポイント16pt

URL->短縮URLに変換に
ハッシュ法というのが用いられています。

これは、URLが違えば必ずそのハッシュ値が違うということを利用しています。
重複する確率がものすごく低いですので、事実上ないのと同じになります。
まったくありえないわけではありません。

ただし、URLが同じでも毎回同ハッシュ値にならないという性質があります。


短縮URLからURLに戻す時は、現在ある短縮URLから検索して
短縮URL->URLに変換しています。
ハッシュ値が決まると一意にURLが決まりますので

そういう検索は数百億レコードあっても、現在のコンピュータでは一瞬で検索できます。

id:pretaroe

仮に枯渇したら、文字列を増やすだけで対応可能です。

2012/01/05 02:48:14
id:a-kuma3

ただし、URLが同じでも毎回同ハッシュ値にならないという性質があります。

違うよ。
入力が同じだったら、それから求めたハッシュ値は必ず同じになる。

これは、URLが違えば必ずそのハッシュ値が違うということを利用しています。

これも、微妙に違う。
入力(URL)が違ってたら、なるべく違うハッシュ値を返すように、ハッシュ関数を設計するの。
ハッシュ値を求めるアルゴリズムは、ひとつだけじゃない。

2012/01/09 00:34:35
id:xxmasaxx No.6

回答回数2ベストアンサー獲得回数0

ポイント16pt

htn.toの実装は分からないのですが、自分がもし短縮URLのサービスを作るとしたら、登録されたURLをデーターベースのIDで管理し、そのID番号を36進数に変換したものを短縮URLとして使います。

つまり、http://hatena.ne.jp/ というURLをID番号123456に紐付けしたとしたら、その短縮URLは「http://hoge/2n9c」となります。

仮にIDを64bitまで管理する想定でも、1844京6744兆0737億0955万1616 まで扱えますから、IDの枯渇は当面気にする必要はないかと思います。

  • id:savilerow
    ふ、ふ、ふしぎだよ
    は、は、はっしゅって なぁに?
  • id:Gutyan
    要するに、DBとハッシュのおかげで重複や枯渇はしないし、
    もし枯渇しそうになったら短縮URLのランダム英数字の桁を1つ増やせばどんどん作れるってことやね。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

回答リクエストを送信したユーザーはいません