memcached缓存分布式部署方案
一、分布式方案介绍
比较流行的两种方案：
1.取余分布：
计算key的哈希值，与服务器数量取余，得到目标服务器。优点：实现简单，当某台服务器不可用时，故障转移方便；缺点：当增减服务器时， Key与服务器取余变动量较大，缓存重组代价极大。
代码实现可参考开源组件Memcached.ClientLibrary下的SockIOPool，源码地址：
https://sourceforge.net/p/memcacheddotnet/code/HEAD/tree/trunk/clientlib/src/clientlib/SockIOPool.cs
2.一致性哈希环分布：
其原理参考
https://www.cnblogs.com/lpfuture/p/5796398.html
http://www.zsythink.net/archives/1182
这两位老哥写的很清楚和直白，很容易理解。
一致性哈希环分布需要物理节点和虚拟节点，且虚拟节点对应到物理节点的服务器上。
二、代码实现
由于Memcached.ClientLibrary的作者已出取余分布的实现，这里不再叙述，以下代码和测试均是一致性哈希分布的。
1.数据结构：
服务器列表：List<string> servers；//IP:PORT
服务器虚拟节点数：List<int> weights；//与servers一一对应，灵活设置每server的不同虚拟节点数
节点存储结构：SortedDictionary<long, String> buckets;
Key：long类型，存储节点的hash%2^32；
Value：String类型，存储节点，即IP:PORT；
2.代码
计算哈希值算法，参考Memcached.ClientLibrary下的SockIOPool：
https://sourceforge.net/p/memcacheddotnet/code/HEAD/tree/trunk/clientlib/src/clientlib/SockIOPool.cs
private int CalculateHashValue(String key)
{
int hv;
switch (_hashingAlgorithm)
{
case EnumHashingAlgorithm.Native:
hv = key.GetHashCode();
break;
case EnumHashingAlgorithm.OldCompatibleHash:
hv = HashingAlgorithmTool.OriginalHashingAlgorithm(key);
break;
case EnumHashingAlgorithm.NewCompatibleHash:
hv = HashingAlgorithmTool.NewHashingAlgorithm(key);
break;
default:
// use the native hash as a default
hv = key.GetHashCode();
_hashingAlgorithm = EnumHashingAlgorithm.Native;
break;
}
return hv;
}
经过测试，OldCompatibleHash方式计算的哈希值比较散列。
//哈希取余值，为什么是2的32次方：IPV4的总量是2的32次方个，可以保证环上的IP不重复
long HashValue = (long)Math.Pow(, );
将Key生成一致性哈希环中的哈希值
private long GenerateConsistentHashValue(String key)
{
long serverHV = CalculateHashValue(key);
long mod = serverHV % HashValue;
if (mod < )
{
mod = mod + HashValue;
}
return mod;
}
将Servers生成节点（物理+虚拟）:
private void GenerateServersToBuckets()
{
for (int i = ; i < _servers.Count; i++)
{
// 创建物理节点
String server = _servers[i];
long mod = GenerateConsistentHashValue(server);
buckets.Add(mod, server);
//创建虚拟节点
List<String> virtualHostServers = GenerateVirtualServer(server, this.Weights[i]);
foreach (String v in virtualHostServers)
{
mod = GenerateConsistentHashValue(v);
buckets.Add(mod, server);
}
}
}
根据物理节点生成虚拟节点
private static List<String> GenerateVirtualServer(String server, int count)
{
if (count > )
{
throw new ArgumentException("每服务器虚拟节点数不能超过254");
}
List<String> virtualServers = new List<string>(); #region 1.按修改IP值+随机GUID生成虚拟节点
String[] ipaddr = server.Split(':');
String ip = ipaddr[];
string port = ipaddr[];
int header = Convert.ToInt32(ip.Split('.')[]);
String invariantIPPart = ip.Substring(ip.IndexOf('.'));
int succ = ;
for (int i = ; i <= ; i++)
{
if (i != header)
{
String virtualServer = i.ToString() + invariantIPPart + ":" + port + i;// Guid.NewGuid().ToString("N").ToUpper();
virtualServers.Add(virtualServer);
succ++;
}
if (succ == count)
{
break;
}
}
#endregion #region 2.物理节点自增序号||随机GUID
//for (int i = 0; i < count; i++)
//{
// //virtualServers.Add(server + i.ToString());
// virtualServers.Add(server + i.ToString()+Guid.NewGuid().ToString());
//}
#endregion #region 32.其它生成算法
//TODO
#endregion return virtualServers;
}
三、节点分布测试
四台服务器：{ "192.168.1.100:11211", "192.168.1.101:11211", "192.168.1.102:11211", "192.168.1.103:11211" }
哈希算法不同，则节点分布规则不同
1.物理节点分布
2．每物理节点10虚拟节点
节点分布测试结果：
节点数共有（物理4+虚拟4*10）：44
在第一个节点和第二个节点间：
服务器A的虚拟节点数：1 占比：10%
服务器B的虚拟节点数：1 占比：10%
服务器C的虚拟节点数：0 占比：0%
服务器D的虚拟节点数：2 占比：20%
在第二个节点和第三个节点间：
服务器A的虚拟节点数：0 占比：0%
服务器B的虚拟节点数：0 占比：0%
服务器C的虚拟节点数：2 占比：20%
服务器D的虚拟节点数：2 占比：20%
在第三个节点和第四个节点间：
服务器A的虚拟节点数：4 占比：40%
服务器B的虚拟节点数：5 占比：50%
服务器C的虚拟节点数：4 占比：40%
服务器D的虚拟节点数：4 占比：40%
在第四个节点和第一个节点间：
服务器A的虚拟节点数：5 占比：50%
服务器B的虚拟节点数：4 占比：40%
服务器C的虚拟节点数：4 占比：40%
服务器D的虚拟节点数：2 占比：20%
3.每物理节点30虚拟节点
节点分布测试结果：
节点数共有（物理4+虚拟4*30）：124
在第一个节点和第二个节点间：
服务器A的虚拟节点数：7 占比：23%
服务器B的虚拟节点数：7 占比：23%
服务器C的虚拟节点数：6 占比：20%
服务器D的虚拟节点数：7 占比：23%
在第二个节点和第三个节点间：
服务器A的虚拟节点数：3 占比：10%
服务器B的虚拟节点数：1 占比：3%
服务器C的虚拟节点数：4 占比：13%
服务器D的虚拟节点数：4 占比：13%
在第三个节点和第四个节点间：
服务器A的虚拟节点数：11 占比：36%
服务器B的虚拟节点数：11 占比：36%
服务器C的虚拟节点数：10 占比：33%
服务器D的虚拟节点数：10 占比：33%
在第四个节点和第一个节点间：
服务器A的虚拟节点数：9 占比：30%
服务器B的虚拟节点数：11 占比：36%
服务器C的虚拟节点数：10 占比：33%
服务器D的虚拟节点数：9 占比：30%
4. 每物理节点50虚拟节点：.
节点分布测试结果：
节点数共有（物理4+虚拟4*50）：204
在第一个节点和第二个节点间：
服务器A的虚拟节点数：14 占比：28%
服务器B的虚拟节点数：13 占比：26%
服务器C的虚拟节点数：12 占比：24%
服务器D的虚拟节点数：13 占比：26%
在第二个节点和第三个节点间：
服务器A的虚拟节点数：4 占比：8%
服务器B的虚拟节点数：3 占比：6%
服务器C的虚拟节点数：5 占比：10%
服务器D的虚拟节点数：7 占比：14%
在第三个节点和第四个节点间：
服务器A的虚拟节点数：17 占比：34%
服务器B的虚拟节点数：18 占比：36%
服务器C的虚拟节点数：16 占比：32%
服务器D的虚拟节点数：16 占比：32%
在第四个节点和第一个节点间：
服务器A的虚拟节点数：15 占比：30%
服务器B的虚拟节点数：16 占比：32%
服务器C的虚拟节点数：17 占比：34%
服务器D的虚拟节点数：14 占比：28%
5. 每物理节点80虚拟节点
节点分布测试结果：
节点数共有（物理4+虚拟4*80）：324
在第一个节点和第二个节点间：
服务器A的虚拟节点数：22 占比：27%
服务器B的虚拟节点数：23 占比：28%
服务器C的虚拟节点数：21 占比：26%
服务器D的虚拟节点数：22 占比：27%
在第二个节点和第三个节点间：
服务器A的虚拟节点数：7 占比：8%
服务器B的虚拟节点数：5 占比：6%
服务器C的虚拟节点数：9 占比：11%
服务器D的虚拟节点数：10 占比：12%
在第三个节点和第四个节点间：
服务器A的虚拟节点数：27 占比：33%
服务器B的虚拟节点数：27 占比：33%
服务器C的虚拟节点数：25 占比：31%
服务器D的虚拟节点数：24 占比：30%
在第四个节点和第一个节点间：
服务器A的虚拟节点数：24 占比：30%
服务器B的虚拟节点数：25 占比：31%
服务器C的虚拟节点数：25 占比：31%
服务器D的虚拟节点数：24 占比：30%
6. 每物理节点100虚拟节点
节点分布测试结果：
节点数共有（物理4+虚拟4*100）：404
在第一个节点和第二个节点间：
服务器A的虚拟节点数：29 占比：29%
服务器B的虚拟节点数：30 占比：30%
服务器C的虚拟节点数：28 占比：28%
服务器D的虚拟节点数：28 占比：28%
在第二个节点和第三个节点间：
服务器A的虚拟节点数：8 占比：8%
服务器B的虚拟节点数：8 占比：8%
服务器C的虚拟节点数：11 占比：11%
服务器D的虚拟节点数：12 占比：12%
在第三个节点和第四个节点间：
服务器A的虚拟节点数：33 占比：33%
服务器B的虚拟节点数：32 占比：32%
服务器C的虚拟节点数：30 占比：30%
服务器D的虚拟节点数：30 占比：30%
在第四个节点和第一个节点间：
服务器A的虚拟节点数：30 占比：30%
服务器B的虚拟节点数：30 占比：30%
服务器C的虚拟节点数：31 占比：31%
服务器D的虚拟节点数：30 占比：30%
说明：由于统计计算时按int取值，服务器虚拟节点比率总和可能有1的误差。
总结：以上可以看出当总节点在300以上时，各物理节点之间的虚拟节点所占比率变化较小，说明分布比较均匀。
四、存取数据查找服务器
原理：根据数据的Key与HashValue取余值hv，查找buckets中Key>=hv的第一个服务器，即是Key的目标服务器，当返回的服务器不可用时，还可以进行故障转移
1.从节点环中查找服务器
private String FindServer(String key, ref long startIndex)
{
long mod = startIndex;
if (mod < )
{
mod = GenerateConsistentHashValue(key);
}
foreach (KeyValuePair<long, String> kvp in buckets)
{
startIndex = kvp.Key;
//找到第一个大于或等于key的服务器
if (kvp.Key >= mod)
{
//若找到的服务器不可用，则继续查找下一服务器
if (_hostDead.ContainsKey(kvp.Value))
{
continue;
}
return kvp.Value;
}
}
//如果大于mod的服务器均不可用或没有找到，则从头开始找可用服务器
foreach (KeyValuePair<long, String> kvp in buckets)
{
startIndex = kvp.Key;
if (kvp.Key >= mod)
{
break;
}
if (_hostDead.ContainsKey(kvp.Value))
{
continue;
}
return kvp.Value;
}
//不存在可用服务器
return string.Empty;
}
2.获取服务器及连接
public ISockIO GetSock(string key)
{
if (buckets.Count == )
{
return null;
} if (buckets.Count == )
{
return GetConnection(buckets[]);
} long startIndex = -;//开始查找位置，-1表示从hash(key)% HashValue位置开始查找
int tries = ;//重试次数，不超过总服务器数
while (tries++ <= this.servers.Count)
{
String server = FindServer(key, ref startIndex);
//找不到可用的服务器
if (String.IsNullOrEmpty(server))
{
return null;
}
ISockIO sock = GetConnection(server);
if (sock != null)
{
WriteLog.Write("key：" + key + ",server：" + server);
return sock;
}
//是否需要故障转移，若需要，则会继续查找可用的服务器
if (!_failover)
{
return null;
}
}
return null;
}
最新文章
- 【转】WiFi基础知识
- Java多线程与并发库高级应用-Callable与Future的应用
- 关于offer选择
- sql 字段重复值，in，like
- Javascript 去掉字符串前后空格的五种方法
- 第二百四十八天 how can I 坚持
- WordLight: highlights all occurrences of a selected text for VS2008
- C#语法糖之第一篇:自动属性&隐式类型
- Java基础知识强化之集合框架笔记08：Collection集合自定义对象并遍历案例（使用迭代器）
- Android ART
- calc() ---一个会计算的css属性
- python入门（11）条件判断和循环
- Web Service进阶(二)如何用Apache TCPMon来截获SOAP消息
- jforum（2）--中文乱码的解决方式
- 关于JBoss7.X修改post传输数据量（max-post-size）的问题
- BP神经网络的理论理论常识
- 关于Web中列表页面的加载问题
- Java实现简单的正则表达式匹配
- mac 必备工具
- HashMap源码分析-基于JDK1.8