松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有JAVA技術和業內最佳實踐,大部分都是務實的、能看懂的、可復現的

掃一掃
關注公眾號

ARTS-12-分布式系統之一致性哈希算法

博客首頁文章列表 松花皮蛋me 2019-06-02 23:00

ARTS的初衷

Algorithm: 主要是為了編程訓練和學習。

Review:主要是為了學習英文

Tip:主要是為了總結和歸納在是常工作中所遇到的知識點。學習至少一個技術技巧。在工作中遇到的問題,踩過的坑,學習的點滴知識。

Share:主要是為了建立影響力,能夠輸出價值觀。分享一篇有觀點和思考的技術文章

https://www.zhihu.com/question/301150832

一、Algorithm

二、Review

http://www.tom-e-white.com/2007/11/consistent-hashing.html 一致性哈希算法

https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8 一致性哈希算法權衡

一致性哈希是用來解決緩存節點刪除增加或者微服務架構中的粘性負載均衡后端節點刪除增加時,避免大部分節點緩存失效的一種算法。原理是將對象和節點都進行相同hash算法( MurmurHash, MetroHash or SipHash1–3,SHA-1 or MD5)處理后映射到一個圓環中(This should be familiar to every Java programmer – the hashCode method on Object returns an int, which lies in the range -231 to 231-1. Imagine mapping this range into a circle so the values wrap around),順時針查找對象映射位置的下一個節點,則是命中的節點,如果沒有找到則返回圓環的第一個節點(To find which cache an object goes in, we move clockwise round the circle until we find a cache point),這種情況當新增和刪除節點時并不會改變原來所有的命中規則

1和4會命中A、2會命中B、3會命中C
當C節點crash和新增D節點時,只會影響3和4的object緩存失效
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);
  } 

}

但是當節點個數比較少時,往往會出現數據傾向現象(With a small number of vnodes, different servers could be assigned wildly different numbers of keys.),所以需要引入虛擬節點(virtual nodes),一般是主機名加編號,數據定位方式不變,只不過命中后要將虛擬節點轉換成真實節點(To add the list of nodes to the ring hash, each one is hashed m.replicas times with slightly different names ( 0 node1, 1 node1, 2 node1, …)),Dubbo服務框架中的ketama算法也是采用的這種思想

然而環哈希算法依舊會導致節點不平衡(the load distribution across the nodes can still be uneven),重復hash也會導致內存開銷增大。于是Google公司于2014年提出Jump Hash,設計思路是當桶的數量變化時,只需要把一些對象從舊桶移動到新桶,不需要做其它移動

func Hash(key uint64, numBuckets int) int32 {
  var b int64 = -1
  var j int64
  for j < int64(numBuckets) {
    b = j
    key = key*2862933555777941757 + 1
    j = int64(float64(b+1) *
      (float64(int64(1)<<31) / float64((key>>33)+1)))
  }
  return int32(b)
}

然而依舊是不足的,輸入是節點數量,輸出是對應的序列號(The main limitation is that it only returns an integer in the range 0..numBuckets-1. It doesn’t support arbitrary bucket names),另外只能增加或者刪除最后的節點,不支持任意節點刪除,也就是說中間節點失效時,失效節點的數據并不會重新平均分配(you can only properly add and remove nodes at the upper end of the range),所以它適用于分布式主備存儲類系統中(These combined make Jump Hash better suited for data storage applications where you can use replication to mitigate node failure)

當然還有其他杰出的算法如Multi-Probe Consistent Hashing、Rendezvous Hashing、Maglev Hashing,具體的大家網上查閱吧

三、Tip

1、推薦一個不太可能被封的國外VPN梯子,justmysocks1.net,沒有服務器,提供了五個域名節點,專屬優惠碼:BWH26FXH3HIQ
2、有些服務的獲取主機方式非常反人類,不像Dubbo中的主機綁定,考慮很多的情況,避免因為無法獲取主機導致不可用(具體代碼就不貼了)

Register & bind IP address for service provider, can be configured separately.
Configuration priority: environment variables -> java system properties -> host property in config file ->/etc/hosts -> default network address -> first available network address

四、Share

微服務架構之Msgpack序列化最佳實踐

談談Linux中的TCP重傳抓包分析

黑龙江6+1开奖结果查询