一、分布式系统的GFS、MapReduce和Bigtable

（1）GFS一致性模型

GFS一致性模型是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。
它运行于廉价的普通硬件上，提供容错功能。现在开源界有HDFS(Hadoop Distributed File System)。

（2）MapReduce

MapReduce是针对分布式并行计算的一套编程模型。最大的优点是编程接口简单，自动备份（数据默认情况下会自动备三份），自动容错和隐藏跨机器间的通信。在Hadoop中，MapReduce作为分布计算框架，而HDFS作为底层的分布式存储系统，但MapReduce不是与HDFS耦合在一起的，完全可以使用自己的分布式文件系统替换掉HDFS。当前MapReduce有很多开源实现，如Java实现Hadoop MapReduce，C++实现Sector/sphere等。

（3）Bigtable

BigTable是用来存储结构化数据的，是非关系型数据库，是一个稀疏的、分布式的、持久化存储的多维度排序Map。Bigtable的设计目的是快速且可靠地处理PB级别的数据，并且能够部署到上千台机器上。实现包括HBase，Cassandra，levelDB等，使用也非常广泛。

二、典型场景的系统设计方案

1.设计一个系统，要求写速度尽可能高，说明设计原理。

解决方案：涉及到BigTable的模型。主要思想是将随机写转化为顺序写，进而大大提高写速度。
由于磁盘物理结构的独特设计，其并发的随机写（主要是因为磁盘寻道时间长）非常慢，考虑到这一点，在BigTable模型中，首先会将并发写的大批数据放到一个内存表（称为“memtable”）中，当该表大到一定程度后，会顺序写到一个磁盘表（称为“SSTable”）中，这种写是顺序写，效率极高。
随机读可不可以这样优化？
通常而言，如果读并发度不高，则不可以这么做，因为如果将多个读重新排列组合后再执行，系统的响应时间太慢，用户可能接受不了，而如果读并发度极高，也许可以采用类似机制。

2.有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速返回queryinfo？

解决方案：
（1）建立适当索引
（2）优化sql语句
（3）实现小数据量和海量数据的通用分页显示存储过程
（4）合理选择聚集索引

?

3.每个城市的IP段是固定的，有十万个ip段，输入IP，如何快速找出它是哪个城市的，设计并实现。

4.设计相应的数据结构和算法，尽量高效的统计一篇英文文章（总单词数目）里出现的所有英文单词，按照在文章中首次出现的顺序打印输出该单词和它的出现次数。

?

5.有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，能否开发出一个算法和系统，找出这几百亿数据的中值？
就是在一组排序好的数据中居于中间的数。由于物理内存限制，一台机器装不下所有的数据，并且尽量少用网络带宽，减少机器间网络传输。

?

6.假设已有10万个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。
解决方案：要判断这50个单词是否存在那10万个敏感词库里，明显是字符串匹配，由于是判断多个单词不是一个，属于多模式字符串匹配问题，
多模式字符串匹配问题的算法包括KMP、hash、trie、AC自动机等。
选择哪种算法需要根据题目的应用场景而定。

10万 + 50，如果允许误差的话，可以考虑使用布隆过滤器；否则，只查一次的话，可能hash最快，但hash消耗空间大，考虑tire树的话，可以针对这10万个敏感词建立trie树，然后对那50个单词搜索这棵10万敏感词构建的tire树，但用tire树同样耗费空间。

?

7.假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的IP地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域IP地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢？
设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？
解决方案：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。
这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。
或者可以建立二级索引，分别是时间和地点来建立索引。

?

8.给你10台机器，每个机器2个CPU和2GB内存，现在已知在10亿条记录的数据库里执行一次查询需要5秒，问用什么方法能让90%的查询能在100毫秒以内返回结果。

解决方案：将10亿条记录排序，然后分到10个机器中，分的时候是一个记录一个记录的轮流分，确保每个机器记录大小分布差不多，每一次查询时，同时提交给10台机器，同时查询，因为记录已排序，可以采用二分法查询。
如果无排序，只能顺序查询，那就要看记录本身的概率分布，否则不可能实现。毕竟一个机器2个CPU未必能起到作用，要看这两个CPU能否并行存取内存，取决于系统架构。

?

9.搜索关键词智能提示
搜索框中，输入“北京”，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词，
请问，如何设计此系统，使得空间和时间复杂度尽量低。
解决方案：简单直接的方法是：用trie树存储大量字符串，当前缀固定时，存储相对来说比较热的后缀。
然后用hashmap+堆，统计出如10个近似的热词，也就是说，只存与关键词近似的比如10个热词。

?

10.某服务器流量统计器，每天有1000亿的访问记录数据，包括时间、URL、IP。设计系统实现记录数据的保存、管理、查询。要求能实现以下功能：
计算在某一时间段（精确到分）时间内的，某URL的所有访问量。
计算在某一时间段（精确到分）时间内的，某IP的所有访问量。

?

11.有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。
已有的做法是根据ServerIPIndex[NUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[NUM%n]与ServerIPIndex[NUM%(n-1)]基本上都不一样了，所以大多数用户的请求都会转到其他服务器，这样会发生大量访问错误。
如何改进或者换一种方法，使得：
一台服务器死掉后，不会造成大面积的访问错误，
原有的访问基本还是停留在同一台服务器上；
尽量考虑负载均衡。

12.类似九宫格键盘，上面有1到9个数字，每个数字都代表几个字母（比如1代表abc三个字母，z代表wxyz等等），现在要求设计当输入某几个数字的组合时，查找出通讯录中的人名及电话号码。

?

13.http服务器会在用户访问某一个文件的时候，记录下该文件被访问的日志，管理员都会去统计每天每文件被访问的次数。编程实现遍历整个日志文件，计算出每个文件被访问的访问次数。

?

14.在线推送服务，同时为10万个用户提供服务，对于每个用户服务从10万首歌的曲库中为他们随机选择一首，同一用户不能推送重复的，设计方案，内存尽可能小，写出数据结构与算法。

?

15.请设计一个排队系统，类似的应用场景非常多，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。

?

16.设计一种用户登录验证手段，例如银行登录系统，这个设备显示6位数字，每60秒变一次，再经过服务器认证，通过则允许登录，如何设计和实现。
系统设计思路？服务器端为何能有效认证动态密码的正确性？
如果是千万量级永固，给出系统设计图示或说明，要求子功能模块划分清晰，给出关键的数据结构或数据库表结构。 考虑用户量级的影响和扩展性，用户密码的随机性等，如果设计系统以支持这几个因素：
系统算法升级时，服务器端和设备端可能都要有所修改，如何设计系统，能够使得升级过程（包括可能的设备替换或重设）尽量平滑？

?

cs