Memcached

memcached是一套分散式的快取系統，目前被許多軟體（如MediaWiki）所使用。這是一套開放原始碼軟體，以BSD license授權釋出。memcached的API使用三十二位元的循環冗餘校驗（CRC-32）計算鍵值後，將資料分散在不同的機器上。當表格滿了以後，接下來新增的資料會以LRU機制替換掉。由於memcached通常只是當作快取系統使用，所以使用memcached的應用程式在寫回較慢的系統時（像是後端的資料庫）需要額外的程式碼更新memcached內的資料。

將純粹使用資料庫查詢的程式碼加上memcached支援是很簡單的，假設這是原來的程式碼：

function get_foo (int userid) {
result = db_select("SELECT * FROM users WHERE userid = ?", userid);
return result;
}

加上memcached的快取機制後：

function get_foo (int userid) {
result = memcached_fetch("userrow:" + userid);
if (!result) {
result = db_select("SELECT * FROM users WHERE userid = ?", userid);
memcached_add("userrow:" + userid, result);
}
return result;
}

上述的程式會先到memcached檢查是否有userrow:userid的資料，如果有則直接傳回結果，如果不存在時再去資料庫查詢，並將結果放到memcached內。

在memcached內已經有快取資訊時將資料庫的資料更新後，上述的程式會抓到舊的資料，這是屬於Cache coherency的問題。其中一種解決的方法是在更新資料庫時，同時更新memcached內的資訊：

function update_foo(int userid, string dbUpdateString) {
result = db_execute(dbUpdateString);
if (result) {
data = createUserDataFromDBString(dbUpdateString);
memcached_set("userrow:"+userid, data);
}
}

前面有提過，Facebook的memcached大約有300TB，因此許多資料不需要再重複讀取DB，因此反應時間可以大幅提昇。

BigPipe

網頁載入的速度十分重要，尤其對於擁有遍佈全球的5億用戶的Facebook這樣的大型網站，有著同時大量請求、極大量資料等現實情況，速度就成了必須克服的難題之一。2010年初的時候，Facebook的前端性能研究小組開始了他們的優化項目，經過了六個月的努力，成功的將個人空間主頁面載入耗時由原來的5 秒減少為現在的2.5 秒。這是一個非常了不起的成就，也給用戶來帶來了很好的體驗。在優化專案中，工程師提出了一種新的頁面載入技術，稱之為Bigpipe。
面對網頁越來越大的情況，尤其是大量的css檔和js檔需要載入，傳統的頁面載入模型很難滿足這樣的需求，直接結果就是頁面載入速度變慢，這絕不是我們希望看到的。目前的技術實現中，使用者提出頁面訪問請求後，頁面的完整載入流程如下：

1.用戶訪問網頁，流覽器發送一個HTTP請求到網路服務器。
2.伺服器解析這個請求，然後從存儲層取資料，接著生成一個html檔內容，並在一個HTTP Response中把它傳送給用戶端。
3.HTTP response在網路中傳輸。
4.流覽器解析這個Response ，創建一個DOM樹，然後下載所需的CSS和JS文件。
5.下載完CSS 檔後，流覽器解析他們並且應用在相應的內容上。
6.下載完JS 後，流覽器解析和執行他們。

完整流程如上圖。圖中左側表示伺服器，右側表示流覽器。流覽器先發送請求，然後伺服器進行查找資料，生成頁面，返回html代碼，最後流覽器進行頁面的呈現。這種模式有非常明顯的缺陷：流程中的操作有著嚴格的順序，如果前面的一個操作沒有執行結束，後面的操作就不能執行，即操作之間是不能重疊。這樣就造成性能的瓶頸：伺服器生成一個頁面的內容時，流覽器是空閒的，顯示空白內容；而當流覽器載入呈現頁面內容時，伺服器又是空閒的，時間與性能的浪費由此產生。



上圖為現有的服務模型，橫軸表示花費的時間。黃色表示在伺服器的生成頁面內容的時間，白色表示網路傳輸時間，藍色表示在流覽器渲染頁面的時間。可以看出，現有的模式造成很大的時間浪費。再考慮下圖中的情況，圖中綠色表示伺服器從存儲層取查資料花費的時間，在極大量資料下，當執行一條很費時的查詢語句時（如下圖右側），伺服器就就阻塞在那裡沒有其他操作，而流覽器更是得不到任何回饋。這會造成非常不友好的用戶體驗，用戶不知道什麼原因使他們等待很長時間。



面對上述問題，我們看看BigPipe的解決辦法。BigPipe提出分塊的概念，即根據頁面內容位置的不同，將整個頁面分成不同的區塊—稱為pagelet。該技術的設計者Changhao Jiang是研究電子電路的博士，可能從微處理器上得到了啟發，將眾多pagelet載入的不同階段像流水線一樣在瀏覽器和伺服器上執行，這樣就做到了瀏覽器和伺服器的並行化，從而達到重疊伺服器端執行時間和瀏覽器端執行時間的目的。使用BigPipe不僅可以節省時間，使載入的時間縮短，而且可以同過pagelet的分步輸出，使一部分的頁面內容更快的輸出，從而獲得更好的用戶體驗。BigPipe中，使用者提出頁面訪問請求後，頁面的完整載入流程如下:

1.Request parsing：伺服器解析和檢查http request
2.Datafetching：伺服器從存儲層獲取資料
3.Markup generation：伺服器生成html 標記
4.Network transport ： 網路傳輸response
5.CSS downloading：流覽器下載CSS
6.DOM tree construction and CSS styling：流覽器生成DOM 樹，並且使用CSS
7.JavaScript downloading: 流覽器下載頁面引用的JS檔
8.JavaScript execution: 流覽器執行頁面JS代碼

這個8 個流程幾乎與上文中提到現有的模式沒有區別，但這整個流程只是一個pagelet 的完整流程，而多個pagelet 的不同操作階段就可以像流水線一樣進行執行了。



從上圖中，可以看出BigPipe對原有的模式進行的改進。流覽器發送訪問請求，然後流覽器分步返回不同的pagelet的內容，BigPipe 打破了原有的循序執行，將頁面分成不同的pagelet ，如此一來，所有的pagelet 的執行時間累加起來還是原有的時間。但是， 通過疊加不同pagelet 的不同階段的執行時間，使總執行時間大大減少，這就是Bigpipe減少頁面載入時間的秘密。

FaceBook的頁面被分成了很多不同的pagelets，如下圖：



經過上面的討論，我們可以發現，使用BigPipe技術優化頁面可以有四個好處：

1.減少頁面的載入時間。
2.使頁面分步輸出，改善用戶體驗。
3.使頁面結構化，提高可讀性，更加便於維護。
4.每個pagelet都是相互獨立的，如果有一個pagelet的內容不能載入，並不會影響其他的pagelet的內容顯示。

BigPipe 的原理非常簡單，並不會引入很多額外的負擔，適用範圍很廣，容易上手。幾乎所有的網頁都可以採用BigPipe的理念去進行優化，尤其對於是有著極大量資料和網頁較大的網站，將會以低成本帶來高回報。一般來講，網站越大，腳本和樣式表越多，流覽器版本越舊，網路環境越差，優化的結果越可觀。

Scribe

Scribe是用來收集日誌的服務器，它可以擴展到大規模的機器集群中，無論是網絡故障還是服務器節點故障，都不會對日誌收集造成影響。大規模集群系統中每個節點服務器上都運行了一個Scribe服務，這個Scribe服務器可以收集資訊然後將資訊發送到一個中央Scribe服務器(也可以是多個中央Scribe服務器)如果中央Scribe服務器(或中央服務器組)出現故障不可用的話，各個節點的Scibe服務器就會將日誌資訊寫到本地磁盤，待中央Scribe服務器恢復正常時再發送。中央Scribe服務器會將這些資訊寫檔保存到最終的磁盤位址，一般是nfs檔系統或者一個分佈式檔系統中，有時也會把這些日誌文件傳輸到其他層的Scribe服務器組中。

