K-way злиття сортування поділено на кілька хостів

У мене є ~ 8000 файлів, з даними ~ 6TB на диску. Кожен файл містить список пар ключових значень, і я хотів би об'єднати ці значення в єдиний список сортованих пар ключ-значення (наприклад, якщо ключ A зустрічається у двох файлах, консолідований файл містить ключ A і цей ключ містить всі значення з двох файлів).

Я здійснив це злиття k-way для одного ядра на одному хості в Python [ суть - див. цей потік для красивого інтуїтивного огляду процедури]. Тепер я хочу поширити роботу над кількома хостами, які не мають спільної пам'яті, але можуть мати спільний доступ до мережі.

Основний простір, який мені потрібно відсортувати, абсолютно величезний, приблизно 26 ^ 24, але переважна більшість ключів не є в даних (тому немає сенсу надавати кожному працівникові набір ключів, з якими можна займатися ).

Чи є у інших ідеї про те, як можна реалізувати алгоритм розподіленого k-way? Це вражає мене як цілком нетривіальне, але може бути низький висячий плід, який я не бачу. Будь-які вказівки, які можуть запропонувати інші, будуть дуже вдячні.


Примітки

Налаштування обчислень можна параметризувати. Я працюю на двох обчислювальних кластерах, кожен з яких дозволить мені використовувати ~ 10-1000 вузлів одночасно, кожен з 12-24 ядрами і ~ 120GB RAM. Машини з'являються в Інтернеті в певний час, коли вони просять. Мережеве спілкування відбувається через TCP. Диски - це SSD з файловою системою AFS, а зберігання багате.

Крім того, я використовую простий пакунок Python великий читання , щоб читати тільки n лінії з кожного з 8000 файлів в оперативній пам'яті в будь-який момент часу, так що управління RAM для "зовнішнього сортування" вже сприймається ...

Високо пов'язані: об'єднання K-шляху за допомогою stxxl

0
Мені цікаво, щоб кожен працівник зробив k-way злиття на двох файлах - викликати ці виходи 2-го порядку. Потім наступні працівники виконують k-way злиття на цих виходах 2-го порядку для отримання виходів 3-го порядку. Продовжуйте зливатись таким чином, доки не буде досягнуто кінцевого результату замовлення. Це дозволить розподілити роботу над багатьма хостами.
додано Автор duhaime, джерело
Чому люди голосують, щоб закрити це питання? Це мені здається цілком відповідним до політики прийнятних запитань SO - це вирішення алгоритмічного завдання.
додано Автор duhaime, джерело
Чому люди голосують, щоб закрити це питання? Це мені здається цілком відповідним до політики прийнятних запитань SO - це вирішення алгоритмічного завдання.
додано Автор duhaime, джерело
Мені цікаво, щоб кожен працівник зробив k-way злиття на двох файлах - викликати ці виходи 2-го порядку. Потім наступні працівники виконують k-way злиття на цих виходах 2-го порядку для отримання виходів 3-го порядку. Продовжуйте зливатись таким чином, доки не буде досягнуто кінцевого результату замовлення. Це дозволить розподілити роботу над багатьма хостами.
додано Автор duhaime, джерело
Було б справедливо описати інфраструктуру - процесор/ядра, DRAM, тип (паралельно використовуваної файлової системи) + вільні потужності місця для зберігання, з'єднати невикористані транспортні потужності + очікуваний час обробки, на який ви націлені - це справедливо, Невже це?
додано Автор user3666197, джерело
(Кластери - це щось інше, ніж будь-яка інцидентна квазі інфраструктура , яка збільшується "на вимогу" за невідомої вартості -ресурси, що використовуються в реальному часі (реально викрадені з вашого "забезпеченого", але тільки віртуального об'єкта інфраструктури (v) вузлів), невизначені затримки вузла-вузла та інші комерційно приховані хмари/i> traps) Інформація про зберігання SSD є марною у всіх випадках, коли дані 8k + ~ 6TB є десь "іншим" (не завантажені, тільки для отримання зібраного стану) як ціль.
додано Автор user3666197, джерело
(Кластери - це щось інше, ніж будь-яка інцидентна квазі інфраструктура , яка збільшується "на вимогу" за невідомої вартості -ресурси, що використовуються в реальному часі (реально викрадені з вашого "забезпеченого", але тільки віртуального об'єкта інфраструктури (v) вузлів), невизначені затримки вузла-вузла та інші комерційно приховані хмари/i> traps) Інформація про зберігання SSD є марною у всіх випадках, коли дані 8k + ~ 6TB є десь "іншим" (не завантажені, тільки для отримання зібраного стану) як ціль.
додано Автор user3666197, джерело
Це дуже важливий фактор, Дуглас, зробіть який-небудь план управління проектами, перш ніж просити людей спонсорувати вашу роботу в напрямку або проти (досі, але невизначеної) мети. Враховуючи досвід CERN, присвячений старінню (з низьким, починаючи з 1983 року в сучасних контекстах HPC), продуктивність AFS, обмежені можливості внутрішнього протоколу, тим більше, коли ваша робота ніколи не повторює кеш-ефекти (вилучені файли ніколи не використовуються повторно) + мережевий транспорт пропускна спроможність вийде нижче <60 МБ/с на об'єм, AFS зробить лише початковий вибірок, - 1,5 дні (і паралельність не є другом AFS)
додано Автор user3666197, джерело
Це дуже важливий фактор, Дуглас, зробіть який-небудь план управління проектами, перш ніж просити людей спонсорувати вашу роботу в напрямку або проти (досі, але невизначеної) мети. Враховуючи досвід CERN, присвячений старінню (з низьким, починаючи з 1983 року в сучасних контекстах HPC), продуктивність AFS, обмежені можливості внутрішнього протоколу, тим більше, коли ваша робота ніколи не повторює кеш-ефекти (вилучені файли ніколи не використовуються повторно) + мережевий транспорт пропускна спроможність вийде нижче <60 МБ/с на об'єм, AFS зробить лише початковий вибірок, - 1,5 дні (і паралельність не є другом AFS)
додано Автор user3666197, джерело
Thx, щоб сказати, як відома, неподільна частина формулювання Проблеми. Ваша перспектива зрозуміла, але HPC-інфраструктура (все ще недостатньо визначена тут) має певну команду спостереження, яка постулює політику використання (і може припинити обробку роботи (worklow + CPU-/RAM-/IO-/interconnect-квоти) qiven поганий потенціал/продуктивність планування було зроблено і наданих потужностей були спожиті.Ви бачили дуже розумні люди залишаються дуже нещасними, враховуючи їх 2 + років досліджень були вбиті на одному з глобальних Топ- 10 HPC-інфраструктура, прямо через поганий планування.
додано Автор user3666197, джерело
Thx, щоб сказати, як відома, неподільна частина формулювання Проблеми. Ваша перспектива зрозуміла, але HPC-інфраструктура (все ще недостатньо визначена тут) має певну команду спостереження, яка постулює політику використання (і може припинити обробку роботи (worklow + CPU-/RAM-/IO-/interconnect-квоти) qiven поганий потенціал/продуктивність планування було зроблено і наданих потужностей були спожиті.Ви бачили дуже розумні люди залишаються дуже нещасними, враховуючи їх 2 + років досліджень були вбиті на одному з глобальних Топ- 10 HPC-інфраструктура, прямо через поганий планування.
додано Автор user3666197, джерело
ВИЗНАЧЕННЯ ЦІЛІ: "прагне скоротити цей час на максимальну кількість" Це загальне завдання для домену HPC. Стратегія інтелектуальної обробки допомогла від днів до десятків хвилин , якщо стратегія могла бути розроблена спеціально для інфраструктури. Думаєте, ви можете просто забути встановити MapReduce для роботи з університетськими файловими системами Andrew (зверніться до своєї univ. HPC-команди, щоб одержати їхні умови та умови, найкраще дізнавшись про всі ваші реальні обмеження доступних ресурсів). + Python не є інструментом, який вони хотіли б бачити на HPC-кластері
додано Автор user3666197, джерело
Якщо завдання HPC не буде адміністративно схвалено, щоб вийти за межі опублікованих обмежень, ви або оптимізуєте стратегію вирішення , щоб відповідати політиці, або отримані вами завдання HPC загинуло після опублікування на стіні або голодувало на низькій оперативній пам'яті і було вбито (всі команди адміністрації кластерів формують WALL, що може розірвати всі ваші зусилля, якщо виконується проти правила, в наносекунді. Консультація та схвалення команди HPC задовго до того, як Ви вирішите розрахувати стратегію обчислень.
додано Автор user3666197, джерело
Якщо завдання HPC не буде адміністративно схвалено, щоб вийти за межі опублікованих обмежень, ви або оптимізуєте стратегію вирішення , щоб відповідати політиці, або отримані вами завдання HPC загинуло після опублікування на стіні або голодувало на низькій оперативній пам'яті і було вбито (всі команди адміністрації кластерів формують WALL, що може розірвати всі ваші зусилля, якщо виконується проти правила, в наносекунді. Консультація та схвалення команди HPC задовго до того, як Ви вирішите розрахувати стратегію обчислень.
додано Автор user3666197, джерело

6 Відповіді

Розподілене сортування/злиття дуже схоже на сортування/злиття на одному хості. Основна ідея - розділити файли між окремими хостами. Дозвольте кожному хосту відсортувати окремі файли, а потім розпочати операцію злиття, яку я описав у розділити пари значень ключів на рівні списки без доступу до значень ключових значень . Таким чином, кожен хост має чергу пріоритету, що містить наступний елемент з кожного файлу, який він сортував.

Один з хостів зберігає чергу пріоритету, яка містить наступний елемент від кожного з інших хостів. Він вибирає перший з цієї черги, виводить її і опитує хост, з якого він прийшов, для наступного елемента, який він вставляє в чергу пріоритетів і продовжує.

Це чергу пріоритетів черг пріоритетів, розподілених між кількома вузлами. Графічно це виглядає приблизно так:

   Host1            Host2             Host3            Host4
------------------------------------------------------------------
F1 F2 F3 F4      F5 F6 F7 F8      F9 F10 F11 F12   F13 F14 F15 F16
 \  |  | /     \  |  | /      \   |   | /     \   |   |  /
 ----------      ----------       ------------      ------------
    PQ1             PQ2               PQ3               PQ4
     \               \               /                /
      \               \             /                /
       \               \           /                /
        \               \         /                /
          ---------------\        /------------------
                          \      /
                           \    /
                            \  /
                             --
                          Master PQ
                       on primary host

Тепер дуже важко запитувати окремий елемент від окремих хостів. Первинний хост може запитувати, скажімо, 1000 елементів з кожного хоста та утримувати їх у окремих буферах. Всякий раз, коли буфер хоста закінчується, первинний хост запитує інший буфер, повне від хоста. Це зменшить обсяг мережевого трафіку.

Це також зменшує введення/виведення окремих вузлів: ви ніколи не повинні писати об'єднані файли на диск. Ви сортуєте окремі файли і записуєте їх на диск, як описано в моїй попередній відповіді, але тоді ви починаєте злиття на окремих вузлах і відправляєте елементи на основний хост, який робить велике об'єднання.

1
додано
Ви пишете відмінні відповіді @JimMischel. Ви коли-небудь думали писати книгу? Я бачив, як ви пишете щось схоже на популярні "алгоритми". Так чи інакше, велике спасибі за це!
додано Автор duhaime, джерело
Ви пишете книги! mischel.com/pubs/index.htm
додано Автор duhaime, джерело
@duhaime Так, я написав кілька книг. Пройшов час, хоча.
додано Автор Jim Mischel, джерело

Чи потрібно спочатку кожен з 8000 файлів відсортувати за ключем або вони вже відсортовані за ключем? Якщо 8000 спочатку потрібно відсортувати за ключем, то початкова фаза буде пов'язана з процесором. Ця початкова фаза для сортування файлів може бути виконана паралельно (і багатопотокові, наприклад, сортування gnu). Після цього процесу процес стає звичайно пов'язаним з файлами, під час операцій злиття, але якщо файл вводу-виводу з SSD може бути виконаний незалежно, то фази злиття можуть виконуватися паралельно, використовуючи групи SSD. Зрештою остаточне злиття для створення єдиного сортованого файлу буде пов'язано з файловим входом-виходом і не було б переваги для спроби паралельної реалізації цього.

1
додано
це звучить добре, але я просто хочу перевірити: чи пропонуєте ви щось на зразок кількох раундів об'єднання, в якому ми спочатку об'єднаємо два з 8000 файлів, потім об'єднаємо два з цих об'єднаних файлів і так далі залишилося одне остаточне злиття між двома файлами? Навіть тоді, підрозділяючи простір ключів і прагнучи знайти працівників, а потім об'єднати їхні ключові діапазони, не варто?
додано Автор duhaime, джерело
@rcgldr так, це саме те, що я зараз реалізую. Дякуємо, що підтвердили, що це, здається, розумний шлях вперед і для цієї статистики
додано Автор duhaime, джерело
@rcgldr ви впевнені, що обіцяєте ~ 500 [МБ/с] IO для O/P, якщо ЦЕРН опублікував, щоб ніколи не перевищувати ~ 60 [МБ/с] на AFS з додатковими особливостями продуктивності (читайте вузькі місця), керовані конструктивні обмеження файлової системи Andrew? Документ Єльської політики цитує те ж саме, що і "Доступність, обмін і можливості мають вищий пріоритет, ніж продуктивність." Ця обіцянка не відповідає спостережуваним фактам.
додано Автор user3666197, джерело
З усією повагою, @rcgldr, ви впевнені в forcast на початковому етапі , оскільки SSD-файли є тимчасовим вузлом-локальним, тоді як когорта файлів, які обробляються, не є -локально, далеко (читати повільно + додати CERN повідомив досвід волі для запуску будь-якого паралельного fileIO) "через" файлову систему AFS 1983, а не локальний SSD один (так додати також центральну сторону DES-шифрування + DES-розшифрування + зростаючі болі над будь-яким вищим ступенем одночасних запитів (не [PARALLEL], але "просто" - [одночасно], що обслуговується в найкращому випадку або WAIT) блокуючий особливість центрального надання AFS-метаданих)?
додано Автор user3666197, джерело
@ user3666197 - я оновлював свою відповідь. "Початкова фаза" виконується, лише якщо кожен з 8000 файлів повинен бути відсортований за ключем. Якщо всі 8000 файлів вже відсортовані за ключем, то немає потреби в початковій фазі сортування.
додано Автор rcgldr, джерело
@ user3666197 - Я не знав про зовнішні обмеження навколишнього середовища, тільки те, що багато SATA SSD розраховані на 500Мб/с для послідовного читання. На крайньому кінці, деякі твердотільні накопичувачі на основі PCIe на зразок seagate nytro оцінюються до 8 Гб/с для послідовного читання.
додано Автор rcgldr, джерело
@duhaime - Це загальне обмеження k-way файлу злиття до 16 способу для жорстких дисків зі швидкістю передачі близько 100MB/S. Якщо використовується більше, ніж 16 способів злиття, те, що зберігається в кількості фаз злиття, може бути втрачено через накладні витрати процесора. Для SSD з швидкістю передачі даних близько 500 Мб/с (або набагато швидше у випадку SSD з PCIe) оптимальне значення для k в k-way merge може бути менше. У вашому випадку у вас є кілька вузлів і дисків. Якщо диски можуть бути доступні самостійно вузлами, то можна виконати кілька k-way зливань паралельно.
додано Автор rcgldr, джерело

Чи потрібно спочатку кожен з 8000 файлів відсортувати за ключем або вони вже відсортовані за ключем? Якщо 8000 спочатку потрібно відсортувати за ключем, то початкова фаза буде пов'язана з процесором. Ця початкова фаза для сортування файлів може бути виконана паралельно (і багатопотокові, наприклад, сортування gnu). Після цього процесу процес стає звичайно пов'язаним з файлами, під час операцій злиття, але якщо файл вводу-виводу з SSD може бути виконаний незалежно, то фази злиття можуть виконуватися паралельно, використовуючи групи SSD. Зрештою остаточне злиття для створення єдиного сортованого файлу буде пов'язано з файловим входом-виходом і не було б переваги для спроби паралельної реалізації цього.

1
додано
це звучить добре, але я просто хочу перевірити: чи пропонуєте ви щось на зразок кількох раундів об'єднання, в якому ми спочатку об'єднаємо два з 8000 файлів, потім об'єднаємо два з цих об'єднаних файлів і так далі залишилося одне остаточне злиття між двома файлами? Навіть тоді, підрозділяючи простір ключів і прагнучи знайти працівників, а потім об'єднати їхні ключові діапазони, не варто?
додано Автор duhaime, джерело
@rcgldr так, це саме те, що я зараз реалізую. Дякуємо, що підтвердили, що це, здається, розумний шлях вперед і для цієї статистики
додано Автор duhaime, джерело
@rcgldr ви впевнені, що обіцяєте ~ 500 [МБ/с] IO для O/P, якщо ЦЕРН опублікував, щоб ніколи не перевищувати ~ 60 [МБ/с] на AFS з додатковими особливостями продуктивності (читайте вузькі місця), керовані конструктивні обмеження файлової системи Andrew? Документ Єльської політики цитує те ж саме, що і "Доступність, обмін і можливості мають вищий пріоритет, ніж продуктивність." Ця обіцянка не відповідає спостережуваним фактам.
додано Автор user3666197, джерело
З усією повагою, @rcgldr, ви впевнені в forcast на початковому етапі , оскільки SSD-файли є тимчасовим вузлом-локальним, тоді як когорта файлів, які обробляються, не є -локально, далеко (читати повільно + додати CERN повідомив досвід волі для запуску будь-якого паралельного fileIO) "через" файлову систему AFS 1983, а не локальний SSD один (так додати також центральну сторону DES-шифрування + DES-розшифрування + зростаючі болі над будь-яким вищим ступенем одночасних запитів (не [PARALLEL], але "просто" - [одночасно], що обслуговується в найкращому випадку або WAIT) блокуючий особливість центрального надання AFS-метаданих)?
додано Автор user3666197, джерело
@ user3666197 - Я не знав про зовнішні обмеження навколишнього середовища, тільки те, що багато SATA SSD розраховані на 500Мб/с для послідовного читання. На крайньому кінці, деякі твердотільні накопичувачі на основі PCIe на зразок seagate nytro оцінюються до 8 Гб/с для послідовного читання.
додано Автор rcgldr, джерело
@ user3666197 - я оновлював свою відповідь. "Початкова фаза" виконується, лише якщо кожен з 8000 файлів повинен бути відсортований за ключем. Якщо всі 8000 файлів вже відсортовані за ключем, то немає потреби в початковій фазі сортування.
додано Автор rcgldr, джерело
@duhaime - Це загальне обмеження k-way файлу злиття до 16 способу для жорстких дисків зі швидкістю передачі близько 100MB/S. Якщо використовується більше, ніж 16 способів злиття, те, що зберігається в кількості фаз злиття, може бути втрачено через накладні витрати процесора. Для SSD з швидкістю передачі даних близько 500 Мб/с (або набагато швидше у випадку SSD з PCIe) оптимальне значення для k в k-way merge може бути менше. У вашому випадку у вас є кілька вузлів і дисків. Якщо диски можуть бути доступні самостійно вузлами, то можна виконати кілька k-way зливань паралельно.
додано Автор rcgldr, джерело

Це вже вирішена проблема. Більшість каркасів, наприклад, Hadoop, роблять розподілений сорт під капотом. Найкращі з них логіки для виявлення невдалих машин, їх вилучення та перероблення їх роботи. (Коли ви працюєте з великими розподіленими системами в масштабі, важливо компенсувати відмову машини.) Просто знайдіть хорошу основу і використовуйте її, а не повторно винаходити колесо.

Що стосується того, як їх сортувати, я розумію, що стандартний підхід - це злиття. Спочатку ви роздаєте шматки роботи, які виглядають так: "Сортувати цей блок". Тоді ви починаєте роздавати шматки роботи, які виглядають так: "Злийте ці шматки разом". Складний біт виникає, коли ваші шматки для об'єднання не вміщуються на одному комп'ютері. Потім потрібно взяти групу шматочків і з'ясувати, де її розділити, а потім об'єднати шматочки. Я не впевнений, як вони це роблять. Моя найкраща ідея від манжети полягає в тому, щоб взяти щось на зразок підселекції елемента кожної тисячі, відсортувати його, поділити її і повідомити кожній машині, яка містить повну інформацію, куди потрібно вирізати свої набори даних, і хто надсилає дані для об'єднання.

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

IMPORTANT: When dealing with large distributed data sets, it is very important to avoid creating bottlenecks anywhere. Implicitly or explicitly. You start with distributed data. You process it in a distributed way. You wind up with distributed data. Always.

1
додано
у вас є конкретні рамки mapreduce ви б перевірити? У мене немає sudo на будь-якому з кластерів, тому потрібно працювати з програмним забезпеченням, яким надані адміністратори кластера. Я написав їм безпосередньо, щоб запитати, чи знають вони про рішення під ключ в цій групі, і вони сказали, що нічого не знали, але якщо б ви могли перерахувати декілька фреймворків, я краще подивимося на кластери. ...
додано Автор duhaime, джерело
Я написав рекурсивний k-way злиття, як здається консенсусом, і кластер Йеля буде виконаний з ним до того, як день закінчиться. Проте, я хотів би бачити ваші нотатки, user3666197. btilly, це правда, що Hadoop сортує ключі, перш ніж передати їх функції зменшення? Якщо так, чи можу я просто потік кожного з 8000 вхідних файлів на крок на карті і об'єднати значення кожного ключа в крок зменшення лінійно? Це здається занадто легким ...
додано Автор duhaime, джерело
@ user3666197 Перший кластер використовує SLURM, а ресурси задокументовані тут: research.computing.yale .edu/support/hpc/clusters/grace Другий кластер використовує Sun Grid Engine, а ресурси описані тут: crc.nd.edu/index.php/services/policies Проте, я не хочу надто оптимізувати ці кластери - я більше за принципи, які узагальнити інші налаштування апаратного/програмного забезпечення/мережі ...
додано Автор duhaime, джерело
Кластерні умови можуть зменшувати АФС-паралельні потоки вводу-виводу, але потік може стати маскуванням за латентністю 1: 1 (майже) -незабаром ~ 1 [us], закріпленим в масово одночасному пулі розподілених сортувальних вузлів розподіл навантажень-відсутність адаптивності), але з величезним позитивним впливом на загальну продуктивність (повністю анти-шаблон до розміщеної/прийнятої ієрархії переміщення тимчасових попередньо відсортованих етапів до 16: 4: 1 концентрації потоку даних + зменшення продуктивності). Мені подобається затримка-маскування потоку на основі смарт-даних гідравліки погляд на те, як підійти до рішень HPC: o)
додано Автор user3666197, джерело
@btilly Вибачте, якщо посаду було більш заплутаним (цитата доктора Wiedermann була заслугою), це було не про QC per-se (я знаю, QC/QUBO масштабування та інші питання, не тільки з популярності текстів), але все йшлося про основні обмеження від планування та використаних інструментів. Як за шкалою, є собака похована. Війна йде на розумну маскування затримки + збереження основних накладних витрат, обґрунтовані [розподіленими обчислювальними] ресурсами, опосередкованими всіма витратами TimeDOMAIN. На папері я накидав ~ 15 [с] AFS в потоці + mass.-split-processing + w/c ~ 147 [s] результуючих файлів AFS-save. Не 30 + днів як було
додано Автор user3666197, джерело
@btilly Або підхід має сенс. Вгадайте, що доктор Відерман сміється і сміється над наївними спробами вирватися з пасток складності TimeDOMAIN + SpaceDOMAIN, що жодне з "просто" - [CONCURRENT], але навіть не істинний [PARALLEL] обчислювальний пристрій не може розв'язати принципово - все в основному не вдається з експоненціально масштабованої задачі, нерозв'язної за допомогою нашого загального, чистого [SEQUENTIAL] обчислення обчислювальних процесів >>> quantumforquants.org/answer/… + додати повторно сформульований закон Амдала >>> stackoverflow.com/revisions/18374629/3 Гра закінчена.
додано Автор user3666197, джерело
@btilly Враховуючи, що у нас було багато ТБ наборів наприкінці 90-х з даними TELCO, не очікувалося, що через двадцять років що-небудь у {PB, EB} у виробництві та підрахунку код>: o)
додано Автор user3666197, джерело
@btilly Враховуючи, що ви рекламуєте певний " продукт ", як перспективний, якщо не правильний (припускаючи, що обробка розподілених наборів даних буде якось виправдати всі витрати на одноразовий ключ : збірка цінностей та консолідація) - ви впевнені, всі ці додаткові витрати залишатимуться обґрунтованими, враховуючи, що початковий стан базується на файлах (у форматі ~ 8 тис. хв. не гарантований, з низькою перфорацією, розподілений запам'ятовуючий пристрій AFS з розрахунковими та верхньою межею розмірності - чи буде ця екосистема колись виправданою для перетворення тривіальної обробки файлів у Hadoop? Якщо ні, чому ви рекомендуєте це?
додано Автор user3666197, джерело
@duhaime - повернутися до площі № 1, чи не могли б ви опублікувати інформацію про реальну інфраструктуру - як надається з NUMA/ hwloc - припинити командного рядка з правилами планування роботи кластера (лімітами використання), які будуть застосовні до вашого проекту? Побачивши університетські гранти для порівняння продуктивності хмарних Hadoop Map/Red v/s інших технологій обробки необроблених даних, вони були лише на самому кінці здивованими, що Hadoop працював "всередині" тільки віртуальних ресурсів (продуктивність була калікою) без будь-якого шансу виправдати таку психічну помилку). Щоб уникнути повторного неправильного шляху ...
додано Автор user3666197, джерело
@btilly Погодьтеся, також доручили O/P зв'язатися з командою Yale HPC. (хороші розрахунки ймовірності на вашому блозі, сер). Останнє оновлення - ~ 6TB є далеко не "Google" -масштаб, чи не так? Мені дуже сподобався підхід SAWZALL Роб Пайк, майже анти-паттерн, до сильно розподілених, незалежних навантажень у масштабі, прямо через достатню кількість дизайну та результативність під час виконання. Тому я віддаю перевагу налаштуванню виконання процесу, ніж нахилити процес, настільки, щоб стати в змозі повторно використовувати якийсь продукт загального призначення (маркетинг, що перевищує). Дякуємо за висловлені вами думки.
додано Автор user3666197, джерело
Ось чому вони це роблять. Перш ніж зменшити, потрібно якось збирати ключі разом. Два природні способи, які повинні пройти через сорт або хеш. Хешінг має перевагу O (n) замість O (n log (n)) . Але це має серйозний недолік, що ви можете легко перевантажити вузол, який випадково отримує кілька "гарячих клавіш", призначених для нього. Це чистий бонус, що сортування представляє значення в упорядкованому порядку, і робить більш ймовірним, що подальша обробка може отримати вигоду від місцевості посилання.
додано Автор btilly, джерело
@duhaime Hadoop приходить на розум. І на blog.ditullio.fr/2015/12/24/& hellip; можна навіть вибрати користувальницький компаратор сортування.
додано Автор btilly, джерело
@duhaime Це саме те, як ви це робите. :-)
додано Автор btilly, джерело
@ user3666197 Квантові обчислювальні системи не змінюють ситуацію так, як кажуть популярні спекуляції. Див. scottaaronson.com/blog/?p=3848 . відповідь. Що стосується будь-якого підходу, напишіть речі на легкій мові, як Python. Тепер ретельно оптимізований код на одній машині зазвичай може отримати 1-2 порядки величини продуктивності над цим, але зі стелею. Розподілений втрачає порядок продуктивності над наївним рішенням, але може масштабуватися назавжди. Обидва займають більше часу програміста, ніж ви думаєте. Вибирати мудро ...
додано Автор btilly, джерело
@ user3666197 Великі дуже, дуже великі. Я не знаю, наскільки вони великі. Індивідуальні команди, однак, часто закінчують справу з набагато меншими наборами речей, які мають значення для їхнього проекту. Є багато, багато наборів даних, які плавають навколо всіх розмірів. Також компанії мають різні філософії. Google "все поширюється, велика архітектура масштабується нескінченно". Амазонка, навпаки, робить дивовижну кількість: "Давайте спробуємо звести це до набору даних, який ми можемо обробити за кілька годин на одній машині, набагато дешевше, ніж дозволяє розподілений".
додано Автор btilly, джерело
@ user3666197 У Google є безліч наборів даних в діапазоні розмірів з декількох терабайт. Тим не менш, він досить великий, щоб розподілені методи мали сенс. SAWZALL дійсно дуже хороший інструмент. Однак я виявив, що він має ті ж "винятки для мене, але не для тебе" мислення, яке також дратує мене в Go. Деякі речі, які йдуть неправильно, я дійсно хочу почути, гарантовано. І ні, я не хочу, щоб поділ на 0 був панікою ...
додано Автор btilly, джерело
@ user3666197 І продовжуючи, моя рекомендація щодо використання MapReduce базується на найкращих практиках, коли я працював у Google. За загальним визнанням, їхня інфраструктура набагато краще, ніж ви очікуєте в університеті. Якщо все було неправильно, ви можете калічити будь-яку технологію. Але зберігати дані в розподіленому сховищі даних, обробляти їх розподіленим способом, потім зберігати його знову розподілений добре працює. Внутрішні орієнтири ставлять їх загальне призначення MapReduce в межах кількох відсотків кращих тестів в будь-якому місці для написаного користувачем розподіленого сортування.
додано Автор btilly, джерело
@ user3666197 Порівняйте вартість та надійність використання існуючого перевіреного програмного рішення з вартістю та надійністю того, що хтось пише домашній користувальницький написаний програмний продукт для того ж самого. Вартість експорту даних з AFS однакова, чи йдеться про іншу файлову систему або спеціальне завдання, і тому вартість у вашому рішенні не має значення. MapReduce і Hadoop добре відомі достатньо ключові слова, які я сподіваюся, що люди, які працюють з кластером, знають, що рекомендувати для тих, хто вважає, що це відповіді на їх проблеми ...
додано Автор btilly, джерело

Якщо ваш метод порівняння не дуже складний, вузьким місцем, швидше за все, є файл-IO. Це буде погіршуватися, коли ви робите це через мережу, а не на локальному жорсткому диску. (Але ви можете бути впевнені лише після профілювання)

Я впевнений, що файл-IO є вашим вузьким місцем (але ви можете бути впевнені тільки після профілювання).

Я рекомендую:

  1. Завантажте дані у великі фрагменти в оперативну пам'ять (настільки великі, як ви можете) використовуйте швидкий вибір для кожного шматка, щоб відсортувати його в ОЗП і записати його як один файл на шматок на диск.
  2. Використовуйте злиття k-way для об'єднання цих великих відсортованих файлів.
0
додано
Припускаючи, що у вас достатньо пам'яті, щоб утримувати навіть невеликий буфер для кожного з сортованих підфайлів, кожен елемент двічі читається з диска і записується двічі на диск. Кількість операцій вводу-виводу лінійна з n. en.wikipedia.org/wiki/External_sorting#External_merge_sort
додано Автор Jim Mischel, джерело
В одному-хост сортувати/об'єднувати, I/O великий фактор, але не обмежуючий фактор. Час розподіляється досить рівномірно між I/O, виконуючи початкові сортування файлів і остаточне злиття. Наявність декількох вузлів дає лінійне збільшення на початкових сортуваннях файлів і принаймні на половині вводу-виводу. Остаточне злиття та виведення, виконане на одному хості, все ще потребує значного часу, але перша половина проблеми швидше йде .
додано Автор Jim Mischel, джерело
I/O - операція O (n). Сортування - це операція O (n log n). Тому час сортування збільшується швидше, ніж час, необхідний для запису. Настає момент, особливо коли порівняння є дорогим, що час сортування більше часу вводу-виводу.
додано Автор Jim Mischel, джерело
З усією повагою, сер, це не відповідає основному питанню - як розробити такий процес у середовищі розподілених обчислень розумним та ефективним. Якщо ви продовжуєте відповідати вашим апріорним переконанням, головним вузлом є диск-I/O, то організована сортування за частинами не є способом швидше у TimeDOMAIN, враховуючи доступний діапазон ~ 10.000 x 120 ГБ RAM SpaceDOMAIN обладнані вузлами з 12-24 CPU-ядрами.
додано Автор user3666197, джерело
@ user3666197: Моє головне: перш ніж розповсюдити проблему, спочатку проаналізуйте, чи дійсно це вирішує вузьке місце вашої проблеми. Якщо IO є проблемою, ви не отримаєте ніякої вигоди, поширюючи алгоритм, якщо IO залишається поганим або стає ще гіршим (за допомогою спільної файлової системи, доступної через мережу замість файлів на локальному диску). Таким чином, перший крок профілю, що ваш вузьке місце.
додано Автор MrSmith42, джерело
@Jim Mischel: "I/O - великий фактор, але не обмежуючий фактор". Що ще може бути обмежуючим фактором? Об'єднати сортування нічого не робить, але читати , порівнювати і писати , щоб порівняння не займало часу порівняно з читанням і записом з/до файлової системи. Сортування великих шматочків в оперативній пам'яті дозволяє уникнути навантажень читання і записів у файлову систему. Після зменшення файлу I/O таким чином ви все ще можете розглянути розподіл між хостами, якщо швидкість все ще занадто повільна.
додано Автор MrSmith42, джерело
@Jim Mischel: MergeSort не читає/записує дані лише один раз, коли ви не можете зберігати їх у оперативній пам'яті. Таким чином, вам доведеться читати/wirte дані з диска O (log n) разів. Це робить число I/O також O (n log n) і, якщо порівняння не дуже складне, константа, швидше за все, гірше для i/o, ніж для функції порівняння.
додано Автор MrSmith42, джерело

Якщо ваш метод порівняння не дуже складний, вузьким місцем, швидше за все, є файл-IO. Це буде погіршуватися, коли ви робите це через мережу, а не на локальному жорсткому диску. (Але ви можете бути впевнені лише після профілювання)

Я впевнений, що файл-IO є вашим вузьким місцем (але ви можете бути впевнені тільки після профілювання).

Я рекомендую:

  1. Завантажте дані у великі фрагменти в оперативну пам'ять (настільки великі, як ви можете) використовуйте швидкий вибір для кожного шматка, щоб відсортувати його в ОЗП і записати його як один файл на шматок на диск.
  2. Використовуйте злиття k-way для об'єднання цих великих відсортованих файлів.
0
додано
Припускаючи, що у вас достатньо пам'яті, щоб утримувати навіть невеликий буфер для кожного з сортованих підфайлів, кожен елемент двічі читається з диска і записується двічі на диск. Кількість операцій вводу-виводу лінійна з n. en.wikipedia.org/wiki/External_sorting#External_merge_sort
додано Автор Jim Mischel, джерело
В одному-хост сортувати/об'єднувати, I/O великий фактор, але не обмежуючий фактор. Час розподіляється досить рівномірно між I/O, виконуючи початкові сортування файлів і остаточне злиття. Наявність декількох вузлів дає лінійне збільшення на початкових сортуваннях файлів і принаймні на половині вводу-виводу. Остаточне злиття та виведення, виконане на одному хості, все ще потребує значного часу, але перша половина проблеми швидше йде .
додано Автор Jim Mischel, джерело
I/O - операція O (n). Сортування - це операція O (n log n). Тому час сортування збільшується швидше, ніж час, необхідний для запису. Настає момент, особливо коли порівняння є дорогим, що час сортування більше часу вводу-виводу.
додано Автор Jim Mischel, джерело
З усією повагою, сер, це не відповідає основному питанню - як розробити такий процес у середовищі розподілених обчислень розумним та ефективним. Якщо ви продовжуєте відповідати вашим апріорним переконанням, головним вузлом є диск-I/O, то організована сортування за частинами не є способом швидше у TimeDOMAIN, враховуючи доступний діапазон ~ 10.000 x 120 ГБ RAM SpaceDOMAIN обладнані вузлами з 12-24 CPU-ядрами.
додано Автор user3666197, джерело
@ user3666197: Моє головне: перш ніж розповсюдити проблему, спочатку проаналізуйте, чи дійсно це вирішує вузьке місце вашої проблеми. Якщо IO є проблемою, ви не отримаєте ніякої вигоди, поширюючи алгоритм, якщо IO залишається поганим або стає ще гіршим (за допомогою спільної файлової системи, доступної через мережу замість файлів на локальному диску). Таким чином, перший крок профілю, що ваш вузьке місце.
додано Автор MrSmith42, джерело
@Jim Mischel: "I/O - великий фактор, але не обмежуючий фактор". Що ще може бути обмежуючим фактором? Об'єднати сортування нічого не робить, але читати , порівнювати і писати , щоб порівняння не займало часу порівняно з читанням і записом з/до файлової системи. Сортування великих шматочків в оперативній пам'яті дозволяє уникнути навантажень читання і записів у файлову систему. Після зменшення файлу I/O таким чином ви все ще можете розглянути розподіл між хостами, якщо швидкість все ще занадто повільна.
додано Автор MrSmith42, джерело
@Jim Mischel: MergeSort не читає/записує дані лише один раз, коли ви не можете зберігати їх у оперативній пам'яті. Таким чином, вам доведеться читати/wirte дані з диска O (log n) разів. Це робить число I/O також O (n log n) і, якщо порівняння не дуже складне, константа, швидше за все, гірше для i/o, ніж для функції порівняння.
додано Автор MrSmith42, джерело