Job 2026 md

title: Алекс Сюй, «System Design. Подготовка к сложному интервью» (Vol. 1, рус. изд.) — глава 5: Согласованное хеширование source: materials/System Design. Подготовка к сложному интервью.pdf, стр. 83–95 конспект: TASK-45.38, извлечено pymupdf 2026-09-17; ниже полный «грязный» текст главы + выжимка статус: выжимка и перенос в knowledge-base.md / methodology.md / classic-designs.md — см. _map.md

Глава 5. Согласованное хеширование

Выжимка

Проблема: hash(key) % N при изменении N (добавили/убрали узел) пересчитывает почти все отображения — лавина кэш-промахов и перегрузка.

Решение — хеш-кольцо: хешируем и ключи, и серверы в одно пространство (например 2^360), ключ обслуживает ближайший сервер по часовой стрелке. При добавлении узла переезжает только его сектор ключей; при удалении — его ключи уходят соседу.

Неравномерность и hot spots лечатся виртуальными нодами: каждый физический сервер представлен сотней-другой точек на кольце → распределение близко к равномерному.

Применения: шардирование БД/кэша, распределённые кэши, routing в CDN/ДЦ. «Управляемый» бонус: часто называемая причина отказа от него — сложность отладки; альтернатива при малых N — таблица соответствий (lookup).

Перенос: KB §6 (стратегии шардирования) — там уже есть consistent hashing + virtual nodes; здесь — происхождение и мотивировка.

Полный текст (грязная выгрузка)

5 СОГЛАСОВАННОЕ ХЕШИРОВАНИЕ Для обеспечения горизонтального масштабирования запросы/данные должны распределяться между серверами эффективно и равномерно. Для этого зачастую используется согласованное хеширование. Давайте сначала подробно поговорим о самой проблеме. ПРОБЛЕМА ПОВТОРНОГО ХЕШИРОВАНИЯ Если у вас есть n кэширующих серверов, балансирование нагрузки обычно обеспечивается с помощью следующего метода хеширования: serverIndex = hash(key) % N, где N — размер пула серверов. Рассмотрим пример того, как это работает. В табл. 5.1 перечислено 4 сер­ вера и 8 строковых ключей вместе с хешами. Таблица 5.1 Ключ Хеш Хеш % 4 ключ 0 18358617 1 ключ 1 26143584 0 ключ 2 18131146 2 ключ 3 35863496 0 ключ 4 34085809 1 ключ 5 27581703 3 ключ 6 38164978 2 ключ 7 22530351 3

84      ГЛАВА 5 Чтобы получить сервер, на котором хранится ключ, мы выполняем опе­ рацию взятия остатка f(key) % 4. Например, hash(key0) % 4 = 1 означает, что для получения закэшированных данных клиент должен обратиться к серверу 1. На рис. 5.1 показано распределение ключей на основе табл. 5.1. Сервер 1 Сервер 2 Сервер 0 Сервер 3 Ключи Серверы serverIndex = hash % 4 Ключ 1 Ключ 0 Ключ 2 Ключ 5 Ключ 3 Ключ 4 Ключ 6 Ключ 7 Индекс сервера 0 1 3 2 Рис. 5.1 Такой подход работает хорошо, когда пул серверов имеет фиксированный размер, а данные распределены равномерно. Но при добавлении новых или удалении существующих серверов возникают проблемы. Например, если сервер 1 выйдет из строя, размер пула станет равным 3. Используя имеющуюся функцию хеширования, мы получим то же значение хеша ключа. Но при взятии остатка индексы серверов изменятся, так как их количество уменьшилось на 1. Применение хеша % 3 даст результаты, показанные в табл. 5.2. Таблица 5.2 Ключ Хеш Хеш % 3 ключ 0 18358617 0 ключ 1 26143584 0 ключ 2 18131146 1 ключ 3 35863496 2 ключ 4 34085809 1 ключ 5 27581703 0 ключ 6 38164978 1 ключ 7 22530351 0

Согласованное хеширование      85 На рис. 5.2 показано распределение ключей на основе табл. 5.2. Сервер 1 Сервер 2 Сервер 0 Сервер 3 Ключи Серверы serverIndex = hash % 3 Ключ 0 Ключ 2 Ключ 3 Ключ 1 Ключ 4 Индекс сервера 0 2 1 Ключ 5 Ключ 7 Ключ 6 Рис. 5.2 Как показано на рис. 5.2, большая часть ключей была распределена заново: изменение коснулось не только тех ключей, которые хранились на вы­ шедшем из строя сервере (сервер 1). Это означает, что при выпадении из пула сервера 1 большинство клиентов начнут извлекать закэшированные данные не из тех серверов. Это приводит к целой лавине кэш-промахов. Согласованное хеширование — эффективный метод борьбы с этой про­ блемой. СОГЛАСОВАННОЕ ХЕШИРОВАНИЕ Цитата из Википедии: «Согласованное хеширование (англ. consistent hashing) — особый вид хеширования, отличающийся тем, что когда хеш- таблица перестраивается, только K/n ключей в среднем должны быть переназначены, где K — число ключей и n — число слотов. В противопо­ ложность этому, в большинстве традиционных хеш-таблиц изменение количества слотов вызывает переназначение почти всех ключей» [1]. Пространство и кольцо хеширования Итак, мы поняли, что такое согласованное хеширование. Теперь давайте посмотрим, как оно работает. Предположим, что в качестве хеш-функции f

