摘要：哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。平衡性平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

標簽（空格分隔）： nosql

memcached是一個分布式，開源的數據存儲引擎。
memcached是一款高性能的分布式內存緩存服務器，通過減少查詢次數來抵消沉重緩慢的數據集或API調用、提高應用響應速度、提高可擴展性。
在高并發的場景下, 大量的讀/寫請求涌向數據庫, 此時磁盤IO將成為瓶頸, 從而導致過高的響應延遲, 因此緩存應運而生.

Memcached的工作方式是將關鍵詞和他們對應的值（最大能達到1MB）保存在一個關聯矩陣中（比如哈希表），延展和分布在大量的虛擬服務器中。

當然無論是單機緩存還是分布式緩存都有其適用場景和優缺點, 最常見的有redis和memcached. 本文主要是介紹memcached.

硬盤 --> 內存 --> 三級緩存 --> 二級緩存 --> 一級緩存

首先訪問較快的存儲介質, 如果命中且未生效則返回內容. 如果命中或失效則訪問較慢的存儲介質將內容返回同時更新緩存.

# 安裝依賴包
apt-get install libevent-dev

#安裝Memcached
wget http://memcached.org/latest
tar -zxvf memcached-1.x.x.tar.gz
cd memcached-1.x.x
./configure && make && make test && sudo make install

#啟動memcached
memcached -p 11211 -d -u root -P /tmp/memcached.pid

-P是表示使用TCP，默認端口為11211 
-d表示后臺啟動一個守護進程(daemon) 
-u表示指定root用戶啟動，默認不能用root用戶啟動 
-P表示進程的pid存放地點，此處“p”為大寫“P” 
-l，后面跟IP地址，手工指定監聽IP地址，默認所有IP都在監聽 
-m后面跟分配內存大小，以MB為單位，默認為64M 
-c最大運行并發連接數，默認為1024 
-f 塊大小增長因子，默認是1.25 
-M 內存耗盡時返回錯誤，而不是刪除項，即不用LRU算法  在64位系統中，會報libevent-1.4.so.2文件無法找到，解決辦法是把32位目錄里的同名文件鏈接至64位目錄中，即像windows那樣建立快捷方式。 Shell > /usr/local/lib/libevent-1.4.so.2 /usr/lib64/libevent-1.4.so.2 啟動后如果發現沒有端口在監聽，是因為命動命令時帶pid參數的“p”是大寫“P”，你可能寫成小寫了。

// 運行一個內存限制為1024MB的容器：

sudo docker run -name csphere-memcached -m 1024m -d -p 11211:11211 memcached:alpine

可以查看Memcached:latest 使用的 Dockerfile, 來獲取 memcached在debian下的安裝方法

# 清空memcache數據    

telnet 10.27.5.71 11211    
flush_all    
quit //退出telnet

yum -y install libmemcached.x86_64 libmemcached-devel.x86_64
 
cd /usr/src
git clone https://github.com/php-memcached-dev/php-memcached.git
cd php-memcached/
git checkout php7
/alidata/server/php/bin/phpize
./configure --with-php-config=/alidata/server/php/bin/php-config
make
make install

可以通過命令行直接管理與監控也可通過nagios等監控軟件進行監控
命令行：

// 如果在啟動時指定了IP及端口號，這里要作相應改動,連接成功后命令 
telnet 127.0.0.1 11211

Memcached利用slab allocation機制來分配和管理內存，它按照預先規定的大小，將分配的內存分割成特定長度的內存塊，再把尺寸相同的內存塊分成組，數據在存放時，根據鍵值 大小去匹配slab大小，找就近的slab存放，所以存在空間浪費現象。

傳統的內存管理方式是，使用完通過malloc分配的內存后通過free來回收內存，這種方式容易產生內存碎片并降低操作系統對內存的管理效率。

Memcached的內存管理制效率高，而且不會造成內存碎片，但是它最大的缺點就是會導致空間浪費。因為每個 Chunk都分配了特定長度的內存空間，所以變長數據無法充分利用這些空間。如圖二所示，將100個字節的數據緩存到128個字節的Chunk中，剩余的28個字節就浪費掉了。

如何避免內存浪費

預先計算出應用存入的數據大小，或把同一業務類型的數據存入一個Memcached服務器中，確保存入的數據大小相對均勻，這樣就可以減少對內存的浪費

在啟動時指定“-f"參數，能在某種程度上控制內存組之間的大小差異

