提出问题如何设计一个像百度短网址一样的服务，一个生成短网址、将短网址定向到原始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 urllong 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 = id62 + shortURL[i] - ‘a’; if (‘A’ <= shortURL[i] && shortURL[i] <= ‘Z’) id = id62 + 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，插入会简单很多，直接找到最后的页就行了。