бегущий за софт скиллами...
Links:
- https://dmedovich.com
- https://github.com/dmedovich
не кусаюсь! -> @dmedovich
Post #30
137
В погоне за ядрами: история про микрооптимизацию хеш-функции
Иногда значительная часть CPU уходит на операцию, которая вообще не выглядит проблемой. Например, системе нужно решить, какой узел должен владеть конкретным ключом.
Это может быть:
- shard;
- cache node;
- worker;
- storage node;
- backend в динамическом пуле;
- узел, которому назначается конкретный объект.
Если узлов несколько — проблем нет. Но если их тысячи или десятки тысяч, выбор владельца сам становится горячей CPU-операцией.
Rendezvous Hashing, или Highest Random Weight (HRW), решает задачу довольно просто. Для каждого узла вычисляется score:
А можно ли просто использовать другой алгоритм?
Существуют алгоритмы, которые смотрят на проблему с другой стороны.
- Jump Consistent Hash уменьшает стоимость поиска до
- Power Consistent Hash идёт ещё дальше и даёт
Но это уже немного другая задача. Если идентификаторы узлов произвольные и разреженные, возникает дополнительный слой:
В чём идея VRH
Пусть:
оба представлены как
VRH вычисляет score следующим образом:
Здесь
XOR
XOR с фиксированным значением обратим и является своей собственной противоположностью.
Сложение
Для
XOR со сдвигом
Эта формула хорошо ложится на SIMD. При обычном HRW для каждого узла мы делаем примерно одно и то же:
Но вычисления между узлами независимы. Нет зависимости вида:
В горячей части вычисления score VRH не использует умножение над
Бенчмарки
Контур 1: выбор владельца
Основной эксперимент. Для каждого ключа необходимо вернуть один node:
Контур 2: полное ранжирование
Здесь измеряется уже другая операция:
Для этого использовался
Методология
Все основные результаты получены на одной машине:
Все прогонялось минимум 10 раз, чтобы результат представлялся медианой
Результаты на картинке(в комментах) и выводы ниже:
Довольно интересно было конечно покопаться, иногда основная проблема находится не в сложности алгоритма, а в стоимости операции, которую мы выполняем N раз.
Сомневаюсь конечно, что когда нибудь довёдется что-то такое руками на больших проектах делать, но в копилочку положить вариант, куда еще можно посмотреть точно стоит. Ну и как коллега у себя это попробует спустя время сделаю ретроспективу результатов, все же это делалось чтобы перестать тратить CPU там, где его можно не тратить. (Ну еще и чтоб SIMD потрогать, а то постов о нем куча везде, а руками трогать негде)
код: https://github.com/dmedovich/VRH
Иногда значительная часть CPU уходит на операцию, которая вообще не выглядит проблемой. Например, системе нужно решить, какой узел должен владеть конкретным ключом.
Это может быть:
- shard;
- cache node;
- worker;
- storage node;
- backend в динамическом пуле;
- узел, которому назначается конкретный объект.
Если узлов несколько — проблем нет. Но если их тысячи или десятки тысяч, выбор владельца сам становится горячей CPU-операцией.
Rendezvous Hashing, или Highest Random Weight (HRW), решает задачу довольно просто. Для каждого узла вычисляется score:
score(key, node) а владельцем становится узел с максимальным score: owner(key) = argmax score(key, node). Если узлов N, то для одного ключа нужно вычислить score для всех N узлов. То есть сложность O(N), что на первый взгляд это не очень привлекательно. Но у HRW есть важное свойство: узлы могут иметь произвольные идентификаторы. Не обязательно иметь: 0, 1, 2, 3, ..., N-1.Идентификатором может быть uint64, hash, UUID, публичный ключ или любое другое значение, которое система использует для идентификации узла. Узел можно добавить или удалить, не перестраивая нумерацию остальных. Для многих распределённых систем это очень удобная модель.А можно ли просто использовать другой алгоритм?
Существуют алгоритмы, которые смотрят на проблему с другой стороны.
- Jump Consistent Hash уменьшает стоимость поиска до
O(log N) и использует очень мало памяти. Но его модель предполагает последовательную нумерацию buckets.- Power Consistent Hash идёт ещё дальше и даёт
O(1) ожидаемое время поиска, также работая с плотным диапазоном bucket ID. Это прекрасные решения, когда модель системы позволяет представить узлы как: 0 ... N-1Но это уже немного другая задача. Если идентификаторы узлов произвольные и разреженные, возникает дополнительный слой:
node ID -> dense bucketID. А при динамическом удалении узлов нужно ещё поддерживать соответствие между этими пространствами. В HRW такого слоя нет. Поэтому не пытаемся сделать сделать быстрее O(N), вместо этого пытаемся узнать насколько дешевым можно сделать сам O(N)-скан. Так появилась идея VRH.В чём идея VRH
Пусть:
key — ключ;node — идентификатор узла;оба представлены как
uint64.VRH вычисляет score следующим образом:
k = SplitMix64(key)
x = node XOR k
x += ROTL(k, 23)
x ^= x >> 29
x += ROTL(k, 41)
x ^= x << 17
x ^= x >> 32
score(key, node) = x
Здесь
SplitMix64 используется для предварительного смешивания ключа, а дальше выполняется последовательность операций над 64-битным словом. У такой конструкции есть два свойства, которые для этой задачи особенно важны. Score не должен сталкиваться для разных узлов Для фиксированного ключа хочется, чтобы разные узлы давали разные scores. Иначе два разных узла могут получить одинаковый максимум, и результат начнёт зависеть от порядка обхода. У VRH это можно получить алгебраически. Для фиксированного key значение: k = SplitMix64(key) фиксировано. Дальше node проходит через композицию обратимых преобразований.XOR
x = node XOR kXOR с фиксированным значением обратим и является своей собственной противоположностью.
Сложение
x += cДля
uint64 это сложение по модулю 2^64. Оно также обратимо: обратная операция — вычитание той же константы по модулю 2^64XOR со сдвигом
x ^= x >> r и x ^= x << r являются обратимыми xorshift-преобразованиями. Следовательно, вся последовательность является композицией биекций. То есть разные node дают разные score. Это полезное свойство, но биективность не доказывает статистическую равномерность распределения. Она доказывает отсутствие коллизий внутри отображения по node.Эта формула хорошо ложится на SIMD. При обычном HRW для каждого узла мы делаем примерно одно и то же:
node 1 -> score
node 2 -> score
node 3 -> score
node 4 -> score
Но вычисления между узлами независимы. Нет зависимости вида:
score(node[i+1]) зависит от score(node[i]). Значит, их можно выполнять параллельно. AVX2 предоставляет 256-битные регистры. В них помещается: 4 × uint64. Поэтому можно обработать четыре узла одновременно. После этого остаётся только найти максимум. Именно поэтому E19 задумывался как score-функция, удобная для дешёвого линейного скана.В горячей части вычисления score VRH не использует умножение над
node. Основные операции: XOR | ADD | SHIFT | ROTATE | XOR. Для этой конкретной задачи хотелось получить максимально простую последовательность операций, которую можно развернуть сразу на несколько независимых node ID.Бенчмарки
Контур 1: выбор владельца
Основной эксперимент. Для каждого ключа необходимо вернуть один node:
owner(key) Сравнение выполняется с go-rendezvous. Этот benchmark показывает эффект VRH как оптимизации ownership-операции.Контур 2: полное ранжирование
Здесь измеряется уже другая операция:
sort(nodes by score).Для этого использовался
nspcc-dev/hrw/v2.Методология
Все основные результаты получены на одной машине:
CPU: AMD Ryzen 5 2600
OS: Linux amd64
Go: 1.27.1
Все прогонялось минимум 10 раз, чтобы результат представлялся медианой
Результаты на картинке(в комментах) и выводы ниже:
Довольно интересно было конечно покопаться, иногда основная проблема находится не в сложности алгоритма, а в стоимости операции, которую мы выполняем N раз.
Сомневаюсь конечно, что когда нибудь довёдется что-то такое руками на больших проектах делать, но в копилочку положить вариант, куда еще можно посмотреть точно стоит. Ну и как коллега у себя это попробует спустя время сделаю ретроспективу результатов, все же это делалось чтобы перестать тратить CPU там, где его можно не тратить. (Ну еще и чтоб SIMD потрогать, а то постов о нем куча везде, а руками трогать негде)
код: https://github.com/dmedovich/VRH
- 🔥 2
- 🏆 1
