S>Сортировка как происходит? Ведь чтобы отсортировать — нужно сравнить друг с другом все строки файла. То есть считывать нужно частями, однако все части должны быть сравнены между собой.
S>Можно полностью всю данные держать на диске — загружать в память только 2 строки — к примеру, с помощью алгоритма B-Tree. Но получится в десятки раз медленнее.
S>Какой алгоритм там применен, что позволяет не считывать все данные с диска в память и одновременно с этим обеспечить высокую скорость сортировки?
Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
Это описание идеи map shuffle reduce. Идеи. Не того, что на самом деле происходит в спарке.
Re[3]: [Ref] Почему не смогли применить готовое решение для
S>Как найти подходящую DB — не знаю. Это если ты случайно с этим столкнулся — то сможешь быстро решить, а так это нужен уровень архитектора матрицы не иначе как.
чувак, это уровень джуна на позицию Data engineer. классический вопрос для джуна на такую позицию, как отсортировать файлик имея ограничение в памяти, ожидается что джун расскажет о map-reduce алгоритмах, от мида ожидается минут за 15 готовый код.
Re: [Ref] Почему не смогли применить готовое решение для простой задачи?
S>Я вам задал конкретный вопрос: сколько памяти потребляет ваше решение? Загружает ли оно все данные целиком в память или нет?
а ты можешь объяснить на кой ты отнимаешь у меня время, вместо того что бы пойти и прочесть вводную в спарк на один из миллионов ресурсов ? лично я тебе объяснил на пальцах даже откуда магия, не жди от меня пережевывание базовой инфы о спарке, которая доступна и без меня.
S>Ты просто взял загрузил все данные в память, взял 10 Гб., памяти в системе у тебя 32. И с радостью отрапортовал что вы тут все дурью маетесь — вы все немудрые, потому что нужно использовать готовые решения, а не велосипедить. Звучит заманчиво. Однако же задача не решена — суть задачи в том, чтобы отработать не загружая данные в память целиком.
хорошо, я потратил еще 10 минут и собрал отдельный проект, собрал uber jar и запустил как полагается через spark-submit:
spark-submit2.cmd --class org.example.Main --master local[8] --driver-memory 2g srt-uber-1.0-SNAPSHOT.jar
25G файл отсортировал спарк процесс который в пике отожрал 2.3G
вот весь код проекта
package org.example;
import org.apache.spark.sql.SparkSession;
public class Main {
public static void main(String[] args) {
SparkSession spark = SparkSession
.builder()
.appName("delta")
.master("local[*]")
.getOrCreate();
spark.read()
.option("delimiter", ".")
.csv("D:/TEST")
.orderBy("_c1", "_c0")
.repartition(1)
.write()
.option("delimiter", ".")
.csv("D:/TEST_COMBINED");
}
}
Re[15]: [Ref] Почему не смогли применить готовое решение для
Gt_>>25G файл отсортировал спарк процесс который в пике отожрал 2.3G
S>Что значит это: repartition(1) ?
S>Понимаете ли как оно работает внутри? Как оно сортирует данные без загрузки в память всего массива данных?
да, понимаю. на позицию джуна у меня твердые знания. под низом там обычные java streams. ты если стримами вычитываешь файл и тут же записывешь, тоже ожидаешь, что весь терабайт в память залезет и лишь потом пойдет запись ? чувак, что у тебя за опыт в ИТ ?
Re[19]: [Ref] Почему не смогли применить готовое решение для
Gt_>>Ответ все тот же, цитирую: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
G>Если будет 100гб одинаковых строк, то как сработает?
ну в нашей задачи еще вторая колонка с цифрами есть, она поможет шафлу раскидать на партиции. а вот если обе колонки одинаковы, да, шафл у spark 2.4 просто все отправит в одну партицию и OM гарантирован. классический подход к борьбе с перекосами данных — подсовывать свою соль. генерируется левая колонка с рандомными значениями и она помогает шафлингу раскидывать более равномерно. вроде в вышедшем пару лет назад spark3 это уже автоматом делается.
Re: [Ref] Почему не смогли применить готовое решение для простой задачи?
в том топике решение с СУБД так и не приведено же.
По-хорошему, вы бы реализовали свой подход и сравнили с предложенными решениями и тыкали страждущих цифрами.
Re[9]: [Ref] Почему не смогли применить готовое решение для
S>Здесь до тебя взрослые дядьки решали данную задачу вручную, готовых решений не нашлось, по крайней мере для данной .Net платформы.
их попросили решать на чистом .net, разрешения юзать обертки вокруг jvm там не было.
но и тут видно что они не столь уж взрослые на этом поприще, я увидел 2 решения и оба однопоточные. но я полагаю и интервьювер хотел увидеть навыки работы с .net, а не мощный параллельный код работающий с unsafe регионами.
S>За счет чего? Понимаешь ли, что паттерн — для распределения данных НА МНОЖЕСТВО машин?
кто тебе такую глупость сказал ? map-reduce это про разбивку задачи на мелкие подзадачи в первую очередь. то что эти подзадачи еще и можно распараллелить хоть в рамках машины, хоть кластера — лишь следствие идеи.
получивший такую задачу джун должен рассказать, что тут map-reduce нужен именно, что бы влезть в рамки по памяти, параллельность просто бонус. очень упрощенно: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
Здравствуйте, syrompe, Вы писали:
S>в том топике решение с СУБД так и не приведено же. S>По-хорошему, вы бы реализовали свой подход и сравнили с предложенными решениями и тыкали страждущих цифрами.
Я попробовал с встраиваемой LevelDB — не возможно сделать быстро, будет на порядки медленнее при кастомной сортировке.
Как найти подходящую DB — не знаю. Это если ты случайно с этим столкнулся — то сможешь быстро решить, а так это нужен уровень архитектора матрицы не иначе как.
Вроде бы задача простая и должна подойти любая СУБД. Но на практике нет — для больших данных они не подходят — нет режима импорта больших данных, только поддержка.
Дайте для начала определение простоты.
Вон Рич Хикки два часа об этом рассуждал, но я так и не понял.
Просто ли ездить на велике? кому как.
Просто. Легко. Сложно.
И самый заменитый вопрос Хикки задайте себе:
И мне нравится задавать этот вопрос: что верно
для каждой ошибки, найденной в продакшене?
Здравствуйте, Gt_, Вы писали:
Gt_>чувак, это уровень джуна на позицию Data engineer. классический вопрос для джуна на такую позицию, как отсортировать файлик имея ограничение в памяти, ожидается что джун расскажет о map-reduce алгоритмах, от мида ожидается минут за 15 готовый код.
А почему же никто не смог продолжить готового решения? Может вы являетесь не просто балаболом, как все тут могли подумать, а на самом деле знаете о чем говорите? Давайте ваше решение — оценим.
Re[5]: [Ref] Почему не смогли применить готовое решение для
Gt_>>чувак, это уровень джуна на позицию Data engineer. классический вопрос для джуна на такую позицию, как отсортировать файлик имея ограничение в памяти, ожидается что джун расскажет о map-reduce алгоритмах, от мида ожидается минут за 15 готовый код.
S>А почему же никто не смог продолжить готового решения? Может вы являетесь не просто балаболом, как все тут могли подумать, а на самом деле знаете о чем говорите? Давайте ваше решение — оценим.
Памяти сколько было задействовано? Я там задал вопрос вам происходила ли сортировка в памяти или нет?
Видимо знаете в чем дело? Вас просто научили использовать некий инструмент, суть которого вы до конца не понимаете. Не знаете как там внутри все работает. Но вы думаете что этот инструмент наиболее подходит для данной задачи — возможно так и совпало случайно — это мы еще не выяснили (т.к. вы сами не знаете происходила ли сортировка 100% в памяти или нет) — и вы уже начали хорохориться и бросаться какашками — мол задача легко решается.
Сначала разберитесь происходит ли сортировка в памяти или нет — если чисто в памяти — то не оно.
Gt_>>к чему эта клоунада ?
S>Памяти сколько было задействовано? Я там задал вопрос вам происходила ли сортировка в памяти или нет?
S>Видимо знаете в чем дело? Вас просто научили использовать некий инструмент, суть которого вы до конца не понимаете. Не знаете как там внутри все работает. Но вы думаете что этот инструмент наиболее подходит для данной задачи — возможно так и совпало случайно — это мы еще не выяснили (т.к. вы сами не знаете происходила ли сортировка 100% в памяти или нет) — и вы уже начали хорохориться и бросаться какашками — мол задача легко решается.
S>Сначала разберитесь происходит ли сортировка в памяти или нет — если чисто в памяти — то не оно.
чувак, ты не тянешь на позицию джуна но пытаешься оценивать. это глупо. я тебе уже разжевал, что от джуна требуется знания самых базовых патернов, начиная с map-reduce. map-reduce глобальный ответ о том как работает внутри этот инструмент.
я не знаю как там карта легла на моей машине, может на столько крошеный файл ему этих 5-6 гигов, но дело не в том как у меня карта легла, а том что сам патерн позволят пережевывать много большие данные, чем памяти на машине.
Re[8]: [Ref] Почему не смогли применить готовое решение для
Здесь до тебя взрослые дядьки решали данную задачу вручную, готовых решений не нашлось, по крайней мере для данной .Net платформы.
Gt_>я тебе уже разжевал, что от джуна требуется знания самых базовых патернов, начиная с map-reduce. map-reduce глобальный ответ о том как работает внутри этот инструмент.
MapReduce — это модель распределенных вычислений — когда нужно разбить и вычислить на n серверах.
Это ты где-то услышал на презентации, запомнил что это круто — и теперь пытаешься хорохориться на форуме взрослых?
Gt_>я не знаю как там карта легла на моей машине, может на столько крошеный файл ему этих 5-6 гигов, но дело не в том как у меня карта легла, а том что сам патерн позволят пережевывать много большие данные, чем памяти на машине.
За счет чего? Понимаешь ли, что паттерн — для распределения данных НА МНОЖЕСТВО машин?
У тебя сколько памяти на машине?
Re[10]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>получивший такую задачу джун должен рассказать, что тут map-reduce нужен именно, что бы влезть в рамки по памяти, параллельность просто бонус. очень упрощенно: маппер читает строку и пишет ту же строку в отдельные файлики, в файлик1 строки начинающииеся на А, файлик2 строки начинающиеся на Б — теперь у тебя не один 10г файлик, а десятки, влезающие в память. осталось лишь отсортировать их содержимое и в нужном порядке слепить в конечный результат. это очень упрощенно, но в этом суть и магия инструмента.
Здравствуйте, Gt_, Вы писали:
Gt_>кто тебе такую глупость сказал ? map-reduce это про разбивку задачи на мелкие подзадачи в первую очередь. то что эти подзадачи еще и можно распараллелить хоть в рамках машины, хоть кластера — лишь следствие идеи.
Так что — долго мы будем ждать от вас "решения джуна"? Или уже понял что сел в лужу?
Ну вот распараллелил ты на одной машине — а кто сказал, что объединять работу оно будет не загрузив в память все порции?
В общем — то что вы привели — работает целиком в памяти — а это как раз не годится по условию задачи. Сколько бы не плевался что это типа легко и можно сделать, применив готовое решение — результата мы не видим.
Re[11]: [Ref] Почему не смогли применить готовое решение для
Gt_>>кто тебе такую глупость сказал ? map-reduce это про разбивку задачи на мелкие подзадачи в первую очередь. то что эти подзадачи еще и можно распараллелить хоть в рамках машины, хоть кластера — лишь следствие идеи.
S>Так что — долго мы будем ждать от вас "решения джуна"? Или уже понял что сел в лужу?
S>Ну вот распараллелил ты на одной машине — а кто сказал, что объединять работу оно будет не загрузив в память все порции?
S>В общем — то что вы привели — работает целиком в памяти — а это как раз не годится по условию задачи. Сколько бы не плевался что это типа легко и можно сделать, применив готовое решение — результата мы не видим.
ты в серьез ждал, что я буду пересказывать вводные статьи о спарке ? эти статьи рассчитаны на джуна после школы. какой мне смысл с тобой, убогим возится, если ты ищешь буквы А и Б в коде ?
Re[12]: [Ref] Почему не смогли применить готовое решение для
Здравствуйте, Gt_, Вы писали:
Gt_>ты в серьез ждал, что я буду пересказывать вводные статьи о спарке ? эти статьи рассчитаны на джуна после школы. какой мне смысл с тобой, убогим возится, если ты ищешь буквы А и Б в коде ?
Я вам задал конкретный вопрос: сколько памяти потребляет ваше решение? Загружает ли оно все данные целиком в память или нет?
Ты просто взял загрузил все данные в память, взял 10 Гб., памяти в системе у тебя 32. И с радостью отрапортовал что вы тут все дурью маетесь — вы все немудрые, потому что нужно использовать готовые решения, а не велосипедить. Звучит заманчиво. Однако же задача не решена — суть задачи в том, чтобы отработать не загружая данные в память целиком.
Здравствуйте, Gt_, Вы писали:
Gt_>да, понимаю. на позицию джуна у меня твердые знания. под низом там обычные java streams. ты если стримами вычитываешь файл и тут же записывешь, тоже ожидаешь, что весь терабайт в память залезет и лишь потом пойдет запись ? чувак, что у тебя за опыт в ИТ ?
Сортировка как происходит? Ведь чтобы отсортировать — нужно сравнить друг с другом все строки файла. То есть считывать нужно частями, однако все части должны быть сравнены между собой.
Можно полностью всю данные держать на диске — загружать в память только 2 строки — к примеру, с помощью алгоритма B-Tree. Но получится в десятки раз медленнее.
Какой алгоритм там применен, что позволяет не считывать все данные с диска в память и одновременно с этим обеспечить высокую скорость сортировки?
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[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) Сортируемые данные могут оказаться далеко не такими, на которых вы тестировали
