【第168期 September 5, 2011】
 

研發新視界

Facebook到底用了哪些技術?(上)

作者/林旻君

[發表日期:2011/9/1]


前言

Facebook作為最大的社群網站,目前流量排名世界第二,僅次於Google,要支撐如此龐大的資料量,所需的硬體設備與技術當然不簡單,我們先來看看Facebook有哪些驚人的成就:

  • Facebook估計擁有超過六萬台伺服器。
  • 所有Memcached的執行程式所儲存的資料總量達300TB。
  • Hadoop跟Hive叢集是由三千台伺服器組成。每台都是八核心,32GB記憶體,12TB硬碟。結果是24000核心,96TB記憶體與36PB的儲存空間。
  • 每天有一千億次的點擊,光log也有130TB。
Facebook目前活躍人數已經快突破10億人,要如何使每一個使用者都享有一樣高品質的使用經驗,一直是一個嚴峻的挑戰,因此Facebook採取了綜合的策略,在整個社群網路中,能夠提昇使用者體驗的技術,都要作最佳化處理,因此本文接下來介紹Facebook主要使用了哪些技術來架構這個系統。以下為本文所要介紹的技術列表:
    1.雲端平臺Hadoop與相關元件(HBase、MapReduce、HDFS、Hive)
    2.HipHop
    3.Apache Thrift
    4.Memcached
    5.BigPipe
    6.Scribe
    7.Haystack
雲端平臺Hadoop與相關元件(HBase、MapReduce、HDFS、Hive)

分散式架構主要目的是讓服務開發人員,不用考慮在這些分散式系統上資料要怎麼放置、運算要怎麼切割,只需要專注在服務的開發就可以了,而資料與運算的切割及分散就交給雲端運算的架構來處理。Hadoop是Apache軟體基金會 (Apache Software Foundation) 底下的開放原始碼計劃 (Open source project),最初是做為Nutch這個開放原始碼的搜尋引擎的一部份。Hadoop是以java寫成,可以提供大量資料的分散式運算環境,而且Hadoop的架構是由Google發表的BigTable及Google File System等文章提出的概念實做而成,所以跟Google內部使用的雲端運算架構相似。

因此我們可以想像,一個雲端平臺必須要有自己的檔案格式與管理策略,因此HDFS就是為了處理分佈於各個伺服器上的檔案系統,而HBase提供了分散式資料庫的功能,MapReduce則提供了在分散式系統上進行更有效率的運算架構,Hive提供了在分散式系統上資料倉儲的功能。Hadoop主要核心完全使用Java開發,而使用者端則提供C++/Java/Shell/Command等程式開發介面,目前可執行於Linux、Mac OS/X、Windows和Solaris作業系統,以及一般商用等級的伺服器。 下圖就是Hadoop的組成元件:


《圖一》


MapReduce

MapReduce誕生源由是Google需要進行大規模資料處理,而在這個過程中,發現了處理大量資料時會面臨某些共同問題,如需要使用許多機器協同計算,以及處理輸入資料時有兩項作業:Map和Reduce。 這兩項作業主要是受到函數編程的啟發,以Map/Reduce為基礎的應用程式,能夠運作於數千台PC所組成的大型叢集上,並以一種容錯的方式平行處理P級別的資料量。 在函數編程中很早就有了Map和Reduce觀念,其實類似於演算法中各個擊破的作法(Divide and Conquer),也就是將問題分解成很多個小問題之後再做總和。Map函數的輸入是一個(Keg,Value)序對組,輸出則為另一組中繼過渡的(Key,Value)序對組。而Reduce函數則負責針對相同的中繼過渡的(Key,Value)序對組合併其所有相關聯的中繼值,並產生輸出結果的鍵/值序對組,如下圖所示。


《圖二》


