摘要：包括近乎實時的數(shù)據(jù)獲取和查詢，高可用性，可靠性，容錯性以及伸縮性。不允許存在對系統(tǒng)進行查詢時，只有一部分?jǐn)?shù)據(jù)更新成功的情況。一個謹(jǐn)慎的數(shù)據(jù)倉庫設(shè)計要求一個事實在多個聚合和物化中保持一致性。作用于所有列的聚合函數(shù)是。

本文來自網(wǎng)易云社區(qū)

作者：王潘安

以下是本人在學(xué)習(xí)Google的Mesa數(shù)據(jù)倉庫論文的記錄，翻譯出來給大家分享，翻譯水平有限，請多多包涵。因論文比較長，本人將論文按照Mesa不同的模塊分開翻譯，方便閱讀。

摘要：Mesa是一個可伸縮性的分析型數(shù)據(jù)倉庫系統(tǒng)，它主要為Google的互聯(lián)網(wǎng)廣告業(yè)務(wù)服務(wù)。Mesa的設(shè)計是為了滿足一系列的來自用戶和系統(tǒng)的復(fù)雜的挑戰(zhàn)。包括近乎實時的數(shù)據(jù)獲取和查詢，高可用性，可靠性，容錯性以及伸縮性。Mesa每秒處理PB級的數(shù)據(jù)以及百萬行的更新。每天服務(wù)十億次查詢，獲取萬億行數(shù)據(jù)。Mesa是一個跨多個數(shù)據(jù)中心的數(shù)據(jù)倉庫，它提供一致的，可重復(fù)，低延遲的查詢服務(wù)，即使是在一個數(shù)據(jù)中心完全癱瘓的情況下。

一．介紹

　　隨著業(yè)務(wù)量的增大，數(shù)據(jù)的處理，存儲和查詢都面臨挑戰(zhàn)。對數(shù)據(jù)存儲的要求有如下幾點（此處省略一堆廢話）：

　　原子更新。一個單用戶的操作就可能引起相關(guān)數(shù)據(jù)的多次更新，影響大量的定義在跨多維度上的多指標(biāo)集的一致性視圖。不允許存在對系統(tǒng)進行查詢時，只有一部分?jǐn)?shù)據(jù)更新成功的情況。

　　一致性和正確性。出于商業(yè)和法律上的考慮。系統(tǒng)必須返回一致和正確的數(shù)據(jù)。即使一個查詢跨多個數(shù)據(jù)中心，我們也要提供強一致性和可重復(fù)的查詢結(jié)果。

    可用性。系統(tǒng)不允許出現(xiàn)單點故障。不會出現(xiàn)由于計劃中或非計劃中的維護或故障所造成的停機，即使出現(xiàn)影響整個數(shù)據(jù)中心或地域性的斷電也不能造成停機。      　　　

    近實時的更新。系統(tǒng)必須支持大約每秒幾百萬行規(guī)模的持續(xù)更新，包括添加新數(shù)據(jù)行和對現(xiàn)有數(shù)據(jù)行的增量更新。這些更新必須在幾分鐘內(nèi)對跨不同視圖和數(shù)據(jù)中心的查詢可見。

    查詢性能。系統(tǒng)必須對那些對時間延遲敏感的用戶提供支持，按照超低延遲的要求為他們提供實時的客戶報表，而進行批處理的用戶需要非常高的吞吐量。總的來說，系統(tǒng)必須支持將99%的點查詢的延遲控制在數(shù)百毫秒之內(nèi)，并且整體查詢控制在每天獲取萬億行的吞吐量。

　　可伸縮性。系統(tǒng)規(guī)模必須可以隨著數(shù)據(jù)規(guī)模和查詢總量的增長而伸展。舉個例子，它必須支持萬億行規(guī)模和PB級的數(shù)據(jù)。但是即使上述參數(shù)再出現(xiàn)顯著增長，更新和查詢的性能必須仍然得以保持。

