7 алгоритмов, которые нужно знать перед следующим собеседованием по проектированию системы

Отлично начните свое следующее собеседование по системному проектированию.

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

Вот список концепций, которые мы будем обсуждать:

1. Дерево Меркла
2. Согласованное хеширование
3. Читать Ремонт
4. Протокол сплетен
5. Фильтр Блума
6. Сердцебиение
7. Теоремы CAP и PACELC

Давайте начнем.

1. Дерево Меркла

Используется для выявления несоответствий данных между серверами.

Фон

Распределенные системы поддерживают несколько копий данных на разных серверах (называемых репликами) для обеспечения отказоустойчивости и более высокой доступности. Для синхронизации данных между всеми серверами-репликами системе необходим эффективный механизм сравнения данных между двумя репликами. Как в распределенной среде мы можем быстро сравнить две копии диапазона данных, находящихся на двух разных репликах, и выяснить, какие именно части отличаются?

Определение

Реплика может содержать много данных. Наивное разбиение всего диапазона для вычисления контрольных сумм для сравнения не очень осуществимо; просто слишком много данных для передачи. Вместо этого мы можем использовать деревья Меркла для сравнения реплик диапазона.

Решение

Дерево Меркла — это бинарное дерево хэшей, где каждый внутренний узел является хэшем двух его дочерних элементов, а каждый листовой узел — хэшем части исходных данных.
Сравнение деревьев Меркла концептуально просто:

1. Сравните корневые хэши обоих деревьев.
2. Если они равны, остановитесь.
3. Рекурсия по левому и правому детям.

В конечном итоге это означает, что реплики точно знают, какие части диапазона отличаются, но объем передаваемых данных сведен к минимуму. Основное преимущество дерева Меркла заключается в том, что каждую ветвь дерева можно проверить независимо, не требуя от узлов загрузки всего дерева или всего набора данных. Следовательно, деревья Меркла минимизируют объем данных, которые необходимо передать для синхронизации, и уменьшают количество операций чтения с диска.

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

Примеры

Для антиэнтропии и разрешения конфликтов в фоновом режиме Dynamo от Amazon использует деревья Меркла.

Подробности: https://lnkd.in/gZpt67uU

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

Распределенные системы используют согласованное хеширование для распределения данных между серверами.

Согласованное хеширование помогает в двух вещах:

1. Он сопоставляет данные с физическими серверами. Всякий раз, когда система хочет прочитать или записать данные, согласованное хеширование сообщает нам, какой сервер хранит данные.
2. Это гарантирует, что при добавлении или удалении серверов перемещается только небольшой набор ключей.

Подробнее: https://lnkd.in/dJQKjN6i

3. Читать Ремонт

Когда данные реплицируются на несколько серверов, функция «Read Repair» используется для передачи последней версии данных на серверы с более старой версией.

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

Подробности: https://lnkd.in/g6kCVgvr

4. Протокол сплетен

Используется для эффективного обмена информацией о состоянии между серверами.

Каждый сервер отслеживает информацию о состоянии других серверов в кластере и сплетничает (то есть делится) этой информацией с одним случайным сервером каждую секунду. Таким образом, в конце концов, каждый сервер узнает о состоянии каждого другого узла в кластере.

Подробности: https://bit.ly/3D2w14j

5. Фильтр Блума

Структура данных фильтра Блума сообщает, может ли элемент быть в наборе или определенно не входит. Единственными возможными ошибками являются ложные срабатывания, т. е. поиск несуществующего элемента может дать неверный ответ. Чем больше элементов в фильтре, тем выше частота ошибок. Пустой фильтр Блума представляет собой битовый массив из m битов, каждый из которых установлен в 0. Существуют также k различных хэш-функции, каждая из которых отображает элемент набора в одну из m битовых позиций.

• Чтобы добавить элемент, передайте его хеш-функциям, чтобы получить k битовые позиции, и установите биты в этих позициях в 1.
• Чтобы проверить, находится ли элемент в наборе, передайте его хеш-функциям, чтобы получить k битовых позиций.
• Если любой из битов в этих позициях равен 0, элемента определенно нет в наборе.
• Если все равны 1, то элемент может быть в наборе.

Вот фильтр Блума с тремя элементами P, Q и R. Он состоит из 20 бит и использует три хеш-функции. Цветные стрелки указывают на биты, на которые отображаются элементы набора.

Фильтр Блума, состоящий из 20 бит.

• Элемента X точно нет в наборе, так как он хешируется в битовую позицию, содержащую 0.
• Для фиксированной частоты ошибок добавление нового элемента и проверка на принадлежность являются операциями с постоянным временем, а фильтр с местом для 'n' элементов требует O(n) пространства .

Подробности: https://bit.ly/3TbSAsR

6. Сердцебиение

Используется для трансляции состояния работоспособности сервера.

Фон

В распределенной среде данные (или работа) распределяются между серверами. Такая настройка требует, чтобы серверы знали, какие другие серверы являются частью системы, чтобы эффективно маршрутизировать запросы. Кроме того, серверы должны иметь возможность определить, запущены ли другие серверы. В децентрализованной среде всякий раз, когда на сервер поступает запрос, сервер должен иметь возможность решить, какой сервер отвечает за обработку этого запроса. Таким образом, своевременное обнаружение сбоя сервера имеет решающее значение, позволяя системе принять корректирующие меры и переместить данные (или работу) на другой работоспособный сервер и предотвратить дальнейшее ухудшение состояния среды.

Определение

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

Решение

Heartbeating — один из механизмов обнаружения сбоев в распределенной системе. Если есть центральный сервер, все серверы периодически отправляют ему сообщения пульса. Если центрального сервера нет, все серверы случайным образом выбирают набор серверов и отправляют им сообщение пульса каждые несколько секунд. Таким образом, если какое-то время от сервера не поступает сообщение пульса, система может заподозрить, что сервер мог выйти из строя. Если в течение настроенного периода таймаута нет пульса, система может сделать вывод, что сервер больше не жив, и прекратить посылать ему запросы и начать работу над его заменой.

Пример

Файловая система Google (GFS)и HDFSиспользуют Heartbeating для связи друг с другом серверов в системе, чтобы давать инструкции и собирать информацию о состоянии.

Подробности: https://bit.ly/3eFnT04

7. Теоремы CAP и PACELC

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

Подробности: https://lnkd.in/dTFksWj9

Заключение

➡ Практикуйте эти концепции проектирования систем, чтобы отличаться от других!

➡ Узнайте больше об этих подходах в разделах «Собеседование по разработке системы» и Собеседование по разработке продвинутой системы.

➡ Подпишитесь на меня в Linkedin, чтобы получать советы по проектированию системы и интервью по программированию.

Узнайте больше об интервью по системному проектированию и кодированию: