共计 2460 个字符，预计需要花费 7 分钟才能阅读完成。
提出问题
如何设计一个像百度短网址一样的服务，一个生成短网址、将短网址定向到原始 URL 的服务。
解决方案
首先，需要一个一对一的映射表，去获取短 URL，然后根据他恢复出完整的 URL。这将会涉及到将这些数据保存到数据库。
我们要考虑下面这些问题：
短网址转换时候的长度是多少？
映射函数是什么？
提供服务的是单机还是集群？
转换长度
我们假设我们设计的系统可以提供超过 10000 亿的 URL，如果我们以从 62 个字符 [a-z,A-Z,0-9] 中选取 n 个作为短网址，我们可以存储 62^n 个网址。所以，在满足条件的情况下，我们选择最小的 n。对于我们的需求来说，我们取 n =7，这样可以提供短网址的个数是 62^7 ~= 35000 亿。
一般方案
一切从简，我们假定短网址类似 http://dwz.com/<alias_hash>，其中 alias_hash 是一个计算过得字符串。
最开始呢，我们把所有的映射存到一个单机数据库，直接生成一个随机的长度为 7 的字符串 alias_hash 作为映射中的键 ID。
所以，我们只需要存储 <ID, URL>。当使用者输入完整网址 http://www.google.com，系统生成一个像 abcd123 一样的长度为 7 的随机字符串作为 ID，存储到数据库中就是 <abcd123, http://www.google.com>。
使用的时候，访问 http://dwz.com/abcd123，系统搜索 IDabcd123，找到后重定向到 http://www.google.com。
此方案存在的问题
我们不能保证通过长 URL 生成 alias_hash 的唯一性。生成 alias_hash 的时候可能会发生冲突（2 个长 URL 映射到同一个短 URL），但我们需要每个长 URL 生成的短 URL 都是唯一的，这样我们才能根据短 URL 定位到唯一的长 URL，但是计算 alias_hash 的函数是单向函数。
这里是不是单向函数其实不重要，我们不需要根据短网址再次做计算，只需要搜索，不知道作者为什么这么写。
改进方案
一个很简单但依然高效的方案，建立这样的数据表：
Table Tiny_Url(
ID : int PRIMARY_KEY AUTO_INC,
Original_url : varchar,
Short_url : varchar
)
其中自增主键 ID 用来做这样的转换：(ID, 10) <==> (short_url, BASE)。使用者随时插入一个长 URL，会返回最新的插入 ID，把他转化为短 URL 标识，保存这个短 URL 标识，并返回给使用者。
转换方法源码（用于 ID 和短 URL 的互相转换）
string idToShortURL(long int n)
{
// Map to store 62 possible characters
char map[] = “abcdefghijklmnopqrstuvwxyzABCDEF”
“GHIJKLMNOPQRSTUVWXYZ0123456789”;
string shorturl;
// Convert given integer id to a base 62 number
while (n)
{
shorturl.push_back(map[n%62]);
n = n/62;
}
// Reverse shortURL to complete base conversion
reverse(shorturl.begin(), shorturl.end());
return shorturl;
}
// Function to get integer ID back from a short url
long int shortURLtoID(string shortURL)
{
long int id = 0; // initialize result
// A simple base conversion logic
for (int i=0; i < shortURL.length(); i++)
{
if (‘a’ <= shortURL[i] && shortURL[i] <= ‘z’)
id = id*62 + shortURL[i] – ‘a’;
if (‘A’ <= shortURL[i] && shortURL[i] <= ‘Z’)
id = id*62 + shortURL[i] – ‘A’ + 26;
if (‘0’ <= shortURL[i] && shortURL[i] <= ‘9’)
id = id*62 + shortURL[i] – ‘0’ + 52;
}
return id;
}
服务器集群
如果我们的服务要处理大量数据，分布式存储可以提高我们的吞吐量。思路也很简单，计算出原始 URL 的 hash 值，然后去对应的及其存储，然后就和单机情况一样了。通常使用一致性 hash 路由到集群中对应的节点。
下面的例子是伪代码：
获取短 URL
将原始 URL 哈希为 2 为数字，假设为 hash_val。
用 hash_val 定位一致性 hash 环上的机器。
像对应的数据库中插入原始 URL，通过 idToShortURL()获取短 URL
合并 hash_val 和短 URL 作为我们最终短 URL（长度 =8），返回给使用者。
根据短 URL 获取原始 URL
从最终短 URL 中获取前两个字符作为机器标识 hash_val。
通过 hash_val 定位到机器。
通过最终短 URL 中的剩余 6 个字符作为短 URL，去数据库获取对应的记录。
返回原始 URL 给使用者。
这里可能有问题，坐着的意思可能是最多 62 台机器，应该是第一个字符是标识机器的，值可能是 [a-z,A-Z,0-9] 中的一个。
看了评论，这里有个问题，如果某台机器挂了，摘掉之后，需要将该机器上的数据复制到一致性 hash 环上的下一台机器的时候，会发生冲突，所以还是使用 redis 之类的生成全局唯一的 ID，直接落到环上对应的机器，这样设计更好。
其他考虑
这里我想深入讨论的是使用 GUID（全局唯一标识）作为 ID，与增量 ID 相比有哪些优缺点？
如果你深入 insert/query 处理语句的话，你会发现使用随机字符串作为 ID 可能会牺牲一小部分性能。特别是当已经有无数的记录的时候，插入是很昂贵的操作，数据库需要寻找合适的页存储插入的 ID。但是，使用增量的 ID，插入会简单很多，直接找到最后的页就行了。
