閱讀筆記：Scaling Memcache at Facebook

緩存是指臨時存儲以供未來快速訪問的技術手段。從比較大的層面來看，緩存存在於計算機軟硬體的方方面面。從硬體方面來看，Cache是內存的緩存，內存是硬碟的緩存，硬碟又是遠端存儲設備（例如雲端）的緩存。在軟體層面，緩存的應用更是不計其數，包括資料庫，操作系統，分散式系統等都大量應用了緩存。

Scaling Memcache at Facebook 這邊論文主要介紹的是臉書對Memcached靈活使用，以支撐臉書處理的非常繁重的網路請求，以及存儲一些計算量大的任務的結果從而避免重複計算。

Memcached提供的是一個純內存的哈希表訪存服務，支持鍵值對的存儲模式，提供的基本介面為put, get, delete。臉書的工程師們用Memcached的實例們搭建了一個系統，叫Memcache。其基本的工作方式為：讀請求首先發送給Memcache，如果請求未命中，則查詢資料庫，查詢資料庫成功後更新Memcache。寫請求直接發送給資料庫，成功後要刪除Memcache中對應的數據。

1. 降低延遲。

由於二八定律的存在，總是少數人在創造內容而大部分人在消費內容，所以臉書的請求的大頭是讀求取，因此臉書的工程師需要對讀請求進行特別的優化。如果每次請求，無論讀寫，都直接到達資料庫層面，那麼面對每秒可能上億次的請求，資料庫層的壓力將是巨大的，解決方法也會異常的昂貴，而請求的延遲卻會很高。

利用Memcache的優化原理很簡單：將可能最近訪問的數據存入Memcache中，也即是內存中，已供未來的請求使用。如果未來的請求在Memcache中找到數據，那麼它就可以立刻返回，延遲狀況也大大的改善了。

雖然原理是很簡單的，但是實際操作起來，有多個細節需要留意。由於臉書數據量巨大，數據是利用一致性分布在Memcached的實例中的，同樣，請求也是並行分配給數量眾多的伺服器並行處理，因此每一個伺服器都能訪問所有的Memcached實例（因為某個請求需要的數據可能緩存在什麼實例）。在這種所有對所有的情況，如何保證負載均衡，如何減少連接通訊的成本，如何控制某一個Memcached實例的工作量，使得其不會崩潰或者產生高延遲是一個很重要的問題。臉書工程師的做法如下：

1）對於伺服器對Memcached連接的三種操作，get， set， delete，其中get是使用UDP進行通訊，只要set和delete才是使用可靠的TCP通訊。UDP的通訊成本顯著低於TCP，因為UDP不需要提前建立連接，也沒有諸如擁塞控制，重連等機制。在比較良好的通訊情況下，UDP的通訊失敗率（通訊失敗指丟包或者亂序包）也相對較低，論文中報告，在請求數達到峰值是，大概有0.25%的通訊失敗。失敗的UDP通訊被當成Cache miss來對待，對應的數據請求會重新傳達給資料庫。這一個技巧帶來了如下的效果：

2）伺服器端對收到的一堆請求進行有向拓撲圖分析，選出獨立的請求，將多個獨立請求進行打包，進行訪問。Batching也是降低成本的常見技巧。

3）為了避免整個系統內進行的並發請求數過高，以及單個的實例可能成為熱點，Memcache自己在連接的客戶端上設置了類似TCP的擁塞控制的方法，也就是一個滑動窗口。每次只發送窗口內的請求，並逐步滑動窗口。窗口的大小和總體延遲也有重要的關係：

從論文中的圖表可見，窗口過大過小都不可以。過大導致道路擁塞，通訊失敗增高，從而影響總體延遲。過小則導致Memcache的性能沒有完全發揮，在隊列里等待的請求過多，也影響了總體延遲。

2. 減少負荷

所謂減少負荷（reduce load），指的是儘可能減少對資料庫的訪問。資料庫的修改都是必須的，但是查詢未必是必須的，也就是資料庫查詢是有可能減少的。舉個栗子：三個讀請求同時到達Memcache，查詢的是同一個鍵，這時只需要一次資料庫查詢，然後更新Memcache對應的數據，則三個讀請求都可以返回，因此不需要三次資料庫查詢。另外，有可能因為負荷過大的原因，Memcache進行了請求數限制。超過限制的請求不得不跳過緩存層，直接去存儲層獲取數據。也就是說，提供Memcache處理並發請求的能力，也可以有效地減少資料庫的負擔。

具體技巧如下：

1）租約。所謂租約，在Memcache中，指的是當請求發生緩存未命中時，由於隨後要更新Memcache，因此在未命中的時刻，Memcache會授予客戶端一個token，用來對隨後請求的對Memcache更新做驗證。如果兩個請求對同一個鍵發生未命中，兩個請求各拿到一個token，在隨後的對Memcache的更新中，先更新的請求獲勝。（也就是鍵與token綁定了）如果一個鍵收到了刪除命令，那麼在此之前的更新的授權都會被廢除。（個人不理解為什麼這個設定可以減少負荷。猜測是這個設定能消除Memcache中的過期數據，例如某一個請求更新了資料庫，要刪除Memcache中的對應數據。但是該請求之前的某個請求讀了一個過期數據，同時嘗試將該過期數據寫入Memcache。那麼之後的請求因為在伺服器端有驗證，拒絕了從Memcache讀到的數據，導致了請求的重新執行，以及可能的資料庫直接查詢）

