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