　　在線的數(shù)據(jù)和元數(shù)據(jù)轉(zhuǎn)換。為了支持新功能的發(fā)布或?qū)ΜF(xiàn)有數(shù)據(jù)粒度的變更，客戶端經(jīng)常需要對數(shù)據(jù)模式進行轉(zhuǎn)換或?qū)ΜF(xiàn)有數(shù)據(jù)的值進行修改。這些變更必須對正常的查詢和更新操作沒有干擾。

　　Mesa是針對這些技術(shù)上和操作上的挑戰(zhàn)的解決方案。盡管這些需求的某一部分已經(jīng)被現(xiàn)有的數(shù)據(jù)倉庫系統(tǒng)解決了。Mesa是一個能同時解決上述問題的解決方案。Mesa是一個針對結(jié)構(gòu)化數(shù)據(jù)的分布式，可備份并且高可用的數(shù)據(jù)處理，存儲和查詢系統(tǒng)。Mesa從生成數(shù)據(jù)的流服務(wù)中獲取數(shù)據(jù)，在內(nèi)部進行聚合和持久化，通過查詢給用戶提供服務(wù)。盡管這篇論文主要討論的是廣告業(yè)務(wù)，但是Mesa是一個能滿足上述所有需求的通用的數(shù)據(jù)倉庫。　

　　Mesa利用谷歌的基礎(chǔ)設(shè)施和服務(wù)，比如Colossus(谷歌下一代的分布式文件系統(tǒng))，BigTable以及MapReduce，將數(shù)據(jù)被水平分片和備份，來實現(xiàn)存儲的可擴展性和可用性。更新操作可能會發(fā)生在一個單表的粒度上或者跨多張表。為了實現(xiàn)一致性以及滿足在更新的時候的反復(fù)查詢，基礎(chǔ)數(shù)據(jù)是多版本的。為了實現(xiàn)數(shù)據(jù)更新的可擴展性，數(shù)據(jù)是批量的，帶版本號的，周期性的合并進入Mesa中的。為了實現(xiàn)跨多數(shù)據(jù)中心的更新一致性，Mesa使用基于Paxos的分布式一致性協(xié)議。

　　 許多基于關(guān)系型和數(shù)據(jù)立方體的數(shù)據(jù)倉庫產(chǎn)品不支持在給用戶提供近實時查詢的同時，每幾分鐘就將數(shù)據(jù)倉庫中的數(shù)據(jù)連續(xù)的集成和匯聚。通常，這些解決方法都是與傳統(tǒng)企業(yè)數(shù)據(jù)倉庫相關(guān)的。在傳統(tǒng)企業(yè)數(shù)據(jù)倉庫中，數(shù)據(jù)匯聚進入數(shù)據(jù)倉庫的頻率低，通常是按天或者周匯聚。類似的，谷歌內(nèi)部的關(guān)于大數(shù)據(jù)的技術(shù)，比如說BigTable, Megastore, Spanner和F1，也都不能滿足這個場景。BigTable不能滿足Mesa提出的必要的原子性的需求。Megastore, Spanner和F1通常用來處理線上業(yè)務(wù)，他們支持跨地域的數(shù)據(jù)的強一致性，但是它們不能滿足Mesa更新操作吞吐量的峰值。但是，Mesa確實使用了BigTable和Paxos技術(shù)以及Spanner的元數(shù)據(jù)存儲的技術(shù)。

　　（這段實在不想翻譯了。總之，目前市面上的大數(shù)據(jù)產(chǎn)品都不行！真是狂拽酷炫吊炸天！）

　　這篇論文的貢獻主要如下：

我們展示了如何創(chuàng)建一個PB級數(shù)據(jù)倉庫，同時又擁有ACID這些事物性處理功能的系統(tǒng)。并且它可伸縮，來滿足谷歌高吞吐率的廣告指標(biāo)。

我們描述了一個版本管理系統(tǒng)，它使得高吞吐量的批量更新操作在可接受的延遲內(nèi)完成，同時也支持大量的查詢在低延遲下完成。

