memcached剖析（1）

此文已由作者赵计刚授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验。

注：本篇博客参考于两本书。

• 《memcached全面剖析》，该书籍市面上应该没有，我传到了百度云盘，链接如下：http://pan.baidu.com/s/1qX00Lti
  
• 《大型网站技术架构：核心原理与案例分析》

前提：

• 本文是基于memcached1.4版本的，之前的版本与该版本在一些地方是不一样的（eg.《memcached全面剖析》的memcached1.2的内存管理方式就与1.4不同）
• 在看本文之前，最好先看一下memcached在实际开发中怎么进行操作的，链接《第八章 企业项目开发--分布式缓存memcached》

1、memcached特征

• 协议简单(文本协议、二进制协议)
• 基于libevent的事件处理，libevent封装了Linux的epoll模型的时间处理功能。
• slab存储模型
• 集群中服务器间互不通信(在大集群的情况下，其性能远超其他同步更新缓存的缓存器，当然小集群下，memcached的性能也十分优秀)

 

2、memcached访问模型

说明：

Xmemcached的具体使用代码查看"Java企业项目开发实践"系列博客的《第八章 企业项目开发--分布式缓存memcached》，下面的解释会依据该代码进行。

在上图中，memcached客户端假设使用XMemcached

• 服务器列表：在根pom.xml文件中进行了配置
• 路由算法有两种：（可以在程序中指定）
  • 一致性hash算法（推荐）
  • 简单求余法
• 通信模块：
  • 通信协议：TCP协议
  • 序列化协议：二进制协议（推荐）、文本协议
• Memcached API（缓存的增删改查）：在程序中编写

整个流程：

应用程序（AdminService）调用Memcached API（假设为add操作），向memcached服务器添加缓存，这时候，程序会首先根据配置的路由算法（假设是一致性hash算法）在服务器列表中选出一台服务器（假设是node1），之后该API通过序列化协议序列化对象（当然，这个是可无的，eg.value是一个String），并通过TCP协议将将要存储的key-value对存入相应的服务器。在get时，只要采用的是与add时相同的hash算法，就会选中add时的那一台服务器。

看完这一段，流程明白了。但是有几点疑问：

• 两种路由算法是怎样实现的？为什么使用一致性hash算法
• 缓存到达服务器的时候究竟怎么存储？（slab内存模型）
• 当缓存超过一定的容量后，缓存的自动删除是采用什么策略，怎样删除的？（LRU）
• 两种序列化协议有什么优缺点？

 

3、hash算法

3.1、简单求余法

原理步骤：求得key的整数hash值（对于Java对象而言，直接使用其hashCode()方法就好），再除以服务器台数，获取余数，根据该余数选择服务器。

注意：如果选择的服务器无法连接时，会进行rehash，即：将连接次数添加到键中，重新计算hash值后，再重新连接。当然可以禁止rehash。

优点：

• 简单
• hash分散性好（因为hashCode()的值具有随机性）

缺点：

• 添加或删除服务器的时候，缓存的获取就会出问题了（因为服务器台数变了，求余的时候分母变了，余数也就可能变了），假设在99台memcached服务器中又新添加而一台，则缓存的不命中率是99%，即n/(n+1)，n表示原有的服务器。

注意：

• 在XMemcached中仍保留了该算法
• 适用于不需要考虑集群伸缩性的时候（即机器总数不变）

3.2、一致性hash算法

对于绝大部分系统，集群的伸缩性是五个非功能需求中比较重要的一个，也就是说必须克服"简单求余法"的缺点。

• 原理：先构造一个长度为0~2³²的整数环（使用二叉树构造），根据节点（memcached服务器）名称的hash值将缓存服务器节点放置在这个hash环上，然后根据需要缓存的数据的key来计算其hash值，然后在hash环上顺时针查找距离这个key的hash值最近的缓存服务器节点，完成key到服务器的hash映射查找。
  • 如果超过2³²还找不到，则存在第一台memcached上（依旧是顺时针）
• 存在的问题：当服务器数量比较少的情况下，有可能造成负载不均衡的情况，为了防止这种情况的发生，使用将物理服务器先虚拟化成多台虚拟服务器，然后将这些虚拟服务器的hash值放在环上，当客户端路由到某台虚拟服务器上时，找到该虚拟服务器所对应的物理服务器即可。
  • 一般而言，一台物理服务器虚拟化为150台虚拟服务器最合适，太少会造成负载不均，太多会影响性能
• Memcached采用这样的算法，在我们新加入服务器或集群中的某台服务器宕机时，都不会有太大的影响，只会影响一小段（见下图），确保了集群的可用性与伸缩性

注意：

• hash环是一个二叉树，最后边叶子与最左边相连成环
• 整个缓存的查找过程就是找一个刚刚大于等于查找数的最小值

疑问：（这一点没查到资料）

• 服务器的hash算法是怎样的
• 计算缓存key的hash算法是否要与服务器的一致，还能不能使用原来的hashCode()

思路：hash算法实际上就是"先将字符串转化为整数，然后再将该整数放到相应的服务器上或环上"，对于key不用讲，我们可以用crc32将字符串的key转化为整数，之后放在0~2³²的环上的一点，对于服务器我们可以采用将"ip:port"这个字符串使用crc32转化为整数，之后放在环上（当然这里我们需要将一个实例"ip:port"虚拟化成一堆虚拟节点，每台虚拟节点可以使用"ip:port-i"作为节点名称，其中i是>0的整数，将每台虚拟节点的名称采用crc32算法算出整数放到环上）。

免费领取验证码、内容安全、短信发送、直播点播体验包及云服务器等套餐

更多网易技术、产品、运营经验分享请点击。