Существует ли гарантированная справедливая вариация для последовательного хеширования?

Question

Я ищу что-то вроде Consistent Hashing, но с гарантией того, что дистрибутив окажется максимально справедливым (а не только в среднем для случайных ключей) - есть ли такая вещь и где я могу ее найти, если так?

Редактировать: в моем конкретном случае, набор ключей известен заранее (и "маленький"). Именно эти ключи всегда будут присутствовать и должны быть выделены ровно одному узлу каждый в любой данный момент времени.

Answer 1

Похоже, вы ищете минимальный идеальный хэш.

Answer 2

не только в среднем для случайных ключей

Это не точное описание гарантий, предоставляемых последовательным хешированием. Во-первых, "в среднем" не учитывается тот факт, что при случайном размещении большого количества виртуальных узлов на окружности и хорошего семейства хэш-функций (например, одного, который является логарифмически независимым), дисбаланс нагрузки серьезно вряд ли будет большим (я считаю, что обычный дисбаланс должен быть порядка квадратного корня из числа клавиш, назначенных конкретной машине). Во-вторых, ключи не должны быть случайными, если они не зависят от случайно выбранной хэш-функции (забывчивый противник).

Так как вы хотите, чтобы хэширование всегда было справедливым, рандомизация не поможет, поскольку у ГСЧ могут быть результаты, неотличимые от этого. Никакой детерминированный алгоритм не может назначать предпочтения узлов ключам статически без возможности дисбаланса, если ключи не известны в автономном режиме.

Если у вас достаточно мало предметов, которые вас волнуют из-за дисбаланса квадратного корня, вы можете выполнить старомодную балансировку нагрузки с учетом состояния.