NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

我最近一段時間在研究 consistent hash。介紹它的paper(Consistent
Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
 byDavid
Karger
 et al) 十年前就出現了,不過直到最近才悄悄的有越來越多的service開始使用consistent hash,這些service包括Amazon’s Dynamo,以及memcached (向Last.fm敬禮)。那麼到底什麼是consistent
hash呢?大家為什麼要關注它呢?

consistent hash的需求來自於執行一個cache叢集(例如web cache)時遇到的一些限制。如果你擁有一個由n臺cache機器組成的叢集,那麼最普通的load balance方式就是把進來的物件o放在編號為hash(o) mod n的那一臺上。你會覺得這個方案簡介優美,直到有一天,由於種種原因你不得不增加或者移除一些cache機器,這時,叢集的機器數目n變了,每個物件都被hash求餘到了新的機器。這將是一場災難,因為真正存放內容的server會被來自於cache叢集的request拖垮。這時整個系統看起來就像沒有cache一樣。這就是大家為什麼關心consistent
hash,因為大家需要使用它來避免系統被拖垮。

情況如果是這樣的就好了:當叢集新增了一臺cache機器,該機器只從其他cache機器中讀取應得的那些物件;相應的,當一個cache機器從叢集中移除,最好是它cache住的物件被分配給其他的cache機器(而沒有更多的資料移動)。這種理想的情境就是consistent hash所追求並實現的:如果可能的話,始終將同一組物件分配給相同的機器。

consistent hash演算法背後最基礎的思想就是:對object和cache machine使用相同的hash函式。這樣做的好處是能夠把cache機器對映到一段interval上,而這段interval就會包含一定數目的物件的hash值。如果某臺cache機器被移除了,那麼它對映到的interval被和它相鄰的一個cache機器託管,其他所有的cache機器都不用變。

描述

讓我們來更深入的來了解一下consistent hash。Hash的作用就是把object和cache對映到一個數值範圍上。Java程式設計師對hash應該很熟悉了–每個物件的hashCode方法會返回一個在[-231,
231-1]的int型整數。我們把這個數值範圍首尾相接的對映到一個環上。下圖描述了一組object(1,
2, 3, 4)和一組cache(A, B, C)分別對映在Hash環上。(圖片源於Web
Caching with Consistent Hashing
 by David Karger et
al
)

圖1

要確定某個object會快取在哪個cache,我們從這個object開始順時針前進,知道我們遇到一個cache點。這樣,從上圖的例子我們看到object 1和4 歸cache A,object 2歸cache B,而cache C快取的事object 3。考慮一下,當cache C被移除了,會發生什麼?在這種情況下,object 3被cache A快取住,所有其他object都不用移動。如果如圖2,cache叢集新增了cache D,那麼D會快取object 3和4,把object 1留給A。

圖2

一切都很好,除了一點:指派給每個cache的間距大小太隨機了,這樣就會object的分配也極度的不均勻。 為了解決這個問題,我們引入”virtual nodes”這個概念:即每個cache在hash環上有多個副本,也就是說,每當我們加入一個cache,在環上都會為這個cache增加多個點。

我下面的程式碼做了一個模擬實驗,將10,000個object存入10個cache,你會在下面的plot圖中看到virtual nodes的影響。x軸上是每個cache的副本數(對數刻度)。當x值較小時,我們看到objects在caches中的分佈是不平衡的(y軸是以百分比形式表示objects在caches中分佈的標準差)。隨著cache的replica的增加,objects的分佈趨向於更加平衡。這個實驗說明了每個cache大概100-200的replica能夠使object的分佈較為平衡(標準差在5%-10%)

experiment result

實現

下面是使用Java的一個簡單實現。要使consistent hash的效果明顯,很重要的一點是使用一個mix的很好的hash函式。Java中object的hashCode方法的大多數實現都沒有提供很好的mix效能。所以我們提供一個HashFunction介面,以便於定製使用的hash函式。在這裡推薦MD5.

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
private final HashFunction hashFunction;
private final int numberOfReplicas;
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i  ) {
circle.put(hashFunction.hash(node.toString()   i), node);
}
}
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i  ) {
circle.remove(hashFunction.hash(node.toString()   i));
}
}
public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}

 


 
上面的程式碼用一個integer的sorted map來表示hash circle。當ConsistentHash建立時,每個node都被新增到circle map中(新增的次數由numberOfReplicas控制)。每個replica的位置,由node的名字加上一個數字字尾所對應的hash值來決定。
要為一個object找到它應該去的node(get方法),我們把object的hash值放入map中查詢。大多數情況下,不會恰好有一個node和這個object重合(即使每個node都有一定量的replica,hash的值空間也比node數要多得多),所以用tailMap方法找到map中的下一個key。如果tail map為空,那麼我們轉一圈,找到circle中的第一個key。

使用

  

那麼你應該如何使用consistent hash呢?一般情況下,你可以使用一些library,而不是自己去寫程式碼。例如上面提到的memcached–一個分散式的記憶體cache系統,現在已經有了支援consisitent hash的client。由Last.fm的Richard
Jones
實現的ketama是第一個,現在是有Dustin
Sallings
貢獻的Java實現。很有趣的是隻有客戶端需要實現consisitent
hash演算法,server端的程式碼不需要任何改變。其他使用consisitent hash的系統有Chord,一個分散式hash表的實現,和Amazon的Dynamo,一個key-value儲存系統。(沒有開源)

libketama – a consistent hashing algo for memcache clients

Posted by muesli inDevelopment
Wednesday, April 11. 2007

We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this:

server = serverlist[hash(key)%serverlist.length];

This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache. We add (and sometimes remove) servers from the memcached pool often enough to warrant writing this – if your
memcached pool never changes, you can probably stop reading now :-)

Ketama is an implementation of a consistent hashing algorithm, meaning you can add or remove servers from the memcached pool without causing a complete remap of all keys.

Here’s how it works:

– Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
– Hash each server string to several (100-200) unsigned ints
– Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
– Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
– To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
– If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.

If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers.

The majority of the code is a C library (libketama) and a PHP4 extension that wraps it. I’ve also included a class from our Java client. (Java Collections makes it rather easy). We use a single-server memcache client wrapped with a native php class to make
it multi-server capable, so we just replaced the hashing method with a ketama_find_server call. (should be easy enough to plug this into libmemcache if need be)

http://static.last.fm/ketama/ketama-0.1.1.tar.bz2

We’ve been using this in production for all our PHP installs and Java services at Last.fm for around 10 days now. We deployed it just in time to smooth over moving loads of webservers between datacenters.

For further information, please refer to the README inside the tarball or these threads on the memcached mailing list:
http://lists.danga.com/pipermail/memcached/2007-April/003853.html
http://lists.danga.com/pipermail/memcached/2007-April/003834.html

相關文章

程式語言 最新文章