【数据蒋堂】第39期：数据分段讨论

现代计算机一般都有多CPU核，而日益广泛应用的固态硬盘也有较强的并发能力，这些硬件资源都为并行计算提供了有力的保证。不过，要实现并行计算还需要有较好的数据分段技术，也就是能方便地把待计算的数据拆分成若干部分，让每个线程（或进程，这里以多线程为例讨论，多进程情况是类似的）分别处理。

设计数据分段方案时，有这么几个目标：

1. 每段的数据量基本相同

并行任务的最终耗时是以那个最慢的线程为准的，而同一机器中各线程的处理能力基本相当，因此数据分段要能做到尽量平均，使各线程的计算时间基本相同。

2. 分段数可灵活动态指定

在数据准备阶段经常并不清楚实际计算用机器的CPU数，而且即使知道，线程数也不能简单地按机器CPU核数去算，因为硬盘的并发能力常常小于CPU；并且，在有并发计算时，能有多少CPU核用到本计算任务也不能事先预知。实际计算用的线程数最好是根据当时场景动态决定，范围从几个到几十个都有可能，这要求能够按随意的数量将数据分段。

3. 每个分段是连续紧凑存储的

因为硬盘不适合频繁随机访问（即使固态硬盘也不适合频繁小量的随机访问），为了保证遍历性能，我们希望每个线程要处理的数据在硬盘上要尽量连续存储，而不是频繁跳跃。

4. 允许数据追加

数据并不是固定不变的，会随着时间不断增长，我们当然希望每次追加数据时不必重新整理所有数据，只需要把追加的数据补上即可。

使用文本文件存储数据时，可以同时保证这4个目标。只要简单地按总字节数把文件分成多段，每个线程读取其中一段即可。

文本中用回车作为记录（行）的分隔符，文本记录的数据本身中不可能出现回车字符，所以用它用为记录的分隔符不会产生歧义。按文件字节数分段时，分段点可能会落到某一行的中间，这时使用去头补尾的方法进行调整，即就是每个分段从分段点继续读到一个回车符才开始，而越过下一个分段点继续读到一个回车符时才结束，这样就可以保证每个分段都只包含完整的记录（行），这也是HADOOP常用的方法。

但是，文本本身的解析实在太慢了，我们还是要考虑二进制的存储方案。

二进制数据中没有回车这种可用于分隔记录的字符，任何字节数值都可能是数据本身，这时就无法识别出记录何时结束。如果一定要人为制造一个分隔符，那就要足够长才能避免和数据本身重复的可能性，每条记录上都增加这么一段字节，会增加大量无意义的数据量，降低性能。而且，这也只能降低出错率而不能彻底杜绝。

改进的方法是使用区块，把数据存入若干相同大小的区块，分段时以区块为单位，只要总区块数量足够多，每个线程分配到的区块数量也就相对比较平均，也就能满足目标1和目标2了。不过目标3却有些问题，区块大小是存储数据之前就确定的，不大可能正好和记录长度匹配，如果要求每个区块中都存储完整的记录，就可能造成区块中的空间浪费（剩余空间存不下一条完整记录时只能作废）。在区块较小且记录字段较多时这个浪费会很严重，影响目标3希望的紧凑性。如果允许一条记录被拆分到两个区块，那又不能按区块为单位来分段了，否则可能造成某个分段将只处理半条记录的情况。

这时候可以借鉴文本的去头补尾方案，允许同一记录拆分到两个区块，在读取分段的第一个区块时跳过第一条（可能是半条）记录，而读取最后一个区块时再继续读下一个区块把当前区块中最后的记录读完整，这样可以保证数据的紧凑性了。这种方法要求在区块中有个标记表明本区块中第一条记录是否是上一区块记录的延续以及最后一条记录是否完整，空间成本不算高，但在遍历数据时总要被这些标记打断，处理起来麻烦不少，会影响性能。

数据库一般也使用区块方案，但由于数据库将所有表的数据存储在一起，它的区块分配算法不会去保证同表数据所占用的区块之间的连续性。而为提高数据的连续性，就要让区块更大，这和区块多又有点矛盾。如果再考虑到数据的可追加性，则还需要一个不断变大的索引表来管理这些区块，在区块数量很多时，这个索引表本身的连续性也不容易得到保证（它的长度事先不知道，在数据追加过程中动态增长）。