scala - Scala 中的 Spark : How to avoid linear scan for searching a key in each partition?

Question

我有一个名为 A 的巨大键值数据集，以及一组名为 B 的键作为查询。我的任务是针对 B 中的每个键，返回键是否存在于 A 中，如果存在，则返回值。

我先用 HashParitioner(100) 对 A 进行分区。目前我可以使用 A.join(B') 来解决它，其中 B' = B.map(x=>(x,null))。或者我们可以对 B 中的每个键使用 A.lookup()。

但是，问题在于 PairRDD 的连接和查找都是对每个分区的线性扫描。这太慢了。如我所愿，每个分区都可以是一个 Hashmap，这样我们就可以在 O(1) 中找到每个分区中的键。所以理想的策略是当master机器收到一堆key后，master将每个key分配给它对应的partition，然后partition使用它的Hashmap查找key并将结果返回给master机器。

有没有简单的方法可以实现？

一种可能的方式:我在网上搜索时，这里有一个类似的问题

http://mail-archives.us.apache.org/mod_mbox/spark-user/201401.mbox/%3CCAMwrk0kPiHoX6mAiwZTfkGRPxKURHhn9iqvFHfa4aGj3XJUCNg@mail.gmail.com%3E

如前所述，我使用如下代码为每个分区构建了Hashmap

 val hashpair = A.mapPartitions(iterator => {
     val hashmap = new HashMap[Long, Double]
     iterator.foreach { case (key, value)  => hashmap.getOrElseUpdate(key,value) }
     Iterator(hashmap)
 })

现在我得到 100 个 Hashmap(如果我有 100 个分区用于数据 A)。我迷路了。我不知道如何查询，如何使用 hashpair 来搜索 B 中的键，因为 hashpair 不是常规的 RDD。我是否需要实现一个新的 RDD 并为 hashpair 实现 RDD 方法？如果是这样，实现哈希对的连接或查找方法的最简单方法是什么？

谢谢大家。

Answer 1

您可能正在寻找 IndexedRDD: https://github.com/amplab/spark-indexedrdd