布隆过滤器bloomfilter-厦门大学数据库室.ppt

Partition类与布隆过滤器 报告人：蔡珉星 厦大数据库实验室 2014-08-02 遇到的问题 目录 Partitioner类 Semi-Join中的布隆过滤器 Part 1 Partition类 MapReduce中的Partition类： 在Map端输出时，需要对key进行分区，来决定输出数据传输到哪个reducer上进行处理。 在提交MapReduce作业时，可以通过指定Partition类来实现分区。 默认的partitioner是HashPartitioner，通过哈希操作来决定分配到哪个reducer。 Partition类 HashPartitioner：结果返回reducer的编号[0, 1, ... NumreducerTasks-1] Partition类 为何要 key.hashCode() Integer.MAX_VALUE： 若key为Text，其hashCode是通过Horner法则(对多项式求值的高效方法)计算得出的一个int值，若Text太大，则可能int会溢出从而得到一个负值。 所以对hashCode和MAX_VALUE(0111111111111111)与运算，保证其值为正数。 优化重分区算法：注意Map输出的key为组合键 Partition类 优化重分区算法： Partition类 Partition是根据组合键中的Join key来分区的，而默认的hash partition是对整个键进行分区的，所以需要自定义一个Partition类。 二次排序将会用整个组合键来进行排序。组合键包括一个标识源数据集（较大或较小）的整数值，因此可以根据这个整数值来保证较小源数据集的值先于较大源数据的值被reducer接收。 优化重分区算法： Partition类 与Partition相关的还有次排序(上图蓝色圈起来的部分) setOutputKeyComparatorClass是key值的第二次比较，决定key的排序； setOutputValueGroupingComparator是指定group的划分。 PS: 0.20.0版本后API有变动: setSortComparatorClass、setGroupingComparatorClass 一般比较函数的实现： Partition类 一般具体排序算法无需用户实现，用户需实现比较函数来决定数据的大小序关系； 返回1, 0, -1来决定大小序关系； 再如PHP中的usort()用于实现用户的自定义排序函数: usort($data, sortByLen) - 使用函数sortByLen(a, b)来排序，返回1, 0, -1。 Part 2 Semi-Join中的布隆过滤器 背景知识 - 位图算法 问题描述：给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中？ 分析: 如果将数据全部存入内存，再遍历判断，需要大约15G内存才能实现(unsigned int为4字节)。 位图算法： 利用2进制位表示是否存在。0表示不存在，1表示存在。 例如： 有{3,5,7,8,2}，可以利用一个8位的二进制来表示该集合 因此，通过申请40亿位长的空间(不到512M)就可以表示这40亿的整数了。 位图算法的实现： Java、C++有BitSe类型，就可以直接定义一个bit数组来实现。 如果没有Bit类型，可以使用int数组，一个int可以表示32个数，通过位操作来实现。 背景知识 - 位图算法 位图算法更多应用： 给40亿个unsigned int的整数，如何判断这40亿个数中哪些数重复？ 同理，可以申请512M的内存空间，然后读取40亿个整数，并且将相应的bit位置1。如果是第一次读取某个数据，则在将该bit位置1之前，此bit位必定是0；如果是第二次读取该数据，则可根据相应的bit位是否为1判断该数据是否重复。 给40亿个unsigned int的整数排序？ 全部存到内存中可能放不下，可使用外部排序（归并排序）来实现，但实现复杂、效率不高。更有效的方法--位图算法: 用位数组表示所有数据，然后从最高位(或最低位)开始遍历，遇到为1的则输出相应的数据。 位图算法的局限： 节省空间，但只能用于整数型的数据，并且需要知道最大范