在應用中使用Memcached時，通常可以不重新設置這個參數，使用默認值1.25進行部署

如果想優化Memcached對內存的使用，可以考慮重新計算數據的預期平均長度，調整這個參數來獲得合適的設置值

Memcached的緩存策略是LRU（最近最少使用）加上到期失效策略。當你在memcached內存儲數據項時，你有可能會指定它在緩存的失效時間，默認為永久。當memcached服務器用完分配的內時，失效的數據被首先替換，然后也是最近未使用的數據。在LRU中，memcached使用的是一種Lazy Expiration策略，自己不會監控存入的key/vlue對是否過期，而是在獲取key值時查看記錄的時間戳，檢查key/value對空間是否過期，這樣可減輕服務器的負載。

當空間占滿時

使用LRU算法來分配空間，刪除最近最少使用的key/value對

如果不使用LRU的話, 在啟動參數上加入”-M”, 內存耗盡時，會返回報錯信息

memcached不相互通信，那么memcached是如何實現分布式的呢？

memcached的分布式實現主要依賴客戶端的實現.

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

也就是說，存取數據分二步走，第一步，選擇服務器，第二步存取數據。

使用什么算法選擇服務器呢?

client 使用Hash算法來完成數據分散存儲.

當向memcached集群存入/取出key/value時，memcached客戶端程序根據一定的算法計算存入哪臺服務器，然后再把key/value值存到此服務器中。也就是說，存取數據分二步走，第一步，選擇服務器，第二步存取數據。

常用的算法有兩種: 余數計算分散法 和 一致性Hash算法.

標準的memcached分布式算法

CRC($key)%N

客戶端首先根據key來計算CPC, 然后結果對服務器取模得到memcached服務器節點

被匹配到的服務器無法連接時

rehash: 嘗試將連接的次數加到key后面, 重新hash

添加/移除服務器

余數計算分散發相當簡單，數據分散也很優秀

幾乎所有的緩存都會失效, 緩存重組的代價相當的大。

權重不易實現

將server的hash值分配至0~2^32的圓環上, 用同樣的方法求出存儲數值鍵的hash值并映射到圓上. 然后從數據映射到的位置開始順時針查找, 將數據存放至找到的第一臺服務器上. 如果超過0~2^32還找不到, 則將數據存放至第一臺服務器.

如果新添/刪除一臺server, 在一致性hash算法下會有什么影響?

如圖, 新添/刪除server時, 只在圓上增加服務器的逆時針方向的第一臺服務器上的鍵會受到影響。

優化一致性hash算法

一般的一致性hash算法最大限度的抑制了鍵的重新分配, 并且有的實現方式還采用了虛擬節點的思想

服務器的映射地點的分布非常的不均勻, 導致數據訪問傾斜, 大量的key被映射到同一臺服務器上.

虛擬節點: 每臺機器計算出多個hash值, 每個值對應環上的一個節點位置

key的映射方式不變, 就多了層從虛擬節點到再映射到物理機的過程

優化后: 在物理機很少的情況下, 只要虛擬節點足夠多, 也能使的key分布相對均勻. 提升了算法的平衡性.

3.5.1 是單調性(Monotonicity)

單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

3.5.2 平衡性

平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
 

hash 算法并不是保證絕對的平衡

Redis在存儲小數據時比Memcached性能更高

在100k以上的數據中，Memcached性能要高于Redis

memcached增加了網絡IO的次數和數據體積

memcached和redis對過期數據的處理

Redis是懶處理，對有有效期的數據會做有效期的標識，在指定時間會對有過期時間的數據做處理。隨機取出一部分數據，檢查是否有過期數據，如果過期數據超過25/100,則反復此過程

它使用libevent，可以應付任意數量打開的連接（使用epoll，而非poll），使用非阻塞網絡IO，分布式散列對象到不同的服務器，查詢復雜度是O(1)。

緩存命中率 = get_hits/cmd_get * 100%

一致性Hash

a. 在軟件工程的項目實戰中, 經常會遇到時間/空間的權衡, 緩存是權衡中被研究出的一種典型的技術, 而memcached又是此類技術中的佼佼者.

b. 在高并發環境下，大量的讀、寫請求涌向數據庫，此時磁盤IO將成為瓶頸，從而導致過高的響應延遲，因此緩存應運而生。

c. 本文在理解緩存基本概念的情況下介紹了memcached的分布式算法實現原理