Java:优化的大规模值(value)存储替代方案

Question

我正在开发网络爬虫/蜘蛛，我需要某种方法来有效地大量存储字符串，作为(1)已存储的站点和(2)爬虫队列的引用。这些存储数据结构必须能够容纳超过数百万个字符串值。我将分别从我研究过的研究和所做的事情开始。

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

Java: optimize hashset for large-scale duplicate detection

在这个帖子中，OP 讨论了优化 HashSet，并得到了很多好的反馈和警告。 HashSet 使用起来非常昂贵，并且导致我的程序很快崩溃。在回复中，建议了像 Trove 这样的替代方案，但该项目已停止，我相信还有更好的替代方案。

我尝试的第二种方法是使用 MongoDB 创建队列。我显式地为​​队列创建了一个集合，其中遵循 FIFO，因为 Mongo 使用锁，因此它应该是线程安全的。据我所知，它的效果非常好。我的爬虫运行得很好，平均使用很少的内存(12~42MB)。然而，这种方法很快被证明非常糟糕，因为 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 
        }
    }

}

检查“网站集合中不存在下一个并且下一个尚未在队列中”，我必须创建一个迭代器或使用 mongo.collection.find().limit(1) (这也是一个迭代器，就在幕后)检查下一个元素是否存在于当前存储的网站或队列中。正如您所看到的，随着这两个集合的增长(目前两个集合都超过 100,000 个条目)，处理器不断检查这两个集合可能会非常昂贵且缓慢。

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

Answer 1

holding potentially up to billions URLs in memory

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

I have to create an iterator

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

<小时/>

next doesn't exist in website collection and next isn't already in queue

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

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

通过将每个新元素放入队列和集合中，可以轻松消除此问题，因此您只需检查集合中是否有重复项(IIUYC 可以你做得很快)。显然，您需要一个标记来区分尚未获取的元素。

<小时/>

下一个优化将在内存中保留一些最近访问的元素的缓存，以便消除一些重复的数据库查询。我敢打赌，布隆过滤器也能有所帮助。

<小时/>

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