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

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, вы можете фактически использовать простой шаг, чтобы уменьшить его на основе его длины. И тада, ты получишь самую короткую.

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

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