Когда мы делаем базу данных, подтаблицу базы данных или распределенный кеш, мы неизбежно сталкиваемся с проблемой:
Как равномерно распределить данные по каждому узлу и попытаться свести к минимуму затронутые данные при добавлении и вычитании узлов.
Хэш по модулю
Не говоря уже о случайном размещении, оно принесет много проблем. Обычно самое простое решение, о котором можно подумать, этоhash 取模.
Вы можете передать входящий ключ какindex = hash(key) % NТаким образом вычисляются узлы, которые необходимо сохранить. Хэш-функция — это метод отображения хэшей, который преобразует строки в положительные целые числа, а N — количество узлов.
Это может обеспечить равномерное распределение данных, но отказоустойчивость и масштабируемость этого алгоритма плохие.
Например, при добавлении или удалении узла необходимо пересчитывать все ключи, очевидно, что это дорого, поэтому требуется алгоритм, удовлетворяющий равномерному распределению, а также обладающий хорошей отказоустойчивостью и масштабируемостью.
Последовательный алгоритм хеширования
Алгоритм Consistent Hash заключается в формировании кольца из всех значений хеш-функции, диапазон которых находится в0 ~ 2^32-1. Как показано ниже:
После хэширования каждого узла в это кольцо вы можете использовать уникальные поля, такие как IP-адрес узла и имя хоста, в качестве ключа.hash(key), после хеширования следующим образом:
После этого вам нужно найти данные на соответствующем узле, используя тот жеhash 函数Сопоставьте Ключ с этим кольцом.
Таким образом, k1 можно расположить по часовой стрелке, чтобыN1节点, k2 расположен наN3节点, k3 находится вN2节点.
Отказоустойчивость
Теперь предположим, что N1 не работает:
Тем не менее, согласно направлению по часовой стрелке, k2 и k3 остаются прежними, только k1 переназначается на N3. Таким образом гарантируется отказоустойчивость, и когда узел выйдет из строя, будет затронута только небольшая часть данных.
Расширяемость
При добавлении узла:
Между N2 и N3 добавляется новый узел N4. В это время будет обнаружено, что только k3 является данными о показах, а остальные данные остаются неизменными, поэтому это также обеспечивает масштабируемость.
виртуальный узел
Пока алгоритм все еще имеет некоторые проблемы:
Когда узлов мало, распределение данных будет неравномерным:
Это приведет к тому, что большая часть данных будет находиться в узле N1, и лишь небольшой объем данных будет находиться в узле N2.
Чтобы решить эту проблему, алгоритм последовательного хеширования вводит виртуальные узлы. Каждый узел хэшируется несколько раз, чтобы сгенерировать несколько узлов и поместить их в кольцо, называемое виртуальными узлами:
При расчете вы можете добавить число после IP, чтобы сгенерировать хеш-значение.
Таким образом, требуется всего несколько шагов отображения виртуальных узлов на фактические узлы на исходной основе, так что даже небольшое количество узлов может удовлетворить однородность.
Дополнительный
Недавно я обобщил некоторые знания, связанные с Java, и заинтересованные друзья могут поддерживать их вместе.