Недавно я оптимизировал задачи распределенного планирования в отделе, и когда я прочитал исходный код XXL-JOB, я обнаружил, что в его логике балансировки нагрузки используется последовательный алгоритм хеширования. На самом деле алгоритм последовательного хеширования также используется в кластерах распределенного кэша, таких как кластер Redis, для повышения отказоустойчивости и масштабируемости кэша. Что касается исходного кода XXL-JOB, я не буду много говорить, здесь я только анализирую волну алгоритма последовательного хэширования, чтобы закрепить знания, а также поделиться ими с друзьями, чтобы расти вместе.
Алгоритмы хеширования и алгоритмы хеширования согласованности
Когда дело доходит до последовательного хэш-алгоритма, я должен сначала поговорить об алгоритме хэширования.Многие ли студенты действительно понимают точное определение этого термина, которое мы часто слышим?
❝Хэш, обычно переводится как хеширование, хеширование или транслитерация как хэш, представляет собой комбинацию произвольной длины.входить(также известный как предварительное изображение предварительной карты) преобразуется в изображение фиксированной длины с помощью хеш-алгоритма.вывод, результатом является хеш-значение. Это преобразование являетсякарта сжатия, то есть пространство хэш-значения обычно намного меньше пространства ввода, и разные входы могут хэшироваться в один и тот же вывод, поэтому невозможно определить уникальное входное значение по хеш-значению. Проще говоря, это метод сжатия сообщения любой длины до фиксированной длины.Дайджест сообщенияФункция.
❞
Проще говоря, хеширование — это «сжатие» входного значения и преобразование его в меньшее значение, которое обычно уникально и имеет чрезвычайно компактный формат. Так что сейчас большинство бизнес-систем представляют собой микросервисные архитектуры, под естественные распределенные характеристики алгоритм хеширования не подходит.
Например, в распределенной системе хранения для хранения данных на определенном узле, если мы используем общий алгоритм хэширования для маршрутизации, сопоставляем данные с определенным узлом, например, ключ%N, где ключ — это ключ данных, N — количество машинных узлов.Если машина присоединяется к кластеру или покидает его, все сопоставления данных становятся недействительными. Если это постоянное хранилище, требуется миграция данных, а если используется распределенный кеш, другие кеши будут недействительны. Вызывать повторное хэширование большого количества данных, что влияет на нормальную работу бизнес-системы.
Неужели мы ничего не можем сделать сейчас? Конечно есть способ:Последовательный хеш-алгоритм.
Последовательный хеш-алгоритм
❝Алгоритм последовательного хеширования был представлен в 1997 г.Массачусетский технологический институтПредлагается специальный алгоритм хэширования, целью которого является решение проблемы распределенного кэша. При удалении или добавлении сервера отношение отображения между существующим запросом на обслуживание и сервером, обрабатывающим запрос, может быть изменено как можно меньше. Непротиворечивое хеширование решает проблему простого хеширования в распределенных системах.хеш-таблицаТакие проблемы, как динамическое масштабирование в (Distributed Hash Table, DHT).
❞
一致性 hash 算法有一下几大特点：
Остаток средств
Равновесие означает, что результат хеширования может быть максимально распределен по всем узлам буфера, чтобы можно было использовать все пространство буфера. Многие алгоритмы хеширования могут удовлетворять этому условию.
монотонность
Монотонность означает, что при изменении размера буфера последовательное хеширование (Consistent hashing) пытается защитить выделенный контент от повторного сопоставления с новой областью буфера, чтобы уменьшить большое количество повторных хэшей и повысить производительность.
Распространять
В распределенной среде терминал может видеть не все кэши, а только некоторые из них. Когда терминал хочет отобразить содержимое в кэш посредством процесса хэширования, диапазон буфера, видимый разными терминалами, может быть разным, что приводит к несогласованным результатам хэширования.Конечным результатом является то, что один и тот же контент отображается на разные терминалы разными терминалами. в буфере. Этой ситуации, очевидно, следует избегать, поскольку она приводит к тому, что один и тот же контент хранится в разных кешах, что снижает эффективность системного хранилища.
Нагрузка
Проблема нагрузки на самом деле представляет собой взгляд на проблему децентрализации под другим углом. Поскольку разные терминалы могут отображать один и тот же контент на разные экземпляры кэша, конкретный экземпляр кэша также может отображаться на разный контент разными пользователями. Подобно децентрализации, этой ситуации следует избегать, поэтому хороший алгоритм хеширования должен минимизировать нагрузку на буферизацию.
Сценарии применения
Давайте рассмотрим конкретный сценарий: как Redis использует согласованный алгоритм хэширования для обеспечения скорости попадания в кэш, отказоустойчивости и масштабируемости.
-
Сначала получается хеш-значение сервера (узла) redis и помещается в 32-й круг мощности (континуум) от 0 до 2.
-
Затем используйте тот же метод, чтобы найти хэш-значение ключа, в котором хранятся данные, и сопоставьте его с тем же кругом.
-
Затем он смотрит по часовой стрелке от места сопоставления данных, сохраняя данные на первом найденном сервере. Если более 2 в 32-й степени по-прежнему не могут найти сервер, он будет сохранен на первом сервере Redis.
(Эта картинка украдена из энциклопедии Baidu..) Добавьте сервер Redis из состояния на изображении выше. Использование распределенного алгоритма остатка повлияет на частоту попаданий в кеш из-за изменений в экземпляре кеша, который сохраняет ключ. Однако в алгоритме последовательного хеширования будет затронута только небольшая часть хэша против часовой стрелки узла (node5), как показано на следующем рисунке:
Этот метод очень хорошо решает проблему попадания в кеш, отказоустойчивость и масштабируемость, но когда сервисных узлов мало, возникает другая проблема, то есть «перекос данных», то есть много ключей выделяется на одном и том же экземпляре сервиса. . Такого рода скрытая опасность тоже очень велика, если зависнет нода с большим количеством ключей, это тоже сильно повлияет на использование системы. Как это решить?"виртуальный узел"
Например, в нашей системе есть два сервера, и их кольцевое распределение выглядит следующим образом:
В это время большой объем данных неизбежно будет сосредоточен на Redis2, и лишь очень небольшой объем будет располагаться на Redis1. Чтобы решить эту проблему перекоса данных, алгоритм согласованного хеширования вводит механизм виртуального узла, то есть несколько хэшей вычисляются для каждого сервисного узла, и сервисный узел помещается в каждую позицию результата вычисления, которая называется виртуальным узлом. Конкретный метод может быть достигнут путем добавления числа после IP-адреса сервера или имени хоста. Например, в приведенном выше случае мы решили вычислить 2 виртуальных узла для каждого сервера, поэтому мы можем вычислить хеш-значения «Redis2 #1», «Redis2 #2», «Redis1 #1», «Redis1 # 2" соответственно, поэтому сформируйте 4 виртуальных узла:
При этом алгоритм позиционирования данных остался прежним, но есть еще одно сопоставление виртуальных узлов с реальными, например, данные, расположенные на двух виртуальных узлах «Redis2#1» и «Redis2#2», расположены на Редис2. Это решает проблему неравномерности данных при небольшом количестве сервисных узлов. В практических приложениях количество виртуальных узлов обычно устанавливается равным 32 и более, поэтому даже несколько сервисных узлов могут обеспечить относительно равномерное распределение данных.
код выше
Если вы так много теряете, вам все равно придется это практиковать, иначе это просто болтовня на бумаге, а практика выявляет истинные знания. Начать!
package com.demo.hash;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* 一致性hash算法demo
*
* @author dongx on 2020/9/18
*/
public class ConsistentHashDemo {
/**
* 待添加入Hash环的服务器列表
*/
private static String[] servers = {"10.0.0.1", "10.0.0.2", "10.0.0.3"};
/**
* key表示服务器的hash值，value表示服务器
*/
private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
/**
* 程序初始化，将所有的服务器放入sortedMap中
*/
static {
for (int i=0; i<servers.length; i++) {
int hash = getHash(servers[i]);
System.out.println("[" + servers[i] + "]加入map中, 其Hash值为" + hash);
sortedMap.put(hash, servers[i]);
}
}
/**
* 得到路由到的节点
* @param key
* @return
*/
private static String getServer(String key) {
//得到该key的hash值
int hash = getHash(key);
//得到大于该Hash值的所有Map，这里用有排序功能的sortedMap，有很多api很方便
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
if(subMap.isEmpty()){
//如果没有比该key的hash值大的，则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
return sortedMap.get(i);
}else{
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
return subMap.get(i);
}
}
/**
* 使用FNV1_32_HASH算法计算Hash值(网上找的标准算法)
* @param str
* @return
*/
private static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++) {
hash = (hash ^ str.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出来的值为负数则取其绝对值
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
public static void main(String[] args) {
String[] keys = {"医生", "护士", "患者"};
for(int i=0; i<keys.length; i++) {
System.out.println("[" + keys[i] + "]的hash值为" + getHash(keys[i])
+ ", 被路由到结点[" + getServer(keys[i]) + "]");
}
}
}
Этот код написан более понятно в моих комментариях, и следующий партнер может переварить его в сочетании с предыдущим контентом. Среди них FNV1_32_HASH — стандартный метод алгоритма, найденный в Интернете.
Результаты приведены ниже:
Заканчивать
Алгоритмы согласованного хеширования широко используются в распределенных сценариях, таких как планирование задач и кэширование. Для большинства программистов понимание этого алгоритма очень полезно для устранения неполадок и анализа. Кроме того, интервьюеры также часто задают вопрос о хеше и последовательном хеше. Для Java-разработки это тоже обязательный курс на пути к среднему и продвинутому уровню. Я надеюсь, что вы узнаете больше и продолжите делиться с вами контентом в будущем.