В распределённом кэше после добавления узла почти все ключи начали промахиваться. Какой механизм уменьшает объём перемещаемых ключей при изменении состава кластера?
Нужен consistent hashing, или согласованное хеширование. Оно размещает узлы и ключи на логическом хеш-кольце, поэтому при добавлении или удалении узла перераспределяется в основном только соседний диапазон ключей, а не весь набор.
При обычном размещении ключа по формуле hash(key) mod N изменение числа узлов меняет остаток для большинства ключей. После добавления одного узла почти весь кэш начинает обращаться к новым адресам, что вызывает массовые промахи и всплеск нагрузки на исходное хранилище.
Согласованное хеширование появилось как способ уменьшить такой эффект в динамических кластерах кэшей и распределённых хранилищ. Оно не устраняет перераспределение полностью, но делает его локальным и предсказуемым.
Пусть ключ выбирает узел по хешу, а состав кластера меняется. При наивном распределении изменение числа узлов нарушает соответствие почти всех ключей и узлов, поэтому ранее прогретый кэш теряет полезность.
Последствиями могут стать лавина промахов, перегрузка базы данных, рост задержек и каскадные отказы. Простое равномерное распределение новых запросов между узлами проблему не решает: важно сохранить как можно больше прежних соответствий ключей.
В consistent hashing хеш-пространство представляют кольцом. Каждый узел получает одну или несколько позиций на этом кольце, а ключ обслуживает первый узел по часовой стрелке от позиции его хеша.
При добавлении узла он забирает только ключи из диапазона между своей позицией и предыдущей позицией на кольце. Остальные ключи сохраняют прежнего владельца. При удалении узла его диапазоны переходят соседним узлам.
На практике используют виртуальные узлы: один физический сервер представлен множеством позиций. Это выравнивает объём данных и нагрузки, потому что несколько случайных позиций дают более равномерное покрытие кольца. Число виртуальных узлов является компромиссом: больше позиций обычно улучшает баланс, но увеличивает служебные структуры и стоимость управления.
При идеальном равномерном распределении добавление одного узла в кластер из N узлов перемещает в среднем около 1/(N+1) ключей. Это вероятностная оценка, а не гарантия: плохая хеш-функция, малое число виртуальных узлов или неравномерные ключи могут дать заметный перекос.
Для реплицируемого кэша или хранилища сначала выбирают основной узел, а затем несколько следующих независимых позиций кольца для реплик. При этом нужно не допустить, чтобы виртуальные позиции одного физического сервера считались разными отказоустойчивыми узлами.
Согласованное хеширование не решает автоматически проблемы горячих ключей, изменения веса серверов, миграции самих данных и согласованности реплик. Для горячих ключей применяют отдельное расщепление нагрузки или кэширование на нескольких владельцах; для изменения мощности узла используют веса и контролируемое перемещение диапазонов.
Кэш из десяти серверов обслуживает каталог товаров. После добавления одиннадцатого сервера команда использовала hash(key) mod 11; почти все записи оказались на других серверах, поэтому база получила резкий поток запросов восстановления кэша.
Рассматривались три варианта. Сохранить остаточное хеширование было проще всего, но оно вызвало бы повторение проблемы при каждом изменении состава. Перенести все ключи вручную позволило бы контролировать процесс, однако потребовало бы большого окна миграции и сложной координации. Consistent hashing с виртуальными узлами ограничил объём перемещений и позволил постепенно прогревать новый сервер.
Выбрали третий вариант. Кольцо изменяли поэтапно, контролируя промахи, задержки и нагрузку на базу. Решение уменьшило массовую потерю кэша, но команда дополнительно ввела защиту от cache stampede, потому что согласованное хеширование само по себе не предотвращает одновременное восстановление одного горячего ключа множеством клиентов.
Нет. Новый узел должен получить часть существующего диапазона, иначе он не начнёт обслуживать данные. Механизм лишь уменьшает долю перемещаемых ключей и локализует её; фактический объём зависит от распределения позиций и реализации миграции.
Равномерность хеш-функции не гарантирует равномерность конечного распределения при небольшом числе физических узлов. Один физический узел с одной позицией может случайно получить слишком большой диапазон. Множество виртуальных позиций снижает дисперсию и позволяет также моделировать разные веса серверов.
Для обычного кэша потеря записи допустима, но одновременное обращение многих клиентов к исходному хранилищу может вызвать cache stampede. Поэтому применяют блокировку или single-flight для одного ключа, ограничение скорости восстановления, случайное распределение времени истечения и иногда временное чтение со старого владельца. Для постоянного хранилища нужна уже полноценная процедура миграции, контроль версий и проверка успешной записи, а не простое изменение маршрутизации.