86      ГЛАВА 5 используется SHA-1, а ее выходной диапазон имеет вид x0, x1, x2, x3, …, xn. В криптографии пространство хеширования SHA-1 находится между 0 и 2^160 – 1. Это означает, что x0 соответствует 0, xn соответствует 2^160 – 1, а все остальные промежуточные значения находятся между 0 и 2^160 – 1. Это пространство хеширования показано на рис. 5.3. x0 xn Viewer does not support full SVG 1.1 Рис. 5.3 Соединив оба конца, как показано на рис. 5.4, мы получим кольцо хеши­ рования. x0 xn Рис. 5.4 Хеш-серверы Используя ту же хеш-функцию f, мы наносим серверы на кольцо с учетом их IP-адресов или имен.

Согласованное хеширование      87 Сервер 1 Сервер 2 Сервер 0 Сервер 3 s0 s3 s2 s1 Серверы f (server 0) s0 = cервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 Рис. 5.5 Хеш-ключи Стоит упомянуть, что эта хеш-функция отличается от той, которая ис­ пользовалась в «проблеме повторного хеширования», и что здесь нет операции взятия остатка. Как видно на рис. 5.6, на кольцо хеширования нанесено 4 ключа (ключ 0, ключ 1, ключ 2 и ключ 3). k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 Рис. 5.6

88      ГЛАВА 5 Поиск серверов Чтобы определить, на каком сервере хранится ключ, мы идем по часовой стрелке, начиная с позиции ключа на кольце, пока не найдем сервер. Этот процесс показан на рис. 5.7. Если двигаться по часовой стрелке, ключ 0 находится на сервере 0, ключ 1 находится на сервере 1, ключ 2 находится на сервере 2, а ключ 3 находится на сервере 3. k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 Рис. 5.7 Добавление сервера Исходя из логики, описанной выше, добавление нового сервера потребует перераспределения лишь небольшой части ключей. Как видно на рис. 5.8, после добавления сервера 4 перераспределению подлежит только ключ 0. Ключи 1–3 остаются на тех же серверах. Давайте подробнее рассмотрим эту логику. Пока не появился сервер 4, ключ 0 находился на сервере 0. Теперь же он будет храниться на сервере 4, так как именно он встречается первым при прохождении по часовой стрелке от позиции ключа 0 на кольце. В соответствии с алгоритмом ­согласованного хеширования, остальные ключи не пере­ распределяются.

Согласованное хеширование      89 Ключ 0 k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 × Ключ 2 Сервер 4 s4 Рис. 5.8 Удаление сервера При использовании согласованного хеширования удаление сервера по­ требует перераспределения лишь небольшой части ключей. Как видно на рис. 5.9, при удалении сервера 1 необходимо перенести только ключ 1 на сервер 2. Остальные ключи остаются на месте. k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 × Рис. 5.9

90      ГЛАВА 5 Две проблемы базового подхода Алгоритм согласованного хеширования был представлен Каргером и др. в MIT (Массачусетском технологическом институте) [1]. Он состоит из двух основных этапов:

серверы и ключи наносятся на кольцо с использованием равно­ мерно распределенной хеш-функции;

чтобы определить, какому серверу принадлежит ключ, нужно прой­ ти по часовой стрелке от позиции ключа к ближайшему серверу на кольце. У этого подхода есть две проблемы. Первая: учитывая, что серверы могут добавляться и удаляться, их отрезки на кольце не могут иметь фиксиро­ ванный размер. Отрезок — это пространство хеширования между двумя соседними серверами. Размер отрезков, назначаемых каждому серверу, может оказаться как очень маленьким, так и достаточно большим. Как видно на рис. 5.10, в случае удаления s1 отрезок s3 (выделенный двуна­ правленными стрелками) станет в два раза больше, чем отрезки s0 и s3. s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 × Рис. 5.10 Вторая проблема состоит в том, что распределение ключей на кольце может быть неравномерным. Например, если серверы имеют позиции,

Согласованное хеширование      91 как на рис. 5.11, большинство ключей окажутся на сервере 2, а серверы 1 и 3 будут пустовать. s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 Рис. 5.11 Для решения этих проблем используется методика, известная как вир­ туальные узлы или реплики. Виртуальные узлы Виртуальный узел ссылается на настоящий; каждый сервер представлен на кольце несколькими виртуальными узлами. Как показано на рис. 5.12, у сервера 0 и сервера 1 есть по три виртуальных узла. Число 3 выбрано произвольно; в реальных системах виртуальных узлов значительно больше. Теперь сервер 0 представлен на кольце не как s0, а как s0_0, s0_1 и s0_2. Точно так же сервер 1 имеет на кольце обозначения s1_0, s1_1 и s1_2. Благодаря виртуальным узлам каждый сервер отвечает сразу за несколько отрезков. Отрезки (грани) с меткой s0 принадлежат серверу 0, а отрезки с меткой s1 — серверу 1. Чтобы узнать, на каком сервере хранится ключ, мы переходим в его позицию на кольце и двигаемся по часовой стрелке к ближайшему вир­ туальному узлу. Как показано на рис. 5.13, чтобы определить сервер, на

