孫榮辛｜大數據穿針引線進階必看——Google經典大數據知識
- 2022 年 11 月 8 日
- 筆記
大數據技術的發展是一個非常典型的技術工程的發展過程，榮辛通過對於Google經典論文的盤點，希望可以幫助工程師們看到技術的探索、選擇過程，以及最終歷史告訴我們什麼是正確的選擇。
何為大數據
「大數據」這個名字流行起來到現在，差不多已經有十年時間了。在這十年里，不同的人都按照自己的需要給大數據編出了自己的解釋。有些解釋很具體，來自於一線寫 Java 程式碼的工程師，說用 Hadoop 處理數據就是大數據；有些解釋很高大上，來自於市場上靠發明大詞兒為生的演說家，說我們能採集和處理全量的數據就是大數據，如果只能採集到部分數據，或者處理的時候要對數據進行取樣，那就不是大數據。
在筆者看來，其實「大數據」技術的核心理念是非常清晰的，基本上可以被三個核心技術理念概括。
-
伺服器規模：能夠伸縮到一千台伺服器以上的分散式數據處理集群的技術。
-
伺服器架構：這個上千個節點的集群，是採用廉價的 PC 架構搭建起來的。
-
編程模式：「把數據中心當作是一台電腦」（Datacenter as a Computer）。
| 觸發問題 | 大數據技術 | 傳統數據處理技術 | 解決的問題 |
|---|---|---|---|
| 伺服器規模 | 千台伺服器以上 | 幾十台伺服器 | 可行性 |
| 伺服器架構 | 普通x86伺服器，普通硬碟 | 專用硬體，如大型機、小型機 | 性價比 |
| 編程模型 | Datacenter as a Computer | 使用方自己處理分散式和容錯問題 | 複雜性 |
大型集群讓處理海量數據變得「可能」；基於開放的 PC 架構，讓處理海量數據變得「便宜」；而優秀的封裝和抽象，則是讓處理海量數據變得「容易」。這也是現在誰都能用上大數據技術的基礎。可以說，這三個核心技術理念，真正引爆了整個「大數據」技術，讓整個技術生態異常繁榮。
筆者認為，Google 能成為散播大數據火種的人，是有著歷史的必然性的：作為一個搜索引擎，Google 在數據層面，面臨著比任何一個互聯網公司都更大的挑戰。無論是 Amazon 這樣的電商公司，還是 Yahoo 這樣的門戶網站，都只需要存儲自己網站相關的數據。而 Google，則是需要抓取所有網站的網頁數據並存下來。而且光存下來還不夠，早在 1999 年，兩個創始人就發表了 PageRank 的論文，也就是說，Google 不只是簡單地根據網頁裡面的關鍵字來排序搜索結果，而是要通過網頁之間的反向鏈接關係，進行很多輪的迭代計算，才能最終確認排序。而不斷增長的搜索請求量，讓 Google 還需要有響應迅速的在線服務。
三駕馬車和基礎設施
面對存儲、計算和在線服務這三個需求，Google 就在 2003、2004 以及 2006 年，分別拋出了三篇重磅論文。也就是我們常說的「大數據」的三駕馬車：GFS、MapReduce 和 Bigtable。
GFS 的論文發表於 2003 年，它主要是解決了數據的存儲問題。作為一個上千節點的分散式文件系統，Google 可以把所有需要的數據都能很容易地存儲下來。GFS它運行於廉價的普通硬體上，並提供容錯功能，和以往的文件系統的不同，系統中部件錯誤不再被當作異常，而是將其作為常見的情況加以處理。其的新穎之處並不在於它採用了多麼令人驚訝的新技術，而在於它採用廉價的商用電腦集群構建分散式文件系統，在降低成本的同時經受了實際應用的考驗。
然後，光存下來還不夠，我們還要基於這些數據進行各種計算。這個時候，就輪到 2004 年發表的 MapReduce 出場了。通過借鑒 Lisp，Google 利用簡單的 Map 和 Reduce 兩個函數，對於海量數據計算做了一次抽象，這就讓「處理」數據的人，不再需要深入掌握分散式系統的開發了。而且他們推出的 PageRank 演算法，也可以通過多輪的 MapReduce 的迭代來實現。MapReduce 解決了處理數據的問題，可以對數據進行各種計算。
這樣，無論是 GFS 存儲數據，還是 MapReduce 處理數據，系統的吞吐量都沒有問題了，因為所有的數據都是順序讀寫。但是這兩個，其實都沒有辦法解決好數據的高性能隨機讀寫問題。
因此，面對這個問題，2006 年發表的 Bigtable 就站上了歷史舞台了。它是直接使用 GFS 作為底層存儲，來做好集群的分片調度，以及利用 MemTable + SSTable 的底層存儲格式，來解決大集群、機械硬碟下的高性能的隨機讀寫問題。
到這裡，GFS、MapReduce 和 Bigtable 這三駕馬車的論文，就完成了「存儲」、「計算」、「實時服務」這三個核心架構的設計。不過這三篇論文其實還依賴了兩個基礎設施。
-
保障數據一致性的分散式鎖。對於這個問題，Google 在發表 Bigtable 的同一年，就發表了實現了 Paxos 演算法的 Chubby 鎖服務的論文。
-
數據怎麼序列化以及分散式系統之間怎麼通訊。Google 在前面的論文里都沒有提到這一點，但是Facebook 在 2007 年發表的 Thrift 的相關論文解決了相關問題。
實際上，Bigtable 的開源實現 HBase，就用了 Thrift 作為和外部多語言進行通訊的協議。Twitter 也開源了 elephant-bird，使得 Hadoop 上的 MapReduce 可以方便地使用 Thrift 來進行數據的序列化。
OLAP 和 OLTP 資料庫
可以說，Google這三駕馬車是為整個業界帶來了大數據的火種，但是整個大數據領域的進化才剛剛開始。
首先 MapReduce，作為一個「計算」引擎，在有著更大計算需求的背景下（OLAP），其開始朝著以下方式進化。
-
編程模型：MapReduce 的編程模型還是需要工程師去寫程式的，所以它進化的方向就是通過一門 DSL，進一步降低寫 MapReduce 的門檻。在這個領域的第一階段最終勝出的，是 Facebook 在 2009 年發表的 Hive。Hive 通過一門基本上和 SQL 差不多的 HQL，大大降低了數據處理的門檻，從而成為了大數據數據倉庫的事實標準；
-
執行引擎。Hive 雖然披上了一個 SQL 的皮，但是它的底層仍然是一個個的 MapReduce 的任務，所以延時很高，沒法當成一個互動式系統來給數據分析師使用。於是 Google 又在 2010 年，發表了 Dremel 這個互動式查詢引擎的論文，採用數據列存儲 + 並行資料庫的方式。這樣一來，Dremel 不僅有了一個 SQL 的皮，還進一步把 MapReduce 這個執行引擎給替換掉了。
-
多輪迭代問題：在 MapReduce 這個模型里，一個 MapReduce 就要讀寫一次硬碟，這對硬碟是無比大的負擔。2010年的Spark論文，通過把數據放在記憶體而不是硬碟里，大大提升了分散式數據計算性能。
圍繞 MapReduce，整個技術圈都在不斷優化和迭代計算性能，Hive、Dremel 和 Spark 分別從「更容易寫程式」，「查詢響應更快」，「更快的單輪和多輪迭代」的角度，完成了對 MapReduce 的徹底進化。
作為一個「在線服務」的資料庫，Bigtable 的進化是這樣的：
-
事務問題和 Schema 問題：Google 先是在 2011 年發表了 Megastore 的論文，在 Bigtable 之上，實現了類 SQL 的介面，提供了 Schema，以及簡單的跨行事務。如果說 Bigtable 為了伸縮性，放棄了關係型資料庫的種種特性。那麼 Megastore 就是開始在 Bigtable 上逐步彌補關係型資料庫的特性。
-
異地多活和跨數據中心問題：Google 在 2012 年發表的 Spanner，能夠做到「全局一致性」。這樣，就算是基本解決了這兩個問題，第一次讓我們有一個「全球資料庫」。
本質上說，MapReduce 的迭代是在不斷優化OLAP類型的數據處理性能，而Bigtable的進化，則是在保障伸縮性的前提下，獲得了更多的關係型資料庫的能力。
實時數據處理的抽象進化
從 MapReduce 到 Dremel，我們查詢數據的響應時間就大大縮短了。但是計算的數據仍然是固定的、預先確定的數據，這樣系統往往有著大到數小時、小到幾分鐘的數據延時。所以，為了解決好這個問題，流式數據處理就走上了舞台。
首先是 Yahoo 在 2010 年發表了 S4 的論文並將其開源。而幾乎是在同一時間，Twitter 工程師南森·馬茨（Nathan Marz）以一己之力開源了 Storm，並且在很長一段時間成為了工業界的事實標準。和 GFS 一樣，Storm 還支援「至少一次」（At-Least-Once）的數據處理。另外，基於 Storm 和 MapReduce，南森更是提出了 Lambda 架構，它可以稱之為是第一個 流批協同 的大數據處理架構。
接著在 2011 年，Kafka的論文也發表了。最早的 Kafka 其實只是一個「消息隊列」，但是由於 Kafka 里發送的消息可以做到「正好一次」（Exactly-Once），所以大家就動起了在上面直接解決 Storm 解決不好的消息重複問題的念頭。於是，Kafka 逐步進化出了 Kafka Streams 這樣的實時數據處理方案。而後在 2014 年，Kafka 的作者 Jay Krepson 提出了 Kappa 架構，這個可以被稱之為第一代「流批一體」的大數據處理架構。
在大數據的流式處理領域似乎沒有 Google 什麼事兒，但是在 2015 年，Google 發表的 Dataflow 的模型，可以說是對於流式數據處理模型做出了最好的總結和抽象。一直到現在，Dataflow 就成為了真正的「流批一體」的大數據處理架構。而後來開源的 Flink 和 Apache Beam，則是完全按照 Dataflow 的模型實現的了。
一致性與調度
到了現在，隨著「大數據領域」本身的高速發展，數據中心裏面的伺服器越來越多，我們對於數據一致性的要求也越來越高。為了解決一致性問題，我們就有了基於 Paxos 協議的分散式鎖。但是 Paxos 協議的性能很差，於是有了進一步的 Multi-Paxos 協議。可惜的是Paxos 協議並不容易理解，於是就有了 Raft 這個更容易理解的演算法的出現。Kubernetes 依賴的 etcd 就是用 Raft 協議實現的。
也正是因為數據中心裏面的伺服器越來越多，我們會發現原有的系統部署方式越來越浪費。當我們有數百乃至數千台伺服器的時候，浪費的硬體和電力成本就成為不能承受之重了。於是，儘可能用滿硬體資源成為了剛需。由此一來，我們對於整個分散式系統的視角，也從虛擬機轉向了容器，這也是 Kubernetes 這個系統的由來。其從更加全面的角度來進行資源管理和調度系統。
爭論與分歧
到此為止，筆者為大家簡單地介紹了大數據技術的論文演進的脈絡。但是整個技術的發展也並不是一個直線上升的狀態:
-
有爭論，比如 MapReduce 的論文發表之後，資料庫領域知名的科學家大衛·德維特（David DeWitt）就發表過一篇論文「MapReduce：A major step backwards」，抨擊 MapReduce 相比於並行資料庫是一種倒退；
-
有妥協，比如，Bigtable 不支援跨行事務也不支援 SQL，就是一個明證。直到 5 年後發表的 Megastore，他們才開始著手解決這兩個問題；
-
更有不成功的嘗試，典型的就是 Sawzall 和 Pig，Google 在發表 MapReduce 論文之前，就發表了 Sawzall 這個用來撰寫 MapReduce 任務的 DSL，Yahoo 也很早就完成了對應的開源實現 Apache Pig。但是 10 年後的今天，我們的主流選擇是用 SQL 或者 DataFrame，Pig 的用戶已經不多了，而 Sawzall 也沒有再聽 Google 提起過。
所以可以說，大數據技術的發展是一個非常典型的技術工程的發展過程，跟隨這個脈絡，我們可以看到工程師們對於技術的探索、選擇過程，以及最終歷史告訴我們什麼是正確的選擇。
大數據技術盤點
相比於某一門電腦課程、某一門程式語言或者某一個開源框架，「大數據」涉及到的知識點多而繁雜。所以這裡，筆者就整理了一份知識地圖，好讓讀者可以對論文中提到的知識點有跡可循。
分散式系統
所有的大數據系統都是分散式系統。我們需要大數據系統，就是因為普通的單機已經無法滿足我們期望的性能了。那麼作為一個分散式的數據系統，它就需要滿足三個特性：可靠性、可擴展性和可維護性。
-
可靠性：如果只記錄一份數據，那麼當硬體故障的時候就會遇到丟數據的問題，所以我們需要對數據做複製。而數據複製之後，以哪一份數據為準，又給我們帶來了主從架構、多主架構以及無主架構的選擇。在最常見的主從架構里，根據複製過程，可以有同步複製和非同步複製之分。同步複製的節點可以作為高可用切換的 Backup Master，而非同步複製的節點只適合作為只讀的 Shadow Master。
-
可擴展性：在「大數據」的場景下，單個節點存不下所有數據，於是就有了數據分區。常見的分區方式有兩種，第一種是通過區間進行分片，典型的代表就是 Bigtable，第二種是通過哈希進行分區，在大型分散式系統中常用的是一致性 Hash，典型的代表是 Cassandra。
-
可維護性。我們需要考慮容錯，在硬體出現故障的時候系統仍然能夠運作。我們還需要考慮恢復，也就是當系統出現故障的時候，仍能快速恢復到可以使用的狀態。而為了確保我們不會因為部分網路的中斷導致作出錯誤的判斷，我們就需要利用共識演算法，來確保系統中能夠對哪個節點正在正常服務作出判斷。這也就引出了 CAP 這個所謂的「不可能三角」。
分散式系統的核心問題就是 CAP 這個不可能三角，我們需要在一致性、可用性和分區容錯性之間做權衡和選擇。因此，我們選擇的主從架構、複製策略、分片策略，以及容錯和恢復方案，都是根據我們實際的應用場景下對於 CAP 進行的權衡和選擇。
存儲引擎
上萬台的分散式集群，最終還是要落到每一台單個伺服器上完成數據的讀寫。那麼在存儲引擎上，關鍵的技術點主要包括三個部分。
-
事務。在傳統的資料庫領域，我們有 ACID 這樣的事務特性即原子性（Atomic）、一致性（Consistency）、隔離性（Isolation）以及持久性（Durability）。而在大數據領域，很多時候因為分散式的存在，事務常常會退化到 BASE 的模型，即表基本可用（Basically Available）、軟狀態（Soft State）以及最終一致性（Eventually Consistent）。不過無論是 ACID 還是 BASE，在單機上，我們都會使用預寫日誌（WAL）、快照（Snapshot）和檢查點（Checkpoints）以及寫時複製（Copy-on-Write）這些技術，來保障數據在單個節點的寫入是原子的。而只要寫入的數據記錄是在單個分片上，我們就可以保障數據寫入的事務性，所以我們很容易可以做到單行事務，或者是進一步的實體組（Entity Group）層面的事務。
-
寫入和存儲。這個既要考慮到電腦硬體的特性，比如數據的順序讀寫比隨機讀寫快，在記憶體上讀寫比硬碟上快；也要考慮到我們在演算法和數據結構中的時空複雜度，比如 Hash 表的時間複雜度是 O(1)，B+ 樹的時間複雜度是 O(logN)。這樣，通過結合硬體性能、數據結構和演算法特性，我們會看到分散式資料庫最常使用的，其實是基於 LSM 樹（Log-Structured Merge Tree）的 MemTable+SSTable 的解決方案。
-
數據的序列化。出於存儲空間和兼容性的考慮，我們會選用 Thrift 這樣的二進位序列化方案。而為了在分析數據的時候盡量減少硬碟吞吐量，我們則要研究 Parquet 或者 ORCFile 這樣的列存儲格式。然後，為了在 CPU、網路和硬碟的使用上取得平衡，我們又會選擇 Snappy 或者 LZO 這樣的快速壓縮演算法。
計算引擎
計算的維度實際上也是大數據領域本身進化和迭代最快的一部分。
-
起初，最原始粗糙的 MapReduce 來進行批數據處理，然後圍繞它不斷迭代出了讓數據處理更快的 Spark 和讓數據處理更容易的各種 DSL（比如Hive）。
-
然後，圍繞著實時數據處理，有了「最少一次」的 S4/Storm，並把它和批處理綜合到一起，產生了著名的 Lambda 架構。
-
緊接著有了「以批為流」，通過 Mini-Batch 來進行實時數據處理的 Spark Streaming，以及「流批一體」，能夠做到「正好一次」的 Kafka 和 Kappa 結構。
-
最後，還是 Google 一錘定音，給出了統一的 Dataflow 模型，並伴隨著有了 Apache Flink 和 Apache Beam 這兩個開源項目。
隨著 Dataflow 論文的發表，整個大數據的處理引擎逐漸收斂成了一個統一的模型，這是大數據領域發展的一個新的里程碑。
經典文章總結
最後，筆者把文中提到的這些論文的前後之間的脈絡聯繫專門做了一張圖，放在了下面。如果讀者對某一篇論文感到困惑的時候，就可以去翻看它前後對應的論文，找到對應問題的來龍去脈。
同時筆者把在文中提到的論文清單列在了下面，供讀者作為一個索引。另外，如果有讀者覺得本文的內還不夠過癮，筆者強烈推薦你可以讀一下 Big Data: A Survey 這篇綜述文章，可以讓讀者更加深入「大數據」技術的全貌。
有的讀者可能擔心如何找到和下載這些論文。筆者已經貼心的為大家收集好了全部論文並上傳到雲盤中，只要點擊下方連接，即可獲得全套經典論文。
# 百度網盤鏈接: //pan.baidu.com/share/init?surl=h9eoDbgIYZMeQKb1zDAPOw提取碼: 4mei
其它相關
izx 問題：
這文章有幾個問題，一個關於序列化和服務間通訊的問題，protobuf/grpc是事實標準，thrift在grpc出現以後用的人就少了。另外，Bigtable不支援跨行事務按當時的場景也的確不需要，Google在跨行事務上是通過Percolator來解決的。
榮辛：高品質的回復，很好的補充!
1. 今日而言，如果新項目選擇rpc，grpc絕對是比thrift更合適的選擇。但Hadoop和HBase 又在使用thrift 和外部交互，要深入了解這些技術，thrift暫時還沒法繞開
2. BigTable不支援跨行事務，但Megastore已經在EntityGroup層面支援，到Spanner已經完全支援了。我的表述目的是在於這個演進的過程
3. Percolator個人感覺在學術和搜索引擎的索引更相關一些，本人水平有限，篇幅有限，就沒有講到。有興趣的讀者歡迎參考
//www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf
izx：
嗯嗯，我想說的是在Bigtable的年代，Google除了實時索引並沒有別的跨行事務的需求，所以就先有了Percolator，其他簡單事務都通過Chubby在應用層解決，後來Google業務複雜化之後才有了Megastore，但也更像是過渡方案，目前他們存儲層都在往Spanner遷移
榮辛：
所以說」大數據技術的發展是一個非常典型的技術工程的發展過程「，沒有完美銀彈的方案，只有最合適當下的方案。
其它文章
