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

[kofj]

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

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

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

[SErHo]

用 Redis 的 Set 啊，最简单的方法，就是内存要足够，一千万条 32 个字符长的 MD5 大约占 1G 多内存。

[aisk]

SQL也不是不能搞啊，Postgres还支持hash索引

[88250]

排序 + 查找

@SErHo 已经估算过内存占用

[lyazure]

为啥会觉得数据库不行呀，千万级的数据很少呀，对大多数关系型数据库来说都完全不是问题
不知道你的实现有什么硬性要求？

[jun4rui]

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

[zwzmzd]

@SErHo 这个方法应该就行了

再底层一点，可以去看看红黑树、平衡二叉树之类的数据结构，这两个都是支持在线插入和删除的

[binux]

哪有那么麻烦，关系型数据库都能搞定
你要用nosql也可以，redis费内存，aof别考虑。要持久话就MongoDB

[sophymax]

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

[em70]

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

[ryd994]

1.既然知道是hash，那就不要比较字符串，种子文件的hash我记得是16进制，转成数字
2.数据库带索引完全可以，带索引的时候是二分搜索，10m也就是15次读而已。

[kofj]

@ryd994 操作的数据量比较大的时候，这样子会很好IO吧？

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

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

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

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

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

@SErHo Thanks,BTW如果单台机器资源不足的情况下，是不是可以通过部署多个Redis服务器来做扩展呐？

[binux]

@kofj 你不会是对 url 做 select 吧，而且 InnoDB 并不适合这样大量查询，MyISAM 更合适。这就是个典型 KV，都是精确命中，谁说关系型数据库不能做KV查询。mysql 亿级别一点问题都没有。

[kofj]

@binux 肯定不是啊，是用where条件select的hash值

[lyazure]

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

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

有索引，查询非常快的。
还可以调节数据库，尽量更多数据缓冲在内存中，读写都会更快
肯定比自己编程山寨个红黑树什么的快速可靠多了
Nosql确实是好东西，但杀鸡不用牛刀

[ryd994]

@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]

楼主分词怎么解决？这个问题我一直想知道，比较好奇，就是比较懒，没怎么看过。。。

[xi_lin]

@harryert 分词的成熟方案很多吧，没必要自己轮？

[ablegao]

不确定你这个千万级是日千万级，还是总量千万级。另外这千万数据是分散存储还是集中存储。
一千万数据不算多， 利用硬盘IO . 直接利用你程序的内存空间过滤就好。 当时我们做广告数据分析， 把一天几千万的日志压缩到文件里面， 直接用php脚本排重，效率很高。

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

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

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

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

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



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