Алгоритм согласованного хеширования был предложен Каргером и др. из Массачусетского технологического института в 1997 г. для решения проблемы распределенного кеша. Цель разработки — решить проблему горячих точек в Интернете. Первоначальная цель очень похожа на CARP. Согласованное хеширование исправляет проблемы, вызванные простым алгоритмом хеширования, используемым CARP, так что DHT можно действительно применять в среде P2P.
Но теперь алгоритм согласованного хеширования получил широкое распространение и в распределенных системах.Любой, кто изучал базу данных кэша memcached, знает, что сервер memcached сам по себе не обеспечивает согласованность распределенного кэша, а обеспечивается клиентом.Следующие шаги используется для вычисления хэша согласованности:
- Сначала найдите хеш-значение memcached-сервера (узла) и настройте его на круг (континуум) от 0 до 232.
- Затем используйте тот же метод, чтобы найти хэш-значение ключа, в котором хранятся данные, и сопоставьте его с тем же кругом.
- Затем он смотрит по часовой стрелке от места сопоставления данных, сохраняя данные на первом найденном сервере. Если сервер все еще не найден после 232, он будет сохранен на первом сервере memcached.
Добавьте сервер memcached из показанного выше состояния. Алгоритм распределения остатка повлияет на частоту попаданий в кэш из-за огромной смены сервера, на котором хранится ключ, но в Consistent Hashing будет затронут только ключ на первом сервере в направлении против часовой стрелки в том месте, где добавляется сервер на континууме. Как показано ниже:
Согласованные свойства хеша
Учитывая, что каждый узел распределенной системы может выйти из строя, а новые узлы, скорее всего, будут добавляться динамически, стоит подумать о том, как обеспечить, чтобы система по-прежнему могла предоставлять хорошие услуги при изменении количества узлов, особенно в реальности. системы кэширования, в случае сбоя сервера, если не используется соответствующий алгоритм для обеспечения согласованности для всей системы, все данные, кэшированные в системе, могут стать недействительными (то есть из-за уменьшения количества системных узлов, когда клиент запрашивает объект, ему необходимо пересчитать его хэш-значение (обычно связанное с количеством узлов в системе. Так как хеш-значение изменилось, очень вероятно, что серверный узел, сохраняющий объект, не может быть найден), поэтому Непротиворечивый хэш. Крайне важно, чтобы алгоритм согласованного хеширования в хорошей распределенной системе кэширования удовлетворял следующим аспектам:
- Остаток средств
Баланс заключается в том, чтобы результаты mych были максимально доступны для всех буферов, чтобы использовались все буферные пространства. Этому условию удовлетворяют многие алгоритмы hash.
- монотонность
Монотонность означает, что если некоторый контент уже был выделен соответствующему буферу посредством хеширования, а в систему добавляется новый буфер, результат хеширования должен быть в состоянии гарантировать, что исходный выделенный контент может быть сопоставлен с новым. буферы без сопоставления с другими буферами в старом наборе буферов. Простые алгоритмы хеширования часто не могут удовлетворить требованиям монотонности, например простейший линейный хеш: x = (ax + b) mod (P), в приведенной выше формуле P представляет собой размер всего буфера. Нетрудно заметить, что при изменении размера буфера (с P1 на P2) изменятся все исходные результаты хеширования, что не удовлетворяет требованию монотонности. Изменение результата хеширования означает, что при изменении буферного пространства необходимо обновить все отношения сопоставления в системе. В системе P2P изменение буфера эквивалентно присоединению или выходу из системы однорангового узла.Эта ситуация часто возникает в системе P2P, поэтому это приведет к большой вычислительной и транспортной нагрузке. Монотонность — это требование, чтобы алгоритм хеширования мог справиться с этой ситуацией.
- Распространять
В распределенной среде терминал может видеть не все буферы, а только некоторые из них. Когда терминал хочет отобразить содержимое в буфер с помощью процесса хеширования, диапазон буфера, видимый разными терминалами, может быть разным, что приводит к несогласованным результатам хеширования.Конечным результатом является то, что одно и то же содержимое отображается на разные терминалы разными терминалами. в буфере. Этой ситуации, очевидно, следует избегать, поскольку она приводит к тому, что один и тот же контент хранится в разных буферах, что снижает эффективность системного хранилища. Рассеяние определяется как серьезность вышеупомянутых явлений. Хороший алгоритм хеширования должен уметь максимально избегать несоответствий, то есть максимально уменьшать дисперсию.
- Нагрузка
Проблема нагрузки на самом деле представляет собой взгляд на проблему децентрализации под другим углом. Поскольку разные терминалы могут отображать один и тот же контент на разные буферы, конкретный буфер также может отображаться на разный контент разными пользователями. Подобно децентрализации, этой ситуации следует избегать, поэтому хороший алгоритм хеширования должен минимизировать нагрузку на буферизацию.
- Гладкость
Плавность означает, что плавное изменение количества серверов кэша согласуется с плавным изменением объектов кэша.
принцип
Базовые концепты
Последовательное хеширование впервые было представлено в статье "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" было предложено. Проще говоря, последовательное хеширование организует все пространство хэш-значений в виртуальное кольцо.Например, предположим, что пространство значений хэш-функции H равно 0-2^32-1 (то есть хэш-значение представляет собой 32-битный символ, формирующий ), все кольцо хеш-пространства выглядит следующим образом:
Все пространство организовано по часовой стрелке. 0 и 232-1 совпадают в направлении нуля.
Следующим шагом является использование Hash для выполнения хэширования на каждом сервере.В частности, IP-адрес или имя хоста сервера можно выбрать в качестве ключа для хеширования, чтобы каждая машина могла определить свою позицию в кольце хеширования.Здесь это Предполагается, что четыре вышеуказанных расположения сервера в кольцевом пространстве после использования хэша IP-адреса выглядят следующим образом:
Далее используйте следующий алгоритм для поиска данных для доступа к соответствующему серверу: используйте ту же функцию Hash для вычисления хеш-значения ключа данных и определения положения данных на кольце, и «пройдите» по кольцу по часовой стрелке. от этой позиции.Сервер, на который он приходит, является сервером, на котором он должен быть расположен.
Например, у нас есть четыре объекта данных: объект A, объект B, объект C и объект D. После вычисления хеш-функции позиции в кольцевом пространстве следующие:
В соответствии с алгоритмом последовательного хеширования данные A назначаются узлу A, B назначаются узлу B, C назначаются узлу C, а D назначаются узлу D.
Отказоустойчивость и масштабируемость последовательного алгоритма хеширования анализируются ниже. Теперь предположим, что узел C, к сожалению, не работает, вы можете видеть, что объекты A, B и D не будут затронуты в это время, и только объект C будет перемещен на узел D. Как правило, в согласованном алгоритме хеширования, если сервер недоступен, затрагиваемые данные — это только данные сервера для предыдущего сервера в его кольцевом пространстве (то есть, первый обнаруженный при обходе в направлении против часовой стрелки) сервер) данные, другие не пострадает.
Рассмотрим другую ситуацию, если в систему добавлен сервер Node X, как показано на следующем рисунке:
В это время объекты Object A, B и D не затрагиваются, и только объект C необходимо переместить на новый Node X. Как правило, в алгоритме последовательного хеширования, если добавляется сервер, затрагиваемые данные — это только новый сервер для предыдущего сервера в его кольцевом пространстве (то есть первый сервер, обнаруженный при обходе против часовой стрелки)), другие данные не пострадает.
Подводя итог, алгоритм согласованного хэширования требует перемещения только небольшой части данных в кольцевом пространстве для увеличения или уменьшения количества узлов, что обеспечивает хорошую отказоустойчивость и масштабируемость.
Кроме того, когда в согласованном алгоритме хеширования слишком мало сервисных узлов, легко вызвать проблему перекоса данных из-за неравномерного распределения узлов. Например, в системе всего два сервера, а распределение колец выглядит следующим образом:
В это время большой объем данных неизбежно будет сосредоточен на узле А, и лишь очень небольшой объем будет располагаться на узле Б. Чтобы решить эту проблему перекоса данных, алгоритм согласованного хеширования вводит механизм виртуального узла, то есть несколько хэшей вычисляются для каждого сервисного узла, и сервисный узел помещается в каждую позицию результата вычисления, которая называется виртуальным узлом. Конкретный метод может быть достигнут путем добавления числа после IP-адреса сервера или имени хоста. Например, в приведенном выше случае для каждого сервера можно рассчитать три виртуальных узла, поэтому «Узел A#1», «Узел A#2», «Узел A#3», «Узел B#1», «Узел B #2» и «Node B#3», образуя шесть виртуальных узлов:
При этом алгоритм позиционирования данных остается неизменным, но есть еще один шаг отображения виртуальных узлов на реальные узлы, например, данные, расположенные на трех виртуальных узлах «Node A#1», «Node A#2 ", и "Узел A#3" расположены в узле A. Это решает проблему неравномерности данных при небольшом количестве сервисных узлов. В практических приложениях количество виртуальных узлов обычно устанавливается равным 32 и более, поэтому даже несколько сервисных узлов могут обеспечить относительно равномерное распределение данных.
Реализация кода JAVA
package org.java.base.hash;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
public class ConsistentHash<T> {
private final int numberOfReplicas;// 节点的复制因子,实际节点个数 * numberOfReplicas =
// 虚拟节点个数
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();// 存储虚拟节点的hash值到真实节点的映射
public ConsistentHash( int numberOfReplicas,
Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes){
add(node);
}
}
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++){
// 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
/*
* 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
* 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
*/
String nodestr =node.toString() + i;
int hashcode =nodestr.hashCode();
System.out.println("hashcode:"+hashcode);
circle.put(hashcode, node);
}
}
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++)
circle.remove((node.toString() + i).hashCode());
}
/*
* 获得一个最近的顺时针节点,根据给定的key 取Hash
* 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点
* 再从实际节点中取得 数据
*/
public T get(Object key) {
if (circle.isEmpty())
return null;
int hash = key.hashCode();// node 用String来表示,获得node在哈希环中的hashCode
System.out.println("hashcode----->:"+hash);
if (!circle.containsKey(hash)) {//数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
public long getSize() {
return circle.size();
}
/*
* 查看表示整个哈希环中各个虚拟节点位置
*/
public void testBalance(){
Set<Integer> sets = circle.keySet();//获得TreeMap中所有的Key
SortedSet<Integer> sortedSets= new TreeSet<Integer>(sets);//将获得的Key集合排序
for(Integer hashCode : sortedSets){
System.out.println(hashCode);
}
System.out.println("----each location 's distance are follows: ----");
/*
* 查看相邻两个hashCode的差值
*/
Iterator<Integer> it = sortedSets.iterator();
Iterator<Integer> it2 = sortedSets.iterator();
if(it2.hasNext())
it2.next();
long keyPre, keyAfter;
while(it.hasNext() && it2.hasNext()){
keyPre = it.next();
keyAfter = it2.next();
System.out.println(keyAfter - keyPre);
}
}
public static void main(String[] args) {
Set<String> nodes = new HashSet<String>();
nodes.add("A");
nodes.add("B");
nodes.add("C");
ConsistentHash<String> consistentHash = new ConsistentHash<String>(2, nodes);
consistentHash.add("D");
System.out.println("hash circle size: " + consistentHash.getSize());
System.out.println("location of each node are follows: ");
consistentHash.testBalance();
String node =consistentHash.get("apple");
System.out.println("node----------->:"+node);
}
}