top100

背景

从100GB大文件中取出前100出现次数的url，内存限制1GB 文件格式：

(url)

方案设计

1、分区后处理（项目实际实现方案）

1. 主要瓶颈在于内存无法支撑100GB数据排序，所以要先将大文件拆散成多个（1000个）小文件，在小文件内部进行局部排序后提取出前100的Url，主要思想是根据hashCode进行分区
2. 子文件内部排序，并从每个子文件中提取出Top100的Url及其出现的次数，维护一个【子文件数 * 100】的对象数组，内部排序实现了两种方案：
   1. 维持单个子文件下的所有对象的对象数组及哈希表，对子文件对象数组按url出现次数排序后取前100位存入全局数组中
   2. 维护一个【100】空间的堆结构数组（小顶堆）及哈希表，局部排序时判断url是否比堆顶元素小，如果是则压入堆中，之后将堆内元素输出到全局对象数组中

【子文件数 * 100】的对象数组内部降序排序，排序后输出前100项即为结果

2、基于1方案且考虑数据倾斜

（1）、在方案1基础上先进行抽样，定义一个边界区分数组存放着分区边界值url（key），如果抽样过程中发现某阶段内url过多，则重新抽样制定区间 （2）、分区之后操作同方案1

测试

测试文件大小：1G+

内存：256M

Top10

运行时内存设置：

结果输出：

耗时：8096ms