Код Senior Кластер, воркеры, масштабирование обновлено
Консистентное хеширование с виртуальными узлами
Условие
Реализуй class HashRing для распределения ключей кеша по серверам:
new HashRing(vnodes): число виртуальных узлов на сервер;add(node): добавляет сервер, его виртуальные узлы стоят на кольце в точкахhash(node + '#' + i)дляiот 0 доvnodes - 1;remove(node);get(key): сервер, которому принадлежит ключ: первая точка кольца с хешем>= hash(key), по часовой стрелке; если таких нет, первая точка кольца. На пустом кольцеnull.
Функция hash (FNV-1a) уже дана в заготовке, её не меняй. get должен работать за O(log n) (бинарный поиск по отсортированным точкам).
Что проверяют тесты
пустое кольцо
один сервер получает всё
точка: первая с хешем >= hash(key)
удаление сервера двигает только его ключи
добавление сервера забирает примерно 1/n ключей
распределение ровное при многих vnodes
Как подойти
Кольцо = отсортированный массив хешей. Поиск владельца = lower bound с переходом через ноль.
Подсказки: 2
- Храни точки кольца отсортированным массивом
{ h, node }. - Нижняя граница бинарным поиском; вышли за конец, значит, берём индекс 0.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Термины по теме
Ещё по теме «Кластер, воркеры, масштабирование»
- Плавный взвешенный round-robin как в nginx
- Код-ревью: сервис перед масштабированием в 4 инстанса
- Модуль cluster
- cluster внутри Kubernetes
- Память у воркеров cluster
- cluster или worker_threads
- setInterval-крон при нескольких экземплярах
- Флаг --max-old-space-size