Scribe的獨特之處是客戶端日誌實例包含兩個字串：類別和信息(a category and a message)。類別(category)是對預期目標資訊的高層次描述，可以在Scribe服務器中進行配置，這樣就允許我們可以通過更改設定檔的方式轉移數據而不需要更改代碼。Scribe服務器也允許基於類別前綴(category prefix)進行配置，缺省狀態下可以在檔路徑中插入類別名稱，相當有靈活性和可擴展性，可通過“存儲(store)“抽象。Stores可以通過一個設定檔靜態配置，也可以在運行時無需停止服務器進行更改。

Scribe是對一個使用非阻斷C++服務器的thrift服務的實現，Facebook在上千台服務器上運行了Scribe服務，每天收集傳輸數十億的資訊。對於普通Facebook用戶而言， Scribe並無多大實際用處。但面向開源社區外公佈Scribe原始程式碼後，將有利於改變Facebook不願公佈原始程式碼的企業形象。

Haystack

Haystack是Facebook圖片管理架構，一般圖片應用系統有兩個關鍵點：

1.Metadata資訊存儲。由於圖片數量巨大，單機存放不了所有的Metadata資訊，假設每個圖片檔的Metadata佔用100位元組，260 billion圖片Metadata佔用的空間為260G * 100 = 26000GB。

2.減少圖片讀取的IO次數。在普通的Linux檔案系統中，讀取一個檔包括三次磁碟IO：讀取目錄中繼資料到記憶體，把檔的inode節點裝載到記憶體，最後讀取實際的檔內容。由於檔數太多，無法將所有目錄及檔案的inode資訊緩存到記憶體，因此磁片IO次數很難達到每個圖片讀取只需要一次磁碟IO的理想狀態。

3.圖片緩存。圖片寫入以後就不再修改，因此，需要對圖片進行緩存並且將緩存放到離用戶最近的位置，一般會使用CDN技術。

Facebook圖片系統初期的架構如下：



這個架構採用CDN作為圖片緩存，底層使用基於NAS的存儲，Photo Store Server 通過NFS掛載NAS中的圖片檔提供服務。使用者的圖片請求首先調度到最近的CDN節點，如果CDN緩存命中，直接將圖片內容返回給使用者；否則CDN請求後端的存儲系統，緩存並將圖片內容返回使用者。Facebook的經驗表明，SNS社交網站中CDN緩存的效果有限，存在大量的”長尾”請求。雖然user profile圖片請求的CDN命中率高達99.8%，但是其它圖片請求CDN命中率只有92%，大約1/10的請求最後落到了後端的存儲系統。這個架構的問題如下：

1.圖片存儲的IO次數過多。這個架構沒有解決圖片物理檔個數太多的問題，因此，無法將目錄和檔的inode資訊全部裝載到記憶體中，且後端存儲系統的訪問比較分散，很難緩存，每次圖片讀取需要多次(一般為3次)IO操作。

2.依賴于CDN提供商。Facebook使用Akamai & Limelight的CDN服務，不可控因素較多，成本也比較高。

Facebook Haystack新架構主要解決圖片存取IO次數過多的檔，主要的思路是多個邏輯檔共用同一個物理檔。Haystack架構及讀請求處理流程圖如下：



Haystack架構主要有三個部分：Haystack Directory，Haystack Store以及Haystack Cache。Haystack Store是物理存儲節點，以物理卷軸(physical volume)的形式組織存儲空間，每個物理卷軸一般很大，比如100GB，這樣10TB的資料也只有100個物理卷軸。每個物理卷軸對應一個物理檔，因此，每個存儲節點上的物理檔元資訊都很小。多個物理存儲節點上的物理卷軸組成一個邏輯卷軸(logical volume)，用於備份。Haystack Directory存放邏輯卷軸和物理卷軸的對應關係，假設每個卷軸的大小為100GB，對應關係的條數為20PB / 100GB = 0.2MB，佔用的記憶體可以忽略。Haystack cache主要用於解決對CDN提供商過於依賴的問題，提供最近增加的圖片的緩存服務。

