memcached缓存分布式部署方案

一、分布式方案介绍

比较流行的两种方案：

1.取余分布：

计算key的哈希值，与服务器数量取余，得到目标服务器。优点：实现简单，当某台服务器不可用时，故障转移方便；缺点：当增减服务器时， key与服务器取余变动量较大，缓存重组代价极大。

代码实现可参考开源组件memcached.clientlibrary下的sockiopool，源码地址：

https://sourceforge.net/p/memcacheddotnet/code/head/tree/trunk/clientlib/src/clientlib/sockiopool.cs

2.一致性哈希环分布：

其原理参考

这两位老哥写的很清楚和直白，很容易理解。

一致性哈希环分布需要物理节点和虚拟节点，且虚拟节点对应到物理节点的服务器上。

二、代码实现

由于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(2, 32);
将key生成一致性哈希环中的哈希值
        private long generateconsistenthashvalue(string key)
        {
            long serverhv = calculatehashvalue(key);
            long mod = serverhv % hashvalue;
            if (mod < 0)
            {
                mod = mod + hashvalue;
            }
            return mod;
        }

将servers生成节点（物理+虚拟）:

        private void generateserverstobuckets()
        {
            for (int i = 0; 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 > 255)
            {
                throw new argumentexception("每服务器虚拟节点数不能超过254");
            }
            list<string> virtualservers = new list<string>();

            #region 1.按修改ip值+随机guid生成虚拟节点
            string[] ipaddr = server.split(':');
            string ip = ipaddr[0];
            string port = ipaddr[1];
            int header = convert.toint32(ip.split('.')[0]);
            string invariantippart = ip.substring(ip.indexof('.'));
            int succ = 0;
            for (int i = 1; i <= 255; 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 < 0)
            {
                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 == 0)
            {
                return null;
            }

            if (buckets.count == 1)
            {
                return getconnection(buckets[0]);
            }

            long startindex = -1;//开始查找位置，-1表示从hash(key)% hashvalue位置开始查找
            int tries = 0;//重试次数，不超过总服务器数
            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;
        }