最近的MapReduce端的Partition根据map生成的Key来进行哈希,导致哈希出来的Reduce端处理任务数量非常不均匀,有些Reduce端处理的数据量非常小(几分钟就执行完成,而最后的part-结果显示其输出文件为0,没有处理任何任务),而有些Reduce端需要执行大量的任务(大概1个多小时)
根据下面的这篇大牛所写的文章,字符串hash算法也有很多种:
https://www.byvoid.com/en/blog/string-hash-compare
这些算法使用位运算使得每个字符都对最后的结果产生影响,作者对其展开了一系列评测,最终BKDR函数无论是在实际效果还是编码实现中,效果都是非常突出的,因此本重构也采用这种算法。
文中给出这种算法的C语言实现:
// BKDR Hash Function unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); }
下面需要做的就是将其转换为Java实现,Java中使用long类型作为C语言中无符号整数的替代(避免int*计算的溢出),后面强制转换为int,去掉高位,并纠正“+/-”号
public static int bkdrHash(String hashString) { long seed = 131L; long hash = 0L; for (int i = 0; i < hashString.length(); i++) { char element = hashString.charAt(i); hash = hash * seed + element; } int hashInt = (int) hash; return hashInt & 0x7FFFFFFF; }
算法修改完成后,我们需要根据实际的结果来判断是否已经hash均匀。
为了确保实际情况中的数据能够有效地哈希均匀,我们直接修改Reduce端,让其直接在reduce函数中仅将key值输出,并将所有输出合并到一个文件以便进行分析。(未设置OutputFormat,直接输出Key文本作为一行)
collector.collect(new Text(iReportKey.getPartitionKey()), new Text(""))
进行均匀的简单分析程序如下:
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(is)); String line; int totalCount = 0; while ((line = bufferedReader.readLine()) != null) { int index = Util.hashCode(line, numberPartition); result[index]++; totalCount++; } bufferedReader.close(); System.out.println("---------------------"); System.out.println("Total Count: " + totalCount); for (int i = 0; i < numberPartition; i++) { System.out.println( String.format("partition=%s, count=%s, percentage=%s%%", i, result[i], (double) result[i] * 100d / (double) totalCount)); } System.out.println("---------------------");
默认设置10个Reduce,分别对生成的Key文件的结果进行处理:
当Map生成的Key数据总量为4390398:
Total Count: 4390398 partition=0, count=632297, percentage=14.401815051847235% partition=1, count=410196, percentage=9.343025393142034% partition=2, count=406882, percentage=9.267542487036483% partition=3, count=531126, percentage=12.097445379667173% partition=4, count=569099, percentage=12.962355576874808% partition=5, count=324720, percentage=7.396140395472119% partition=6, count=394503, percentage=8.985586272588499% partition=7, count=343889, percentage=7.832752292616751% partition=8, count=384954, percentage=8.76808890674604% partition=9, count=392732, percentage=8.945248244008857%
数据量提高一个等级,当Map生成的Key数据总量为40976446时:
Total Count: 40976446 partition=0, count=4905825, percentage=11.972304772356294% partition=1, count=5172735, percentage=12.623678978894363% partition=2, count=3850931, percentage=9.397913620912853% partition=3, count=3595419, percentage=8.774355394316043% partition=4, count=3432017, percentage=8.375584842082205% partition=5, count=3625976, percentage=8.848927503375965% partition=6, count=3829224, percentage=9.344939285364084% partition=7, count=3844329, percentage=9.381801925916172% partition=8, count=4410943, percentage=10.76458168187646% partition=9, count=4309047, percentage=10.515911994905561%
可以看出数据量比较符合预期,最终的实际Reduce(设置为5)效果也比较好,Reduce的执行时间变得非常均匀了:
但是经过分析后,直接将long值截取一下并不是一个好的方案,有些暴力:
int hashInt = (int) hash;
考虑将算法中的每一步局部变量都设置成int,这样就不会有截取的麻烦,将&操作放到循环内:
public static int bkdrHash(String hashString) { int seed = 131; int hash = 0; for (int i = 0; i < hashString.length(); i++) { char element = hashString.charAt(i); hash = (hash * seed + element) & 0x7FFFFFFF; } return hash; }
但是我们知道,如果int值执行乘法操作时,是有可能溢出的,表现为结果直接返回一个负数。由于我们每次循环都需要*seed,必须保证hash出来的值*seed要小于Integer.MAX_VALUE。
Integer.MAX_VALUE=2147483647 (Integer.MAX_VALUE & 0x1FFFFFFF) * 131=1610612605
1610612605会加一个char值,不可能超出最大值,于是选择0x1FFFFFFF替代0x7FFFFFFF。
于是,我们最终的hash方法更改为下面的版本:
public static int bkdrHash(String hashString) { int seed = 131; int hash = 0; for (int i = 0; i < hashString.length(); i++) { char element = hashString.charAt(i); hash = (hash * seed + element) & 0x1FFFFFFF; } return hash; }
经过hash均匀测试,也同样满足要求。
相关推荐
在C++编程语言中,创建自定义函数来处理字符串是很常见的任务。本例中的目标是编写一个名为`stringLower()`的函数,它接受一个包含大写字母的字符串,并将其所有大写字母转换为小写字母。这个功能在处理用户输入、...
本篇将详细介绍Hive中的一些关键函数,特别是数学函数和字符串函数,这些函数对于数据预处理和分析至关重要。 #### 二、Hive函数分类 Hive中的函数主要可以分为三类: 1. **聚合函数**:用于执行汇总操作,如求和...
MapReduce模型在Hadoop实现中的性能分析及改进优化
可以查看与字符编码相关的类,如`Text`、`Charsets`等,了解Hadoop如何处理字符编码。 解决Hadoop中文乱码问题的关键在于识别和匹配数据的正确编码,并在Hadoop组件和工具中设置相应的编码选项。在实际操作中,可能...
在“Similarity”这个项目中,开发者提供了一套代码示例,演示了如何在Hadoop环境下运用TF-IDF和向量空间模型计算文本相似度。虽然这只是一个简单的示例,但对于理解Hadoop处理大规模文本数据的流程以及相关算法的...
在计算机科学中,字符串比较通常通过逐字符匹配来实现,如简单的“顺序比较”或使用“哈希函数”进行快速预判。然而,当比较的字符串数量巨大时,这些基础方法会变得低效。因此,我们需要更高级的算法和技术来应对大...
在IT领域,尤其是在软件开发和数据处理中,查询文件中的特定字符串是一项常见的任务。这个任务可能涉及到文本编辑、日志分析、代码搜索等场景。在本文中,我们将深入探讨如何在文件中有效地查询特定字符串,以及相关...
Hadoop 中的超长字符串匹配 Hadoop 中的超长字符串匹配。 给定一个没有 '\n' 或任何仅包含 4 个字符的分隔符的超长字符串,包括多个 1 GB 文件中的 a、b、c 和 d。 目标是使用 Hadoop 在多个 1 GB 文件中找到给定...
旧版API中Partitioner的类图如图所示。它继承了JobConfigurable,可通过configure方法初始化。它本身只包含一个待实现的方法getPartition。该方法包含三个参数,均由框架自动传入,前面两个参数是key/value,第三个...
3. **字符串函数**: - Oracle PL-SQL有`SUBSTR`、`INSTR`、`UPPER`、`LOWER`等处理字符串的函数。Hive中对应的函数为`substring`、`indexOf`、`upper`和`lower`。Phoenix的字符串处理函数如`substr`、`instr`、`...
Hadoop2.7.1是Hadoop发展中的一个重要版本,它在前一个版本的基础上进行了一系列的优化和改进,增强了系统的稳定性和性能。这个压缩包文件包含的是Hadoop2.7.1的中文文档,对于学习和理解Hadoop的运作机制、配置以及...
16. 空格字符串函数:space 27 17. 重复字符串函数:repeat 27 18. 首字符ascii函数:ascii 28 19. 左补足函数:lpad 28 20. 右补足函数:rpad 28 21. 分割字符串函数: split 28 22. 集合查找函数: find_in_set 29 ...
8. **编程接口**:对于开发人员,文档会讲解如何编写MapReduce程序,包括Java API的使用以及Hadoop Streaming,允许使用其他语言(如Python或Perl)编写Map和Reduce函数。 9. **性能优化**:文档还会涵盖如何优化...
7. 字符串函数: - length():计算字符串长度。 - reverse():反转字符串。 - concat() 和 concat_ws():连接字符串,后者可以指定分隔符。 - substr() 或 substring():截取字符串。 - upper() 和 lower():将...
本文档将详细介绍Hive中各种常用的函数,包括关系运算、数学运算、逻辑运算、数值计算、日期函数、条件函数、字符串函数以及集合统计函数。 #### 一、关系运算 这些运算符用于进行基本的关系比较。 1. **等值比较...
由于文本中未提供完整的第七部分“字符串函数”和第八部分“集合统计函数”的内容,以上知识点仅包括文档中给出的部分函数。实际Hive函数库更丰富,包含更多细节和用法。在使用Hive进行数据处理时,需要根据具体场景...
08.hive内置函数--时间-日期-字符串--函数.mp4
hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文文档hadoop2.7中文...
在Hadoop生态系统中,Windows平台上的开发和运行通常比Linux环境更为复杂,因为Hadoop主要设计为在Linux上运行。然而,随着Hadoop的普及,开发者们也找到了在Windows上搭建和测试Hadoop环境的方法。标题提到的"hadop...
在文档描述中提到,文档是一本中文手册,内容包括Hadoop的快速入门指南、集群搭建步骤、Hadoop分布式文件系统(HDFS)的架构设计、使用方法、权限管理以及配额管理等。由此,我们可以知道文档内容非常丰富,覆盖了从...