Haystack圖片讀取請求大致流程為：使用者訪問一個頁面時，Web Server請求Haystack Directory構造一個URL：http:// / / / ，後續根據各個部分的資訊依次訪問CDN，Cache和後端的Haystack Store存儲節點。Haystack Directory構造URL時可以省略部分從而使得使用者直接請求Haystack Cache而不必經過CDN。Haystack cache收到的請求包含兩個部分：用戶Browser的請求及CDN的請求，Haystack cache只緩存用戶Browser發送的請求且要求請求的Haystack Store存儲節點是可寫的。一般來說，Haystack Store的存儲節點寫一段時間以後達到容量上限變為唯讀，因此，可寫節點的圖片為最近增加的圖片，是熱點資料。Haystack的寫請求(圖片上傳)處理流程為：Web Server首先請求Haystack Directory獲取圖片的id和可寫的邏輯卷軸，接著將資料寫入對應的每一個物理卷軸(備份數一般為3)。

HayStack的幾點優勢：

1.採用羽量級的HayStack Directory維護邏輯卷到多個物理卷的映射關係，方便的實現了副本技術，以實現系統容錯。

2.簡化檔的中繼資料結構，以追加寫的方式往物理卷中存儲圖片，效率高。同時將圖片key與位置的映射關係全部保留在記憶體中，通過一次lookup即可獲取圖片的位置。

3.物理卷中所有的圖片都對應有index檔(固定大小，結構簡單)，從而每次系統重啟時，物理卷的映射資訊能快速的通過index檔構建。

4.引入delete flag、compaction、batch upload以及進一步提高存儲的效率。

總結

Facebook所使用的相關技術，是一個綜合的結果，每一項技術都是為了處理其特殊的問題所採用或自行研發的，但彼此依然有相依性，例如Hadoop是整體分散式平臺架構，Thrift是為了解決各系統語言之間的溝通，因此Scribe, Haystack, BigPipe等技術需要互相溝通時，就會需要Thrift。下面以Facebook所提供的服務為構面，來列舉該服務用到了哪些技術：

1.前端程式採用PHP撰寫。寫完之後透過Facebook做的HipHop翻譯成C++程式碼，然後用g++來編譯。這樣的結果是前端在生成網頁以及執行網站邏輯的時候可以超快，高效能。

2.商業邏輯的元件都用Apache Thrift，以服務形式提供。撰寫語言可能是PHP, C++或是JAVA。

3.由於使用了Thrift來提供服務，運行JAVA程式碼的伺服器都是用Facebook自行研發的軟體，而不採用tomcat或Jetty這種，又再提升了些效能。

4.資料儲存的部份用了MySQL, Memcached, cassandra, 還有HBase。Memcached拿來做MySQL的暫存，也用作其他一般用途的暫存。近來，cassandra使用率有下降趨勢，而HBase在Facebook內的使用有日益提高的趨勢。

5.離線處理資料用的是Hadoop跟Hive。

6.紀錄檔，點擊數與feed等等是用Scribe來整合，並存在Scribe-HDFS裡。如果要分析，就用MapReduce。

7.為了加速瀏覽器上畫出網頁這件事，Facebook自製了BigPipe這個技術。

8.Varnish Cache用來做HTTP proxying。

9.Facebook數十億張的照片由Haystack來處理。這是Facebook自行研發的技術，低階且僅支援新增寫入動作。

10.Facebook訊息用了自己的動態叢集管理架構。商業邏輯跟儲存一併封裝成一個Cell，每個Cell處理一部份的使用者，因此使用者增加只需要增加Cell。儲存的部份用的是HBase。

11.Facebook訊息中的搜尋是透過在HBase上建立了反向索引。

12.聊天室是用Erlang開發的Epoll來完成，一樣透過Thrift服務界面來存取。

參考資料

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

2.BigPipe學習研究,http://kb.cnblogs.com/page/99459/

3.Finding a needle in Haystack: Facebook's photo storage, http://muratbuffalo.blogspot.com/2010/12/finding-needle-in-haystack-facebooks.html

4.Memcached, http://zh.wikipedia.org/wiki/Memcached

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

6.Facebook Scribe簡介, http://fan.renren.it/a/qitazonghe/other/2011/0226/78667.html

7.Facebook如何管理150億張照片http://www.bookfm.net/discussion/discussionview.html?did=100145


8.Facebook Haystack圖片儲存架構,http://www.nosqlnotes.net/archives/116

9.淺談Facebook圖片儲存系?HayStack概要, http://storage.it168.com/a2011/0515/1190/000001190566.shtml