缓存系列知识点-memcached篇
说明：摘自互联网文章，在此总结作为自己日后一个回顾作用，不喜勿喷！
一、Memcached篇
1.1、 简介
是一个高性能的分布式的内存对象缓存系统，用来分担数据库的压力，通过在内存中维护一个巨大的hash表，它能够用来存储各种格式的数据，如图像、视频、文件以及数据库检索的结果等，简单说就是将数据调用到内存中，然后从内存中读取，从而大大提高读取速度。
查询数据的常规方法：
l 直接查询数据库(慢)
l 使用真静态(块)
l 直接操作内存(极快)
1.2、 原理
先访问内存表，如果在memcached中没有存放查询结果，访问数据库，然后把查询的结果放入到memcached，如果查询的数据已经存在内存中，就直接访问内存。
Memached的key一般是字符串，且唯一；value可以存放字符串、数值、数组、对象、布尔、二进制数据、null。
机制深入
l C/S架构，此时memcached为服务器端，我们可以使用如php、c/c++等程序链接memcached服务器，客户端通信并不使用XML等格式，而使用简单的基于文本行的协议。因此通过telnet也能在mamcached上保存数据、取得数据。
l 基于libevent的时间处理，libevent是一套跨平台的时间处理接口的封装，能够兼容windows/linux/BSDSolaris等操作系统的时间处理。使用libvent来进行网络并发链接的处理，能够保持在很大并发情况下，仍旧能够保持快速的响应能力。
l 为了提高性能，memcached中保存的数据都存储在memcached内置的内存存储空间中，由于数据仅存在内存中，因此重启memcached、重启操作系统会导致全部数据小时，另外，内容容量达到指定值之后，就基于近期最少使用算法LRU(Least Recently Used)自动删除不使用的缓存，memcached本身是为了缓存而设计的服务器，一次病没有过多考虑数据的永久性问题。
l 基于客户端的分布式。尽管是分布式缓存服务器，但服务器并没有分布式功能，各个memcached不会互相通信以共享信息，那么怎样进行分布式呢？这完全取决于客户端的实现。
l Slab Allocation机制：整理内存以便重复使用
默认采用名为Slab Allcator的机制分配、管理内存、在该机制出现以前，内存的分配是通过对所有记录简单地进行malloc和free来进行的。但是，这种方式会导致内存碎片，加重操作系统内存管理器的负担，最坏的情况下，会导致操作系统比memcached进行本身还慢。Slab Allocator就是为了解决该问题而生的。
Slab Allocation 的原理箱单简单。将分配的内存分割成各种尺寸的块(chunk)，并把尺寸相同的块分成组(chunk的组合)
l Page 分配给Slab的内存空间，默认是1MB，分配给Slab之后根据slab的大小切分成chunk。
l Chunk 用于缓存记录的内存空间。
l Memcahed根据收到的数据大小，选择最适合的数据大小的slab，memcached中保存着slab内空闲chunk的列表，根据该列表选择chunk，然后将数据缓存于其中
l Slab Allocator的缺点
由于分配的是特定长度的内存，因此无法有效利用分配到额内存，比如将100字节的数据缓存到128字节的chunk中，剩余的28自己就浪费了。
l Growth Factor进行调优
Memcached在启动时指定GrowthFactor因子(通过f选项)，就可以在某种程度上控制slab之间的差异，默认值为1.25，但是在该选项出现之前，这个因子曾经固定为2，成为powsersof 2策略。
可见从128字节的组开始，组的大小依次增大为原来的2倍，这样设置的问题是，slab之间的差别比较大，有些情况下就相当浪费内存，因此为尽量减少内存浪费，两年前追加了growth factor这个选项来看看现在的默认设置(f=1.25)时的输出
可见组之间的差距比因子为2时小的多，更适合缓存几百字节的记录，从上面的输出结果来看，可能会觉得有些计算误差，这些误差是为了保持字节数的对齐而故意设置的，将memcached引入产品，或者直接使用默认值进行部署时，最好重新计算一下数据的预期平均长度，调整growth factor，以获得最恰当的设置，内存是珍贵的资源
l 删除
Memcached不会释放已经分配的内存，记录过期之后，客户端无法再看到这条记录，其存储空间就可以利用。
Memcached内部不会监视记录是否过期，而是在get时查看记录的时间戳，检查记录是否过期，这种技术被称为lazyexpiration.因此memcached不会在过期监视上耗费CPU时间。
Memcached会优先使用已超时的记录的空间，但即使如此，也会发生追加新记录时空间不足的情况，此时就要使用使用名为least Rcently Used机制来分配空间。顾名思义，这是删除最近最少使用的记录的机制。因此当memcached的内存空间不足时(无法从slab class获取到最新的控件时)，就从最近未被使用的记录中搜索，并将其空间分配给新的记录。从缓存的实用角度来看，该模型十分理想，不过，有些情况下LRU机制反倒会造成麻烦，memcached启动时通过”M”参数可以禁止LRU，如下所示：
l 分布式算法
余数分布式算法，根据服务器台数的余数进行分散，求得键的整数哈希值，根据其余数来选择服务器，算法简单，数据的分散性也相当优秀，但也有其缺点，那就是当添加或者移除服务器时，缓存重组的代价相当巨大，添加服务器后，余数就会产生巨变，这样就无法获取保存时相同的服务器，从而影响缓存的命中。
哈希算法，即散列函数，将任意长度的二进制映射为较短的固定长度的二进制，这个小的二进制成为哈希值，哈希值是一段数据唯一且机器紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值，要找到散列为同一个值的两个不同输入，在计算上是不可能的，所以数据的哈希值可以校验数据的完整性，一般用于快速查找和加密算法(MD5、SHA-1)
Consistent Hashing的简单说明：
首先求除memcached服务器节点的哈希值(一般的方法可以使用cache机器的ip地址或者机器名作为hash输入)，并将其配置到-~2 32次上，然后同样的方法求除存储数据的键的哈希值，并映射到圆上，然后从数据映射到的位置开始顺时针的查找，将数据保存到找到的第一个服务器上，如果超过2的32仍找不到服务器，就会保存到第一台memcache服务器上。
从上图的状态中添加一台memcached服务器，余数分布式计算法由于保存键的服务器会发生巨大的而变化，从而影响缓存的命中率，但Consistent Hashing中，自由在continuum上增加服务器的地点逆时针方向的第一台服务器上的键受到影响。
Constistent hashing的基本思路就是将对象和cache都映射到同一个hash数值空间中，并且使用相同的hash算法。
现在cache和对象都已经通过同一个hash算法映射到hash数值空间中了，接下来要考虑的就是如何将对象映射到cache上面了。
在这个环形空间中，如果沿着顺时针方向从对象的key值触发，直到遇到一个cache，那么就将该对象存储在这个cache上，因为对象和cache的hash值是固定的，因此这个cache必然是唯一和确定的，这样不就找到了对象和cache的映射方法了吗？
因此consistenthashing最大限度的限制了建的重新分布，而且有的consistent hashing的实现方法还采用了虚拟节点的思想，使用一般的hash函数的话，服务器的映射地点的分布非常不均匀，因此使用虚拟节点的思想，为每个物理节点在continuum上分配100到200个点，这样就能抑制分布不均匀，最大限度的地减少服务器增减时的缓存重新分布。
1.3、 应对memcached缓存失效，导致高并发查询DB的集中几种思路
当缓存将要失效时，及时地把新的数据刷懂啊memcached里，这个是解决缓存失效瞬间高并发查DB的最好方法，那么如何及时地知道缓存将要失效。
如一个key是aaa,失效时间是30s
l 定期从DB里查询数据，再刷到memcached里
这种方法有缺点，有些业务的key可能是变化的，不确定的，而且不好界定哪些数据是应该查询出来放到缓存中的，难以区分冷热数据。
l 当缓存取null时，加锁去查询DB，只允许一个线程去查DB
这种方法存在并发操作，当有多台web服务器时。
l 在向memcached写入value时，同时写入当前机器在时间作为过期时间
当get得到数据时，如果当前时间-过期时间>5s,则后台启动一个任务去查询DB，更新缓存，当然这里的后台任务必须保证同一个key，只有一个线程在执行查询DB的任务，不然这个还是高并发查询DB。
缺点要把过期时间和value合在一起序列化，取出数据后还要反序列化，很不方便。
l 两个key，一个key用来存放数据，另外一个用来标记失效时间
比如key是aaa，设置失效时间为30s，则另外一个key为expie_aaa，失效时间为25s
在取数据时，用multiget同时去除aaa和expire_aaa，如果expire_aaa的value==null,则后台启动一个恩物去查询DB，更新缓存。
对于后台启动一个恩物去查询DB，更新缓冲呢，要保证一个key只有一个线程在执行，这个如何实现，对于同一个进程，简单加锁即可，拿到锁的就去更新DB，没拿到锁的就直接返回。
l 对于集群式的部署的，如何实现只允许一个任务执行？
l 这里就要用到memcached的add命令了。
l add命令是如果不存在key，则设置成功，返回true，如果已存在key，则不存储，返回false。
l 当get expired_aaa是null时，则add expired_aaa 过期时间由自己灵活处理。比如设置为3秒。
l 如果成功了，再去查询DB，查到数据后，再set expired_aaa为25秒。set aaa 为30秒。
l 综上所述，来梳理下流程：
l 比如一个key是aaa，失效时间是30s。查询DB在1s内。
l put数据时，设置aaa过期时间30s，设置expire_aaa过期时间25s；
l get数据时，multiget aaa 和 expire_aaa，如果expired_aaa对应的value != null，则直接返回aaa对应的数据给用户。如果expire_aaa返回value == null，则后台启动一个任务，尝试add expire_aaa，并设置超时过间为3s。这里设置为3s是为了防止后台任务失败或者阻塞，如果这个任务执行失败，那么3秒后，如果有另外的用户访问，那么可以再次尝试查询DB。如果add执行成功，则查询DB，再更新aaa的缓存，并设置expire_aaa的超时时间为25s。
l 5. 时间存到Value里，再结合add命令来保证只有一个线程去刷新数据
l update:2014-06-29
l 最近重新思考了下这个问题。发现第4种两个key的办法比较耗memcached的内存，因为key数翻倍了。结合第3种方式，重新设计了下，思路如下：
l 仍然使用两个key的方案：
l key
l __load_{key}
l 其中，__load_{key} 这个key相当于一个锁，只允许add成功的线程去更新数据，而这个key的超时时间是比较短的，不会一直占用memcached的内存。
l 在set 到Memcached的value中，加上一个时间，(time,value)，time是memcached上的key未来会过期的时间，并不是当前系统时间。
l 当get到数据时，检查时间是否快要超时： time – now < 5 *1000，假定设置了快要超时的时间是5秒。
l * 如果是，则后台启动一个新的线程：
l * 尝试 add __load_{key}，
l * 如果成功，则去加载新的数据，并set到memcached中。
l * 原来的线程直接返回value给调用者。
l 按上面的思路，用xmemcached封装了下：
l DataLoader，用户要实现的加载数据的回调接口：
l 1
l 2
l 3 public interfaceDataLoader {
l public <T> T load();
l }
l RefreshCacheManager，用户只需要关心这这两个接口函数：
l 1
l 2
l 3
l 4 public classRefreshCacheManager {
l static public <T> TtryGet(MemcachedClient memcachedClient, final String key, final int expire,final DataLoader dataLoader);
l static public <T> TautoRetryGet(MemcachedClient memcachedClient, final String key, final intexpire, final DataLoader dataLoader);
l }
l 其中autoRetryGet函数如果get到是null，内部会自动重试4次，每次间隔500ms。
l RefreshCacheManager内部自动处理数据快过期，重新刷新到memcached的逻辑。
l 详细的封装代码在这里：https://gist.github.com/hengyunabc/cc57478bfcb4cd0553c2
l 总结：
l 我个人是倾向于第5种方式的，因为很简单，直观。比第4种方式要节省内存，而且不用mget，在使用memcached集群时不用担心出麻烦事。
l 这种两个key的方式，还有一个好处，就是数据是自然冷热适应的。如果是冷数据，30秒都没有人访问，那么数据会过期。
l 如果是热门数据，一直有大流量访问，那么数据就是一直热的，而且数据一直不会过期。