系统设计题 TinyURL

之前做了几轮系统面试的模拟面，感觉系统设计这个东西真的非常不确定，说什么的都可以。那么接下来，从个最开始的来呗 先说个简单的东西 TinyURL

TinyURL是啥呢？就是当年微博和Twitter兴起的时候，很多网站的链接是没有办法缩短的足够短的。这样一来岂不是有很多帖子要发布出去或者就只有一个链接干不了别的了么？解决办法就是有几家公司或者社会团体把一个相对比较长的URL映射到一个短的URL上。这样一来。长URL对应短URL。微博就好弄了。

要求

好了 关键点一：我们设计这个东西需要有什么要求吗？（啥叫要求？一个形容词能形容的才叫要求，如果一个形容词装不下，那好了，别继续想了，答案肯定不对）

1. 这个系统必须highly available 啥意思？就是说，我给你一个短的URL你必须得给我一个长的URL，不能宕机。为什么要有这个要求，因为这个产品是在别人产品之中要用到的东西，牵一发而动全身，所以一定要能够在部分系统失效的时候，还要能够返回结果，否则不光自己不行 大家一起不行。

2. 整个系统一定要快。为什么要快，还是一样道理。这个系统是别人系统里面要用到的东西，你的延迟是别人延迟的一个组成部分，你慢了可是损害人家KPI的，所以你绝对要快，要实时给信息。

3. 整个系统要有一定的保密性。一个人看短URL应该要能猜不出长URL。 这个是为什么呢。。。

关键点二： 这个系统有什么特点吗？这个问题是自己想的，之所以要想这个特点， 是因为你能够确定系统的特点，你就可以在接下来要用什么数据库要怎么存数据这里有很大的帮助。

1.这个系统明显的读大于写。因为世界上就那么几个网页，但是每天大家可能都要读好多次。

2. 这个系统不太需要大文件读写（就文本换文本，要不然呢）

好了，高层次的东西答完了，接下来就开始来设计这个系统了

应用层级

分布式的应用服务来处理：

1. URL映射的CRUD

（好像也没什么别的功能了）

首先，长URL是真是存在的，短URL怎么创建？

1. 计数法

一个中央计数器。每次请求给一个单调递增的数字。想要32位给32位，想要64位给64位。

2. 加密法

找一个加密的算法，然后算出一个唯一的hash值存上。

然后，算法搞定了，如何创建？在数据库里面找找，这个东西是否存在。如果存在，返回已经建立好的值或者返回失败。如果不存在，新创建一个值，返回成功。

然后我们要等一下。之前说的两个方法其实是两个很不一样的approach。为什么呢？

1. 计数法是离线生成短连接的办法。因为这里我们需要有一个中央计数器。这个计数器是不属于任何一个application service的。所以，这样一来，这个计数器这里就一定要做多线程控制，要不然就乱了。怎么乱？就是多个长URL会对应到一个短URL，就会形成冲突。那如果管了会有什么问题了呢？慢呗。如果管了，就有可能会有多个请求同时要创建锁，所以生成过程就会比较慢。但是我们之前说了这个是读大于写的系统，所以如果写这里慢了， 可能不是一个很严重的问题。我们需要进一步的讨论。

2. 加密法是在线生成短连接的办法。因为加密算法是一定的，一个长URL唯一对应一个短URL，谁来算都是这个。所以我们不需要去问任何其他的服务器。我们可以在application里面完成生成工作。这里的问题的话，可能不是非常的直接。这里有一个问题是说如果我们有不同用户的话，多个用户的同一个长URL都对应同一个短URL。那这样可能会有问题。具体什么问题我也不知道。可能是说这样加密性能就会有损失吧。那么对应这个问题怎么解决呢？一个办法是吧UserID加到长URL里面然后一起哈希。但是这是一个half baken solution。为啥？因为之前说了我们是出于安全考虑才要生成不同的URL的。现在的UserID用可以用，但是绝对不能用一个不加密的UserID。这要出事情的。所以我们要不就再想个办法加密UserID。要不就让每个User存一个URL key。这个key每个用户只需要生成一次。所以可以慢慢来。

好了。这里说了不少关于生成连接的内容了。那查找呢？

查找的时候，我们就把短URL发给服务器。服务器直接返回相对应的长URL就可以了。这里的话，为了防止一个陌生用户随意发送随机短连接来猜出映射关系，我们在返回结果之前一定要认证用户。认证的方法就是所有网站都在用的方法就行。

那么生成和查找都有了，删除我们怎么办呀？

首先，又来了，我们是读大于写的系统。既然是读大于写，既然我们的期待值是大家都要用。那么我们就不会随便删URL的。我们在存URL的时候加一个活跃位就可以了。删除指令来了，我们只要把我们的URL标记为不活跃，我们也就没事儿了。

然后 修改呢？修改这个东西就比较微妙了。我们一般来说是不提倡长URL到处改的，但是作为一个比较典型的甩手掌柜的做法，我们可以把修改权给用户。但是也说清楚。如果用户自己改映射 后果自负。

数据

我们既然是要设计一个系统，我们自然需要解决数据存储的问题。数据怎么存呢？

首先，我们需要存relational还是Non-relational。这个答案这里很明显，我们又不sort， 然后数据都是文本。了不起加一个符号位。完全没有必要用relational。我们就用non-relational的key value pair就可以满足要求。

然后 是说数据要怎么分布。 基本上来说两种方法

1. 按照字母序分布。这个好处就是简单，你一看就知道要放哪。坏处也比较明显，就是很容易有一个特定开头的单词的访问频率比别人都高。一般来说解决办法是在这里多层分布。

2. 按照随机哈希序分布。这个的话就可以用上我们的一致性哈希来更加简单的scale。

接下来，就是数据缓存。我们之前一再说了这个东西读大于写。既然这样， 我们只要加了缓存，就会极大增强系统的速度。缓存我们可以按照CPU那么放。好几层。application里面是一级缓存，数据server里面有二级缓存。缓存一般来说是不会改变的。所以如果有变化了，可以直接广播删除。如果Cache miss了，一级二级缓存同时更新。

高级话题

1. 遥感

我们是不是要测量一些东西来方便我们的大数据需求啊？

如果这样的话，我们在不改变现有数据库结构的情况下，我们可以用另一套遥感系统， 从application直接发送用户统计，比如国家啊，性别啊，时间点啊，之类的。 这些数据的系统就是另外一套系统了，我们可以另外讨论。

2. 出错了怎么办

这也没什么可说的，动态扩容加上动态复制。我们这个系统是中央集中系统，所以会面临单点失败问题。我们就需要花最大的资源在中央系统上来解决这个问题。

3. 负载平衡

Load Balancing有好几个地方可以做。

1. 客户端和application之间

2. application和数据服务之间

3. application和缓存之间

一般来说，因为URL访问模式相对比较随机，所以我们简单的round robin就可以搞定。

4. 访问控制。

我们可以通过单独的列表来控制哪些用户可以访问这个URL。这个单独的列表也可以用数据库来存放。如果白名单里面没有的话，我们就返回401，就可以实现访问控制了。

哎哟写了还不少，以上就是我自己对于这个简单数据库的总结，欢迎大家批评添加~~~