[High Load Website] Fnv算法不好

2010年4月14日 | By C.C. | Filed in: 原创, 未分类.

为什么有这篇blog

BeITMemcached Client这个Memcached的client是.net下开源的实现的相对不错的客户端,其中使用的是修改后的Fnv32算法作为Consistent hashing算法,但是经过测试发现该算法存在很大的问题。于是以.net下的MD5算法为基础修改的算法来替代,结果8错~~~

为什么会有Consistent Hashing算法:

为了更高效更安全更可信赖的Scale-Out

测试方法:
1.假定有3台cache server,图片中黄色文字为cache server的key
2.使用Guid.ToString(’N’)作为测试数据的cache key
3.10,000个测试数据先分布到现有的服务器上,再模拟增加服务器,然后rehash,比较两次分布情况。

【先来看Fnv32算法的改良版使用的情况】

情况1:增加一台cache server后

情况2:增加1倍的cache server后

【使用以MD5为基础改进的算法】

情况1:增加一台cache server后

情况2:增加1倍的cache server后

——总结————-(华丽的分割线)—————————–

【基于Fnv32算法改良版的最大缺陷】

a) 分布不均匀。大多数load balance采用的算法都与这个的结果差不多,第一台server往往会承受较大的压力,所以我们在做负载均衡的时候,第一台服务器都要选择比其他服务器性能更好的。而cache server的最大特点是要保持高命中率,当某台server承载的数据量超过该memcached使用的内存后,就会自动使用老的数据的存储空间来存储新来的数据,那么这台cache server基本上了讲就丧失了cache的功效,增加了系统的压力。

b)某一台server的数据迁移现象非常严重。看书长大的孩子和崇拜技术牛人的孩子一样,总是以最终计算的数字来比较好坏。而distribution和load balance的核心是什么?依照我的经验和认识,这个核心就是符合自然界最基本的规律——平衡,达到均衡的状态,才是优美的。

———-关于cache使用的经验————

根据在.net下使用缓存的经验,就说几点可能大家存在误解的:

1.要缓存的东西本身是比较少的——不要为了使用缓存而增加系统复杂度。
2.有了缓存系统抗压能力可以上升很大,就忽视了db的满载时的处理能力——缓存从业务架构上来讲经常是不可靠的。
3.缓存的关键不是把东西扔到难为GC的地方——缓存要的是命中率,当然如果不是asp.net进程内就没关系。
4.memcached不是万能的——缓存的最大潜力是让数据离执行请求的web server的cpu更近。


发表评论

电子邮件地址不会被公开。 必填项已用*标注