Partition类和布隆过滤器.ppt

《Partition类和布隆过滤器.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Partition类与布隆过滤器报告人：蔡珉星厦大数据库实验室2014-08-02遇到的问题目录Partitioner类Semi-Join中的布隆过滤器Part1Partition类MapReduce中的Partition类：在Map端输出时，需要对key进行分区，来决定输出数据传输到哪个reducer上进行处理。在提交MapReduce作业时，可以通过指定Partition类来实现分区。默认的partitioner是HashPartitioner，通过哈希操作来决定分配到哪个reducer。Partition类HashPartitioner：结果返回reducer的编号[0,1,...N

2、umreducerTasks-1]Partition类为何要key.hashCode()&Integer.MAX_VALUE：若key为Text，其hashCode是通过Horner法则(对多项式求值的高效方法)计算得出的一个int值，若Text太大，则可能int会溢出从而得到一个负值。所以对hashCode和MAX_VALUE(0111111111111111)与运算，保证其值为正数。优化重分区算法：注意Map输出的key为组合键Partition类优化重分区算法：Partition类Partition是根据组合键中的Joinkey来分区的，而默认的hashpartition是对整个键进

3、行分区的，所以需要自定义一个Partition类。二次排序将会用整个组合键来进行排序。组合键包括一个标识源数据集（较大或较小）的整数值，因此可以根据这个整数值来保证较小源数据集的值先于较大源数据的值被reducer接收。优化重分区算法：Partition类与Partition相关的还有次排序(上图蓝色圈起来的部分)setOutputKeyComparatorClass是key值的第二次比较，决定key的排序；setOutputValueGroupingComparator是指定group的划分。PS:0.20.0版本后API有变动:setSortComparatorClass、setGro

4、upingComparatorClass一般比较函数的实现：Partition类一般具体排序算法无需用户实现，用户需实现比较函数来决定数据的大小序关系；返回1,0,-1来决定大小序关系；再如PHP中的usort()用于实现用户的自定义排序函数:usort($data,'sortByLen')->使用函数sortByLen(a,b)来排序，返回1,0,-1。Part2Semi-Join中的布隆过滤器背景知识-位图算法问题描述：给40亿个不重复的unsignedint的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中？分析:如果将数据全部存入内存，再遍历判断，需要大约

5、15G内存才能实现(unsignedint为4字节)。位图算法：利用2进制位表示是否存在。0表示不存在，1表示存在。例如：有{3,5,7,8,2}，可以利用一个8位的二进制来表示该集合11010110因此，通过申请40亿位长的空间(不到512M)就可以表示这40亿的整数了。位图算法的实现：Java、C++有BitSe类型，就可以直接定义一个bit数组来实现。如果没有Bit类型，可以使用int数组，一个int可以表示32个数，通过位操作来实现。背景知识-位图算法位图算法更多应用：给40亿个unsignedint的整数，如何判断这40亿个数中哪些数重复？同理，可以申请512M的内存空间，然后读

6、取40亿个整数，并且将相应的bit位置1。如果是第一次读取某个数据，则在将该bit位置1之前，此bit位必定是0；如果是第二次读取该数据，则可根据相应的bit位是否为1判断该数据是否重复。给40亿个unsignedint的整数排序？全部存到内存中可能放不下，可使用外部排序（归并排序）来实现，但实现复杂、效率不高。更有效的方法--位图算法:用位数组表示所有数据，然后从最高位(或最低位)开始遍历，遇到为1的则输出相应的数据。位图算法的局限：节省空间，但只能用于整数型的数据，并且需要知道最大范围。布隆过滤器(BloomFilter)问题描述：1亿个不重复的正整数(大致范围已知)中，是否存在某个数

7、可以使用位图来实现，若是1亿个邮件地址，如何确定某个邮件地址是否在这1亿个地址中？分析:通常情况下是利用Hash表，但Hash表不可避免的会发生碰撞，且Hash表需要较大的存储空间。布隆过滤器：是一种数据结构，由BurtonHowardBloom在1970年提出的，它结合了位图和Hash表两者的优点，位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题，而Hash表却恰巧解决了位图无法解决的问题，