MemCache分布式緩存的一個bug

Memcached分布式緩存策略不是由服務器端至支持的，多臺服務器之間并不知道彼此的存在。分布式的實現是由客戶端代碼（Memcached.ClientLibrary）通過緩存key-server映射來實現的，基本原理就是對緩存key求hash值，用hash值對服務器數量進行模運算，該key值被分配到模運算結果為索引的那臺server上。

Memcached.ClientLibrary對緩存key計算hashcode的核心算法如下：

  1 /// <summary>  2 /// Returns apPRopriate SockIO object given  3 /// string cache key and optional hashcode.  4 ///   5 /// Trys to get SockIO from pool.  Fails over  6 /// to additional pools in event of server failure.  7 /// </summary>  8 /// <param name="key">hashcode for cache key</param>  9 /// <param name="hashCode">if not null, then the int hashcode to use</param> 10 /// <returns>SockIO obj connected to server</returns> 11 public SockIO GetSock(string key, object hashCode) 12 { 13     string hashCodeString = "<null>"; 14     if(hashCode != null) 15         hashCodeString = hashCode.ToString(); 16  17     if(Log.IsDebugEnabled) 18     { 19         Log.Debug(GetLocalizedString("cache socket pick").Replace("$$Key$$", key).Replace("$$HashCode$$", hashCodeString)); 20     } 21  22     if (key == null || key.Length == 0) 23     { 24         if(Log.IsDebugEnabled) 25         { 26             Log.Debug(GetLocalizedString("null key")); 27         } 28         return null; 29     } 30  31     if(!_initialized) 32     { 33         if(Log.IsErrorEnabled) 34         { 35             Log.Error(GetLocalizedString("get socket from uninitialized pool")); 36         } 37         return null; 38     } 39  40     // if no servers return null 41     if(_buckets.Count == 0) 42         return null; 43  44     // if only one server, return it 45     if(_buckets.Count == 1) 46         return GetConnection((string)_buckets[0]); 47  48     int tries = 0; 49  50     // generate hashcode 51     int hv; 52     if(hashCode != null) 53     { 54         hv = (int)hashCode; 55     } 56     else 57     { 58  59         // NATIVE_HASH = 0 60         // OLD_COMPAT_HASH = 1 61         // NEW_COMPAT_HASH = 2 62         switch(_hashingAlgorithm) 63         { 64             case HashingAlgorithm.Native: 65                 hv = key.GetHashCode(); 66                 break; 67  68             case HashingAlgorithm.OldCompatibleHash: 69                 hv = OriginalHashingAlgorithm(key); 70                 break; 71  72             case HashingAlgorithm.NewCompatibleHash: 73                 hv = NewHashingAlgorithm(key); 74                 break; 75  76             default: 77                 // use the native hash as a default 78                 hv = key.GetHashCode(); 79                 _hashingAlgorithm = HashingAlgorithm.Native; 80                 break; 81         } 82     } 83  84     // keep trying different servers until we find one 85     while(tries++ <= _buckets.Count) 86     { 87         // get bucket using hashcode  88         // get one from factory 89         int bucket = hv % _buckets.Count; 90         if(bucket < 0) 91             bucket += _buckets.Count; 92  93         SockIO sock = GetConnection((string)_buckets[bucket]); 94  95         if(Log.IsDebugEnabled) 96         { 97             Log.Debug(GetLocalizedString("cache choose").Replace("$$Bucket$$", _buckets[bucket].ToString()).Replace("$$Key$$", key)); 98         } 99 100         if(sock != null)101             return sock;102 103         // if we do not want to failover, then bail here104         if(!_failover)105             return null;106 107         // if we failed to get a socket from this server108         // then we try again by adding an incrementer to the109         // current key and then rehashing 110         switch(_hashingAlgorithm)111         {112             case HashingAlgorithm.Native:113                 hv += ((string)("" + tries + key)).GetHashCode();114                 break;115 116             case HashingAlgorithm.OldCompatibleHash:117                 hv += OriginalHashingAlgorithm("" + tries + key);118                 break;119 120             case HashingAlgorithm.NewCompatibleHash:121                 hv += NewHashingAlgorithm("" + tries + key);122                 break;123 124             default:125                 // use the native hash as a default126                 hv += ((string)("" + tries + key)).GetHashCode();127                 _hashingAlgorithm = HashingAlgorithm.Native;128                 break;129         }130     }131 132     return null;133 }

從源碼中（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;