目录

  1. 导言
  2. 三种链接生成办法
  3. 重定向进程
  4. 缓存优化
  5. 高可用规划
  6. 跋文

01 导言

1）布景

这是本人在面试“字节抖音”部分的一道体系规划题，岗位是“后端高级开发工程师”，二面的时分问到的。一开端，面试官笑眯眯地让我做个自我介绍，然后聊了聊项目。

当完美无瑕（闪烁其词）地聊完项目，并写了一道算法题之后。

面试官就开端发问了：小伙子，简历里边写到了了解架构规划是吧，那你知道程序规划的‘三高’指什么吗？

我心想，那不是因为程序员的体系不靠谱，领导不当人，天天加班改 BUG，导致年纪轻轻都高血脂、高血压和高血糖嘛！

可是，已然是面试，那领导必定不愿意听这，所以我答复：程序三高，便是体系规划时需求考虑的高并发、高功能和高可用：

  • 高并发便是在体系开发的进程中，需求确保体系能够同时并行处理许多恳求；
  • 高功能是指程序需求尽或许地占用更少的内存和 CPU，而且处理恳求的速度要快；
  • 高可用一般描述体系在一段时刻内不行服务的时分很短，比方全年停机不超越 31.5 秒，俗称 6 个 9，即确保可用的时刻为 99.9999%。

所以，面试官轻轻点头，心想小伙子还行，已然这难不住你，那我可得出大招了，就来道体系规划题吧！

2）需求阐明

众所周知，当事务场景需求给用户发送网络地址或许二维码时，因为地址的长度比较长，一般为了占用更少的资源和提高用户体会。例如，谷歌搜索“计算机”词条地址如下：

https://www.google.com/search?q=%E8%AE%A1%E7%AE%97%E6%9C%BA&ei=KNZ5Y7y4MpiW-AaI4LSACw&ved=0ahUKEwi87MGgnbz7AhUYC94KHQgwDbAQ4dUDCBA&uact=5&oq=%E8%AE%A1%E7%AE%97%E6%9C%BA&gs_lcp=Cgxnd3Mtd2l6LXNlcnAQAzIECAAQQzIFCAAQgAQyBQgAEIAEMgUIABCABDIFCC4QgAQyBQgAEIAEMgUIABCABDIFCAAQgAQyBQgAEIAEMgUIABCABDoKCAAQRxDWBBCwAzoLCC4QgAQQxwEQ0QM6FggAEOoCELQCEIoDELcDENQDEOUCGAE6BwguENQCEENKBAhBGABKBAhGGABQpBZYzSVglydoA3ABeACAAZ0DiAGdD5IBCTAuNy4xLjAuMZgBAKABAbABCsgBCsABAdoBBAgBGAc&sclient=gws-wiz-serp

很明显，假如将这一长串网址发给用户，是十分不“面子”的。而且，遇到一些有字数限制的体系里边，比方微博发帖子就有字数限制，必定无法发送这样的长链接地址。一般的短信链接中，大多也都是短链接地址：

听说你学过架构设计？来，弄个短链系统

所以，为了提高用户体会，以及日常事务的需求。咱们需求规划一个短链接生成体系，除了事务功用完结以外，咱们还得为全国的网络地址服务。在这么大的用户量下，数据该如何存储，高并发如何处理呢？

02 三种链接生成办法

1）需求分析

我心想，这面试官看着“慈眉善目”还笑眯眯的，但出的标题可不简略，这种类型的体系需求考虑的点太多了，肯定不能掉以轻心。

所以，我分别从链接生成、网址拜访、缓存优化和高可用四个方面开端着手规划。

首先，生成短链地址，能够考虑用 UUID 或许自增 ID。对于每一个长链接转短链地址时，都必须生成一个全局仅有的短链值，不然就会产生抵触。所以，短链接的特点是：

  • 数据存储量很大，全国的网址每天至少都是百万个短链接地址需求生成；

  • 并发量也不小，遇到同时来拜访体系，按一天 3600 秒来算，平均每秒至少上千个恳求数；

  • 短链接不行重复，不然会引起数据拜访抵触。

2）雪花算法

首先，生成短链接，能够用雪花算法+哈希的办法来完结。

听说你学过架构设计？来，弄个短链系统

雪花算法是在分布式场景下，依据时刻戳、不同的机器 ID 以及序列号生成的仅有数。它的长处在于简略便利，随取随用。

经过雪花算法取到的仅有数，再用哈希映射，将数字转为一个随机的字符串，假如短链字符串比较长，能够直接取前 6 位。可是，因为哈希映射的成果或许会产生抵触，所以对哈希算法的要求比较高。

2）62 进制数生成短链接

除了雪花算法，还能够用 62 进制数（A-Za-z0-9）来生成短链接地址。首先得到一个自增 ID，再将此值转化为 62 进制（a-zA-Z0-9）的字符串，一个亿的数字转化后也就五六位（1亿 ->zAL6e）。

将短链接服务器域名，与这个字符串进行拼接，就能得到短链接的 URL，比方：t.cn/zAL6e。

而生成自增 ID 需求考虑功能影响和并发安全性，所以咱们能够经过 Redis 的 incr 命令来做一个发号器，它是一个原子操作，因此咱们不用忧虑数字的安全性。而 Redis 是内存操作，所以效率也挺高。

3）随机数+布隆过滤器

除了自增 ID 以外，咱们还能够生成随机数再转 62 进制的办法来生成短链接。可是，因为随机数或许重复，因此咱们需求用布隆过滤器来去重。

布隆过滤器是一个奇妙规划的数据结构，它的原理是将一个值屡次哈希，映射到不同的 bit 位上并记录下来。当新的值运用时，经过同样的哈希函数，比对各个 bit 位上是否有值：假如这些 bit 位上都没有值，阐明这个数是仅有的；不然，就或许不是仅有的。

当然，这或许会产生误判，布隆过滤器必定能够发现重复的值，但 也或许将不重复的值判别为重复值，误判率大约为 0.05%，是能够接受的范围，而且布隆过滤器的效率极高。

因此，经过布隆过滤器，咱们能判别生成的随机数是否重复：假如重复，就从头生成一个；假如不重复，就存入布隆过滤器和数据库，从而确保每次取到的随机数都是仅有的。

4）将短链接存到数据库

存库时，或许会因为库存量和技能栈，选用不同的数据库。但因为公司部分用 MySQL 比较多，且当时标题未提及技能选型，所以咱们仍是选用 MySQL 作为持久化数据库。

每当生成一个短链接后，需求在 MySQL 存储短链接到长链接的映射联系并加上仅有索引，即 zAL6e -> 实在URL。

03 重定向进程

浏览器拜访短链接服务时，依据短链地址取到原始 URL，然后进行网址重定向。咱们一般有两种重定向办法：

  • 一种是回来给浏览器 301 响应码永久重定向，让其后续直接拜访实在的 URL 地址；
  • 一种是 302 暂时重定向，让浏览器当时这次拜访实在 URL，但后续恳求时仍是依据短链地址拜访。

尽管用 301 浏览器只需一次恳求，后续能够直接从浏览器获取长链接，这种办法能够提高拜访速度，可是它无法计算短链接的拜访次数。

所以依据事务需求，咱们一般选用 302 重定向。

04 缓存规划

因为短链接是分发到多个用户手里的，或许在短时刻内会屡次拜访，所以从 MySQL 写入/获取到长链接后能够放入 redis 缓存。

1）加入缓存

而且，短链接和长链接的对应联系一般不会频频修改，所以数据库和缓存的一致性经过简略的旁路缓存形式来确保：

  • 读（Read）数据时，若缓存未射中，则先读 DB，从 DB 中取出数据，放入缓存，同时回来响应；
  • 写（Write）数据时，先更新 DB，再删除缓存。

当用户需求生成短链接时，先到这个映射表中看一下有没有对应的短链接地址。有就直接回来，并将这个 key-value 的过期时刻添加一小时；没有就从头生成，而且将对应联系存入这个映射表中。

