Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 63
Такими темпами, гугл за день лекарство от рака найдёт. Брутфорсом.
Или откроет новый сервис по факторизации чисел :) Вводишь в строку поиска: «1046823347», а он тебе:
P.S. А пока, все фотографии фейсбука можно превратить в однородную цепочку байт всего за шесть часов :)
Или откроет новый сервис по факторизации чисел :) Вводишь в строку поиска: «1046823347», а он тебе:
1046823347 = 7687 * 3167 * 43
P.S. А пока, все фотографии фейсбука можно превратить в однородную цепочку байт всего за шесть часов :)
Ну, на сортировку байтов так много времени не нужно, можно просто взять массив long[256] и просто посчитать, сколько каждого байта нам повстречалось. А потом записать — если нужно. Можно распараллелить — будет быстро. :-)
P.S. Сорри за невольный педантизм.
P.S. Сорри за невольный педантизм.
Лекарство от рака уже ищут брутфорсом :)
worldcommunitygrid.org
worldcommunitygrid.org
К сожалению в гугловском блоге подробностей нет. Но написано, что через некоторое время будет публикация с описанием эксперимента. Я думаю там и расскажут про алгоритм.
Вероятно, нет, ибо сортировка слиянием одна из самых медленных.
www.citforum.ru/programming/theory/sorting/sorting1.shtml#3
По нашим институтским данным самая быстрая была многопутевая, а еще быстрее многофазная.
www.citforum.ru/programming/theory/sorting/sorting1.shtml#3
По нашим институтским данным самая быстрая была многопутевая, а еще быстрее многофазная.
Заметил. Как заметили мы в процессе реализации, на практике эти сортировки отличаются настолько, что мы предпочитали их все же разделять.
Выбор алгоритма сортировки определяется решаемой задачей — да. Ссылка была для примера, чтобы не искать судорожно информацию про внешние сортировки.
Для всех внешних сортровок узким местом как раз является шина передачи данных. Именно поэтому я думаю, что использовался какой-то свой алгоритм, активно использующий числа Фибоначчи.
Выбор алгоритма сортировки определяется решаемой задачей — да. Ссылка была для примера, чтобы не искать судорожно информацию про внешние сортировки.
Для всех внешних сортровок узким местом как раз является шина передачи данных. Именно поэтому я думаю, что использовался какой-то свой алгоритм, активно использующий числа Фибоначчи.
Кстати, попутно узнал, что Billion может означать и 109, и 1012… Ужас.
ага, я тоже удивился когда узнал, что американцы в основном говорят биллион вместо миллиарда)
Еще здесь очень интересно описано.
Круто, с точки зрения инфраструктуры.
Но Гугл сортировал слабо связанные или несвязанные «числа». Напротив, например, колайдер выдаёт не просто «числа», а связанные структуры данных, в первую очередь во времени и пространстве, ну и т.д. По которым нужно восстановить протекание всех процессов, насколько я понимаю. Это совершенно разные вещи. В случае колайдера, как пишут, обработка может занять годы, на инфраструктуре аналогичной гугловской.
Но Гугл сортировал слабо связанные или несвязанные «числа». Напротив, например, колайдер выдаёт не просто «числа», а связанные структуры данных, в первую очередь во времени и пространстве, ну и т.д. По которым нужно восстановить протекание всех процессов, насколько я понимаю. Это совершенно разные вещи. В случае колайдера, как пишут, обработка может занять годы, на инфраструктуре аналогичной гугловской.
Надеюсь, корпорация Umbrella ээ… Google с такой мощностью подольше будет оставаться корпорацией добра :0)
Отсюда можно вычислить энергетическую ценность такой сортировки, если принять потребляемую мощность каждого компа за 600 Вт — это скромно для 12 дисков на машину.
6 часов * 4000 компов * 600 Вт = 14,4 МВт*час = 51,84 ГДж.
А если еще посчитать затраты на охлаждение… Хорошая игрушка.
6 часов * 4000 компов * 600 Вт = 14,4 МВт*час = 51,84 ГДж.
А если еще посчитать затраты на охлаждение… Хорошая игрушка.
Интересно, с такими темпами уже можно подобрать пароль для любого MD5 хеша?
Если я верно понял ваш вопрос, то нахождение коллизии для md5 (по данным securitylab.ru от 2005 г.) составляет 8 часов на Intel Pentium 1,6 GHz.
Неправильно поняли. Из-за [url=http://ru.wikipedia.org/wiki/Парадокс_дней_рождения]известного парадокса[/url] коллизию найти гораздо проще чем подобрать пароль. Подобрать пароль даже Google не может пока…
Что значит коллизию найти гораздо легче чем подобрать пароль? Как отличить реальный пароль от коллизии, если единственное что мы знаем о пароле — это результат хеширования, который будет одинаков для пароля и для коллизии?
И в поиске коллизий парадокс дней рождения ничем не поможет. Он работает если у вас есть, допустим, миллион хешей — тогда шанс что два каких-то _случайных_ хеша совпадут достаточно высок. Но если у вас есть один конкретный хеш — тут уже не парадокс нужен, а радужные таблицы или брутфорс.
И в поиске коллизий парадокс дней рождения ничем не поможет. Он работает если у вас есть, допустим, миллион хешей — тогда шанс что два каких-то _случайных_ хеша совпадут достаточно высок. Но если у вас есть один конкретный хеш — тут уже не парадокс нужен, а радужные таблицы или брутфорс.
Что значит коллизию найти гораздо легче чем подобрать пароль?Да.
Как отличить реальный пароль от коллизии, если единственное что мы знаем о пароле — это результат хеширования, который будет одинаков для пароля и для коллизии?Ну если вы не сами выбираете пароль, то никак.
И в поиске коллизий парадокс дней рождения ничем не поможет.Очень даже поможет. Вы вообще в курсе — что именно строится за 8 часов на Intel Pentium 1,6 GHz? Правильно:
В 2005 году исследователи Сяоюнь Ван и Хунбо Ю из университета Шандонг в Китае, опубликовали алгоритм, который может найти две различные последовательности 128 байт, которые дают одинаковый MD5 хешРассказывать — при чём тут парадокс близнецов и почему это не поможет вам подобрать пароль или не стоит?
э, в основном пароли как-бы не 128 символов, а? :)
тем более, практически ни один сервис не даст вам вбить такой суровый пасс…
тем более, практически ни один сервис не даст вам вбить такой суровый пасс…
Ответ «Да.» на вопрос «что значит?» меня поразил :)
Почему парадокс дней рождения превратился в парадокс близнецов я тоже не понял.
Парадокс дней рождения помогает найти коллизии второго рода, а odessky задавал вопрос о коллизиях первого рода.
Объясните, как имея заданный хеш, например «e76d565e7ba1b8ff4a7cc813bdf58284» (обычный MD5 без соли), парадокс дней рождения поможет мне найти его коллизию?
Почему парадокс дней рождения превратился в парадокс близнецов я тоже не понял.
Парадокс дней рождения помогает найти коллизии второго рода, а odessky задавал вопрос о коллизиях первого рода.
Объясните, как имея заданный хеш, например «e76d565e7ba1b8ff4a7cc813bdf58284» (обычный MD5 без соли), парадокс дней рождения поможет мне найти его коллизию?
Ответ «Да.» на вопрос «что значит?» меня поразил :)Бывает :-) А меня поразило ваше замечание — вроде как вы всё понимаете, но начинаете разводить демагогию.
Объясните, как имея заданный хеш, например «e76d565e7ba1b8ff4a7cc813bdf58284» (обычный MD5 без соли), парадокс дней рождения поможет мне найти его коллизию?Никак — потому тот факт что «нахождение коллизии для md5 (по данным securitylab.ru от 2005 г.) составляет 8 часов на Intel Pentium 1,6 GHz» не означает что «с такими темпами уже можно подобрать пароль для любого MD5 хеша».
Я думал вы не понимаете чем отличается процесс подбора коллизии от подбора пароля — а теперь я вообще уже не понимаю о чём вы спрашиваете.
Да, и если занести в таблицу только все возможные варианты md5-хэшей (без коллизий), они займут данных в намного больше порядков, чем петабайт.
Но есть проекты (типа passcracking.ru), собирающие такие базы. Копнул в гугле, нашел инфу по rainbowcrack.com — (он уже оказывается закрылся) — на 2007 г. у них было 900 Гб таблиц, которые позволяли с вероятностью порядка 99% найти за несколько минут обратное преобразование из хэша в любой пароль длиной до 7 символов (не только из букв, но также цифр и многих спец-символов), зашифрованных по алгоритмам LanMan, NT LanMan, MD2, MD4, MD5, SHA1, RIPEMD-160, Cisco PIX, MySQL 3.23, MySQL SHA1.
Так что все от задач зависит
Но есть проекты (типа passcracking.ru), собирающие такие базы. Копнул в гугле, нашел инфу по rainbowcrack.com — (он уже оказывается закрылся) — на 2007 г. у них было 900 Гб таблиц, которые позволяли с вероятностью порядка 99% найти за несколько минут обратное преобразование из хэша в любой пароль длиной до 7 символов (не только из букв, но также цифр и многих спец-символов), зашифрованных по алгоритмам LanMan, NT LanMan, MD2, MD4, MD5, SHA1, RIPEMD-160, Cisco PIX, MySQL 3.23, MySQL SHA1.
Так что все от задач зависит
>Да, и если занести в таблицу только все возможные варианты md5-хэшей (без коллизий), они займут данных в намного больше порядков, чем петабайт.
Просто цифры для общего интереса.
md5 — это 128 бит.
Т.е. кодируется 2^128 = 3,4*10^38 байт :) Это не просто больше на порядки, это на порядок порядков больше, чем петабайты.
Это, например, количество молекул воздуха, содержащиеся в кубике размером 23x23x23 км :)
Просто цифры для общего интереса.
md5 — это 128 бит.
Т.е. кодируется 2^128 = 3,4*10^38 байт :) Это не просто больше на порядки, это на порядок порядков больше, чем петабайты.
Это, например, количество молекул воздуха, содержащиеся в кубике размером 23x23x23 км :)
Ну не порядок порядков, а «всего-лишь» на 23 :)
Тоже хотел цифири привести, но задумался о том, во сколько раз количество занимаемого места увеличится при вставке всех этих хэшей в Berkeley DB (как по логике самая «малопотребляющая места» база, хотя не знаю)
Тоже хотел цифири привести, но задумался о том, во сколько раз количество занимаемого места увеличится при вставке всех этих хэшей в Berkeley DB (как по логике самая «малопотребляющая места» база, хотя не знаю)
>Ну не порядок порядков
Ну да, загнул… Двоичный порядок десятичных порядков ;)
>во сколько раз количество занимаемого места увеличится при вставке всех этих хэшей в Berkeley DB (как по логике самая «малопотребляющая места» база, хотя не знаю)
Ну, это, как раз, немного будет. Пусть даже по 100 байт на запись. Будет не 10^38, а 10^40. Не 23x23x23, а 108x108x108 км. Какая разница, тонна кирпичей на голову свалится или 10 тонн? © :)
Ну да, загнул… Двоичный порядок десятичных порядков ;)
>во сколько раз количество занимаемого места увеличится при вставке всех этих хэшей в Berkeley DB (как по логике самая «малопотребляющая места» база, хотя не знаю)
Ну, это, как раз, немного будет. Пусть даже по 100 байт на запись. Будет не 10^38, а 10^40. Не 23x23x23, а 108x108x108 км. Какая разница, тонна кирпичей на голову свалится или 10 тонн? © :)
Пишем грамотно: Пб — это петабит, ПБ — петабайт. То есть большая буковка «Б» — это байт, а маленькая «б» — это бит. По-моему, запоминается на раз.
Обратите внимание на оригинальные написания в блоге Гугла (TB, PB), посмотрите в Википедии, например en.wikipedia.org/wiki/Megabyte
На прошлой неделе Москалюка поправлял, который писал про вай-фай со скоростью 320 мегабайт в секунду неправильно (320 Mbps вместо MBps); видимо, это болезнь многих русских айтишников.
Обратите внимание на оригинальные написания в блоге Гугла (TB, PB), посмотрите в Википедии, например en.wikipedia.org/wiki/Megabyte
На прошлой неделе Москалюка поправлял, который писал про вай-фай со скоростью 320 мегабайт в секунду неправильно (320 Mbps вместо MBps); видимо, это болезнь многих русских айтишников.
Спасибо, поправил.
Ну не стоит всё-таки смешивать английское написание и наше. Если я правильно понял ГОСТ 8.417-2002 (Таблица А.1), то там вообще не вводится сокращения для «бит».
Разве «бит» сокращают? ИМХО, нет.
сокращают чаще всего «бит в секунду», просто потому что пропускная способность каналов исторически меряется в этих величинах, 10Mbps, например.
В русском для одноканальной линии биты в секунду обычно боды :)
если уж быть до конца педантом, то бод — это количество передач (изменений напряжения) в течение одной секунды, что не всегда равняется бит в секунду. Если же брать общий случай, то да, принято считать, что бод = бит в секунду
Я потому и отметил сразу, что в случае одноканальной передачи :)
вообще-то, количество каналов передачи на количество бод не влияет (а влияет на скорость передачи). Еще раз повторю, что БОД — количество ПЕРЕДАЧ за одну секунду.
Вообще-то, под каналом я имел в виду одну линию шины. Одна линия — одна передача — одна смена состояния в один момент времени.
ох, вот привязались-то мы к боду…
итак, внесем ясность.
бод — количество бит, переданное в секунду (при двоичном кодировании).
Однако одним изменением уровня сигнала может кодироваться несколько (до 16) бит информации (к примеру, квадратурная амплитудная модуляция — КАМ). Например, при символьной скорости 2400 бод скорость передачи может составлять 9600 бит/c благодаря тому, что в каждом временном интервале передаётся 4 бита.
итак, внесем ясность.
бод — количество бит, переданное в секунду (при двоичном кодировании).
Однако одним изменением уровня сигнала может кодироваться несколько (до 16) бит информации (к примеру, квадратурная амплитудная модуляция — КАМ). Например, при символьной скорости 2400 бод скорость передачи может составлять 9600 бит/c благодаря тому, что в каждом временном интервале передаётся 4 бита.
>ох, вот привязались-то мы к боду…
:)
>бод — количество бит, переданное в секунду (при двоичном кодировании).
Да нет же, бод — это количество изменений состояния в секунду. При любом кодировании :)
Но потом ты всё верно пишешь.
Если линия однобитовая (классический модем или ethernet), то бод — это 1 бит в секунду.
Если линия, скажем, 8-битная шина данных, то бод — это 8бит в секунду будет.
Вообще, вот: ru.wikipedia.org/wiki/Бод
…
Кстати, я не прав на счёт модема оказался :)
:)
>бод — количество бит, переданное в секунду (при двоичном кодировании).
Да нет же, бод — это количество изменений состояния в секунду. При любом кодировании :)
Но потом ты всё верно пишешь.
Если линия однобитовая (классический модем или ethernet), то бод — это 1 бит в секунду.
Если линия, скажем, 8-битная шина данных, то бод — это 8бит в секунду будет.
Вообще, вот: ru.wikipedia.org/wiki/Бод
…
Кстати, я не прав на счёт модема оказался :)
Значится так:
мои слова «бод — количество бит, переданное в секунду (при двоичном кодировании)» следует понимать как: при двоичном кодировании сигнала, количество бод равно количеству бит в секунду (поэтому утверждение «бод — это 1 бит в секунду» справедливо только для однободовой (о как!) скорости).
итак, мы о чем спорим-то?
я изначально сказал, что БОД не всегда равен битам в секунду.
мои слова «бод — количество бит, переданное в секунду (при двоичном кодировании)» следует понимать как: при двоичном кодировании сигнала, количество бод равно количеству бит в секунду (поэтому утверждение «бод — это 1 бит в секунду» справедливо только для однободовой (о как!) скорости).
итак, мы о чем спорим-то?
я изначально сказал, что БОД не всегда равен битам в секунду.
Кроме того, гугл использовал десятичный петабайт (10^15), а не двоичный пебибайт (2^50).
Экономия составила более 114 тебибайт (2^40) или 125 терабайт (10^12) :)
Экономия составила более 114 тебибайт (2^40) или 125 терабайт (10^12) :)
Мы скоро все будем бродить в упорядоченном интернете %)
> В ходе эксперимента сотрудникам Google пришлось решать проблему с размещением 1 ПБ данных. Дело в том, что при каждом новом запуске сортировки, выходил из строя хотя бы один из 48 000 используемых жестких дисков. В итоге, было решено дать Google File System команду хранить по три копии каждого файла на разных жестких дисках.
Поправка: с такой проблемой сотрудникам Гугла приходится справлять не только в ходе эксперимента, а каждый день. Хранение всей информации в трёх экземплярах — это стандрт для GFS (Google File System).
Поправка: с такой проблемой сотрудникам Гугла приходится справлять не только в ходе эксперимента, а каждый день. Хранение всей информации в трёх экземплярах — это стандрт для GFS (Google File System).
Google хорошая компания.
Вдогонку: перевод сегодняшнего поста Mark C. Chu-Carroll.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка петабайта данных заняла 6 часов 2 минуты.