Memcached分散クラスタアルゴリズム

973 ワード

分布式の型取りアルゴリズム
げんり
N個のMemcachedノードは、0->N-1から番号付けされ、keyはNに対して型を取り、残りのiは、keyのi個のノード上にある.
モールドアルゴリズムがキャッシュヒット率に与える影響
仮に8台のサーバがあり、運転中、突然1台ダウンしたとすると、型取り底数が7になってしまうと、命中率が低下して元の1/7にN台のサーバがあり、N-1台となり、N(N-1)あたりの個数のうち、(n-1)個のユニットのみ、%N,%(N-は同じ結果を得るため、命中率はサーバdownの短期間で、(N-1)/(N*(N-1)=1/(N-1)まで急激に低下するので、サーバが多ければ多いほど、ダウンマシンの結果が深刻になる!
コンシステンシハッシュアルゴリズム
げんり
各サーバノードを時計の各時刻にマッピングする、keyも時計のある時刻にマッピングする.このkeyは時計に沿って時計回りに歩いて、出会った第1のノードはこのkeyの記憶ノードの例である:abcdの4つのノードがあると仮定して、平均的に時計の上に分布して、すなわちa 0,b 3 c 6 d 9、keyが記憶して、keyは相応の転化規則で5を得て、keyは時計回りに歩いて、第1のc 6に出会って、keyはcノードが存在します.
              ,      ,          [0,2^32-1]   。
          ,            .        ,             .

コンシステンシハッシュが他のノードに与える影響
あるノードがダウンすると、そのノードが時計回りに1つだけ影響し、他のノードは影響を受けない.従って、Consistent Hashingはキーの再分布を最大限に抑制する
仮想ノード
N個のリアルノードは、各リアルノードをM個のバーチャルノードにマッピングする、M*N個のバーチャルノードを円環上にハッシュする.各リアルノードに対応する仮想ノードが互いに交錯して分布するように、あるリアルノードdown後、その影響を他のすべてのノードに平均的に分担する.