面试-系统设计题

it2024-12-21  11

系统设计题

凡是不涉及高并发的,基本可以采用 Google 的三个技术解决,即 GFS、MapReduce 和 Bigtable,这三个技术被称为“Google 三驾马车”,Google 只公开了论文而未开源代码,开源界对此非常有兴趣,仿照这三篇论文实现了一系列软件,如 Hadoop、HBase、HDFS 及 Cassandra 等。

在 Google 这些技术还未出现之前,企业界在设计大规模分布式系统时,采用的架构往往是 database+sharding+cache,现在很多公司(比如 taobao、weibo.com)仍采用这种架构。在这种架构中,仍有很多问题值得去探讨。如采用什么数据库,是 SQL 界的 MySQL 还是 NoSQL 界的 Redis/TFS,两者有何优劣?采用什么方式 sharding(数据分片),是水平分片还是垂直分片?

据网上资料显示,weibo.com 和 taobao 图片存储中曾采用的架构是Redis/MySQL/TFS+sharding+cache,该架构解释如下:前端 cache 是为了提高响应速度,后端数据库则用于数据永久存储,防止数据丢失,而 sharding 是为了在多台机器间分摊负载。 最前端由大块大块的 cache 组成,要保证至少 99%(该数据在 weibo.com 架构中的是自己猜的,而 taobao 图片存储模块是真实的)的访问数据落在 cache 中,这样可以保证用户访问速度,减少后端数据库的压力。此外,为了保证前端 cache 中的数据与后端数据库中的数据一致,需要有一个中间件异步更新(为什么使用异步?理由简单:同步代价太高。异步有缺点,如何弥补?)数据,这个有些人可能比较清楚,新浪有个开源软件叫 Memcachedb(整合了 Berkeley DB 和 Memcached),正是完成此功能。另外,为了分摊负载压力和海量数据,会将用户微博信息经过分片后存放到不同节点上(称为“Sharding”)。

这种架构优点非常明显:简单,在数据量和用户量较小的时候完全可以胜任。但缺点是扩展性和容错性太差,维护成本非常高,尤其是数据量和用户量暴增之后,系统不能通过简单地增加机器解决该问题。

1.设计一个 DNS 的 Cache 结构,要求能够满足每秒 5000 次以上的查询,满足 IP 数据的快速插入,查询的速度要快(题目还给出了一系列的数据,比如站点数总共为 5000 万、IP 地址有 1000 万等)。
2)有 N 台机器,M 个文件,文件可以以任意方式存放到任意机器上,文件可任意分割成若干块。假设这 N 台机器的宕机率小于 1/3,想在宕机时可以从其他未宕机的机器中完整导出这 M 个文件,求最好的存放与分割策略。

现在通用的分布式文件系统的副本存放策略。一般是将大文件切分成小的 block(如 64MB)后,以 block 为单位存放三份到不同的节点上,这三份数据的位置需根据网络拓扑结构配置,一般而言,如果不考虑跨数据中心,可以这样存放:两个副本存放在同一个机架的不同节点上,而另外一个副本存放在另一个机架上,这样从效率和可靠性上,都是最优的(这个 Google 公布的文档中有专门的证明,有兴趣的可参阅一下)。如果考虑跨数据中心,可将两份存在一个数据中心的不同机架上,另一份放到另一个数据中心。

3)假设有三十台服务器,每台服务器上面都存有上百亿条数据(有可能重复),如何找出这三十台机器中,根据某关键字,重复出现次数最多的前 100 条?要求使用 Hadoop 来实现。
4)设计一个系统,要求写速度尽可能快,并说明设计原理。

涉及 BigTable 的模型。主要思想是将随机写转化为顺序写,进而大大提高写速度。具体是:由于磁盘物理结构的独特设计,其并发的随机写(主要是因为磁盘寻道时间长)非常慢,考虑到这一点,在 BigTable 模型中,首先会将并发写的大批数据放到一个内存表(称为“memtable”)中,当该表大到一定程度后,会顺序写到一个磁盘表(称为“SSTable”)中,这种写是顺序写,效率极高。

此时可能有读者问,随机读可不可以这样优化? 答案是:看情况。通常而言,如果读并发度不高,则不可以这么做,因为如果将多个读重新排列组合后再执行,系统的响应时间太慢,用户可能接受不了,而如果读并发度极高,也许可以采用类似机制。

5)设计一个高并发系统,说明架构和关键技术要点。
6)有 25T 的 log(query->queryinfo),log 在不断地增长,设计一个方案,给出一个 query能快速返回 queryinfo。
最新回复(0)