寫在前面： 前不久在工作中被問到關于MC一致哈希的問題，由于時隔太久差點兒忘記，特前來惡補一下MC，下面是前幾年在工作中學習MC時的一些資料，來歷不明，特整理一下，希望對大家的學習也能有幫助。

關于memcache的安裝，有興趣的朋友請參考這篇文章： http://blog.csdn.net/xifeijian/article/details/22000173

1、memcached 介紹

1.1 memcached 是什么？

memcached 是以LiveJournal 旗下Danga Interactive 公司的Brad Fitzpatric 為首開發的一款軟件。如今已成為mixi、hatena、Facebook、Vox、LiveJournal 等眾多服務中提高Web

應用擴展性的重要因素。很多Web 應用都將數據保存到RDBMS 中，應用server從中讀取數據并在瀏覽器中顯示。但隨著數據量的增大、訪問的集中，就會出現RDBMS 的負擔加重、數據庫響應惡化、站點顯示延遲等重大影響。這時就該memcached 大顯身手了。memcached 是高性能的分布式內存緩存server。一般的使用目的是，通過緩存數據庫查詢結果，降低數據庫訪問次數，以提高動態Web 應用的速度、提高可擴展性。

內置內存存儲方式

為了提高性能，memcached 中保存的數據都存儲在memcached 內置的內存存儲空間中。由于數據僅存在于內存中，因此重新啟動memcached、重新啟動操作系統會導致全部數據消失。另外，內容容量達到指定值之后，就基于LRU(Least Recently Used)算法自己主動刪除不使用的緩存。memcached 本身是為緩存而設計的server，因此并沒有過多考慮數據的永久性問題

memcached 不互相通信的分布式

memcached 盡管是 “ 分布式 ” 緩存server，但server端并沒有分布式功能。各個

memcached 不會互相通信以共享信息。那么，如何進行分布式呢？這全然取決于client的實現。

2.2 memcached 啟動

memcached 啟動的命令在安裝文件夾的bin 二級文件夾下，如/home/test/app/memcahced-1.4.2/bin/memcached -p 11222 -m 128 – d

經常使用的一些啟動選項介紹選項說明

-p 偵聽的端口，默覺得11211

-m 使用內存大小，默認的64m

-d 作為daemon 在后臺啟動

-vv 用very vrebose 模式啟動，調試信息和錯誤輸出到控制臺

-l 偵聽的地址，默覺得全部能夠訪問的地址

-M 用于在內存溢出的時候，返回一個錯誤，禁止自己主動的移出數

據，替代的是返回一個error

-P Pid 文件存在的路徑，僅限加上-d 參數是用

-c 最大同一時候的連接數，默覺得1024

其它的一些選項，能夠通過 – h 命令來進行查看

2.3 命令行訪問 memcached

下面假設memcached 啟動時的-p 參數為11311，命令操作在啟動memcached

本機首先telnet 連接到memcached server

telnet 127.0.0.1 11311

telnet 成功之后，大概會顯示下面的信息

Trying 127.0.0.1...

Connected to localhost.localdomain (127.0.0.1).

Escape character is '^]'.

?

各種狀態（ stats ）

STAT <name> <value>\r\n

如：stats 命令，則返回下面信息：

stats
STAT pid 26804
STAT uptime 182783
STAT time 1404973716
STAT version 1.4.13
STAT libevent 2.0.11-stable
STAT pointer_size 64
STAT rusage_user 2.320647
STAT rusage_system 5.411177
STAT curr_connections 34
STAT total_connections 558
STAT connection_structures 37
STAT reserved_fds 20
STAT cmd_get 127292
STAT cmd_set 60056
STAT cmd_flush 145
STAT cmd_touch 0
STAT get_hits 83811
STAT get_misses 43481
STAT delete_misses 15970
STAT delete_hits 11992
STAT incr_misses 0
STAT incr_hits 0
STAT decr_misses 0
STAT decr_hits 0
STAT cas_misses 0
STAT cas_hits 0
STAT cas_badval 0
STAT touch_hits 0
STAT touch_misses 0
STAT auth_cmds 0
STAT auth_errors 0
STAT bytes_read 14300156
STAT bytes_written 11507140
STAT limit_maxbytes 134217728 ? ??? # ?分配給memcache的內存大?。ㄗ止潱?
STAT accepting_conns 1
STAT listen_disabled_num 0
STAT threads 4
STAT conn_yields 0
STAT hash_power_level 16
STAT hash_bytes 524288
STAT hash_is_expanding 0
STAT expired_unfetched 16884
STAT evicted_unfetched 0
STAT bytes 609350 ?? ?# 當前server存儲items占用的字節數
STAT curr_items 4668 ??? # server當前存儲的items數量
STAT total_items 60056
STAT evictions 0 ? ?? # 分配給memcache的空間用滿后須要刪除舊的items數，踢出。
STAT reclaimed 27160 ?#回收再利用，已過期的數據條目來存儲新數據。
END

?

存儲命令（ set ,add ,replace ）

client會發送一行像這樣的命令：

<command name> <key> <flags> <exptime> <bytes>\r\n

如：

set key1 0 600 5\r\nvalue\r\n

add key2 0 500 2\r\n

replace key1 0 600 6\r\nvalue1\r\n

具體的命令說明，能夠見附錄的memcached 中英文協議內容

?

讀取命令（get ）

命令例如以下：get <key>*\r\n

- <key>* 表示一個或多個鍵值，由空格隔開的字串

如：

get key1

VALUE key1 0 7

value12

?

刪除命令（ delete ）

命令如：delete <key> <time>\r\n

<key> 是client希望server刪除的內容的鍵名

- <time> 是一個單位為秒的時間（或代表直到某一刻的Unix 時間），在該時間內server會拒絕對于此鍵名的 “ add ” 和 “ replace ” 命令。此時內容被放入delete 隊列，無法再通過 “ get ” 得到該內容，也無法是用 “ add ” 和 “ replace ” 命令（可是 “ set ” 命令可用）。直到指定時間，這些內容被終于從server的內存中徹底清除

<time> 參數是可選的，缺省為0 （表示內容會立馬清除，并且隨后的存儲命令均可用

如：delete key1

退出命令 (quit)

如： quit

4、理解memcached 的內存存儲

4.1Slab Allocation 機制：整理內存以便反復使用

近期的memcached 默認情況下採用了名為Slab Allocator 的機制分配、管理內存。在該機制出現以前，內存的分配是通過對全部記錄簡單地進行malloc和free 來進行的?？墒?，這樣的方式會導致內存碎片，加重操作系統內存管理器的負擔，最壞的情況下，會導致操作系統比memcached 進程本身還慢。 Slab Allocator 就是為解決該問題而誕生的

Slab Allocation 的原理相當簡單。將分配的內存切割成各種尺寸的塊

（chunk），并把尺寸同樣的塊分成組（chunk 的集合）

并且， slab allocator 還有反復使用已分配的內存的目的。 也就是說， 分配到的內存不會釋放，而是反復利用。

Slab Allocation 的主要術語

Page

分配給Slab 的內存空間，默認是1MB。 分配給Slab 之后依據slab 的大小切分成chunk 。

Chunk

用于緩存記錄的內存空間。

Slab Class

特定大小的chunk 的組

4.2 在 Slab 中緩存記錄的原理

memcached 依據收到的數據的大小，選擇最適合數據大小的slab，memcached 中保存著slab 內空暇chunk 的列表，依據該列表選擇chunk，然

后將數據緩存于當中

4.3 Slab Allocator 的缺點

由于分配的是特定長度的內存，因此無法有效利用分配的內存。比如，將100 字節的數據緩存到128 字節的chunk 中，剩余的28字節就浪費了

對于該問題眼下還沒有完美的解決方式，但在文檔中記載了比較有效的解決方式。就是說，假設預先知道client發送的數據的公用大小，或者僅緩存大小同樣的數據的情況下，僅僅要使用適合數據大小的組的列表，就能夠降低浪費?？墒欠浅＿z憾，如今還不能進行不論什么調優，僅僅能期待以后的版本號了。可是，我們能夠調節slab class 的大小的區別。接下來說明growth factor 選項。

?

4.4 使用 Growth Factor 進行調優

memcached 在啟動時指定Growth Factor 因子（通過f 選項），就能夠在某種程度上控制slab 之間的差異。默認值為1.25。 可是，在該選項出現之前，這個因子以前固定為2，稱為 “ powers of 2 ” 策略。

下面是啟動后的verbose 輸出：

slab class 1: chunk size 128 perslab 8192

slab class 2: chunk size 256 perslab 4096

slab class 3: chunk size 512 perslab 2048

slab class 4: chunk size 1024 perslab 1024

slab class 5: chunk size 2048 perslab 512

slab class 6: chunk size 4096 perslab 256

slab class 7: chunk size 8192 perslab 128

slab class 8: chunk size 16384 perslab 64

slab class 9: chunk size 32768 perslab 32

slab class 10: chunk size 65536 perslab 16

