現(xiàn)代計(jì)算機(jī)一般都有多CPU核，而日益廣泛應(yīng)用的固態(tài)硬盤也有較強(qiáng)的并發(fā)能力，這些硬件資源都為并行計(jì)算提供了有力的保證。不過，要實(shí)現(xiàn)并行計(jì)算還需要有較好的數(shù)據(jù)分段技術(shù)，也就是能方便地把待計(jì)算的數(shù)據(jù)拆分成若干部分，讓每個線程(或進(jìn)程，這里以多線程為例討論，多進(jìn)程情況是類似的)分別處理。

一

設(shè)計(jì)數(shù)據(jù)分段方案時(shí)，有這么幾個目標(biāo)：

1. 每段的數(shù)據(jù)量基本相同

并行任務(wù)的最終耗時(shí)是以那個最慢的線程為準(zhǔn)的，而同一機(jī)器中各線程的處理能力基本相當(dāng)，因此數(shù)據(jù)分段要能做到盡量平均，使各線程的計(jì)算時(shí)間基本相同。

2. 分段數(shù)可靈活動態(tài)指定

在數(shù)據(jù)準(zhǔn)備階段經(jīng)常并不清楚實(shí)際計(jì)算用機(jī)器的CPU數(shù)，而且即使知道，線程數(shù)也不能簡單地按機(jī)器CPU核數(shù)去算，因?yàn)橛脖P的并發(fā)能力常常小于CPU;并且，在有并發(fā)計(jì)算時(shí)，能有多少CPU核用到本計(jì)算任務(wù)也不能事先預(yù)知。實(shí)際計(jì)算用的線程數(shù)***是根據(jù)當(dāng)時(shí)場景動態(tài)決定，范圍從幾個到幾十個都有可能，這要求能夠按隨意的數(shù)量將數(shù)據(jù)分段。

3. 每個分段是連續(xù)緊湊存儲的

因?yàn)橛脖P不適合頻繁隨機(jī)訪問(即使固態(tài)硬盤也不適合頻繁小量的隨機(jī)訪問)，為了保證遍歷性能，我們希望每個線程要處理的數(shù)據(jù)在硬盤上要盡量連續(xù)存儲，而不是頻繁跳躍。

4. 允許數(shù)據(jù)追加

數(shù)據(jù)并不是固定不變的，會隨著時(shí)間不斷增長，我們當(dāng)然希望每次追加數(shù)據(jù)時(shí)不必重新整理所有數(shù)據(jù)，只需要把追加的數(shù)據(jù)補(bǔ)上即可。

二

使用文本文件存儲數(shù)據(jù)時(shí)，可以同時(shí)保證這4個目標(biāo)。只要簡單地按總字節(jié)數(shù)把文件分成多段，每個線程讀取其中一段即可。

文本中用回車作為記錄(行)的分隔符，文本記錄的數(shù)據(jù)本身中不可能出現(xiàn)回車字符，所以用它用為記錄的分隔符不會產(chǎn)生歧義。按文件字節(jié)數(shù)分段時(shí)，分段點(diǎn)可能會落到某一行的中間，這時(shí)使用去頭補(bǔ)尾的方法進(jìn)行調(diào)整，即就是每個分段從分段點(diǎn)繼續(xù)讀到一個回車符才開始，而越過下一個分段點(diǎn)繼續(xù)讀到一個回車符時(shí)才結(jié)束，這樣就可以保證每個分段都只包含完整的記錄(行)，這也是HADOOP常用的方法。

但是，文本本身的解析實(shí)在太慢了，我們還是要考慮二進(jìn)制的存儲方案。

三

二進(jìn)制數(shù)據(jù)中沒有回車這種可用于分隔記錄的字符，任何字節(jié)數(shù)值都可能是數(shù)據(jù)本身，這時(shí)就無法識別出記錄何時(shí)結(jié)束。如果一定要人為制造一個分隔符，那就要足夠長才能避免和數(shù)據(jù)本身重復(fù)的可能性，每條記錄上都增加這么一段字節(jié)，會增加大量無意義的數(shù)據(jù)量，降低性能。而且，這也只能降低出錯率而不能徹底杜絕。

改進(jìn)的方法是使用區(qū)塊，把數(shù)據(jù)存入若干相同大小的區(qū)塊，分段時(shí)以區(qū)塊為單位，只要總區(qū)塊數(shù)量足夠多，每個線程分配到的區(qū)塊數(shù)量也就相對比較平均，也就能滿足目標(biāo)1和目標(biāo)2了。不過目標(biāo)3卻有些問題，區(qū)塊大小是存儲數(shù)據(jù)之前就確定的，不大可能正好和記錄長度匹配，如果要求每個區(qū)塊中都存儲完整的記錄，就可能造成區(qū)塊中的空間浪費(fèi)(剩余空間存不下一條完整記錄時(shí)只能作廢)。在區(qū)塊較小且記錄字段較多時(shí)這個浪費(fèi)會很嚴(yán)重，影響目標(biāo)3希望的緊湊性。如果允許一條記錄被拆分到兩個區(qū)塊，那又不能按區(qū)塊為單位來分段了，否則可能造成某個分段將只處理半條記錄的情況。

這時(shí)候可以借鑒文本的去頭補(bǔ)尾方案，允許同一記錄拆分到兩個區(qū)塊，在讀取分段的***個區(qū)塊時(shí)跳過***條(可能是半條)記錄，而讀取***一個區(qū)塊時(shí)再繼續(xù)讀下一個區(qū)塊把當(dāng)前區(qū)塊中***的記錄讀完整，這樣可以保證數(shù)據(jù)的緊湊性了。這種方法要求在區(qū)塊中有個標(biāo)記表明本區(qū)塊中***條記錄是否是上一區(qū)塊記錄的延續(xù)以及***一條記錄是否完整，空間成本不算高，但在遍歷數(shù)據(jù)時(shí)總要被這些標(biāo)記打斷，處理起來麻煩不少，會影響性能。

四

數(shù)據(jù)庫一般也使用區(qū)塊方案，但由于數(shù)據(jù)庫將所有表的數(shù)據(jù)存儲在一起，它的區(qū)塊分配算法不會去保證同表數(shù)據(jù)所占用的區(qū)塊之間的連續(xù)性。而為提高數(shù)據(jù)的連續(xù)性，就要讓區(qū)塊更大，這和區(qū)塊多又有點(diǎn)矛盾。如果再考慮到數(shù)據(jù)的可追加性，則還需要一個不斷變大的索引表來管理這些區(qū)塊，在區(qū)塊數(shù)量很多時(shí)，這個索引表本身的連續(xù)性也不容易得到保證(它的長度事先不知道，在數(shù)據(jù)追加過程中動態(tài)增長)。