GoLang实现一致性哈希算法

<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg>

直接上代码，windows7，go1.7下直接运行。

<pre class="prettyprint"><code class=" hljs go"><span class="hljs-keyword">package</span> main <span class="hljs-keyword">import</span> ( <span class="hljs-string">"fmt"</span> <span class="hljs-string">"sort"</span> <span class="hljs-string">"strconv"</span> <span class="hljs-string">"hash/crc32"</span> <span class="hljs-string">"sync"</span> ) <span class="hljs-keyword">const</span> DEFAULT_REPLICAS =<span class="hljs-number"> 160</span> <span class="hljs-keyword">type</span> HashRing []<span class="hljs-typename">uint32</span> <span class="hljs-keyword">func</span> (c HashRing) Len() <span class="hljs-typename">int</span> { <span class="hljs-keyword">return</span> <span class="hljs-built_in">len</span>(c) } <span class="hljs-keyword">func</span> (c HashRing) Less(i, j <span class="hljs-typename">int</span>) <span class="hljs-typename">bool</span> { <span class="hljs-keyword">return</span> c[i] < c[j] } <span class="hljs-keyword">func</span> (c HashRing) Swap(i, j <span class="hljs-typename">int</span>) { c[i], c[j] = c[j], c[i] } <span class="hljs-keyword">type</span> Node <span class="hljs-keyword">struct</span> { Id <span class="hljs-typename">int</span> Ip <span class="hljs-typename">string</span> Port <span class="hljs-typename">int</span> HostName <span class="hljs-typename">string</span> Weight <span class="hljs-typename">int</span> } <span class="hljs-keyword">func</span> NewNode(id <span class="hljs-typename">int</span>, ip <span class="hljs-typename">string</span>, port <span class="hljs-typename">int</span>, name <span class="hljs-typename">string</span>, weight <span class="hljs-typename">int</span>) *Node { <span class="hljs-keyword">return</span> &Node{ Id: id, Ip: ip, Port: port, HostName: name, Weight: weight, } } <span class="hljs-keyword">type</span> Consistent <span class="hljs-keyword">struct</span> { Nodes <span class="hljs-keyword">map</span>[<span class="hljs-typename">uint32</span>]Node numReps <span class="hljs-typename">int</span> Resources <span class="hljs-keyword">map</span>[<span class="hljs-typename">int</span>]<span class="hljs-typename">bool</span> ring HashRing sync.RWMutex } <span class="hljs-keyword">func</span> NewConsistent() *Consistent { <span class="hljs-keyword">return</span> &Consistent{ Nodes: <span class="hljs-built_in">make</span>(<span class="hljs-keyword">map</span>[<span class="hljs-typename">uint32</span>]Node), numReps: DEFAULT_REPLICAS, Resources: <span class="hljs-built_in">make</span>(<span class="hljs-keyword">map</span>[<span class="hljs-typename">int</span>]<span class="hljs-typename">bool</span>), ring: HashRing{}, } } <span class="hljs-keyword">func</span> (c *Consistent) Add(node *Node) <span class="hljs-typename">bool</span> { c.Lock() <span class="hljs-keyword">defer</span> c.Unlock() <span class="hljs-keyword">if</span> _, ok := c.Resources[node.Id]; ok { <span class="hljs-keyword">return</span> <span class="hljs-constant">false</span> } count := c.numReps * node.Weight <span class="hljs-keyword">for</span> i :=<span class="hljs-number"> 0</span>; i < count; i { str := c.joinStr(i, node) c.Nodes[c.hashStr(str)] = *(node) } c.Resources[node.Id] = <span class="hljs-constant">true</span> c.sortHashRing() <span class="hljs-keyword">return</span> <span class="hljs-constant">true</span> } <span class="hljs-keyword">func</span> (c *Consistent) sortHashRing() { c.ring = HashRing{} <span class="hljs-keyword">for</span> k := <span class="hljs-keyword">range</span> c.Nodes { c.ring = <span class="hljs-built_in">append</span>(c.ring, k) } sort.Sort(c.ring) } <span class="hljs-keyword">func</span> (c *Consistent) joinStr(i <span class="hljs-typename">int</span>, node *Node) <span class="hljs-typename">string</span> { <span class="hljs-keyword">return</span> node.Ip <span class="hljs-string">"*"</span> strconv.Itoa(node.Weight) <span class="hljs-string">"-"</span> strconv.Itoa(i) <span class="hljs-string">"-"</span> strconv.Itoa(node.Id) } <span class="hljs-comment">// MurMurHash算法 :https://github.com/spaolacci/murmur3</span> <span class="hljs-keyword">func</span> (c *Consistent) hashStr(key <span class="hljs-typename">string</span>) <span class="hljs-typename">uint32</span> { <span class="hljs-keyword">return</span> crc32.ChecksumIEEE([]<span class="hljs-typename">byte</span>(key)) } <span class="hljs-keyword">func</span> (c *Consistent) Get(key <span class="hljs-typename">string</span>) Node { c.RLock() <span class="hljs-keyword">defer</span> c.RUnlock() hash := c.hashStr(key) i := c.search(hash) <span class="hljs-keyword">return</span> c.Nodes[c.ring[i]] } <span class="hljs-keyword">func</span> (c *Consistent) search(hash <span class="hljs-typename">uint32</span>) <span class="hljs-typename">int</span> { i := sort.Search(<span class="hljs-built_in">len</span>(c.ring), <span class="hljs-keyword">func</span>(i <span class="hljs-typename">int</span>) <span class="hljs-typename">bool</span> { <span class="hljs-keyword">return</span> c.ring[i] >= hash }) <span class="hljs-keyword">if</span> i < <span class="hljs-built_in">len</span>(c.ring) { <span class="hljs-keyword">if</span> i == <span class="hljs-built_in">len</span>(c.ring<span class="hljs-number">)-1</span> { <span class="hljs-keyword">return</span><span class="hljs-number"> 0</span> } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">return</span> i } } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">return</span> <span class="hljs-built_in">len</span>(c.ring) -<span class="hljs-number"> 1</span> } } <span class="hljs-keyword">func</span> (c *Consistent) Remove(node *Node) { c.Lock() <span class="hljs-keyword">defer</span> c.Unlock() <span class="hljs-keyword">if</span> _, ok := c.Resources[node.Id]; !ok { <span class="hljs-keyword">return</span> } <span class="hljs-built_in">delete</span>(c.Resources, node.Id) count := c.numReps * node.Weight <span class="hljs-keyword">for</span> i :=<span class="hljs-number"> 0</span>; i < count; i { str := c.joinStr(i, node) <span class="hljs-built_in">delete</span>(c.Nodes, c.hashStr(str)) } c.sortHashRing() } <span class="hljs-keyword">func</span> main() { cHashRing := NewConsistent() <span class="hljs-keyword">for</span> i :=<span class="hljs-number"> 0</span>; i <<span class="hljs-number"> 10</span>; i { si := fmt.Sprintf(<span class="hljs-string">"%d"</span>, i) cHashRing.Add(NewNode(i, <span class="hljs-string">"172.18.1."</span> si,<span class="hljs-number"> 8080</span>, <span class="hljs-string">"host_"</span> si,<span class="hljs-number"> 1</span>)) } <span class="hljs-keyword">for</span> k, v := <span class="hljs-keyword">range</span> cHashRing.Nodes { fmt.Println(<span class="hljs-string">"Hash:"</span>, k, <span class="hljs-string">" IP:"</span>, v.Ip) } ipMap := <span class="hljs-built_in">make</span>(<span class="hljs-keyword">map</span>[<span class="hljs-typename">string</span>]<span class="hljs-typename">int</span>,<span class="hljs-number"> 0</span>) <span class="hljs-keyword">for</span> i :=<span class="hljs-number"> 0</span>; i <<span class="hljs-number"> 1000</span>; i { si := fmt.Sprintf(<span class="hljs-string">"key%d"</span>, i) k := cHashRing.Get(si) <span class="hljs-keyword">if</span> _, ok := ipMap[k.Ip]; ok { ipMap[k.Ip] =<span class="hljs-number"> 1</span> } <span class="hljs-keyword">else</span> { ipMap[k.Ip] =<span class="hljs-number"> 1</span> } } <span class="hljs-keyword">for</span> k, v := <span class="hljs-keyword">range</span> ipMap { fmt.Println(<span class="hljs-string">"Node IP:"</span>, k, <span class="hljs-string">" count:"</span>, v) } } </code></pre> 到此这篇关于“GoLang实现一致性哈希算法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
谈谈一致性哈希算法及其 Golang 实现（含负载均衡算法概述）
mysql索引教程之哈希索引
「对比Python学习Go」- 高级数据结构下篇
接口安全机制
golang map源码分析
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
PHP开发者如何做好密码保护以及Laravel底层密码存储和验证实现
【golang】HashMap原理和实现
Go基础编程：Map
Go从入门到精通系列视频之go编程语言密码学哈希算法