понедельник, 16 июля 2018 г.

[prog.c++] Довелось столкнуться со странной структурой данных: и очередь, и multimap.

В рамках следующей итерации над демо-проектом Shrimp постарались закрыть несколько "косяков" самой первой, простейшей версии Shrimp-а. В частности, в простейшей версии Shrimp-а были возможны ситуации, когда пришедшие практически одновременно одинаковые запросы шли в параллельную обработку. Т.е., если мы получаем запрос "demo.jpg?op=resize&max=1024" и следом еще один такой же, то операция трансформации картинки demo.jpg к размеру 1024px могла быть запущена дважды.

Происходило это потому, что Shrimp проверял наличие уже трансформированной картинки в своем кэше. Если ее в кэше нет, то при наличии свободных worker-ов запрос сразу же шел в обработку. Получили запрос для demo.jpg, увидели, что в кэше результата нет, отдали на трансформацию. Результат трансформации еще не пришел, а у нас уже еще один запрос для demo.jpg. Поскольку трансформированной картинки в кэше, ожидаемо, нет, то отдаем запрос на обработку. И получаем, что одна и так же картинка трансформируется параллельно несколькими воркерами. Что не есть хорошо.

Понятное дело, что для самой первой, самой простейшей версии Shrimp-а не было смысла делать контроль уникальности запросов. Но вот добавить подобный контроль в последующих версиях нужно было. Работы тут не так много, а солидности демо-проекту добавляет :)

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

С другой же стороны, нужно иметь возможность эффективно проверить наличие конкретного ключа в контейнере. И, сюда же, нужно иметь возможность изъять из очереди сразу все элементы с одинаковым ключом. Нужно это в случае, когда освободился worker и мы берем самый старый элемент из очереди. Но, если ключ этого элемента не уникален (т.е. есть более свежие запросы с тем же ключом), то оставлять в очереди другие аналогичные элементы нет смысла. Ведь когда картинка будет трансформирована, то ее можно будет отдать сразу всем этим запросам.

Предположим, что мы добавляем элементы в такой контейнер в следующем порядке: [k1:v1], [k2:v2], [k1:v3], [k3:v4], [k2:v5], [k1:v6]. Где k(i) -- это ключ (который может повторяться), а v(j) -- это значение, которое мы рассматриваем как уникальное.

Для того, чтобы было лучше понятно: ключ применительно к Shrimp-у -- это URL вида "demo.jpg?op=resize&max=1024". А значением -- экземпляр restinio::http_request_t, через который можно работать с HTTP-запросом. Так, если мы получаем запросы "demo.jpg?op=resize&max=1024", "demo.jpg?op=resize&max=2048" и "demo.jpg?op=resize&max=1024", то у нас будет три разных экземпляра http_request (соответственно и три разных значения), но только два уникальных ключа: "demo.jpg?op=resize&max=1024" и "demo.jpg?op=resize&max=2048".

Если мы посмотрим на контейнер как на очередь с сохранением хронологического порядка, то должны увидеть следующее:

[k1:v1] [k2:v2] [k1:v3] [k3:v4] [k2:v5] [k1:v6]

В то же время, если мы посмотрим на контейнер как на индексированную структуру (т.е. как на multimap), то мы должны увидеть следующее:

[k1:v1, v3, v6] [k2:v2, v5] [k3:v4]

Соответственно, если мы удаляем из контейнера два самых старых элемента из-за того, что время их ожидания превышено (а это [k1:v1] и [k2:v2]), то у нас должно остаться в виде очереди:

[k1:v3] [k3:v4] [k2:v5] [k1:v6]

или в виде multimap:

[k1:v3, v6] [k2:v5] [k3:v4]

Если теперь мы берем самый старый элемент из очереди на обработку, а это элемент [k1:v3], то из контейнера мы должны изъять и все другие элементы, которые имеют ключ k1. В результате наш контейнер должен принять вид:

[k3:v4] [k2:v5]

или в виде multimap:

[k2:v5] [k3:v4]

Признаюсь, в структурах данных я не особо силен, поэтому такой контейнер для Shrimp-а был навелосипеден на коленке с использованием std::multimap и std::list внутри. Именно std::multimap/std::list использовались потому, что в них итераторы не инвалидируются при модификации контейнеров. Что делает возможным безопасные ссылки из std::multimap в std::list и обратно.

Самым сложным в этом деле оказалось выбрать название для такого контейнера. В результате нескольких подходов было выбрано имя key_multivalue_queue_t. Не фонтан, но хоть как-то отражает то, чем этот контейнер должен являться.

Если кому-то интересно, то текущую реализацию (пожалуй, самую тривиальную из возможных) можно увидеть на bitbucket-е.


На данный момент есть ощущение, что следующая достойная публичного обсуждения версия Shrimp-а, уже полностью готова. Мы закрыли проблему контроля уникальности ждущих запросов, добавили логирование посредством отличной современной C++ной библиотеки spdlog и еще кое-что по мелочи. Опишем все это в статье для Хабра. Надеюсь, к концу недели все это опубликуем.

Потом у нас запланирована еще одна итерация вокруг Shrimp-а. В частности, есть желание прикрутить еще и преобразование изображения из одного формата в другой при трансформации. Скажем, картинка была в jpg, в ответ на конкретный запрос отдали ее в webp. Если у кого-то есть еще хотелки, то не стесняемся, набрасываем. Сделать, понятное дело, не обещаем. Но вдруг ;)


Напоследок отмечу забавный момент в новой реализации Shrimp-а.

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

Дело в том, что изначально хотелось контролировать время жизни и для тех запросов, которые уже пошли в обработку. Действительно, если запрос ждал worker-а 29 секунд, дождался все-таки worker-а, но сама обработка заняла еще 5 секунд, тогда как ограничение на всю обработку запроса 30 секунд, то логично было бы ответить ошибкой клиенту. Поэтому для m_inprogress_requests был выбран key_multivalue_queue_t для того, чтобы можно быть проверять самые старые элементы. Но уже во время реализации обнаружился интересный сценарий: из m_inprogress_requests выбросили все элементы, относящиеся к конкретному запросу. И тут приходит новый запрос для той же самой картинки. Оказывается, что картинка в данный момент в обработке, но ее описания нет ни в кэше уже трансформированных картинок, ни в m_pending_requests, ни в m_inprogress_requests. И как тут быть?

В принципе, нормальный выход был бы в том, чтобы для m_inprogress_requests иметь такой контейнер, который бы позволял хранить ключи без значений. Т.е. еще более извращенный вариант key_multivalue_queue_t. Но уходить в такие дебри ради демо-проекта просто не имеет смысла. Поэтому сейчас если уж запрос перешел из m_pending_requests в m_inprogress_requests, то время жизни для него уже не контролируется.

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

Комментариев нет: