# 4.4 Scaling Memcache at Facebook
## Introduction and Overview
- 對於一個有上億使用者的大型社群網路，必須做到以下幾點
- 即時的通訊
- 即時從多個來源獲取小資料整合成完整資料
- 可以存取以及更新熱門的共用內容
- 每秒可以同時服務上百萬的請求
- 此篇論文說明 Facebook 如何把原本是單節點的 memcache 做到分散式版本，並且足夠承受如此龐大的社群網路架構
- 影響作者們的研發考量
- 讀請求的數量遠大於寫請求
- 讀取可能會從各種不同引擎的資料庫獲取，有一個快取機制會比起去不同資料庫拿資料好很多
- memcache 只有提供簡單的操作：set, get, delete。不複雜的操作適合用於大型的分散式系統中
- 有以下兩種動作會存取快取
- 讀
1. 先從 cache 查看有無該資料
2. cache miss 的話，轉往 DB 拿資料
3. 把從 DB 拿到的東西寫回 cache
- 寫
1. 將資料寫進 DB
2. 寫成功後，將 cache 裡對應的資料刪除
- 作者也優化 memcache，透過 configuration, aggregation 以及 路由機制，使 memcache 更好融入分散式架構
- 對於讀到過時資料的機率設計成可調參數，用意是為了保護後端資料庫不會因為過度大量的即時更新導致出問題
- 透過不同的部署程度，關注的點也不同
- 單一集群時，著重在大量的讀取請求以及 wide fan-out (?)
- 隨著用量擴大，更多集群，著重在 data replication 問題
- 最終，探討如何讓全球的使用者具有一致性的使用者體驗，以及操作成本和容錯率
- 大致部署架構
- 一個地區有多個共同合作的集群
- 採用主僕架構，有主人地區會負責更新僕人地區的資料

## 單一集群
### 延遲
- 一個網頁請求背後可能會是上百個 memcache server 的讀取操作，因此在一個 web server 的集群裡放了很多 memcache server。
- 但一個 web server 可能會去查找所有的 memcache server 才能找到請求所需的東西，這會造成:
- incast congestion
- 最慢的 server 成為集群效能的瓶頸點
<!-- - Data replication 可以降低集群負載，但造成內存使用率低 -->
- 作者通過改進跑在每個 web server 裡的 memcache client，此 client 也會維護一個 map 表，紀錄有哪些可用的 memcache server
- Memcache client 的重點改進
- Parallel requests and batching
- 將所需資料的關係表示成 有向無環圖 (directed acyclic graph)，並行地向 memcache server 發送數據請求
- Client-server communication
- memcache client 分成兩個部分: 內部程式 sdk 以及 作為 proxy 的 mcrouter，此 proxy 當作與 memcache server 之間的抽象介面
- memcache client 也會因為不同的請求行為，使用不同的傳輸協定。
- 讀取使用 UDP，因為 UDP 比起 TCP，少了更多的連結步驟，更為輕量。並且在實驗中，只有極少量的封包(0.25%)因為順序不對或是丟包導致失敗，作者也不打算將這些失敗的封包做回覆能力，讓 memcache client 直接報錯。
- 更新及刪除使用 TCP，因為須確保資料有真的被改變，使用 TCP 更為保險。假如直接與多個 memcache server 做 TCP 連線，會消耗大量的資源，因此透過 web server 跟自己的 mcrouter 做 TCP 連線，再讓 mcrouter 去跟對應的 memcache server 做資料行為，藉此優化 TCP 連線的行為。
- 作者透過大量讀請求的實驗，顯示使用 UDP 比起 TCP，會降低 20% 的延遲
- Incast congestion
- memcache client 如果短時間發送大量 key 請求，而且這一堆回復如果一次回來，就會造成網路壅塞
- 使用 sliding window，類似於 TCP 的 congestion control，此 windows 會根據目前擁塞狀況自適應變化。越大代表越多 request，越有可能導致擁塞；越小反之，可能導致請求處理太慢，造成延遲。

### 負載
- Memcache 可以降低直接訪問 DB 的次數，但如果一直 cache miss 還是得去 DB 查找
- 提出 Leases 以應對以下兩個狀況
- 過期更新: 兩次讀取跟一個寫入並行發生，且兩次讀取都 cache miss，造成最終寫入 cache 的值可能會是舊的

        原狀況:
        假設兩個 web server， x 和 y，需要讀取同一資料 d，其執行順序如下：
        x 從 memcache 讀取資料 d，發生 cache miss，從資料庫讀出 d = A
        另一個 memcache client 將 DB 中的 d 更新為 B
        y 從 memcache 讀取資料 d，發生 cache miss，從資料庫讀出 d = B
        y 將 d = B 寫入 memcache 中
        x 將 d = A 寫入 memcache 中

