memcached分散式實現原理

架構師(JiaGouX)我們都是架構師!

摘要

在高並發環境下,大量的讀、寫請求湧向資料庫,此時磁碟IO將成為瓶頸,從而導致過高的響應延遲,因此緩存應運而生。無論是單機緩存還是分散式緩存都有其適應場景和優缺點,當今存在的緩存產品也是數不勝數,最常見的有redis和memcached等,既然是分散式,那麼他們是怎麼實現分散式的呢?本文主要介紹分散式緩存服務mencached的分散式實現原理。

緩存本質

計算機體系緩存

什麼是緩存,我們先看看計算機體系結構中的存儲體系,根據馮·諾依曼計算機體系結構模型,計算機分為五大部分:運算器、控制器、存儲器、輸入設備、輸出設備。結合現代計算機,CPU包含運算器和控制器兩個部分,CPU負責計算,其需要的數據由存儲提供,存儲分為幾個級別,就拿我當前的PC舉個例子,我的機器存儲清單如下:

  1. 356G的磁碟

  2. 4G的內存

  3. 3MB三級緩存

  4. 256KB二級緩存(pre core)

除了上述部分,還有CPU內的寄存器,當然有的計算機還有一級緩存等。CPU運算器工作的時候需要數據,數據哪裡來?首先從距離CPU最近的二級緩存去拿,這塊緩存速度最快,通常也是體積最小,因為價格最貴:

存儲金字塔

如上圖所示,存儲體系就像個金子塔,最上層最快,價格最貴,最下層最

慢,價格也最便宜,CPU的數據源優先順序一層層從上到下去尋找數據。

很顯然,除了最慢的那塊存儲,在計算機體系中,相對較快的那些存儲都可以被稱為緩存,他們解決的問題是讓存儲訪問更快。

緩存應用系統

計算機體系存儲系統模型擴展到應用也是一樣,應用需要數據,數據哪裡來?緩存(更快的存儲)->DB(較慢的存儲),他們的工作流程大致如下圖所示:

帶緩存的存儲訪問一般模型

如上圖所示,緩存應用系統一般存儲訪問流程:首先訪問緩存較快的存儲介質,如果命中且未失效則返回內容,如果未命中或失效則訪問較慢的存儲介質將內容返回同時更新緩存。

memcached簡介

什麼是memcached

memcached是LiveJournal旗下的Danga Interactive公司的Brad Fitzpatric為首開發的一款軟體。現在已經成為mixi、hatena、Facebook、Vox、LiveJournal等眾多服務中提高Web應用擴展性的重要因素。傳統的Web應用都將數據保存到RDBMS中,應用伺服器從RDBMS中讀取數據、處理數據並在瀏覽器中顯示。但是隨著數據量增大、訪問的集中、就會出現RDBMS的負擔加重、資料庫響應變慢、導致整個系統響應延遲增加。

而memcached就是為了解決這個問題而出現的,memcached是一款高性能的分散式內存緩存伺服器,一般目的是為了通過緩存資料庫的查詢命中減少資料庫壓力、提高應用響應速度、提高可擴展性。

memcached緩存應用

memcached緩存特點

  1. 協議簡單

  2. 基於libevent的事件處理

  3. 內置內存存儲方式

  4. memcached不相互通信的分散式

memcached分散式原理

今天的內容主要涉及memcached特點的第四條,memcached不相互通信,那麼memcached是如何實現分散式的呢?memcached的分散式實現主要依賴客戶端的實現:

memcached分散式

如上圖所示,我們看下緩存的存儲的一般流程:

當數據到達客戶端,客戶端實現的演算法就會根據「鍵」來決定保存的memcached伺服器,伺服器選定後,命令他保存數據。取的時候也一樣,客戶端根據「鍵」選擇伺服器,使用保存時候的相同演算法就能保證選中和存的時候相同的伺服器。

餘數計算分散法

餘數計算分散法是memcached標準的memcached分散式方法,演算法如下:

CRC($key)%N

該演算法下,客戶端首先根據key來計算CRC,然後結果對伺服器數進行取模得到memcached伺服器節點,對於這種方式有兩個問題值得說明一下:

  1. 當選擇到的伺服器無法連接的時候,一種解決辦法是將嘗試的連接次數加到key後面,然後重新進行hash,這種做法也叫rehash。

  2. 第二個問題也是這種方法的致命的缺點,儘管餘數計算分散發相當簡單,數據分散也很優秀,當添加或者移除伺服器的時候,緩存重組的代價相當大。

Consistent Hashing演算法

Consistent Hashing演算法描述如下:首先求出memcached伺服器節點的哈希值,並將其分配到0~2^32的圓上,這個圓我們可以把它叫做值域,然後用同樣的方法求出存儲數據鍵的哈希值,並映射到圓上。然後從數據映射到的位置開始順時針查找,將數據保存到找到的第一個伺服器上,如果超過0~2^32仍找不到,就會保存在第一台memcached伺服器上:

memcachd基本原理

再拋出上面的問題,如果新添加或移除一台機器,在consistent Hashing演算法下會有什麼影響。上圖中假設有四個節點,我們再添加一個節點叫node5:

添加了node節點之後

node5被放在了node4與node2之間,本來映射到node2和node4之間的區域都會找到node4,當有node5的時候,node5和node4之間的還是找到node4,而node5和node2之間的此時會找到node5,因此當添加一台伺服器的時候受影響的僅僅是node5和node2區間。

優化的Consistent Hashing演算法

上面可以看出使用consistent Hashing最大限度的抑制了鍵的重新分配,且有的consistent Hashing的實現方式還採用了虛擬節點的思想。問題起源於使用一般hash函數的話,伺服器的映射地點的分布非常不均勻,從而導致資料庫訪問傾斜,大量的key被映射到同一台伺服器上。為了避免這個問題,引入了虛擬節點的機制,為每台伺服器計算出多個hash值,每個值對應環上的一個節點位置,這種節點叫虛擬節點。而key的映射方式不變,就是多了層從虛擬節點再映射到物理機的過程。這種優化下儘管物理機很少的情況下,只要虛擬節點足夠多,也能夠使用得key分布的相對均勻。

總結

本文介在理解緩存基本概念的情況下介紹了memcached的分散式演算法實現原理,memcached的分散式是由客戶端函數庫實現的。

來源:oschina


推薦閱讀:

陳天橋與盛大的18年:除了被馬化騰實現的舊夢,還埋葬了哪些?
重磅消息,EXCEL也能實現一對多查找了!VLOOKUP COUNTIF實現一對多查找案例教程!
通州副中心將投千億建設 預定2017年實現辦公
乾貨:七大法則實現完美現場調音
三種觀察者模式的C#實現

TAG:分散式 | 原理 | 實現 |