Код 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
  1. Храни точки кольца отсортированным массивом { h, node }.
  2. Нижняя граница бинарным поиском; вышли за конец, значит, берём индекс 0.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Термины по теме