Оттенки FIFO

Контекст — различные системы, в которых есть производители/ потребители/ актёры/ агенты/ процессы и т.д., и в которых так или иначе происходит обмен сообщениями/ задачами/ объектами/ элементами работы и т.д. В таких системах зачастую даются какие-либо гарантии относительно порядка передачи сообщений, и одна из самых распространенных гарантий — это FIFO. Вот его-то мы и препарируем.

В однопоточном окружении всё очень просто - у нас либо есть FIFO, либо нет FIFO совсем. Причин иметь какие-либо промежуточные варианты обычно практически нет. Однако в многопоточном окружении ситуация становится интереснее, т.к. промежуточные варианты могут иметь существенные последствия для производительности и/или масштабируемости. Итак, какие варианты есть в многопоточном окружении (в порядке убывания свойств, т.е. каждый последующий вариант есть подмножество предыдущего):

- полный FIFO, или причинно-следственный FIFO (causal FIFO)

- FIFO для каждого отдельного производителя (per-producer FIFO)

- почти FIFO (best-effort FIFO)

- отсутствие FIFO (no FIFO)

Остановимся на каждом варианте подробнее.

Causal FIFO.

Самое сильное из FIFO свойств, можно сказать "полный FIFO". Формально можно охарактеризовать следующим образом. Гарантируется FIFO порядок на основе happened-before [1, 2] отношения, т.е. если какое-то сообщение отослано раньше другого, то оно будет и потреблено раньше. Актуален этот вариант в основном в ситуации, когда есть только один потребитель, т.к. иначе этот вариант фактически деградирует до best-effort FIFO. В данном случае термин "раньше" накладывает частичный порядок на все сообщения, проходящие через очередь, а не только на сообщения одного производителя (как в варианте per-producer FIFO). Очевидно, что это свойство является надмножеством per-producer FIFO, т.к. для сообщений от одного производителя happened-before порядок согласуется с программным порядком. Реализовывать такую очередь можно двумя способами. Первый - при добавлении сообщения в очередь, поток захватывает некий мьютекс (либо выполняет атомарную RMW (Interlocked) операцию над некой ячейкой памяти), это обеспечивает автоматическое упорядочивание сообщений от нескольких производителей/потоков (из определения мьютекса). Достаточно очевидно (по крайней мере с практической т.з.), что такой порядок будет согласовываться с happened-before. Второй - сообщения не упорядочиваются при добавлении в очередь (допустим внутреннее очередь состоит из множества очередей, по одной для каждого производителя, либо на группу производителей), однако при извлечении сообщения потребитель "вручную" мультиплексирует внутренние очереди, и т.о. обеспечивает соответствие порядка happened-before (например, на основе векторных часов - vector clock [3], или Lamport timestamping [4]). Такая реализация может применяться и в нераспределенной системе, однако наиболее интересна для распределенных систем (где производить упорядочивание в момент добавления в очередь проблематично/невозможно).

В идеале, causal FIFO - это то, что всегда бы хотелось видеть конечному пользователю, однако это и самое "дорогое" свойство, т.к. наложение некого глобального порядка на распределенную систему (тут под распределенной системой я имею в виду и многоядерные процессоры в т.ч.) не может быть бесплатным. Именно поэтому, например, Erlang [5, 6] и не обеспечивает causal FIFO, а обеспечивает только per-producer FIFO (я думаю, что корни этого в том, что изначально Erlang предназначался для физически распределенных систем).

Per-producer FIFO.

Формально можно охарактеризовать следующим образом. Гарантируется FIFO порядок для каждой отдельной пары производитель-потребитель, т.е. если один производитель производит несколько сообщений, и их потребляет один потребитель, то потребитель потребит их именно в том порядке, в котором их произвёл производитель (тут опять же в основном имеет смысл рассматривать ситуацию с одним потребителем, т.к. иначе это свойство деградирует до best-effort FIFO). Гарантия per-producer FIFO целесообразна, когда (1) упорядочивание между производителями не требуется, или (2) система распределенная и упорядочивание между производителями выполнить сложно/невозможно, или (3) конечный пользователь готов мириться с отсутствием упорядочивания между производителями. Как плюс (по сравнению с применением causal-fifo) мы получаем более масштабируемую реализацию. Традиционный вариант реализации - очередь (multi-producer/single-consumer) внутреннее состоит из множества single-producer/single-consumer очередей (по одной на каждого производителя), производитель кладёт сообщения в свою очередь, потребитель "опрашивает" очереди в произвольном порядке (возможно, отдавая предпочтение той, из которой выбиралось сообщение в предыдущий раз). В распределенной системе это - фактически единственный вариант реализации; каждая single-producer/single-consumer очередь тут будет являться, например, TCP соединением.

Рассмотрим практический пример, где causal FIFO и per-producer FIFO различаются существенным образом. Допустим у нас есть агенты А, Б и В; агент А отсылает агенту Б сообщение 1; далее агент А отсылает сообщение 2 агенту В; далее агент В отсылает сообщение 3 агенту Б. При наличии гарантии causal FIFO агнет Б гарантированно получит сообщение 1 раньше сообщения 3 (сообщение 1 "happened-before" сообщения 3). При наличии только гарантии per-producer FIFO (например - Erlang), агент Б может получить сообщение 3 раньше сообщения 1 (т.к. они от разных производителей).

Best-effort FIFO.

Фактически это не FIFO совсем, т.к. никаких конкретных гарантий относительно порядка не предоставляется; "гарантируется" только что реализация будет "стараться" по-возможности обеспечивать FIFO. Однако это - интересная на практике гарантия по следующим причинам. Во-первых, иногда именно она и нужна; например, в контексте некого абстрактного веб-вервера/сервиса мы хотим, что бы запросы обрабатывались "примерно" в FIFO порядке (для обеспечения справедливой (fair) обработки), однако строгих гарантий не требуется, и, если реализация может быть более эффективной иначе, то нас это вполне устраивает. Во-вторых, более сильные FIFO гарантии (per-producer, causal) всё равно деградируют до best-effort в присутствии нескольких потребителей. В-третьих, best-effort FIFO действительно можно реализоваться более эффективно.

В качестве примера можно рассмотреть следующую ситуацию. Веб-сервис. Необходимо реализовать планировщик запросов, желателен некий FIFO-подобный порядок для обеспечения справедливой (fair) обработки. Традиционный подход обычно состоит в создании единой FIFO очереди запросов, защищённой мьютексом; новые запросы добавляются в хвост очереди; рабочие потоки по-необходимости извлекают запросы из головы очереди. Основной недостаток этого подхода - это излишняя централизация данных (а централизованные данные не могут быть масштабируемыми). Альтернативный подход, который пользуется знанием, что никакие конкретные гарантии FIFO нам не нужны, будет следующим. С каждым рабочим потоком ассоциирована single-producer/multi-consumer FIFO очередь запросов; при поступлении нового запроса рабочий поток кладёт его в хвост своей очереди; при необходимости взять следующий запрос для обработки поток берёт его из головы своей очереди, если она не пустая, или из головы очереди какого-либо другого потока иначе (work stealing). Такой дизайн обеспечивает справедливую обработку, т.е. любой запрос будет обработан в конечное время, однако структура полностью распределенная (читай - масштабируемая).

No FIFO.

Вариант отсутствия FIFO (например, LIFO) тоже интересен для рассмотрения, т.к. для некоторых ситуаций вообще не требуется справедливой (fair) обработки, а LIFO в такой ситуации может давать значительно лучшие показатели производительности, из-за лучшей локальности обработки (последний созданный элемент работы, читай - "горячий" в кэше, обрабатывается первым). Как пример можно привести распределенный аллокатор памяти [7] - каждый поток имеет приватный пул памяти, но требуется передача блоков/суперблоков памяти между потоками (приватными пулами). Для передачи блоков целесообразно рассмотреть использование очереди, обеспечивающей LIFO порядок; т.к. LIFO будет обеспечивать переиспользование наиболее "горячих" в кэше/памяти блоков.

Другой пример - планировщик "вычислительных" задач (например TBB, TPL, Cilk, когда предполагается, что объём работы конечен, а порядок не важен) [8]. Все такие системы используют преимущественно LIFO (опять же из-за лучшей локальности). Классическая схема реализации следующая. С каждым рабочим потоком связан дек (deque) задач (элементов работы). При создании новой задачи поток помещает его в голову своего дека; при поиске следующей задачи для выполнения поток вначале пытается взять задачу из головы своего дека, а если он пуст - берёт задачу из хвоста дека другого потока (work stealing [8]).

В принципе, улучшенная локальность одинакова полезна как для многопоточного окружения, так и для однопоточного (обход дерева в ширину vs обход дерева в глубину). Основная идея тут - что вначале надо определить, требуется ли вообще FIFO как таковое.

Вот, наверное, и всё. Как резюме можно сказать, что как и разработчику системы, так и конечному пользователю полезно различать оттенки FIFO. Разработчику — для выбора наиболее подходящей реализации и четкого отражения гарантий в документации, да и вообще для осмысленного выбора между ними (особенно это касается causal FIFO vs per-producer FIFO). Конечному пользователю — для того, что бы не делать необоснованных предположений относительно гарантий, предоставляемых системой.

[1] Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport. 1978. http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf

[2] Happened-before, http://en.wikipedia.org/wiki/Happened-before

[3] Vector clocks, http://en.wikipedia.org/wiki/Vector_clocks

[4] Lamport timestamps, http://en.wikipedia.org/wiki/Lamport_timestamps

[5] Erlang, http://erlang.org

[6] Erlang, http://en.wikipedia.org/wiki/Erlang_(programming_language)

[7] Streamflow, http://people.cs.vt.edu/~scschnei/streamflow/

[8] Scheduling Multithreaded Computations by Work Stealing. Robert D. Blumofe, Charles E. Leiserson. 1994. ftp://theory.lcs.mit.edu/pub/cilk/focs94.ps.Z