Последовательное хеширование: как насчет перефразирования?

Question

Как вы, возможно, знаете, последовательное хеширование - отличная идея при работе с DHT.Основная идея состоит в том, чтобы не сильно страдать при добавлении или удалении нового узла.

Из оригинальной бумаги:

Когда машина добавляется или удаляется из наборакеши, ожидаемая доля объектов, которые должны быть перемещены в новый кеш, - это минимум, необходимый для поддержания сбалансированной нагрузки на кеши.

Решение отличное, но есть явление плохого распределенияиз ключей.Чтобы решить эту проблему, реплики исходных узлов распространяются случайным образом.Это решение работает довольно хорошо.Посмотрите на этот график , если хотите быть уверенным.

Хорошо, похоже, хорошо работает.Но есть кое-что, о чем я думал, что никто не упомянул.

Что происходит, когда один узел добавляется (или удаляется)?Итак, каждый ключ «перед» размещенным узлом необходимо перефразировать.Это кажется хорошим, потому что эти ключи не будут «всеми» ключами.Но если мы решим разместить несколько реплик, скажем, 20, то 20 узлов будут чувствовать боль повторной перефразировки.

Меньшее количество реплик означает худшее распределение, но большее количество реплик означает больше боли, когда необходима перефразировка.

Какое решение, как вы знаете, подойдет в этой ситуации?Я что-то упустил?

Answer 1

Да, я думаю, что вы смотрите на это неправильно.Я буду использовать термины «узел» для машины и «объект» для вещи, которую нужно кэшировать.

В среднем почти каждый узел будет зависеть от добавления нового добавления.Это не плохо;он распределяет нагрузку перефразирования по всем доступным узлам.

Важная часть заключается в том, что большинство объектов не подвержены перефразированию.В среднем, только 1 / узлы объекты должны быть переназначены;и в среднем каждому узлу нужно будет справиться только с переносящимися узлами 1 / узлов ^ 2, что действительно снижает воздействие этого.

Answer 2

Похоже, что вы пытаетесь решить проблему распространения путем увеличения количества реплик, когда «лучшая» хеш-функция справилась бы с задачей.Хорошие хеш-функции обеспечивают хорошее распределение (см. MD5, SHA и т. Д.).