X

系统设计面经 如何设计一个推特Twitter系统

当前很多大厂的面试中,除了会被问到类似leetcode上的算法题目之外,系统设计也是常被考到的一类题型。本篇文章我们来分享一下关于大规模系统设计的问题,比较典型的例子就是设计一个类似于推特的社交服务。

首先,我们需要明确一点,系统设计与算法不同,并没有一个标准的答案或者一套精确的测试用例。一千个考官心中会有一千个哈姆雷特。对于这一轮的面试,我们需要做好以下3个方面:

  1. 做到与考官的充分沟通,明确他的需求。
  2. 你的设计中一定要有亮点。
  3. 尽可能的让你的设计没有明显的漏洞。

言归正传,对于设计一个推特系统,首先我们要对该系统提出几项功能,比如:

  1. 发推功能。
  2. timeline
    1. 自己的timeline。显示所有自己的推文。
    2. 主页timeline。显示所有关注人的推文。
  3. 关注其他用户

以上只是举例,大家可以根据自身情况设计出更多的功能。接下来我们开始尝试设计出该推特系统。简单来看,我们可以使用关系型数据库(比如MySQL)来构建两个数据表,一个用户表和一个推文表。其中用户表包含字段user_id与user_name,存储了所有用户的信息。而推文表包含t_id(推文id),user_id以及contents三列,记录了每一个用户发表的所有推文信息。两个表通过user_id作为外键连接。一个用户可以发表多条推文,因此用户表与推文表之间存在1对多的映射关系。

在一个小型系统中,对于上述的数据库模型,不存在任何的效率问题。但对于类似于推特这样超大规模的系统,推文表中可能会存在上万亿条数据,当一个用户访问他的主页timeline时,我们需要在庞大的推文表中查找出所有他关注人发表过的推文,并组合成一个列表返回给终端显示,这显然是一个十分耗时的工作,此外,同一时刻还会有成千上万的用户在进行着同样的请求,对于这样一个高费时的操作,是你必须要面对的问题。在面试过程中,即使你没有意识到这个问题,你的面试官也会将该难题抛给你,你的解决方案将体现出你的价值所在。

对于twitter这样超大型的网络服务,用户浏览推文的频率是非常高的,因此让用户快速的看到他们的主页timeline是一个非常重要的点。通常情况下,每次request的响应时间不应该超过1秒钟。其实不仅仅是推特,包括facebook,微信等其他大型服务来说,快速响应是系统设计的重中之重。

接下来我们看看推特的系统是如何解决该问题的。我们从头来模拟一个用户打开推特到他看到主页timeline的过程

  1. 用户打开他的主页timeline页面。
  2. 接下来,浏览器或者app会将该请求通过http协议传送到推特服务器。
  3. 大型服务通常都会使用到负载均衡器(load balance,以下简称LB),LB会根据你的ip地址等信息将接受到的http请求分发到一个响应最快的服务器或数据中心去处理。这一步骤叫做fan out。
  4. 接下来推特的服务器会首先在in-memory database(例如比较有名的Redis)中查找你要请求的timeline信息。听到这里,你可能会觉得非常不可思议,难道集群中的所有服务器的内存中都要存储所有用户的timeline信息吗?实际上内存中存储的只是一部分用户的timeline,这部分用户即是近期的活跃用户。非活跃用户的timeline信息会在一定时间后删除。另外,一个用户的信息会存在3台服务器中,LB会在这3台服务器中选择响应速度最快的一台进行连接,并将该内存中的数据返回给用户的终端设备。只有当内存中不存在该用户的信息时,才会真正的去请求数据库执行庞大的select SQL文。换句话说,如果你经常打开推特,你会发现你timeline的显示速度非常快,反之当你在很久之后重新启动推特时,显示速度会相对较慢。
  5. 另外,你可能会提出另一个问题,服务器是如何保证内存中每个用户的timeline信息是最新的呢?这是用户发文之后,服务器需要做的一项工作。当用户发布或更新一条推文后,服务器会更新该用户所有活跃粉丝在内存中的timeline,以保证所有timeline信息的实时性。比如用户A有100名粉丝,当他发布一条推文后,内存中这100名粉丝的timeline信息都会进行更新,并且,每个粉丝的信息会保存在3台服务器中,因此更新操作需要进行300次,即时间复杂度为O(3n),n为粉丝数量。不过这又会衍生出另一个问题,如果该用户是一个名人,拥有上千万的粉丝,他每发一条推文,服务器便要更新上千万人的timeline列表,在此基础上再乘以3,这对系统的消耗同样非常巨大。因此,当名人发推时,系统可以不对其粉丝的timeline列表进行更新,当粉丝获取完其timeline列表后再异步去执行sql文获取名人的推文,最后在合并至终端的显示列表中即可。
  6. 内存中的数据定期存储至数据库。

总结:

以上就是我们设计的一个简易的推特系统,他的关键在于能够满足在数据量非常巨大的情况下,用户依旧可以快速的访问他们各自的timeline列表。对于一个用户来说,看推的速度要远远重要于发推的速度。因此我们通过对用户在发推后的数据进行预处理操作,大大提高了访问速度。这是面试时你需要展示给面试官的关键点。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/系统设计面经-如何设计一个推特twitter系统/
Categories: 系统设计
kwantong: