基于MemCache的分布式扩展算法

齐建军

摘要：随着近些年来互联网的高速发展，每天产生的数据量也随之不断增大，对于网站访问速度的要求不断提高，传统的关系型数据库不能够满足当前的需求。因此我们引入NoSQL数据库，即基于Key-Value模型的缓存关系数据库，用于提高网站的读写效率和访问速度。该文着重讨论基于MemCache的分布式扩展算法来进行研究，实验证明，选取合理的分布式算法，将会进一步大大的提升网站的稳定性和高可用性。

关键词：数据缓存；NoSQL；分布式算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）28-0018-02

1 概述

随着web2.0网站的兴起以及近些年来移动互联网的大爆发，传统的关系型数据库已经不能够满足数据的高并发读写、高效率存储和访问以及高可用性等需求，于是非关系型数据库（NoSQL）的出现成为了解决这些问题的有效手段。

针对数据库高并发的读写的需求[1]，网站需要提供实时的动态页面和信息，如果使用传统的关系型数据库，并发负载明显偏高，达到每秒上万次的读写请求。关系型数据库可以应对多次SQL查询，但对于写数据请求，硬盘的IO就显得力不从心了。

在网站架构升级的过程中发现，随着用户数量和网站访问量的不断增加，我们的数据库却无法像应用层的业务逻辑一样，简单的以添加服务器和服务节点的方法扩展负载能力和总体性能。尤其对于那些支付网站以及对系统实时性要求比较高的网站来说，对数据库进行升级以及迁移是一件非常麻烦的事情，而且我们在迁移的过程中，要保证用户对此操作是没有任何感知的，这显然对传统的数据库来说，通过添加服务器节点来实现扩展几乎是不可能的[2]。

为有效解决传统关系型数据库的缺陷，使用NoSQL数据库进行替代。当前业内比较流行的NoSQL的数据库产品主要包括MemCache，Redis和MongoDB等，这三种NoSQL数据库用的比较多，也是性能比较不错的三款NoSQL数据库。在本文中，将重点讨论MemCache分布式存储数据的相关算法。

2 基于MemCache的介绍

MemCache是一个高性能的分布式的内存对象缓存系统。通过在内存里维护一个统一的巨大的hash表，并且能够存储各种格式的数据[3]。它是DangaInteractive公司研发的一款软件。初期只是为了用来提高自己公司网站的访问速度，目前已经成为了mixi、hatena、Facebook、Vox、LiveJournal等网站用来提高Web应用扩展性的一款产品。

相比传统的Web应用过程，是把数据保存在RDBMS中，服务器从RDBMS中读取数据，进行数据处理后在显示于浏览器中。但是，如果数据量增大亦或访问集中，必然使得RDBMS的负担加重，数据库响应变得缓慢，最终导致系统响应延迟增加。

采用MemCache可以有效解决这个问题，目的就是通过缓存数据库的查询命中来减少数据库压力，提高响应速度和可扩展性。

如下图示，为常见的MemCache的缓存应用示意图：

从上图，我们不难看出，当客户端过来取数据的时候，首先是从缓存中查询数据，如果没有的话，才会到数据库中查询数据，最终将数据返回给客户端，并且存入到缓存中，以供下一次查询使用。

3 MemCache的分布式原理

MemCache是“分布式”缓存服务器，可是其服务器端并不具备分布式功能。各个服务器之间不会相互通信来共享信息。如何进行分布完全取决于客户端（严格的说是取决于分布式算法如何选择）的实现，因此也称为基于客户端的分布式。

一般有两种实现分布式的算法：

3.1 余数取余算法

余数计算分散法是标准的MemCache分布式方法，客户端根据key计算CRC，对服务器数进行取模，最终得到MemCache服务器节点。

这种方法的缺点是在添加或者移除服务器的时候，缓存重组的代价比较大。

3.2 一致性哈希算法

为了解决余数取余算法添加或者移除服务器带来的性能问题，我们使用一致性哈希算法来解决。

具体的步骤如下：

（1） 使用crc32算法算出每个服务节点的hash值，并将每个值映射到一个0～2^32的圆环上。我们称这个圆环为一个值域。

（2） 使用同样的算法算出要存入的每个key的hash值，也将其配置到这个圆环上。

（3） 接下来从数据映射的位置开始顺时针查找，将数据保存在寻找到的第一个服务器上，倘若超过0～2^32仍然找不到，结果将会保存在第一个服务器中。

如果移除或者添加一台服务器会出现什么情况？

我们发现，当添加node5节点后，node5被放在了node4和node2之间，原本映射到node2和node4之间的区域都会找到node4，如果存在node5，node5和node4之间的仍然找到node4，而在node5和node2之间的则会找到node5，也就是说，添加一台服务器时，受影响的仅仅是node5和node2区间。

3.3 优化一致性hash算法[4]

从上面的例子中，我们发现一致性hash最大限度的抑制了键的重新分配，但是有的时候，我们在计算服务器或者key的hash值时，如果使用一般函数进行处理的话，服务器的映射节点会非常的不均匀，从而导致缓存存储倾斜，大量的key被映射到同一台服务器上。为了避免这个问题发生，因此上引入虚拟节点的机制。具体做法就是为每一个服务器计算出多个hash值，每个计算值对应环上的一个节点位置，这种节点即是虚拟节点。使用虚拟节点，当某个节点移除后，跟这个节点关联的相应虚节点也会移除，但我们发现，数据分布并没有因为此节点的移除而大面積的崩溃。

4 结束语

分布式数据缓存模式越来越被国内的大型互联网公司以及中型公司应用，大规模的企业级应用可以用集群来保证。数据缓存可以减少数据库的访问压力，提高数据命中率，而相应的分布式模式可以均衡服务器的压力，减少业务逻辑对底层服务的访问，从而进一步提高系统的性能。

参考文献：

[1] 黄贤立.NoSQL 非关系型数据库的发展及应用初探[J].福建电脑，2010（7）：30-45.

[2] 谢毅.NoSQL.非关系型数据库综述[J].先进技术研究通报，2010，4（8）：46-50.

[3] 宗小中.基于Memcached构建Web缓存服务器[J].电脑知识与技术，2011，7（5）：1-4.

[4] 潘金贵.Cormen TH.算法导论[M].北京：机械工业出版社，2006.endprint