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

Question

面试官要求我设计一个系统来存储千兆字节的数据，并且该系统还必须支持某种查询。

描述:

IDC中会产生海量的记录，每条记录由一个url、访问该url的IP、访问时间组成。记录可能可以像这样表示为结构，但我不确定应该选择哪种数据类型来表示它们:

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

要求:

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

First, given a time period (t1, t2) and a IP, query how many urls this IP has visited in the given period.

Second, given a time period (t1, t2) and a url, query how many times this url has been visited.

我被迷住了，这是我愚蠢的解决方案:

分析:

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

1.创建一个集合，将所有的访问时间放入集合中，集合按照时间值从早到晚的顺序排列。

2.使用hash(visit_time)作为key创建一个哈希表，这个哈希表叫做time-hash-table，然后每个节点在一个特定的bucket中有2个指针分别指向另外2个哈希表。

3.另外 2 个哈希表 是一个ip-hash-table 和一个url-hash-table。

ip-hash-table uses hash(ip) as the key and all the ips in the same ip-hash-table have the same visit-time;

url-hash-table uses hash(url) as the key and all the urls in the same url-hash-table have the same visit-time.

给个图如下:

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 出现的次数。

问题:

1.我的解决方案很笨，希望你能给我另一个解决方案。

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

Answer 1

我相信面试官期待的是基于分布式计算的解决方案，尤其是涉及“1000 亿条记录”时。由于我对分布式计算的了解有限，我建议您查看 Distributed Hash Table和 map-reduce (用于并行查询处理)