最近在看<<Hadoop技术内幕>>里面对shuffle中"奇迹发生的地方"有比较细致的叙述
在这整理一下：
在mapper端业务逻辑走完后，调用MapOutputCollector.collect()输出结果，其中MapOutputCollector这个接口有两个实现类MapOutputBuffer和DirectMapOutputCollector，后者是在没有ReduceTask时调用的直接写入HDFS，而前者就是环形缓冲区所在地。
MapOutputBuffer采用二级索引结构，涉及三个环形内存缓冲区kvoffsets(键值对索引的偏移量)、kvindices(分区信息、键值对索引)、kvbuffer(键值对具体的值)，总大小在配置文件中io.sort.mb属性设置(默认为100mb)。
缓冲区采用典型单生产者消费者模型。MapOutputBuffer的collect方法和MapOutputBuffer.Buffer的write方法作为生产者，spillThread线程是消费者，其间同步是通过可重入互斥锁spillLock和spillLock上的两个条件变量(spillDone和spillReady)实现的。
1、kvoffsets
这部分比较简单，主要由三个变量控制，kvstart、kvend、kvindex。开始时kvstart=kvend，kvindex指向待写入位置，当写入一条数据后，kvindex向后移动一位，当kvoffsets内存使用率超过io.sort.spill.percent(默认80%)后，数据开始溢出到磁盘。
2、kvbuffer
kvbuffer的读写操作由指针bufstart/bufend/bufvoid/bufindex/bufmark控制，其中bufstart/bufend/bufindex含义与kvstart/kvend/kvindex相同，bufvoid指向缓冲区中有效内存结束位置。
写入一个key，bufindex移动到可写内存初始位置
写入一个value，bufmark和bufindex都进行移动，表示已经写入一个完整的kv键值对
不断写入，直到满足溢出条件，kvoffsets或者kvbuffer空间使用率超过io.sort.spill.percent(默认80%)，令bufend=bufindex，将缓冲区[bufstart,bufend)之间的数据写出到磁盘，spill线程以bufstart为读指针，
溢出时，MapTask仍然可向kvbuffer中写入数据。
最终，bufstart到达bufend的位置，至此，等待新的一轮溢写。
在hadoop 0.21版本中，将以上三个区域进行了整合，使得索引与记录共享一个环形缓冲区最大限度的利用io.sort.mb空间，进而减少磁盘溢写次数。其中新增指针equator限定索引与数据的分界。
