Введение
В распределенных системах хранения данных назначение ключей узлам осуществляется через консистентное хеширование: каждому ключу сопоставляется позиция на хеш-кольце, а ближайший токен определяет ответственный узел [1]. Данный механизм используется в промышленных системах распределенного хранения данных [2, 3]. Он также применяется в одноранговых протоколах [4] и сетевых балансировщиках нагрузки [5]. Масштабируемые варианты консистентного хеширования направлены на снижение стоимости переназначений при изменении состава множества узлов [6].
При неоднородности узлов по ресурсным емкостям равномерное распределение токенов приводит к дисбалансу нагрузки: слабые узлы перегружены, сильные простаивают. Статическое взвешивание через виртуальные узлы, применяемое в схемах горизонтального масштабирования [7], не адаптируется к динамике нагрузки. Динамическое взвешивание по наблюдаемой нагрузке, рассматриваемое в работах по балансировке неоднородных систем [8, 9], может быть чувствительно к колебаниям параметров распределения и само по себе не задает бюджета перестройки. Современные работы по балансировке нагрузки в гетерогенных вычислительных средах также фиксируют компромисс между учетом текущей нагрузки, затратами на взаимодействие узлов и устойчивостью планирования [10]. Метод bounded loads [11] ограничивает нагрузку перенаправлением запросов, но не управляет числом токенов и не формализует ограничения на объем миграций.
Каждое переназначение токенов влечет миграцию данных между узлами, что создает дополнительную нагрузку на сетевую подсистему и подсистему хранения [2, 12]. Исследования распределенных систем и оптимизации ресурсов баз данных показывают, что маршрутизация запросов, репликация, миграции данных и балансировка соединений создают самостоятельные накладные расходы [12, 13]. Отсутствие формализованных ограничений на объем миграций приводит к режиму непрерывной перестройки, ухудшающему качество обслуживания [9, 14]. В работах по балансировке при гетерогенных узлах [7, 14] используются виртуальные токены и квантованные весовые схемы, однако бюджет перестройки не формализуется. Подход на основе динамических весов с эвристической оптимизацией [9] снижает дисбаланс, но не ограничивает накопленную стоимость миграций. Ни в одном из перечисленных подходов ограничения на стоимость адаптации не формализованы явно.
Среди современных алгоритмов консистентного хеширования с малым потреблением памяти выделяются MementoHash [15], DxHash [16] и JumpHash [17]. По данным сравнительного обзора [18], remap-rate этих алгоритмов близок к теоретическому минимуму K/N (K – число ключей, N – число узлов): при добавлении или удалении узла мигрирует приблизительно 1/N доли ключевого пространства. По памяти MementoHash и DxHash требуют O(N), JumpHash – O(1); по сложности поиска JumpHash и DxHash – O(1), MementoHash – O(log N) в среднем. В базовой постановке и в проверенных источниках эти алгоритмы не формализуют адаптацию к разным текущим емкостям узлов; поэтому они не закрывают задачу распределения нагрузки между узлами различной емкости. Смежные направления включают динамическую балансировку на основе хеш-слотов [19], консистентное хеширование с динамическими весами [9] и модификацию равномерности кольца консистентного хеширования [20], а также аналитическое описание сценариев LRU-кэширования при консистентном хешировании [21]. Альтернативный подход в Pegasus [22] основан на избирательной репликации горячих ключей через программируемые сетевые коммутаторы. Метод ACH дополняет перечисленные работы: он управляет назначением токенов гетерогенных узлов на хеш-кольце при ограничении стоимости перестройки и совместим с указанными схемами минимального переназначения.
Цель исследования – разработать метод адаптивного управления распределением ключей на основе консистентного хеширования, при котором дисбаланс нагрузки снижается в рамках заданных ограничений на стоимость перестройки.
Материалы и методы исследования
Предлагаемый метод адаптивного консистентного хеширования (ACH) функционирует на уровне маршрутизации запросов между клиентом и узлами кластера. Схема встраивания в архитектуру распределенной системы показана на рис. 1: метод размещается между клиентом и узлами кластера, получает телеметрию от узлов и управляет назначением токенов хеш-кольца. Метод включает три конструктивных элемента.
Элемент 1. Коэффициент интенсивности управления. Коэффициент интенсивности C(t) = C_max · γ(t) · η(t) задает масштаб вмешательства на уровне кластера. Коэффициент разрешенности перестройки γ(t) = clip((τ − total_load(t)) / (τ − τ_min), 0, 1) подавляет перестройку при приближении агрегированной загрузки кластера к насыщению. Показатель локального дисбаланса η(t) = I(t) / (I(t) + κ) связывает интенсивность управления с масштабом перегрузки, где I(t) – максимальное положительное отклонение загрузки узла от целевого уровня ℓ*. Мультипликативная форма C(t) приводит к нулевой интенсивности управления в двух случаях: при отсутствии локальной перегрузки (η = 0) и при насыщении кластера (γ = 0) [23].
Рис. 1. Архитектурная схема встраивания метода ACH в распределенную систему управления данными.
Примечание: составлен авторами по результатам исследования
Элемент 2. Бюджет переназначений. Позиции токенов на хеш-кольце фиксированы; адаптация выполняется через переназначение токенов между узлами. Стоимость перестройки определяется как доля переназначенного ключевого пространства: M_keys(t) = Σ L_s по токенам с измененным назначением, где L_s – длина сегмента хеш-пространства. Бюджет переназначений
m(t) = min(M_max, Δ/H · M_H) · C(t)/C_max
ограничивает плановый объем переназначений; из-за дискретной длины токенов фактическая величина дополнительно контролируется инвариантом
M_keys(t) ≤ m(t) + |O| · max_s L_s.
Двойное ограничение (пошаговое M_max и горизонтное M_H) ограничивает как одиночные крупные перестройки, так и накопление миграционной активности на горизонте [23].
Элемент 3.
Гистерезис порогов чувствительности. Дискретное состояние σ_i(t) ∈ {−1, 0, +1} определяет, включен ли узел в множество источников (перегруженных, σ = +1) или приемников (недогруженных, σ = −1). Пороги ε_on > ε_off > 0 обеспечивают запас устойчивости: переключение σ_i из нейтрального состояния (σ = 0) требует отклонения загрузки не менее ε_on, а возврат в нейтральное состояние – снижения отклонения до ε_off. При шуме телеметрии |ξ_i(t)| ≤ ε_off состояние σ_i остается нейтральным и перестройка не инициируется [23].
Для экспериментального исследования разработана имитационная модель кластера из 10 узлов трех классов гетерогенности (табл. 1). Модель включает пуассоновский поток запросов с интенсивностью Λ(t), распределение ключей маршрутизации по закону Ципфа с параметром s, модель насыщения ресурсов (очередь M/M/1) и модель искажений телеметрии (аддитивный шум σ_ν, лаг d шагов, пропуски с вероятностью p_miss). Интенсивность Λ = 1437,5 запросов в шаг определена калибровкой, при которой слабые узлы перегружены (ℓ_i > ℓ* + ε_on = 0,75), а сильные недогружены (ℓ_i < ℓ* − ε_on = 0,55).
Таблица 1
Параметры классов узлов в имитационной модели
|
Параметр |
Класс A (сильный) |
Класс B (средний) |
Класс C (слабый) |
|
c_cpu (отн. ед.) |
1,0 |
0,55 |
0,25 |
|
μ_i (запр./шаг) |
350 |
193 |
88 |
|
Доля в кластере |
30 % |
40 % |
30 % |
Примечание: составлена авторами на основе полученных данных в ходе исследования.
Алгоритм 1. Перестройка распределения токенов на шаге t
Вход: кольцо R, оценки загрузки ℓ_i, шаг t
состояния σ_i ∈ {−1, 0, +1}
Выход: обновленное кольцо R, M_keys(t)
1. обновить σ_i по правилам гистерезиса (ε_on, ε_off)
2. C_norm ← γ(t) · η(t) // C_norm = C(t) / C_max
3. m ← min(M_max, M_H / H) · C_norm
4. если C ≤ 0 или m ≤ 0 – возврат 0
5. O ← {i : σ_i = +1}; U ← {j : σ_j = −1}
6. g_i ← max(ℓ_i − ℓ*, 0) для i ∈ O
7. r_j ← max(ℓ* − ℓ_j, 0) для j ∈ U
8. если Σ g_i = 0 или Σ r_j = 0 – возврат 0
9. T_out ← ∅ // Фаза 1
10. для каждого i ∈ O:
11. share_i ← m · g_i / Σ_k g_k
12. отсортировать токены узла i по убыванию L_s
13. набирать токены в T_out, пока Σ L_s < share_i
14. остановка по достижении v_min оставшихся токенов
15. для каждого j ∈ U: // Фазы 2 – 3
16. n_j ← |T_out| · r_j / Σ_k r_k
17. переназначить n_j токенов из T_out на узел j
18. M_keys(t) ← Σ L_s по переназначенным токенам
19. проверить инвариант: M_keys(t) ≤ m + |O| · max_s L_s
20. возврат M_keys(t)
Таблица 1а
Параметры метода ACH, используемые в экспериментах
|
Параметр |
Значение |
Назначение |
|
ℓ* |
0,65 |
Целевой уровень загрузки узла |
|
ε_on |
0,10 |
Порог включения коррекции для узла |
|
ε_off |
0,04 |
Порог выключения коррекции (запас гистерезиса) |
|
τ |
0,85 |
Верхний порог подавления перестройки при насыщении кластера |
|
τ_min |
0,50 |
Нижний порог насыщения; ниже него γ(t) = 1 |
|
κ |
0,10 |
Смещение в показателе локального дисбаланса η(t) |
|
M_max |
0,02 |
Максимальная пошаговая доля переназначенного пространства |
|
M_H |
0,25 |
Бюджет переназначений на горизонте H шагов |
|
H |
100 |
Длина горизонтного окна (шагов) |
|
v_min |
3 |
Минимальное число токенов на узле |
Примечание: составлена авторами на основе полученных данных в ходе исследования; значения соответствуют программной реализации имитационной модели.
Таблица 2
Сводные результаты метода ACH по сериям С1–С5 (30 повторений)
|
Серия |
Сценарий |
D̄ (ACH) |
D̄ (А0) |
Снижение |
M_cum |
n_viol |
|
С1 |
Стационарный |
0,177 |
0,225 |
−21,5 % |
0,063 |
0 |
|
С2 |
Нестационарный |
0,016 |
0,035 |
−55,4 % |
0,028 |
0 |
|
С3 |
Ципф + churn |
0,340 |
0,496 |
−31,6 % |
0,310 |
0 |
|
С4a |
Шум σ = 0,02 |
0,172 |
0,224 |
−23,2 % |
0,070 |
0 |
|
С4b |
Шум σ = 0,05 |
0,166 |
0,222 |
−25,2 % |
0,167 |
0 |
|
С4c |
Шум + лаг |
0,198 |
0,219 |
−9,8 % |
4,565 |
0 |
Примечание: D̄ – средний дисбаланс на окне анализа [40, 2000), M_cum – накопленная стоимость перестройки, n_viol – число нарушений инвариантов корректности. Критерий Вилкоксона: p < 0,001 для серий С1–С4c.
Составлена авторами на основе полученных данных в ходе исследования.
Процедура переназначения токенов реализована в три фазы. На первой фазе для каждого узла-источника (σ_i = +1) токены упорядочиваются по убыванию длины дуги L_s и отбираются до достижения индивидуальной доли бюджета
share_i = m(t) · g_i / Σ_j g_j,
где g_i = max(ℓ_i − ℓ*, 0); отбор прекращается также по достижении минимума v_min токенов на узле. На второй фазе отобранные токены объединяются в общий пул. На третьей фазе пул распределяется между узлами-приемниками (σ_i = −1) пропорционально дефициту r_i = max(ℓ* − ℓ_i, 0). Аддитивный гауссовский шум применяется к телеметрии с одинаковой реализацией для всех сравниваемых алгоритмов на каждом шаге, что обеспечивает корректность парного критерия Вилкоксона; лаг моделируется задержкой наблюдения на d шагов, пропуски – независимыми событиями с вероятностью p_miss и замещением последним валидным значением. Для каждой серии выполняется 30 повторений с воспроизводимыми начальными условиями генераторов псевдослучайных чисел; на каждом шаге каждого повторения контролируется выполнение пяти инвариантов корректности.
Полная программная реализация имитационной модели, конфигурации серий, исходные значения seed-ов, агрегированные выборки результатов, индивидуальные значения по 30 повторениям для построения boxplot и ECDF, расчетные скрипты для критерия Вилкоксона и дельты Клиффа, а также набор из 57 модульных тестов опубликованы в открытом репозитории: https://github.com/Kronv3rk/ach-experiment (MIT License).
Эксперимент включает семь серий: стационарный режим (С1), нестационарная нагрузка с деградацией узлов (С2), изменение состава узлов с распределением Ципфа (С3), три подсерии устойчивости при различном уровне шума (С4a, С4b, С4c) и чувствительность к параметрам (С5) (табл. 2).
Для сравнения используются четыре алгоритма: статическое распределение без взвешивания (А0), статическое взвешивание пропорционально емкости (А1), динамическое взвешивание без бюджета [8] (А2), ограничение нагрузки [11] (А3). Каждая серия выполнена в 30 повторениях. Статистическая значимость различий проверяется критерием Вилкоксона при α = 0,05. Корректность программной реализации проверялась набором из 57 модульных тестов; на каждом шаге каждого повторения контролировалось выполнение пяти инвариантов.
Результаты исследования и их обсуждение
В стационарном режиме (серия С1) метод снижает средний дисбаланс D̄ на 21,5 % по сравнению с алгоритмом равномерного распределения А0 (0,177 против 0,225, p < 0,001). По качеству балансировки метод сопоставим с алгоритмом статического взвешивания А1, использующим априорные знания об емкостях узлов (D̄ = 0,175, различие незначимо). Стоимость перестройки составляет M_cum = 0,063, тогда как у алгоритма динамического взвешивания А2 M_cum = 30,028 при сопоставимом снижении дисбаланса (рис. 2).
Рис. 2. Сравнение алгоритмов по среднему дисбалансу D̄ (а) и стоимости перестройки M_cum (б) в серии С1 Примечание: составлен авторами по результатам исследования
Рис. 3. Сравнение алгоритмов в серии С3: средний дисбаланс D̄ (а) и стоимость перестройки M_cum с числом нарушений инвариантов (б). Кружки обозначают число нарушений: красный – нарушения, зеленый – ноль Примечание: составлен авторами по результатам исследования
Таблица 3
Сравнение адаптивных алгоритмов в серии С3 (30 повторений)
|
Алгоритм |
D̄ ± CI₉₅ |
M_cum |
π_chg |
n_viol |
|
А0 (статич.) |
0,496 ± 0,008 |
0,000 |
0,000 |
0 |
|
А1 (взвешен.) |
0,485 ± 0,008 |
0,000 |
0,000 |
0 |
|
А2 (динамич.) |
0,339 ± 0,006 |
4,839 |
0,155 |
0 |
|
А3 (ограничен.) |
0,275 ± 0,023 |
0,750 |
0,045 |
0 |
|
ACH (предлагаемый) |
0,340 ± 0,003 |
0,310 |
0,058 |
0 |
Примечание: CI₉₅ – 95 %-ный доверительный интервал, π_chg – доля шагов с ненулевой перестройкой, n_viol – число нарушений инвариантов.
Составлена авторами на основе полученных данных в ходе исследования
Серия С3 моделирует изменение состава узлов (удаление двух узлов на шаге t = 150, добавление трех на шаге t = 300) при неравномерном распределении запросов по закону Ципфа с параметром s = 1,0. Снижение D̄ в ней составляет 31,6 % относительно А0 (0,340 против 0,496, p < 0,001) и 30,0 % относительно А1 (0,485). В данном сценарии метод показывает статистически значимое снижение дисбаланса относительно как А0, так и А1 (p < 0,001): статические алгоритмы не адаптируют распределение при изменении состава кластера. Стоимость перестройки ACH составила M_cum = 0,310 против 4,839 у А2 (табл. 3, рис. 3). При смене состава узлов статические алгоритмы не перераспределяют ключевое пространство без явного пересчета весов; ACH перераспределяет ключевое пространство инкрементально, в рамках бюджетного ограничения.
Отсутствие нарушений у предлагаемого метода объясняется конструкцией: бюджет m(t) вычисляется до начала перестройки, процедура выбора токенов прекращается при достижении предела; фактический расход дополнительно проверяется инвариантом с дискретной верхней оценкой M_keys(t) ≤ m + |O| · max_s L_s [23].
Серии С4a–С4c иллюстрируют изменение характеристик метода при возрастающем уровне искажений телеметрии (рис. 4). При шуме σ = 0,02 (С4a) и σ = 0,05 (С4b) метод снижает D̄ на 23–25 % по сравнению с А0 (p < 0,001) при качестве балансировки, практически неотличимом от А1. В подсерии С4c (σ = 0,10, лаг d = 2 шага, пропуски p_miss = 10 %) снижение дисбаланса относительно А0 составляет 9,8 % (D̄ = 0,198 против 0,219, p < 0,001). Вместе с тем накопленная стоимость перестройки в С4c возрастает до M_cum = 4,565 (против 0,070 в С4a и 0,167 в С4b): шум телеметрии превышает зону нечувствительности гистерезиса и вызывает избыточные переназначения токенов. Нарушений инвариантов во всех подсериях не зафиксировано.
Рис. 4. Градиент деградации ACH при увеличении искажений телеметрии Серые столбцы – алгоритм статического распределения А0, синие – ACH Красная штриховая линия обозначает границу применимости (σ > ε_off ∧ d > 1) Примечание: составлен авторами по результатам исследования
Таблица 4
Чувствительность ACH к параметрам ε_on, κ, τ, M_max
|
Параметр |
Значение |
D̄ |
M_cum |
π_chg |
Замечание |
|
ε_on |
0,05 |
0,169 |
0,234 |
0,256 |
Агрессивная коррекция |
|
ε_on |
0,10 (база) |
0,176 |
0,064 |
0,036 |
Рабочая точка |
|
ε_on |
0,15 |
0,208 |
0,000 |
0,000 |
Коррекция не запускается |
|
κ |
0,05–0,20 |
0,176 |
0,064 |
0,036 |
В диапазоне без эффекта |
|
τ |
0,70–0,80 |
0,225 |
0,000 |
0,000 |
γ = 0, подавление |
|
τ |
0,85 (база) |
0,176 |
0,064 |
0,036 |
Возобновление коррекции |
|
M_max |
0,005–0,10 |
0,176 |
0,064 |
0,036 |
Ограничен M_H/H |
Примечание: по параметрам κ и M_max представлен интервал значений, в котором агрегированные показатели одинаковы в пределах разрешающей способности эксперимента (10 повторений). Полные результаты sweep по 5 значениям ε_on, 4 значениям κ, 5 значениям τ и 5 значениям M_max сохранены в repos./results/C5/sensitivity.json. Доверительные интервалы (95 %) для всех метрик не превышают: ΔD̄ < 0,008, ΔM_cum < 0,012, Δπ_chg < 0,015.
Составлена авторами на основе полученных данных в ходе исследования.
Результат подсерии С4c определяет количественную границу применимости метода: эффективность сохраняется при σ_ν ≤ ε_off (порог выключения коррекции, в эксперименте ε_off = 0,04) и при лаге d ≤ 1 шаг. При нарушении этих условий шум телеметрии превышает зону нечувствительности гистерезиса, что приводит к ложным включениям коррекции и нецелесообразным переназначениям.
Для пары ACH–А0 в каждой серии (30 повторений) рассчитана дельта Клиффа |δ| как мера эффекта: С1 – 0,996; С2 – 1,000; С3 – 1,000; С4a – 1,000; С4b – 1,000; С4c – 0,936. Значения близки к 1 и указывают на сильное разделение эмпирических распределений D̄. По шкале Romano и др. (2006) |δ| ≥ 0,474 классифицируется как «большой» эффект, что выполнено во всех сериях, включая C4c (|δ| = 0,936). Индивидуальные значения D̄ по 30 повторениям, использованные для расчета |δ|, и позволяют независимо построить графики boxplot и ECDF распределений D̄.
По результатам анализа чувствительности (серия С5), поведение метода определяют два параметра: порог включения коррекции ε_on и порог подавления перестройки τ. При ε_on = 0,05 переназначения выполняются на 25,6 % шагов (D̄ = 0,169); при ε_on ≥ 0,15 перестройка не инициируется (D̄ ≈ 0,208). Параметр τ демонстрирует пороговое поведение: при τ ≤ 0,80 перестройка полностью подавлена (γ = 0, так как total_load ≥ τ), при τ ≥ 0,85 перестройка возобновляется. Детальные результаты серии C5 с разбиением по четырем параметрам (ε_on, κ, τ, M_max) приведены в табл. 4. Диапазоны выбраны симметрично относительно базовых значений из табл. 1а: ε_on ∈ [0,05; 0,20] покрывает область от агрессивной до консервативной коррекции; κ ∈ [0,05; 0,20] – от двукратного снижения до удвоения базового значения κ = 0,10; τ ∈ [0,70; 0,95] – от уровня tau_min до близкого к насыщению; M_max ∈ [0,005; 0,10] – от пятикратного снижения до пятикратного увеличения базового бюджета 0,02. Параметры κ и M_max в исследованном диапазоне не показали значимого влияния на агрегированные показатели D̄ и M_cum: при базовой удельной потребности |O| · g_i ≈ 0,0025 на шаг ограничивающим всегда выступает компонент M_H/H = 0,0025, а не M_max; параметр κ входит как мультипликативное смещение в множителе η и при М_keys, ограниченном бюджетом, его варьирование в указанном диапазоне не выходит за погрешность повторений.
При развертывании в производственной среде метод ACH работает как отдельный сервис маршрутизации между клиентами и узлами кластера (рис. 1). Источником телеметрии m_i(t) служит внешняя система мониторинга (Prometheus, Zabbix) или встроенные средства СУБД. Подсистема миграции данных вызывается контуром управления через потоковую передачу, bulk transfer или штатные механизмы перебалансировки СУБД; переназначение токена фиксируется только после завершения переноса соответствующего сегмента ключевого пространства. Это позволяет не изменять протоколы транзакционной согласованности и репликации при условии, что переключение маршрутизации выполняется атомарно после подтвержденного переноса сегмента и согласовано с механизмом репликации.
Выводы
1. Предложен метод адаптивного консистентного хеширования, включающий мультипликативный коэффициент интенсивности управления C(t), бюджет переназначений m(t) и гистерезис порогов чувствительности. Ограничения на стоимость перестройки соблюдаются на каждом шаге и на заданном временном горизонте с учетом дискретной верхней оценки перерасхода на длины токенов.
2. Вычислительный эксперимент (7 серий, 30 повторений каждая для С1–С4) показал статистически значимое (p < 0,001) снижение дисбаланса нагрузки относительно алгоритма равномерного распределения А0 в диапазоне 9,8–55,4 % в зависимости от сценария. В стационарных условиях качество балансировки сопоставимо с алгоритмом статического взвешивания А1, который требует априорного знания емкостей узлов. При динамическом изменении состава кластера (С3) снижение дисбаланса относительно А0 и А1 статистически значимо (p < 0,001). Стоимость перестройки ниже, чем у алгоритма динамического взвешивания А2.
3. Установлены условия ограниченной применимости метода: при одновременном действии шума телеметрии σ_ν > ε_off и задержки измерений d ≥ 2 шагов стоимость перестройки возрастает до M_cum = 4,565, а снижение дисбаланса ограничено 9,8 %; без предварительной фильтрации телеметрии применение метода в таких условиях нецелесообразно. При доминировании горячих ключей (распределение Ципфа, s = 1,0) снижение дисбаланса ограничено 31,6 %.
4. Среди возможных направлений дальнейшей работы – распространение подхода на управление отдельными горячими ключами и оперативная адаптация параметров гистерезиса.
Конфликт интересов
Финансирование
Библиографическая ссылка
Батанов А. О., Болбаков Р. Г. МЕТОД АДАПТИВНОГО КОНСИСТЕНТНОГО ХЕШИРОВАНИЯ С БЮДЖЕТНЫМ ОГРАНИЧЕНИЕМ СТОИМОСТИ ПЕРЕСТРОЙКИ РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ // Современные наукоемкие технологии. 2026. № 6. С. 23-32;URL: https://top-technologies.ru/ru/article/view?id=40813 (дата обращения: 03.07.2026).
DOI: https://doi.org/10.17513/snt.40813