Java:优化的大规模值存储方案

Question

我正在研究一个网络爬虫/蜘蛛，我需要一些方法来高效地存储字符串作为(1)已经存储的站点和(2)我的爬虫的队列的参考。这些存储数据结构必须能够保存数百万以上的字符串值。我将从我已经研究过的研究和我所做的工作开始。

我尝试的第一个方法是从这个线程引用的。

Java: optimize hashset for large-scale duplicate detection

在这个线程中，OP讨论了如何优化HashSet，并得到了许多良好的反馈和警告。使用HashSet非常昂贵，并且导致我的程序很快崩溃。在答复中，有人提出了像Trove这样的替代方案，但是该项目已经停止，我相信还有更好的替代方案。

我尝试的第二个方法是使用MongoDB创建队列。我为一个队列显式地创建了一个集合，在那里我遵循FIFO，因为Mongo使用锁，所以它应该是线程安全的。据我所知，效果很好。我的爬虫运行得很好，平均占用的内存很少(12~42 My )。然而，由于MongoDB的搜索速度为o(n)，这种方法很快就被证明是很差的。创建了一个迭代器来检查每个要缓存的网站的两个集合(网站集合和队列集合)，事实证明这是非常有害的。

跟随这条线

Strategies for fast searches of billions of small documents in MongoDB

它确实稍微提高了搜索质量，但这是一个轻微的偏移。下面是我的网页爬虫的一个简单的伪代码。

while(true){
    parse();
}

public void parse(){
    String next = // next url in queue to be parsed
    Document document = // get HTML dom from next url

    // store document inside of site storage (mongo collection)
    // grab links from document

    for( all links found ) {
        if(next doesn't exist in website collection and next isn't already in queue){
            add to queue 
        }
    }

}

检查"next在网站集合中不存在并且next还没有在队列中“，我必须创建一个迭代器或使用mongo.collection.find().limit(1) (它也是一个迭代器，就在幕后)来检查当前存储的网站或队列中是否存在下一个元素。因此，正如您所看到的，随着这两个集合的增长，目前这两个集合中都有超过10万个条目，对于处理器来说，经常检查这两个集合可能非常昂贵，速度也很慢。

这让我回到了我的第一种方法，它可能在内存中保存多达数十亿个URL，以便更快地在两个存储库中搜索副本。我读到的大部分东西都很有用，但已经过时了，我想知道你们认为最好的方法是什么？

Answer 1

可能在内存中保存多达数十亿个URL

这肯定是你不需要也不应该做的事情。

我必须创建一个迭代器

这肯定是您不能做的事情(除非迭代器只运行在数据的一小部分上)。

next在网站集合中不存在，next也没有在队列中

考虑一下数据表示。对于搜索，列表太慢，因此需要索引搜索。类似于HashMap或TreeMap的东西，但在磁盘上。

我对MongoDB几乎一无所知，但每一个值得它命名的数据库都可以做到这一点。我想，它已经适用于您的收藏，只是队列是一个问题。队列更复杂，因为您需要快速搜索和队列性。

通过将每个新元素都放入队列和集合中，可以很小地消除这个问题，因此您只需要检查集合中是否存在重复项( IIUYC可以非常快地完成这一任务)。显然，您需要一个标记来区分尚未获取的元素。

下一个优化是在内存中保存一些最近访问的元素的缓存，这样就可以消除一些重复的DB查询。我敢打赌，布鲁姆过滤器也能帮上忙。

您还可以在磁盘上使用真正的Map：https://github.com/OpenHFT/Chronicle-Map