Google的工程師為了方便內(nèi)部人員使用MapReduce，研發(fā)了一種名為Sawzall的DSL，同時Hadoop也推出了類似Sawzall的Pig語言，但在語法上面有一定的區(qū)別。今天就給大家貼一下Sawall的論文，值得注意的是其第一作者是UNIX大師之一（Rob Pike）。原文地址，并在這里謝謝譯者崮山路上走9遍。
概要
超大量的數(shù)據(jù)往往會采用一種平面的正則結(jié)構(gòu)，存放于跨越多個計算機的多個磁盤上。這方面的例子包括了電話通話記錄，網(wǎng)絡(luò)日志，web文檔庫等等。只要這些超大量的數(shù)據(jù)集不能裝在單個關(guān)系數(shù)據(jù)庫里邊的時候，傳統(tǒng)的數(shù)據(jù)庫技術(shù)對于研究這些超大數(shù)據(jù)集來說那就是沒有意義的。此外，對于這些數(shù)據(jù)集的分析可以展示成為應(yīng)用簡單的，便于分布式處理的計算方法：比如過濾，聚合，統(tǒng)計抽取，等等。我們在這里介紹這樣一種這樣的自動化分析系統(tǒng)。在過濾階段，查詢請求通過一種全新的編程語言來快速執(zhí)行，把數(shù)據(jù)處理到聚合階段。無論過濾階段還是聚合階段都是分布在上百臺甚至上千臺計算機上執(zhí)行的。他們的結(jié)果通過比較并且保存到一個文件。這個系統(tǒng)的設(shè)計-包括分成兩階段，以及這種新式的編程語言，聚合器的特性-都是在數(shù)據(jù)和計算分布在很多臺機器上的情況下，內(nèi)嵌使用并行機制的。
1．介紹
有不少數(shù)據(jù)集都是超大的，或者非常動態(tài)，或者就是因為太笨拙了，而不能有效地通過關(guān)系數(shù)據(jù)庫進行管理。典型的場景是一組大量無格式文件-有時候是上petabytes(2的50次方1,125,899,906,842,624)-分布在多個計算機上的多個磁盤上。這些文件都包含了無數(shù)的記錄，這些記錄是通常會通過一個軸來組織，比如通過時間軸或者地理軸進行組織。例如：這堆文件可能包含一個web網(wǎng)頁倉庫，用來構(gòu)造internet搜索引擎的索引系統(tǒng)，或者這堆文件用來記錄上千臺在線服務(wù)器的健康日志，或者用來記錄電話呼叫記錄或者商業(yè)交易日至，網(wǎng)絡(luò)包記錄，web服務(wù)器查詢記錄，或者高級一點的數(shù)據(jù)比如衛(wèi)星圖像等等。但是對這些數(shù)據(jù)的分析經(jīng)?？梢员硎境蔀楹唵蔚牟僮鳎h比普通SQL查詢要簡單得操作來完成。舉一個例子，我們通常會統(tǒng)計滿足某條件的記錄數(shù)，或者抽取這些記錄，或者查詢異常記錄，或者構(gòu)造記錄中某一個域值的頻率柱狀圖。另一方面，查詢也可能會較為復(fù)雜，但是這些查詢依舊可以展示成為通過一系列簡單查詢來完成，這些簡單查詢都可以簡單映射到這些文件的記錄集上。
圖1：5組機架，每組有50-55臺計算機，每臺計算機有4個磁盤。這樣一個架構(gòu)可以有到250TB的待分析數(shù)據(jù)量。我們可以在250臺以上的計算機上分別執(zhí)行過濾來極大的的提高并行度，并且把他們的結(jié)果通過網(wǎng)絡(luò)匯聚到一起（參見弧線）
由于數(shù)據(jù)記錄存放在多臺計算機上，那么用這些計算機本身的能力來進行分析的方法就相當(dāng)有效。特別是，當(dāng)單獨每一個步驟都可以表示成為每次對獨立的記錄進行操作的時候，我們就可以把計算分布到所有這些機器上，這樣就能達到相當(dāng)高的吞吐量。（前邊提及的每個例子都有這樣的特點）。這些簡單操作都要求一個聚合的階段。例如，如果我們統(tǒng)計記錄數(shù)，我們需要把每一個機器統(tǒng)計出來的記錄數(shù)相加，作為最終的輸出結(jié)果。
所以，我們把我們的計算分成兩個階段。第一個階段我們對每一條記錄分別計算，第二個階段我們聚合這些結(jié)果（圖2）。本論文描述的系統(tǒng)更進一步考慮了這個問題。我們用一個全新的編程語言來進行第一個階段的分析，從處理粒度上，它一次處理一條記錄，并且在階段2嚴格限制預(yù)先定義的處理階段1產(chǎn)出物的聚合器處理的集合。通過約束本模式的計算量，我們可以達到非常高的吞吐量。雖然并非所有的計算都能適合這樣的模式，但是僅僅通過不多的代碼就能夠驅(qū)動上千臺機器并行計算還是很劃算的。
RAW DATA
圖2：總體數(shù)據(jù)流圖，過濾，聚合和比較。每一步都比上一步產(chǎn)生更少的數(shù)據(jù)。
當(dāng)然，我們還有很多小問題要解決。計算必須要分解成為小塊并且分布到每一個存儲數(shù)據(jù)的節(jié)點上進行執(zhí)行，盡量讓計算和數(shù)據(jù)在一臺機器上以避免網(wǎng)絡(luò)瓶頸。由于使用的機器越多，那么越有可能有機器會在運算中宕機，所以，必須系統(tǒng)必須要有容錯能力。這些都是困難但是有趣的問題，但是他們都必須能夠在沒有人為干預(yù)的情況下完成。Google有好幾個這樣的基礎(chǔ)架構(gòu)，包括GFS[9]和MapReduce[8]，通過容錯技術(shù)和可靠性設(shè)計來提供了一個非常強大的框架，可以用來實現(xiàn)一個很大的，分布式處理的并行系統(tǒng)。因此我們著重于我們的目標(biāo)：清晰的表達分析處理，并且迅速執(zhí)行分析處理。
2．總覽
簡要而言，我們的系統(tǒng)通過處理用戶提交的用特別設(shè)計的編程語言寫成的查詢，并發(fā)的在分布到大量機器上的記錄集中，進行記錄級別的查詢，并且搜集查詢結(jié)果，通過一組高性能的聚合器進行查詢結(jié)果的匯聚。這兩部發(fā)呢別執(zhí)行，通常分布到不同的計算機集群上。
這樣的處理典型類型是并發(fā)處理分布在成百上千臺計算機上的gigabyte或者數(shù)Tbyte數(shù)據(jù)。一個簡單的分析可能需要花去一個CPU好幾個月的時間，但是通過上千臺計算機的并行處理，只需要幾個小時的時間就能處理完。
有兩個條件決定著系統(tǒng)的設(shè)計。首先，如果查詢操作是對記錄間可交換的，就是說記錄處理的先后順序是不重要的。我們于是可以用任意的順序來處理這個查詢操作。第二，如果聚合操作是可交換的，中間結(jié)果的處理順序是不重要的。此外，如果他們也是可結(jié)合的，中間處理結(jié)果可以被任意分組或者分成不同的步驟進行聚合。舉一個例子，對于統(tǒng)計數(shù)量包括匯總數(shù)量來說，無論中間結(jié)果如何的累加或者分組結(jié)合累加，他們最終的結(jié)果都不會受到影響。這個交換性和結(jié)合性的約束并不算過分苛刻，他們可以提供很廣闊的查尋范圍，包括：統(tǒng)計，篩選，取樣，柱狀圖，尋找常見項目，等等。
雖然聚合器組是有限的，但是對于查詢階段來說，應(yīng)當(dāng)包括更加通用的內(nèi)容，我們介紹一種新的解釋執(zhí)行的程序語言Sawzall[1]（解釋語言的性能已經(jīng)足夠了：因為程序多數(shù)都是比較小的，而且他們需要處理的數(shù)據(jù)往往很大，所以往往是受I/O的限制，這在性能的章節(jié)有所討論）
一個分析操作如下：首先輸入被分解成為要被處理的數(shù)據(jù)小塊，也許是一組獨立的文件或者一組記錄，這些記錄或者文件分布于多個存儲節(jié)點上。數(shù)據(jù)小塊可以遠遠多于計算機的數(shù)量。
其次，Sawzall解釋器開始處理每一個小塊數(shù)據(jù)。這個處理跨越了大量機器，也許數(shù)據(jù)和機器綁定在一起，也可能數(shù)據(jù)在臨近的機器上而不在一起。
Sawzall程序分別處理每一個輸入記錄。每一個記錄的輸出結(jié)果，0個或者多個中間結(jié)果值-整數(shù)，字串，key-value pairs，tuple等等-將和其他記錄的輸出值合并。
這些中間結(jié)果于是被發(fā)送到運行聚合器的進一步處理的結(jié)點上，這些節(jié)點比較和減少中間結(jié)果，并且構(gòu)造終結(jié)結(jié)果。在一個典型的運行中，主要的計算機集群會運行Sawzall，并且小一點的集群會運行聚合器，這樣的結(jié)構(gòu)反映不僅是體現(xiàn)在計算量的差異，也體現(xiàn)在網(wǎng)絡(luò)負載的均衡考慮；每一個步驟，數(shù)據(jù)流量都比上一個步驟要少（參見圖2）。
當(dāng)所有的處理都完成之后，結(jié)果將被排序，格式化，并且保存到一個文件。
3．例子
用這個簡單的例子可以更清楚的表達這樣的想法。我們說我們的輸入是一個由浮點數(shù)記錄組成的文件集合。這個完整的Sawzall程序?qū)x取輸入并且產(chǎn)生三個結(jié)果：記錄數(shù)，值得總合，并且值得平方和。
count: table sum of int;
total: table sum of float;
sum_of_squares: table sum of float;
x: float=input;
emit count<-1;
emit sum<-x;
emit sum_of_squares <- x*x;
前三行定義了聚合器：計數(shù)器，合計，平方和。關(guān)鍵字table定義了聚合器類型；在Sawzall中，即使聚合器可能是單例的，也叫做table。這些特定的table是屬于合計的table；他們把輸入的整數(shù)或者浮點數(shù)的值進行累加。
對于每一個輸入的記錄，Sawzall初始化預(yù)定義的變量input來裝載尚未處理的輸入記錄二進制串。因此，行：
x: float = input;
把輸入記錄從它對外的表示轉(zhuǎn)換成為內(nèi)嵌的浮點數(shù)，并且保存在本地變量x。最后，三個emit語句發(fā)送中間結(jié)果到聚合器。
當(dāng)程序執(zhí)行的時候，程序?qū)γ恳粋€輸入記錄只執(zhí)行1次。程序定義的本地變量每次重新創(chuàng)建，但是程序定義的table會在所有執(zhí)行中共享。處理過的值會通過全局表進行累加。當(dāng)所有記錄都處理了以后，表中的值保存在一個或者多個文件中。
接下來的幾節(jié)講述了本系統(tǒng)所基于的部分Google的基礎(chǔ)架構(gòu)：協(xié)議buffers，Google文件系統(tǒng)，工作隊列，MapReduce。后續(xù)章節(jié)描述語言和其他系統(tǒng)的詳盡部分。
4．協(xié)議Buffer
雖然在最開始已經(jīng)考慮了定義服務(wù)器之間的消息通訊，Google的協(xié)議Buffer也同樣用于描述保存在磁盤的持久化存儲的記錄格式。
這個協(xié)議Buffer的用處很類似XML，但是要緊湊的多，通過一個二進制的表示以及一個外部的數(shù)據(jù)描述語言（DataDescription Language DDL）是的協(xié)議編譯器能夠把協(xié)議編譯成為各種語言的支持代碼。
DDL構(gòu)造一個清晰，緊湊，可擴展的針對二進制記錄的描述，并且對記錄的字段進行命名。雖然二進制格式已經(jīng)是相當(dāng)緊湊的，但是常常還會在保存到磁盤的時候再進行一個壓縮，包裹一個壓縮層。
協(xié)議編譯器讀取DDL描述并且產(chǎn)生用于對數(shù)據(jù)的：組織，訪問，列集及散列處理的代碼。編譯時候的標(biāo)志指定了輸出的語言：C++，Java，Python,等等。這個產(chǎn)生的代碼通過嵌入應(yīng)用程序中，能夠提供對數(shù)據(jù)記錄高效簡潔的訪問。同時，也應(yīng)該提供驗證和調(diào)試保存的協(xié)議buffer的工具包
我們系統(tǒng)操作的大部分數(shù)據(jù)集都是按照協(xié)議buffer約定的格式存儲的記錄。協(xié)議編譯器通過增加對Sawzall的擴展來提供在新語言下的協(xié)議buffer的高效IO性能。
5．Google文件系統(tǒng)（GFS）
我們系統(tǒng)訪問的數(shù)據(jù)集通常保存在GFS內(nèi)，就是Goole的文件系統(tǒng)[9]。GFS提供一個可靠的分布式存儲系統(tǒng)，它可以通過分布在上千臺計算機的64M”塊”組織成為上Petabyte級別的文件系統(tǒng)。每一個塊都有備份，通常是3個備份，在不同的計算機節(jié)點上，這樣GFS可以無縫的從磁盤或者計算機的故障中容錯。
GFS是一個應(yīng)用級別的文件系統(tǒng)，有著傳統(tǒng)的分級的命名機制。數(shù)據(jù)集本身通常用一個常規(guī)的結(jié)構(gòu)存放，這些結(jié)構(gòu)存放在很多獨立的GFS文件中，每一個GFS文件大小接近1G。例如，一個文檔倉庫（web搜索器機器人探索結(jié)果），包含數(shù)十億HTMLpages，可能會存放在上千個文件中，每一個文件壓縮存放百萬級別的文檔，每個文檔大概有數(shù)K字節(jié)大小。
6．工作隊列和MapReduce
把工作安排到一組計算機集群上進行工作的處理軟件叫做（稍稍有點容易誤解）工作隊列。工作隊列很有效的在一組計算機及其磁盤組上創(chuàng)建了一個大尺度的分時共享機制。它調(diào)度任務(wù)，分配資源，報告狀態(tài)，并且匯集結(jié)果。
工作隊列和Condor[15]等其他系統(tǒng)比較類似。我們經(jīng)常把工作隊列集群和GFS集群部署在相同的計算機集群上。這是因為GFS是一個存儲系統(tǒng)，CPU通常負載不太高，在CPU空閑階段可以用來運行工作隊列任務(wù)。
MapReduce[8]是一個運行在工作隊列上的應(yīng)用程序庫。它提供三個主要功能。首先，它提供一個給予大量數(shù)據(jù)的并行處理的程序運行模式。第二，它把應(yīng)用從運行在分布式程序的細節(jié)中隔離出來，包括類似數(shù)據(jù)分布，調(diào)度，容錯等等。最后，當(dāng)發(fā)現(xiàn)條件許可時，各個計算機或者存儲自己的GFS數(shù)據(jù)節(jié)點上的應(yīng)用程序可以執(zhí)行計算，減少網(wǎng)絡(luò)的流量。
就是MapReduce名字說明的含義，這個執(zhí)行模式分成兩個步驟：第一個步驟是把一個執(zhí)行操作映射到數(shù)據(jù)集合的全部元素；第二個步驟是簡化第一個步驟地輸出結(jié)果，并且產(chǎn)生最終的應(yīng)答。例如，一個使用MapReduce的排序程序?qū)成湟粋€標(biāo)準(zhǔn)的排序算法到數(shù)據(jù)集和的每一個文件上，接下來就是運行一個合并排序程序來簡化第一個步驟出來的單獨結(jié)果，并且產(chǎn)生最終地輸出。在上千臺機器的Cluster中，一個MapReduce程序可以用每秒排序1G數(shù)據(jù)的速度排序上TB的數(shù)據(jù)[9]。
我們的數(shù)據(jù)處理系統(tǒng)是基于MapReduce的最上層的。Sawzall解釋器運行在映射步驟。這是在大量機器上并發(fā)完成的，每一個執(zhí)行實例處理一個文件或者一個GFS塊。Sawzall程序?qū)γ恳粋€數(shù)據(jù)集的記錄執(zhí)行只執(zhí)行一次。映射步驟地輸出是一個數(shù)據(jù)項的集合，并且是交給聚合器去處理。聚合器在簡化/減少的步驟運行來合并結(jié)果成為最終的輸出結(jié)果。
接下來的章節(jié)講述這些處理的細節(jié)。
7．Sawzall語言概覽
作為一種查詢語言，Sawzall是一種類型安全的腳本語言。由于Sawzall自身處理了很多問題，所以完成相同功能的代碼就簡化了非常多-與MapReduce的C++代碼相比簡化了10倍不止。
Sawzall語法和表達式很大一部分都是從C照搬過來的；包括for循環(huán)，while循環(huán)，if語句等等都和C里邊的很類似。定義部分借鑒了傳統(tǒng)Pascal的模式：
i: int ; # a simple integer declaration;
i: int=0; # a declaration with an initial value;
基本類型包括整數(shù)（int），是64位有符號值；浮點數(shù)（float），是一個double精度的IEEE浮點數(shù)；以及很類似整數(shù)的time和fingerprint。time是毫秒級別的時間，并且函數(shù)庫包括了對這個類型的轉(zhuǎn)換和操作。fingerprint是一個執(zhí)行定義的hash值，可以很容易通過建立數(shù)據(jù)的fingerprint來構(gòu)造聚合器索引。
同時，Sawzall也有兩種基本的數(shù)組類型：bytes，類似C的unsigned char的數(shù)組；string，string用來存放UNICODE的字符串。在Sawzall中沒有”字符”類型；byte數(shù)組和string的基本元素是int，而雖然int的容量遠比字節(jié)或者字符串的基本元素來得大。
復(fù)合類型包括數(shù)組，maps（本文檔中是可以重載概念），tuples。數(shù)組是用整數(shù)作為下標(biāo)檢索的，maps是結(jié)合了數(shù)組或者Python字典的類型，可以用任意類型檢索，可以根據(jù)需要建立無序的索引。最后tuples是對數(shù)據(jù)的任意分組，類似C或者PASCAL的結(jié)構(gòu)類型。任何類型都可以有一個正式的名字。
類型轉(zhuǎn)換操作是把數(shù)據(jù)從一種類型轉(zhuǎn)換成為另一種類型，并且Sawzall提供了很廣泛的類型轉(zhuǎn)換。例如，把一個字符串表示的浮點數(shù)轉(zhuǎn)換成為一個浮點數(shù)：
f: float;
s: string = "1.234";
f = float(s);
部分轉(zhuǎn)換是可以帶參數(shù)的：
string(1234, 16)
就可以把一個整數(shù)轉(zhuǎn)換成為一個16進制的字符串。并且：
string(utf8_bytes, "UTF-8")
轉(zhuǎn)換一個UTF-8的byte數(shù)組成為一個unicode字符串。
為了方便起見，并且為了避免某些語言定義上的啰嗦，編譯器可以在初始化定義的時候隱含的左適當(dāng)?shù)霓D(zhuǎn)換操作（使用缺省的轉(zhuǎn)換參數(shù)）。因此：
b: bytes = "Hello, world!\n";
等價于顯示的轉(zhuǎn)換：
b: bytes = bytes("Hello, world!\n", "UTF-8");
任何類型的值都可以轉(zhuǎn)換成為字符串，這是為了調(diào)試的方便考慮。
Sawzall最重要的轉(zhuǎn)換是和協(xié)議buffer相關(guān)的。Sawzall有一個編譯時刻參數(shù)：proto，有點類似C的#include指令，可以從一個定義了Sawzall tuple類型的文件加載DDL協(xié)議buffer。通過tuple描述，就可以轉(zhuǎn)換輸入的協(xié)議buffer到Sawzall的值了。
對于每一個輸入記錄，解釋器都需要把這個由二進制數(shù)組表達的值初始化到特定的輸入變量中，尤其是轉(zhuǎn)換到協(xié)議buffer類型的輸入變量中去。Sawzall程序?qū)τ诿恳粋€記錄的執(zhí)行都是由下邊這條語句隱式執(zhí)行的：
input: bytes = next_record_from_input();
因此，如果文件：some_record.proto包含了類型Record的協(xié)議buffer的定義，那么下邊的代碼會把每一個輸入記錄分析道變量r中：
proto "some_record.proto" # define ’Record’
r: Record = input; # convert input to Record
Sawzall有很多其他的傳統(tǒng)特性，比如函數(shù)以及一個很廣泛的選擇基礎(chǔ)函數(shù)庫。在基礎(chǔ)函數(shù)庫中是給調(diào)用代碼使用的國際化的函數(shù)，文檔分析函數(shù)等等。
7.1．輸入和聚合
雖然在語句級別Sawzall是一個很傳統(tǒng)的語言，但是它有兩個非常不尋常的特性，都在某種意義上超越了這個語言本身：
- Sawzall程序定義了對于數(shù)據(jù)的單個記錄的操作。這個語言沒有提供任何可以同時處理多條記錄的方法，以及沒有提供通過一個輸入記錄的值來影響另一個記錄的方法。
- 這個語言為一個輸出時emit語句，這個語句發(fā)送數(shù)據(jù)到一個外部的聚合器來匯聚每一個記錄的結(jié)果并且在聚合器進行結(jié)果的加工和處理。
因此普通的Sawzall程序行為是使用輸入變量，用轉(zhuǎn)換操作把輸入的記錄分析到一個數(shù)據(jù)結(jié)構(gòu)，檢查數(shù)據(jù)，并且處理成一些值。我們在第三節(jié)可以看到這種模式的一個簡單例子。
下邊是一個更有代表性的Sawzall程序例子。對于給定的我們原代碼管理系統(tǒng)的源代碼提交記錄集合，這個程序會用分鐘級別的分辨率，給出周的提交變化頻率表。
proto "p4stat.proto"
submitsthroughweek: table sum[minute: int] of count: int;
log: P4ChangelistStats = input;
t: time = log.time; # microseconds
minute: int = minuteof(t)+60*(hourof(t)+24*(dayofweek(t)-1));
emit submitsthroughweek[minute] <- 1;
這個程序一開始從文件p4stat.proto引入了協(xié)議buffer描述。在這個文件中定義了類型: P4ChangelistSTats(程序員必須明確知道這個類型是從proto引入的，而且還要知道這個是由協(xié)議bufferDDL定義的)
接下來就是定義了submitsthroughweek。它定義了一個sum值得table，這個table使用一個整數(shù)minute作為下標(biāo)。注意index值在table定義的時候是給出了一個可選的名字（minute）。這個名字沒有任何語義，但是使得這個定義更容易理解，并且提供了一個聚合輸出的域標(biāo)簽。
log的定義把輸入的byte數(shù)組轉(zhuǎn)換成為Sawzall的類型：P4ChangelistStats,這個轉(zhuǎn)換是用（proto語句引入的代碼轉(zhuǎn)換的），這個類型是tuple類型，保存在輸入變量log里邊。接著我們把time值取出來，并且接著就保存到變量t中。
接下來的定義有著更復(fù)雜的初始化表達式，這個表達式使用了一部分內(nèi)嵌的函數(shù)，用來從time值來計算基準(zhǔn)的周分鐘基線數(shù)字[2]。
最后，emit語句通過增加該分鐘的數(shù)字來統(tǒng)計這個提交情況。
總結(jié)一下，這個程序，對于每一個記錄，都取得時間戳，把時間轉(zhuǎn)換成為本周的分鐘數(shù)，然后在這周的對應(yīng)分鐘發(fā)生次數(shù)增加1。并且，隱式的，這個會重新取下一個記錄進行循環(huán)處理。
當(dāng)我們在全部的提交日志上運行這個程序，這個記錄跨越了很多個月，并且輸出結(jié)果，我們可以看到一個按照分鐘區(qū)分的聚合的周活動趨勢。輸出結(jié)果可能像這樣的：
submitsthroughweek[0] = 27
submitsthroughweek[1] = 31
submitsthroughweek[2] = 52
submitsthroughweek[3] = 41
…
submitsthroughweek[10079] = 34
當(dāng)使用圖像表達，那么這個圖就像圖三一樣。
我們舉這個例子要表達的意思當(dāng)然不是說這個提交源碼的頻率數(shù)據(jù)如何如何，而是說這個程序怎樣產(chǎn)生抽取這個數(shù)據(jù)出來。
圖3：周源代碼提交頻率。本圖從周一早上凌晨0點開始。
7.2．聚合器補充說明
因為某些原因，我們在本語言之外完成聚合。應(yīng)該由一個傳統(tǒng)的語言來用語言處理能力本身來處理結(jié)果，但是由于聚合的算法可能會相當(dāng)?shù)膹?fù)雜，最好用某種形式的機器語言來實現(xiàn)。更重要的是，雖然在語言層面上隱藏了并行的機制，但是在過濾階段和聚合階段劃一條清晰的界限能夠有助于更高級別的并行處理。在Sawzall中不存在記錄的多樣性的，在Sawzall典型任務(wù)就是在上百或者上千臺機器上并發(fā)操作上百萬條記錄，
集中精力在聚合器上可以創(chuàng)造出很不尋常的聚合器?，F(xiàn)在已經(jīng)有許多聚合器；下邊是一個不完整的列表：
● 搜集器
c: table collection of string;
一個簡單的輸出結(jié)果列表，這個結(jié)果在列表中是任意順序的。
● 采樣器
s: table sample(100) of string
類似搜集器，但是存的是無偏差的輸出結(jié)構(gòu)的采樣值。這個采樣的大小是用參數(shù)體現(xiàn)的。
● 累加
s: table sum of (count:int,revenue:float);
所有輸出結(jié)果的合計。這個輸出結(jié)果必須是算數(shù)的或者可以以算術(shù)為基礎(chǔ)的（也就是可累加的，by 譯者），就像例子中的tuple結(jié)構(gòu)那樣（也就是說一般可以是sum of int,也可以像上邊說的一樣，可以用sum of (count:int,revenue:float)這樣的tuple結(jié)構(gòu)。對于復(fù)合值，元素是按照內(nèi)部的項進行累加的。在上邊的例子，如果count始終為1，那么平均revenue可以在處理完和以后用revenue除以count來得到。
● 最大值
m: table maximum(10) of string weight length: int;
取得最大權(quán)重的值。每一個值都有一個權(quán)重，并且最終選擇的值是根據(jù)最大權(quán)重來選擇的。這個參數(shù)（例子中是10）規(guī)定了需要保留的最終輸出的值數(shù)量。權(quán)重是以明確的keyword來描述的，并且它的類型（這里是int）是在這里定義的，它的值是emit語句給出的。對上邊例子來說，emit語句如下：
emit m <- s weight len(s);
這樣將會在結(jié)果中放置最長的字符串。
● 分位數(shù)
q: table quantile(101) of response_in_ms:int;
是用輸出的值來構(gòu)造一個每個概率增量分位數(shù)的累計概率分布（算法是一個Greenwald和Khanna的分布式算法[10]）。這個例子可以用來查看系統(tǒng)的響應(yīng)變化的分布情況。通過參數(shù)101，這個參數(shù)用來計算百分點。第50個元素是中間點的響應(yīng)時間，第99個元素是99%的響應(yīng)時間都小于等于第99個元素。
● 最常見
c: table top(10) of language: string;
top table評估這個值是否最常見（與之對應(yīng)的，maximun table找到最高權(quán)重的值，而不是最常見的值）
例如：
emit t <- language_of_document(input);
將會從文檔庫中建立10個最常見的語言。對于很大的數(shù)據(jù)集來說，它可能需要花費過大的代價來找到精確的出席頻率的order，但是可以有很有效的評估算法。top table是用了Charikar,Chen,Farach-Colton[5]的分布式算法。算法返回的最常見的頻率是極為接近真實的出現(xiàn)頻率。因為它的交換性和結(jié)合性也不是完全精確的：改變處理的輸入記錄先后順序確實會影響到最終的結(jié)果。作為彌補措施，我們在統(tǒng)計元素個數(shù)之外，也要統(tǒng)計這些個數(shù)的誤差。如果這個誤差和元素個數(shù)相比比較小，那么結(jié)果的正確度就比較高，如果錯誤相對來說比較大，那么結(jié)果就比較差。對于分布不均勻的大型數(shù)據(jù)集來說，top table工作的很好。但是在少數(shù)情況下比如分布均勻的情況下，可能會導(dǎo)致工作的不是很成功。
● 取唯一
u: table unique(10000) of string;
unique table是比較特別的。它報告的是提交給他的唯一數(shù)據(jù)項的估計大小。sum table可以用來計算數(shù)據(jù)項的總和個數(shù)，但是一個unique table會忽略掉重復(fù)部分；最終計算輸入值集合得大小。unique table同樣特別無論輸入的值是什么類型，它的輸出總是一個count。這個參數(shù)是給出了內(nèi)部使用的table大小，這個是用來內(nèi)部作評估是用的內(nèi)部表；10000的參數(shù)值會讓最終結(jié)果有95%的概率正負2%的誤差得到正確的結(jié)果（對于N，標(biāo)準(zhǔn)偏差是大概N*參數(shù)**(-1/2)）
有時候也會有新的聚合器出來。雖然聚合器用處很大，但是增加一個新的聚合器還算容易。聚合器的實現(xiàn)復(fù)雜在需要支持所有解釋器所支持的數(shù)據(jù)類型。聚合器的實現(xiàn)還需要效驗?zāi)承╊愋停ㄐｒ瀰?shù)值和元素類型），并且對保存和讀取數(shù)據(jù)作打包。對于簡單的聚合器，類似sum，就沒有什么其他的要求了。對于更復(fù)雜的聚合器，類似分位數(shù)和top，必須注意要選擇一個符合交換律和結(jié)合律的算法，并且這個算法要在分布式處理上有足夠的效率。我們最小的聚合器實現(xiàn)上大概只用了200行C++代碼，最大的聚合器用了大概1000行代碼。
有些聚合器可以作為map階段來處理數(shù)據(jù)，這樣可以降低聚合器的網(wǎng)絡(luò)帶寬。例如sum table可以本地作各個元素的累加，只是最后把本部分的小計發(fā)往遠端的聚合器。用MapReduce的詞語來說，這就是MapReduce的合并階段，一種在map和reduce中間的優(yōu)化階段。
7.3．帶索引的聚合器
聚合器可以是帶索引的，這個可以使得每一個索引下標(biāo)的值都有一個單獨的聚合器。這個index可以是任意的Sawzall類型，并且可以是一個聚合器的多維的結(jié)構(gòu)下標(biāo)。
例如，如果我們檢查web服務(wù)器的log，table：
table top(1000)[country:string][hour:int] of request:string;
可以用來找到每一個國家每一個小時的最常用的請求字串。
當(dāng)新的索引值產(chǎn)生的時候，就會動態(tài)產(chǎn)生一個獨立的聚合器，某種意義上比較類似map，但是是和所有運行的機器無關(guān)。聚合階段會比較每一個索引下標(biāo)對應(yīng)的值，并且產(chǎn)生適當(dāng)?shù)木酆现到o每一個索引值。
作為整理的一部分，數(shù)據(jù)值將按照索引排序，這樣使得從不同機器上合并最終結(jié)果比較容易。當(dāng)任務(wù)完成的時候，輸出值就按照索引進行排序了，這就意味著聚合器的輸出是索引順序的。
index本身就是構(gòu)造了一個有用的信息。就像上邊講述的web服務(wù)器的例子，當(dāng)運行完以后，在country索引的記錄中就構(gòu)造了請求接收到的國家集合。另外，index的引入使得可以用index對結(jié)果集進行分類。table sum[country:string] of int產(chǎn)生的索引結(jié)果將會等同于去掉重復(fù)項以后的table collection of country:string的結(jié)果值。
8．System Model
下邊介紹本語言的基本特性，通過對數(shù)據(jù)分析的建立，我們可以給出高級別的系統(tǒng)模式概覽。
系統(tǒng)運行是基于一個批處理的模式的：用戶提交一個工作，這個工作分布在一個固定的文件集合上，并且在執(zhí)行完成以后搜集輸出的結(jié)果。輸入格式和數(shù)據(jù)源（通常是文件集）以及輸出目標(biāo)都是在程序語言外指定的，通過執(zhí)行工作的參數(shù)形式來遞交給系統(tǒng)進行執(zhí)行。
當(dāng)系統(tǒng)接收到一個工作請求，Sawzall處理器就開始效驗這個程序是否語法正確。如果語法正確，源代碼就發(fā)送給各個將被執(zhí)行的機器，每一個機器就開始分析代碼并且開始執(zhí)行。
每一個執(zhí)行的機器的輸出都分不到一組文件中，每一個文件都部署在一個聚合器機器上。這個輸出結(jié)果拆分到不同的機器上，是為了能讓聚合器并行工作。我們給予特定的table和他上邊的相關(guān)索引來確定這些分布在各個文件中的值。
基于table的類型，輸入table的值可以是最終格式的值，也可以是某種中間結(jié)果的值，這些中間結(jié)果便于進行合并或者處理。這種合并處理必須能夠良好的結(jié)合起來才能工作的一個步驟。某些工作由于十分巨大，而結(jié)合率允許他們拆成多個小塊，并行運行，最后再合并在一起。（這是本系統(tǒng)的一個優(yōu)勢，優(yōu)于平坦模式的MapReduce;因為MapReduce可能會在一個需要運行幾天幾周的任務(wù)上出問題）
通常，分解處理以后的數(shù)據(jù)要比輸入要小得多，但是也會有某些關(guān)鍵的應(yīng)用不是這樣的。例如，我們的程序可以用一個帶索引的collection table來對數(shù)據(jù)作多維的組織，在這樣的情況下，輸出結(jié)果就可能比輸入要多。
Sawzall中一個常用的輸入是把結(jié)果數(shù)據(jù)注入一個傳統(tǒng)的關(guān)系數(shù)據(jù)庫中，以備后續(xù)的分析。通常這些都是有不同的用戶程序來注入，也許是用Python，它把數(shù)據(jù)轉(zhuǎn)換成為通過SQL指令建立的表。我們以后也許會提供更多的直接方法來完成八結(jié)果注入到數(shù)據(jù)庫的動作。
Sawzall的結(jié)果有時也用于其它Sawzall程序的輸入，這個就是鏈?zhǔn)教幚?。鏈?zhǔn)教幚淼暮唵卫泳褪蔷_計算輸出的”top 10”列表。Sawzall的top table雖然高效，但是他不精確。如果需要精確的結(jié)果，那么就需要分為兩個步驟。第一步創(chuàng)建一個帶索應(yīng)的sum table來統(tǒng)計輸入值得頻率；第二個步驟是用一個maximum table來選擇最常見的頻率。這樣可能有點笨，但是這種方法依舊是非常高效的方法來計算多維的table。
9．例子
這里是另外一個完整的例子，演示了Sawzall在實際中如何使用。這里是處理一個web文檔庫，并且產(chǎn)生一個結(jié)果：對于每一個web服務(wù)器，那一個page有著最高的Page Rank[13]？答曰來說，那一個是最多l(xiāng)ink指向的page？
proto “document.proto”
max_pagerank_uri:
table maximun(1)[domain:string] of url:string
weight pagerank:int;
doc: Document = input;
url: string = doc.url;
emit max_pagerank_url[domain(url)] <- url
weight doc.pagerank;
protocol buffer 的格式是在”document.proto”中定義的。這個table是max_pagerank_url，并且會紀錄每一個索引中最高權(quán)重的值。這個索引是domain，值是URL，權(quán)重勢document的PageRank。程序處理輸入的紀錄，解出URL，并且執(zhí)行相關(guān)的emit語句。它會調(diào)用庫函數(shù) domain(url)來解出URL所對應(yīng)的domain，并且使用這個domain作為index，把URL作為值，并且用這個document對應(yīng)的PageRank作為權(quán)重。
當(dāng)這個程序在一個數(shù)據(jù)倉庫上運行的時候，輸出對于大部分site，most-linked網(wǎng)頁是www.site.com-真是令人驚訝。Acrobat 下載站點是adobe.com的top page，并且連接到banknotes.com的就是連接到連接最多的圖庫站點，并且bangkok-th.com是最多引用的夜生活page。
因為是用Sawzall能簡單表達這樣的計算，所以程序是又簡潔又優(yōu)美。即使用了MapReduce,等價的C++程序也要好幾百行代碼。
下邊是一個例子，使用了多維索引的聚合器。我們目的是通過檢索搜索log，建立一個查詢發(fā)起點的世界地圖。
proto “querylog.proto”
queries_per_degree: table sum[lat:int][lon:int] of int;
log_record: QueryLogProto = input;
loc: Location = locationinfo(log_record.ip);
emit queries_per_degreee[int(loc.lat)][int(loc.lon)] <- 1;
這個程序相當(dāng)直接，我們引入查詢log的DDL，定義一個用了經(jīng)緯作索引的table，并且從log中解包查詢。接著我們是用內(nèi)嵌函數(shù)把這個IP地址對應(yīng)到請求及其的位置（可能是ISP的位置），并且為每一個經(jīng)緯點增加1。int(loc.lat)把loc.lat，一個浮點值轉(zhuǎn)換成為一個整數(shù)，截斷成為一個維數(shù)下標(biāo)。對于高分辨的地圖來說，可能要求更精細的計算。
這個程序的輸出是一個數(shù)組，可以用來構(gòu)造一個地圖，參見圖4。
10．執(zhí)行模式
在語句級別，Sawzall是一個常規(guī)的語言，但是從更高的角度看，他有一些特點，所有的設(shè)計目的都是為了并行計算。
當(dāng)然，最重要的是，一次處理一個紀錄。這就意味著，其他紀錄的處理將不消耗額外的內(nèi)存（除了在語言本身外把結(jié)果提交給聚合器）。Sawzall在上千臺機器上并行執(zhí)行，是Sawzall的一個設(shè)計目的，并且系統(tǒng)要求這些機器之間沒有額外的通訊。唯一的通訊就是從Sawzall的執(zhí)行結(jié)果下載到聚合器。
圖四：查詢分布
為了強調(diào)這點，我們用計算輸入記錄數(shù)的數(shù)量來入手。就像我們之前看到的這個程序：
count: table sum of int;
emit count <- 1;
這個程序?qū)⑼瓿山y(tǒng)計記錄數(shù)的工作。與之對比的是，如下的一個錯誤的程序：
count: int = 0;
count ++;
這個程序?qū)⒉荒芙y(tǒng)計記錄數(shù)，因為，對于每一個記錄來說，count都被設(shè)置成為0，然后再++，最后結(jié)果就扔掉了。當(dāng)然，并行到大量機器上執(zhí)行，扔掉count的效率當(dāng)然很高。
在處理每一個記錄之前，Sawzall程序都會回到初始的狀態(tài)。類似的，處理完成一條記錄，并且提交了所有的相關(guān)的數(shù)據(jù)給聚合器后，任何執(zhí)行過程中使用到的資源—變量—臨時空間等等—都可以被廢棄。Sawzall因此使用的是一個arena allocator[11](單向遞增分配，場地分配策略，就是說，從一個內(nèi)存池中通過單向增加一個指針的方式來分配內(nèi)存，類似零散內(nèi)存的管理方式)。當(dāng)一個記錄都處理完成之后，就釋放到初始狀態(tài)。
在某些情況下，重新初始化是不需要的。例如，我們可能會創(chuàng)建一個很大的數(shù)組或者影射表來對每條記錄進行分析。為了避免對每條記錄都作這樣的初始化，Sawzall有一個保留字static可以確保這個變量只初始化一次，并且是在處理每條記錄的最開始的初始化的時候執(zhí)行。這就是一個例子：
static CJK: map[string] of string = {
“zh” : “Chinese”,
“jp”:”Japanese”,
“ko”,”Korean”,
};
CJK變量會在初始化的時候創(chuàng)建，并且作為處理每條記錄的初始化的時候都保留CJK變量的值。
Sawzall沒有引用類型；它是純粹值語義的。數(shù)組和maps也可以作為值來是用（實現(xiàn)的時候，在大部分情況下，用copy-on-write引用計算來提高效率）。某些時候這個比較笨拙-在一個函數(shù)中修改一個數(shù)組，那么這個函數(shù)必須返回一個函數(shù)-但是在典型的Sawzall程序中，這個并沒有太大的影響。但是這樣的好處，就可以使得并發(fā)處理記錄的時候，不需要擔(dān)心同步問題或者擔(dān)心交叉使用的問題，雖然實現(xiàn)上很少會用到這個情況。
11．語言的Domain相關(guān)特性
為了解決domain操作的問題，Sawzall有許多domain相關(guān)的特性。有一部分已經(jīng)討論過了，本節(jié)討論的是剩下的一部分。
首先，跟大部分”小語言”[2]所不同，Sawzall是一個靜態(tài)類型語言。主要是為了可靠性的考慮。Sawzall程序在一次運行中，會是用數(shù)小時，乃至好幾個月的CPU時間，一個遲綁定（late-arising）動態(tài)類型錯誤導(dǎo)致的代價就有可能太大。另外，還有一個潛在的原因，聚合器使用完整的Sawzall類型，靜態(tài)類型會讓聚合器的實現(xiàn)比較容易。類似的爭議也在分析輸入?yún)f(xié)議buffer上；靜態(tài)類型可以精確檢測輸入的類型。同樣的，也會因為避免了運行時刻動態(tài)類型檢測而提高整個的性能。最后，便以時候類型檢查和強制類型轉(zhuǎn)換要求程序員精確的指出類型轉(zhuǎn)換。唯一的例外是在變量初始化的時候，但是就算在這個時候，類型以就是清晰而且程序也是類型安全的。
從另外的角度上看，強類型保證了變量的類型一定可知，在初始化的時候容易處理。例如：
t: time=”Apr 1 12:00:00 PST 2005”;
這樣的初始化就很容易理解，而且還是類型安全的。并且有一些基本類型的屬性也是主機相關(guān)的。比如處理log記錄的time stamps的時候，這個time基本類型就是依賴于log記錄的time stamps的；對于它來說，如果要支持夏令時的時間處理就太過奢侈了。更重要的是（近來比較少見了），這個語言定義了用UNICODE表示string，而不是處理一組擴展字符集編碼的變量。
由于處理大量數(shù)據(jù)集的需要，我們有賦予這個語言兩個特性：處理未定義的值，處理邏輯量詞。下兩節(jié)詳細描述這個特性。
11.1 未定義的值
Sawzall沒有提供任何形式的異常處理機制。相反，他有自己的未定義值得處理概念，用來展示錯誤的或者不確定的結(jié)果，包括除0錯，類型轉(zhuǎn)換錯誤，I/O錯誤，等等。如果程序在初始化以外的地方，嘗試去讀一個未定義的值，它會崩潰掉，并且報告一個失敗。
def（）斷言，用于檢測這個值是否一定定義了；如果這個值是一個確定值，他返回true，否則返回false。他的通常用法如下：
v: Value = maybe_undefined();
if (def(v)) {
compute(v);
}
下面是一個必須處理未定義值得例子。我們在query-mapping程序中擴展一個時間軸。原始程序使用函數(shù)locationinfo()來通過外部數(shù)據(jù)庫判定IP地址的位置。當(dāng)IP地址不能在數(shù)據(jù)庫中找到的時候，這個程序是不穩(wěn)定的。在這種情況下，locationinfo()函數(shù)返回的是一個不確定的值，我們可以通過使用def()斷言來防止這樣的情況。
下邊就是一個簡單的擴展：
proto "querylog.proto"
static RESOLUTION: int = 5; # minutes; must be divisor of 60
log_record: QueryLogProto = input;
queries_per_degree: table sum[t: time][lat: int][lon: int] of int;
loc: Location = locationinfo(log_record.ip);
if (def(loc)) {
t: time = log_record.time_usec;
m: int = minuteof(t); # within the hour
m = m – m % RESOLUTION;
t = trunctohour(t) + time(m * int(MINUTE));
emit queries_per_degree[t][int(loc.lat)][int(loc.lon)] <- 1;
}
（注意，我們只是簡單的扔掉我們不知道的位置，在這里是一個簡單的處理）。在if后邊的語句中，我們用了一些基本的內(nèi)嵌函數(shù)（內(nèi)嵌常數(shù)：MINUTE），來截斷記錄中的time stamp的微秒部分，整理成5分鐘時間段。
這樣，給定的查詢log記錄會擴展一個時間軸，這個程序會把數(shù)據(jù)構(gòu)造多一個時間軸，這樣我們可以構(gòu)造一個動畫來展示如何隨著時間變化而查詢位置有變化。
有經(jīng)驗的程序員會使用def()來保護常規(guī)錯誤，但是，有時候錯誤混雜起來會很怪異，導(dǎo)致程序員很難事先考慮。如果程序處理的事TB級別的數(shù)據(jù)，一般都會有一些數(shù)據(jù)不夠規(guī)則；往往數(shù)據(jù)集的數(shù)據(jù)規(guī)則度超乎作分析程序的人的控制，或者包含偶爾當(dāng)前分析不支持的數(shù)據(jù)。在Sawzall程序處理的情況下，通常對于這些異常數(shù)據(jù)，簡單丟棄掉是最安全的。
Sawzall因此提供了一種模式，通過run-time flag的設(shè)置，可以改變未定義值得處理行為。通常，如果遇到一個未定義的值（就是說沒有用def()來檢測一下），將會終止程序并且會給出一個錯誤報告。當(dāng)run-time flag設(shè)置了，那么，Sawzall簡單的取消這個未定義的值相關(guān)的語句的執(zhí)行。對于一個損壞的記錄來說，就意味著對臨時從程序處理中去除一樣的效果。當(dāng)這種情況發(fā)生的時候，run-time會把這個作為日志，在一個特別的預(yù)先定義的Collection table中記錄。當(dāng)運行結(jié)束的時候，用戶可以檢查錯誤率是否可以接受。對于這個flag的用法來說，還可以關(guān)掉這個flag用于調(diào)試-否則就看不到bug！-但是如果在一個大數(shù)據(jù)集上運行的時候，還是打開為妙，免得程序被異常數(shù)據(jù)所終止。
設(shè)置run-time flag的方法是不太常見的錯誤處理方法，但是在實際中非常有用。這個點子是和Rinard etal[14]在gcc編譯器生成容錯代碼有點類似。在這樣的編譯器，如果程序訪問超過數(shù)組下表的索引，那么生成的代碼可以使得程序能夠繼續(xù)執(zhí)行。這個特定的處理方式參考了web服務(wù)器的容錯設(shè)計的模式，包括web服務(wù)器面臨惡意攻擊的健壯性的設(shè)計。Sawzall的未定義值得處理增加了類似的健壯性設(shè)計級別。
11.2 量詞
雖然Sawzall是基于單個記錄的操作，這些記錄可能會包含數(shù)組或者結(jié)構(gòu)，并且這些數(shù)組或者結(jié)構(gòu)需要作為單個記錄進行分析和處理。哪個數(shù)組元素有這個值？所有值都符合條件？為了使得這些容易表達，Sawzall提供了邏輯量詞操作，一組特定的符號，類似”for each”,”for any”,”for all”量詞。
在when語句的這種特定的構(gòu)造中，可以定義一個量詞，一個變量，和一個使用這個變量的布爾類型的條件。如果條件滿足，那么就執(zhí)行相關(guān)的語句。量詞變量就像普通的integer變量，但是它的基礎(chǔ)類型（通常是int）會有一個量詞前綴。比如，給定數(shù)組a，語句：
when(i: some int; B(A[i]))
F(i);
就會當(dāng)且僅當(dāng)對于一些i的取值，布爾表達式B(a[i])為TRUE的情況下，執(zhí)行F（i）。當(dāng)F（i）執(zhí)行了，他會被綁訂到滿足條件的值。對于一個when語句的執(zhí)行來說，要求有求值范圍的一個限制條件；在這個例子中，隱式的指出了關(guān)于數(shù)組的下標(biāo)就是求值的范圍。在系統(tǒng)內(nèi)部實現(xiàn)上，如果需要，那么系統(tǒng)使用def()操作來檢查邊界。
一共有三個量詞類型：some，當(dāng)有任意值滿足條件的時候執(zhí)行（如果超過一個滿足條件，那么就任選一個）;each,執(zhí)行所有滿足條件的值；all，當(dāng)所有的值都滿足條件的時候執(zhí)行（并且不綁定值到語句體）。
when語句可能包含多個量詞，通?？赡軙?dǎo)致邏輯編程的混淆[6]。Sawzall對量詞的定義已經(jīng)足夠嚴格了，在實際運用中也不會有大問題。同樣的，當(dāng)多重變量出現(xiàn)的時候，Sawzall規(guī)定他們將按照他們定義的順序進行綁定，這樣可以讓程序員有一定的控制能力，并且避免極端的情況。
下邊是一些例子。第一個測試兩個數(shù)組是否共享一個公共的元素：
when(i, j: some int; a1[i] == a2[j]) {
…
}
第二個例子擴展了這個用法。使用數(shù)組限制，在數(shù)組的下標(biāo)中使用用:符號來限制，他測試兩個數(shù)組中，是否共享同樣的3個或者更多元素的子數(shù)組：
when(i0, i1, j0, j1: some int; a[i0:i1] == b[j0:j1] &&i1 >= i0+3) {
…
}
在類似這樣的測試中，不用寫處理邊界條件的代碼。即使數(shù)組小于三個元素，這個語句依舊可以正確執(zhí)行，when語句的求值可以確保安全的執(zhí)行。
原則上，when語句的求值處理是可以并行計算的，但是我們還沒有研究這方面的內(nèi)容。
12 性能
雖然Sawzall是解釋執(zhí)行的，但是這不是影響性能的主要因素。大部分Sawzall程序都只會帶來很少一點的處理開銷和I/O開銷，而大部分的CPU時間都用于各種run-time的操作，比如分析protocol buffer等等。
不過，為了比較單CPU的Sawzall和其他解釋語言的解釋執(zhí)行性能，我們寫了一些小的測試程序。第一個是計算Mandelbrot的值，來測試基本的算術(shù)和循環(huán)性能。第二個測試函數(shù)用遞歸函數(shù)來計算頭35個菲波納契級數(shù)。我們在一個2.8G x86臺式機上執(zhí)行的測試。表1是測試結(jié)果，顯示了Sawzall遠比Python,Ruby或者Perl快，起碼這些benchmarks上要快。另一方面，在這些測試上，Sawzall比解釋執(zhí)行的Java慢1.6倍，比編譯執(zhí)行的Java慢21倍，比C++編譯的慢51倍。
表1：Microbenchmarks.第一個Mandelbrotset計算：500×500圖像，每點最多500次疊代。第二個用遞歸函數(shù)計算頭35個菲波納契級數(shù)。
這個系統(tǒng)的性能關(guān)鍵并非是單個機器上的性能，而是這個性能在處理大數(shù)據(jù)量時，增加機器的時候性能增加曲線。我們使用了一個450GB的壓縮后的查詢log數(shù)據(jù)，并且在其上運行一個Sawzall程序來統(tǒng)計某一個詞出現(xiàn)的頻率。這個程序的核心代碼是類似這樣的：
result: table sum[key: string][month: int][day: int] of int;
static keywords: array of string =
{ "hitchhiker", "benedict", "vytorin",
"itanium", "aardvark" };
querywords: array of string = words_from_query();
month: int = month_of_query();
day: int = day_of_query();
when (i: each int; j: some int; querywords[i] == keywords[j])
emit result[keywords[j]][month][day] <- 1;
我們在50到600臺2.4G Xeon服務(wù)器上執(zhí)行了這個測試程序。測試的時間結(jié)果在圖5體現(xiàn)了。在600臺機器的時候，匯聚器大概可以每秒處理1.06G壓縮后的數(shù)據(jù)，或者3.2G未壓縮的數(shù)據(jù)。如果這個性能擴展能力是比較完美的，那么隨著機器的增加處理性能能近似線形增長，這就是說，每增加一臺機器，都能增加一臺機器的完整處理性能。在我們的測試中，增加1臺機器的效率增加大約是相當(dāng)于增加0.98臺機器。
圖5：當(dāng)增加機器的時候性能變化曲線。實線是花費的時間，虛線是機器的工作時間產(chǎn)出。從50到600臺機器的一個區(qū)間內(nèi)，單機的性能產(chǎn)出僅僅下降了30%。
為什么需要一個新語言？
為什么我們需要在MapReduce之上增加一個新的語言？MapReduce已經(jīng)很高效了；還少什么嗎？為什么需要一個全新的語言？為什么不在MapReduce之上使用現(xiàn)成的語言比如Python？
這里給出了構(gòu)造一個特殊目的語言的常見原因。為某一個問題領(lǐng)域構(gòu)造特定的符號描述有助于程序清晰化，并且更緊湊，更有效率。在語言內(nèi)嵌聚合器（包括在運行時刻內(nèi)嵌聚合器）意味著程序員可以不用自己實現(xiàn)一個，這點不像使用MapReduce需要自己實現(xiàn)。同樣的，它也更符合大規(guī)模并發(fā)處理超大數(shù)據(jù)集時候的處理思路，并且根據(jù)這個處理思路寫出一流的程序。同樣的，對協(xié)議棧buffer的支持，并且提供了平臺相關(guān)的類型支持，在較低層面上簡化了程序開發(fā)。總的來說，Sawzall程序要比基于MapReduce的C++小上10~20倍，并且更容易書寫。
定制語言還有其他優(yōu)勢包括了增加平臺相關(guān)的特性，定制的調(diào)試和模型界面，等等。
不過，制作這個Sawzall的原始動機完全不同：并行，拆分聚合器，并且提供不需要對記錄內(nèi)部作分析就可以最大程度的對記錄進行并行處理。它也提供了一個分布式處理的模式，激勵用戶從另外的思維角度考察并行問題。在現(xiàn)成的語言中比如Awk[12],Python[1],用戶可能要用這個語言書寫聚合器，這就可能比較難以做到并行化處理。甚至就算在這些語言中提供了清晰的聚合器接口和函數(shù)庫，經(jīng)驗老到的用戶還有可能要實現(xiàn)他們自己的內(nèi)容，用以大幅度提高處理性能。
Sawzall采用的模式已經(jīng)被證明非常有效。雖然對于少數(shù)問題來說，這樣的模式還不能有效處理，但是大部分海量數(shù)據(jù)的處理來說都已經(jīng)很適用了，并且可以簡單用程序?qū)崿F(xiàn)，這就使得Sawzall成為google中很受歡迎的語言。
這個語言對用戶編程方面的限制也帶來額外的一些好處。因為用戶程序的數(shù)據(jù)流是強類型化的，它很容易用來提供記錄中的單獨字段的訪問控制。就是說，系統(tǒng)可以自動并且安全的在用戶程序外增加一層，這個層本身也是由Sawzall實現(xiàn)的，它用來隱藏敏感信息。例如，產(chǎn)品工程師可以在不被授權(quán)業(yè)務(wù)信息的情況下，訪問性能和監(jiān)控信息數(shù)據(jù)。這個會在單獨的論文中闡述。
14 工具
雖然Sawzall僅僅發(fā)布了18個月，他已經(jīng)成為了google應(yīng)用最廣泛的語言之一。在我們的源碼控制系統(tǒng)內(nèi)已經(jīng)有上千個Sawzall程序（雖然，天生這些程序就是短小精干的）。
Sawzall工具的一個衡量指標(biāo)就是它所處理的數(shù)據(jù)量。我們監(jiān)控了2005年3月的使用情況。在3月份，在一個有1500個XeonCPU的工作隊列集群上，啟動了32580個Sawzall job，平均每個使用220臺機器。在這些作業(yè)中，產(chǎn)生了18636個失敗（應(yīng)用失敗，網(wǎng)絡(luò)失敗，系統(tǒng)crash等等），導(dǎo)致重新運行作業(yè)的一部分。所有作業(yè)讀取了大約3.2×10^15字節(jié)的數(shù)據(jù)（2.8PB），寫了9.9×10^12字節(jié)（9.3TB）（顯示了”數(shù)據(jù)合并”有些作用）。平均作業(yè)處理大概100GB數(shù)據(jù)，這些作業(yè)總共大約等于一個機器整整工作一個世紀的工作。
15 相關(guān)工作
傳統(tǒng)的數(shù)據(jù)處理方式通常是通過關(guān)系數(shù)據(jù)庫保存數(shù)據(jù)，并且通過SQL查詢來進行查詢。我們的系統(tǒng)有比較大的不同。首先，數(shù)據(jù)集通常過于巨大，不能放在關(guān)系型數(shù)據(jù)庫里；而且文件直接在各個存儲節(jié)點進行處理，而不用導(dǎo)入一個數(shù)據(jù)庫服務(wù)器。同樣的，我們的系統(tǒng)也沒有預(yù)先設(shè)定的table或者索引；我們用構(gòu)造一個特別的table和索引來進行這樣的相關(guān)計算。
Sawzall和SQL完全不同，把高效的處理單個記錄分析結(jié)果的聚合器接口結(jié)合到傳統(tǒng)的過程語言。SQL有很高效的數(shù)據(jù)庫join操作，但是Sawzall卻不行。但是另一方面來說，Sawzall可以在上千臺機器上運行處理超大數(shù)據(jù)集。
Brook[3]是另一個數(shù)據(jù)處理語言，特別適合圖像處理。雖然在不同的應(yīng)用領(lǐng)域，就像Sawzall一樣，它也是基于一次處理一個元素的計算模式，來進行并行處理，并且通過一個聚合器內(nèi)核來合并（reduce）輸出。
另外一種處理大數(shù)據(jù)的方式是通過數(shù)據(jù)流的模式。這樣的系統(tǒng)是處理數(shù)據(jù)流的輸入，他們的操作是基于輸入記錄的順序。比如，Aurora[4]就是一個流模式處理系統(tǒng)，支持單向數(shù)據(jù)流輸入的數(shù)據(jù)集處理。就像Sawzall預(yù)定義的聚合器，Aurora提供了一個很小的，固定操作功能集合，兩者都是通過用戶定義的函數(shù)來體現(xiàn)的。這些操作功能可以構(gòu)造很多有意思的查詢。同Sawzall不同的是，部分Aurora操作功能是基于輸入值得連續(xù)的序列，或者輸入值得一個數(shù)據(jù)窗。Aurora只保存被處理的有限的一部分數(shù)據(jù)，并且不是為了查詢超大的歸檔庫設(shè)計的。雖然對Aurora來說，增加新的查詢很容易，但是他們只能在最近的數(shù)據(jù)上進行操作。Aurora和Sawzall不同，Aurora是通過精心設(shè)計的運行時刻系統(tǒng)和查詢優(yōu)化器來保證性能，而Sawzall是通過強力的并行處理能力來保證性能。
另一種流模式處理系統(tǒng)是Hancock[7]，對流模式的處理方式進行了擴展，提供了對每個查詢的中間狀態(tài)作保存。這個和Sawzall就完全不同，Sawzall完全不考慮每個輸入記錄的處理后的狀態(tài)。Hancock和Aurora一樣，專注于依靠提高單進程處理效率，而不是依靠大規(guī)模并行處理來提高性能。
16 展望
成百臺機器并行處理的生產(chǎn)力是非常大的。因為Sawzall是一個大小適度的語言，用它寫的程序通常比較小，并且是綁定I/O的。因此，雖然他是一個解釋語言，實現(xiàn)上效率也足夠了。但是，有些超大的，或者超復(fù)雜的分析可能需要編譯成為機器碼。那么編譯器需要每臺機器上執(zhí)行一次，然后就可以用這些高速的二進制代碼處理每條輸入記錄了。
有時候，程序在處理記錄的時候需要查詢外部數(shù)據(jù)庫。雖然我們已經(jīng)提供了對一些小型數(shù)據(jù)庫的支持，比如什么IP地址信息之類的，我們的系統(tǒng)還是可以用一個接口來操作一個外部數(shù)據(jù)庫。因為Sawzall對每條記錄來說是單獨處理的，所以當(dāng)進行外部數(shù)據(jù)庫操作的時候，系統(tǒng)會暫時停頓，當(dāng)操作完成，繼續(xù)處理記錄。在這個處理過程中，當(dāng)然有并行處理的可能。
有時候，我們對數(shù)據(jù)的分析需要多次處理，無論多次Sawzall處理或者從其他系統(tǒng)的處理而導(dǎo)致的多次Sawzall處理，比如從一個傳統(tǒng)數(shù)據(jù)庫來的，或者一個其他語言寫的程序來的；由于Sawzall并不直接支持”chaining”(鏈?zhǔn)教幚?，所以，這些多重處理的程序很難在Sawzall中展示。所以，對這個進行語言方面的擴展，可以使得將來能夠簡單的表達對數(shù)據(jù)進行多次處理，就如同聚合器的擴展允許直接輸出到外部系統(tǒng)一樣。
某些分析需要聯(lián)合從不同的輸入源的數(shù)據(jù)進行分析，通常這些數(shù)據(jù)是在一次Sawzall處理或者兩次Sawzall處理之后進行聯(lián)合分析。Sawzall是支持這樣的聯(lián)合的，但是通常要求額外的鏈接步驟。如果有更直接的join支持會簡化這樣的設(shè)計。
更激進的系統(tǒng)模式可以完全消除這種批處理的模式。在激進的模式下，一個任務(wù)比如性能檢測任務(wù)，這個Sawzall程序會持續(xù)的處理輸入數(shù)據(jù)，并且聚合器跟進這個數(shù)據(jù)流。聚合器本身在一些在線服務(wù)器上運行，并且可以在任何時候來查詢?nèi)魏蝨able或者table 條目的值。這種模式和流式數(shù)據(jù)庫[4][7]比較類似，事實上這個也是基于數(shù)據(jù)流模式考慮的。不過，在研究這種模式以前，由Dean和Ghemawat構(gòu)造的MapReduce庫由于已經(jīng)非常有效了，所以這樣的模式還沒有實現(xiàn)過。也許有一天我們會回到這樣的模式下。
17 結(jié)束語
隨著問題的增大，就需要有新的解決方案。為了更有效的解決海量數(shù)據(jù)集的大規(guī)模并發(fā)分析計算，就需要進一步限制編程模式來確保高并發(fā)能力。并且還要求不影響這樣的并發(fā)模式下的展示/應(yīng)用/擴展能力。
我們的覺得方法是引入了一個全新的語言叫做Sawzall。這種語言通過強制程序員每次考慮一條記錄的方式來實現(xiàn)這樣的編程模式，并且提供了一組強力的接口，這些接口屬于常用的數(shù)據(jù)處理和數(shù)據(jù)合并聚合器。為了能方便寫出能并發(fā)運行在上千臺計算機上執(zhí)行的簡潔有效的程序，學(xué)一下這個新的語言還是很超值的。并且尤其重要的是，用戶不用學(xué)習(xí)并發(fā)編程，本語言和底層架構(gòu)解決了全部的并發(fā)細節(jié)。
雖然看起來在一個高效環(huán)境下使用解釋語言有點夸張，但是我們發(fā)現(xiàn)CPU時間并不是瓶頸，語言明確指出，絕大部分程序都是小型的程序，并且大量的時間都耗費在I/O上以及run-time的本地代碼。此外，解釋語言所帶來的擴展性是比較強大的，在語言級別和在多機分布式計算上的表達都是容易證明擴展能力。
也許對我們系統(tǒng)的終極測試就是擴展能力。我們發(fā)現(xiàn)隨著機器的增加，性能增長是近似線性增長的。對于海量數(shù)據(jù)來說，能通過增加機器設(shè)備就能取得極高的處理性能。
18 致謝
Geeta Chaudhry寫了第一個強大的Sawzall程序，并且給出了超強建議。Amit Pate,Paul Haahr，Greg Rae作為最早的用戶給與了很多幫助。Paul Haahr創(chuàng)建了PageRank 例子。Dick Sites， Ren’ee French對于圖示有貢獻。此外Dan Bentley,Dave Hanson,John Lamping,Dick Sites,Tom Szymanski, Deborah A. Wallach 對本論文也有貢獻。
19 參考資料
[1] David M. Beazley, Python Essential Reference, New Riders, Indianapolis, 2000.
[2] Jon Bentley, Programming Pearls, CACM August 1986 v 29 n 8 pp. 711-721.
[3] Ian Buck et al., Brook for GPUs: Stream Computing on Graphics Hardware, Proc. SIGGRAPH,Los Angeles, 2004.
[4] Don Carney et al., Monitoring Streams – A New Class of Data Management Applications, Brown Computer Science Technical Report TR-CS-02-04. At
http://www.cs.brown.edu/research/aurora/aurora tr.pdf.
[5] M. Charikar, K. Chen, and M. Farach-Colton, Finding frequent items in data streams, Proc 29th Intl. Colloq. on Automata, Languages and Programming, 2002.
[6] W. F. Clocksin and C. S. Mellish, Programming in Prolog, Springer, 1994.
[7] Cortes et al., Hancock: A Language for Extracting Signatures from Data Streams, Proc. Sixth International Conference on Knowledge Discovery and Data Mining, Boston, 2000, pp. 9-17.
[8] Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Proc 6th Symposium on Operating Systems Design and Implementation, San Francisco, 2004, pages 137-149.
[9] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, The Google File System, Proc. 19th Symposium on Operating System Principles, Lake George, New York, 2003, pp. 29-43.
[10] M. Greenwald and S. Khanna, Space-efficient online computation of quantile summaries, Proc. SIGMOD, Santa Barbara, CA, May 2001, pp. 58-66.
[11] David R. Hanson, Fast allocation and deallocation of memory based on object lifetimes. Software–Practice and Experience, 20(1):512, January 1990.
[12] Brian Kernighan, Peter Weinberger, and Alfred Aho, The AWK Programming Language, Addison-Wesley, Massachusetts, 1988.
[13] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The pagerank citation algorithm: bringing order to the web, Proc. of the Seventh conference on the World Wide Web, Brisbane, Australia, April 1998.
[14] Martin Rinard et al., Enhancing Server Reliability Through Failure-Oblivious Computing, Proc. Sixth Symposium on Operating Systems Design and Implementation, San Francisco, 2004, pp. 303-316.
[15] Douglas Thain, Todd Tannenbaum, and Miron Livny, Distributed computing in practice: The Condor experience, Concurrency and Computation: Practice and Experience, 2004.
