囲碁の一貫したハッシュ.

Go - zeroの分散キャッシュ実装では、一貫したハッシュアルゴリズムを使いました.この記事では、我々は一貫したハッシュのアルゴリズムとGo - zeroでのその実装詳細について話します.
ストレージを例として、ストレージが全体のマイクロサービスシステムの一つのノードであると言うことは不可能です.

まず第一に、安定性を改善することです.単一のノードがダウンすると、ストレージ全体がサービス不可可用性に直面しています.

第2に、データフォールトトレランスのために.単一ノードデータ損失はデータ損失を引き起こす.マルチノードの場合は、相互バックアップノードが同時に破壊されない限り、ノードはバックアップを持っています.

それで、質問は起こります.そして、どのノードがデータをマルチノード・ケースに書かなければなりませんか?

ハッシュ

本質的に:私たちは、“圧縮”**であることができる入力値を必要とし、より小さな値に変換されます.

同一の値でハッシュが計算されるたびに、同じ値が得られることを保証しなければなりません

これがhash アルゴリズムは.
でも普通にhash ルーティングのアルゴリズム、例えばkey % N . ノードが例外またはハートビート例外のためにクラスタから降りるならばhash route 多くのデータをredistributed を返します.ノードが新しい要求を受け入れるとき、それはデータを得るために論理を再処理する必要があります:キャッシュにあるならば、それは簡単にキャッシュなだれを引き起こすことができます.
この場合、それを導入する必要がありますconsistent hash アルゴリズム.

一貫したハッシュ

見ましょうconsistent hash これらの問題を解決します.

再ハッシュする

大質量を解くことから始めましょうrehash 問題

上に示されるように、新しいノードが加えられるとき、影響を受ける唯一のキーはそうですkey31 . 新しいノードが追加(削除)されると、そのノードの近くのデータだけが影響を受けます.他のノードのデータは影響を受けないので、ノードの変更の問題を解決します.
これはまさに単調性です.これも理由ですnormal hash アルゴリズムは分散シナリオを満足できない.

データ歪曲

事実上、上記の図は、キーの大部分が現在集中していることを示しますnode 1 . ノードの数が比較的小さい場合、あるキーに集中しているほとんどのキーをトリガーすることができますnode , 監視時の問題点:ノード間の不均一な負荷.
この問題を解決するにはconsistent hash コンセプトを紹介virtual node .
負荷が不均一であるので、我々は人工的にバランスのよいシナリオを構築します、しかし、実際のノードだけがあります.だから我々はvirtual node 領域を分割するには、実際のノードが提供している間はまだ前のものと同じです.

具体的実施

始めましょうGet() .

ゲット

まず、実装の原理について話しましょう.

ハッシュ計算key

最初のマッチングのインデックスを探すvirtual node を返し、対応するh.keys[index] : 仮想ノードハッシュ値

これにring そしてactual node マッチ

実際、我々はそれを見ることができますring Aを得る[]node . これは計算でvirtual node hash , ハッシュコンフリクトがあるかもしれませんvirtual node hash 実際のノードに対応します.
これもnode and virtual node は、1対多の関係にある.とring 内部は以下のデザインです.

これは、一貫性ハッシュの配分戦略を実際に示します.

virtual node 値のドメイン分割として使用されます.The key はnode , これはvirtual node .

virtual node 異なるノードに割り当てられたキーがほぼ均等に分配されることを保証するhash . すなわち、分割結合.

新しいノードが追加されると、複数のvirtual nodes が割り当てられる.新しいノードは複数の既存のノードの圧力をロードすることができます.そして、それはグローバルな視点から容量を拡大するとき、それが簡単にロードバランシングを成し遂げるのをより簡単にします.

ノードの追加

読書の後Get , 全体的に一貫したハッシュがどのように設計されているかを実際に知っています.

type ConsistentHash struct {
  hashFunc Func // hash function
  replicas int // virtual node amplification factor
  keys []uint64 // store virtual node hash
  ring map[uint64][]interface{} // virtual node to actual node correspondence
  nodes map[string]lang.PlaceholderType // actual node storage [easy to find quickly, so use map]
  lock sync.RWMutex
}

基本的に一貫したハッシュが完全に実装されるように.

code: https://github.com/zeromicro/go-zero/blob/master/core/hash/consistenthash.go

使用シナリオ

最初に、一貫性ハッシュが分散システムで広く使われることができると言います.

分散キャッシュあなたはcache proxy ストレージシステム上でredis cluster そして、ルーティングを自由に制御します.このルーティング規則のために、我々は一貫したハッシュアルゴリズムを使用できます

サービス発見

タスクの分散スケジューリング

上記の分散システムは全て負荷分散モジュールで使用できる.

プロジェクトアドレス

https://github.com/zeromicro/go-zero
ようこそゼロと星を使用して私たちをサポートする!