В настоящее в время существует огромное количество сетей распределенных вычислений. Я насчитал порядка 30. Наиболее крупные — Folding@home, BOINC, SETI@home, Einstein@Home, Rosetta@home (по результатам их вычислений было написано несколько десятков диссертаций). Вычисляют они все, что только можно вычислять распределено — от подбора md5 паролей до симуляции свертывания белка.
Каждая из эти сетей имеет необычно высокую производительность и включает в себя миллионы нодов. Производительность каждой сравнима с производительностью суперкомпьютера.
По расчетам на конец 2010 года пользователей Инернет было около 2000000000 (2 млрд).
Каждый пользователь имеет хотя бы 1 ядро процессора производительностью не менее 8 Гфлопс (AMD Athlon 64 2,211 ГГц).
По нехитрым математическим расчетам производительность такой сети составит:
Такая сеть в 800 раз производительней, чем ещё не построенная IBM Sequoia (2012), в 1700 раз производительней, чем сеть Bitcoin и производительней всех суперкомьютеров и вычислительных сетей вместе взятых! Сейчас число пользователей ПК и Интерент растет, растет и число ядер. Безусловно, это число (16 эксафлопс) идеальное, никто не будет вычислять 24/7, но если каждый пользователь будет вычислять хотя бы 2 минуты в день (что, впринципе, более чем реально), то такая сеть сравнится с IBM Sequoia.
Сейчас распределенные браузерные вычислительные сети на JavaScript более чем реальны.
Эта стятья логическое продолжение моей статьи годичной давности: Распределенные вычисления на javascript
Что же изменилось за год и что мешало создать вычислительную сеть год назад?
Практически все хорошие браузеры за год получили WebWorkers, localStorage, SQL DB, IndexedDB. Нам ничего не мешало год назад вычислять в основном потоке JavaScript и использовать Flash Storage, но вычисление в основном потоке является потрясающим источником лагов, а Flash Storage ограничен по объему. Год назад у нас получилась бы распределенная сеть-инвалид: лагучая, костыльная, навязчивая.
Сейчас же мы с помощью WebWorkers можем утилизировать 100% ресурсов 1-го ядра процессора, если 2 воркера, то 2 ядер (распределение воркров по ядрам зависит от реализации воркеров в конкретном браузере). Мы практически не ограничены объемом, хранимых данных: 50Мб IndexedDB (Firefox) + 5Мб localStorage + ещё какое-то хранилище. Этих 55+Мб нам хватит для хранения данных задачи и промежуточных данных. В конце 2010 в 2011 году необычаной быстро начал развиваться Node.js. Я считаю, что это идеальное решение для сервера распределенных вычислений.
Мы имеем: Подходящие технологии Node.js + WebWorkers + localStorage + IndexedDB. 2000000000 интернет пользователей, число которых увеличивается. Количество ядер растет и их производительность увеличивается. С каждым месяцем браузеры становятся все быстрее и быстрее. Сейчас самое время направить этот поток не утилизированных мощностей размером в 16 эксафлопс в правильное русло!
Пока вы просматриваете страницу, ваш процессор загружен на 10-20%, пока вы смотрите видео с YouTube ваш процессор загружен на 30-50% (не думаю, что больше). Вам приходится смотреть рекламу и назойливые флеш-банеры, которые могут загрузить ваш процессор. Представьте, что вместо просмотра назойливых банеров и рекламы вас просят повычислять на благое дело: вы смотрите видео с YouTube, а в это время ваш браузер вычисляет свертывание белка для Folding@home. Представьте, что пока вы скачиваете файл с вашего любимого файлообменника, а в это время ваш браузер вычисляет что-то полезное за это вы не смотрите рекламу (я прекрасно знаю про adBlock). Представьте, что пока вы читаете эту статью ваш браузер вычисляет что-то полезное. При этом каждый пользователь, пришедший на сайт, делает что-то полезное для сайта, то, что может принести доход или пользу обществу. Утопично, но реализуемо.
Любую задачу в которой нужна молотилка цифр: задачи полного перебора, обучение нейросетей и т.п. и которая вычисляется параллельно, ибо по Закону Амдала распределенное вычисление наиболее эффективны только в том случае если задача не имеет последовательных вычислений т.е. вычисления одной ноды не зависят от данных другой.
Интересно? Давайте сделаем такую сеть!
В примере я покажу какую архитектуру сети можно выбрать для этой задачи. Мы будем подбирать пароль длина 8 и менее символов, алфавит 96 и менее символов из хэша md5. Понятно, что так или иначе задача решается только полным перебором. Не будем использовать словари паролей или какие-то хитрые схемы — просто перебор.
Мы имеем максимум 968 потенциальных паролей. Дадим каждому паролю номер в 10-ричной системе от 1 до 968. Теперь каждый пароль можно получить переводом числа в 10-ричной системе в 96-ричную (
Каждая задача будет содержать промежуток из 400000 паролей для подбора (Google Chrome вычисляет около 200000 md5 в секунду). Всего у нас 18034739475 задач — много, но не так безнадежно как с паролем из 16 символов… Может случиться так, что клиент забрал задачу, но не выполнил. Для каждой задачи добавим время после которого она устареет — expires.
Логика клиента сети элементарна — в цикле перебираем пароли от N1 до N2 для каждого находим md5, полученный хэш сравниваем с эталоном. Если хэши совпадают — отправляем на сервер пароль, иначе пустую строку:
1. Клиент приходит на сервер, авторизуется
2. Клиент загружает вычисляющие скрипты и прочую промежуточную логику
3. Клиент удаляет устаревшие задачи из Хранилища
4. Клиент запускает Воркеры (количество их зависит от настройки)
5. Клиент проверяет задачи (в Хранилище), которые были выполнены, но не доставлены на сервер — Отправляет эти задачи через Воркеры
6. Каждый Воркер запрашивает задачи с Сервера или берет не выполненные задачи из Хранилища через Клиент (1-ну или несколько)
7. Клиент сохраняет задачи в Хранилище (на случай если будет перезагружена страница)
8. Каждый Воркер начинает вычислять свою задачу
9. После окончания вычисления задачи Воркер сохраняет решение в Хранилище (на случай если будет перезагружена страница или сервер не доступен)
10. Воркер отправляет решение задачи на Сервер (и так далее с пункта 6)
Пока клиент выполняет задачу другие клиенты (скрипты на других страницах в одном браузере) блокируются.
1. Сервер авторизует Клиента
2. Приходит запрос задачи от Воркера — Сервер проверяет устаревшие задачи, если такие есть — отправляет клиенту
2.1. Если устаревших задач нет — создает новую задачу, отправляет клиенту
3. Воркер отправляет ответ на задачу — Сервер проверяет ответ, отмечает задачу как выполненную
3.1. Сервер отправляет Воркеру новую задачу (и так далее с пункта 2)
4. Как только Сервер получает правильный ответ от Воркера Сервер не прекрашает работу — не выдает задачи
Выше была представлена простая схема работы MD5 Брутфорс сервера, реализовать схему практически можно с использованием Фрэймворка для построения сетей распределенных вычислений JavaScript ECDC
То, что получилось у меня вы можете посмотреть вот тут: Сервер Подбора пароля из md5 хэша (при первом входе вы получите сообщение «You are unauthorized. Login»), Вы можете использовать любой email или любое имя, они используются для ведение вашей статистики — вашего вклада в объем вычислений (хранятся в виде md5 хэша).
Статистику подбора пароля можно посмотреть тут (необходима авторизация).
Клиент Сети работает только в браузерах с поддержкой Workers, localStorage, JSON, XMLHttpRequest. Если вы ведите фразу «You are calculating md5», то вы учительствуете в вычислении, ура! Я включил лог работы воркеров, то, что они делают вы можете посмотреть в любой консоли.
Вы можете встроить вычисляющий фрэйм на вашу страницу его код можно найти в исходнике главной страницы.
1. Рабочий пример сервера подбора пароля
2. Статистика подбора пароля (необходима авторизация на главной)
3. JavaScript Фрэймворк для создания сетей распределенных вычислений
4. Исходный код сервера в примере: md5-bruteforce-server.js, md5-bruteforce-server/
Система доказала свою жизнеспособность (в тесте я успешно подобрал 3-символьный пароль, да серьёзно!) осталось проверить её на достаточно больших объемах пользователей, за одним проверим потенциал хостинга от nodester.
Участвуете ли вы в каких-либо распределенных вычислениях? Как вы считаете есть ли будущее у браузерных распределенных вычислительных сетей? Хотели ли вы вместо просмотре рекламы и во время просмотра видео с YouTube вычислять что-то полезное?
Критика, предложения, пожелания приветствуются!
Каждая из эти сетей имеет необычно высокую производительность и включает в себя миллионы нодов. Производительность каждой сравнима с производительностью суперкомпьютера.
- Rosetta@home — более 110 Тфлопс
- Einstein@Home — более 355 Тфлопс
- SETI@home — более 560 Тфлопс
- BOINC — более 5.6 Пфлопс
- Folding@home — более 5.9 Пфлопс
- Bitcoin — более 9.4 Пфлопс
- Blue Gene/L (2006) — 478.2 Тфлопс
- Jaguar (суперкомпьютер) (2008) — 1.059 Пфлопс
- IBM Roadrunner (2008) — 1.042 Пфлопс
- Jaguar Cray XT5-HE (2009) — 1.759 Пфлопс
- Тяньхэ-1А (2010) — 2.507 Пфлопс
- IBM Sequoia (2012) — 20 Пфлопс
По расчетам на конец 2010 года пользователей Инернет было около 2000000000 (2 млрд).
Каждый пользователь имеет хотя бы 1 ядро процессора производительностью не менее 8 Гфлопс (AMD Athlon 64 2,211 ГГц).
По нехитрым математическим расчетам производительность такой сети составит:
8 * 109 * 2 * 109 = 16 эксафлопс (1018). Такая сеть в 800 раз производительней, чем ещё не построенная IBM Sequoia (2012), в 1700 раз производительней, чем сеть Bitcoin и производительней всех суперкомьютеров и вычислительных сетей вместе взятых! Сейчас число пользователей ПК и Интерент растет, растет и число ядер. Безусловно, это число (16 эксафлопс) идеальное, никто не будет вычислять 24/7, но если каждый пользователь будет вычислять хотя бы 2 минуты в день (что, впринципе, более чем реально), то такая сеть сравнится с IBM Sequoia.
Сейчас распределенные браузерные вычислительные сети на JavaScript более чем реальны.
Эта стятья логическое продолжение моей статьи годичной давности: Распределенные вычисления на javascript
Что же изменилось за год и что мешало создать вычислительную сеть год назад?
Практически все хорошие браузеры за год получили WebWorkers, localStorage, SQL DB, IndexedDB. Нам ничего не мешало год назад вычислять в основном потоке JavaScript и использовать Flash Storage, но вычисление в основном потоке является потрясающим источником лагов, а Flash Storage ограничен по объему. Год назад у нас получилась бы распределенная сеть-инвалид: лагучая, костыльная, навязчивая.
Сейчас же мы с помощью WebWorkers можем утилизировать 100% ресурсов 1-го ядра процессора, если 2 воркера, то 2 ядер (распределение воркров по ядрам зависит от реализации воркеров в конкретном браузере). Мы практически не ограничены объемом, хранимых данных: 50Мб IndexedDB (Firefox) + 5Мб localStorage + ещё какое-то хранилище. Этих 55+Мб нам хватит для хранения данных задачи и промежуточных данных. В конце 2010 в 2011 году необычаной быстро начал развиваться Node.js. Я считаю, что это идеальное решение для сервера распределенных вычислений.
Мы имеем: Подходящие технологии Node.js + WebWorkers + localStorage + IndexedDB. 2000000000 интернет пользователей, число которых увеличивается. Количество ядер растет и их производительность увеличивается. С каждым месяцем браузеры становятся все быстрее и быстрее. Сейчас самое время направить этот поток не утилизированных мощностей размером в 16 эксафлопс в правильное русло!
Куда можно встроить клиенты сетей?
Пока вы просматриваете страницу, ваш процессор загружен на 10-20%, пока вы смотрите видео с YouTube ваш процессор загружен на 30-50% (не думаю, что больше). Вам приходится смотреть рекламу и назойливые флеш-банеры, которые могут загрузить ваш процессор. Представьте, что вместо просмотра назойливых банеров и рекламы вас просят повычислять на благое дело: вы смотрите видео с YouTube, а в это время ваш браузер вычисляет свертывание белка для Folding@home. Представьте, что пока вы скачиваете файл с вашего любимого файлообменника, а в это время ваш браузер вычисляет что-то полезное за это вы не смотрите рекламу (я прекрасно знаю про adBlock). Представьте, что пока вы читаете эту статью ваш браузер вычисляет что-то полезное. При этом каждый пользователь, пришедший на сайт, делает что-то полезное для сайта, то, что может принести доход или пользу обществу. Утопично, но реализуемо.
Что же можно вычислять?
Любую задачу в которой нужна молотилка цифр: задачи полного перебора, обучение нейросетей и т.п. и которая вычисляется параллельно, ибо по Закону Амдала распределенное вычисление наиболее эффективны только в том случае если задача не имеет последовательных вычислений т.е. вычисления одной ноды не зависят от данных другой.
Интересно? Давайте сделаем такую сеть!
Пример распределенных вычислений: Подбор пароля из md5 хэша
В примере я покажу какую архитектуру сети можно выбрать для этой задачи. Мы будем подбирать пароль длина 8 и менее символов, алфавит 96 и менее символов из хэша md5. Понятно, что так или иначе задача решается только полным перебором. Не будем использовать словари паролей или какие-то хитрые схемы — просто перебор.
Распределение задач
Мы имеем максимум 968 потенциальных паролей. Дадим каждому паролю номер в 10-ричной системе от 1 до 968. Теперь каждый пароль можно получить переводом числа в 10-ричной системе в 96-ричную (
from10toN), используя не хитрое преобразование и алфавит: var alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKL" +
"MNOPQRSTUVWXYZ+/*-\\?=`~!@#$%^&*()_{}[];:'\"|.,<> ",
alphabetLength = alphabet.length;
function from10toN (number, base) {
if (!base || base > alphabetLength) {
base = alphabetLength;
}
if (base < 2) {
base = 2;
}
var result = '';
while (number > 0) {
result = alphabet.charAt(number % base) + result;
number = Math.floor(number / base);
}
return result;
}Каждая задача будет содержать промежуток из 400000 паролей для подбора (Google Chrome вычисляет около 200000 md5 в секунду). Всего у нас 18034739475 задач — много, но не так безнадежно как с паролем из 16 символов… Может случиться так, что клиент забрал задачу, но не выполнил. Для каждой задачи добавим время после которого она устареет — expires.
Логика клиента сети элементарна — в цикле перебираем пароли от N1 до N2 для каждого находим md5, полученный хэш сравниваем с эталоном. Если хэши совпадают — отправляем на сервер пароль, иначе пустую строку:
EcdcWorker.prototype.calculateSync = function (id, data) {
var maxPasswordId = data.max,
password,
alphabetBase = data.base,
hash = data.hash;
for (var i = data.min; i <= maxPasswordId; i++) {
// переводим ид пароля в реальный пароль
// затем вычисляем md5
password = from10toN(i, alphabetBase);
if (md5(password) === hash) { // tada!
return {id: id, data: password}; // найдено
}
}
return {id: id, data: ""}; // не найдено
};Логика Клиента
1. Клиент приходит на сервер, авторизуется
2. Клиент загружает вычисляющие скрипты и прочую промежуточную логику
3. Клиент удаляет устаревшие задачи из Хранилища
4. Клиент запускает Воркеры (количество их зависит от настройки)
5. Клиент проверяет задачи (в Хранилище), которые были выполнены, но не доставлены на сервер — Отправляет эти задачи через Воркеры
6. Каждый Воркер запрашивает задачи с Сервера или берет не выполненные задачи из Хранилища через Клиент (1-ну или несколько)
7. Клиент сохраняет задачи в Хранилище (на случай если будет перезагружена страница)
8. Каждый Воркер начинает вычислять свою задачу
9. После окончания вычисления задачи Воркер сохраняет решение в Хранилище (на случай если будет перезагружена страница или сервер не доступен)
10. Воркер отправляет решение задачи на Сервер (и так далее с пункта 6)
Пока клиент выполняет задачу другие клиенты (скрипты на других страницах в одном браузере) блокируются.
Логика Сервера
1. Сервер авторизует Клиента
2. Приходит запрос задачи от Воркера — Сервер проверяет устаревшие задачи, если такие есть — отправляет клиенту
2.1. Если устаревших задач нет — создает новую задачу, отправляет клиенту
3. Воркер отправляет ответ на задачу — Сервер проверяет ответ, отмечает задачу как выполненную
3.1. Сервер отправляет Воркеру новую задачу (и так далее с пункта 2)
4. Как только Сервер получает правильный ответ от Воркера Сервер не прекрашает работу — не выдает задачи
Общая схема
[Workers: EcdcWorker]
/ \
Tasks: XHR / \ Messages: postMessage
/ Page: html \
[Server: EcdcServer] ------------ [Browser: EcdcClient] --- [User]
| |
[Database: Any] [Storage: localStorage]
Выше была представлена простая схема работы MD5 Брутфорс сервера, реализовать схему практически можно с использованием Фрэймворка для построения сетей распределенных вычислений JavaScript ECDC
Результат
То, что получилось у меня вы можете посмотреть вот тут: Сервер Подбора пароля из md5 хэша (при первом входе вы получите сообщение «You are unauthorized. Login»), Вы можете использовать любой email или любое имя, они используются для ведение вашей статистики — вашего вклада в объем вычислений (хранятся в виде md5 хэша).
Статистику подбора пароля можно посмотреть тут (необходима авторизация).
Клиент Сети работает только в браузерах с поддержкой Workers, localStorage, JSON, XMLHttpRequest. Если вы ведите фразу «You are calculating md5», то вы учительствуете в вычислении, ура! Я включил лог работы воркеров, то, что они делают вы можете посмотреть в любой консоли.
Вы можете встроить вычисляющий фрэйм на вашу страницу его код можно найти в исходнике главной страницы.
Ссылки
1. Рабочий пример сервера подбора пароля
2. Статистика подбора пароля (необходима авторизация на главной)
3. JavaScript Фрэймворк для создания сетей распределенных вычислений
4. Исходный код сервера в примере: md5-bruteforce-server.js, md5-bruteforce-server/
Заключение
Система доказала свою жизнеспособность (в тесте я успешно подобрал 3-символьный пароль, да серьёзно!) осталось проверить её на достаточно больших объемах пользователей, за одним проверим потенциал хостинга от nodester.
Участвуете ли вы в каких-либо распределенных вычислениях? Как вы считаете есть ли будущее у браузерных распределенных вычислительных сетей? Хотели ли вы вместо просмотре рекламы и во время просмотра видео с YouTube вычислять что-то полезное?
Критика, предложения, пожелания приветствуются!