簡而言之,MapReduce提供程式設計者一個在分散式系統上處理問題的框架,程式設計者需要設計Map與Reduce函數,決定如何切割與合併問題以達到最佳的效能,剩餘的底層處理則交給MapReduce框架。MapReduce是由Google所發展的軟體框架,目的是對電腦叢集上的大型資料集執行分散式運算,讓使用者可以把心力放在定義Map和Reduce函數,進行運算的Mapper和Reducer會由系統會自動指派不同的運算節點擔任,所以程式設計時完全不用做資料和運算的切割 (decomposition),運算資源會由JobTracker分配到各個運算節點上的TaskTracker,並指派不同的節點擔任Mapper和Reducer。透過MapReduce可以用於大型資料處理,例如:搜尋、索引製作與排序,大型資料集的資料採礦與機器學習,大型網站的網站存取日誌分析等應用。

在龐大的分散式架構下,有伺服器或資料損壞是十分常見的事,由於有MapReduce在處理細節,因此在處理過程中能夠大大降低因資料錯誤造成整個程式需重新啟動的狀況,因為龐大的資料量往往需要數十小時至數天的運算時間,因此能夠避免不必要的時間浪費。

HDFS

Hadoop Distributed File System (HDFS) 將分散的儲存資源整合成一個具容錯能力、高效率且超大容量的儲存環境,在Hadoop系統中大量的資料和運算時產生的暫存檔案,都是存放在這個分散式的檔案系統上。HDFS的設計理念是在分散式的儲存環境裡,提供單一的目錄系統 (Single Namespace),一個典型的超大型分散式檔案系統中,通常會有數萬個節點、數億個檔案、以及數十Peta Bytes的資料量,而這樣的分散式檔案系統具備的資料存取特性為Write Once Read Many存取模式。 也就是檔案一旦建立、寫入之後就不允許修改,因此當資料有異動時,檔案系統會重新建立一個新的檔案,在這之中,每個檔案被分割成許多區塊(block)與異地備份,每個區塊的大小通常為128 MB,系統會將每個區塊複製許多複本(replica),並分散儲存於不同的資料節點(DataNode)上。

除此之外,HDFS中很重要的概念是認為移動運算到資料端通常比移動資料到運算端來的成本低,這是由於資料的位置資訊會被考慮在內,因此運算作業可以移至資料所在位置,處理資料的檔案複本預設是每個檔案儲存3份,該設定可由開發人員自訂。 如前面提到的MapReduce在系統分配運算工作時,會將運算工作分配到存放有運算資料的節點上進行,減少大量資料透過網路傳輸的時間。HDFS採用的是一般等級伺服器,因此透過複製資料的方式以因應硬體的故障,當偵測到錯誤時,即可從複製的備份資料執行資料回復。下圖為HDFS架構。


《圖三》


HBase

簡而言之,HBase的目標是作為Hadoop所使用的資料庫,這可讓我們需要在隨機且即時的讀寫超大資料集時所使用。HBase是一種分散式儲存系統,其類似RDBM資料表的資料結構(Multi-Dimensional Map),並具備高可用性、高效能,以及容易擴充容量及效能的特性。HBase適用於利用數以千計的一般等級伺服器上,來儲存Petabytes級的資料,其中以Hadoop分散式檔案系統(HDFS)為基礎,提供類似Bigtable的功能,HBase同時也提供了MapReduce程式設計的能力。

HBase使用列 (row) 和行 (column) 為索引存取資料值,因此查詢的時候比較像在使用map容器 (container);HBase的另一個特點是每一筆資料都有一個時間戳記 (timestamp),因此同一個欄位可依不同時間存在多筆資料。一個HBase的資料表 (table) 是由許多row及數個column family組成,每個列都有一個row key做為索引;一個column family就是一個column label的集合 (set),裡面可有很多組label,這些label可以視需要隨時新增,而不用重新設定整個資料表如下表所示。在存取資料表的時候,通常就使用 (‘row key’, ‘family:label’) 或 (‘row key’, ‘family:label’, ‘timestamp’) 的組合取出需要的欄位元。下表為HBase的資料結構。


《圖四》