slab class 11: chunk size 131072 perslab 8

slab class 12: chunk size 262144 perslab 4

slab class 13: chunk size 524288 perslab 2

可見，從128 字節的組開始，組的大小依次增大為原來的2 倍。這樣設置的問題是，slab 之間的區別比較大，有些情況下就相當浪費內存。因此，為盡量降低內存浪費，兩年前追加了growth factor 這個選項來看看如今的默認設置（f=1.25）時的輸出（篇幅所限，這里僅僅寫到第10 組）：

slab class 1: chunk size 88 perslab 11915

slab class 2: chunk size 112 perslab 9362

slab class 3: chunk size 144 perslab 7281

slab class 4: chunk size 184 perslab 5698

slab class 5: chunk size 232 perslab 4519

slab class 6: chunk size 296 perslab 3542

slab class 7: chunk size 376 perslab 2788

slab class 8: chunk size 472 perslab 2221

slab class 9: chunk size 592 perslab 1771

slab class 10: chunk size 744 perslab 1409

可見，組間差距比因子為2 時小得多，更適合緩存幾百字節的記錄。從上面的輸出結果來看，可能會覺得有些計算誤差，這些誤差是為了保持字節數的對齊而有益設置的。將memcached 引入產品，或是直接使用默認值進行部署時，最好是又一次計算一下數據的預期平均長度，調整growth factor，以獲得最恰當的設置。內存是珍貴的資源，浪費就太可惜了。

5、memcached 刪除機制

memcached 是緩存，不須要永久的保存到server上，本章介紹memcache 的刪除機制

5.1 memcached 在數據刪除方面有效的利用資源

Memcached 不會釋放已經分配的內存，記錄過期之后，client無法再看到這一條記錄，其存儲空間就能夠利用。

Lazy Expiration

memcached 內部不會監視記錄是否過期，而是在get 時查看記錄的時間戳，檢查記錄是否過期。這樣的技術被稱為lazy（惰性）expiration。因此，memcached不會在過期監視上耗費CPU 時間

5.2 LRU ：從緩存中有效刪除數據的原理

memcached 會優先使用已超時的記錄的空間，但即使如此，也會發生追加新記錄時空間不足的情況，此時就要使用名為Least Recently Used（LRU）機制來分配空間。顧名思義，這是刪除 “ 近期最少使用 ” 的記錄的機制。因此，當memcached 的內存空間不足時（無法從slab class 獲取到新的空間時），就從近期未被使用的記錄中搜索，并將其空間分配給新的記錄。從緩存的有用角度來看，該模型十分理想。只是，有些情況下LRU 機制反倒會造成麻煩。memcached 啟動時通過 “ M ” 參數能夠禁止LRU，例如以下所看到的：

$ memcached -M – m 1024

啟動時必須注意的是，小寫的 “ m ” 選項是用來指定最大內存大小的。不指定具體數值則使用默認值64MB。

指定 “ M ” 參數啟動后，內存用盡時memcached 會返回錯誤。話說回來，memcached 畢竟不是存儲器，而是緩存，所以推薦使用LRU

6、memcached 的分布式算法

6.1memcached 的分布式

memcached 盡管稱為 “ 分布式 ” 緩存server，但server端并沒有 “ 分布式 ” 功能。memcached 的分布式，則是全然由client程序庫實現的。這樣的分布式是memcached 的最大特點

memcached 的分布式是什么意思？

下面假設memcached server有node1～node3 三臺，應用程序要保存鍵名為 “ tokyo ” 、 “ kanagawa ” 、 “ chiba ” 、 “ saitama ” 、 “ gunma ” 的數據

首先向memcached 中加入 “ tokyo ” 。將 “ tokyo ” 傳給client程序庫后，client實現的算法就會依據 “ 鍵 ” 來決定保存數據的memcached server。server選定后，即命令它保存 “ tokyo ” 及其值

同樣， “ kanagawa ” 、 “ chiba ” 、 “ saitama ” 、 “ gunma ” 都是先選擇server再保接下來獲取保存的數據。獲取時也要將要獲取的鍵 “ tokyo ” 傳遞給函數庫。函數庫通過與數據保存時同樣的算法，依據 “ 鍵 ” 選擇server。使用的算法同樣，就能選中與保存時同樣的server，然后發送get 命令。僅僅要數據沒有由于某些原因被刪除，就能獲得保存的值。

這樣，將不同的鍵保存到不同的server上，就實現了memcached 的分布式。memcached server增多后，鍵就會分散，即使一臺memcached server發生問題無法連接，也不會影響其它的緩存，系統依舊能繼續執行

