首页 > 试题广场 > 有1000亿条记录,每条记录由url,ip,时间组成,设计一
[问答题]
有1000亿条记录,每条记录由url,ip,时间组成,设计一个系统能够快速查询以下内容
1.给定url和时间段(精确到分钟)统计url的访问次数
2.给定ip和时间段(精确到分钟)统计ip的访问次数
推荐
答:首先,1000亿条记录全部放到内存肯定不够,那就是分成小文件了,然后整合;
公共的时间段,因为精确到分钟,我们把这每一分钟建成一个小文件,每个小文件肯定会有许多重复的ip,url;
现在统计每个小的文件中url的访问量和ip的访问次数,方法就是建立索引;
(建立索引的目的是为了减少查询次数,但是随着索引级数增多也会造成花更多的时间在建立索引上);
建立url的索引,假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引,那么来了一条url,先看一级索引是不是匹配,匹配再看二级索引,相同的话就是我们要的url目标;
ip的索引也是一样,ip分成4段建立索引;
所以这里影响效率的就是在索引建立这块,索引建立好那就是查询的事了的,就会变得非常快。
假定给定了某个时间段,找出url的访问量,那么先找到给定的时间段,对应着刚开始分割的小的文件(每一个分钟)中搜索,通过索引找到相同的url之后,开始统计,直到搜索完所有的给定时间段内的所有的小的文件;
求ip的访问次数也是一样,按照给定的时间段,找到对应的小的文件,通过索引找到相同的ip后统计,直到搜索完了给定时间段内的所有的小的文件。
编辑于 2015-02-09 09:50:41 回复(0)
MapReduce思想:
1.按照时间对日志数据进行分区。
2.对url或者ip做hash,然后分桶。
3.merge最终结果。

发表于 2014-12-29 10:40:55 回复(0)
一种方法是用现有的大数据框架如Hadoop的Map/Reduce来处理
一种是将这项数据放在Hbase中,Hbase是一种列式NoSQL数据库,存放时用记录中的时间代替默认的时间戳,正好可以满足需求。这是最好的解决办法。
如果不允许使用分布式计算,那就只能将数据分成小文件计算了,一般单个计算机内存没有这么大。这1000亿条数据的ip和Url肯定有很多重复的,就是去重生成目标文件,然后排好顺序,这样就可以用二分查找快速得到想要的结果了
发表于 2015-01-09 11:11:07 回复(0)
1、将记录按照时间(精确到分钟)写到不同的文件time_record.data

2、使用MapReduce,输入为所有time_record.data文件,输出为time_url_count.data和time_ip_count.data。也就是分别统计每一分钟内的url的次数和ip的次数(每行格式为url count或者ip count);

3、根据时间段[time1,time2]和所要统计的类型(url/ip)确定MapReduce的输入文件##_xx_count.data,对统计结果进行合并。便可以得出[time1,time2]时间段内url或ip的数量;

或者省略2,直接根据时间段[time1,time2]和所要统计的类型(url/ip)确定MapReduce的输入文件time_record.data,匹配每个文件中的url或ip并计数,最后进行合并即可。
编辑于 2015-08-27 11:18:24 回复(0)
答:首先,1000亿条记录全部放到内存肯定不够,那就是分成小文件了,然后整合;
公共的时间段,因为精确到分钟,我们把这每一分钟建成一个小文件,每个小文件肯定会有许多重复的ip,url;
现在统计每个小的文件中url的访问量和ip的访问次数,方法就是建立索引;
(建立索引的目的是为了减少查询次数,但是随着索引级数增多也会造成花更多的时间在建立索引上);
建立url的索引,假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引,那么来了一条url,先看一级索引是不是匹配,匹配再看二级索引,相同的话就是我们要的url目标;
ip的索引也是一样,ip分成4段建立索引;
所以这里影响效率的就是在索引建立这块,索引建立好那就是查询的事了的,就会变得非常快。
假定给定了某个时间段,找出url的访问量,那么先找到给定的时间段,对应着刚开始分割的小的文件(每一个分钟)中搜索,通过索引找到相同的url之后,开始统计,直到搜索完所有的给定时间段内的所有的小的文件;
求ip的访问次数也是一样,按照给定的时间段,找到对应的小的文件,通过索引找到相同的ip后统计,直到搜索完了给定时间段内的所有的小的文件。
发表于 2017-04-03 16:46:54 回复(0)
将访问记录拆分成两个数据表,表1是IP地址、时间段、时间和对应访问url在表2的主键和段内序号,表2是url、时间段、时间和对应IP地址在表1的主键和排序,
将两个数据表存储在NoSQL数据中,将一天分成4个时间段以后,每个IP地址按照访问时间在对应的时间段下增加一条时间记录,给该条记录一个序号。同理,表2
也按照时间段分开存储记录,拆分后,进行水平分表,按照IP地址和时间段拆分表1,按照url和时间段拆分表2。进行检索的时候,首先根据查询时间段和表2中
时间段划分,将一条查询分成一条或多条查询,将跨时间大段的查询转换为每个大时间段里面的查询,根据划分后的查询时间,索引到表2中的数据记录,
在该条记录中统计访问次数,最后进行结果相加。给定IP地址和时间段的查询同理。
表1设计为{"ip_id":"111","IP":"x.x.x.x","time_segment":"20170401-1","recorde":[{"time":"20170401052223","ip_order":1,"url":url_id,"url_order":1}]}
表1设计为{"url_id":"2","url":"qq.com","time_segment":"20170401-1","recorde":[{"time":"20170401052223","url_order":1,"ip":ip_id,"ip_order":1}]}

