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

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

作者：王潘安

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

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

一．介紹

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

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

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

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

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

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

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

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

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

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

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

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

　　這篇論文的貢獻(xiàn)主要如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 更新和查詢

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

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

    舉個(gè)例子，圖片2中的展示了兩次關(guān)于圖片1中的表的更新操作。為了保證表的一致性，每個(gè)更新操作包含對(duì)兩個(gè)表A,B的一致性的行（譯者注：說白了，就是要同時(shí)更新兩個(gè)表中的某一行），Mesa會(huì)自動(dòng)算出表C的更新操作，這是因?yàn)樗梢灾苯釉醋员鞡的更新操作。理論上說，一個(gè)單次的更新操作同時(shí)包含AdvertiserId和PublisherId屬性也可以被用作更新這三張表，但是這個(gè)代價(jià)比較大，特別是在表包含大量的屬性的情況下。



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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

更多網(wǎng)易研發(fā)、產(chǎn)品、運(yùn)營(yíng)經(jīng)驗(yàn)分享請(qǐng)?jiān)L問網(wǎng)易云社區(qū)。

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