🔥 Consistent Hashing   💡 Хеш-таблица - структура данных, которая обеспечивает быстрый доступ к объектам по их ключам. Ключи проходят через хеш-функцию, которая преобразует их в индексы для доступа к данным в таблице.   1⃣ Distributed hashing (распределенное хеширование) Если хеш-таблица большая, ее можно разнести по нескольким серверам (шардам).   📌 У нас N серверов, на какой сервер попадут данные? ✅ server_index = hash(key) mod N Хеш-функция преобразует key в число, от которого берется остаток от деления на N. В результате мы получаем индекс сервера, который будет хранить данные по ключу key.   📌 Что будет, если мы захотим увеличить/уменьшить кол-во серверов? 🆘 В данном случае нужно будет снова перехешировать все данные, что бы с измененным N разложить их по серверам.   2⃣ Consistent Hashing (последовательное хеширование) – улучшение распределенного хеширования. Key получает позицию в хеш-кольце. Мы можем масштабировать сервера, перехешируя меньшее количестово данных, в идеале только с соседних серверов.   ⚙ Допустим сервера и данные располагаются на окружности - минимальный угол 0, максимальный 360.   data = {server1, ..., serverN, key1, ..., keyM}   position_on_ring = hash(data[i]) mod 360   📌 У нас N серверов, на какой сервер попадут данные? ✅ Используем правило - двигаемся по часовой стрелке и берем первый найденный сервер. Например, если у нас есть отсортированный по position_on_ring список серверов, найти следующий можно с помощью бинарного поиска.   📌 Что будет, если мы захотим увеличить/уменьшить кол-во серверов? ✅В среднем будет перераспределено только M/N данных   📌 Как поддержать равномерное распределение данных в последовательном хешировании? ✅ Каждый физический сервер, может быть представлен несколькими виртуальными серверами на хеш-кольце. Чем больше виртуальных серверов, тем более равномерно распределены данные по ним. Однако для хранения данных о виртуальных серверах требуется больше места.   Подробнее о хешировании Consistent hashing в Cassandra #consistent_hashing #hashing