缓存的筛选战略能够选用：

  • LRU：Least Recently Used，最近最少运用算法，最近经常被读写的短链地址作为热门数据能够一向存在于缓存，筛选那些很久没有拜访过的短链 key；

  • LFU：Least Frequently Userd，最近最不频频运用算法，最近拜访频率高的短链地址作为热门数据，筛选那些拜访频率较低的短链 key。

2）缓存穿透

可是，运用缓存也避免不了一些异常情况，比方“缓存穿透”。所谓缓存穿透，便是查询一个缓存和数据库中都不存在的短链接，假如并发量很大，就会导致所有在缓存中不存在的恳求都打到 MySQL 服务器上，导致服务器处理不了这么多恳求而堵塞，乃至溃散。

所以，为了避免不法分子经过相似“缓存穿透”的办法来进犯服务器，咱们能够选用两种办法来应对：

  • 对不存在的短链地址加缓存，key 为短链接地址，value 值为空，过期时刻能够设置得短一点；
  • 选用布隆过滤器将已有的短链接屡次哈希后存起来，当有短链接恳求时，先经过布隆过滤器判别一下该地址是否存在数据库中；假如不在，则阐明数据库中不存在该地址，就直接回来。

05 高可用规划

因为缓存和数据库持久化依赖于 Redis 和 MySQL，因此 MySQL 和 Redis 的高可用性必须要确保。

1）MySQL 高可用

MySQL 数据库选用主从复制，进行读写别离。Master 节点进行写操作，Slave 节点用作读操作，而且能够用 Keepalived 来完结高可用。

Keepalived 的原理是选用虚拟 IP，检测入口的多个节点，选用一台热备服务器作为主服务器，并分配给它一个虚拟 IP，外部恳求都经过这个虚拟 IP 来拜访数据库。

同时，Keepalived 会实时检测多个节点的可用状态，当发现一台服务器宕机或呈现毛病时，会从集群中将这台服务器踢除。假如这台服务器是主服务器，keepalived 会触发推举操作，从服务器集群中再选出一个服务器充任 master 并分配给它相同的虚拟 IP，以此完结毛病搬运。

而且，在 Keepalived 的支持下，这些操作都不需求人工参加，只需修正毛病机器即可。

2）Redis 高可用

因为在大数据高并发的场景下，写恳求全部落在 Redis 的 master 节点上，压力太大。假如一味地选用添加内存和 CPU 这种纵向扩容的办法，那么一台机器所面临的磁盘 IO，网络等压力逐步增大，也会影响功能。

所以 Redis 选用集群形式，完结数据分片。而且，加入了岗兵机制来确保集群的高可用。它的基本原理是岗兵节点监控集群中所有的主从节点，当主节点宕机或许产生毛病今后，岗兵节点会符号它为主观下线；当足够多的岗兵节点将 Redis 主节点符号为主观下线，就将其状态改为客观下线。

此时，岗兵节点们经过推举机制选出一个领头岗兵，对 Redis 主节点进行毛病搬运操作，以保障 Redis 集群的高可用，这整个流程都不需求人工干预。

3）体系容错

服务在上线之前，需求做好充沛的事务量点评，以及功能测试。做好限流、熔断和服务降级的逻辑，比方：选用令牌桶算法完结限流，hystrix 框架来做熔断，而且将常用装备放到能够热更新的装备中心，便利对其实时更改。

当事务量过大时，将同步使命改为异步使命处理。经过这些服务管理方案，让体系愈加安稳。

06 跋文

当我答完最终一个字的时分，面试官看着我，目光中充满了“欣赏”与疑问。我想，他应该是被我这番体现给镇住了，此次面试应该是万无一失。

​可是，出奇地，面试官没有对方才的架构规划提出点评，只看了看我说：“那今天的面试就到这里，你有什么想要问的吗？”

这下，轮到我震动了，那究竟过不过呢？倒是给句话呀，所以我问道：“经过这次面试，您觉得我有哪些方面需求提高呢？”

“算法和项目需求再多练练，可是我发现了你一个长处。”面试官笑了笑接着说，“八股文背的倒是挺不错的！”

悬着的心总算放下，我心想：“哦，那稳了~”