基于MemCache的分布式擴展算法

齊建軍

摘要：隨著近些年來互聯網的高速發展，每天產生的數據量也隨之不斷增大，對于網站訪問速度的要求不斷提高，傳統的關系型數據庫不能夠滿足當前的需求。因此我們引入NoSQL數據庫，即基于Key-Value模型的緩存關系數據庫，用于提高網站的讀寫效率和訪問速度。該文著重討論基于MemCache的分布式擴展算法來進行研究，實驗證明，選取合理的分布式算法，將會進一步大大的提升網站的穩定性和高可用性。

關鍵詞：數據緩存；NoSQL；分布式算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）28-0018-02

1 概述

隨著web2.0網站的興起以及近些年來移動互聯網的大爆發，傳統的關系型數據庫已經不能夠滿足數據的高并發讀寫、高效率存儲和訪問以及高可用性等需求，于是非關系型數據庫（NoSQL）的出現成為了解決這些問題的有效手段。

針對數據庫高并發的讀寫的需求[1]，網站需要提供實時的動態頁面和信息，如果使用傳統的關系型數據庫，并發負載明顯偏高，達到每秒上萬次的讀寫請求。關系型數據庫可以應對多次SQL查詢，但對于寫數據請求，硬盤的IO就顯得力不從心了。

在網站架構升級的過程中發現，隨著用戶數量和網站訪問量的不斷增加，我們的數據庫卻無法像應用層的業務邏輯一樣，簡單的以添加服務器和服務節點的方法擴展負載能力和總體性能。尤其對于那些支付網站以及對系統實時性要求比較高的網站來說，對數據庫進行升級以及遷移是一件非常麻煩的事情，而且我們在遷移的過程中，要保證用戶對此操作是沒有任何感知的，這顯然對傳統的數據庫來說，通過添加服務器節點來實現擴展幾乎是不可能的[2]。

為有效解決傳統關系型數據庫的缺陷，使用NoSQL數據庫進行替代。當前業內比較流行的NoSQL的數據庫產品主要包括MemCache，Redis和MongoDB等，這三種NoSQL數據庫用的比較多，也是性能比較不錯的三款NoSQL數據庫。在本文中，將重點討論MemCache分布式存儲數據的相關算法。

2 基于MemCache的介紹

MemCache是一個高性能的分布式的內存對象緩存系統。通過在內存里維護一個統一的巨大的hash表，并且能夠存儲各種格式的數據[3]。它是DangaInteractive公司研發的一款軟件。初期只是為了用來提高自己公司網站的訪問速度，目前已經成為了mixi、hatena、Facebook、Vox、LiveJournal等網站用來提高Web應用擴展性的一款產品。

相比傳統的Web應用過程，是把數據保存在RDBMS中，服務器從RDBMS中讀取數據，進行數據處理后在顯示于瀏覽器中。但是，如果數據量增大亦或訪問集中，必然使得RDBMS的負擔加重，數據庫響應變得緩慢，最終導致系統響應延遲增加。

采用MemCache可以有效解決這個問題，目的就是通過緩存數據庫的查詢命中來減少數據庫壓力，提高響應速度和可擴展性。

如下圖示，為常見的MemCache的緩存應用示意圖：

從上圖，我們不難看出，當客戶端過來取數據的時候，首先是從緩存中查詢數據，如果沒有的話，才會到數據庫中查詢數據，最終將數據返回給客戶端，并且存入到緩存中，以供下一次查詢使用。

3 MemCache的分布式原理

MemCache是“分布式”緩存服務器，可是其服務器端并不具備分布式功能。各個服務器之間不會相互通信來共享信息。如何進行分布完全取決于客戶端（嚴格的說是取決于分布式算法如何選擇）的實現，因此也稱為基于客戶端的分布式。

一般有兩種實現分布式的算法：

3.1 余數取余算法

余數計算分散法是標準的MemCache分布式方法，客戶端根據key計算CRC，對服務器數進行取模，最終得到MemCache服務器節點。

這種方法的缺點是在添加或者移除服務器的時候，緩存重組的代價比較大。

3.2 一致性哈希算法

為了解決余數取余算法添加或者移除服務器帶來的性能問題，我們使用一致性哈希算法來解決。

具體的步驟如下：

（1） 使用crc32算法算出每個服務節點的hash值，并將每個值映射到一個0～2^32的圓環上。我們稱這個圓環為一個值域。

（2） 使用同樣的算法算出要存入的每個key的hash值，也將其配置到這個圓環上。

（3） 接下來從數據映射的位置開始順時針查找，將數據保存在尋找到的第一個服務器上，倘若超過0～2^32仍然找不到，結果將會保存在第一個服務器中。

如果移除或者添加一臺服務器會出現什么情況？

我們發現，當添加node5節點后，node5被放在了node4和node2之間，原本映射到node2和node4之間的區域都會找到node4，如果存在node5，node5和node4之間的仍然找到node4，而在node5和node2之間的則會找到node5，也就是說，添加一臺服務器時，受影響的僅僅是node5和node2區間。

3.3 優化一致性hash算法[4]

從上面的例子中，我們發現一致性hash最大限度的抑制了鍵的重新分配，但是有的時候，我們在計算服務器或者key的hash值時，如果使用一般函數進行處理的話，服務器的映射節點會非常的不均勻，從而導致緩存存儲傾斜，大量的key被映射到同一臺服務器上。為了避免這個問題發生，因此上引入虛擬節點的機制。具體做法就是為每一個服務器計算出多個hash值，每個計算值對應環上的一個節點位置，這種節點即是虛擬節點。使用虛擬節點，當某個節點移除后，跟這個節點關聯的相應虛節點也會移除，但我們發現，數據分布并沒有因為此節點的移除而大面積的崩潰。

4 結束語

分布式數據緩存模式越來越被國內的大型互聯網公司以及中型公司應用，大規模的企業級應用可以用集群來保證。數據緩存可以減少數據庫的訪問壓力，提高數據命中率，而相應的分布式模式可以均衡服務器的壓力，減少業務邏輯對底層服務的訪問，從而進一步提高系統的性能。

參考文獻：

[1] 黃賢立.NoSQL 非關系型數據庫的發展及應用初探[J].福建電腦，2010（7）：30-45.

[2] 謝毅.NoSQL.非關系型數據庫綜述[J].先進技術研究通報，2010，4（8）：46-50.

[3] 宗小中.基于Memcached構建Web緩存服務器[J].電腦知識與技術，2011，7（5）：1-4.

[4] 潘金貴.Cormen TH.算法導論[M].北京：機械工業出版社，2006.endprint