短链的实现

问题的起因是这个:

BLOG 这是我的刷题日志。当时是 2017.3.4 号,做了这道题之后,一直想写下是否有更好的解题思路。但是一直没(lan)有(lan)时(lan)间(lan)。

正巧今天在复习数据结构的时候看到了 LZW 压缩器。这就可以拉出来好好扯一下了。

其实现在流行的,或者网上的标准操作套路都是使用 hash 的方式,将其对应到几个短的链接上,但是因为毕竟这个属于 hash 映射,在长度变短的情况下,始终会有冲突的危险。所以也就带来了 rehash(cpu 开销和内存开销) 和 hash 表最坏情况(退化为链表结构,查找效率退化成 O(n))的风险。

比如常见的,使用 md5 摘要一把,然后将结果存到一个 hash 表中,这个 hash 表是个抽象的概念,他可以使具象化的数据库,Key-Value Store,或者仅仅的文件存储,或者内存数据。

但是,以上真的是个很烂的解法。具体的原因如下:

  1. 世界上并不存在不会碰撞的 hash 算法。只要使用 hash 必然就会带来冲突风险。这个风险就会造成之前提到的 rehash 和 退化 问题。为了解决这个引入的问题,往往就会加大系统的复杂性。所以可以从源头开始解决。
  2. 这样存贮之后,并不利于系统 (加入后台使用 DB) 查询效率的优化。查询的关键字为短链的值 — 字符串。这就带来了字符串索引的问题。这个就是在数据库优化中讨论的问题了。

不过,也是有优点的。因为是自己选定的 hash 函数,所以长度可控。比如我就要 32 位 hash 结果,那么最后得到的值的期待长度固定,方便进行自造轮子的存储系统或者说特别利于 redis 的发挥(redis 对等长数据的存储非常赞,几乎不会造成内存碎片的问题,如果这边展开讲 redis 的内存分配,有是一篇废话)。

当然除此之外,还有以下的几种解决思路。

  1. 压缩
  2. 发号

压缩这个很好理解,比如常用的 LZW 压缩算法和 zip 等使用的商业化压缩算法结合起来。通常情况下 LZW 的压缩算法的压缩比在 1.8 左右(数据较大的情况)而商业化的 Zip 工具压缩比则要更高。

但是,在这个业务场景中,他并不适用。

  1. LZW 的压缩结果包含两个部分,一个是压缩串,一个是数对字典。压缩串很短,但是数对字典的存储空间占用则会远远大于压缩串(如果你需要针对每一个 URL 进行 LZW 压缩,则这个必不可少。不过可以针对相同的 host 进行字典的共用,不过这不是自己找麻烦么)。
  2. 针对 URL 的缩短,数据通常在 100B ~ 1000B 之间,在这个范围内,我自己写的 LZW 压缩比是大于 1 的。也就是说,最后的结果,会超出原有的数值(不过,发给用户的压缩串就短了很多,不过这就带来了数对字典存服务器,之后还会有状态保存的问题)。

之后就是发号的思路了。其实这个也挺有意思的。他和秒杀的库存数是类似的。要求并发条件下不会出现发重号或者突然挂掉的问题。并发条件下不发重号。这个就是和分布式数据库的自增 id 生成业务类似,可以参考这个的实现思路(这个还挺多的,有用 redis 的,有自建服务的)。

然后,发号之后,可以使用 array 或者 hashmap 进行存储。不过,有一个小的优化的地方,自增 id 假设是从 0 开始的整数,那似乎交给用户的结果为纯数字,似乎是有点 low。不过不要紧,可以自己写一个 62 (26+26+10) 的进制转换器,分别映射到 [0-9|a-z|A-Z] 这么 62 个数,这样,看起来就很高端大气了。

总的来说,Leetcode 的这道面试题其实挺有意思的。估计面试官也是想考察这个人的思路的广阔性和思考的深度。而且针对其不同的业务场景和企业的发展期,做出不同的技术选型。同时也能考察这个人的沟通能力。不得不说真的好玩。

没有永远的银弹,只有恰到好处的击杀。这就是编程的魅力啊。

1 Reply to “短链的实现”

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.