Как правильно реализовать систему распределенных вычислений?

Question

[Николай Маринкин]

У меня довольно необычная задача...

Есть проект(node.js) который довольно высоко нагружен.
Задача проекта:

• В базе данных(Redis) есть более 20 миллионов крупных записей(у каждой свыше 100 различных параметров в JSON-строке)
  
• Есть очень сложная функция, которая модифицирует запись.
  
• Каждая запись обязательно должна обрабатывается функцией раз в 10-15 секунд, и выдавать в качестве результата большой объект(конкретно - большущий лог своей работы)
  
• Допустимая задержка не более 10 секунд(не должно быть запланировано выполение новой итерации, если не была выполнена старой, иначе система даст сбой)
  

Имеющиеся ресурсы:

• 5000$ на железо
  
• около 100.000 одновременно работающих клиентов(Android(Unity 3D), iOS(Unity 3D), браузеры(JS, поддержка с IE10)) на WebSocket
  

Как видно из задачи и ресурсов, бюджет на сервера в 5000 долларов не расчитан на такое приложение, но у нас довольно много активных клиентов. Потому напрашивается идея о распределенных вычислениях клиентами.

Схема сейчас следующая:
1. Все записи во время каждой итерации кладутся в стек FIFO, назовем его "стек задач"
2. На каждый клиент во время начала сессии отправляется функция-обработчик(она часто меняется, мы не можем позволить внедрять ее в код клиента)
3. Каждый клиент, когда ему нечего делать, берет из стека задачу. Выполняет ее и отправляет результат на сервер.
4. Сервер кладет полученный результат в FIFO-стек который назовем "стек валидации"
5. Каждый клиент так же периодически берет задачи по валидации не своих результатов(мы не можем сильно доверять одному клиенту). Проводит валидацию и отправляет результат на сервер.
5.1. Если валидация успешна - модифицируем запись и закрываем задачу.
5.2. Если валидация провалена - сервер сам, лично займется задачей

Но проблемы в следующем:

• С браузерами проблем нет - там клиенты на JS и вполне справятся с функцией, но браузерных клиентов у нас слишком мало(не больше 10.000), в основном сидят с телефонов и планшетов. Можно ли организовать кроссбраузерную функцию, работающую и на сервере и на всех типах клиентов одинаково? Если да, то каким примерно образом?
  
• Можно ли вообще так делать? Если да, то обязательно ли предупреждать пользователей? Сильно нагружать клиентов не планируем, будем делать небольшие перерывы между вычислениями, иначе потеряем доверие к приложению из-за отзывов типа "жрет батарейку за несколько часов". Нагружать клиентов, у которых приложение свернуто(только в случае мобильных платформ), так же не планируем.
  

UPD:
Время выполнения функции сервером около 30мс

UPD 2:
Наверное мне все же стоит кратко описать функционал:
Записи в БД - это персонажи игроков.
Функция-обработчик это генерация боя между двумя персонажами. Результатом является полноценный лог боя, который позже воспроизводит клиент.
На вход функции передаются только те данные, которые нужны и ничего лишнего.
Функция довольно хорошо оптимизирована, но в силу сложной механики игры эта функция все равно сложна(представьте себе быстрый генератор матчей между ботами в какой нибудь игре вроде Heroes of Might and Magic в режиме боя, запускаемый два миллиона раз в секунду).

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

UPD 3:
Способ решения проблемы сменой языка и покупкой специфического железа - это конечно хорошо, нам следовало бы вообще написать проект на Erlang... ведь мы не знали что будет такая проблема, и считали node.js подходящим языком, способным пройти такой стресс-тест.
Но давайте все же попытаемся найти ответы на вопросы:

1. О возможности эффективно выполнить функцию написанную на одном языке программирования(абсолютно любой язык высокого уровня, не обязательно JS, может быть даже Lua), разными языками программирования.
   
2. О легальности выполнения подобных вычислений на клиенте, с ведомом и без ведома пользователя. Ведь эти вычисления выполняются пользователем не для него самого, а для третьего лица.
   

Comments

[Кирилл]

Если делать как предлагаете вы, сложность системы будет слишком большая на мой взгляд, потом баги ловить бесконечно придется. Проще было бы ответить, если бы вы могли сообщить больше подробностей о данных и о том, какие модификации они проходят. А вы уверены что нельзя модифицировать запись при обращении к ней например? Мне нравится совет Pavel, возможно есть способ поменять формат данных таким образом, что обработка в N потоков на текущем железе на каком нибудь Go или Си, станет приемлемой по скорости задачей?

Answer 1

[Юрий]

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

Comments

[Николай Маринкин]

Спасибо. Довольно интересное решение вопроса о этике и легальности использования распределенных вычислений - мне очень нравится философия такого подхода.
Учитывая что игра f2p с донатом влияющим на баланс - это реально способ получения дополнительной взаимной выгоды.
Скорее всего мы применим что-нибудь эдакое, о результатах обязательно сообщу с релизом и полевыми испытаниями этого функционала.

Offtop:
По поводу майнинга, имеет ли смысл в 2015 году использовать подобную "ферму"? Я уже давно не в курсе сложности майнинга. Если на этой "ферме" можно будет заработать хотя-бы 10-20 биткоинов в месяц - то с этого будет ощутимая выгода.

[Юрий]

Николай Маринкин: решение самому понравилось - оно просто взаимовыгодное, и клиенты злится не будут если батарея садится - потому что выбор осознанный, им за это платят, но они и отказаться могут, если это правильно вписать в геймпдей, например как сбор некой силы, то получится довольно интерсно и взаимовыгодно, ктото только ради этого может будет на компе заходить параллельно, или вкладку открытой оставлять например на рабочем компе ))) сам раньше играл, знаю что это такое ))).

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

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

[Юрий]

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

[Николай Маринкин]

Юрий: в случае успешного запуска распределенной системы можно попробовать выпустить игру на Win, Mac и Linux - возмножно она найдет там свою нишу. Проблема только в том, что этот жанр больше подходит для мобильников... это все равно что выпускать Cookie Clicker в Steam. Да и если использовать ботнет для майнинга в игре - то уж точно нужно предупредить об этом игроков.
Мы используем подобную схему и для рекламы - она запускается только с согласия пользователя и за награду.

[Юрий]

Николай Маринкин: согласен

[Юрий]

Neoline: так я и предлагаю чтобы они честно им чем то платили, пусть внутриигровыми бубликами, но все же.

а так рынок же свободный - если сайт конкурента не грузит а ваш грузит, для кого то это может быть решающим словом.

Answer 2

[DrunkMaster]

Вам сложно помочь даже при желании. Первым делом надо посмотреть что там за строка с параметрами, все ли в ней необходимы. Допустим все. Все ли необходимы именно сейчас? Видели наверное что статистика (процент побед) у WOT обновляется раз в сутки ночью - не случайно же.
Про GO Pavel верно сказал, посмотрите в сети исходники Ogame - там вся игра на php но система боя написана на каком-то из С-языков.
Зачем вам распределённая система? Купите на 5000$ 1 сервер почти без оперативы и HDD, закажите туда процессоров побольше и напишите обработчик на GO, C++ и т.п. Отправляйте все задачи по расчётам на него. PROFIT! )))

Answer 3

[Ai Lab]

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

Comments

[Николай Маринкин]

Это в нашей системе уже используется...
"Неактивных" игроков мы считаем по множеству итераций разом в больших интервалах времени, при этом высылая им уведомления вроде "За время отсутствия вы получили множество наград" =)