S>Сортировка как происходит? Ведь чтобы отсортировать — нужно сравнить друг с другом все строки файла. То есть считывать нужно частями, однако все части должны быть сравнены между собой.
S>Можно полностью всю данные держать на диске — загружать в память только 2 строки — к примеру, с помощью алгоритма B-Tree. Но получится в десятки раз медленнее.
S>Какой алгоритм там применен, что позволяет не считывать все данные с диска в память и одновременно с этим обеспечить высокую скорость сортировки?
Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
Это описание идеи map shuffle reduce. Идеи. Не того, что на самом деле происходит в спарке.
Re[4]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>чувак, это уровень джуна на позицию Data engineer. классический вопрос для джуна на такую позицию, как отсортировать файлик имея ограничение в памяти, ожидается что джун расскажет о map-reduce алгоритмах, от мида ожидается минут за 15 готовый код.
А merge sort не проканает?
Кодом людям нужно помогать!
Re[18]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
Если будет 100гб одинаковых строк, то как сработает?
Re[5]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, Gt_, Вы писали:
Gt_>>чувак, это уровень джуна на позицию Data engineer. классический вопрос для джуна на такую позицию, как отсортировать файлик имея ограничение в памяти, ожидается что джун расскажет о map-reduce алгоритмах, от мида ожидается минут за 15 готовый код.
S>А merge sort не проканает?
Не просто проканает, а это единственное правильное решение. Ключевой вопрос как его сделать быстрым, чтобы 100гб сортировалось за разумное время.
Re[18]: [Ref] Почему не смогли применить готовое решение для
Gt_>Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память.
Это вы точно знаете или просто верите в это? В какой папке файлы хранит? Удаляет потом?
Почему вы думаете что группирует по первой букве? Это ваша гипотеза или знание?
Что если у большинства строк есть некий префикс? Вот такой формат строки, к примеру GOOGLE-slkdaf;ae3wrfsdafadsf.
Что если 26 букв — мало для группировки, т.к. даже при делении на 26 — все-равно файлы получаются большими.
Gt_>Это описание идеи map shuffle reduce. Идеи. Не того, что на самом деле происходит в спарке.
Идей у всех полно разных — важно что происходит на самом деле. Вот в чем вопрос.
Важно как вы реально решите задачу — а не гипотетическое детсадовское шапкозакидательство.
Re[6]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, gandjustas, Вы писали:
S>>А merge sort не проканает? G>Не просто проканает, а это единственное правильное решение. Ключевой вопрос как его сделать быстрым, чтобы 100гб сортировалось за разумное время.
Подобрать такой вариант, чтобы уменьшить disk io. Ну т.е. чтобы оно было оптимальным при заданной конф-ии машины.
Кодом людям нужно помогать!
Re[19]: [Ref] Почему не смогли применить готовое решение для
Gt_>>Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
G>Если будет 100гб одинаковых строк, то как сработает?
ну в нашей задачи еще вторая колонка с цифрами есть, она поможет шафлу раскидать на партиции. а вот если обе колонки одинаковы, да, шафл у spark 2.4 просто все отправит в одну партицию и OM гарантирован. классический подход к борьбе с перекосами данных — подсовывать свою соль. генерируется левая колонка с рандомными значениями и она помогает шафлингу раскидывать более равномерно. вроде в вышедшем пару лет назад spark3 это уже автоматом делается.
Re[20]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>ну в нашей задачи еще вторая колонка с цифрами есть, она поможет шафлу раскидать на партиции.
А как ваш шафл решает как раскидывать, какие данные для этого использовать?
Gt_>а вот если обе колонки одинаковы, да, шафл у spark 2.4 просто все отправит в одну партицию и OM гарантирован.
И даже если буквы разные, но данных, к примеру, 260 Гб. — на одну букву около 10 Гб. при равномерном, но если слова словарные — то может быть и 30 Гб. на какую-либо из букв. И все — тот же привет.
По этому и нужно точно знать как оно работает и можете ли вы этим управлять.
Gt_>классический подход к борьбе с перекосами данных — подсовывать свою соль. генерируется левая колонка с рандомными значениями и она помогает шафлингу раскидывать более равномерно. вроде в вышедшем пару лет назад spark3 это уже автоматом делается.
Будет ошибка в данных — это все равно что разбить на части без учета содержимого, потом отсортировать каждую часть, потом склеить на основе порядка, в котором происходила разбивка.
Вот в этом и проблема — вы не знаете что вы делаете и когда это применимо а когда нет.
Gt_>>ну в нашей задачи еще вторая колонка с цифрами есть, она поможет шафлу раскидать на партиции.
S>А как ваш шафл решает как раскидывать, какие данные для этого использовать?
ты всерьез думаешь, что я начну с тобой разбирать нюансы шафлинга ? с человеком который не осознает как файлы сконкотенировать без затягивания целиком в память !?
ты катастрофически не тянешь на джуна, отказываешься даже вводную по спарку прочесть, поверь, алгоритмы шафлинга тебе не осилить вообще никак.
Re[22]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>ты всерьез думаешь, что я начну с тобой разбирать нюансы шафлинга ?
Если знаешь как используемый тобой инструмент работает — то напиши нам всем. Сомневаюсь что знаешь — а переход на личности не от большого ума.
Gt_>с человеком который не осознает как файлы сконкотенировать без затягивания целиком в память !?
Сконкатенировать не проблема. Только смотри ситуацию. Такой файл входящий:
А3
А1
А4
А2
Это упрощенно. Ты добавляешь рандомный префикс слева так что первая часть файла идет в 1 порцию, вторая во 2 порцию:
1А3
1А1
-
2А4
2А2
Сортируешь порции независимо:
1А1
1А3
-
2А2
2А4
Просто склеиваешь (да, без загрузки в память) и убираешь соль:
А1
А3
А2
А4
Дальше объяснять?
Gt_>ты катастрофически не тянешь на джуна, отказываешься даже вводную по спарку прочесть, поверь, алгоритмы шафлинга тебе не осилить вообще никак.
Давай по сути дела — переход на личности не от большого ума и здесь считается сливом в дискуссии.
Re[7]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, gandjustas, Вы писали:
S>>>А merge sort не проканает? G>>Не просто проканает, а это единственное правильное решение. Ключевой вопрос как его сделать быстрым, чтобы 100гб сортировалось за разумное время.
S>Подобрать такой вариант, чтобы уменьшить disk io. Ну т.е. чтобы оно было оптимальным при заданной конф-ии машины.
В этом и суть задачи:
1) Код будет запускаться не на той машине, на которой он создавался
2) Нужно алгоритмы реализовать так, чтобы они в disk io не упирались
3) Сортируемые данные могут оказаться далеко не такими, на которых вы тестировали
