大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C#技巧 > MemCache分布式缓存的一个bug

MemCache分布式缓存的一个bug

关键词:分布式缓存MemCachebug  阅读(1725) 赞(20)

[摘要]本文是对MemCache分布式缓存的一个bug的讲解,对学习C#编程技术有所帮助,与大家分享。

Memcached分布式缓存策略不是由服务器端至支持的,多台服务器之间并不知道彼此的存在。分布式的实现是由客户端代码(Memcached.ClientLibrary)通过缓存key-server映射来实现的,基本原理就是对缓存key求hash值,用hash值对服务器数量进行模运算,该key值被分配到模运算结果为索引的那台server上。

Memcached.ClientLibrary对缓存key计算hashcode的核心算法如下:

 /// <summary>
 /// Returns appropriate SockIO object given
 /// string cache key and optional hashcode.
 /// 
 /// Trys to get SockIO from pool.  Fails over
 /// to additional pools in event of server failure.
 /// </summary>
 /// <param name="key">hashcode for cache key</param>
 /// <param name="hashCode">if not null, then the int hashcode to use</param>
 /// <returns>SockIO obj connected to server</returns>
 public SockIO GetSock(string key, object hashCode)
 {
     string hashCodeString = "<null>";
     if(hashCode != null)
         hashCodeString = hashCode.ToString();
 
     if(Log.IsDebugEnabled)
     {
         Log.Debug(GetLocalizedString("cache socket pick").Replace("$$Key$$", key).Replace("$$HashCode$$", hashCodeString));
     }
 
     if (key == null || key.Length == 0)
     {
         if(Log.IsDebugEnabled)
         {
             Log.Debug(GetLocalizedString("null key"));
         }
         return null;
     }
 
     if(!_initialized)
     {
         if(Log.IsErrorEnabled)
         {
             Log.Error(GetLocalizedString("get socket from uninitialized pool"));
         }
         return null;
     }
 
     // if no servers return null
     if(_buckets.Count == 0)
         return null;
 
     // if only one server, return it
     if(_buckets.Count == 1)
         return GetConnection((string)_buckets[0]);
 
     int tries = 0;
 
     // generate hashcode
     int hv;
     if(hashCode != null)
     {
         hv = (int)hashCode;
     }
     else
     {
 
         // NATIVE_HASH = 0
         // OLD_COMPAT_HASH = 1
         // NEW_COMPAT_HASH = 2
         switch(_hashingAlgorithm)
         {
             case HashingAlgorithm.Native:
                 hv = key.GetHashCode();
                 break;
 
             case HashingAlgorithm.OldCompatibleHash:
                 hv = OriginalHashingAlgorithm(key);
                 break;
 
             case HashingAlgorithm.NewCompatibleHash:
                 hv = NewHashingAlgorithm(key);
                 break;
 
             default:
                 // use the native hash as a default
                 hv = key.GetHashCode();
                 _hashingAlgorithm = HashingAlgorithm.Native;
                 break;
         }
     }
 
     // keep trying different servers until we find one
     while(tries++ <= _buckets.Count)
     {
         // get bucket using hashcode 
         // get one from factory
         int bucket = hv % _buckets.Count;
         if(bucket < 0)
             bucket += _buckets.Count;
 
         SockIO sock = GetConnection((string)_buckets[bucket]);
 
         if(Log.IsDebugEnabled)
         {
             Log.Debug(GetLocalizedString("cache choose").Replace("$$Bucket$$", _buckets[bucket].ToString()).Replace("$$Key$$", key));
         }
 
         if(sock != null)
             return sock;
 
         // if we do not want to failover, then bail here
         if(!_failover)
             return null;
 
         // if we failed to get a socket from this server
         // then we try again by adding an incrementer to the
         // current key and then rehashing 
         switch(_hashingAlgorithm)
         {
             case HashingAlgorithm.Native:
                 hv += ((string)("" + tries + key)).GetHashCode();
                 break;
 
             case HashingAlgorithm.OldCompatibleHash:
                 hv += OriginalHashingAlgorithm("" + tries + key);
                 break;
 
             case HashingAlgorithm.NewCompatibleHash:
                 hv += NewHashingAlgorithm("" + tries + key);
                 break;
 
             default:
                 // use the native hash as a default
                 hv += ((string)("" + tries + key)).GetHashCode();
                 _hashingAlgorithm = HashingAlgorithm.Native;
                 break;
         }
     }
 
     return null;
 }
根据缓存key得到服务器的核心代码

从源码中(62--82行代码)可以发现,计算hashcode的算法共三种:

(1)HashingAlgorithm.Native: 即使用.NET本身的hash算法,速度快,但与其他client可能不兼容,例如需要和java、ruby的client共享缓存的情况;

(2)HashingAlgorithm.OldCompatibleHash: 可以与其他客户端兼容,但速度慢;

