写在前面： 前不久在工作中被问到关于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发送的数据的公用大小，或者仅缓存大小同样的数据的情况下，仅仅要使用适合数据大小的组的列表，就能够降低浪费。可是非常遗憾，如今还不能进行不论什么调优，仅仅能期待以后的版本号了。可是，我们能够调节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 32 的圆（continuum）上。然后用同样的方法求出存储数据的 键 的哈希值，并映射到圆上。然后从数据映射到的位置開始顺时针查找，将数据保存到找到的第一个server上。假设超过 2 32 仍然找不到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。
