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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3733 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

P.S. 更倾向于NoSQL的那个方案，但是我没有使用过NoSQL的数据库，不知道MongoDB和Redis选用哪个更合适，望指教。

Redis

NoSQL

filter

18 条回复 • 2015-01-13 00:37:57 +08:00

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 via Android

首先排序，然后看临近数据是否一样，懒人的办法

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 via iPad

hadoop搭起来的话一句hive语句就搞定了，问题是手头没有现成的hadoop集群的话自己就是搭个单机的也费劲，环境不好搭，前置知识太多。折衷的办法就是借助memcache或者redis的map结构写个小程序

em70

2014-10-10 19:43:14 +08:00 via Android

这是搜索引擎的关键技术，好像用矩阵计算的，吴军的《数学之美》有介绍

ryd994

2014-10-10 21:33:31 +08:00 via Android

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 via iPad

数据库带了一堆常用的工具和方法来存储和处理数据，一般最先考虑这个没错

你说的这个排重用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 建立一个任务的分发机制，让一个点去做用户输入的内容分词操作，将数分词向后发，计算用户词组的分词系数，就是比如说：我饿了，是分成 “我、饿了” 还是“我饿、了”这样的系数，然后根据系数向后分发，每个点开始读取你对应分词的内容。然后整理，开始向用户反馈。当然反馈中还有一些机制。你需要去处理。

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