相关疑难解决方法(0)

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

描述:

在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适用于这个系统？

我试图理解PyTables如何管理大小大于内存大小的数据.这是PyTables代码中的注释(链接到GitHub):

# Nodes referenced by a variable are kept in `_aliveNodes`.
# When they are no longer referenced, they move themselves
# to `_deadNodes`, where they are kept until they are referenced again
# or they are preempted from it by other unreferenced nodes.

在_getNode方法中也可以找到有用的注释.
似乎PyTables有非常智能的IO缓冲系统,据我所知,它将用户在快速RAM中引用的数据存储为"aliveNodes",在之前保持引用,当前未引用的数据为"deadNodes",以便在需要时快速"恢复"它,以及如果请求的密钥在死或活类别中都不存在,则从磁盘读取数据.

我需要一些关于PyTables在处理大于可用内存的数据时如何处理情况的专业知识.我的具体问题:

1. deadNode/aliveNode系统如何工作(常见图片)？
2. 如果我正确的话,aliveNodes/deadNodes之间的关键区别是什么,而它们都代表存储在RAM中的数据？
3. 可以手动调整缓冲RAM的限制吗？在评论下方,有代码从中读取值 params['NODE_CACHE_SLOTS'].它可以以某种方式由用户指定吗？例如,如果我想为其他需要内存的应用程序留下一些RAM？
4. 在处理大量数据时,PyTables在什么情况下会崩溃或显着减速？在我的情况下可以超过内存100倍,在这种情况下常见的陷阱是什么？
5. PyTables在大小意义,数据结构以及数据操作方面的用途,被认为是"正确"的数据以实现最佳性能？
6. Docs建议.flush()在每个基本.append()周期后使用.这个周期实际上可以有多长？我正在执行一些基准测试,比较SQLite和PyTables如何处理从大型CSV文件创建一个包含键值对的巨大表格.当我使用时.flush(),主循环中的频率较低,PyTables获得了巨大的加速.那么 - 对于.append()相对较大的数据块是否正确,然后使用.flush()？