几个系统设计问题

Published: 13 Jan 2019 Category: arch

一、DNS服务器实现域名到IP地址的转换

每个域名的平均长度为25个字节(在域名的命名标准中,对于域名长度是有明显限制的。其中,中国国家域名不得超过20个字符,国际通用域名不得超过26个字符),每个IP为4个字节,所以Cache的每个条目需要大概30个字节。

总共50M个条目,所以需要1.5G个字节的空间。可以放置在内存中。(考虑到每秒5000次操作的限制,也只能放在内存中。)

可以考虑的数据结构包括hash_map,字典树,红黑树等等。

我觉得比较好的解决方法是,将每一个URL字符串转化为MD5值,作为key,建立最大或最小堆,这样插入和查找的效率都是O(log(n))。MD5是128bit的大整数也就是16byte,比直接存放URL要节省的多。

具体可应用方法:每秒5000的查询不算高啊,最土的方法使用MySQL+Memcached架构应该都能满足吧?

数据结构建议以域名的md5值为主键来存储,值可以只存储目标IP就行。Memcached用户支撑前端查询,MySQL用户存储数据,还要看总数量会有多大,如果不是特别大,直接使用MyISAM引擎来存储就行,更新插入都非常快,如果超千万,可以使用InnoDB来存储,每次有新数据插入时直接使用replace into table就行,Memcached数据的更新直接使用set。

Memcached随便用得好些,每秒上万次的get是容易达到的,MySQL你别小看,在有的测试里,以主键查询的测试,一台普通的服务器上,MySQL/InnoDB 5.1服务器上获得了750000+QPS的成绩。

总结:关于高并发系统设计。主要有以下几个关键技术点:缓存,索引,数据分片,锁粒度尽可能小。。

二、从海量数据中找数据

假设有三十台服务器,每个上面都存有上百亿条数据(有可能重复),如何找出这三十台机器中,根据某关键字,重复出现次数最多的前100条?要求用Hadoop来做。

方案:针对每一台机器有100亿,类似100万时的处理方法,对数据进行切片,可以都切为100万的记录,对100万、取最前100,不同在于这前100也存入hash,如果key相同则合并value,显然100亿的数据分割完后的处理结果也要再进行类似的处理,hash表不能过长,原理其实也就是map和reduce。然后合并这30台机器的结果。

三、设计一个系统,要求写速度尽可能高,说明设计原理。

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

类似LSM。