谷歌的海量數(shù)據(jù)排序?qū)嶒?yàn)史

自從相關(guān)工具創(chuàng)建以來(lái)，我們一直通過(guò)對(duì)海量的隨機(jī)數(shù)據(jù)執(zhí)行排序來(lái)測(cè)試MapReduce。這種方式很受歡迎，因?yàn)樯扇我鈹?shù)量的數(shù)據(jù)非常簡(jiǎn)單，想要驗(yàn)證輸出結(jié)果是否正確也很簡(jiǎn)單。

盡管最開(kāi)始的MapReduce論文報(bào)告的是TeraSort的結(jié)果。工程師們將定期對(duì)1TB或10TB數(shù)據(jù)執(zhí)行排序當(dāng)作回歸測(cè)試來(lái)做，因?yàn)闇y(cè)試時(shí)使用的數(shù)據(jù)量越大，那些不顯眼的bug就越容易被發(fā)現(xiàn)。然而，當(dāng)我們進(jìn)一步擴(kuò)大數(shù)據(jù)規(guī)模后，真正的樂(lè)趣才剛開(kāi)始。本文將會(huì)討論幾年前我們所做的一些PB規(guī)模的排序?qū)嶒?yàn)，包括在我們看來(lái)最大的一次MapReduce任務(wù)：對(duì)50PB的數(shù)據(jù)執(zhí)行排序。

如今，GraySort已是海量數(shù)據(jù)排序基準(zhǔn)之選，測(cè)試者必須以最快速度按字典順序?qū)χ辽?00TB的數(shù)據(jù)執(zhí)行排序。網(wǎng)站sortbenchmark.org跟蹤記錄了這項(xiàng)基準(zhǔn)測(cè)試的官方優(yōu)勝者，但谷歌從未參加過(guò)官方競(jìng)賽。

由于實(shí)現(xiàn)Reduce的過(guò)程就是對(duì)鍵值排序，MapReduce剛好適合解決這個(gè)問(wèn)題。通過(guò)合適的(詞典)分片功能，MapReduce就能輸出一系列的文件，其中包含最終排序后的數(shù)據(jù)集。

有時(shí)在數(shù)據(jù)中心有新集群出現(xiàn)時(shí)(一般是為了搜索索引團(tuán)隊(duì)的使用)，我們這些MapReduce團(tuán)隊(duì)的人員就有機(jī)會(huì)歇口氣，在實(shí)際工作量壓過(guò)來(lái)之前休閑幾周。這些時(shí)候，我們才有機(jī)會(huì)試試看：讓集群“超負(fù)荷”、探究硬件的極限、搞掛一些硬盤(pán)、測(cè)試一些非常昂貴的設(shè)備，并學(xué)到很多系統(tǒng)性能相關(guān)的東西，同時(shí)(在非官方的)排序基準(zhǔn)測(cè)試獲得勝利。

圖一：谷歌的Petasort記錄

2007

(1PB，12.13小時(shí)，1.37TB/分鐘，2.9 MB/秒/worker)

我們?cè)?007年首次運(yùn)行Petasort。那時(shí)候，我們主要是開(kāi)心能把這個(gè)測(cè)試完成，盡管對(duì)輸出結(jié)果的正確性還有些疑問(wèn)(由于未作驗(yàn)證而無(wú)法確認(rèn))。當(dāng)時(shí)，若不是我們關(guān)閉了檢查map分片與備份的輸出結(jié)果是否一致的機(jī)制，這項(xiàng)任務(wù)是無(wú)法完成的。我們懷疑，這是用作輸入和輸出結(jié)果存儲(chǔ)的谷歌檔案系統(tǒng)(GFS)所造成的限制。GFS的校驗(yàn)和保護(hù)不足，有時(shí)會(huì)返回?fù)p壞的數(shù)據(jù)。不幸的是，該基準(zhǔn)測(cè)試所使用的文件格式并不包含任何內(nèi)嵌的校驗(yàn)和，無(wú)法讓MapReduce發(fā)送通知(在谷歌，通常使用MapReduce的方式就是使用內(nèi)嵌校驗(yàn)和的文件格式)。

2008

(1PB，6.03小時(shí)，2.76TB/分鐘，11.5 MB/秒/worker)

2008年，我們首次專(zhuān)注于優(yōu)化調(diào)整，花了幾天時(shí)間調(diào)整分片數(shù)量、不同緩沖區(qū)的大小、預(yù)讀/預(yù)寫(xiě)策略、頁(yè)面緩存使用等，并在博客中記錄了結(jié)果。最終，通過(guò)將輸出結(jié)果三路復(fù)制到GFS，我們解決掉了瓶頸，這也成了我們那時(shí)在谷歌的標(biāo)準(zhǔn)用法，少一路都會(huì)有很高的風(fēng)險(xiǎn)損失掉數(shù)據(jù)。

2010

(1PB，2.95小時(shí)，5.65TB/分鐘，11.8 MB/秒/worker)

在這個(gè)測(cè)試中，我們使用了新版本的GraySort基準(zhǔn)，這個(gè)版本使用到了不可壓縮的數(shù)據(jù)。在前幾年中，我們從GFS讀取或者向其寫(xiě)入1PB數(shù)據(jù)時(shí)，實(shí)際shuffle的數(shù)據(jù)量?jī)H有大約300TB左右，因?yàn)槟菚r(shí)所使用的ASCII格式都是壓縮過(guò)的。