6.2 余數分布式算法

就是 “ 依據server臺數的余數進行分散 ” 。求得鍵的整數哈希值，再除以server臺數，依據其余數來選擇server

余數算法的缺點

余數計算的方法簡單，數據的分散性也相當優秀，但也有其缺點。那就是當加入或移除server時，緩存重組的代價相當巨大。加入server后，余數就會產生巨變，這樣就無法獲取與保存時同樣的server，從而影響緩存的命中。

6.3Consistent Hashing（一致哈希）

知識補充：哈希算法，即散列函數。將隨意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。假設散列一段明文并且哪怕僅僅更改該段落的一個字母，隨后的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數據的哈希值能夠檢驗數據的完整性。一般用于高速查找和加密算法。（常見的有MD5，SHA-1）

Consistent Hashing 的簡單說明

Consistent Hashing 例如以下所看到的：首先求出memcached server（節點）的哈希值（一般的方法能夠使用 cache 機器的 IP 地址或者機器名作為 hash 輸入。），并將其配置到0～ 2 ³² 的圓（continuum）上。然后用同樣的方法求出存儲數據的 鍵 的哈希值，并映射到圓上。然后從數據映射到的位置開始順時針查找，將數據保存到找到的第一個server上。假設超過 2 ³² 仍然找不到server，就會保存到第一臺memcached server上。

從上圖的狀態中加入一臺memcached server。余數分布式算法由于保存鍵的server會發生巨大變化，而影響緩存的命中率，但Consistent Hashing中，僅僅有在continuum 上添加server的地點逆時針方向的第一臺server上的鍵會受到影響

?Consistent hashing 的基本思想就是將對象和 cache 都映射到同一個 hash 數值空間中，并且使用同樣的 hash 算法。

如今 cache 和對象都已經通過同一個 hash 算法映射到 hash 數值空間中了，接下來要考慮的就是如何將對象映射到 cache 上面了。

在這個環形空間中，假設沿著順時針方向從對象的 key 值出發，直到遇見一個 cache ，那么就將該對象存儲在這個 cache 上，由于對象和 cache 的 hash 值是固定的，因此這個 cache 必定是唯一和確定的。這樣不就找到了對象和 cache 的映射方法了嗎？

Consistent Hashing ：加入server

因此，Consistent Hashing 最大限度地抑制了鍵的又一次分布。并且，有的Consistent Hashing 的實現方法還採用了虛擬節點的思想。使用一般的hash函數的話，server的映射地點的分布非常不均勻。因此，使用虛擬節點的思想，為每一個物理節點（server）在continuum上分配100～200 個點。這樣就能抑制分布不均勻，最大限度地減小server增減時的緩存又一次分布。

通過上文中介紹的使用Consistent Hashing 算法的memcached client函數庫進行測試的結果是，由server臺數（n）和添加的server臺數（m）計算添加server后的命中率計算公式例如以下：

(1 n/(n+m)) * 100

存儲命令

<command name> <key> <flags> <exptime> <bytes>\r\n

- <command name> 是set, add, 或者repalce

- <key> 是接下來的client所要求儲存的數據的鍵值

- <flags> 是在取回內容時，與數據和發送塊一同保存server上的隨意16 位無符號整形（用十進制來書寫）。client能夠用它作為 “ 位域 ” 來存儲一些特定的信息；它對server是不透明的。

- <exptime> 是終止時間。假設為0 ，該項永只是期(盡管它可能被刪除，以便為其它緩存項目騰出位置)。假設非0（Unix 時間戳或當前時刻的秒偏移），到達終止時間后，client無法再獲得這項內容。

- <bytes> 是隨后的數據區塊的字節長度，不包含用于分野的 “ \r\n ” 。它能夠是0 （這時后面尾隨一個空的數據區塊）。

- <data block> 是大段的8 位數據，其長度由前面的命令行中的<bytes>指定。

?

? set 意思是 “ 儲存此數據 ”

? add 意思是 “ 儲存此數據，僅僅在server* 未*保留此鍵值的數據時 ”

? replace 意思是 “ 儲存此數據，僅僅在server* 曾*保留此鍵值的數據時 ”

?

發送命令行和數據區塊以后，client等待回復，可能的回復例如以下：

- "STORED\r\n" 表明成功.

- "NOT_STORED\r\n" 表明數據沒有被存儲，但不是由于錯誤發生。這通常意味著add 或replace 命令的條件不成立，或者，項目已經位列刪除隊列（參考后文的 “ delete ” 命令）。

?

取回命令

