Здесь поговорим о том, как хеширование применяется для шардирования, что такое консистентное хеширование и как оно связано с шардированием.
Содержание:
- Distributed Storages
- Проблема рехеширования
- Консистентное хеширование
- Hash Ring
- Jump Consistent Hash. Пример использования
- Почему консистентное хеширование не распространено в обычных хеш таблицах?
- Персистентное хеширование
Перед тем как далее обсуждать консистентное хеширование, давайте поговорим о распределенных хранилищах, чаще всего это Key-Value хранилища.
В таких хранилищах мы часто хотим разделить данные на несколько частей, которые хостятся на разных серверах. Одна из мотиваций сделать это - это обойти ограничения по мощности и памяти одного компьютера, позволяя создать таблицу сколько угодно большого размера. Как пример, существуют распределенные хеш таблицы: Distributed Hash Table. Также существуют распределенные кэши, например Memcached, и много другого.
В общем, ключи распределяются между разными серверами. Окей, допустим, что как хранить данные на сервере мы знаем. Но как же нам понять, на каком сервере лежат данные? То есть вопрос стоит такой: как для каждого ключа вычислить сервер?
Один из вариантов - это прибегнуть к помощи хеширования.
Тогда самый простой и наивный путь - это вычислить хеш-код ключа и взять модуль от числа серверов (размера пула). То есть:
Существуют и другие варианты определения сервера по ключу, но здесь мы говорим только о хешировании.
Выше приведенная схема вычисления сервера простая и понятная. Однако, все это хорошо работает до того момента, пока не изменится количество серверов, а это может быть, ведь сервера часто падают или добавляются новые. Тогда нам потребуется перехешировать все ключи между серверами еще раз, ведь мы использовали оператор взятию по модулю от размера пула. А это плохо, так как теперь ключи будут мапиться в новые сервера, где значения не закешированы, соответственно мы получим много cache miss, что ухудшит производительность.
Так как же нам решить проблему рехеширования? Очевидно, нам нужен такой алгоритм хеширования, который не зависит напрямую от количества серверов. Здесь нам и приходит на помощь консистентное хеширование.
Консистентное хеширование позволяет нам распределять ключи так, что при изменении количества бакетов (серверов) будет рехешировано в среднем только K/N ключей, где K - количество ключей, а N - количество бакетов после изменения ( количество серверов, размер пула). Для сравнения, в большинстве стандартных имплементаций хеш-таблиц требуется рехешировать почти все ключи.
Хочу еще раз обговорить такой важный для понимания момент: в случае с распределенной системой, алгоритм консистентного хеширования может применяться только для вычисления сервера по ключу. То есть, на самом сервере данные по ключу могут лежать каким угодно образом.
Один из популярных алгоритмов консистентного хеширования - это Hash Ring, который назначает серверам и ключам позицию на абстрактном кольце (circle), или, как его называют, hash ring.
Итак, как же работает эта схема? Представим, что все выходные значения хеш функции замаплены на кольцо, где может быть
расположено [0; 2^32-1] значений, то есть диапазон выходного значения хеш функции, что является, по сути, размером
Integer.
Для каждого сервера вычисляется hash code и на окружности располагают сервера в получившиеся значения. Когда приходят новые ключи, то для них также вычисляется hash code. Теперь мы можем замапить ключ в сервер, просто взяв ближайший сервер, который встретится, если двигаться от hash code ключа по окружности по часовой стрелке. По сути, нам нужен сервер "successor" от хеш кода ключа, поэтому эффективно для хранения серверов использовать Binary Search Tree (TreeMap в Java).
Удаление сервера:
- При выходе (удалении) какого либо сервера из строя потребуется переназначить только те ключи, которые мапились в данный сервер или его виртуальные ноды. Тогда новым их сервером станет тот, который следовал после старого по часовой стрелке. А остальные ключи мапятся все в те же сервера, как и раньше - их не трогаем
- Самое шикарное при удалении то, что требуется переназначить всего лишь
$\frac{1}{N-1}$ от всех ключей, где$(N-1)$ - количество серверов после удаления
Добавление сервера:
- При добавлении нового сервера потребуется переназначить те ключи, которые стали ближе к новому добавленному серверу, чем к тому, на который они мапились раннее. А остальные ключи мапятся все в те же сервера - их не трогаем
- Таким же образом, самое шикарное при добавлении то, что требуется переназначить всего лишь
$\frac{1}{N+1}$ от всех ключей, где$(N+1)$ - количество серверов после добавления
Один из примеров distributed hashing - это Memcached, который поддерживает консистентное хеширование из коробки.
Чтобы распределить нагрузку с учетом мощности серверов, мы можем задать вес серверов. Имплементируется это с помощью так называемых Virtual Nodes. Это сервера, которые существуют на Hash Ring только виртуально, и любой маппинг в них отображается в действительный сервер.
При использовании виртуальных серверов на окружности размещается не один сервер, а такое количество виртуальных серверов, равное весу физического сервера. Тогда для более мощного сервера в него будет мапиться пропорционально большее количество ключей.
Итак, давайте покажу на практике, как можно использовать консистентное хеширование. Я не буду использовать Hash Ring алгоритм, а заиспользую Jump Consistent Hash алгоритм, который был изобретен в Google.
Данный алгоритм делает очень хорошую работу по равномерному распределению ключей: в среднем при изменении количества
серверов потребуется перехешировать
Давайте заиспользуем этот алгоритм для шардирования на основе консистентного хеширования. Допустим, у нас есть фиксированное количество шардов - 3 штуки, шарды пронумерованы от 0 до 2 и каждому шарду можно задать вес (количество Virtual Nodes). Тогда вычислить шард по ключу можно следующим образом:
public class ShardResolver {
public static Shard getShard(@NotNull String senderId, @NotNull Collection<Shard> shards) {
// вычисляем hashCode
HashCode hashCode = Hashing.murmur3_128().hashString(senderId, Charsets.UTF_8);
// вычисляем индекс для элемента, используя консистентное хеширование
// функция consistentHash принимает вычисленный хеш код и количество бакетов
// здесь количество бакетов - это количество виртуальных нод
int totalWeight = shards.stream()
.map(Shard::getWeight)
.reduce(0, Integer::sum);
int weightedKey = Hashing.consistentHash(hashCode, totalWeight);
// ищем ближайший к вычисленному индексу шард по часовой стрелке (successor)
// шарды идут по порядку их расположения на Hash Ring
int weightAccum = 0;
for (Shard shard : shards) {
if (weightedKey <= weightAccum) {
return shard;
}
weightAccum += shard.getWeight();
}
}
}ID шарда вычисляется следующим образом:
-
Берется ключ и по нему считается
hashCode -
Для данного хеш значения применяется алгоритм консистентного хеширования для вычисления ID шарда:
consistentHash(hash, buckets). Первым параметром передается вычисленное на 1-ом шаге значение хеша, а вторым - общий вес шардов. На выходе мы получаем значение weightedKey из промежутка [0; W), где W - общий вес шардов -
Результирующее значение из промежутка [0; W) приводится к нужному шарду.
Делается это так: мы проходимся по всем шардам, начиная с первого, и суммируем текущий общий вес шардов. Если результирующее значение weightedKey меньше текущего общего веса weightAccum, то мы нашли нужный шард, иначе ищем дальше. Например, даны веса шардов: 3, 1, 4. Если алгоритм консистентного хеширования принимает на вход ID пользователя и число 8 (общий вес шардов) и выдает {0, 1, 2}, то этой 1-ый шард (на этой итерации текущий общий вес равен 3); если выдает {3}, то это 2-ой шард (на этой итерации текущий общий вес равен 4); если выдает {4, 5, 6, 7}, то это третий шард (на этой итерации общий вес шардов равен 8).
Для первичного хеширования используется алгоритм MurmurHash3, который
является персистентным (детерминированным), то есть всегда возвращает одинаковый результат для одних и тех же входных
данных, в независимости от среды выполнения. Используемая библиотека -
это Google Guava, так как в ней есть все
необходимое для нашего примера, но можно взять и другую. Посмотреть полный код можно в пакете me.progbloom.hashing.jump.
Почему же консистентное хеширование активно применяется в распределенных системах, но не применяется в хеш таблицах? Дело в том, что проблема рехеширования присутствует только при шардировании - ведь если мы рехешируем все ключи в другие сервера, то потеряем доступ к ранее сохраненных данным, поэтому там очень важно иметь алгоритм, который предлагает минимальное количество рехеширований.
В случае с хеш мапой же, она не является распределенной, а лежит в памяти одного инстанса приложения и нам совершенно не оправданно использовать такие сложные алгоритмы хеширования, ведь мы можем спокойно рехешировать все ключи и не получить ухудшения работы приложения.
Персистентный (детерминированный) алгоритм - это такой алгоритм, который всегда для одних и тех же входных данных выдает одинаковый результат вне зависимости от среды выполнения.
Стандарт языка Java не говорит, какой конкретный алгоритм должен использоваться для функции hashCode() и тем более не
говорит о том, что алгоритм должен быть персистентным - это все зависит от имплементации Java (OpenJDK, Oracle,
Corretto). Именно поэтому в примере с шардированием я выбрал MurmurHash3, который является детерминированным, а
не hashCode из Java, так как иначе при изменении среды выполнения ключи могли бы начать мапиться по-другому, и мы попадали бы в неверный шард.