Я читал Введение в Алгоритмы и начал получать несколько идей и вопросов, всплывающих в моей голове.Больше всего меня сбило с толку то, как вы подходите к разработке алгоритма для планирования элементов / сообщений в очереди, которая распределяется.
Мои мысли привели меня к просмотру Википедии по таким темам, как сортировка, очереди сообщений, планированиеРаспределенные хеш-таблицы, если назвать несколько.
Сценарий: Допустим, вы хотите иметь систему, которая помещает в очередь сообщения (например, строки или какой-либо сериализованный объект).Ключевой особенностью этой системы является избежание какой-либо одной точки отказа.Система должна была быть распределена по нескольким узлам в некотором кластере и должна последовательно (или как можно лучше) даже загружать рабочую нагрузку каждого узла в кластере, чтобы избежать горячих точек.
Вы хотите избежать использованияглавный / подчиненный дизайн для репликации и масштабирования (без единой точки отказа).Система полностью избегает записи на диск и поддерживает в памяти структуры данных.
Поскольку предполагается, что это какая-то очередь, система должна иметь возможность использовать различные алгоритмы планирования (FIFO, самый ранний срок, циклический перебор и т. Д.), Чтобы определить, какое сообщение должно быть возвращено при следующемзапрос независимо от того, к какому узлу в кластере сделан запрос.
Мои первоначальные мысли Я могу представить, как это будет работать на одной машине, но когда я начинаю думать о том, как выРаспространите что-то вроде этих вопросов, таких как:
Как бы я хэшировал каждое сообщение?
Как узнать, на какой узел было отправлено сообщение?
Как мне запланировать каждый элементчтобы я мог определить, какое сообщение и с какого узла должно быть возвращено следующим?
Я начал читать о распределенных хеш-таблицах и о том, как такие проекты, как Apache Cassandra, используют какое-то согласованное хеширование для распределения данных, но затем я подумал, посколькузапрос не предоставит ключ, мне нужно знать, где находится следующий элемент, и просто предоставить его ... Это приводит кчтение о одноранговых протоколах и о том, как они подходят к проблеме синхронизации между узлами.
Итак, мой вопрос: как бы вы подошли к проблеме, подобной описанной выше, или она слишком надуманна и просто глупа?идея ...?
Просто обзор, указатели, различные подходы, подводные камни и преимущества каждого.Технологии / концепции / дизайн / теория, которые могут быть уместными.По сути, все, что может пригодиться для понимания того, как что-то подобное может работать.
И если вам интересно, нет, я не собираюсь реализовывать что-то подобное, это просто выскочило у меня во время чтения (Бывает, меня отвлекают дикие идеи, когда я читаю хорошую книгу).
ОБНОВЛЕНИЕ
Еще один интересный момент, который может стать проблемой, - это распределенное удаление. Я знаю, что такие системы, как Cassandra, справились с этой задачей, внедрив HintedHandoff , Read Repair и AntiEntropy и, похоже, работают хорошо, но есть ли другие(жизнеспособный и эффективный) способ решения этой проблемы?