网址缩短服务

前一段时间帮一个朋友做了一个非常简单的网址缩短服务，已经上线运行了一段时间，这里把当时设计的一些想法分享出来，等有时间我会把代码也发布出来，程序很简单，用 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映射关系）基础上再增加一个查找表的方法来解决。

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