memcached

简介Memcached

memcached是高性能的分布式内存缓存服务器。它通过缓存数据库查询结果，减少数据库访问次数，以提高动态Web应用的速度、提高可扩展性。memcached的API使用32位元的循环冗余校验（CRC-32）计算键值后，将资料分散在不同的机器上。当表格满了以后，接下来新增的资料会以LRU机制替换掉。Memcached基于一个存储键/值对的hashmap。其守护进程（daemon）是用C写的，但是客户端可以用任何语言来编写，并通过memcached协议与守护进程通信
Memcached的分布式算法

A.余数哈希：根据服务器台数的余数进行哈希,求得键的哈希值,再处理服务器台数,根据余数选择服务器, 缺点:当添加或者移除服务器时,缓存重组的代价太大, 当添加服务器,要进行重哈希，会导致原来的服务器序号变了，下一次找不到，访问数据,Memcached命中率下降,那么就增加了数据库服务器的负载.

B.一致性哈希：一致性哈希是将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间是0~(2^32 -1)(即哈希值是一个32位的无符号整型),这个哈希空间为环。然后让每台机器占一个扇形空间。

举个例子：余数哈希相当于一个萝卜一个坑，刚刚好，这时候在中间新挖一个坑，下一次去拿的时候会按照原有逻辑，会导致最后一个有萝卜的坑没被拿到丢了。一致性哈希就是这100米内都来这个坑挖，100米之后的去下一个坑，这时候新挖一个坑，重新调整一些空间给新的坑就行，不至于数据全部丢失。

LRU。每个slab会维护一个队列，刚插入的数据在队头，经常get的数据也会移动到队头，这样较老或者访问较少的数据相对都留在队尾。该算法从队尾开始淘汰。当slab分配不到足够的内存时，首先会检查队尾是否有过期数据。如果有的话会直接将其覆盖为新的对象，如果没有，会开始淘汰队尾的对象。

Slab是一个内存块，它是memcached一次申请内存的最小单位。Slab的大小固定为1M（1048576 Byte），一个slab由若干个大小相等的chunk组成。每个chunk中都保存了一个item结构体、一对key和value。

Memcacehd的工作流程

先检查客户端的请求数据是否在memcached中，如有，直接把请求数据返回，不再对数据库进行任何操作；如果请求的数据不在memcached中，就去查数据库，把从数据库中获取的数据返回给客户端，同时把数据缓存一份到memcached中（memcached客户端不负责，需要程序明确实现）；每次更新数据库的同时更新memcached中的数据，保证一致性；当分配给memcached内存空间用完之后，会使用LRU（Least Recently Used，最近最少使用）策略加上到期失效策略，失效数据首先被替换，然后再替换掉最近未使用的数据。