人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: trini
●カテゴリ:インターネット ウェブ制作
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● nattow
●17ポイント

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

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


2 ● うぃんど
●17ポイント

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

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

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

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

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


3 ● kodairabase
●17ポイント

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

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

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


4 ● a-kuma3
●17ポイント ベストアンサー

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

(ハッシュ関数 @Wikipedia)
ハッシュ関数 (ハッシュかんすう、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 ● pretaroe
●16ポイント

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

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

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


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

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


pretaroeさんのコメント
仮に枯渇したら、文字列を増やすだけで対応可能です。

a-kuma3さんのコメント
>> ただし、URLが同じでも毎回同ハッシュ値にならないという性質があります。 << 違うよ。 入力が同じだったら、それから求めたハッシュ値は必ず同じになる。 >> これは、URLが違えば必ずそのハッシュ値が違うということを利用しています。 << これも、微妙に違う。 入力(URL)が違ってたら、なるべく違うハッシュ値を返すように、ハッシュ関数を設計するの。 ハッシュ値を求めるアルゴリズムは、ひとつだけじゃない。

1-5件表示/6件
4.前の5件|次5件6.
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