`

memcached的总结和分布式一致性hash

 
阅读更多
当前很多大型的web系统为了减轻数据库服务器负载,会采用memchached作为缓存系统以提高响应速度。

目录:

memchached简介
hash
取模
一致性hash
虚拟节点
源码解析
参考资料
1. memchached简介
memcached是一个开源的高性能分布式内存对象缓存系统。
其实思想还是比较简单的,实现包括server端(memcached开源项目一般只单指server端)和client端两部分:

server端本质是一个in-memory key-value store,通过在内存中维护一个大的hashmap用来存储小块的任意数据,对外通过统一的简单接口(memcached protocol)来提供操作。
client端是一个library,负责处理memcached protocol的网络通信细节,与memcached server通信,针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。
web系统则通过client库来使用memcached进行对象缓存。
2. hash
memcached的分布式主要体现在client端,对于server端,仅仅是部署多个memcached server组成集群,每个server独自维护自己的数据(互相之间没有任何通信),通过daemon监听端口等待client端的请求。
而在client端,通过一致的hash算法,将要存储的数据分布到某个特定的server上进行存储,后续读取查询使用同样的hash算法即可定位。

client端可以采用各种hash算法来定位server:
取模
最简单的hash算法

targetServer = serverList[hash(key) % serverList.size]

直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

一致性hash
为了解决这个问题,需要采用一致性hash算法(consistent hash)
相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

为了方便理解,可以把这个有限值域理解成一个环,值顺时针递增。

如上图所示,集群中一共有5个memcached server,已通过server的hash值分布到环中。

如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点

可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

那么它是怎么解决增/删server导致的cache不能命中的问题呢?
假设,现在增加一个server F,如下图


此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

虚拟节点
但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

如图,一共有3台server – 1,2,4。命中4的几率远远高于1和2。
为解决这个问题,需要使用虚拟节点的思想:为每个物理节点(server)在环上分配100~200个点,这样环上的节点较多,就能抑制分布不均匀。
当为cache定位目标server时,如果定位到虚拟节点上,就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。

另外,如果每个实际server的负载能力不同,可以赋予不同的权重,根据权重分配不同数量的虚拟节点。

// 采用有序map来模拟环   
this.consistentBuckets = new TreeMap();  
  
MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值   
  
// 计算总权重   
if ( this.totalWeight   for ( int i = 0; i < this.weights.length; i++ )  
        this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];  
} else if ( this.weights == null ) {  
    this.totalWeight = this.servers.length;  
}  
  
// 为每个server分配虚拟节点   
for ( int i = 0; i < servers.length; i++ ) {  
    // 计算当前server的权重   
    int thisWeight = 1;  
    if ( this.weights != null && this.weights[i] != null )  
        thisWeight = this.weights[i];  
  
    // factor用来控制每个server分配的虚拟节点数量   
    // 权重都相同时,factor=40   
    // 权重不同时,factor=40*server总数*该server权重所占的百分比   
    // 总的来说,权重越大,factor越大,可以分配越多的虚拟节点   
    double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );  
  
    for ( long j = 0; j < factor; j++ ) {  
        // 每个server有factor个hash值   
        // 使用server的域名或IP加上编号来计算hash值   
        // 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值:   
        // 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor   
        byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );  
  
        // 每个hash值生成4个虚拟节点   
        for ( int h = 0 ; h < 4; h++ ) {  
            Long k =  
                ((long)(d[3+h*4]&0xFF) << 24)  
                  | ((long)(d[2+h*4]&0xFF) << 16)  
                  | ((long)(d[1+h*4]&0xFF) << 8 )  
                  | ((long)(d[0+h*4]&0xFF));  
  
            // 在环上保存节点   
            consistentBuckets.put( k, servers[i] );  
        }  
  
    }  
    // 每个server一共分配4*factor个虚拟节点   
}  
// 采用有序map来模拟环
this.consistentBuckets = new TreeMap();

MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值

// 计算总权重
if ( this.totalWeight 	for ( int i = 0; i < this.weights.length; i++ )
		this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
	this.totalWeight = this.servers.length;
}

// 为每个server分配虚拟节点
for ( int i = 0; i < servers.length; i++ ) {
	// 计算当前server的权重
	int thisWeight = 1;
	if ( this.weights != null && this.weights[i] != null )
		thisWeight = this.weights[i];

	// factor用来控制每个server分配的虚拟节点数量
	// 权重都相同时,factor=40
	// 权重不同时,factor=40*server总数*该server权重所占的百分比
	// 总的来说,权重越大,factor越大,可以分配越多的虚拟节点
	double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );

	for ( long j = 0; j < factor; j++ ) {
		// 每个server有factor个hash值
		// 使用server的域名或IP加上编号来计算hash值
		// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值:
		// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
		byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );

		// 每个hash值生成4个虚拟节点
		for ( int h = 0 ; h < 4; h++ ) {
			Long k =
				((long)(d[3+h*4]&0xFF) << 24)
			      | ((long)(d[2+h*4]&0xFF) << 16)
			      | ((long)(d[1+h*4]&0xFF) << 8 )
			      | ((long)(d[0+h*4]&0xFF));

			// 在环上保存节点
			consistentBuckets.put( k, servers[i] );
		}

	}
	// 每个server一共分配4*factor个虚拟节点
}


// 用MD5来计算key的hash值   
MessageDigest md5 = MD5.get();  
md5.reset();  
md5.update( key.getBytes() );  
byte[] bKey = md5.digest();  
  
// 取MD5值的低32位作为key的hash值   
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);  
  
// hv的tailMap的第一个虚拟节点对应的即是目标server   
SortedMap tmap = this.consistentBuckets.tailMap( hv );  
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();  
分享到:
评论

相关推荐

    memcached//分布式数据缓存

    6. **分布式存储**:虽然单个Memcached实例的内存有限,但可以通过在多台机器上部署多个实例,使用一致性哈希等算法实现分布式缓存,扩大存储容量并提高可用性。 7. **源码分析**:对于深入理解其工作原理,可以...

    解决分布式数据插入数据库~一致性hash算法

    此外,一致性哈希算法在分布式缓存如Memcached、Redis中也得到了广泛应用。它不仅简化了数据分布的逻辑,还允许动态扩展和收缩集群规模,无需大规模的数据迁移。 在文件名为“distribute-mysql”的压缩包中,可能...

    一致性哈希算法源码 Ketama一致性hash算法源码

    一致性哈希算法是一种分布式哈希(Distributed Hash Table, DHT)技术,旨在解决在分布式环境中数据分布不均匀的问题。Ketama算法是基于一致性哈希的一种优化实现,由Last.fm公司的Simon Willison提出,其目标是在...

    搞懂分布式技术11:分布式session解决方案与一致性hash.docx

    - **分布式缓存**:如Memcached等,通过一致性Hash算法可以有效地解决数据分布问题。 - **负载均衡**:在多台服务器之间分发请求时,一致性Hash可以帮助实现请求到特定服务器的稳定映射。 #### 四、总结 在分布式...

    一致性Hash简单实现

    - **分布式缓存**:如Memcached、Redis集群中,一致性哈希用于确定数据应该存储在哪个节点上。 - **负载均衡**:在负载均衡器中,一致性哈希可以用来分配请求到不同的服务器,避免在动态调整服务器数量时大量请求...

    一致性Hash算法的原理及实现

    一致性Hash算法是一种用于解决分布式环境下数据存储和检索问题的重要技术。它最初由David Karger等人在1997年的论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots...

    一致性hashjava实现

    6. **应用场景**:一致性哈希在分布式缓存系统如Memcached和Redis中被广泛使用,同时在CDN(Content Delivery Network)、负载均衡器等场景也有应用。 7. **优缺点**:Ketama一致性哈希算法的优点在于减少了因节点...

    Ketama一致性Hash算法(含Java代码) 1

    总的来说,Ketama一致性哈希算法通过引入虚拟节点的概念,有效解决了传统一致性哈希中的热点问题,使得在动态调整服务器数量时,数据分布的变动更加平滑,提高了分布式系统的稳定性和效率。在Java环境中,可以通过...

    memcached全面剖析.pdf

    memcached 还支持一致性 Hash 算法,以确保数据的分布式存储。 memcached 的应用场景 memcached 广泛应用于各种 Web 应用程序中,包括社交媒体、电商平台、博客平台等。memcached 可以用于缓存用户数据、文章数据...

    libconhash一致性hash

    在实际应用中,一致性哈希常用于分布式缓存(如Memcached、Redis集群)、分布式数据库分片、负载均衡器等场景,帮助构建可扩展、高可用的分布式系统。 总之,`libconhash`是一个方便的C语言实现的一致性哈希库,...

    分布式设计与开发基础 - 博客频道 - CSDN1

    一致性Hash常用于分布式缓存(如Memcached、Redis集群)和分布式数据库系统,确保数据能在节点之间均匀分布,同时减少因节点变化带来的重新映射成本。 ### 总结 分布式设计与开发需要理解和掌握这些基础算法,如...

    Memcached内存分析、调优、集群.pptx

    1. 一致性Hash:Memcached使用一致性Hash算法来实现分布式缓存。 2. 集群:Memcached支持集群模式,多台服务器组成一个集群,提供高可用性和高性能。 Memcached客户端 1. Memcached客户端:Memcached提供了多种...

    jar包.zip(Nginx的Session一致性,使用memcached解决所需要的jar包)

    在Java Web应用中,...通过以上步骤,我们可以利用memcached实现Nginx下的Session一致性,确保用户在分布式环境中的会话体验。这不仅可以提升应用的可用性和响应速度,还能简化运维,降低因Session丢失导致的问题。

    ConsistentHash(Ketama)

    一致性哈希(Consistent Hashing)是一种分布式哈希(Distributed Hash Table,DHT)算法,主要用于解决在分布式系统中的数据存储和检索问题。在云计算、缓存系统(如Redis、Memcached)以及负载均衡等领域广泛应用...

    memcached-笔记资料

    【标题】"memcached-笔记资料"涉及到的核心...3. "ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf":这篇论文深入探讨了一致性哈希算法...

    一致性hash算法1

    在实际应用中,一致性哈希算法不仅用于分布式缓存系统,还可以用于分布式数据库、CDN内容分发网络等场景,有效解决了动态扩展性和负载均衡的问题。它通过最小化数据迁移,降低了系统在节点变化时的复杂性和性能影响...

    memcached集群linux搭建

    总结来说,构建Memcached集群并在Linux上实现淘宝月光宝盒架构是一项涉及多个步骤的任务,包括安装Memcached、配置集群、设置客户端以及部署和管理MoonBox架构。理解这些概念和技术对于优化大规模Web应用的性能至关...

    memcached和TTserver的使用

    - **分布式一致性**: 实现分布式存储的关键在于客户端的hash机制,一致性哈希算法可以均匀分配数据,减少因节点增减导致的数据迁移。 6. **应用实践**: - **部署策略**: 对于32位系统,可以考虑在同一台机器上...

    Memcached 内存分析、调优、集群

    Memcached分布式:一致性Hash 在分布式环境中,为了实现数据的高效分发,Memcached使用了一致性哈希算法。一致性哈希能够确保即使在网络中添加或删除节点时,数据迁移也尽可能少。 #### 5. Key-Value系统的比较 ...

Global site tag (gtag.js) - Google Analytics