get <key>*\r\n

- <key>* 表示一個或多個鍵值，由空格隔開的字串這行命令以后，client的等待0 個或多個項目，每項都會收到一行文本，然后跟著數據區塊。全部項目傳送完成后，server發送下面字串："END\r\n"來指示回應完成,server用下面形式發送每項內容：

VALUE <key> <flags> <bytes>\r\n

<data block>\r\n

- <key> 是所發送的鍵名

- <flags> 是存儲命令所設置的記號

- <bytes> 是隨后數據塊的長度，* 不包含* 它的界定符 “ \r\n ”

- <data block> 是發送的數據

假設在取回請求中發送了一些鍵名，而server沒有送回項目列表，這意味著server沒這些鍵名（可能由于它們從未被存儲，或者為給其它內容騰出空間而被刪除，或者到期，或者被已client刪除）。

?

刪除

delete <key> <time>\r\n

- <key> 是client希望server刪除的內容的鍵名

- <time> 是一個單位為秒的時間（或代表直到某一刻的Unix 時間），在該時間內server會拒絕對于此鍵名的 “ add ” 和 “ replace ” 命令。此時內容被放入delete 隊列，無法再通過 “ get ” 得到該內容，也無法是用 “ add ” 和 “ replace ” 命令（可是 “ set ” 命令可用）。直到指定時間，這些內容被終于從server的內存中徹底清除。<time> 參數是可選的，缺省為0（表示內容會立馬清除，并且隨后的存儲命令均可用）。

此命令有一行回應：- "DELETED\r\n" 表示執行成功

- "NOT_FOUND\r\n" 表示沒有找到這項內容

?

添加/ 降低

命令 “ incr ” 和 “ decr ” 被用來改動數據，當一些內容須要替換、添加或降低時。這些數據必須是十進制的32 位無符號整新。假設不是，則當作0 來處理。改動的內容必須存在，當使用 “ incr ” / “ decr ” 命令改動不存在的內容時，不會被當作0 處理，而是操作失敗。

client發送命令行：

incr <key> <value>\r\n 或decr <key> <value>\r\n

- <key> 是client希望改動的內容的建名

- <value> 是client要添加/ 降低的總數。

回復為下面集中情形：

- "NOT_FOUND\r\n" 指示該項內容的值，不存在。

- <value>\r\n ，<value> 是添加/降低。

注意"decr" 命令發生下溢：假設client嘗試降低的結果小于0 時，結果會是0。"incr" 命令不會發生溢出。

?

狀態

命令"stats" 被用于查詢server的執行狀態和其它內部數據。有兩種格式。不帶參數的：

stats\r\n

這會在隨后輸出各項狀態、設定值和文檔。還有一種格式帶有一些參數：

stats <args>\r\n

通過<args> ，server傳回各種內部數據。由于隨時可能發生變動，本文不提供參數的種類及其傳回數據。

?

各種狀態

受到無參數的"stats" 命令后，server發送多行內容，例如以下：

STAT <name> <value>\r\n

server用下面一行來終止這個清單：END\r\n，在每行狀態中，<name> 是狀態的名字，<value>使狀態的數據。下面清單，是全部的狀態名稱，數據類型，和數據代表的含義。

在 “ 類型 ” 一列中，"32u"表示32 位無符號整型，"64u"表示64 位無符號整型，"32u:32u"表示用冒號隔開的兩個32 位無符號整型。

?

名稱	類型	含義
pid	32u	server進程ID
uptime	32u	server執行時間，單位秒
time	32u	server當前的UNIX時間
version	string	server的版本號號
rusage_user	32u	該進程累計的用戶時間(秒:微妙)
rusage_system	32u	該進程累計的系統時間(秒:微妙)
curr_items	32u	server當前存儲的內容數量
total_items	32u	server啟動以來存儲過的內容總數
bytes	64u	server當前存儲內容所占用的字節數
curr_connections	32u	連接數
total_connections	32u	server執行以來接受的連接總數
connection_structures	32u	server分配的連接結構的數量
cmd_get	32u	取回請求總數
cmd_set	32u	存儲請求總數
get_hits	32u	請求成功的總次數
get_misses	32u	請求失敗的總次數
bytes_read	64u	server從網絡讀取到的總字節數
bytes_written	64u	server向網絡發送的總字節數
limit_maxbytes	32u	server在存儲時被同意使用的字節總數

?

?假設不想每次通過輸入stats來查看memcache狀態，能夠通過echo "stats" |nc ?ip port 來查看，比如：echo "stats" | nc 127.0.0.1 9023。