我們描述了一個高擴展性的分布式架構(gòu)，在單數(shù)據(jù)中心中，它可以從宕機和網(wǎng)絡(luò)故障中恢復(fù)。我們也展示了一個跨地域備份的架構(gòu)來應(yīng)對數(shù)據(jù)中心的癱瘓。這種設(shè)計的不同之處在于，業(yè)務(wù)數(shù)據(jù)是通過獨立且冗余的進程在多數(shù)據(jù)中心間異步備份。只有關(guān)鍵的元數(shù)據(jù)是同步的拷貝到每個地方。這種技術(shù)可以使跨數(shù)據(jù)中心的同步代價最小，并且還可以提供高吞吐的更新操作。

我們展示了如何在不影響正確性和已存在應(yīng)用的性能的條件下，動態(tài)和高效的處理大量表模型的變化。

我們描述了應(yīng)對由硬件或者軟件引起的數(shù)據(jù)錯誤的關(guān)鍵技術(shù)。

我們描述了這種規(guī)模的系統(tǒng)在保證正確性，一致性和性能上的挑戰(zhàn)。并且提出幾點供新的研究來改進。

二 . Mesa存儲子系統(tǒng)

   Mesa中的數(shù)據(jù)持續(xù)不斷的生成，它是谷歌量級最大，價值最高的數(shù)據(jù)集。在這個數(shù)據(jù)集上的分析型查詢包括簡單的查詢，諸如：“某一個特定的廣告在某一天有多少點擊量？”和涉及更多內(nèi)容的查詢，諸如：“某一個特定的廣告，在十月份第一個星期的上午8點到11點間，通過移動設(shè)備在某個特定的地理位置，通過關(guān)鍵字decaf在google.com上搜索獲得的點擊量是多少？”

　　數(shù)據(jù)在Mesa中以多維模型存放，它依據(jù)不同的維度獲取了所有谷歌廣告平臺上最細(xì)節(jié)的事實。這些事實由兩部分屬性組成：維度屬性（我們稱為鍵）和度量屬性（我們稱為值）。因為很多維度屬性是分層的，甚至有多層，比如日期維度中年/月/日或者周/季度/年。那么單一事實就需要根據(jù)這些層次維度匯聚成多個物化視圖，來滿足數(shù)據(jù)分析中的上卷和下鉆操作。一個謹(jǐn)慎的數(shù)據(jù)倉庫設(shè)計要求一個事實在多個聚合和物化中保持一致性。

2.1 數(shù)據(jù)模型

　　在Mesa中，數(shù)據(jù)以表的形式存儲。每張表有它的模型（schema）來描述它的結(jié)構(gòu)。一個表模型有它的鍵空間Ｋ和相應(yīng)的值空間Ｖ，Ｋ和Ｖ在這里都是集合。表模型也有它的聚合函數(shù)Ｆ: V × V -> V 用來聚合跟同一鍵相關(guān)的多個值。聚合函數(shù)必須滿足結(jié)合律。在很多情況下，它也滿足交換律，盡管Mesa中包含不滿足交換律的聚合函數(shù)。表模型中也包含一個或者多個K的全序索引。

    鍵空間K和值空間V表現(xiàn)為列的二元組。他們都有固定的數(shù)據(jù)類型，表模型為每個多帶帶的列指定了聚合函數(shù)F，F(xiàn)隱式的定義成如下形式（譯者注：說白了，就是把V放在一起寫，對應(yīng)于每個二元組的聚合函數(shù)不多帶帶寫出來，統(tǒng)一寫成個F）：

     F((x1,.....,xk),(y1,.....yk)) = (f1(x1, y1),......fk(xk, yk))

其中(x1,.....,xk)和(y1,.....yk)都屬于V，f1....fk這種形式是聚合函數(shù)的顯式表現(xiàn)形式。（真蛋疼）

    舉個例子。圖片1展示了Mesa中的三個表。這三張表都包含廣告的點擊量和費用，只不過被分散到不同的屬性中，比如按天的點擊量，（譯者注：圖中的Date, PublisherId, Country, AdvertiserId都是key， Clicks和Cost是value）。作用于所有列的聚合函數(shù)是SUM。假設(shè)相同的底層事件更新了這三張表的數(shù)據(jù)，那么所有的指標(biāo)都被一致的表現(xiàn)在三個表中。表1只是簡單的呈現(xiàn)了表模型。在生產(chǎn)環(huán)境中，Mesa包含上千張表，每張表包含上百列，使用多個聚合函數(shù)。

