delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

23 Dec 2009

网址缩短服务

前一段时间帮一个朋友做了一个非常简单的网址缩短服务,已经上线运行了一段时间,这里把当时设计的一些想法分享出来,等有时间我会把代码也发布出来,程序很简单,用 web.py 做的。

网址缩短服务需要考虑两个问题,第一个问题是如何有效地查询,即,作为约束条件,在访问"短网址"的时候,它必须能够迅速的将结果返回;第二个问题是如何有效地将写操作复制出去。还有一点就是,缩短形成的短网址要真的越短越好。

接口

整个服务包括两个主要接口:一个是请求短网址,输入为网址(作为HTTP回应),输出为短网址;另一个是请求重定向,输入为短网址,输出为到短网址对应的真实网址的HTTP 302重定向回应。

设计

__请求短网址的流程__大致如下:

首先,检测输入的网址是否有效。

然后,计算输入的网址的 SHA256 散列值(计算时增加一个系统全局的salt值)的 URL-safe base64,并查找此散列串是否已经存在;如果已经存在,但对应的网址不同,目前版本将返回一异常(由于SHA256设计中的雪崩效应,这种情况基本可以忽略)。

如果不存在,则从前3位开始逐字向后取散列串,在查找表中查找到找到相同URL,或找不到结果为止;如果找不到结果,则将目前散列串的子串以及网址插入。

__请求重定向的流程__大致如下:

首先检测输入是否有效(不超长或超短)。

然后,直接从Berkeley DB中查找字符串对应的URL(实际实现中,将db文件以散列串首个字符命名,以利于未来将负载分散到不同的服务器)。

返回302回应。

未来的改进

目前的设计假定存在 2^0或2^1或2^2 .. 2^6 个节点能够提直接提供转向服务。转向回应信息可以在前端代理上永久缓存,因此可以通过增加前端代理服务器,而不是后端转向服务节点的方式来进行扩展。目前设计中故障转移等机制比较简单(根据SHA256计算出来的优先权值轮转),未来版本需要解决集群的原子提交问题。

目前的设计没有考虑自定义短网址,比如 foo.com/survey 这样的情况。这个问题可通过在长域名表(完整SHA256 base64与URL映射关系)基础上再增加一个查找表的方法来解决。

目前设计没有考虑删除以及禁止访问某些短网址的情况。