最新的Yusi主题上线啦!

短网址服务思考

未分类 lzxianren 699℃ 0评论

什么是短网址?

短网址(Short URL),顾名思义就是在形式上比较短的网址。通常用的是asp或者php转向,在Web 2.0的今天,不得不说,这是一个潮流。目前已经有许多类似服务,借助短网址您可以用简短的网址替代原来冗长的网址,让使用者可以更容易的分享链接。比如腾讯、新浪微博等等都有这些短地址服务,用户在发布链接的时候自动转为短地址,既美观又好看。在变成二维码的时候也不用担心url太长,导致二维码太大。

本质

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

以上是leetcode的上一道题目,其实就是长短地址的转换。短地址的本质就是把任意一个常地址经过加密算法变成一个唯一的短地址,而且这个短地址经过解密算法能够还原出来一个唯一的常地址。

几个问题

  1. 是否有什么算法可以直接把一百个字符左右的长网址缩短到10位以内,并可以原样还原,即可逆。

    10倍的压缩比在无损压缩算法领域谁介绍下?当然这个比例是基于多样数据而不是特定的文本,否则文本只有一个字符a,那压缩比想多少有多少。

  2. 只实现字符压缩/hash,不需要做到可逆,然后存储到数据库中,恢复时只需要查询数据库。

    从压缩的角度和第一条说明没有区别,不可能无损压缩,那就有可能出现hash碰撞。不同的长网址缩短成了同一个短网址,那也做不到还原了。

  3. 接着第二条,出现碰撞了可以后面再加随机字符。

    随机字符可以缓解碰撞问题,但是无法根治。另外,增加几位字符呢才可靠呢?这种概率事件无法通过测试来回答,通过运维监控不断的调整也是一件头疼和折磨人的事。

  4. 预先在redis/db里异步生成一批短码,每次从列表里面取不就好了。

    具体是在redis还是db里批量生成其实是截然不同的两种实现。
    若是redis, 那么里面要放入全量的短码么?否则怎么知道这个短码到底是不是唯一的?如果全量,那对redis的可用性就要严格保证,否则它挂了,就必须全量的预热,这个过程要做好不是那么的容易;
    若是db, 那么就要有大量的并发锁定,意味着大量读写,这个对数据库也是个考验。

  5. 短网址的还原跳转用301还是302呢?

    301是永久重定向,302是临时重定向。短地址一经生成就不会变化,所以用301是符合http语义的。同时浏览器会对301请求保存一个比较长期的缓存,这样就减轻对服务器的压力;而且301对于网址的SEO有一定的提升。但是很多情况下我们需要对接口点击或者用户行为进行一些业务监控处理的时候,301明显就不合适了(浏览器直接按照缓存数据跳转了), 所以很多业务场景下还是采用302比较合适。

常见算法

  1. 内存里面放一个hashmap,用一个long作为map的key,输入长地址,long自增+1,然后放到map中。解密的时候,就对map进行循环,拿到长地址即可。
    问题:

    1. 放到内存里面,当长地址个数很多的时候,内存即会溢出;
    2. long要保证多线程的唯一,可以加automatic解决;
    3. 此解法本质是通过增加一个唯一的key作为短地址的一部分问题。
  2. 对长地址进行hash算法,得到的结果作为key,存入db/redis中
    具体可以参见:http://www.jianshu.com/p/d1cb7a51e7e5

转载请注明:程序员的自我修养 » 短网址服务思考

喜欢 (1)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址