2.2 更新和查詢

    為了實現(xiàn)大吞吐量的更新操作，Mesa采用批量更新。這些更新的批量包產(chǎn)生于Mesa系統(tǒng)外的上游系統(tǒng)，每隔幾分鐘產(chǎn)生（更小的頻率更高的更新包可以使更新操作延遲低，但是它需要消耗更多的資源）。每次更新，Mesa都會指定一個版本號 n (從0開始的序列)以及這些更新行的構(gòu)成（表名，鍵，值）。每一個（表名，鍵）至多包含一個匯聚值。

    Mesa上的一個查詢包含一個版本號 n 和 鍵空間上的謂語P。返回值包含一行符合條件P的鍵，這些鍵出現(xiàn)在一些更新中并帶上了版本號0到n。而數(shù)據(jù)值按照表結(jié)構(gòu)中定義的聚合函數(shù)進行聚合后，返回聚合值。Mesa實際上支持更復(fù)雜的查詢功能，但是所有的都可以看成對這種基本查詢的預(yù)處理和后加工。

    舉個例子，圖片2中的展示了兩次關(guān)于圖片1中的表的更新操作。為了保證表的一致性，每個更新操作包含對兩個表A,B的一致性的行（譯者注：說白了，就是要同時更新兩個表中的某一行），Mesa會自動算出表C的更新操作，這是因為它可以直接源自表B的更新操作。理論上說，一個單次的更新操作同時包含AdvertiserId和PublisherId屬性也可以被用作更新這三張表，但是這個代價比較大，特別是在表包含大量的屬性的情況下。



    注意表C與以下這個表B的物化視圖的關(guān)系：SELECT SUM(Clicks), SUM(Cost) GROUP BY AdvertiserId, Country. 這個查詢可以直接當(dāng)作Mesa中的表，這是因為查詢中的SUM函數(shù)就是對表B中所有度量值列的匯聚函數(shù)。Mesa約束在所有的度量列上使用相同的聚合函數(shù)，才能稱作物化視圖。

    為了使更新原子性，Mesa采用了多版本的方法。Mesa按版本號的順序執(zhí)行更新操作。通過在執(zhí)行下一條更新操作之前完全合并此次更新操作來確保原子性。用戶永遠(yuǎn)感受不到局部合并更新帶來的影響。

    嚴(yán)格的按順序更新帶來的不僅僅是原子性的應(yīng)用。Mesa中的有些聚合函數(shù)不滿足交換律，比如在標(biāo)準(zhǔn)的Key-Value存儲中，一個(Key, Value)的更新完全覆蓋它之前的值。更細(xì)致的來看，按順序的約束使得Mesa支持將錯誤的事實用相反的行為來表示。特別的，谷歌使用欺詐探測來決定廣告的點擊是否合法。欺詐性的點擊可以用相反的事實來表示。比如在上圖2中，就可以跟一個版本2的更新，這個更新包括負(fù)值的點擊數(shù)和費用，去標(biāo)記之前處理的點擊數(shù)是非法的。通過嚴(yán)格的按順序更新，Mesa保證了負(fù)的更新事實永遠(yuǎn)不會在它的正事實之前被合并。

