Consistent hashing, Rendezvous hashing | Вопросы собеседований

• В видео обсуждаются способы шардирования данных, включая использование хэш-функции для определения позиции данных на сервере.  

• Обсуждаются преимущества и недостатки различных алгоритмов шардирования, включая рандеву хэшинг и консистентное каширование.  

• Рандеву хэшинг основан на выборе максимального значения хэш-функции для определения позиции данных на сервере.  

• Этот подход обеспечивает равномерное распределение нагрузки при добавлении новых серверов.  

• Консистентное каширование использует окружность для распределения данных между серверами.  

• Каждый ключ проецируется на окружность, и затем определяется, на какой сервер его отправить.  

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

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

• Однако, при добавлении новых шартов, распределение ключей может быть неравномерным.  

• Автор предлагает улучшить алгоритм, распределяя шарты по окружности не в случайном порядке, а по модулю от 360 градусов.  

• Это позволяет сделать распределение ключей более равномерным.  

• Автор объясняет, как можно преобразовать один шарт в несколько виртуальных нод, используя хэш-функцию и конкатенацию идентификаторов шартов.  

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

• Консистентное хэширование обладает полезным свойством: при добавлении новых шартов данные будут перемещаться только на следующий шарт по часовой стрелке.  

• Это обеспечивает более равномерное распределение нагрузки на шарты и предотвращает хаотичное перемещение данных между серверами.  

• В видео обсуждаются два подхода к шардированию: рандеву хэшинг и консистен хэшинг.  

• Рандеву хэшинг используется в реби кью и позволяет равномерно распределять трафик между очередями.  

• Консистен хэшинг позволяет указывать веса очередей и распределять нагрузку в зависимости от количества задействованных шардов.  

• Рандеву хэшинг имеет линейную сложность относительно количества шардов, а консистен хэшинг - логарифмическую.  

• Выбор алгоритма зависит от конкретных потребностей и сложности реализации.  

• В видео предлагается использовать хэш от ключа по модулю количества партиций для равномерного распределения трафика.  

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

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

• Упоминаются популярные базы данных, такие как Redis, Hazelcast, Cassandra и PostgreSQL, которые уже имеют оптимизированные алгоритмы для большинства случаев использования.  

• Автор объясняет, что знание алгоритмов поиска может быть полезным для понимания гарантий, предоставляемых различными базами данных.  

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

• Автор обсуждает, как важно заранее знать о возможных проблемах при миграции данных и как это может помочь избежать проблем в будущем.  

• Он также упоминает, что создание новых топиков и переключение между ними может быть сложным процессом, требующим интеллектуального труда.