Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 1,279

ADAPTIVE CONSISTENT HASHING METHOD WITH BUDGETED REDISTRIBUTION COST CONSTRAINT

1

• Authors
• Files
• Abstract
• Keywords
• References

Введение

В распределенных системах хранения данных назначение ключей узлам осуществляется через консистентное хеширование: каждому ключу сопоставляется позиция на хеш-кольце, а ближайший токен определяет ответственный узел [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. Среди возможных направлений дальнейшей работы – распространение подхода на управление отдельными горячими ключами и оперативная адаптация параметров гистерезиса.

---

Conflict of interest

---

Financing

---

Библиографическая ссылка

Батанов А. О., Болбаков Р. Г. МЕТОД АДАПТИВНОГО КОНСИСТЕНТНОГО ХЕШИРОВАНИЯ С БЮДЖЕТНЫМ ОГРАНИЧЕНИЕМ СТОИМОСТИ ПЕРЕСТРОЙКИ РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ // Современные наукоемкие технологии. 2026. № 6. С. 23-32;
URL: https://top-technologies.ru/en/article/view?id=40813 (дата обращения: 03.07.2026).
DOI: https://doi.org/10.17513/snt.40813