Балансировка нагрузки по модулю без мьютекса?

Возможно, я ошибаюсь, но вот моя проблема и предлагаемое решение:

У вас есть файл размером 50+ гигабайт с сотнями миллионов независимых записей, которые необходимо обработать очень быстро. Мое текущее решение - 74 миллиона записей в час. Я использую блокирующую очередь для потока ввода-вывода, и каждый рабочий поток пытается захватить фрагменты данных из этой очереди.

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

Есть ли способ обойтись без блокировок в этом стиле производителя / потребителя?


c++ multithreading pthreads large-files bigdata
person Mike Lyons    schedule 04.05.2011    source источник
comment
Вы уверены, что это раздор, а не просто удушье из-за ввода-вывода?   -  person Marcelo Cantos    schedule 04.05.2011
comment
Чтобы найти конкретное решение, требуется дополнительная информация. Что вы имеете в виду под независимыми записями? У каждой записи фиксированная длина? Записи бинарные или текстовые?   -  person Collin Dauphinee    schedule 04.05.2011

Ответы (3)


arrow_upward
1
arrow_downward

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

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

Один из способов гарантировать, что записи не перезаписываются, - это то, что рабочие потоки отправляют сообщение для обновления потока ввода-вывода с указанием количества обработанных записей, время от времени. Этот подход не требует блокировки; только атомарная операция для частого обновления потока ввода-вывода.

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

person Collin Dauphinee    schedule 04.05.2011
comment
Спасибо за совет. Просто наткнулся на это, прочитав ваш ответ и немного погуглил: msmvps.com/blogs/vandooren/archive/2007/01/05/ - person Mike Lyons; 04.05.2011

arrow_upward
0
arrow_downward

А как насчет одного потока чтения, помещающего куски рабочего размера в очередь, к которой имеют доступ потребители? Или пусть потребители помещают свои собственные идентификаторы в очередь, из которой средство чтения файлов извлекает каждый раз, когда читает очередной фрагмент. Последнее, вероятно, не будет часто блокировать читателя.

person AShelly    schedule 04.05.2011
comment
Я делаю пакетное распределение, которое вы уже упоминали, ввод-вывод считывает некоторый размер буфера, скажем, 20000 записей, и помещает их в единую структуру данных, которую рабочий поток занимает целиком. Я думал, что с такой настройкой я смогу минимизировать блокировку. Видимо я этого недостаточно свернул :) - person Mike Lyons; 04.05.2011

arrow_upward
0
arrow_downward

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

Что касается ввода-вывода: можно ли разделить файл? Если у вас есть дешевый способ определить конец записи, можно просто разделить файл и разместить различные части на разных машинах. Или просто купите более быстрый HDD.

person Matthieu M.    schedule 04.05.2011