- x 遭遇 cache miss 時，memcache server 會提供與 key 綁定的 lease token
- 第三者 client 更新 DB，會把 memcache 中的 key 刪除，使其 lease token 失效
- x 要把從 DB 抓回來的值寫入 memcache，但因為這之前已經有第三方 client 更新過那個 key，memcache 發現該 key 的 lease token 已經失效，變拒絕執行
- 短時間持續大量交錯讀寫: 一直 cache miss，轉向 DB 查詢
- 規定 memcache server 在一段時間後才可以再次發送 lease token，預設是 10 秒。
- 其餘想存取此 key 的 client 會先被告知等一小段時間
- 擁有此 lease token 的 client 通常在極短時間內就會將新的值寫進去，屆時其餘 client 變可以存取此 key 的新值
- 可以發現整個過程只有一次的 DB 存取而已
- (額外) 過期的值:
- 前面有提到，寫入行為會把 memcache 的 key 刪除，然而在某些應用下，可以允許獲取過期的值，此時被刪除的值會進入另一個資料結構，假如有 client 想要該值，便可直接獲取，而不用再次經歷 cache miss
- Memcache Pools
- 把 memcache 這層當作通用性 cache 的話，就代表不同的應用都共享這個 cache。
- 然而不同應用可能對於 cache 的影響有所不同，下圖為作者統計，churn 代表更新頻率，並且觀察每天以及每周結束時，兩種更新頻率的值在 cache 裡的占比。可以看到幾乎都是更新頻率高的把低的都擠出去了，這樣導致想拿低更新頻率的應用只能去DB獲取，反而降低時間
- 透過 pool 分類，將不同特性的 data 丟到不同的 memcache
- small pool: 存取頻率高且 cache miss 成本不高的
- large pool: 存取頻率低且 cache miss 成本高的
- Replication Within Pools
- 假如某個 pool 一值被存取，該 pool 可能會遇到負載上限，可以透過對整個 pool 做副本來提高效率
- 選擇整個 pool 是因為如果只是單純把一個 pool 裡的資料拆分成兩個 pool，那這樣代表 web server 就要去兩個 pool 撈東西，如果拆分越多，就要去越多地方拿，反而有機會造成增加讀取延遲。因此選擇直接副本整個 pool，但其代價是要維持 data consistency

### 處理錯誤
- 伺服器還是會遇到偶發的錯誤狀況，像是網路壞掉，或是伺服器停擺
- 如果是整個叢集壞掉了，FB 會把流量轉往另一個叢集處理
- 如果只是叢集內的少數伺服器停擺，FB 會將這些伺服器的留量轉交給 Gutter 處理
- Gutter 是比較小的叢集，平常不會使用，而是作為備用機制

## 單一區域
- 服務做大，叢集的規模也會越大。但橫向的擴充伺服器並不是解法，反而產生更多問題
- 熱門項目隨著使用者變多而越多，並且每個項目比以往更常被存取
- memcache client 要跟更多 memcache server 溝通，incast congestion 更嚴重
- 本來是把 web server 跟 memcache server 都集中於一個叢集，這次把它拆成多個前端叢集，而些多個前端叢集都存取同個 DB 叢集，此架構稱為 地區(region)
### Regional Invalidations
- 叢集變多了，就會有資料不同版本的問題。而 DB 叢集就要維護這些前端叢集裡 memcache 的資料版本
- 作者在 DB 叢集裡運行一種程序叫做 mcsqueal，負責解析資料庫收到的 sql 語句，將被更新的值廣播給所有前端叢集，讓其 memcache 刪除該對應的 key
- mcsqueal 會廣播給所有 memcache，但如果有很多 DB 叢集以及很多前端叢集，便會導致大量的封包數量，進而網路壅塞
- 那麼就直接將這堆刪除行為批次化，並將其送給 mcrouter 拆解批次包，最後由 mcrouter 將要刪除的行為路由到對應的 memcache

### Regional Pools
- 假如使用者的請求是隨機分配給任一個前端叢集，時間久了，每個 memcache server 幾乎會有相通ˊ 資料。然而對於那些不常存取的資料卻也在多個 memcache server，造成 memory 浪費的問題
- 因此把這些相對不常存取的資料，放入 regional pool
- regional pool 捨棄 replicate 的優點，一個 region 就只有一個 regional pool
- 因為一個 region 只有一個 regional pool，前端叢集就必須跨叢集來獲取此資料
- 雖然跨叢集的延遲較高，但因為此種資料存取頻率低且大小較小，反而對整體系統沒造成很多負擔

