Scaling Memcache in Facebook 筆記（三）

Scaling Memcache in Facebook 筆記（一）

Scaling Memcache in Facebook 筆記（二）

FB的數據中心分布在不同地方，互相之間數據需要保持一致性，這部分就是講在資料庫和Memcache層面保證數據正確性的。

首先，底層數據存儲用的是MySQL（跟開源版本不完全一樣，有一些Facebook自己的強化），採用Master-Slave Replication（主從複製）架構，其中一個Regional作為Master Region，接受所有的Write，然後通過MySQL本身的Replication把數據更新廣播到其他Slave Region。這是資料庫層面，簡單直接。

那麼Memcache層面呢？如果是Master Region的Write，那好辦，完全照搬之前的流程：

1. Web Server往資料庫發更新，然後invalidate local（同一個Cluster的） cache

2. 同一個Cluster的Web Server遇上cache miss會從資料庫拿新的數據然後往cache寫

但是如果是非Master Region，就不能照搬了，因為更新是往Master Region發，而這個更新可能要很久才會被廣播到當前的Region。一旦local cache被清掉，別人來讀發現cache miss了，但是新的數據還沒傳到本Region的資料庫，這時候別人就會讀本地數據里那個實際上已經過期的值往cache里寫了。這麼一寫，這個陳舊數據就可能不知道會存活到何年何月了。

要避免這種情況發生，就得保證本地cache被清掉了，但是本地資料庫還沒有最新數據的時候，要到Master Region去拿正確的數據。所以步驟如下。假如一個Web Server要更新一個key k：

1. 先在某個地方放一個標誌Rk。這個標誌的含義就是我更新數據了，但是這個更新數據還沒到我這個Region的資料庫。

2. 把k和Rk一起放在SQL里發給Master Region

3. 清掉本Cluster的k

4. Master Region收到更新後會把同樣的更新廣播到本地Region

5. 本地Region收到後負責把其他Cluster的k，和之前的標誌Rk刪掉

然後別人的讀如果發生在3之後，5之前，它就會看到Rk存在，於是它就不會去讀本地資料庫去拿數據，而是直接訪問Master Region的資料庫，這樣就能很大程度上保證讀到的數據不是過期的。

這就是大概的思路。至於實現細節，Rk是放在Regional Pool中的，被整個Regional共享（讀到這裡真是感覺人生如此巧妙，需要某個東西的時候恰好可以拿現成的東西來用，這種感覺真是太爽了）。

論文里還提到一個歷史細節：在需要擴張到多個Region之前，其實清空cache過期數據的工作其實完全是靠Web Server來乾的。前面說過Web Server跨Cluster幹這種事情已經很蛋疼了，還要跨Region就太不實際了（而且還容易發生Race condition），於是才把這部分邏輯放在後端。這個故事告訴我們系統是逐漸演變的，沒有一步到位的完美系統。

D. Single Server Improvement

這部分講的是如何提高單個伺服器的性能。

D.1 基本優化

基本的優化有三個

1) 允許Hashtable自動擴張（否則衝突太多的時候，look-up time會趨向O(n))

2) 從單線程變成多線程，通過全局鎖來保護數據結構

3) 每個線程使用單獨的埠通信

然後在此基礎上

1) 把全局鎖改成粒度更小的鎖，使得throughput提高

2) 使用UDP而不是TCP來通信，使得throughput大致提升了10%（論文做了兩個實驗，分別是8%和13%)

D.2 Slab Allocator

Slab Allocator是Memcached的內存管理模塊。它的演算法大致是：

1. 定義不同的內存塊大小(slab class)，從64 bytes等比數列一直到1M （1.07 factor)

2. 每個slab class會對應一堆預先分配的內存塊

3. 每當需要放什麼東西的時候，它會找對應大小的slab class，然後從這個class對應的內存塊里找空閑的，然後把數據塞進去。找不到就清掉沒人用的內存塊，再把數據塞進去騰出來的空間。

論文提出的修改是：動態的重新分配給每個slab class的內存。比如原來是64bytes一直都有100塊內存，1M一直都有10塊內存，都是固定的。但是，隨著workload的改變，一台Server可能早上要存的東西都是64 bytes以下的，晚上要存的東西都是0.99M的。理想狀況是，早上我們把1M的那些內存塊對應的內存分給64bytes，晚上把64bytes的內存塊對應的內存分給1M。這就是大致的演算法思路。

具體實現則是，結合之前的例子，我發現64 bytes這個class老是在騰空間給新數據，而且被清掉的數據塊的歷史，比其他slab class最沒人用的數據塊（least recently used）還要短20%，那麼我就知道64 bytes這個class內存不夠了，我就從別的slab class里找最最最least recently used的內存塊，把它resize一下分給64 bytes這個急切需要用內存的class。

D.3 Transient Item Cache

Memcached在清cache的時候是很拖延症的——不到滿了都不清。在大部分情況下，這是沒問題的。但是，有一部分key，只在很短的一段時間之內有用，之後根本不會被用到，但它們還是會在cache呆著，占著內存（請想像一個人在廁所賴著不出來直到下一個人來的情況），直到它們到了eviction隊列尾端。

其實問題不大，但就是看它們不爽，那麼怎麼清掉呢？方法是對於expiration time比較短的key，把他們放到另外一個數據結構了，然後過一段時間check一下，有過期的就主動把它刪掉，即使內存還沒滿。

D.4 Software Upgrade

我們每更新一次軟體都要重啟Server，然後要等一段時間cache才能滿上數據。解決辦法是更新前把cached的數據放到某個地方（System V Shared Memory Region，我也不知道是啥。。。)，然後這部分數據之後就可以接著用了。

==================================================================

論文最後還提到一些數據分析，大家感興趣的話可以找原文看。

引用：

Scaling Memcache at Facebook (Paper)

推薦閱讀：