Проблема:

Файл размером 1 ГБ создается каждые 24 часа на одной из машин в центре обработки данных Google. Этот файл необходимо скопировать только один раз на все машины во всех центрах обработки данных. Разработайте эту систему.

У Google миллионы машин и центров обработки данных по всему миру. Таким образом, невозможно использовать эту машину в качестве единой централизованной точки обмена файлами. Цель состоит в том, чтобы разработать системную архитектуру и последовательность операций, которые могут обрабатывать эти огромные файлы. Дизайн-интервью проверяет вашу способность быстро анализировать и решать большие проблемы. Это сложно, но возможно, особенно если тщательно подготовиться.

Важные соображения по дизайну:

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

Какие уточняющие вопросы мы можем задать к исходной проблеме?

  1. Можем ли мы сжать этот файл?
  2. Можем ли мы подключить любую пару машин?
  3. Можем ли мы быть отказоустойчивыми к сбоям сети?
  4. Сколько времени потребуется, чтобы скопировать этот файл?
  5. Какие типы аварийных событий могут произойти?
  6. Как оптимизировать время синхронизации
  7. Не все узлы одинаковы по характеристикам вычислений / хранилищ / сети и текущей нагрузке (узел может выполнять тяжелые задачи cpu / gpu).

Оценка емкости и ограничения

  1. Предположим, 1 центр обработки данных имеет в среднем 100 тыс. серверных узлов и машин. Подобным образом все эти серверы подключены через (единую локальную) сеть с плоской топологией, где любой узел может подключаться к любому другому узлу в пределах того же контроллера домена.
  2. Прикинем и предположим, что у нас есть пропускная способность до 400 МБ (загрузка + загрузка).

Если мы обслуживаем этот файл с одного компьютера, одна загрузка займет 1 ГБ / 400 МБ / с = 25 с.

Таким образом, на распространение более 100 тысяч машин потребуется более 25 дней!

Даже если мы предположим, что этот файл представляет собой своего рода файл журнала и может быть сжат до 0,5 размера, это все равно приведет нас к 12–15 дням синхронизации. Так что давайте пока отложим сжатие.

Очевидно, время синхронизации - ключевая проблема этой конструкции, но хорошая новость заключается в том, что она масштабируется ~ O (N / M), где N - количество серверов, а M - количество одноранговых серверов, обслуживающих файлы (M = 1 в нашей спине на салфетке по математике выше)

К концу этого раздела у нас есть ответ на

  1. (4) Сколько времени потребуется для копирования этого файла - от 25 секунд на загрузку до O (N / M) для полной синхронизации.

Очевидно, что эта проблема может выявить совершенно новый уровень сложности, если мы изменим начальное требование с 1 ГБ на 100 ГБ, но это может быть дополнительным вопросом *

Подходы и компромиссы

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

  1. Следует ли разделить файл на более мелкие части и подать его на все машины?
  2. Следует ли нам рассмотреть возможность использования однорангового подхода для решения проблемы O (N / M)?
  3. Должны ли мы просто увеличить файловые серверы M до фиксированного числа, например 100 в O (N / M)?
  4. Как скоординировать 100к машин от жадности и не исчерпать всю пропускную способность сети?

Давайте приступим к изучению идеи совместного использования файлов P2P. В упрощенном случае - для его создания нам нужны 3 вещи - сидеры файлов и загрузчики файлов и индекс сидеров для координации. Последнюю тоже нужно централизовать. Узлы сидера (FS файлового сидера) и леечера (FL) координируются через индексатор. Сам индексатор должен быть с отслеживанием состояния, линейно масштабируемым и отказоустойчивым. Это могло быть реальной практической проблемой.

Процесс согласования p2p следующий.

  1. Узлы FS регистрируются и снимаются с индексации
  2. FL извлекает индексатор и подключается к любому доступному сидеру узла для загрузки файла.
  3. После завершения загрузки FL зарегистрируется в индексаторе и станет FS (1)

Эти шаги повторяются до тех пор, пока в конечном итоге файл не станет доступен всем узлам.

Как решить проблему холодного запуска, когда потенциально все 100k будут пытаться подключиться к одной машине?

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

Знаем ли мы классическую структуру данных, которая могла бы помочь нам представить и индексатор p2p?

Наивным подходом было бы хранилище KV или хеш-карта для реализации блокировки узла во время его загрузки. Компромисс этого подхода заключается в том, что клиенту придется повторять попытки подключения к сидеру и постоянно извлекать это состояние блокировки из индексатора.

Другой вариант - использовать стек / очередь для хранения доступных сидеров. И после каждой загрузки FS и FL могут автоматически помещаться в эту очередь, чтобы ускорить распространение файлов.

Решение

Мой любимый подход - использовать распределенную очередь по следующим причинам. Сидер может поставить в очередь координаты подключения к локальному файловому серверу (ip / порт) и дождаться загрузки. FL просто нужно принять сообщение и подключиться к сеялке для загрузки (которая предоставляет доступ исключительно к этой сеялке). После завершения загрузки у нас будет +2 только что поставленных в очередь сеялок (одна исходная сеялка и одна только что преобразованная пиявка).

  1. Очередь очень легко масштабировать и разбивать на части
  2. Это простой и элегантный подход, основанный на хорошо известной классической концепции.
  3. Для полной синхронизации требуется только время O (Ln (N)) в среднем.
  4. Адаптивное распределение нагрузки - более быстрые сеялки будут быстрее делиться
  5. Наличие в очереди 100 тыс. Сообщений будет означать, что синхронизация завершена.
  6. Поскольку на пике нам нужно обрабатывать до 100 тыс. Оборотов в секунду, мы могли бы развернуть 10 разделов очереди x 10 тыс. Оборотов в секунду, что находится в самом низком диапазоне тестов для любой реализации очереди.

Примечание: простое решение всегда лучше.

Компромиссы

  1. Наихудший сценарий приводит к O (N), когда только один узел может заполнять загрузку.
  2. Медленный FL может быть узким местом для быстрого распространения (узел может быть в середине долгосрочной вычислительной задачи). Как вариант, мы можем исключить такие узлы из раздачи.
  3. Если загрузка не удалась, сеялке необходимо повторно зарегистрироваться в очереди, и это может потенциально перейти в бесконечный цикл в сочетании с тем же плохим FL. С этим можно справиться, сохранив дополнительное состояние счетчика / загрузки в глобальном
  4. Доставка хотя бы один раз - частая ошибка в очередях. Одно и то же сообщение может быть доставлено 2 потребителям, что приводит к состоянию гонки. Чтобы справиться с этим, мы можем использовать TCP-соединение с одним сервером, одновременно доступное на загрузчике. Любые ошибки отказа в соединении должны игнорироваться FL.
  5. Обработка мертвых узлов сеялки в очереди. Поведение аналогично (4) с точки зрения FL
  6. Обработка мертвых FL в процессе измерения. Можно решить, отслеживая его с помощью дополнительного состояния
  7. Что делать, если выйдет из строя один из разделов очереди? Это может быть выполнено с помощью логики / реализации раздела, такой как согласованное хеширование с использованием уникальных атрибутов узла (IP / Mac-адреса / идентификатор оборудования и т. Д.)

Мульти DC

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

Бонусные вопросы:

  1. Что делать, если сеть не ровная?
  2. Что, если частота ошибок соединения между узлами составляет ~ 2% из-за проблем с несколькими арендаторами?
  3. Как следить за процессом?

Понравилась эта статья или есть лучшее решение? Дай мне знать в комментариях.