Параллельный десятый алгоритм распределенных данных

Ответ 1

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

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

Каждая машина сортирует свой собственный журнал.

"Главный" компьютер объединяет данные с отдельных компьютеров и делает верхний выбор K. Это на самом деле две проблемы, но их можно объединить в один.

Мастер создает две очереди приоритетов: одну для слияния и одну для выбора верхнего К. Первый имеет размер N, где N - количество компьютеров, с которых они объединяют данные. Второй - размер K: количество элементов, которые вы хотите выбрать. Для этого я использую кучу минут, так как это легко и разумно быстро.

Чтобы настроить очередь слияния, инициализируйте очередь и получите первый элемент с каждого из "рабочих" компьютеров. В псевдокоде ниже "получить наименьший элемент из очереди слияния" означает получение корневого элемента из очереди слияния, а затем получение следующего элемента из того, какой рабочий компьютер представил этот элемент. Поэтому, если очередь содержит [1, 2, 3], а элементы поступают с компьютеров B, C, A (в этом порядке), то получение младшего элемента означает получение следующего элемента с компьютера B и добавление его в очередь приоритета.

Затем мастер выполняет следующее:

working = get lowest item from merge queue
while (items left to merge)
{
    temp = get lowest item from merge queue
    while (temp.url == working.url)
    {
        working.count += temp.count
        temp = get lowest item from merge queue
    }
    // Now have merged counts for one url.
    if (topK.Count < desired_count)
    {
        // topK queue doesn't have enough items yet.
        // so add this one.
        topK.Add(working);
    }
    else if (topK.Peek().count < working.count)
    {
        // the count for this url is larger
        // than the smallest item on the heap
        // replace smallest on the heap with this one
        topK.RemoveRoot()
        topK.Add(working)
    }
    working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
    // the count for this url is larger
    // than the smallest item on the heap
    // replace smallest on the heap with this one
    topK.RemoveRoot()
    topK.Add(working)
}

В этот момент очередь topK имеет элементы K с наивысшим количеством отсчетов.

Таким образом, каждый компьютер должен выполнять сортировку слиянием, которая представляет собой O (n log n), где n - количество элементов в этом журнале компьютера. Слияние на хозяине - O (n), где n - сумма всех элементов с отдельных компьютеров. Выбор верхних позиций k - O (n log k), где n - количество уникальных URL-адресов.

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

Ответ 2

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

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

• Используйте хэш-функцию с ограниченным целевым пространством (скажем, 10 000, обратите внимание, что ожидаются встречные значения хэш-функции), чтобы вычислить хэш-значение каждого элемента в файле журнала и подсчитать, сколько раз каждое из значений имеет значение. Сообщайте полученную гистограмму с сервером (хотя, вероятно, также возможно избежать централизованного сервера путем многоадресной передачи результата для всех остальных node, но я буду придерживаться более очевидного подхода к серверу здесь).
• Сервер должен объединить гистограммы и сообщить результат. В зависимости от распределения URL-адресов может существовать целый ряд четко видимых пиков, содержащих URL-адреса, посещаемые сверху.
• Каждый из узлов должен сосредоточиться на пиках на гистограмме. Он должен снова пройти через свой файл журнала, использовать дополнительную хеш-функцию (снова с ограниченным целевым пространством), чтобы вычислить новую хэш-гистограмму для тех URL-адресов, которые имеют первое значение хэш-функции в одном из пиков (количество пиков для фокусировки on будет параметром, который будет настроен в алгоритме, в зависимости от распределения URL-адресов) и вычислить вторую гистограмму с новыми значениями хеширования. Результат должен быть передан серверу.
• Сервер должен снова объединить результаты и проанализировать новую гистограмму по сравнению с исходной гистограммой. В зависимости от четко видимых пиков он может сделать выводы о двух хэш-значениях десяти лучших URL-адресов уже. Или это может потребовать, чтобы машины вычисляли больше значений хэша со второй хэш-функцией и, вероятно, после этого прошли третий проход хеш-вычислений с еще одной хэш-функцией. Это должно продолжаться до тех пор, пока из коллективной группы гистограмм не будет сделан вывод о том, каковы значения хеш файла пиковых URL-адресов, а затем узлы могут идентифицировать разные URL-адреса.

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

Этот подход должен хорошо работать, если в URL есть четкое распределение. Я подозреваю, что, практически, вопрос в этом случае имеет смысл.

Ответ 3

Предварительная обработка: каждая компьютерная система обрабатывает полный файл журнала и подготавливает список уникальных URL-адресов с подсчетом против них.

Получение верхних URL-адресов:

• Рассчитать количество URL-адресов в каждой компьютерной системе.
• Процесс сортировки в центральной системе (виртуальный)
  • Отправлять URL-адреса со счетчиками в центральный процессор по одному в порядке DESC (например, сверху)
  • В центральной системе сопоставляются входящие URL-адреса.
  • Повторяйте до тех пор, пока сумма всех отсчетов от входящих URL-адресов не станет меньше десяти десятого URL-адреса в основном списке. Важный шаг, чтобы быть абсолютно уверенным

PS: у вас будет десятка URL-адресов в разных системах, не обязательно в этом порядке. Чтобы получить фактический заказ, вы можете изменить сортировку. Для данного URL в первой десятке получите индивидуальный счет от dist-компьютеров и сформируйте окончательный порядок.

Ответ 4

Предполагая, что приведенные ниже условия верны:

• Вам нужны верхние n URL-адресов из m хостов.
• Вы не можете хранить файлы в оперативной памяти
• Существует мастер node

Я бы взял подход ниже:

Каждый node читает часть файла (то есть MAX urls, где MAX может быть, скажем, 1000 URL-адресов) и сохраняет массив arr [MAX] = {url, hits}.

Когда node считывает MAX URL-адрес с файла, он отправляет список мастеру node и перезапускает чтение до тех пор, пока MAX-URL не будет снова получен.

Когда a node достигает EOF, он отправляет оставшийся список URL-адресов и флаг EOF в master node.

Когда мастер node получает список URL-адресов, он сравнивает его со своим последним списком URL-адресов и генерирует новый, обновленный.

Когда мастер node получает флаг EOF из каждого node и заканчивает чтение своего собственного файла, верхние n URL-адресов последней версии его списка - это те, которые мы ищем.

Или

Другой подход, который освобождает мастера от выполнения всего задания, может быть:

Каждый node считывает свой файл и сохраняет массив, такой же, как указано выше, до EOF.

Когда EOF, node отправит первый URL-адрес списка и количество обращений к мастеру.

Когда мастер собрал первый URL-адрес и количество обращений для каждого node, он генерирует список. Если мастер node имеет меньше, чем n URL-адресов, он попросит узлы отправить второй и т.д. Пока мастер не будет отсортирован по n URL-адресам.

Ответ 5

Ниже описывается идея решения. это не псевдокод.
У вас есть коллекция систем.
1. для каждого A: Коллекции (системы)
 1.1) Запустите daemonA на каждом компьютере, который проверяет файл журнала на предмет изменений.
 1.2) Когда замечено изменение, пробуждение AnalyzerThreadA
 1.3) Если AnalyzerThreadA находит URL-адрес с использованием некоторого регулярного выражения, обновите localHashMapA с помощью count ++.
    (key = URL, value = count).
2) Вставьте topTen записи localHashMapA в ComputerA, где будет запущен демон AnalyzeAll.

Вышеупомянутый шаг будет последним шагом в каждой системе, который будет перетаскивать записи topTen в главную систему, например, например: computerA.

3) AnalyzeAll, запущенный в компьютереA, будет разрешать дубликаты и обновлять счет в masterHashMap URL.

4) Распечатайте topTen из masterHashMap.