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

闲话少说，直切重点。

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

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

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

“每一个Java应用都唯一对应一个JVM实例，每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程共享.跟C/C++不同，Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的，但是这个对象的引用却是在栈中分配,也就是说在建立一个对象时从两个地方都分配内存，在堆中分配的内存实际建立这个对象，而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。”问题虽然解决了，但对jvm堆栈方面技术需要重新审视深究，于是我顺便查了些资料学习了一下。众所周知，堆是有序完全二叉树，栈是一种先进后出的线性表，栈的特点是速度快，jvm的压栈和出栈操作都是非常高效的（相对来说，堆的二叉树遍历是要比先进后出线性表要慢的）。

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

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

对于我们一般的本地化应用来说，遍历目录这样的简单任务，用递归还是最高效的，这不仅是因为算法设计上较为清晰简单，更因为递归利用了栈的高效，程序整体运行速度会比较快。但是对于hdfs这样的文件系统来说，目录的层次深度可能会多达数十甚至数百层，这样一来，使用递归必然会使得函数空间层层堆叠直到导致栈溢出，这也是为什么DistCP中使用了Stack类来规避递归的原因（而我最开始看到这一段的时候只是觉得这样的算法费事不讨巧，完全没有理解其深层次的原因）。此外，对于MR编程框架来说，计算量的增加或者说计算速度的增加到是可以通过增加slot数来进行弥补的，所以，如果真遇到大量需要遍历的应用，合理切分到多个slot中去执行才是提高效率的正道。这段代码执行下来，可以看到默认情况下递归深度是10827（java version "1.6.0_65"，系统不同值略有不同）。在stackLevel函数中，增加一个变量（Stringbuf = “”;）之后，再执行一遍，得到的深度为9925。随意的给字符串buf赋值，无论字符串长度是多少，9925这个深度都不会发生变化。而如果再增加一个变量申明，则递归深度又会再次变小。从而证明了栈只存放指针，而堆负责存储这件事情。

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

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