遇到千万级数据排重问题,欢迎童鞋们来讨论,指教。

2014-10-10 16:48:23 +08:00
 kofj
近期在尝试写搜索引擎,全文检索,分词,数据缓存问题一个接一个。现在遇到了一个非常“简单”的问题,就是对千万级的数据进行排重检查(查看一条URL或者hash值是否已经在需要处理的队列当中)。昨天通宵查了一夜的资料,网上资料主要提供了几种排重方案:
1.关系型数据库排重(千万级数据这就是作死的节奏啊,肯定排除);
2.Bloom filter快速排重算法
3.NoSQL(使用Redis的set进行排重)

我需要排重的其实就是一串种子文件的HASH值,据说Bloom filter有误差,Redis没有使用过。具体选用哪种进行排重已经头晕了,同学们有什么建议?

P.S. 更倾向于NoSQL的那个方案,但是我没有使用过NoSQL的数据库,不知道MongoDB和Redis选用哪个更合适,望指教。
7821 次点击
所在节点    编程
18 条回复
SErHo
2014-10-10 17:29:21 +08:00
用 Redis 的 Set 啊,最简单的方法,就是内存要足够,一千万条 32 个字符长的 MD5 大约占 1G 多内存。
aisk
2014-10-10 17:33:53 +08:00
SQL也不是不能搞啊,Postgres还支持hash索引
88250
2014-10-10 17:40:06 +08:00
排序 + 查找

@SErHo 已经估算过内存占用
lyazure
2014-10-10 17:59:00 +08:00
为啥会觉得数据库不行呀,千万级的数据很少呀,对大多数关系型数据库来说都完全不是问题
不知道你的实现有什么硬性要求?
jun4rui
2014-10-10 18:32:00 +08:00
首先排序,然后看临近数据是否一样,懒人的办法
zwzmzd
2014-10-10 19:10:34 +08:00
@SErHo 这个方法应该就行了

再底层一点,可以去看看红黑树、平衡二叉树之类的数据结构,这两个都是支持在线插入和删除的
binux
2014-10-10 19:34:09 +08:00
哪有那么麻烦,关系型数据库都能搞定
你要用nosql也可以,redis费内存,aof别考虑。要持久话就MongoDB
sophymax
2014-10-10 19:41:44 +08:00
hadoop搭起来的话一句hive语句就搞定了,问题是手头没有现成的hadoop集群的话自己就是搭个单机的也费劲,环境不好搭,前置知识太多。折衷的办法就是借助memcache或者redis的map结构写个小程序
em70
2014-10-10 19:43:14 +08:00
这是搜索引擎的关键技术,好像用矩阵计算的,吴军的《数学之美》有介绍
ryd994
2014-10-10 21:33:31 +08:00
1.既然知道是hash,那就不要比较字符串,种子文件的hash我记得是16进制,转成数字
2.数据库带索引完全可以,带索引的时候是二分搜索,10m也就是15次读而已。
kofj
2014-10-10 23:47:12 +08:00
@ryd994 操作的数据量比较大的时候,这样子会很好IO吧?

@sophymax 集群就算了,个人没条件玩儿

@binux 我试过MySQL(InnoDB),通过select查询,效果非常不理想

@zwzmzd 太底层的暂时没有考虑过,一个完整的引擎要做的太多,目前考虑尽快低成本的实现并应用到业务当中去

@lyazure 重点在排重,千万级的数据量确实不算多,但是排重在搜索引擎和大数据处理中是个不简单的问题

@aisk 这个不熟~还真不知道

@SErHo Thanks,BTW如果单台机器资源不足的情况下,是不是可以通过部署多个Redis服务器来做扩展呐?
binux
2014-10-11 00:10:47 +08:00
@kofj 你不会是对 url 做 select 吧,而且 InnoDB 并不适合这样大量查询,MyISAM 更合适。这就是个典型 KV,都是精确命中,谁说关系型数据库不能做KV查询。mysql 亿级别一点问题都没有。
kofj
2014-10-11 00:14:27 +08:00
@binux 肯定不是啊,是用where条件select的hash值
lyazure
2014-10-11 00:48:15 +08:00
数据库带了一堆常用的工具和方法来存储和处理数据,一般最先考虑这个没错

你说的这个排重用mysql非常简单,建表,建唯一索引,利用索引就可以了
如果千万条数据是现成的存在文件里, load data infile... ignore into ... 命令加载进去就自动去重了
如果是动态生成的用insert ignore into... 就可以了

有索引,查询非常快的。
还可以调节数据库,尽量更多数据缓冲在内存中,读写都会更快
肯定比自己编程山寨个红黑树什么的快速可靠多了
Nosql确实是好东西,但杀鸡不用牛刀
ryd994
2014-10-11 02:08:42 +08:00
@kofj MySQL用unique索引

@binux 最近MySQL的测试不是说inno无论读写都优于MyISAM么 http://www.lemug.fr/wp-content/uploads/2011/01/Wp_MySQL-5.5_InnoDB-MyISAM.en_.pdf
harryert
2014-10-11 08:39:16 +08:00
楼主分词怎么解决?这个问题我一直想知道,比较好奇,就是比较懒,没怎么看过。。。
xi_lin
2014-10-11 10:19:32 +08:00
@harryert 分词的成熟方案很多吧,没必要自己轮?
ablegao
2015-01-13 00:37:57 +08:00
不确定你这个千万级是日千万级,还是总量千万级。另外这千万数据是分散存储还是集中存储。
一千万数据不算多, 利用硬盘IO . 直接利用你程序的内存空间过滤就好。 当时我们做广告数据分析, 把一天几千万的日志压缩到文件里面, 直接用php脚本排重,效率很高。

搜索引擎笼统说几个功能:
1.爬虫。
2.分词相关操作
3.用户搜索任务触发

方向上的建议:
1.你的架构不能主要依赖数据库和什么nosql , 这个在千万级的数据处理中, 网络io消耗不起。太慢。所以本地硬盘的文件读取, 直接在内存中做数据处理。你可以把这个些数据分包处理,多用几个脚本来跑。 很快可以搞定。

2. 建立一个预处理任务链。 这个任务链的意思, 就是将数据有先有后的分开, 然后根据需要分成多步, 一步步向后传递, 来提高数据的处理速度。
比如说爬虫1, 爬虫2, 爬虫3 。 每个都爬数据, 爬到后粗略计算有效性然后向自己的后面仍。 在一个你认为合适的时机,将数据整合到一起。然后可以根据不同的分词再向后仍给多哥服务,比如这个脚本只处理A-C的数据, 另外一个脚本只处理1~9的数据。不过衡量你脚本的拆分细节标准,一个时时间消耗, 还有一个是CPU利用。 要把一个内核跑到100%情况下程序都能有效快速执行, 速度上不来不行,CPU不满不行。 这个你得自己衡量。

通过上面的步骤,你就会有一堆已经分门别类的基础数据。 这些数据你可以随便灌入到一个数据库中,根据新旧程度建立索引。

3. 用户的搜索操作是另外一个分词的时候。 这时候你需要一个快速响应的服务。利用MQ 建立一个任务的分发机制, 让一个点去做用户输入的内容分词操作, 将数分词向后发, 计算用户词组的分词系数, 就是 比如说:我饿了,是分成 “我、饿了” 还是“我饿、了”这样的系数, 然后根据系数向后分发,每个点开始读取你对应分词的内容。 然后整理,开始向用户反馈。当然反馈中还有一些机制。你需要去处理。



东西太多。。。 我就不废脑细胞了。 适不适用的,随便看看吧。欢迎指正。 如果错字, 算你倒霉。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/138071

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX