задача с интервью

[juan_gandhi]

Есть огромный диск (ну типа gfs); там миллионы фолдеров, короче, большое дерево. Надо построить график, по оси X дата, по оси Y сколько файлов модифицировано в тот день.

Есть несколько машин. Организуйте производство. В смысле, чтобы они трудились эффективно и произвели нужный результат за осмысленное время.

Comments

[smalgin.livejournal.com]

А где подвох? Распараллелить findfirst-findnext тупой дихотомией вроде бы тривиально, ну а дальше work stealing queue подберет остатки... где грабли-то?

[ivan-gandhi.livejournal.com]

:) Да, можно и так. Мне в решении понравилось, что для wfs нужна queue, так вот эту queue и раздёргивать на threads.

[smalgin.livejournal.com]

Про wfs я не знаю, а gfs has single master machine with in-memory metadata storage, никаких грабель не предвидится, разделяй и властвуй :)

[ivan-gandhi.livejournal.com]

А, я не в курсе был.

wfs - это width first search

Я, кстати, не верю, что будет всё равно, читать ли директории с одной машины или с кучи машин.

[kashnikov.livejournal.com]

Кстати, wfs, довольно редко употребляется. Обычно всё-таки Breadth-First Search. Возможно, поэтому собеседник и был смущен названием ;-)

[ivan-gandhi.livejournal.com]

Да, BFS, конечно, правильнее.

[softmaster.livejournal.com]

скорость чтения с диска быстрее, чем машины обрабатывают? если нет, лучше одной машиной последовательно читать, чем параллелить и вызывать лишний random seek.

я бы делал так:
главный процесс раздаёт фолдеры всем машинам из очереди (начальный стейт очереди "/" (root)) ,
на каждой машине клиентский процесс берет фолдер из раздатчика, траверсит, файлы добавляет в локальный мап date/number, фолдеры отдаёт распределяющему процессу.
как очередь кончится, все процессы отдают мапы главному для слияния по датам.
главный процесс может ранниться на одной машине с клиентским, остальные машины - только клиентский.

[ivan-gandhi.livejournal.com]

Да, но только один процесс может закончить через секунду, а другой - через два дня.

[softmaster.livejournal.com]

если бы был api для рандом доступа к списку файлов в фолдере, можно разделять на одинаковые куски(по тысяче файлов, например) и раздавать куски фолдера разным машинам.
обычный find first/find next только последовательный

[hill-report.livejournal.com]

баян
если студент прослушал курс по параллельным системам, он сразу же ответит.

[ivan-gandhi.livejournal.com]

Ну это, видимо, кое-где.

[zamotivator.livejournal.com]

Можно примеры хороших курсов по данной теме?

[hill-report.livejournal.com]

http://cs.unc.edu/~prins/Classes/633/

[zamotivator.livejournal.com]

Большое спасибо!

[lev.livejournal.com]

а зачем несколько машин? узкое место диск

[ivan-gandhi.livejournal.com]

Эх... ну хорошо, не диск. Файловая система.

[lev.livejournal.com]

хмм
network drive с несколькими клиентами?
сканируем фолдер, если попался сабфолдер - выкладываем в общую очередь. файлы процессим. по исчерпанию - лезем в общую очередь за очередным фолдером.

[ivan-gandhi.livejournal.com]

Ну! Правда, красиво! BFS с пулом обработчиков.

[lev.livejournal.com]

softmaster, собственно, это и предложил

[softmaster.livejournal.com]

похоже, у меня получилось слишком многословно %)

[itman.livejournal.com]

Кстати да. А разве у GFS директории уже не поделены между машинами?

Re: у GFS директории уже не поделены между машинами?

[dememax]

Папки, насколько я понимаю, у них - метаданные (http://labs.google.com/papers/gfs-sosp2003.pdf).

По следам GFS: Evolution on Fast-forward:

А метаданные живут под одним мастером на одной ячейке.
А мастер, как известно, загибается.
Зато есть мультиячейки.

[dmzlj.livejournal.com]

map-reduce обычный? Только вопрос как диск устроен. Если это физически один диск, то одна история, если много дисков --- то несколько другая.

Re: map-reduce обычный?

[dememax]

Нет, нет. Не стоит использовать патентованные технологии!
http://www.h-online.com/open/news/item/Google-patents-Map-Reduce-908602.html

Re: map-reduce обычный?

[itman.livejournal.com]

О, писец.... Как можно запатентовать то, что ты не изобрел :-((( Оказывается можно!
PS: хочется верить, что это действительно defensive.

Re: Как можно запатентовать то, что ты не изобрел

[dememax]

Леонид, а что, собственно, вас удивляет?
История кишит такими примерами.
Кто успел, тот и съел!

Ну, дык, они заявляют, что они - белые и пушистые, что никому зла не желают, починяют примус...
А там, конечно, посмотрим, может это - своеобразная форма американского юмора.

Re: Как можно запатентовать то, что ты не изобрел

[itman.livejournal.com]

Да, Тесла был гениальным изобретателем, опередившим время, а Эдисон - хорошим предпринимателем. Именно поэтому он настолько засношал всем мозги с идей постоянного тока, что последний потребитель постоянного тока был отключен уже в нашем столетии! (21-ом если что) Ужас, какой ужас.

[zamotivator.livejournal.com]

*решения из комментов намеренно не читал, сам хочу понять*
Это задача на организацию эффективного storage, или задача "как эффективно посчитать количество меченных вершин в дереве"?
Кстати, а симлинки есть?

Re: Кстати, а симлинки есть?

[dememax]

The Google File System:

4.1 Namespace Management and Locking

...Unlike many traditional file systems, GFS does not have a per-directory data structure that lists all the files in that directory. Nor does it support aliases for the same file or directory (i.e, hard or symbolic links in Unix terms). GFS logically represents its namespace as a lookup table mapping full pathnames to metadata...

[109.livejournal.com]

ясен пень, очередь. но из предложенных гениальных решений непонятно, распределённая ли (тогда весь фокус в том, как её организовать), или все воркеры лезут на одну выделенную машину за следующим джобом (тогда не скалируется).