Как обрабатывать график, который постоянно обновляется с низкой задержкой?

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

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

Проблемы, которые я могу предвидеть:

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

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

У меня возникла идея обрабатывать различные части графика и индексировать их, а затем отслеживать, где график обновляется и перерабатывать этот раздел графика (своего рода подход к распределенному динамическому программированию), но im not уверен, насколько это возможно.

Спасибо!

Ответ 1

Как мне начать сталкиваться с этими проблемами?

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

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

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

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

Если 2. приемлемо, у вас есть возможность для более высокой производительности. Однако есть компромиссы. У вас возникнут ситуации, когда вы должны отменить транзакцию после первоначального принятия.

Как только вы ответили на этот вопрос, вы столкнулись с вашими проблемами и, я полагаю, будут иметь дополнительные вопросы.

Ответ 2

Я мало знаю о графиках, но понимаю, что я немного разбираюсь в сетях.

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

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

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

Клиенты должны знать только, есть ли новые записи или старые записи были изменены.

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