2.3 數(shù)據(jù)版本管理

     數(shù)據(jù)版本在Mesa的更新和查詢中扮演了十分重要的角色。但是它也帶來了很多挑戰(zhàn)。首先，對于那些可以被聚合的廣告統(tǒng)計數(shù)據(jù)，多帶帶存儲每一個版本從存儲的角度來看非常昂貴。聚合后的數(shù)據(jù)量就要小的多。其次，在查詢的時候，遍歷所有的版本并且聚合它們的代價也很大，并且會加大查詢的延遲。再次，在每次更新時都提前聚合所有的版本也需要極高的代價。

    為了處理這個問題。Mesa提前聚合某些版本的數(shù)據(jù)并且使用deltas存儲（譯者注：說白了就是分版本區(qū)間存儲），每一個delta包含一組不重復(fù)鍵的數(shù)據(jù)，以及一個delta版本號，用[V1, V2]表示，其中V1和V2是更新操作版本號，并且V1小于或等于V2。我們用版本號來表示delta就很清楚了。delta[V1, V2]中的行指的是那些出現(xiàn)在版本號為V1和V2之間的更新操作的鍵，值對應(yīng)的就是這些更新操作聚合后的值。更新操作被當(dāng)做是一個單例delta合并進Mesa。一個單例delta版本[V1, V2]滿足V1=V2=n, 其中n就是此次更新的版本號。

    delta[V1, V2]和delta[V2+1, V3]可以通過簡單的合并鍵/聚合值的方式合并成一個delta[V1, V3]（2.4章節(jié)中會討論，所有的行都是以鍵的方式存儲的，所以說，兩個delta可以在線性時間內(nèi)合并完成），這個計算的正確性是由聚合函數(shù)F確保的。這個正確性并不依賴函數(shù)F的交換律。無論何時Mesa通過一個給定的鍵合并兩個值時，delta的版本都是形如[V1, V2]和[V2+1, V3]的，并且這個操作是在不斷增長的有序版本號上進行的。

    Mesa僅僅允許用戶查詢一段時間以內(nèi)的所有版本，比如24小時以內(nèi)的。這就說明，早于這個時間的版本就可以聚合到一個基礎(chǔ)delta中，設(shè)它的版本號為[0, B], 其中B大于或等于0，這樣，任意一個delta[V1, V2]只要滿足0 <= V1 <= V2 <= B就可以被刪除。這個過程被稱為base compaction（基礎(chǔ)壓縮聚合，譯者注：真不知道該如何翻譯這個專業(yè)名詞）。Mesa同其他操作，比如查詢和更新，并發(fā)的異步執(zhí)行這個base compaction操作。

    注意一下，跟更新版本有關(guān)的的時間是由那個版本生成的，它獨立于數(shù)據(jù)中的任何時間信息。舉個例子，圖1中的Mesa表，數(shù)據(jù)中的2014/01/01這個時間是永遠(yuǎn)不會被移除的。Mesa可能會拒絕超過某個時間后的版本的查詢。數(shù)據(jù)中的時間數(shù)據(jù)其實是另外一個屬性并且它對Mesa不透明（譯者注：提醒讀者數(shù)據(jù)中的時間和Mesa中記錄版本的時間不要混為一談）。

    有了base compaction， 回答某個版本n上的查詢，我們可以聚合一個基本的delta[0, B]和一系列單例delta[B+1, B+1]. [B+2, B+2],...,[n,n]，然后返回值。雖然我們經(jīng)常的聚合成一個基礎(chǔ)delta（比如說每天），但是我們的單例delta個數(shù)很容易上百，甚至上千，特別是對于那些更新密集的表。為了支持更高效的查詢，Mesa包含了一些形如[U,V]的累積delta D，其中B < U < V。這些累積的delta可以被用來求解一個版本n的delta劃分，比如{[0, B],[B+1, V1],[V1+1, V2],...,[Vk+1, n]}，這樣就比直接使用單例delta需要更少的聚合操作。當(dāng)然，這些累積delta也需要一些處理和存儲上的開銷。但是這些開銷被分?jǐn)偟搅怂械牟僮髦腥チ?，特別是查詢操作。所以用這些delta代替單例delta是可行的。

     delta的聚合策略決定了每個時刻deta在Mesa上是如何維護的。它的基本目的是平衡那些查詢操作，更新操作以及處理和存儲累積delta的開銷。這個delta的策略要考慮三件事情：1. 哪些delta（除了單例delta）需要優(yōu)先生成來滿足這些更新版本可以被查詢到。這個操作是在更新路徑上同步進行的，會降低更新的速度。2. 哪些delta是可以在更新路徑以外異步的生成的。3. 那些delta是可以被刪除的。

     如圖3所示的一個delta匯聚策略就是一個雙重級別的策略。在這種策略中，任何時刻都存在一個基本delta[0, B], 一系列的累積delta[B+1, B+10], [B+1, B+20],[B+1, B+30],...以及B以后的所有單例delta。每當(dāng)?shù)贐+10X個版本合并時，就異步的生成delta[B+1, B+10X]。新的基礎(chǔ)delta[0, B1]每天生成一次，但是這個新的基礎(chǔ)delta在所有基于它的累積delta還沒完全生成之前是不可用的。當(dāng)基礎(chǔ)delta B切換到B1時，這個策略就將老的基礎(chǔ)delta，累積delta以及所有B1版本之前的單例delta刪除。這樣的話，一個查詢就只需要一個基礎(chǔ)delta，一個累積delta和幾個單例delta組合完成，大大減少了查詢時的工作量。



     Mesa目前所使用的是兩級別delta的變種策略，它使用多種級別的累積delta，對于最近的版本，累積delta包含少量的單例delta，對于比較老的版本，累積delta包含較多的單例delta。一個delta層級可能包含一個基礎(chǔ)delta，一個包含100個版本的delta，一個包含10個版本的累積delta，以及多個單例delta。類似的基于日志結(jié)構(gòu)的存儲引擎有LevelDB和BigTable。我們注意到，基于差異更新的Mesa維護數(shù)據(jù)的方式，是一個簡單的對不同存儲模型的適配。并且它可以被用于增長性視圖和列存的更新。（譯者注：我真看不懂這句話，隨便翻譯的。）

