в чем консистентность консистентного хеширования? можно ли это свойство выразить математически?

консистентность в данном случае — гарантия, что нода будет соответствовать запросу, независимо от структуры кластера (точнее, при любом допустимом изменении кластера)

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

Node(a) before == node(a) after

Да, это неконсистентность по положению на нодах. При ненулевой цене стораджа и нетворка это имеет значение

А что это формула значит ?

добавили ноду, ключ остался на той которой был
кеш миссы не увеличились

но это ведь не для всех ключей.

ну так для большинства
для весьма приличного большинства в зависимости от того сколько нод добавили... с каждой соседней по чуть чуть уйдет...

про модуль нельзя сказать. при изменении числа реплик остаток меняется почти всегда

да, вы правы @BloodJazMan @cblp_su . Вот нашел такое опредение в работе David Karger в которой вводится это понятие "Roughly speaking, a consistent
hash function is one which changes minimally as the range of the
function changes" ... т.е не требуется, чтобы совсем не было измений. требуется минимальность только. Или вот там же "This reflects one intuition about
consistency: when the set of usable buckets changes, items should
only move if necessary to preserve an even distribution"

А никто не может прокомментировать, как в классическом консистентном хешировании понять, какие ключи надо перемещать между серверами, когда добавили новый сервер?

Грубо говоря, как вычислить дифф между старым и новым hash ring?

Когда добавляется новый сервер , то от него тоже берется hash. И получается ,что он делит какой то интервал , который раньше существовал. И соответственно часть этого интервала берет на себя. Обычно эта часть диапазона от его hash до предыдущего hash

Это как раз случай без виртуальных нод. Классический, можно сказать

Да, но ведь ключи базы данных вроде как должны хешироваться перед попаданием на кольцо. И как вернуться от интервалов на кольце к диапазонам ключей?

От ключей тоже берется hash. Т.е у нас есть условно отсортированный список хэшей сервера. Мы взяли хэш от ключа и ищем ближайший к нему хэш ( тот ,который больше хэша ключа ) в списке хэшей сервера. Но если у нас значение key hash больше максимального значения в списке хэшей нод, то берём для него ноду с минимальным хэш ( индекс 0)

Иными словами, практическая реализация ребалансировки в  классическом консистентном хешировании будет выглядеть как полный проход по всей базе с выяснением вопроса, где теперь новое место данного ключа? И перемещение с сервера на сервер тех ключей, у которых новое и старое расположение отличаются

По всей базе не нужно только по ключам одной ноды. Было n1,n2,n3 нод. Стало n1, n11,n2,n3 . Только нода n2 должна переслать часть ключей на n11.

+

Это если у каждой физ ноды по одной позиции на кольце?