设计一个支持海量数据存储和查询的系统

Question

面试官要求我设计一个存储千兆字节数据的系统,系统也必须支持某种查询.

描述:

在IDC中生成大量记录,每个记录由URL,访问URL的IP以及访问发生的时间组成.该记录可能被声明为这样的结构,但我不确定应该选择哪种数据类型来代表它们:

struct Record {
    url;  //char *
    IP;   //int?
    visit_time;   //time_t or simply a number?
}

要求:

设计一个存储1000亿条记录的系统,系统至少要支持2种查询:

首先,给定时间段(t1,t2)和IP,查询该IP在给定时间段内访问了多少URL.

其次,给定一个时间段(t1,t2)和一个url,查询该URL被访问了多少次.

我被绊倒了,这是我的愚蠢解决方案:

分析:

因为每个查询都是在给定的时间段内执行的,所以:

1. 创建一个集合,将所有访问时间放入集合中,并根据从旧到最新的时间值保持集合的顺序.

2. 使用hash(visit_time)作为密钥创建哈希表,该哈希表称为时间哈希表,然后特定桶中的每个节点有2个指针,分别指向另外2个哈希表.

3,另外2哈希表将是一个IP哈希表和URL的哈希表.

ip-hash-table 使用hash(ip)作为密钥,同一ip-hash-table中的所有ips具有相同的访问时间;

url-hash-table 使用hash(url)作为密钥,同一url-hash-table中的所有url具有相同的访问时间.

给出如下图纸:

time_hastbl
  []
  []
  []-->[visit_time_i]-->[visit_time_j]...[visit_time_p]-->NIL
  []                     |          |
  []               ip_hastbl       url_hastbl
                      []               []
                      :                :
                      []               []
                      []               []

所以,在(t1,t2)上进行查询时:

1. 从时间设置中找到最接近的匹配,假设匹配为(t1',t2'),则所有有效访问时间将落入从t1'到t2'开始的集合部分;

2. 对于时间集[t1':t2']中的每个访问时间t,执行hash(t)并找到t的ip_hastbl或url_hastbl,然后计算并记录给定ip或url出现的次数.

问题:

我的解决方案很愚蠢,希望你能再给我一个解决方案.

2.关于如何将大量记录存储在磁盘上,有什么建议吗？我想到了B树,但是如何使用它或者B-tree适用于这个系统？

Answer 1

我相信面试官期待一个基于分布式计算的解决方案,特别是涉及"1000亿条记录"时.由于我对分布式计算的了解有限,我建议你研究一下Distributed Hash Table和map-reduce(用于并行查询处理)