systems · advanced · 5d
Кольцо consistent hashing
Собери кольцо на виртуальных узлах, которое перераспределяет минимальный набор ключей при появлении или уходе узла — базовый примитив за Dynamo, Cassandra и каждым шардированным кэшем, который должен пережить ротацию узлов без полного перебалансирования.
Результат
HashRing, отображающий произвольные ключи на узлы с consistent hashing, доказывающий минимальный remap при изменении состава и показывающий, что виртуальные узлы измеримо снижают дисбаланс нагрузки по сравнению с одной точкой на узел.
Этапы
0/6 · 0%- 01Построй кольцо: отсортированные позиции, поиск ключа
Кольцо consistent hashing отображает каждый ключ на узел, хешируя ключ в круговое целочисленное пространство и находя первую позицию узла, не меньшую хеша (successor). Кольцо хранится как отсортированный массив пар (позиция, nodeId); поиск — это бинарный поиск хеша ключа с wrap-around от последней позиции к первой, если ключ выходит за правый крайний узел. Выбор хеш-функции важен: хорошее распределение предотвращает горячие пятна ещё до добавления виртуальных узлов, а функция должна быть детерминированной и устойчивой к коллизиям, чтобы два узла не попали на одну позицию. Начни с одной физической позиции на узел; тесты используют инжектируемый хеш, чтобы результаты были полностью воспроизводимы. Докажи контракт: для любого ключа getNode возвращает один из присутствующих id узлов, никогда устаревший или удалённый.
Критерии готовности- addNode / removeNode поддерживают отсортированное кольцо, а getNode всегда возвращает один из присутствующих id узлов (доказано на наборе ключей).
- Поиск использует бинарный поиск или отсортированную вставку, а не линейный скан, и ты можешь объяснить wrap-around, когда хеш ключа превышает наибольшую позицию узла.
Самопроверка
Пройди поиск ключа, чей хеш больше позиции каждого узла — senior-ревьюер проверяет, что ты делаешь wrap-around к первому узлу, а не возвращаешь undefined и не бросаешь исключение.
- 02Виртуальные узлы: реплицируй позиции по всему кольцу
Одна позиция на узел даёт ужасный баланс: при N узлах размеры дуг следуют экспоненциальному распределению, так что самый нагруженный узел типично несёт в 2–3 раза больше средней доли. Виртуальные узлы исправляют это, размещая каждый физический узел в V позициях по кольцу (например, hash('nodeId#0'), hash('nodeId#1'), … hash('nodeId#V-1')), перемежая позиции всех узлов, так что каждый узел владеет множеством маленьких дуг вместо одной большой. По мере роста V стандартное отклонение назначения ключей сходится к 1/√(N·V) от среднего — измеримо ниже, чем в случае одной точки. Компромисс — память: V позиций на узел × N узлов записей в отсортированном кольце; для 100 узлов при V=150 это 15 000 отсортированных записей — приемлемо, но V=10 000 уже имеет значение. Реализуй виртуальные узлы и докажи улучшение баланса на фиксированной популяции ключей.
Критерии готовности- При vnodes > 1 кольцо содержит V отсортированных позиций на узел, и ты можешь показать, что записи кольца визуально перемежаются, а не сгруппированы по узлу.
- На фиксированной популяции ~100 ключей стандартное отклонение числа ключей на узел при vnodes > 1 строго ниже, чем при vnodes = 1 (измерено и сформулировано).
Самопроверка
Назови расход памяти кольца при N=100 узлах, V=150 vnodes — senior-ревьюер проверяет, что ты знаешь: кольцо — отсортированный массив N·V записей, а стоимость поиска ограничена O(log N·V).
- 03Минимальный remap: перенаправляется только уходящая дуга
Весь смысл consistent hashing в том, что добавление или удаление одного узла перераспределяет только ключи, назначенные на дугу(-и) этого узла — всё остальное остаётся на месте. При N узлах каждый ключ имеет вероятность 1/N быть перераспределённым при любом изменении состава, в отличие от полного перемешивания при схеме с modulo-hash. Это свойство «радиуса взрыва» (blast radius): отказ узла или событие масштабирования затрагивает только ограниченную долю пространства ключей. Докажи это: запиши назначение каждого ключа до изменения состава, примени изменение, запиши назначения после и проверь, что доля переместившихся ключей значительно ниже 1 — конкретно, что ключи, чей узел до изменения не был добавленным/удалённым, не были затронуты.
Критерии готовности- После addNode доля популяции ключей (~200 ключей), чей назначенный узел изменился, ниже 0.4 (жёстче, чем 0.5 — схема modulo-hash, перемещающая случайные ключи, может случайно удовлетворить < 0.5). При переходе 3→4 узла ожидаемый remap ≈ 1/4 = 0.25.
- Сильное свойство consistent hashing: каждый ключ, изменивший назначение после addNode, теперь направляется на вновь добавленный узел — ни один ключ не переместился между двумя уже существовавшими узлами. Это свойство отличает consistent hashing от схемы с случайно-малым remap.
- После removeNode каждый ключ, ранее не назначенный на удалённый узел, сохраняет ровно свой прежний узел — никакого побочного перемещения.
Самопроверка
Покажи таблицу назначений до/после removeNode — senior-ревьюер проверяет, что переместились только ключи, назначенные на удалённый узел, а общая доля перемещённых близка к 1/N при N узлах.
- 04Измерь баланс нагрузки: стандартное отклонение числа ключей по узлам
Consistent hashing с умеренным числом виртуальных узлов всё равно даёт несбалансированную нагрузку, если хеш-функция плохая или V слишком мало. Измерь это. На большой популяции ключей (например, 1000 ключей, 5 узлов, разные значения V) вычисли коэффициент вариации (stddev / mean) числа ключей на узел. Одна позиция на узел (V=1) обычно даёт CV около 0.5–1.0 при малом N; V=100–150 снижает его до 0.1–0.2. Построй график или таблицу V vs. CV, чтобы утверждать монотонное улучшение и дать правило большого пальца: после V=150 отдача быстро убывает, а расход памяти растёт линейно. Этот анализ — то, что senior-инженер представляет при обосновании числа vnode в продакшн-деплое Cassandra или Redis Cluster.
Критерии готовности- Ты вычислил распределение числа ключей на узел для не менее двух значений V (V=1 и V≈150) на ≥ 200 ключах: stddev при V=150 строго ниже, чем при V=1 (относительное утверждение), И коэффициент вариации (CV = stddev / mean) при V=150 ниже 0.3 (абсолютное утверждение). CV при V=1 для N=5 обычно 0.5–1.0.
- Ты сформулировал конкретную рекомендацию по V для N=5 узлов и N=50 узлов на основе измерений CV, а не просто «больше V лучше».
Самопроверка
При N=5, V=1 против V=150 на 1000 ключах: senior-ревьюер ожидает CV при V=1 ≥ 0.4 и CV при V=150 ≤ 0.25, и хочет, чтобы ты назвал расход памяти для каждого и точку, где убывающая отдача делает увеличение V бессмысленным.
- 05Взвешенные узлы: пропорциональное распределение ёмкости
Реальные кластеры гетерогенны: узел с 2× RAM должен нести 2× ключей. Consistent hashing обрабатывает это нативно: назначай V × weight позиций вместо V, где weight — относительная ёмкость узла. Узел с weight=2 получает 2V позиций; с weight=0.5 — V/2 позиций. Доля назначений ключей для каждого узла сходится к его доле в сумме весов. Так настраивается 'num_tokens' на узел в Cassandra для кластера смешанного поколения, и так Redis Cluster перебалансируется при повышении реплики до более крупного инстанса. Реализуй поддержку весов, проверь, что доля назначений отслеживает долю весов на большой популяции ключей, и порассуждай о том, что происходит при перебалансировке: добавление тяжёлого узла перераспределяет больше ключей, чем добавление лёгкого.
Критерии готовности- addNode принимает опциональный weight; узел с weight=2 получает примерно вдвое больше ключей, чем узел с weight=1, на ≥ 200 ключах (в пределах 20% допуска).
- Ты можешь назвать blast radius при добавлении узла weight=2 против weight=1 в 4-узловое кольцо и объяснить, почему тяжёлые узлы добавляются поэтапно в продакшне.
Самопроверка
Покажи доли назначений на узел для 3-узлового кольца с весами [1, 2, 1] на 500 ключах — senior-ревьюер проверяет, что узел weight=2 несёт ~50% ± 15% ключей, и может объяснить стоимость перебалансировки при удвоении веса этого узла в живом кластере.
- 06Bounded load: ограничь любой узел на ε выше среднего
Даже при большом числе виртуальных узлов кольцо может давать горячие пятна при перекошенном распределении ключей — вирусный ключ или горячая область пространства хешей концентрирует запросы на одной дуге. Bounded-load consistent hashing от Google (2017) исправляет это, добавляя мягкий потолок: когда узел уже на (1+ε)-кратном среднем уровне нагрузки, ключ маршрутизируется к следующему узлу. Потолок динамический — он отслеживает живую нагрузку, а не статические счётчики позиций, — поэтому самонастраивается при смещении нагрузки. Параметр ε торгует балансом нагрузки (ε→0 — идеальный баланс, но деградирует в round-robin) против консистентности (ε→∞ — чистый consistent hashing без перенаправления). Пройди компромисс: при ε=0.25 узел может нести не более 25% выше среднего, и эмпирически скорость переназначений очень низка при равномерном распределении, но резко растёт при перекошенном. Реализуй зондирование bounded-load: найдя successor в кольце, иди вперёд до узла ниже потолка. Измерь среднее число зондирований при равномерном и перекошенном трафике.
Критерии готовности- getNode зондирует вперёд за successor кольца, когда successor превышает потолок (1+ε)× среднего, и нагрузка ни одного узла не превышает потолок во время прогона на ≥ 200 запросах.
- Ты измерил среднее число зондирований при равномерном и перекошенном распределении ключей и можешь сформулировать стоимость задержки дополнительных зондирований против выгоды баланса нагрузки.
Самопроверка
При перекошенном распределении ключей (80% запросов на 10% ключей) покажи среднее число зондирований bounded-load и какой ε ты выбрал — senior-ревьюер проверяет, что ε обоснован измеренным распределением нагрузки, а не выбран произвольно.
Стартер
- README.md
- src/ring.ts
- test/ring.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| Размещение в кольце и поиск | Ключи назначаются итерацией по узлам; коллизии позиций и wrap-around не обрабатываются. Назначение меняется при изменении порядка итерации. | Кольцо — отсортированный массив позиций; поиск — бинарный поиск с wrap-around; детерминированный хеш размещает узлы; getNode всегда возвращает присутствующий id узла. | Ты обосновываешь выбор хеш-функции (устойчивость к коллизиям, качество распределения), рассуждаешь об ожидаемой дисперсии размеров дуг при N узлах с одной позицией каждый, и измеряешь, что виртуальные узлы снижают коэффициент вариации ниже 0.25 при V=150. |
| Минимальный remap при изменении состава | Добавление или удаление узла переназначает многие ключи, которые не были на дуге изменённого узла — радиус взрыва не ограничен. | После addNode или removeNode перемещаются только ключи, ранее назначенные на затронутую дугу (-и); все остальные ключи остаются на своём узле (проверено на фиксированной популяции). | Ты измеряешь долю переназначённых ключей при addNode и removeNode, показываешь, что она примерно равна 1/(N+1) и 1/N соответственно, и называешь worst-case blast radius при изменении взвешенного узла (пропорциональная весу доля remap). |
| Баланс нагрузки (vnodes, веса) | Все узлы имеют одну позицию; нагрузка явно неравномерна, измерений не делается. | Виртуальные узлы снижают дисперсию нагрузки (измеренные stddev или CV), а взвешенные узлы назначают пропорционально больше позиций узлам с большей ёмкостью, и доли назначений отслеживают доли весов. | Ты даёшь конкретную рекомендацию по V на размер кластера (целевой CV с числами), указываешь расход памяти кольца при этом V и реализуешь или рассуждаешь о bounded-load для ограничения любого горячего узла на (1+ε)× среднего даже при перекошенном распределении ключей. |
Эталонный разбор (спойлер)
Зачем consistent hashing: схема modulo-hash (ключ mod N) переназначает почти каждый ключ при изменении N — добавление одного узла в 10-узловое кольцо переназначает 90% пространства ключей, запуская кластерный ресинк. Consistent hashing отображает ключи и узлы на одно кольцо, так что изменение состава переназначает только дугу, которой владел изменяющийся узел — примерно 1/N ключей — ограниченный blast radius независимо от размера кластера.
Виртуальные узлы против одной позиции на узел: при одной позиции на узел размеры дуг следуют экспоненциальному распределению. Самый тяжёлый узел несёт E[max arc] ≈ H_N / N от среднего, где H_N — N-е гармоническое число — примерно в 3 раза для N=10. Виртуальные узлы перемежают множество маленьких дуг на физический узел, так что распределение нагрузки по узлам сходится к нормальному со stddev ≈ mean / √(N·V), снижая кратность самого тяжёлого узла с 3× до < 1.25× при V=150.
Взвешенные узлы на практике: 'num_tokens' на узел в Cassandra — это ровно V × weight. Seed-узел с 3× хранилища получает 3× токенов, а его доля владения ключами сходится к его доле в общем бюджете токенов. Когда тяжёлый узел заменяется на живом кластере, blast radius пропорционален его весу — причина разбивать изменения большого веса на инкрементные добавления.
Bounded-load consistent hashing (Mirrokni, Thorup, Zadimoghaddam, 2017): ключ назначается successor кольца, если только этот узел уже не находится на (1+ε)× текущей средней нагрузки — тогда кольцо зондируется вперёд до узла ниже потолка. Ожидаемое число зондирований — O(log(1/ε)) при равномерном распределении нагрузки, сохраняя почти O(log N) стоимость поиска при гарантии, что ни один узел не перегружен более чем на (1+ε)× — используется во внутреннем балансировщике нагрузки Google и адаптирован в нескольких распределённых хеш-таблицах.
Требования к хеш-функции для размещения в кольце: функция должна быть детерминированной (одна строка → одна позиция на разных прогонах и узлах), равномерно распределённой (без кластеризации позиций) и устойчивой к коллизиям префиксов (иначе два узла попадают на одну позицию и один молча теряется). FNV-1a и MurmurHash3 — распространённые варианты; MD5 и SHA-1 избыточны для качества распределения, но обеспечивают известные гарантии равномерности. В продакшне функция, как правило, инжектируется, чтобы её можно было заменить без переписывания логики кольца.
Сделай по-сеньорски
- Реализуй репликацию: каждый ключ отображается на R последовательных узлов кольца (пропуская виртуальные узлы того же физического узла), и докажи, что удаление одного узла никогда не опускает число реплик ниже R-1 ни для одного ключа.
- Добавь rendezvous (HRW) хеш-кольцо как альтернативу и сравни: HRW не нуждается в отсортированной структуре (каждый узел независимо оценивает ключ), но O(N) поиск против O(log N·V) — измерь точку перехода, где стоимость поиска HRW превышает кольцо с бинарным поиском.
- Управляй bounded-load реальным сигналом нагрузки (p99 задержки запроса на узел) вместо статического счётчика ключей и покажи, что кольцо самовосстанавливается при замедлении одного узла — ключи уходят ещё до явного удаления узла.
- Реализуй jump consistent hashing (10-строчный алгоритм, отображающий ключ на бакет за O(log N) с идеальным балансом, но без поддержки удаления) и порассуждай, когда он выигрывает у кольца с виртуальными узлами: статические счётчики шардов, из которых узлы никогда не уходят.