最近一段时间,在登月项目中接触到一个涉及数据对比的工具,需要对hdfs上的一些原始数据进行按行解析,并重新保存成可被hive识别的数据文件。作为一个复杂度不高的应用MR并行计算框架的工具,设计制作过程还是很顺利的,两三天的功夫编码完成,自测也通过了,然而上线使用后,却发生了一个意想不到的bug,在解决该bug的过程中,我有幸从中获得了一些新的技术启发,也许对大多数技术人员来说只是一个常规到不值一提的小技术点,然而对我却是一个不错的感悟,记录下来以供抛砖引玉。

闲话少说,直切重点。

事情是这样的,用户的需求是希望将某个路径作为参数传递给工具,然后工具可以遍历该目录下的所有子目录和文件,将所有数据文件进行解析转换。对于这样一个需求,最常规的思路是做一个递归函数,遇到文件时处理文件,遇到目录时则进行递归,这样很快就可以把某个路径下的所有子目录和文件都遍历一遍,程序也会显得简洁明了。代码一般如下:

private void recursion (Path path) {

  FileStatus[] children = fs.listStatus (path);

  for(FileStatus child : children){

if(child.isDir()){

  recursion(child.getPath());

}

else{

  …… //执行文件处理代码

}

  }

}

这样一段程序在我个人自测阶段也没有发现什么问题,但是放到云梯上实际使用的时候问题就来了——栈溢出了。工具抛出了StackOverflowError异常。

当用户告知出现这个问题的时候,一刹那间我曾经通读过的DistCP的源码立即在我脑海中闪现了出来,曾经不理解为何要那么写的一段代码,此时此刻我终于恍然大悟。这个问题的根源在于hdfs文件系统的目录层次太深了,因此每一层递归累积起来终于将jvm的栈空间撑爆了。自测阶段之所以没有暴露出问题,完全是因为云梯线上的目录文件树在一个小集群中很难模拟。

解决这个问题是非常简单的,只需要将递归算法替换成迭代算法就可以了。修改后的代码如下:

Stack<FileStatus> pathstack = new Stack<FileStatus>();

for(pathstack.push(fs.getFileStatus(path)); !pathstack.empty();){

  FileStatus cur = pathstack.pop();

  FileStatus[] children = fs.listStatus(cur.getPath());

  for(int i = 0; i < children.length; i++) {

final FileStatus child = children[i];

if (child.isDir()) {

pathstack.push(child);

    }

    else {

      …… //执行文件处理代码

    }

  }

}

问题虽然解决了,但对jvm堆栈方面技术需要重新审视深究,于是我顺便查了些资料学习了一下。众所周知,堆是有序完全二叉树,栈是一种先进后出的线性表,栈的特点是速度快,jvm的压栈和出栈操作都是非常高效的(相对来说,堆的二叉树遍历是要比先进后出线性表要慢的)。

“每一个Java应用都唯一对应一个JVM实例,每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程共享.C/C++不同,Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的,但是这个对象的引用却是在栈中分配,也就是说在建立一个对象时从两个地方都分配内存,在堆中分配的内存实际建立这个对象,而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。”

JVM堆中存的是对象。JVM栈中存的是基本数据类型和JVM堆中对象的引用。一个对象的大小是不可估计的,或者说是可以动态变化的,但是在JVM栈中,一个对象只对应了一个4btye的引用。”

关于这一点,我制作了下面这段程序来进行证实:

public class StackLevel {

    private int level = 1;

    public void stackLevel(){

        level++;

        stackLevel();

    }

    public static void main(String[]args) throws Throwable{

        StackLevel sl = new StackLevel();

        try{

            sl.stackLevel();

        }catch(StackOverflowError e){

            System.out.println(sl.level);

        }

    }

}

这段代码执行下来,可以看到默认情况下递归深度是10827java version "1.6.0_65",系统不同值略有不同)。在stackLevel函数中,增加一个变量(Stringbuf = “”;)之后,再执行一遍,得到的深度为9925。随意的给字符串buf赋值,无论字符串长度是多少,9925这个深度都不会发生变化。而如果再增加一个变量申明,则递归深度又会再次变小。从而证明了栈只存放指针,而堆负责存储这件事情。

对于我们一般的本地化应用来说,遍历目录这样的简单任务,用递归还是最高效的,这不仅是因为算法设计上较为清晰简单,更因为递归利用了栈的高效,程序整体运行速度会比较快。但是对于hdfs这样的文件系统来说,目录的层次深度可能会多达数十甚至数百层,这样一来,使用递归必然会使得函数空间层层堆叠直到导致栈溢出,这也是为什么DistCP中使用了Stack类来规避递归的原因(而我最开始看到这一段的时候只是觉得这样的算法费事不讨巧,完全没有理解其深层次的原因)。此外,对于MR编程框架来说,计算量的增加或者说计算速度的增加到是可以通过增加slot数来进行弥补的,所以,如果真遇到大量需要遍历的应用,合理切分到多个slot中去执行才是提高效率的正道。

有趣的是,不同的语言对递归深度都有不同的解释,我尝试了pythonC这两种语言,python代码如下:

global level

level = 1

def stackLevel():

            global level

            level += 1

            stackLevel()

 

try:

            stackLevel()

except RuntimeError:

            print level

得到的结果是1000,且无论在函数stackLevel中增加多少个变量,其递归深度都始终是1000。对于python来说递归深度是一个可以设置的值,其默认就是1000,可以通过(sys.setrecursionlimit(递归深度值))来进行设置。但是这个设置只不过是起到一个保护的作用,当设置的深度非常大,以至于超过进程内存空间时,python依然会报出“Segmentation fault: 11”(11SIGSEGV信号,无法捕获)。

C里面,递归深度则可以到一个很大的数值,不过最终也会被SIGSEGV信号中断。

           由这个问题再引申一下,我对递归的使用更加感觉需要审慎,尤其类似大数据项目的测试中,每一个递归都应该仔细考量其规模,因为大数据的文件系统往往在深度、广度上都不是普通文件系统可以比拟的,单机上不会出现的问题,到了大数据上都有可能成为问题。再进一步,有了这次的这个经验,更提醒我在将来的coding中,使用递归前也要预估一下可能带来的后果,防止类似的bug重现。