HBase為了方便分散資料和運算工作,又將整個資料表分為許多region,一個region是由一到數個列所組成的,可以分別存放在不同HBase主機上,這些存放region的主機就是region server,另外還有master server用來紀錄每一個region對應的region server;master server也會自動將不能提供服務的region server上的region重新分配到其他的region server上。

Hive

Hive是架構在Hadoop上的資料倉儲系統,目的是提供在分散是環境下的資料倉儲功能,我們先來簡單瞭解一下資料倉儲與資料庫的差異。資料庫與資料倉儲最大差異點是資料庫進行資料的新增、刪除、修改、查詢等功能其主要目的於管理資料庫的存取;而資料倉儲重視的是資訊的獲得,以問題決策分析導向,強調多維度視野,視覺化的提供決策者資訊可用性,資料倉儲與傳統資料庫差異比較如下表所示。


《圖五》


而Hive提供了類似SQL的語法稱為HQL讓使用者更容易操作Hive,同時Hive也提供了MapReduce外掛功能,來補足Hive本身指令的不足,Hive在Facebook主要是作為資料探勘的功能,例如當Facebook在推出新功能時,就會利用Hive研究新功能與舊功能兩者之間使用者行為的差異,藉以決定是否該推出新功能。當時Facebook計畫推出他們的“Like”按鈕時,他們擔心會不會發生“自相蠶食”的結果,會不會因此反而減少了文字評論,而不是提升了參與度?為了驗證這一點,他們運行了A/B測試來比較用戶行為,給一組用戶使用新功能(Like按鈕),而另一個對照組則沒有。這需要在一個互接連的社區內進行測試,“內生的組織”,在組織之外的連接很少。他們使用了兩組南美國家來進行比較,哥倫比亞、委內瑞拉 vs 阿根廷、智利。測試的結果是使用Like按鈕的時候評論增加了4.46%,而對照組的資料則是0.63%。這一類測試所產生的巨大的資料集正是Facebook使用Hadoop來處理資料的例子。

HipHop

Hiphop是一個由PHP到C++的轉換程式,一個重新實現的PHP運行庫和許多常用PHP擴展的重寫版本構成,目的是在加速和優化PHP。眾所周知,Facebook的前端主要是用PHP寫的。PHP非常簡單,易學易用,好讀好調適,因此新工程師成長很快,有利地促進了Facebook的快速創新。PHP是一種指令碼語言,其好處是程式設計效率高,能夠支援產品的快速反覆運算。但是與傳統的編譯語言相比,指令碼語言的CPU和記憶體使用效率不好。隨著Ajax技術的廣泛採用,加上SNS對動態要求較高,這些缺點更顯得突出。對於每月超過4000億次PV的Facebook來說,如何實現擴展,尤其具有挑戰性。常見的辦法是直接用C++重寫PHP應用中比較複雜的部分,作為PHP擴展。從技術角度講這也沒有問題,但是增加了技能需求,能夠在整個應用上工作的工程師數量就大大減少了。最後,Facebook選擇了HipHop,工程師可以編寫代碼,用PHP編寫組合最後頁面的邏輯,並能夠繼續快速反覆運算,同時後端服務使用C++, Erlang, Java, Python編寫,提供新聞提要、搜索、聊天和其他核心功能。

HipHop將PHP代碼轉換為高度優化的C++代碼,然後再用g++編譯器編譯。它可以保持語義等效地執行原始程式碼,但為了提高性能,犧牲了一些很少用到的特性,比如eval()。HipHop開發中的主要困難在於,在PHP和C++這兩種很不一樣的語言之間怎麼實現轉換。雖然PHP也可以寫一些很巧妙的動態特性,但是大多數PHP代碼還是非常簡單的。if (...) {...} else {..} 比foo($x) { include $x; } 肯定更常見。HipHop生成的代碼盡可能地使用函數和變數的靜態繫結。同時,還使用類型推演來選出變數最可能對應的某個類型,從而節省記憶體。下圖為HipHop運作流程:


《圖六》


轉換過程分三步驟:

