公司做广告业务， 为了对流量切分，提升广告效益，结合自身业务用C++写了一个类决策树模型(决策树变种简化版)，开发完成后该模型在提升广告效果上取得不错成效，但随着feature不断增加, 建树原始记录快速增长，单机内存建树遇到瓶颈，因建树及分枝裁剪都在内存进行，当数据量超过5000W行后出现内存不足，同时建树时间也急剧延长。
     公司本身有hadoop集群， 在仔细分析c++建树代码后发现建树过程可以用MR实现,遂决定写一个分布式建树MR job，这里将分布式建树分析及实现过程记录下，有类似需求的朋友可以参考下， 如果有更好的方式也请分享。

建树原始数据格式:
eg:
feature1 feature2 feature3 feature... featureN PV click action
每一行各feature间都以'\t'分割，
最后三列代表
pv:     浏览量
click:  点击量
action: 转换次数
内存建树过程描述:
一: 建树阶段:
1. 从建树原始文件按行依次读入
2. 每一行按 '\t' 分割符分割
3. feature1作为树的第一层节点，feature2作为树的第二层节点,依次类推
4. 当feature的值相同时将该行的pv, click, action值加到feature的属性值上
4. 叶子节点的属性值会带上每一行的pv, click, action. 非叶子节点的属性值是其子节点属性值之和

二: 分枝裁剪阶段:
      建树完成后就要按设置的预值进行分枝裁剪操作，分枝裁剪按自顶向下方式进行，对每一层的每个节点判断其属性值是否小于设置的预值, 如果小于，者将该节点及其子节点都归并到restNode(用'*'表示)节点,如果大于等于，则不做操作, 依次循环递归, 指导完成整颗树的分支裁剪操作.

示例:
注:
两个示例分支裁剪的PV预值都设置成5000
椭圆表示节点，里面的值标志节点值
长方形表示节点的属性值，即pv

示例一:
输入数据:
f1 f2  pv
1  2  5000
1  3  3000
1  4  2000
这里f1表示feature1, f2表示feature2, 属性值只有一个pv
建树过程 1:

分布式建树(MapReduce)

建树过程 2:

分布式建树(MapReduce)

分支裁剪:
先对第一层feature做分支裁剪
因为第一层feature 1的属性值为10000, 大于预值，不做归并
第二层中的3和4属性值分别是3000和2000, 都小于预值，将这两个节点归并到
restNode(*)节点,restNode节点的属性值即为3,4两个节点的属性值之和(5000)

分布式建树(MapReduce)

 输出结果:
f1  f2   pv
1   2    5000
1   *    5000


示例二:
输入数据
f1 f2 f3 f4 pv
1 2 5 9 3000
1 2 5 2 1000
1 2 6 3 2000
1 3 7 4 4000
1 3 8 5 500
1 4 7 5 1000
1 4 7 6 500

建树过程 1:

分布式建树(MapReduce)

建树过程 2:
 

分布式建树(MapReduce)

第一层分支裁剪:
   因为第一层节点的属性值12000, 大于5000， 不做分支裁剪

第二层分支裁剪:
   第二层中3，4节点属性值分别是4500,1500,需要做归并操作

分布式建树(MapReduce)

第三层分支裁剪:
  第三层的5，6，8节点小于预值， 做归并操作

分布式建树(MapReduce) 

第四层分支裁剪:

分布式建树(MapReduce)

输出结果:
1 2 * * 6000
1 * 7 * 4000
1 * * * 500

   在理解上述内存建树及分支裁剪过程后，下面用MR实现同样的功能。
MapReduce 建树过程描述:

记录eg:
   feature1  feature2  feature3  feature4  feature5  pv     click action
    对feature从左至由依次组合,针对每一次组合都计算key对应的pv,click,action总和,然后对每一层用设置的预值做裁剪

 

   第一趟: key=> feature1
   第二趟: key=> feature1        feature2
   第三趟: key=> feature1        feature2  feature3
   第四趟: key=> feature1        feature2  feature3  feature4
   第五趟: key=> feature1        feature2  feature3  feature4  feature5
   最后一次归并: 将相同的记录归并， 并使用设置的预值判断是否输出本条路径

存在问题:
   计算key对应的pv,click,action总和时如果某个key对应的值很多， 会存在数据倾斜问题

优化方法:
   1. 针对前几层feature组合key较少的情况(key对应的值很多), 第一个MR JOB统 计输出 <key,[pv,click,action]>, 第二个MR JOB在map阶段load <key,   [pv,click,action]> 文件, 对各记录做分枝裁剪, 小于预值的节点设置成 '*',因为在map端就做了分枝裁剪， 碰到数据倾斜的可能性非常小，也因为不涉及到分区分组， 性能也可以接受

   2. 针对后几层feature组合key较多的情况(key对应的值较少), key很多，这map阶段就无法load <key,[pv,click,action]> 文件到内存， 第一种优化方式失效, 但正因为key很多,且比较散,对key分区分组后不容易出现数据倾斜问题, 这些层次的<key,[pv,click,action]>, 统计和分枝裁剪可以在一个MR JOB中就可以实现, 性能也比较可观

   3. 对建树过程进行分析，发现当某一层次的rest node的父节点也为rest node时，可以将后续节点都归并成一条记录输出,做这一归并操作需要在每一层多加一个归并作业, 需要根据数据分布及feature层数择机运行,一般当feature较后几层时,运行该作业可以归并不少数据量

   4. 简单归并,该归并不分析rest node与父节点之间的关系，基于这样一个事实考 虑，当运行到后面几层feature时，前面可能, 有很多结点已经被归并成rest node,这时数据中将所有feature作为key， 发现会存在很多重复，该作业就是将这些重复,记录合并成一条,运行该作业也需要视数据情况而定,不是每一层级都运行该作业就能提高性能

测试结果:

   记录数: 600W
   featrue: 16个
   reduces: 64个
   运行时长: 12分钟

   记录数: 4千万
   featrue: 18个
   reduces: 64个
   运行时长: 27分钟

   记录数: 1.5亿
   featrue: 18个
   reduces: 64个
   运行时长: 48分钟