(3)HashingAlgorithm.NewCompatibleHash: 可以与其他客户端兼容,据称速度快。

进一步分析发现,Memcached.ClientLibrary默认计算缓存key的hashcode的方式就是HashingAlgorithm.Native,而HashingAlgorithm.Native计算hashcode的算法为“hv = key.GetHashCode()”,即用了.net类库string类型自带的GetHashCode()方法。

Bug就要浮现出来了,根据微软(http://msdn.microsoft.com/zh-cn/library/system.object.gethashcode.aspx)对GetHashCode的解释:the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value this method returns may differ between .NET Framework versions and platforms, such as 32-bit and 64-bit platforms。string类型的GetHashCode()函数并不能保证不同平台同一个字符串返回的hash值相同,这样问题就出来了,对于不同服务器的同一缓存key来说,产生的hashcode可能不同,同一key对应的数据可能缓存到了不同的MemCache服务器上,数据的一致性无法保证,清除缓存的代码也可能失效。

// 64位 4.0
[__DynamicallyInvokable, ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical]
public unsafe override int GetHashCode()
{
    if (HashHelpers.s_UseRandomizedStringHashing)
    {
        return string.InternalMarvin32HashString(this, this.Length, 0L);
    }
    IntPtr arg_25_0;
    IntPtr expr_1C = arg_25_0 = this;
    if (expr_1C != 0)
    {
        arg_25_0 = (IntPtr)((int)expr_1C + RuntimeHelpers.OffsetToStringData);
    }
    char* ptr = arg_25_0;
    int num = 5381;
    int num2 = num;
    char* ptr2 = ptr;
    int num3;
    while ((num3 = (int)(*(ushort*)ptr2)) != 0)
    {
        num = ((num << 5) + num ^ num3);
        num3 = (int)(*(ushort*)(ptr2 + (IntPtr)2 / 2));
        if (num3 == 0)
        {
            break;
        }
        num2 = ((num2 << 5) + num2 ^ num3);
        ptr2 += (IntPtr)4 / 2;
    }
    return num + num2 * 1566083941;
}


// 64位 2.0
// string
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public unsafe override int GetHashCode()
{
    IntPtr arg_0F_0;
    IntPtr expr_06 = arg_0F_0 = this;
    if (expr_06 != 0)
    {
        arg_0F_0 = (IntPtr)((int)expr_06 + RuntimeHelpers.OffsetToStringData);
    }
    char* ptr = arg_0F_0;
    int num = 5381;
    int num2 = num;
    char* ptr2 = ptr;
    int num3;
    while ((num3 = (int)(*(ushort*)ptr2)) != 0)
    {
        num = ((num << 5) + num ^ num3);
        num3 = (int)(*(ushort*)(ptr2 + (IntPtr)2 / 2));
        if (num3 == 0)
        {
            break;
        }
        num2 = ((num2 << 5) + num2 ^ num3);
        ptr2 += (IntPtr)4 / 2;
    }
    return num + num2 * 1566083941;
}

//32位 4.0
[__DynamicallyInvokable, ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical]
public unsafe override int GetHashCode()
{
    if (HashHelpers.s_UseRandomizedStringHashing)
    {
        return string.InternalMarvin32HashString(this, this.Length, 0L);
    }
    IntPtr arg_25_0;
    IntPtr expr_1C = arg_25_0 = this;
    if (expr_1C != 0)
    {
        arg_25_0 = (IntPtr)((int)expr_1C + RuntimeHelpers.OffsetToStringData);
    }
    char* ptr = arg_25_0;
    int num = 352654597;
    int num2 = num;
    int* ptr2 = (int*)ptr;
    int i;
    for (i = this.Length; i > 2; i -= 4)
    {
        num = ((num << 5) + num + (num >> 27) ^ *ptr2);
        num2 = ((num2 << 5) + num2 + (num2 >> 27) ^ ptr2[(IntPtr)4 / 4]);
        ptr2 += (IntPtr)8 / 4;
    }
    if (i > 0)
    {
        num = ((num << 5) + num + (num >> 27) ^ *ptr2);
    }
    return num + num2 * 1566083941;
}
GetHashCode几种版本的实现代码

解决问题的方法就是不要用MemCache默认的hash算法,实现方式有两种:

(1)初始化MemCache服务器的时候,指定为MemCahce自带其它的hash算法,代码为“this.pool.HashingAlgorithm = HashingAlgorithm.OldCompatibleHash;”。

(2)自定义hash算法,调用set()、get()、delete()等方式时传递hash值,这几个方法有参数传递hashcode的重载。

参考资料:分析Memcached客户端如何把缓存数据分布到多个服务器上(转)、memcached client - memcacheddotnet (Memcached.ClientLibrary) 1.1.5、memcache分布式实现、Object.GetHashCode 方法、关于 HashCode做key的可能性。



相关评论