今天寫點周末在火車上看的memcached的東西:
一:memcached的分布式
雖然memcached被稱為“分布式”緩存伺服器,但是伺服器端并沒有“分布式”的功能。而是通過用戶端來實作的。
memcached分布式原理:
假設有5台memcached伺服器:node1,node2… node5。現在要儲存鍵為key1,key2…key10的資料。首先往memcached中添加key1。将key1傳給用戶端程式之後,用戶端實作的算法會根據這個鍵“key1”來決定儲存資料的memcached伺服器。
将伺服器標明之後,将會用標明的伺服器來儲存“key1”和對應的值。
在擷取資料的時候,通過先根據要擷取的資料的key來根據用戶端實作的相同的算法選擇對應的資料儲存的伺服器,然後取出資料。
這樣就實作了memcached的分布式。memcached的伺服器增多,則鍵就會更加的分散。及時一台伺服器挂掉,也不會影響其他的緩存。
memcached分布式方法:
1.根據餘數計算
這種方法簡單的說就是”根據伺服器的台數的餘數來進行分散“。首先求取鍵所對應的整數哈希值,然後根據餘數來選擇伺服器。
這種方法簡單高效,而且資料的分散性也非常的好。但是問題是當增加或者删除一台memcached伺服器的時候,餘數就會發生巨大的變化。這樣就沒有辦法擷取和儲存時間相應的伺服器。進而會極大的降低緩存的命中率。2
2. 一緻性哈希
這種方法首先求出memcached伺服器的哈希值,然後将它配置設定到0~2^32的圓上,然後使用同樣的辦法求出資料的健的哈希值,将其映射到圓上。然後從資料映射的點開始順時針的查找,将資料儲存到查找到的第一台伺服器上面。如果超出了2^32仍然沒有找到伺服器,那麼就将資料儲存到第一台memcached伺服器上面。
這種方法在一定程度上決了在修改memcached伺服器資料的時候對緩存命中率的影響。在一緻性雜湊演算法中,隻有在這個圓上,從增加伺服器的那個點逆時針遇到的第一台伺服器之間的健會受到影響。是以一緻性哈希最大限度的抑制了鍵的重新分布。
另外一些一緻性雜湊演算法也采用了虛拟節點的辦法。因為使用一般的hash函數的話,伺服器的映射地點會分布的可能不太均勻,是以使用虛拟節點的思想,為每一台伺服器在圓上配置設定100~300個點。這樣就能夠抑制分布不均勻,最大限度的減少伺服器增加或者減少的時候緩存的重新分布。
參考代碼:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
<code>import</code> <code>java.util.collection;</code>
<code>import</code> <code>java.util.sortedmap;</code>
<code>import</code> <code>java.util.treemap;</code>
<code>public</code> <code>class</code> <code>consistenthash<t> {</code>
<code> </code><code>private</code> <code>final</code> <code>hashfunction hashfunction;</code>
<code> </code><code>private</code> <code>final</code> <code>int</code> <code>numberofreplicas;</code>
<code> </code><code>private</code> <code>final</code> <code>sortedmap<integer, t> circle = </code><code>new</code> <code>treemap<integer, t>();</code>
<code> </code><code>public</code> <code>consistenthash(hashfunction hashfunction, </code><code>int</code> <code>numberofreplicas,</code>
<code> </code><code>collection<t> nodes) {</code>
<code> </code><code>this</code><code>.hashfunction = hashfunction;</code>
<code> </code><code>this</code><code>.numberofreplicas = numberofreplicas;</code>
<code> </code><code>for</code> <code>(t node : nodes) {</code>
<code> </code><code>add(node);</code>
<code> </code><code>}</code>
<code> </code><code>}</code>
<code> </code><code>public</code> <code>void</code> <code>add(t node) {</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>i = </code><code>0</code><code>; i < numberofreplicas; i++) {</code>
<code> </code><code>circle.put(hashfunction.hash(node.tostring() + i), node);</code>
<code> </code><code>public</code> <code>void</code> <code>remove(t node) {</code>
<code> </code><code>circle.remove(hashfunction.hash(node.tostring() + i));</code>
<code> </code><code>public</code> <code>t get(object key) {</code>
<code> </code><code>if</code> <code>(circle.isempty()) {</code>
<code> </code><code>return</code> <code>null</code><code>;</code>
<code> </code><code>int</code> <code>hash = hashfunction.hash(key);</code>
<code> </code><code>if</code> <code>(!circle.containskey(hash)) {</code>
<code> </code><code>sortedmap<integer, t> tailmap = circle.tailmap(hash);</code>
<code> </code><code>hash = tailmap.isempty() ? circle.firstkey() : tailmap.firstkey();</code>
<code> </code><code>return</code> <code>circle.get(hash);</code>
<code>}</code>
參考資料: