@AlexHell

Есть ли структура данных для многопоточной обработки с лимитами не-параллельности по ID?

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

Должна быть такой:
1) Очередь сообщений (возможно несколько), при этом у каждого сообщения есть SubjectId (скажем ID пользователя и т.п.)
2) Пул потоков (т.е. больше 1 потока в общем виде), которые берут сообщения из очереди и начинают их исполнять (consumer)
3) При этом обязательно запрещено начинать исполнение запроса с SubjectId который уже исполняется, т.е.
можно начать исполнять в 1м потоке Message с SubjectId == 1,
можно во 2м потоке Message с SubjectId == 2,
но если условно у нас 3 потока, то нельзя начать исполнять в 3м потоке Message с SubjectId == 1 или 2, это должен быть любой другой SubjectId
* как только один из потоков закончил работу, тот SubjectId становится свободным, скажем == 1, и тогда новый поток может взять Message с SubjectId == 1 из очереди (структуры)

Для чего нужна такая структура - чтобы не требовались дополнительные критические секции (lock \ synchronized) в разрезе одинаковых объектов, т.к. когда мы работаем в параллель с объектом с SubjectId == 1 из 2х потоков то мы обязаны lock-ть обращения к его структурам, а в случае же такой структуры - lock-ть не нужно на сам объект (с SubjectId) (хотя возможны lock-и на другие общие структуры - не суть вопроса)

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

Главное чтобы тут все не было покрыто lock-ами или их аналогами, что сильно порежет перфоманс изза простоя ядер CPU.

Как мне видится на первый взгляд тут нужен HashMap с ключем SubjectId и значение List т.е. все сообщения которые по этому SubjectId.
И куча обвязки в виде начал и конца обработки, выбора нужного SubjectId и т.п.

Тут есть сходство с акторами из Akka, но я не эксперт в них. Но самое главное что в них не устраивает на первый взгляд - каждый actor это инстанс через new и со своей очередью, а если в большинстве случаев у нас разные SubjectId то расточительно по памяти иметь по инстансу класса со своей очередью на один-два Message да плюс не известно как оно по перфомансу будет в таком кол-ве акторов. Например если у нас SubjectId от 1 до 1_000_000 то создастся 1_000_000 акторов, у каждого своя очередь, что вероятно траблы (надо профайлить).

__ update

глобальный порядок не нужен (действительно если бы нужен был - только в однопотоке можно это сделать), а вот локальный желателен

и если получится - глобальный хоть сколько-нибудь нужен в том плане чтобы не висели задачи в очереди вечно, например если придет 1я задача, 2я .. 1000я, не надо чтобы 1я висела до окончания веков, потому что новые задачи будут появляться (1000я-2000я и т.п)
  • Вопрос задан
  • 132 просмотра
Пригласить эксперта
Ответы на вопрос 2
sergey-gornostaev
@sergey-gornostaev
Седой и строгий
Выглядит как обычный striped lock. Берёте обычную очередь, обычный пул потоков и заполняете массив экземплярами Lock. Поток в начале работы берёт Message из очереди, получает из него SubjectId, вычисляет его хэш и пытается захватить блокировку из соответствующего хэшу элемента массива. Если блокировка удалась, поток выполняет свою работу. Если нет, возвращает Message в конец очереди и берёт следующий из начала. Остаётся только подобрать эффективный размер массива блокировок.
Ответ написан
Думаю надо почитать про "Очереди сообщений" и сервис RabbitMQ https://habr.com/ru/post/150134/
"Это как раз то что вам НУЖНО, Поттер"
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы