Как масштабировать алгоритм / сервис / систему с несколькими машинами?

Question

Недавно у меня было несколько интервью, и вполне нормально, когда меня спрашивают о некоторых масштабных проблемах. Например, у вас есть длинный список слов (dict) и список символов в качестве входных данных, разработайте алгоритм для поиска самого короткого слова, которое в dict содержит все символы в списке символов. Затем интервьюер спросил, как масштабировать ваш алгоритм на несколько машин. Другой пример - вы разработали систему управления светофорами для перекрестка в городе. Как вы масштабируете эту систему управления на весь город, который имеет много перекрестков. Я всегда понятия не имею о таких "масштабных" проблемах, приветствую любые предложения и замечания.

Answer 1

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

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

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

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

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

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

Надеюсь, поможет...

Answer 2

Для первого вопроса, как искать слова, которые содержат все символы в списке символов, которые могут одновременно выполняться на другом компьютере. (Пока не самый короткий). Я сделаю это с map-reduce в качестве базы.

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

С помощью map-reduce, вы можете map каждое слово как value и затем проверьте, содержит ли он каждый символ в списке символов.

Map(Word, keyout, valueout){
    //Word comes from dbase, keyout & valueout is input for Reduce
    if(check if word contain all char){
        sharedOutput(Key, Word)//Basically, you send the word to a shared file. 
    //The output shared file, should be managed by the 'said like' hadoop
    }
}

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

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

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