При разработке масштабируемой системы одним из наиболее важных аспектов является определение того, как данные будут разделены и реплицированы между серверами.
Давайте сначала определим разделение и репликацию, чтобы мы были на одной странице.
Разделение данных: это процесс распределения данных по набору серверов. Это улучшает масштабируемость и производительность системы.
Репликация данных: это процесс создания нескольких копий данных и их хранения на разных серверах. Это улучшает доступность и надежность данных в системе.
Стратегии разделения и репликации данных лежат в основе любой распределенной системы. Тщательно разработанная схема разделения и репликации данных повышает производительность, доступность и надежность системы, а также определяет, насколько эффективно система будет масштабироваться и управляться.
Дэвид Каргер и др. впервые представил согласованное хеширование в своей статье 1997 года и предложил использовать его в распределенном кэшировании. Позже согласованное хеширование было адаптировано и улучшено для использования во многих распределенных системах. В этом посте мы увидим, как согласованное хеширование эффективно решает проблему разделения и репликации данных. Давайте идти.
Что такое разделение данных?
Как указано выше, процесс распределения данных по набору узлов называется разделением данных. Когда мы пытаемся распространять данные, возникают две проблемы:
- Как мы узнаем, на каком узле будет храниться конкретный фрагмент данных?
- Когда мы добавляем или удаляем узлы, как мы узнаем, какие данные будут перемещены из существующих узлов в новые узлы? Кроме того, как мы можем минимизировать перемещение данных при присоединении или выходе узлов?
Наивный подход будет использовать подходящую хеш-функцию для сопоставления ключа данных с числом. Затем найдите сервер, применив его по модулю к этому числу и общему количеству серверов. Например:
Схема, описанная на диаграмме выше, решает проблему поиска сервера для хранения / извлечения данных. Но когда мы добавляем или удаляем сервер, все наши существующие сопоставления будут нарушены. Это связано с тем, что будет изменено общее количество серверов, которые использовались для поиска фактического сервера, на котором хранятся данные. Итак, чтобы все снова заработало, мы должны переназначить все ключи и переместить наши данные на основе нового количества серверов, что будет полным беспорядком!
Последовательное хеширование приходит на помощь
Распределенные системы могут использовать согласованное хеширование для распределения данных по узлам. Последовательное хеширование сопоставляет данные с физическими узлами и гарантирует, что только небольшой набор ключей перемещается при добавлении или удалении серверов.
Последовательное хеширование хранит данные, управляемые распределенной системой, в кольце. Каждому узлу в кольце назначается диапазон данных. Вот пример последовательного хеш-кольца:
При последовательном хешировании кольцо делится на более мелкие заранее определенные диапазоны. Каждому узлу назначается один из этих диапазонов. Начало диапазона называется токеном. Это означает, что каждому узлу будет присвоен один токен. Диапазон, назначенный каждому узлу, вычисляется следующим образом:
Начало диапазона: значение токена
Конец диапазона: значение следующего токена - 1
Вот токены и диапазоны данных четырех узлов, описанных на диаграмме выше:
Когда системе требуется прочитать или записать данные, первым делом она применяет алгоритм хеширования MD5 к ключу. Выходные данные этого алгоритма хеширования определяют, в каком диапазоне находятся данные и, следовательно, на каком узле они будут храниться. Как мы видели выше, каждый узел должен хранить данные для фиксированного диапазона. Таким образом, сгенерированный из ключа хеш сообщает нам узел, на котором будут храниться данные.
MD5 (также известный как алгоритм MD5 Message-Digest) - это функция хеширования, которая принимает сообщение любой длины в качестве входных и возвращает в качестве выходных данных значение дайджеста фиксированной длины.
Как мы видели выше, каждый узел должен хранить данные для фиксированного диапазона. Таким образом, сгенерированный из ключа хеш сообщает нам узел, на котором будут храниться данные.
Описанная выше схема согласованного хеширования отлично работает, когда узел добавляется или удаляется из кольца, как в этих случаях, поскольку затрагивается только следующий узел. Например, когда узел удаляется, следующий узел становится ответственным за все ключи, хранящиеся на исходящем узле. Однако эта схема может привести к неравномерному распределению данных и нагрузки. Решить эту проблему можно с помощью Виртуальных узлов.
Виртуальные узлы
Добавление и удаление узлов в любой распределенной системе довольно распространено. Например, существующие узлы могут умереть, и может потребоваться их вывод из эксплуатации. Точно так же новые узлы могут быть добавлены к существующему кластеру для удовлетворения растущих потребностей. Чтобы эффективно обрабатывать эти сценарии, согласованное хеширование использует виртуальные узлы (или виртуальные узлы).
Как мы видели выше, базовый алгоритм согласованного хеширования назначает один токен (или последовательный диапазон хеширования) каждому физическому узлу. Это было статическое разделение диапазонов, которое требует вычисления токенов на основе заданного количества узлов. Эта схема сделала добавление или замену узла дорогостоящей операцией, так как в этом случае мы хотели бы перебалансировать и распределить данные по всем другим узлам, что привело бы к перемещению большого количества данных. Вот несколько потенциальных проблем, связанных с ручным и фиксированным разделением диапазонов:
- Добавление или удаление узлов: добавление или удаление узлов приведет к перерасчету токенов, что вызовет значительные административные издержки для большого кластера.
- Горячие точки. Поскольку каждому узлу назначен один большой диапазон, некоторые узлы могут стать горячими точками, если данные распределены неравномерно.
В распределенной системе любой сервер, ответственный за огромный раздел данных, может стать узким местом для системы. Большая часть запросов на хранение и извлечение данных будет поступать на этот узел, что может эффективно снизить производительность всей системы. Такие загруженные серверы называются точками доступа.
- Восстановление узла. Поскольку данные каждого узла могут быть реплицированы (для обеспечения отказоустойчивости) на фиксированное количество других узлов, когда нам нужно перестроить узел, только его узлы-реплики могут предоставить данные. Это создает большую нагрузку на узлы-реплики и может привести к ухудшению качества обслуживания.
Для решения этих проблем в Consistent Hashing введена новая схема распределения токенов по физическим узлам. Вместо того, чтобы назначать один токен узлу, хэш-диапазон делится на несколько меньших диапазонов, и каждому физическому узлу назначается несколько из этих меньших диапазонов. Каждый из этих поддиапазонов считается Vnode. С Vnodes, вместо того, чтобы узел отвечать только за один токен, он отвечает за множество токенов (или поддиапазонов).
На практике виртуальные узлы случайным образом распределены по кластеру и обычно не являются смежными, так что никакие два соседних виртуальных узла не назначаются одному и тому же физическому узлу или стойке. Кроме того, узлы содержат копии других узлов для обеспечения отказоустойчивости. Кроме того, поскольку в кластерах могут быть разнородные машины, некоторые серверы могут содержать больше виртуальных узлов, чем другие. На рисунке ниже показано, как физические узлы A, B, C, D и E используют виртуальные узлы. Каждому физическому узлу назначается набор виртуальных узлов, и каждый виртуальный узел реплицируется один раз.
Преимущества Vnodes
Vnodes дает следующие преимущества:
- Поскольку виртуальные узлы помогают более равномерно распределять нагрузку по физическим узлам в кластере, разделяя диапазоны хеширования на более мелкие поддиапазоны, это ускоряет процесс перебалансировки после добавления или удаления узлов. Когда добавляется новый узел, он получает множество виртуальных узлов от существующих узлов для поддержания сбалансированного кластера. Точно так же, когда узел необходимо перестроить, вместо получения данных от фиксированного числа реплик в процессе перестройки участвуют многие узлы.
- Виртуальные узлы упрощают обслуживание кластера, содержащего разнородные машины. Это означает, что с помощью Vnodes мы можем назначить большое количество поддиапазонов мощному серверу и меньшее количество поддиапазонов - менее мощному серверу.
- В отличие от одного большого диапазона, поскольку виртуальные узлы помогают назначать меньшие диапазоны каждому физическому узлу, это снижает вероятность возникновения горячих точек.
Репликация данных с использованием согласованного хеширования
Чтобы обеспечить высокую доступность и надежность, согласованное хеширование реплицирует каждый элемент данных на нескольких N узлах в системе, где значение N эквивалентно коэффициенту репликации .
Коэффициент репликации - это количество узлов, которые получат копии одних и тех же данных. Например, коэффициент репликации, равный двум, означает, что есть две копии каждого элемента данных, причем каждая копия хранится на другом узле.
Каждый ключ назначается узлу координатора (обычно первому узлу, попадающему в диапазон хеширования), который сначала сохраняет данные локально, а затем реплицирует их на N-1 по часовой стрелке узлов-преемников на кольце. Это приводит к тому, что каждый узел владеет областью в кольце между ним и его N-м предшественником. В системе в конечном итоге согласованной репликация выполняется асинхронно (в фоновом режиме).
В постоянно согласованных системах копии данных не всегда должны быть идентичными, если они предназначены для того, чтобы в конечном итоге стать согласованными. В распределенных системах конечная согласованность используется для достижения высокой доступности.
Сценарии использования последовательного хеширования
Amazon Dynamo и Apache Cassandra используют согласованное хеширование для распределения и репликации данных между узлами.
Последовательное хеширование в интервью по проектированию системы
Как мы видели выше, согласованное хеширование помогает эффективно разделять и реплицировать данные; Таким образом, любая распределенная система, которой необходимо увеличивать или уменьшать масштаб или которая хочет достичь высокой доступности за счет репликации данных, может использовать согласованное хеширование. Вот несколько таких примеров:
- Любая система, работающая с набором серверов хранения (или базы данных), должна увеличиваться или уменьшаться в зависимости от использования, например, системе может потребоваться больше памяти во время Рождества из-за высокого трафика.
- Любая распределенная система, которая требует динамической настройки использования кеша путем добавления или удаления серверов кеширования в зависимости от нагрузки трафика.
- Любая система, которая хочет реплицировать свои сегменты данных для достижения высокой доступности.
Ссылки и дополнительная литература
Посетите Design Gurus, чтобы найти несколько хороших курсов по собеседованию по системному дизайну.