发表于 2017-04-01 17:16:16 回复(0)
这个题属于哪类知识范畴啊
发表于 2016-09-21 16:49:57 回复(0)


发表于 2016-08-21 17:19:59 回复(0)
1.
//将1000亿条记录分成1000个文件:t1,t2,t3....t1000,每个文件有1亿条记录
//使用多线程技术同时处理1000个文件,构造每个文件所对应的hashtable HT,包含<url,time>
//根据url访问HT,判断时间是否在指定范围内,如果在则将访问次数累加
2.
//将1000亿条记录分成1000个文件:t1,t2,t3....t1000,每个文件有1亿条记录
//使用多线程技术同时处理1000个文件,构造每个文件所对应的hashtable HT,包含<ip,time>
//根据ip访问HT,判断时间是否在指定范围内,如果在则将访问次数累加

发表于 2016-03-25 10:03:30 回复(0)
<div> 1.将URL和ip都创建为数据库的索引; </div> <div> 查询url访问次数,url作为hashMap的key;value中存放访问次数。 </div> <div> 查询ip访问次数,ip作为HashMap的key。 </div>
发表于 2015-08-13 14:53:18 回复(0)

映射Map[url][time],将url进行字符串hash,再进行枚举统计。

这两题如果做成两维映射,内存吃不消,既然两题中的一维是已经指定的,变化的只是时间段,因此可以用一维表示,先预处理,再进行统计。
      用的MapReduce的思想。

按时间分成小文件,各自对url和ip进行hash。
再分级做桶,同时merge各时间区段的hash表。
这样查询就能做到Log级别。

发表于 2015-05-18 23:34:24 回复(0)
    1000亿条记录数据量很大,可以使用hadoop生态圈中的HBase,它是一种nosql的分布式列式数据库,它的特点是支持海量数据在简单查询下的秒级响应。
    如果历史数据是存放在关系型数据库中,可以使用sqoop或者编写mapreduce导入到HBase中;如果数据是日志类文本数据,可以编写mapreduce导入HBase中。
    使用Hbase时,把rowkey设计成url_time以及ip_time,查询时设置scan条件,类似的startRowKey:19216812210_20150511000 endRowKey:19216812210_20150511000,然后使用HBase自带的协处理器来统计次数。

发表于 2015-05-11 11:03:35 回复(0)
没有经验,但大致认为属于map-reduce思路范围。按某种哈希把记录分片到各个机器上,然后map-reduce。
发表于 2015-04-26 18:39:39 回复(0)
ip转换成数字存储,
时间增加索引
发表于 2015-04-16 12:37:24 回复(0)
Template<typename T>
unsigned long Count(Time t_s, Time t_e, T t) {
    index==type(url) ? 0 : 1;
    search_s = Find_s(t_s);
    search_e = Find_e(t_e);
    p = search_s;
    count = 0;
    for(; p<search_e+1); ++p)
        if((*p)[index]==t) {count++;}
    return count;
}

for loop build hash.
    data[2] = {url, ip};
    hash[time] = data;
发表于 2015-04-01 22:36:39 回复(0)
1.使用这样的一个数据结构V: (url, S{time(精确到分钟), count}) 也就是每一个url都有一个列表S,里面按时间排序升序存放着到time时间点总共访问次数,这样某个时段[i,j]的访问次数就可以通过S[j].count - S[i - 1].count来计算出来.
首先把文件进行按url和时间来排序,计算出数据结构V并按照url的顺序序列化到一个结果文件中.
查询的时候首先使用url进行二分查找, 找到这个url的数据结构v之后,在v.S里通过二分查找分别找到时间段I, J的对应项, 并通过上述方法计算出访问次数.
2.做法和1类似,只不过把url改成ip.
编辑于 2015-04-01 17:38:34 回复(0)
使用索引,创建两张索引,一张以url为key,一张以ip为key,使用链式存储,并对个链表进行时间排序,进行时间段选取的时候使用二分查找.将这两张表加载到多台主机的内存中,一台主机进行分段索引,然后请求发送到对应主机进行统计
发表于 2015-03-31 18:06:56 回复(0)