数据挖掘化功大法（17）——分布式缓存

先看架构：

图一

用户通过访问http服务器，然后访问应用服务器资源，应用服务器调用后端的数据库，在第一次访问的时候，直接访问数据库，然后将要缓存的内容放入memcached集群，集群规模根据缓存文件的大小而定。在第二次访问的时候就直接进入缓存读取，不需要进行数据库的操作。这个适合数据变化不频繁的场景，比如：互联网站显示的榜单、阅读排行等。

博客园的48小时阅读排行就类似于这一种：

当然，缓存的架构使用方式不止这一种方式，在数据挖掘系统中，对于不频繁更新的数据或者离线的数据都可以使用这种方式。具体的应用需要在不同的场景下进行架构设计。

一致性hash

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希(DHT)可以在P2P环境中真正得到应用。

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要讲解一下一致性哈希算法是如何设计的：

1、 hash机器节点

首先求出机器节点的hash值(怎么算机器节点的haship可以作为hash的参数吧。。当然还有其他的方法了)，然后将其分布到0～2^32的一个圆环上(顺时针分布)。如下图所示：

图二

集群中有机器：A , B, C, D, E五台机器，通过一定的hash算法我们将其分布到如上图所示的环上。

2、访问方式

如果有一个写入缓存的请求，其中Key值为K，计算器hash值Hash(K)， Hash(K) 对应于图 – 1环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点，如果超过了2^32仍然找不到节点，则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间，那么命中的机器节点应该是B节点(如上图 )。

3、增加节点的处理

如上图二，在原有集群的基础上欲增加一台机器F，增加过程如下：

计算机器节点的Hash值，将机器映射到环中的一个节点，如下图：

图三

增加机器节点F之后，访问策略不改变，依然按照(2)中的方式访问，此时缓存命不中的情况依然不可避免，不能命中的数据是hash(K)在增加节点以前落在C～F之间的数据。尽管依然存在节点增加带来的命中问题，但是比较传统的 hash取模的方式，一致性hash已经将不命中的数据降到了最低。

Memcached

Memcached 是一个高性能的分布式内存对象缓存系统，用于动态Web应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提高动态、数据库驱动网站的速度。Memcached基于一个存储键/值对的hashmap。其守护进程(daemon )是用C写的，但是客户端可以用任何语言来编写，并通过memcached协议与守护进程通信。下图图四介绍的是缓存的拓补结构：

图四

Memcached的特点包括：

全内存运转
哈希方式存储
简单文本协议进行数据通信
叧操作字符型数据
其它类型数据由应用解释，序列化以及反序列化
集群也由应用进行控制，采用一致性散列(哈希)算法

Memcached变种产品介绍

国内外有很多基于Memcached开发的产品，这些产品支持所有Memcached的协议，同时侧重不同的应用场景，可以根据自己的应用需求选择合适的Memcached变种。下面分别介绍几种Memcached的变种产品。

1. memcachedb

memcachedb是新浪网基于Memcached开发的一个开源项目。通过为Memcached增加Berkeley DB的持久化存储机制和异步主辅复制机制，使Memcached具备了事务恢复能力、持久化能力和分布式复制能力，非常适合需要超高性能读写速度、持久化保存的应用场景，例如，将memcachedb应用于新浪博客的管理。如果对Memcached有持久化需求，可以考虑使用memcachedb。

2. repcached

repcached是日本人开发的基于Memcached的一个patch，实现Memcached的复制功能，它支持多个Memcached之间相互复制，可以解决Memcached的容灾问题。有cache容灾需求的可以尝试使用这一功能。

3. memcached_functions_mysql

这个功能相当于MySQL的UDFs(User Defined Functions)，在MySQL中通过触发器更新Memcached。这样可以做到把数据写入MySQL，然后从Memcached获取数据，以减轻数据库的压力，同时减少很多开发的工作量。

关于memcached_functions_mysql的使用和经验会在下一节进行详细介绍。

4. memcacheQ

memcacheQ在Memcached的基础上实现了消息队列。下面以PHP客户端为例介绍memcacheQ实现消息队列的方式。

消息从尾部入栈：memcache_set

消息从头部出栈：memcache_get

memcacheQ最大的优势是：它是基于Memcached开发的，可以通过各种Memcached命令对它进行操作。基于Memcached开发的应用完全不需要做任何修改。

总结

分布式缓存通常用在频繁访问或者不能实时处理的情况下，使用场景包括：