当前很多大厂的面试中，除了会被问到类似leetcode上的算法题目之外，系统设计也是常被考到的一类题型。本篇文章我们来分享一下关于大规模系统设计的问题，比较典型的例子就是设计一个类似于推特的社交服务。
首先，我们需要明确一点，系统设计与算法不同，并没有一个标准的答案或者一套精确的测试用例。一千个考官心中会有一千个哈姆雷特。对于这一轮的面试，我们需要做好以下3个方面：
- 做到与考官的充分沟通，明确他的需求。
- 你的设计中一定要有亮点。
- 尽可能的让你的设计没有明显的漏洞。
言归正传，对于设计一个推特系统，首先我们要对该系统提出几项功能，比如：
- 发推功能。
- timeline
- 自己的timeline。显示所有自己的推文。
- 主页timeline。显示所有关注人的推文。
- 关注其他用户
以上只是举例，大家可以根据自身情况设计出更多的功能。接下来我们开始尝试设计出该推特系统。简单来看，我们可以使用关系型数据库（比如MySQL）来构建两个数据表，一个用户表和一个推文表。其中用户表包含字段user_id与user_name，存储了所有用户的信息。而推文表包含t_id（推文id），user_id以及contents三列，记录了每一个用户发表的所有推文信息。两个表通过user_id作为外键连接。一个用户可以发表多条推文，因此用户表与推文表之间存在1对多的映射关系。
在一个小型系统中，对于上述的数据库模型，不存在任何的效率问题。但对于类似于推特这样超大规模的系统，推文表中可能会存在上万亿条数据，当一个用户访问他的主页timeline时，我们需要在庞大的推文表中查找出所有他关注人发表过的推文，并组合成一个列表返回给终端显示，这显然是一个十分耗时的工作，此外，同一时刻还会有成千上万的用户在进行着同样的请求，对于这样一个高费时的操作，是你必须要面对的问题。在面试过程中，即使你没有意识到这个问题，你的面试官也会将该难题抛给你，你的解决方案将体现出你的价值所在。
对于twitter这样超大型的网络服务，用户浏览推文的频率是非常高的，因此让用户快速的看到他们的主页timeline是一个非常重要的点。通常情况下，每次request的响应时间不应该超过1秒钟。其实不仅仅是推特，包括facebook，微信等其他大型服务来说，快速响应是系统设计的重中之重。
接下来我们看看推特的系统是如何解决该问题的。我们从头来模拟一个用户打开推特到他看到主页timeline的过程
- 用户打开他的主页timeline页面。
- 接下来，浏览器或者app会将该请求通过http协议传送到推特服务器。
- 大型服务通常都会使用到负载均衡器（load balance，以下简称LB），LB会根据你的ip地址等信息将接受到的http请求分发到一个响应最快的服务器或数据中心去处理。这一步骤叫做fan out。
- 接下来推特的服务器会首先在in-memory database（例如比较有名的Redis）中查找你要请求的timeline信息。听到这里，你可能会觉得非常不可思议，难道集群中的所有服务器的内存中都要存储所有用户的timeline信息吗？实际上内存中存储的只是一部分用户的timeline，这部分用户即是近期的活跃用户。非活跃用户的timeline信息会在一定时间后删除。另外，一个用户的信息会存在3台服务器中，LB会在这3台服务器中选择响应速度最快的一台进行连接，并将该内存中的数据返回给用户的终端设备。只有当内存中不存在该用户的信息时，才会真正的去请求数据库执行庞大的select SQL文。换句话说，如果你经常打开推特，你会发现你timeline的显示速度非常快，反之当你在很久之后重新启动推特时，显示速度会相对较慢。
- 另外，你可能会提出另一个问题，服务器是如何保证内存中每个用户的timeline信息是最新的呢？这是用户发文之后，服务器需要做的一项工作。当用户发布或更新一条推文后，服务器会更新该用户所有活跃粉丝在内存中的timeline，以保证所有timeline信息的实时性。比如用户A有100名粉丝，当他发布一条推文后，内存中这100名粉丝的timeline信息都会进行更新，并且，每个粉丝的信息会保存在3台服务器中，因此更新操作需要进行300次，即时间复杂度为O(3n)，n为粉丝数量。不过这又会衍生出另一个问题，如果该用户是一个名人，拥有上千万的粉丝，他每发一条推文，服务器便要更新上千万人的timeline列表，在此基础上再乘以3，这对系统的消耗同样非常巨大。因此，当名人发推时，系统可以不对其粉丝的timeline列表进行更新，当粉丝获取完其timeline列表后再异步去执行sql文获取名人的推文，最后在合并至终端的显示列表中即可。
- 内存中的数据定期存储至数据库。
总结：
以上就是我们设计的一个简易的推特系统，他的关键在于能够满足在数据量非常巨大的情况下，用户依旧可以快速的访问他们各自的timeline列表。对于一个用户来说，看推的速度要远远重要于发推的速度。因此我们通过对用户在发推后的数据进行预处理操作，大大提高了访问速度。这是面试时你需要展示给面试官的关键点。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/系统设计面经-如何设计一个推特twitter系统/