эффективный алгоритм для группировки узлов графа в параллельном/кластере

Question

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

• У каждого игрока есть состояние: «ждет игры» или «в игре». Только ожидающие игроки должны быть сгруппированы в игры
• каждая игра имеет минимальное и максимальное количество игроков

Мои мысли по реализации: График будут сохранены и доступны через базу данных NoSQL (из разных машин в кластере). Пока нет какой-либо конкретной схемы (любые предложения?). Также блокировка доступа к отдельным игрокам (а также пессимистическим блокировкам) не является вариантом, поскольку это потенциальное узкое место для замедления других процессов, которые будут пытаться получить/собрать одного и того же игрока (ов).

Мой вопрос: кто-нибудь реализовал такие алгоритмы? Какие-либо предложения?

PS: У меня уже есть идея, но сначала хочу обсудить/проверить, что предлагают люди.

Спасибо!

EDIT1: В ответ на Thomas Jungblut: Использование игровых автоматов - интересная идея, но (как только я ее правильно понимаю) она может не работать в некоторых случаях. Пример Fox: в каждой игре должно быть ровно 3 игрока. Новые 6 игроков (назовем их ABCDEF см exaple 1) вступают в графе/очереди один за другим в таком порядке: A, B, E, F, C, D.

example 1

В результате только одна игра будет создана (A, B, C), плюс 2 игры с пустыми слотами: (D) и (E, F). Но оптимальным должно быть 2 игры: (A, C, D) и (B, E, F), правильно?

Answer 1

Я подозреваю, что вы не должным образом продумали бизнес-требования.

Фразы типа «оптимальное согласование» с произвольными условиями пахнут NP-полным для меня. Вы не найдете эффективного точного решения для одного из тех, у кого большой набор данных, просто разумное приближение.

И какова стоимость субоптимального матча? Тебе приходится ждать немного дольше, чтобы найти кого-то. Не проблема.

Я бы выполнил что-то простое. У вас есть очередь игр, которые вы настраиваете. Каждый, кто приходит, пытается попасть в первую игру, не получив второго, не получив третьего, и так далее. Если ни один не найден, вы создаете новую игру в конце очереди. Игра начинается, когда она достигает максимального размера или фиксированного количества времени после достижения минимума. Когда игра начинается, она удаляется из передней части очереди.

С учетом этого, почему вы думаете, что будет миллион активных игроков?

Если это потому, что вы стартап с большими мечтами, я настоятельно рекомендую вам сосредоточиться на решении ваших известных проблем настолько эффективно, насколько это возможно. В маловероятном случае успеха (серьезно, вы видели статистику?), Вы можете масштабировать позже. И только решение реальных проблем резко улучшит ваши шансы на успех на всем пути от ужасающего к просто бедному. (Я не собираюсь обескураживать, но мечта о запуске - это бедные шансы безумных возвращений. Каждое действие, которое вы принимаете, должно быть направлено на улучшение шансов.)

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

Очевидное замечание, которое я не должен упоминать, заключается в том, что вы захотите реализовать критические биты производительности на относительно быстром языке. Если вы пишете, например, в основном на Python, это будет хороший кусок для написания на Java, Go или C++.

Далее, первое, что не будет масштабироваться, это информация о игроке. Так распределите это. Выполнение этого замедлит вашу проверку «can player fit in game». Поэтому добавьте за игру блокировку и распределите это вычисление асинхронно. Ограничьте, как сильно вы попытаетесь попасть в игру, прежде чем отказаться от нее и создать новую.

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

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

Я был бы шокирован, если вы достигнете этого уровня масштаба. Если вы превзошли его, я оставлю следующие шаги, например, покраснет Redis к вам.

Случайные заметки. Это достойный тип интервью. «Разработайте эту простую вещь, сделайте ее масштабной, сделайте ее более масштабной. Сделайте ее более масштабной». Если вы действительно ищете человека, который понимает распределенную производительность, это хороший тест. (Но только если собеседник может хорошо сказать из плохих ответов.)