1.靜態分析。收集聲明關係和依賴關係等資訊。
2.類型推演。選擇最合適的類型,是C++?還是String, Array, classes, Object或者Variant。
3.代碼生成。大部分直接將PHP語句和運算式對應為C++的語句和運算式。

HipHop在保持了PHP優點的同時,也兼得了C++的性能優勢。專案總共有30萬行代碼,5000多個單元測試。所有這些都將以PHP開源許可證形式發佈到GitHub。

Apache Thrift

Thrift源自於facebook之手,在2007年facebook提交Apache基金會將Thrift作為一個開源專案,對於當時的facebook來說創造thrift是為了解決facebook系統中各系統間大資料量的傳輸通訊以及系統之間語言環境不同需要跨平臺的特性。所以thrift可以支援多種程式語言,例如: C++, C#, Cocoa, Erlang, Haskell, Java, Ocami, Perl, PHP, Python, Ruby, Smalltalk. 在多種不同的語言之間通訊,thrift可以作為二進位的高性能的通訊中介軟體,支援資料(物件)序列化和多種類型的RPC服務。Thrift適用於程式對程式靜態的資料交換,需要先確定好他的資料結構,他是完全靜態化的,當資料結構發生變化時,必須重新編輯IDL檔,代碼生成,再編譯載入的流程,跟其他IDL工具相比較可以視為是Thrift的弱項,Thrift適用於搭建大型資料交換及存儲的通用工具,對於大型系統中的內部資料傳輸相對於JSON和xml無論在性能、傳輸大小上有明顯的優勢。

Thrift 具有自己內部定義的傳輸協定規範(TProtocol)和傳輸資料標準(TTransports),通過IDL腳本對傳輸資料的資料結構(struct) 和傳輸資料的業務邏輯(service)根據不同的運行環境快速的構建相應的代碼,並且通過自己內部的序列化機制對傳輸的資料進行簡化和壓縮提高併發、大型系統中資料交互的成本,下圖描繪了Thrift的整體架構,分為6個部分:

1.你的業務邏輯實現(Your Code)
2.用戶端和服務端對應的Service
3.執行讀寫操作的計算結果
4.TProtocol
5.TTransports
6.底層I/O通信


《圖七》


假定需要傳輸相同的內容,但使用不同的方式從1、傳輸內容所產生的大小 2、傳輸過程中服務端和用戶端所產生的開銷,這2個方便進行比較。使用Thrift和其他方式的所產生的內容大小比較結果如下:


《圖八》


在上圖中我們能明顯看出,最臃腫的是RMI,其次是xml,使用Thrift的TCompactProtocol協定和Google 的 Protocol Buffers 相差的不算太多,相比而言還是Google 的 Protocol Buffers效果最佳。

而使用Thrift 中的協定和其他方式的所產生的運行開銷比較結果如下:


《圖九》


在上圖中我們能明顯看出,最占資源是REST2中協定,使用Thrift的TCompactProtocol協定和Google 的 Protocol Buffers 相差的不算太多,相比而言Thrift的TCompactProtocol協議效果最佳。(下期待續)

參考資料

1.做出Facebook規模,你所需要的技術元件總覽, http://www.inside.com.tw/2011/04/21/facebook-platform-component

2.開放原始碼的雲端運算平台技術(1) 初探Hadoop開放原始碼平台環境, http://www.runpc.com.tw/content/cloud_content.aspx?id=105318

3.Facebook性能大提升的秘密:HipHop, http://news.csdn.net/a/20100203/216872.html

4.Apache Thrift入門1-架構&介紹, http://www.javabloger.com/article/apache-thrift-architecture.html

5.What is Facebook's architecture? http://www.quora.com/What-is-Facebooks-architecture


6.雲端運算平台—Hadoop作者:周秉誼 / 臺灣大學計算機及資訊網路中心作業管理組碩士後研究人員, http://www.cc.ntu.edu.tw/chinese/epaper/0011/20091220_1106.htm

7.Facebook談Hadoop,Hive,HBase和 A/B測試, http://www.cc.ntu.edu.tw/chinese/epaper/0011/20091220_1106.htm