たとえば htn.to のだとアルファベット(大文字、小文字)+数字で [a-zA-Z0-9]^6 で 56,800,235,584 通り??(←そもそもこれであってます?)
また、一度使われた短縮URL って以前使われてないかとかってチェックされてるのでしょうか?
すでに、10億通りの短縮URL が使われてたとして、一瞬で 10億ものチェックをしてるのかな、と。
ちょっと疑問に思いました。
URL 短縮サービスの実装を見たことはありませんが、ハッシュを使ってるはずです。
ハッシュ関数 (ハッシュかんすう、hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。
URL から求められたハッシュ値が、短縮URL の可変な部分に相当します。
ハッシュ関数は、ハッシュ値が、なるべくユニークな値を取るように設計されます。
それでも、元の文字列の長さ (情報量) が限定されていない場合には、衝突することがあります (違う URL なのに、同じハッシュ値になる)。
回避方法は幾つかあるのですが、そのひとつが、次の値をハッシュ値とすることです。
「次の値が使われているかもしれないじゃないか」というのは、その通りですが、ハッシュ関数というのは、似たようなデータが入力されても、なるべく値が散らばるように設計されるので、衝突したときに、その次の値が空いていることが多い (ように設計される) です。
短縮URL の作成する場合には、以下のような処理になります。
短縮URL から実際の URL を取得する場合には、テーブルから探すだけです。
RDB はプライマリキーからレコードを特定する処理が早くなるように設計されています (ここでもハッシュが使われることが多い)。
10億通りのチェックをしているわけではありません。
登録テーブルの空いているところを探しながら処理をするので、56,800,235,584 をすべて使い切るまでは枯渇はしないのですが、ハッシュの衝突が多くなると性能が落ちます。
ただ、この「性能」は、短縮URL の登録時にかかわってくるだけで、検索時には全く影響が無いので、サービスの性質上 560億通りの組合せを使いきるまでは、枯渇した状態にはなりません。
もし、枯渇したとしても、使える文字を一文字増やしたり、桁をひとつ増やすだけで対応できる数は格段に増えますので、実質、枯渇することは無いということになります。
trini さんは、62 の 6乗を正しく計算できる方のようなので、ある程度、情報処理の基礎を持っている方だと想像し、かなり説明を端折りました。
意味が分からないところがあれば、補足します。
使用済み url の検索については、正しくデータが管理されていれば問題ありません。具体的には使用済みの url をソートした状態で持っておけば検索は一瞬ででき
ます。
枯渇問題は、ちょっと自信がないですが、桁数を増やせば指数関数的にオーダーが増えていきますし、ドメイン自体を複数用意すればそれが何倍にもなりますので、今すぐに枯渇する心配はないかと思います。
最近のパソコンなら1秒かからずに一瞬でチェックできますし、
数台でカバーすれば、さらに安定して高速な処理が可能です
もう少し詳しく知るには、
まず、パソコンのメモリの量について知る必要があります
1KB 1,024 千
1MB 1,048,576 百万
1GB 1,073,741,824 十億
単純に、URL1つに1KBが必要だったとしても、
最近のパソコンのようにメモリが8GBもあれば、
800万もの変換情報をメモリ上だけで高速処理できますので、
直前に登録されたり使われたものをメモリに置いておくことで、
1秒間に数百万回の変換だって可能になるわけです
今のところは、
インターネットの速度のほうがはるかに遅いので、
サーバー側の検索スピードが負けることはまず無いです
枯渇しそうになれば、桁数を7に増やすか、
サーバーのアドレスを新たに用意すればいいだけなので、
心配するほどの問題ではないでしょう
>56,800,235,584 通り??(←そもそもこれであってます?)
合っています。
>一度使われた短縮URL って以前使われてないかとかってチェックされてるのでしょうか?
ちゃんとデータベースで管理されています。
ただし、英数字6文字とは限定されていません。将来的に7文字や8文字になるかもしれません。
URL 短縮サービスの実装を見たことはありませんが、ハッシュを使ってるはずです。
ハッシュ関数 (ハッシュかんすう、hash function) とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことをハッシュ値または単にハッシュという。
URL から求められたハッシュ値が、短縮URL の可変な部分に相当します。
ハッシュ関数は、ハッシュ値が、なるべくユニークな値を取るように設計されます。
それでも、元の文字列の長さ (情報量) が限定されていない場合には、衝突することがあります (違う URL なのに、同じハッシュ値になる)。
回避方法は幾つかあるのですが、そのひとつが、次の値をハッシュ値とすることです。
「次の値が使われているかもしれないじゃないか」というのは、その通りですが、ハッシュ関数というのは、似たようなデータが入力されても、なるべく値が散らばるように設計されるので、衝突したときに、その次の値が空いていることが多い (ように設計される) です。
短縮URL の作成する場合には、以下のような処理になります。
短縮URL から実際の URL を取得する場合には、テーブルから探すだけです。
RDB はプライマリキーからレコードを特定する処理が早くなるように設計されています (ここでもハッシュが使われることが多い)。
10億通りのチェックをしているわけではありません。
登録テーブルの空いているところを探しながら処理をするので、56,800,235,584 をすべて使い切るまでは枯渇はしないのですが、ハッシュの衝突が多くなると性能が落ちます。
ただ、この「性能」は、短縮URL の登録時にかかわってくるだけで、検索時には全く影響が無いので、サービスの性質上 560億通りの組合せを使いきるまでは、枯渇した状態にはなりません。
もし、枯渇したとしても、使える文字を一文字増やしたり、桁をひとつ増やすだけで対応できる数は格段に増えますので、実質、枯渇することは無いということになります。
trini さんは、62 の 6乗を正しく計算できる方のようなので、ある程度、情報処理の基礎を持っている方だと想像し、かなり説明を端折りました。
意味が分からないところがあれば、補足します。
URL->短縮URLに変換に
ハッシュ法というのが用いられています。
これは、URLが違えば必ずそのハッシュ値が違うということを利用しています。
重複する確率がものすごく低いですので、事実上ないのと同じになります。
まったくありえないわけではありません。
ただし、URLが同じでも毎回同ハッシュ値にならないという性質があります。
短縮URLからURLに戻す時は、現在ある短縮URLから検索して
短縮URL->URLに変換しています。
ハッシュ値が決まると一意にURLが決まりますので
そういう検索は数百億レコードあっても、現在のコンピュータでは一瞬で検索できます。
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の枯渇は当面気にする必要はないかと思います。
仮に枯渇したら、文字列を増やすだけで対応可能です。
2012/01/05 02:48:14違うよ。
入力が同じだったら、それから求めたハッシュ値は必ず同じになる。
これも、微妙に違う。
2012/01/09 00:34:35入力(URL)が違ってたら、なるべく違うハッシュ値を返すように、ハッシュ関数を設計するの。
ハッシュ値を求めるアルゴリズムは、ひとつだけじゃない。