### Cold Cluster Warmup
- 當一個新的叢集上線(cold cluster)，他的 memcache 是空的，會一直 cache miss，然後就會一直去 DB 拿東西，造成暫時性的高延遲
- 讓 cold cluster 去其他已經 ready 的叢集 (warm cluster)的 memcache 把數據加載進去，讓 cold cluster 快速進入 ready 狀態
- 要注意 race condition 的狀況 (TODO)

## 跨區域
- 隨著服務更加龐大，擴及全球，開始將叢集部署在世界各地
- 將某個區域做為 master 區域，其他區域做為唯讀區域，然後仰賴 mysql 的複製能力，將 master 區域複製到其他唯讀區域。最主要問題還是 data consistency
- 使用 Remote Marker，用延遲換取不要讀到過期資料
- 要更新時，web server 把該筆資料在本地 memcache 標上 marker
- 將值更新到 master 區域的 DB，並把 marker 註記在sqlstatement
- 把本地 memcache 對應的 key 刪除，但不刪除 marker
- 後續 web server 有還想繼續讀該資料的話，發現 cache 是空的，而且有 marker 存在，他就會知道要去 master DB 拉資料。如果沒有 marker，則直接從本地 DB 拉資料
- 這邊額外提及，當 memcache 或 db 的資料刪除行為沒有回應，採用 buffer 等待的方式，直到部件正確運作

## 效能優化
### Performance Optimizations
- 主要的幾個 memcache 優化
- 優化 key-value 搜尋時間複雜度
- 從 single-thread 改進到 multi-thread，搭配全域鎖
- 每個 thread 都提供 UDP port，降低封包發送的競爭
- 比較不同 lock 的效能差別
- 作者設計的 memcache
- 套用改良的 lock
- 社群版本的 memcache
- 可以看到，透過改良的 lock，同步處理的數量大幅增加
- Get 請求的 UDP vs TCP
- UDP 減少連線成本，使用 UDP 使處理數量增加
### Adaptive Slab Allocator
- 一種對於 memcache 的記憶體管理工具，類似我們在 os 學到的 page，但是他可以動態增長，以 4-byte 為基底，最大道 1MB
- 當其塞滿了，就把最舊的(LRU)排除並重塞
### The Transient Item Cache
- 過期資料雖然可以透過 cache miss 更新或是因為 LRU 而排除，但為了更加優化記憶體效率，考慮主動剔除
- 每筆資料都加上其存活時間，並使用 circular buffer of linked lists，每秒持續往前，查看頭資料的時間，如果過期了，就直接剔除
### Software Upgrades
- 系統升級會導致 memcache server 短暫不能用，轉而導向 DB 增加延遲
- memcache server 會同時把資料儲存於 System V shared memory 區域，軟體升級時，也可以去這邊撈資料

## 效能展現
- 透過實際投入運作來呈現
### 伺服器效能
- fanout
- 一個請求會連線伺服器的數量
- 56% 的請求用不到 20 個伺服器，代表這些請求的資料只需少部分的 cache server 即可
- 但針對很熱門的請求，更好的展現此篇的 all-to-all 架構。
- Response size
- 請求的資料大小從 135 bytes ~ 954 bytes 都有，變化很大
- Latency
- 從發送請求到收到回覆的時間段
- 在 7 天內，請求延遲的中位數為 333 微秒，而第 75 和第 95 百分位數（p75 和 p95）分別為 475 微秒和 1.135 毫秒。空閒網絡服務器的端到端延遲中位數為 178 微秒，而 p75 和 p95 分別為 219 微秒和 374 微秒。
### Pool 分類比較
- wildcard: 預設 pool
- app: 給特定應用用的
- replicated: 頻繁存取
- regional: 不頻繁存取
### Invalidation Latency
- 因為 DB 更新，而要刪除 memcache 裡資料的延遲，此延遲也代表過期資料存在的時間
- 兩種比較
- master 區域發起的更新，並直接刪除 master 地區的 memcache 裡對應資料
- 唯讀區域發起的更新，並刪除其他唯讀區域的 memcache 裡對應資料
- 當然跨區域的傳送比較容易失敗，但因為此種類型的連線都是 TCP，因此當失敗時會迅速重做