2.4 物理數(shù)據(jù)和索引形式

    Mesa中的delta是基于delta聚合策略來創(chuàng)建和刪除的。一旦delta被創(chuàng)建，它就是不可變的，所以物理的存儲結(jié)構(gòu)不需要支持高效的增量更新。

    不可變的delta就允許Mesa使用一個相當(dāng)簡單的存儲結(jié)構(gòu)。因為存儲是Mesa的主要開銷，因此，對這種存儲結(jié)構(gòu)的基本要求就是省空間。Mesa還必須支持根據(jù)鍵的快速查找，因為一個查詢往往關(guān)系幾個delta，然后根據(jù)鍵將值聚合起來。為了使查詢鍵變的高效，每個Mesa表包含一個或多個表索引，每個表索引都包含一個根據(jù)索引排序的數(shù)據(jù)的拷貝（譯者注：空間換時間咯）。

    存儲結(jié)構(gòu)的細(xì)節(jié)比較偏向技術(shù)，所以我們只關(guān)注最重要的部分。delta中的行按順序存儲在有大小限制的數(shù)據(jù)文件中（這是針對文件系統(tǒng)文件大小限制的優(yōu)化）。這些行本身被組織在行塊中，每個行塊被多帶帶的變換和壓縮。每個行塊中的數(shù)據(jù)按列式存儲來進行變換壓縮，提高壓縮率。因為存儲是Mesa主要的開銷，并且在查詢時解壓性能比寫入時壓縮性能重要。所以我們在選用壓縮算法的時候更強調(diào)壓縮比和解壓速率。

    Mesa為每份數(shù)據(jù)文件存儲一份索引文件。每個索引實例包含一個行塊的短鍵，這個短鍵由這個行塊第一個鍵的固定長度前綴以及這個壓縮行塊在數(shù)據(jù)文件中的偏移量組成。那么查詢一個指定的鍵的算法就可以分為兩步，首先通過二分法從索引文件中找出可能包含這個短鍵的行塊，然后在這個壓縮的行塊中通過二分法找到想要的鍵。

這一篇就翻譯到這里，其中的思想很值得借鑒，有些開源的項目已經(jīng)采用了部分技術(shù)。下一篇我們一起看看Mesa的架構(gòu)。

網(wǎng)易云免費體驗館，0成本體驗20+款云產(chǎn)品！

更多網(wǎng)易研發(fā)、產(chǎn)品、運營經(jīng)驗分享請訪問網(wǎng)易云社區(qū)。

文章來源： 網(wǎng)易云社區(qū)