Memcached использует распределенное согласованное хеширование, чтобы выбрать сервер, на который будет помещен ключ, но какой хэш-алгоритм он использует, чтобы сопоставить строковый ключ в финальном хэше, на котором применяется алгоритм Ketama для выбора сервера. И насколько хорош этот алгоритм для распространения похожих ключей на разные серверы.Какой алгоритм хеширования использует memcached для хеш-ключей?
В соответствии с исходным кодом в hash.c, Memcached используется следующий алгоритм:
хэш-функция, используемая здесь Боб Дженкинс, 1996:
http://burtleburtle.net/bob/hash/doobs.html
«Боб Дженкинс, 1996. [email protected] Вы можете использовать этот код по своему усмотрению, частный, образовательный, или коммерческий.
С сайта Боба Дженкинса:
Я предлагаю вам новую хэш-функции для хэш-таблицы поиска, которая быстрее и более тщательно, чем тот, который вы используете в настоящее время. Я также даю вам возможность проверить, что он более тщательный.
Кроме того, его требования:
- Ключи UNALIGNED переменной длины массивы байтов.
- Иногда ключами являются несколько таких массивов.
- Иногда требовался набор независимых хеш-функций.
- Средняя длина ключа варьировалась от 8 до 200 байт.
- Ключами могут быть символьные строки, цифры, бит-массивы или странные вещи.
- Размеры стола могут быть любыми, включая степень 2.
- Хэш должен быть быстрее старого.
- Хэш должен хорошо поработать.
...
Реальное требование, то в том, что хорошая хеш-функция должна распределять хэш-значения равномерно для ключей, которые пользователи на самом деле использовать.
Чтобы вернуться к вашему другому вопросу, он измерил способность алгоритма равномерно распределять значения хэширования, поэтому я бы предположил, что хэш неплохо справляется с распространением подобных ключей на разных серверах. Если у вас есть проблемы, код изолирован, чтобы вы могли запускать собственные тесты.