租約的另一個設定的好處十分容易理解。Memcache對租約的發放進行了限制，在一定時間內只發放一次。這一個設定說的就是上面的例子，三個請求只需要一次資料庫查詢，因為只有一個請求拿到了token，其它兩個請求會在稍後重試。

論文中提到，使用了租約後，在請求數達到峰值時，資料庫操作從17k/s降到了1.3k/s。

2）資源池。所謂的池，指的其實是資源的分區，對於數據中的不同的訪問模式，根據模式進行資源分區。例如緩存未命中的代價小，但是訪問頻次高的鍵放入一個小池，緩存未命中代價高，但訪問頻次低的鍵放入一個大池。

對某一個特定池，可以用數據冗餘的方式提高處理並發請求的數量。

3. 處理更大規模的請求

隨著請求規模的擴大，超出了一個集群的機器的處理能力（對於集群的概念，我的理解就是一個機架上的40台或者更多的刀片機子），那麼將Memcache擴展到多個集群就很有必要的了。注意，擴展有兩種方法，一種是更加細分鍵域，例如一個台機器負責100個鍵，但是現在將50個鍵分布到另一個機子上；另一種方法是冗餘，就是將一台機器的100個鍵拷貝一份到另一個機器。第一種方法是不可取的：它即無法解決單個熱鍵對機器帶來的超負荷，也可能增加實質請求數（例如一個請求要訪問100個鍵，之前這100個鍵都在一台機器上，現在分割到了兩台機器，那麼實質上請求多了一個，要發送兩個UDP給兩台不同的機器）。第二種方法更科學，它提供了數據冗餘，這樣可用性就提供了，單個鍵對應的主機的負擔也減輕了，但是第二種方法的代價是數據一致性。

論文中提出了區（region）的概念，一個區包含了多個運行了伺服器和Memcached實例的前端集群（Frontend Cluster)，也包含了一個共享的存儲集群（例如MySQL集群或者其它分散式資料庫/文件系統）。每一個前端集群的都存有一個完整的Memcache的數據備份，也就是每個前端集群都能用來處理相同的請求，同時也要保證所有集群數據的一致。數據一致設計是：MySQL的交易被監控，一旦有數據被刪除或者修改，且交易提交，那麼對應的Memcache鍵就被一個守護進程記錄。累積的鍵達到一定程度，就會打包發送給每一個集群內某幾台特定機子所運行的特定進程，這些進程會將刪除命令發給負責的Memcached實例。

共享區池（regional pool）。由於每一個前端集群是獨立處理髮送過來的請求的，經常一段時間的隨機的請求處理，所有前端集群緩存的數據是差不多的（大概是因為超高的請求負荷）。但是問題是有一些數據是冷數據，不常被訪問。對於這些冷數據，前端的集群如果每一個都保存一份，那麼有點得不償失。一時浪費了內存，二是浪費了集群內帶寬。解決方法是設置一個區池，把這些冷數據緩存區區池中。這樣集群本身負責響應熱數據。但是如何切割和定義冷熱數據的標準不得而知。

冷集群的熱身（cold cluster warmup）。在一個新集群上線時，由於整個集群是空的，那麼所有轉發過來的請求都會未命中。這時候如果這些請求全部去查詢資料庫，那可能直接就把資料庫衝垮了。因此有了一個設定，就是對於冷集群，它先去其它正常運行的集群去做查詢，如果命中了就不用去資料庫查了。

4. 更大的規模（基於地理的數據中心）

上面所談到的區是在某一個數據中心的。由於臉書的多個數據中心的存在，那麼實際上每一個數據中心都得有一個（或多個）區，來就近服務用戶。對於存儲來說，數據中心之間實現的是主從複製的MySQL，某一個數據中心是主，其它是從，所有寫都是發給主來處理，再傳播到從。這個是MySQL的一致性的保證過程。那麼對於建立在MySQL之上的Memcache，對於地理分割下的不同區的一致性，也得有一套保證的辦法。

分兩種情況：

1）如果是MySQL主區那裡的Memcache，工作流相對比較簡單

a. 某個前端集群收到更新，將更新發給資料庫，同時刪掉本集群的緩存記錄

b. 資料庫里的進程發現更新提交，發給其他前端集群，用於刪除緩存記錄。

c. 資料庫從主區傳播到從區，從區刪除過期的緩存記錄。

這種情況比較簡單，原因是更新發生在主區，從區的緩存過期數據只能來自於過期的資料庫的拷貝版，這種從區的過期Memcache無能為力，只能依賴於資料庫的一致性模型。

2）但是如果是從區發生了資料庫更新，就有可能發生麻煩。考慮一下的一個例子：

從區收到更新，刪除本地緩存，且將更新轉發給主區的資料庫進行更新。在主區更新完之前，從區收到了對應鍵的讀。從區緩存未命中，去從區的資料庫讀。從區資料庫依然存著過期數據，也就是過期數據被讀入從區的緩存中。從此後用戶沒有更新，也就是從區緩存會一直命中。因此對用戶而言，更新丟失。（一個極端的例子：在京東買東西，添加了一個商品進購物車，刷新發現購物車為空，然後再不停的添加，刷新，還是空。只等某一刻刷新，購物車出現了幾十個一樣的商品。用戶心想嗶了狗了）

解決這一個方法原理上不難：在從區更新時，對應的鍵加一個標記。這個標記只能主區更新完畢，傳播回從區後才能去掉。在標記存在的期間，鍵的全部緩存未命中，請求直接轉發給主區的集群。用這種犧牲延遲的方式保證最終一致性。

至此基本的點已經介紹完了。

推薦閱讀：