92      ГЛАВА 5 котором находится k0, мы двигаемся по часовой стрелке от его позиции к виртуальному узлу s1_1, который ссылается на сервер 1. s1_0 s0_2 s1_2 s1_1 s1 s0 s0_1 s0_0 s0 Сервер 1 Сервер 0 Серверы s0 = сервер 0 s1 = сервер 1 s1 s0 s1 Рис. 5.12 k0 s1_0 s0_2 s1_2 s1_1 s0_1 s0_0 Сервер 1 Сервер 0 Серверы s0 = сервер 0 s1 = сервер 1 Рис. 5.13

Согласованное хеширование      93 Чем больше виртуальных узлов, тем равномернее становится распреде­ ление ключей. Это вызвано уменьшением стандартного отклонения, бла­ годаря которому данные распределяются более сбалансированно. Стан­ дартное отклонение определяет, как распределены данные. Результаты эксперимента, проведенного в ходе онлайн-исследования [2], показывают, что стандартное отклонение от среднего составляет 5 % и 10 % для 200 и, соответственно, 100 виртуальных узлов. Чем больше виртуальных узлов, тем меньше отклонение. Но при этом нужно больше места для хранения данных о виртуальных узлах. Мы можем подобрать такое количество, которое лучше всего соответствует требованиям нашей системы. Поиск затронутых ключей При добавлении или удалении сервера часть данных нужно перераспре­ делить. Как определить диапазон затронутых ключей? На рис. 5.14 на кольцо наносится сервер 4. Затронутый диапазон начина­ ется с s4 (добавленного узла) и идет по кольцу против часовой стрелки до ближайшего сервера (s3). Таким образом, ключи, размещенные между s3 и s4, необходимо перенести на s4. Ключ 0 k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 × Ключ 2 Сервер 4 s4 Рис. 5.14

94      ГЛАВА 5 Когда сервер (s1) удаляется (как показано на рис. 5.15), затронутый диа­ пазон начинается с s1 (удаленного узла) и идет по кольцу против часовой стрелки до ближайшего сервера (s0). Таким образом, ключи, размещенные между s0 и s1, необходимо перенести на s2. k1 k3 k2 k0 s0 = сервер 0 s1 = сервер 1 s2 = сервер 2 s3 = сервер 3 k0 = ключ 0 k1 = ключ 1 k2 = ключ 2 k3 = ключ 3 Сервер 1 Сервер 2 Сервер 0 Сервер 3 Серверы s0 s3 s2 s1 × Рис. 5.15 ИТОГИ В этой главе мы подробно обсудили согласованное хеширование и объ­ яснили, для чего оно нужно и как оно работает. Этот подход имеет сле­ дующие преимущества.

При добавлении или удалении серверов перераспределяется ми­ нимальное количество ключей.

Его легко горизонтально масштабировать, так как данные распре­ делены более равномерно.

Минимизация проблемы «горячих» ключей. Чрезмерный доступ к какому-то определенному сегменту может привести к перегрузке сервера. Представьте, что информация о Кэтти Перри, Джастине

Согласованное хеширование      95 Бибере и Леди Гаге очутилась в одном и том же сегменте. Согласо­ ванное хеширование помогает бороться с этой проблемой за счет более равномерного распределения данных. Согласованное хеширование широко применяется в реальных системах, среди которых можно выделить следующие:

компонент секционирования данных в БД Dynamo от Amazon [3];

разбиение данных по кластеру в Apache Cassandra [4];

система обмена сообщениями Discord [5];

сеть доставки содержимого Akamai [6];

сетевой балансировщик нагрузки Maglev [7]. Поздравляем, вы проделали длинный путь и можете гордиться собой. Отличная работа! СПРАВОЧНЫЕ МАТЕРИАЛЫ [1]  Согласованное хеширование: https://ru.wikipedia.org/wiki/Согласованное_хе­ ширование [2]  Consistent Hashing: https://tom-e-white.com/2007/11/consistent-hashing.html [3]  Dynamo: Amazon’s Highly Available Key-value Store: https://www. allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf [4]  Cassandra - A Decentralized Structured Storage System: http://www.cs.cornell. edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF [5]  How Discord Scaled Elixir to 5,000,000 Concurrent Users: https://blog.discord. com/scaling-elixir-f9b8e1e7c29b [6]  CS168: The Modern Algorithmic Toolbox Lecture #1: Introduction and Consistent Hashing: http://theory.stanford.edu/~tim/s16/l/l1.pdf [7]  Maglev: A Fast and Reliable Software Network Load Balancer: https://static. googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf