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

Question

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

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

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

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

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

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

Answer 2

Я мало знаю о графах, но я понимаю немного сетей.

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

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

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

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

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