Xavier
(Xavier)
30 December 2018 23:15
1
Given large set of files, design a system to efficiently handle a query like:
Find all files that have these words and doesn’t have these words.
Followup optimization question:
Can you make it efficient for queries that involve words which are common across most files (not all) and not frequently queried.
7ToSmoke
(7ToSmoke)
6 January 2019 19:25
2
先clarify一下题意并加上自己的一些假设:1. 文件都是是按数字编号的,内容完全由英文单词构成 2. 一个query包含一个或多个单词,并以AND逻辑连接 3. 符合query的结果按文件编号全部返回(剩下的就是不包含这些word的)
单机版:
存放查询所需的数据结构:用类似HashMap的结构,key是单词字符串,value是存放文件编号的list,对每个文件,用HashSet存放出现过的单词,再遍历hashset中元素来update HashMap中的value。 假设N为文件数量,M为平均一个文件包含的单词,再假设单词数为W ,则总共需要的空间最多为O(W * N) , 建HashMap的时间复杂度为: 遍历文件的时间 + 遍历HashSet 并update HashMap value的时间O(N * M)
查询算法: 对query中包含的每个单词(假设query中有Q个单词),在hashmap中查询其对应的value分别得到一个list,假设平均长度为L,对这些list求公共的intersection 得到最后的文件编号的list (可以两两一求)需要的时间为O(Q * L), 每次求intersection需要的额外空间之和是O(Q * L)
需求变化:1. 如果query中出现的单词,只要包含一个或以上就返回,则把intersection那一步改成求并集,空间时间复杂度不变。 2. 如果要求返回排名前K(比如前100)条结果,则不仅需要每个单词出现的文件编号还需要出现频率,可以直接去掉上面建HashMap过程中用HashSet存放出现过的单词这一步,每出现一次就记录一次文件编号。(如果一个单词出现频率很高,这样的存储过于低效,可以考虑类似string compression的方法对value list重新编码。)
分布式方案:文件数量很多时,采用map-reduce的方法,在map阶段切分文件集,如果按照固定长度切割,切割点有可能落在某个文件中间,导致文件中不同单词出现在不同的chunk里,reduce结果的时候需要先按单词汇总,再对各个单词的list做并集或者交集
follow up:对于大多数文件中都出现但又不是经常被搜索到的单词(e.g. “the”, “and”, etc),可以改为存不包含该词的文件编号
Xavier
(Xavier)
6 January 2019 19:34
3
你的答案比较可惜的是我没看到 bloom filter 的提出,这个我们在第一课讲了,可以去看下
Xavier
(Xavier)
6 January 2019 19:36
4
7ToSmoke:
文件都是是按数字编号的
可以认为文件有ID的,如果这是你的意思。 ID 也可以是 String,即 UUID,不一定是数字。
我们第一课说到了checksum或digest的概念,D老师也重复提了。这个点也很重要。
1 Like
Xavier
(Xavier)
6 January 2019 19:38
6
感觉答偏了,你说的是文件系统的存储,但这里重点是查询
Xavier
(Xavier)
6 January 2019 19:39
7
可以增加缓存,存的其实是不出现这些单词的文件,即补集。因为不太会变,这个存储是static的。
Xu_Sun
(Edward Sun)
9 January 2019 06:30
8
把文件存储在一个分布式文件系统里面。然后在一个host或者数据库上build一个索引来存储word->FileUUID的Mapping,这个mapping是map所有的file和word的
查询的时候先通过找到这几个需要存在的word对应的文件,在这些文件里面再用bloomfilter筛掉存在那些不应该存在的words