6.5　CountOnce

假设HDFS只存储一个标号为ID的Block，每份数据保存2个备份，这样就有2个机器存储了相同的数据。其中ID是小于10亿的整数。若有一个数据块丢失，则需要找到哪个是丢失的数据块。

在某个时间，如果得到一个数据块ID的列表，能否快速地找到这个表中仅出现一次的ID？即快速找出出现故障的数据块的ID。

问题阐述：已知一个数组，数组中只有一个数据是出现一遍的，其他数据都是出现两遍，将出现一次的数据找出。

1.实例描述

输入为Block ID。

  1. 1、2、2、3、3、1、5、7、11……

输出为：

  1. 100

2.设计思路

利用异或运算将列表中的所有ID异或，之后得到的值即为所求ID。先将每个分区的数据异或，然后将结果进行异或运算。

3.代码示例

CountOnce的代码示例如下：

  1. import org.apache.spark.SparkContext
  2. import org.apache.spark.SparkContext._
  3.  */
  4. object NumOnce {
  5.   def computeOneNum（args： Array[String]） {
  6.     val spark = new SparkContext（"local[1]"， "NumOnce"，
  7.       System.getenv（"SPARK_HOME"）， SparkContext.jarOfClass（this.getClass））
  8.     val data = spark.textFile（"data"）
  9.    /*每个分区分别对数据进行异或运算，最后在reduceByKey阶段，将各分区异或运算的结果再做异或运算合并。偶数次出现的数字，异或运算之后为0，奇数次出现的数字，异或后为数字本身*/
  10.     val result = data.mapPartitions（iter => {
  11.         var temp = iter.next（）
  12.         while（iter.hasNext） {
  13.           temp = temp^iter.next（）
  14.         }
  15.         Seq（（1， temp））.iterator
  16.       }）.reduceByKey（_^_）.collect（）
  17.     println（"num appear once is ："+result（0））
  18.   }
  19. }

4.应用场景

数据块损坏检索。例如，每个数据块有两个副本，有一个数据块损坏，需要找到那个数据块。