小议短网址系统的设计(有些时候,需要换个角度思考问题) – 韩子迟

前言

短网址,我想大家应该都见过,如果没有,试着点击下面这条链接 https://git.io/vSY4o,会跳到我的 GitHub 主页,但是它确实比原始链接 https://github.com/hanzichi 要短了一些。关于短网址的作用,这里不作描述,本文主要讲讲如何实现一个简单的短网址系统。

Leetcode 正好 有一题 与此有关,不妨一试。

思路

如果没有接触过短网址,不妨去 https://goo.gl/https://git.io/ 稍微体验下。体验的结果是,短网址都把网址压缩成了六个字符,这是巧合吗?

短网址整个运转逻辑非常简单,我们以 https://goo.gl/SfzlA2 为例,当我们访问这个网址的时候,后端可以获取 "SfzlA2" 这个字符串,然后跳转到 https://github.com/hanzichi,很显然,这个字符串和这个地址已经绑定,通过某种映射关系可以从 "SfzlA2" 获取完整的地址。

那么,看起来我们只需要找到一个算法,能够将一个长字符串压缩成一个短的字符串,并且该算法应该是可逆的。但是实现这样的文本压缩算法,是非常困难的(不存在?),如果真有这么一个算法和逆运算,那么基本上现在的压缩软件都可以歇菜了,而世界上所有的信息(网址长度未知),都可以压缩成固定长度个字符,这可能吗?所以不要幻想使用压缩算法,而且对于 URL 这种不超过 100 bytes 的字符串,压缩算法的压缩比通常都大于 1。

所以我们应该转变思路。目前流行的短网址算法大概有两种,一种是利用 md5,将长网址 md5 后,再进行分组压缩,因为 md5 实质上是一种哈希算法,所以难免出现碰撞,当然,我们有解决哈希冲突的 N 种方法,但是这只会增加系统的复杂度,不推荐。另外一种是将网址和一个 62 进制数(0-9 & a-Z)对应,存入数据库中,需要的时候,通过数据库查询提取。

实现

接着我们就根据以上的思路,来实现一个简单的短网址系统。

我们先不考虑 62 进制的转换,用 Map 来当做一个 k-v 的数据库。当存入第一个网址的时候,假设我们的短网址是 xx.com/0,可以将 0 当做 key,将实际网址当做 value,需要查询的时候直接提取,如果有新的短网址需要生成,将 key 自增。代码如下。

let [p, index] = [new Map(), 0];

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
  p.set(index, longUrl);
  return index++;
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
  return p.get(shortUrl);
};

很显然,用一个 62 进制数表示,短网址可以更短。我们可以自己实现一个简单的 10 进制到 62 进制的转换算法。

let [p, index] = [new Map(), 0];

var base62 = (n) => {
  let str = '0123456789abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ';
  let len = str.length;
  let ret = '';

  do {
    ret += str[n % len];
    n = ~~(n / len);
  } while (n);

  return ret;
};

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
  let shortUrl = base62(index++);
  p.set(shortUrl, longUrl);
  return shortUrl;
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
  return p.get(shortUrl);
};

这样实现的话实际的短网址的数量其实是受限的,理论上应该是(JavaScript)能表示的最大的整数。

其他

这样的实现,还有一些其他的问题,比如短网址的长度并不是固定的,这点容易解决,补位即可。再比如,这些短网址,按照顺序排列,并不显得随机,这也好办,比如可以随机生成六位字符串当作 key,而不是用整数的递增,这样的话,短网址数量也不受限了(可以增加短网址位数)。还有一点,相同的 URL 可能得到不同的短网址,这点可以另外加个哈希或者用 Set 去解决,还可以加个缓存来解决(在缓存时间内,重定向到相同地址,一旦缓存失效,重新分配 key)。

除了算法设计外,真正的系统还需要考虑很多,比如发号器的设计,比如缓存(挂个 Redis),比如跳转,等等,本文只是抛砖引玉,这些就留给你们自己去思考了。

短网址系统的设计,其实依赖的并不是文本压缩算法。有些时候,需要换个角度思考问题

参考



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量