在這一年中，谷歌將GFS更新為下一代分布式存儲(chǔ)系統(tǒng)Colossus。之前使用GFS時(shí)所遇到的數(shù)據(jù)損壞問(wèn)題不再出現(xiàn)了，我們還在輸出結(jié)果中使用了RS編碼(Colossus的新功能)，從而將寫(xiě)入的總數(shù)據(jù)量從3PB(三路復(fù)制)減少到大約1.6PB。這時(shí)我們也首次證實(shí)了輸出結(jié)果的正確性。

為了減少離散數(shù)據(jù)的影響，我們運(yùn)用了動(dòng)態(tài)分片技術(shù)(也就是減少子分片)，后來(lái)演變?yōu)榱嗽贒ataflow中使用完全動(dòng)態(tài)分片技術(shù)。

2011

(1PB，0.55小時(shí)，30.3TB/分鐘，63.1 MB/秒/worker)

這一年我們的網(wǎng)絡(luò)速度更快，也開(kāi)始關(guān)注每臺(tái)服務(wù)器的效率，特別是輸入/輸出(I/O)方面的問(wèn)題。我們要確保所有的硬盤(pán)I/O操作都是在2MB大小的塊區(qū)內(nèi)進(jìn)行的，解決有時(shí)會(huì)縮小到64kB塊區(qū)的問(wèn)題。我們使用了固態(tài)硬盤(pán)(SSD)來(lái)記錄部分?jǐn)?shù)據(jù)，這使得Petasort測(cè)試首次在一小時(shí)之內(nèi)完成，準(zhǔn)確來(lái)講是33分鐘，可以參考這里的記錄。最終，在分布式存儲(chǔ)中輸入/輸出以及將中間數(shù)據(jù)保存在硬盤(pán)中以支持容錯(cuò)(由于在實(shí)驗(yàn)中，某些硬盤(pán)甚至整臺(tái)服務(wù)器都會(huì)宕掉，而且這種情況會(huì)頻繁出現(xiàn)，因此容錯(cuò)非常重要)的問(wèn)題上，性能達(dá)到了指定MapReduce架構(gòu)的硬件極限性能的將近兩倍。同時(shí)也獲得了更高的擴(kuò)展：我們?cè)?小時(shí)27分鐘之內(nèi)運(yùn)行了10PB的數(shù)據(jù)(26TB/分鐘)。

2012

(50PB，23小時(shí)，36.2TB/分鐘，50 MB/秒/worker)

在這個(gè)測(cè)試中，我們將注意力轉(zhuǎn)向更大規(guī)模的數(shù)據(jù)排序，通過(guò)調(diào)用我們?cè)诠雀杷芸刂频淖畲笠?guī)模集群，將shuffle的數(shù)據(jù)量提到最大，然后運(yùn)行相應(yīng)的MapReduce任務(wù)。不幸的是，這個(gè)集群的空間不夠讓100PB的數(shù)據(jù)排序，因此我們將要排序的數(shù)據(jù)限制在50PB。這個(gè)測(cè)試僅運(yùn)行了一次，也沒(méi)有做專(zhuān)門(mén)的優(yōu)化調(diào)整，而且設(shè)置還是取自之前做10PB實(shí)驗(yàn)時(shí)所用的那一套，完成時(shí)間為23小時(shí)5分鐘。

注意，這個(gè)排序的規(guī)模是GraySort的500倍，在吞吐量上是2015年GraySort官方優(yōu)勝者的兩倍。

學(xué)到的經(jīng)驗(yàn)

這些實(shí)驗(yàn)讓我們獲益良多：包括在運(yùn)行萬(wàn)臺(tái)規(guī)模的服務(wù)器上執(zhí)行排序時(shí)遇到了什么挑戰(zhàn)，以及如何優(yōu)化調(diào)整以接近硬件性能的速度極限。

盡管這些排序?qū)嶒?yàn)非常有趣，但仍有一些缺點(diǎn)：

1. 真正海量的全局排序輸出是沒(méi)有人需要的，我們還沒(méi)有找到如上所述實(shí)驗(yàn)的任何一個(gè)真實(shí)用例。
2. 這些實(shí)驗(yàn)證實(shí)了系統(tǒng)能夠良好地運(yùn)行，不過(guò)回避了所需努力程度的問(wèn)題。MapReduce需要很多的調(diào)整才能良好運(yùn)行，事實(shí)上，我們發(fā)現(xiàn)在生產(chǎn)中有很多的MapReduce任務(wù)就是由于配置不當(dāng)而導(dǎo)致表現(xiàn)不佳。
3. 近來(lái)，我們已經(jīng)轉(zhuǎn)向?qū)ο到y(tǒng)自身構(gòu)建的注重，讓大多部分不再需要優(yōu)化調(diào)整。例如：Dataflow可以自動(dòng)找出分片的數(shù)量(以及自動(dòng)按需重新分片)，以代替人工摸索著手動(dòng)執(zhí)行這一任務(wù)。不過(guò)這些話(huà)題還有達(dá)成的結(jié)果，我們會(huì)在以后的博客中再來(lái)描述。