Раскладка слотов Maglev — как это работает

Источник: hc/maglev.go Назначение: справка для разработки: что гарантирует алгоритм, что нет и где границы применимости.

Задача

Отобразить 1024 слота на членов пула так, чтобы:

раскладка была детерминированной — одинаковый вход даёт одинаковый результат на любом узле и после любого перезапуска;
слоты делились равномерно (с точностью до веса);
при изменении состава пула переезжало минимальное число слотов.

Номер слота вычисляет датапас: multipath(symmetric_l4, pool_id, modulo_n, 1024, 0, reg1). Демон отвечает только за содержимое таблицы слот → член.

Вход

Что	Откуда	Роль
Живые члены	`m.Active()` — `state=up && admin=enabled`	только они попадают в раскладку
Ключ члена	`Key() = "адрес:порт"`	не ID объекта: пересоздание члена с теми же адресом и портом даёт ту же раскладку
Порядок	`sort.Slice` по `Key()`	убирает зависимость от порядка в конфигурации
`poolID`	`topology.env`	соль хэша: разные пулы дают независимые раскладки
Вес	`WeightOrDefault()`, по умолчанию 1	пропорция слотов

Пустой список живых членов → nil → таблица слотов пуста → fail-close.

Алгоритм — четыре шага

1. Перестановка на каждого члена

Для члена вычисляются два независимых хэша (FNV-32a от poolID ‖ salt ‖ key):

offset = hash(key, poolID, 1) mod M
skip   = hash(key, poolID, 2) mod (M-1) + 1     // затем принудительно нечётный
p[j]   = (offset + j*skip) mod M                 // j = 0..M-1

Это личный порядок обхода слотов данным членом — его «список предпочтений».

Почему skip делается нечётным. Последовательность обойдёт все M слотов, только если skip взаимно прост с M. Классический Maglev рассчитан на простое M; здесь M = 1024 — степень двойки, поэтому достаточно нечётности. Чётный шаг покрыл бы половину слотов, и заполнение зациклилось бы.

2. Квоты по весам

quota[i] = M * weight[i] / totalWeight     (минимум 1)
остаток раздаётся по кругу до суммы M

Квота — верхняя граница числа слотов члена. Именно она, а не длина перестановки, определяет долю.

3. Заполнение

Раунды по членам в отсортированном порядке. В каждом раунде член берёт из своей перестановки первый ещё свободный слот, занимает его и уменьшает квоту. Раунды идут, пока не заполнены все M слотов.

for filled < M:
    for i in members:
        if quota[i] == 0: continue
        c = следующий свободный слот из perm[i]
        table[c] = live[i].ID; quota[i]--; filled++

Конкуренция за слот разрешается по принципу «кто раньше дошёл»: слот достаётся члену, у которого он раньше встретился в перестановке при равных условиях раунда.

4. Страховка

Слоты, оставшиеся -1, отдаются первому живому члену. При нечётном skip это недостижимо; ветка оставлена, чтобы дефект хэша не оставил дыру в таблице.

Что получается на выходе

table []int — 1024 элемента, ID члена в каждом.
Digest(table) — SHA-256 от раскладки, первые 16 hex-символов. Служит для сравнения раскладок между узлами и между перезапусками. Эталон текущего стенда на четырёх членах — 0a16713c5a9eb94d.
FlowBundle(...) — директивы ovs-ofctl bundle: одна строка flow delete table=11, затем priority=0 actions=drop (основание fail-close) и 1024 правила reg1=<слот> → load reg2=<член>, goto_table:12. Весь файл применяется одной транзакцией, поэтому датапас не проходит через состояние с полузаполненной таблицей.

Гарантии и их цена

Свойство	Как достигается	Измерено на стенде
Детерминизм	хэш от `(poolID, key)`, сортировка по ключу, без seed датапаса	дайджест совпадает после `down`/`up`
Равномерность	квоты по весам	256 / 256 / 256 / 256 на четырёх членах
Минимальное возмущение	у оставшихся членов перестановки не изменились, переназначаются только освободившиеся слоты	при выводе одного из четырёх: 256 его слотов переехали обязательно, у остальных сменили владельца 8 из 768 — 1 %

Возмущение малое, но не нулевое: это свойство классического Maglev, а не дефект. Проверка в verify.sh сформулирована как порог (не более 20 слотов), а не как равенство нулю.

Для сравнения: группа type=select при изменении числа бакетов переложила бы все соединения.

Границы применимости

Живые сессии алгоритм не защищает — в текущем stateful-датапасе их держит ct(commit, nat): привязка закрепляется при создании соединения. Ценность минимального возмущения раскроется при переходе на stateless-датапас.
Веса поддержаны в коде, но в конфигурации у всех членов вес 1. Гранулярность веса — 1/1024.
hash_algo_version не реализована. Дайджест считается и логируется, но сравнивать его пока не с кем: узел один.
M фиксировано в двух местах — в правиле multipath и в конфигурации демона (SLOTS в topology.env). Рассинхронизация сделает часть слотов недостижимой.
Пересчёт выполняется только при смене состояния члена (up/down, drain/enable) или по /reapply; если дайджест не изменился, заливка не выполняется.

Как проверить

make slots                                   # раскладка и per-member счётчики
make health | grep дайджест                  # текущий дайджест
make drain M=be1 && make slots               # возмущение при выводе члена
make trace SRC=10.20.0.10 SPORT=40000 SEG=p2 # какой слот и член даёт 5-tuple

Повтор trace с теми же аргументами обязан дать тот же reg1 и reg2 — это и есть проверка детерминизма.

8.6 KiB Raw Permalink Blame History Unescape Escape