Если в крупномасштабной системе с высокой степенью параллелизма требуется распределенное хранилище данных, и ожидается, что данные будут равномерно распределены и обладают сильной масштабируемостью, то алгоритм согласованного хэширования может идеально решить эту проблему. Применение согласованного алгоритма хеширования во многих областяхКэширование распределенной базы данных Hadoop ES
Принцип последовательного хэш-алгоритма
Алгоритм согласованного хеширования использует метод по модулю, а алгоритм согласованного хеширования использует модуль от 2 до 32. То есть последовательный алгоритм хеширования организует все хеш-пространство в виртуальное кольцо.Пространство значений хэш-функции равно 0 ~ 2^32 - 1 (32-битное целое число без знака).Все хеш-кольцо выглядит следующим образом: Значение хеш-функции является целым и неотрицательным.Для определенного атрибута кластера, такого как имя узла, берем значение хеш-функции и помещаем его в кольцо, а значение хэш-функции берем для ключа данных и помещаем в кольцо. Найдите ближайший узел по часовой стрелке и наденьте на него. Все кольцо организовано по часовой стрелке, причем первая точка справа от точки 0 представляет сервер n1 и так далее. Мы используем Hash для выполнения хеширования на каждом сервере. В частности, IP-адрес или имя хоста сервера можно выбрать в качестве ключа для хеширования, чтобы каждый сервер определялся как находящийся в кольце хеширования. Например, мы иметь три машины, используя расположение IP-адреса в кольцевом пространстве после хэширования показано на рисунке:
Используйте ту же функцию Hash, чтобы вычислить хеш-значение ключа данных и определить положение данных в кольце.От этой позиции выполните поиск по кольцу по часовой стрелке, и обнаруженный сервер — это сервер, который он должен найти.
Как показано на рисунке ниже, после хеширования трех данных O1, O2 и O3 их положение в кольцевом пространстве следующее: O1-->n1 O2-->n2 O3-->n3
Отказоустойчивость и масштабируемость последовательных алгоритмов хеширования
Теперь, предполагая, что наш n3 не работает, мы можем видеть из рисунка, что n1, n2 не затрагиваются, только объект O3 перемещается в n1. Итак, мы обнаружили, что в алгоритме согласованного хеширования, если сервер недоступен, затрагиваемые данные — это только данные между этим сервером и предыдущим сервером в его кольцевом пространстве, а другие не будут затронуты. как показано на рисунке:
Теперь в нашу систему добавлен сервер n4, как показано на рисунке
Алгоритму согласованного хеширования требуется лишь переместить небольшую часть данных в кольцевом пространстве для увеличения или уменьшения количества узлов, и он обладает хорошей отказоустойчивостью и масштабируемостью. В случае слишком малого количества служебных узлов последовательного алгоритма хеширования легко вызвать перекос данных (большая часть кэшируемых объектов кэшируется на определенном сервере) из-за неравномерного распределения узлов, как показано на рисунке:
В это время мы обнаружили, что большой объем данных сосредоточен на узле A, в то время как узел B имеет лишь небольшой объем данных. Чтобы решить проблему перекоса данных, алгоритм последовательного хеширования вводит механизм виртуального узла, то есть для каждого узла сервера вычисляется несколько хэшей, а в каждую позицию результата вычисления помещается узел обслуживания, который называется виртуальным узлом. . Конкретную операцию можно реализовать, добавив число после IP-адреса сервера или имени хоста, как показано на рисунке: Например, для узла n1 мы виртуализируем 100 виртуальных узлов, а те, что находятся в кольце, являются виртуальными узлами Аналогично, n2 и n3 также имеют 100 виртуальных узлов.
Когда данные приходят, как судить, на какой сервер их ставить?
Когда данные поступают в кольцо, сначала найдите соответствующий виртуальный узел, а затем найдите соответствующий сервер через виртуальный узел, чтобы данные можно было равномерно распределить путем добавления виртуальных узлов.
Алгоритм позиционирования данных остается неизменным, нужно добавить только один шаг: сопоставление виртуальных узлов с реальными точками. Поэтому после добавления виртуальных узлов, даже если сервисных узлов немного, данные можно распределить равномерно. Вышеупомянутые ситуации все равномерно распределены в идеальных условиях, На самом деле существует согласованный алгоритм хеширования.проблема искажения данных
Класс интерфейса алгоритма
public interface IHashService {
Long hash(String key);
}
Класс реализации интерфейса алгоритма
public class HashService implements IHashService {
/**
* MurMurHash算法,性能高,碰撞率低
*
* @param key String
* @return Long
*/
public Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
Имитация машинного узла
public class Node<T> {
private String ip;
private String name;
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
/**
* 使用IP当做hash的Key
*
* @return String
*/
@Override
public String toString() {
return ip;
}
}
Согласованная хэш-операция
public class ConsistentHash<T> {
// Hash函数接口
private final IHashService iHashService;
// 每个机器节点关联的虚拟节点数量
private final int numberOfReplicas;
// 环形虚拟节点
private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
public ConsistentHash(IHashService iHashService, int numberOfReplicas, Collection<T> nodes) {
this.iHashService = iHashService;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
/**
* 增加真实机器节点
*
* @param node T
*/
public void add(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.put(this.iHashService.hash(node.toString() + i), node);
}
}
/**
* 删除真实机器节点
*
* @param node T
*/
public void remove(T node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.iHashService.hash(node.toString() + i));
}
}
public T get(String key) {
if (circle.isEmpty()) return null;
long hash = iHashService.hash(key);
// 沿环的顺时针找到一个虚拟节点
if (!circle.containsKey(hash)) {
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}
тестовый класс
public class TestHashCircle {
// 机器节点IP前缀
private static final String IP_PREFIX = "192.168.0.";
public static void main(String[] args) {
// 每台真实机器节点上保存的记录条数
Map<String, Integer> map = new HashMap<String, Integer>();
// 真实机器节点, 模拟10台
List<Node<String>> nodes = new ArrayList<Node<String>>();
for (int i = 1; i <= 10; i++) {
map.put(IP_PREFIX + i, 0); // 初始化记录
Node<String> node = new Node<String>(IP_PREFIX + i, "node" + i);
nodes.add(node);
}
IHashService iHashService = new HashService();
// 每台真实机器引入100个虚拟节点
ConsistentHash<Node<String>> consistentHash = new ConsistentHash<Node<String>>(iHashService, 500, nodes);
// 将5000条记录尽可能均匀的存储到10台机器节点上
for (int i = 0; i < 5000; i++) {
// 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
String data = UUID.randomUUID().toString() + i;
// 通过记录找到真实机器节点
Node<String> node = consistentHash.get(data);
// 再这里可以能过其它工具将记录存储真实机器节点上，比如MemoryCache等
// ...
// 每台真实机器节点上保存的记录条数加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
// 打印每台真实机器节点保存的记录条数
for (int i = 1; i <= 10; i++) {
System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get(IP_PREFIX + i));
}
}
}
Результаты приведены ниже: