[c++] как лучше реализовать таймаут ответа?
клади их в стэк ожидающих друг на друга
потом в отдельном трэде вычищай стэк
потом в отдельном трэде вычищай стэк
можно сделать вокруг std::map класс. который кладет и вытаскивает ID + timeout
при обращении в нему в некоторые моменты времени иницировать процедуру подчистки expired ID, например, каждую минуту
в этом случае доп поток не нужен, но это отразится на времени вставки\удаления элемента в map
при обращении в нему в некоторые моменты времени иницировать процедуру подчистки expired ID, например, каждую минуту
в этом случае доп поток не нужен, но это отразится на времени вставки\удаления элемента в map
но это отразится на времени вставки\удаления элемента в mapвот это крайне нежелательно
вернее нежелательно задерживать отсылку-получение пакета, ибо будут терятся если делать что-то долгое.
вот это крайне нежелательнону при доп потоке такой же эффект возможен
нельзя ли зафиксировать таймаут для ID? ну или хотя бы максимум зафиксировать. в этом случае их можно держать в отсортированном виде, удаление будет шустрее работать
опять же желательно ускорять после профилирования
вернее нежелательно задерживать отсылку-получение пакетаможно дергать явную подчистку в другие моменты, по каким-то событиям. не обязательно при получении\вставки. зависит от проги
Как насчет функций signal и alarm?
Ещё можно без затей заюзать произвольный eventloop и таймер.
Интересно, но использование signal смущает, там вроде как обработчик нереентерабельно вызывается и кроме того задержка в секундах это слишком грубо что ли. Мне тогда проще раз в секунду из отдельного треда прочищать.
Можно держать коллекцию запросов, сортированную по времени.
Каждый раз при добавлении запроса вычищать устаревшие.
по идее set должен подойти (если это то же самое, что TreeSet в жабе).
Небольшая утечка будет, Но максимум - просранные запросы за время ожидания.
Каждый раз при добавлении запроса вычищать устаревшие.
по идее set должен подойти (если это то же самое, что TreeSet в жабе).
Небольшая утечка будет, Но максимум - просранные запросы за время ожидания.
так как запросы отправлены в разное время, нужно коллекцию сортировать не по времени ожидания а по разности между текущим временем и временем отправки и сравнивать ее с таймаутом, который хранить рядом.
в сете и мапе это не очень удобно потому что ключ - разность времени текущего и ожидания - нужно регулярно уменьшать, а там ключ вроде как ридонли. получается нужно выдергивать (стирать) из сета (внутри которого красно-черное дерево вроде) элемент, уменьшать у элемента время, сравнивать с интервалом, если истекло - выкидывать, иначе вставлять обратно в сет и переходить к следующему элементу. весь этот алгоритм оставляет ощущение черезжопности.
в сете и мапе это не очень удобно потому что ключ - разность времени текущего и ожидания - нужно регулярно уменьшать, а там ключ вроде как ридонли. получается нужно выдергивать (стирать) из сета (внутри которого красно-черное дерево вроде) элемент, уменьшать у элемента время, сравнивать с интервалом, если истекло - выкидывать, иначе вставлять обратно в сет и переходить к следующему элементу. весь этот алгоритм оставляет ощущение черезжопности.
короче в идеале хотелось бы некий примитив синхронизации(? которому взводятся таймауты (больше одной штуки а он при их достижении разблокируется а-ля условная переменная или вызывает пользовательский обработчик, при этом еще было бы хорошо знать какой именно таймаут истек, ну то есть назначать им пользовательский ID.
видимо, дополнительного треда не избежать.
видимо, дополнительного треда не избежать.
трэд не читал. для этого используют eventloop с таймерами. например libev
не тормози, в качестве ключа надо просто брать время, когда таймаут истекает. тогда (в случае жабки, конечно же) код очистки того, для чего таймаут уже наступил будет выглядеть наипримитивнейше
eventMap.headMap(System.currentTimeMillis.clear
так как запросы отправлены в разное время, нужно коллекцию сортировать не по времени ожидания а по разности между текущим временем и временем отправки и сравнивать ее с таймаутом, который хранить рядом.в сете и мапе это не очень удобно потому что ключ - разность времени текущего и ожидания - нужно регулярно уменьшать, а там ключ вроде как ридонли. получается нужно выдергивать (стирать) из сета (внутри которого красно-черное дерево вроде) элемент, уменьшать у элемента время, сравнивать с интервалом, если истекло - выкидывать, иначе вставлять обратно в сет и переходить к следующему элементу. весь этот алгоритм оставляет ощущение черезжопности.Есть же дофига библиотек, в которых всё уже давно сделано умными людьми. Используй их, или покопай исходники и выковыряй нужное. Я вот когда-то asio смотрел, там есть timer_queue, сделанный на куче.
Надо сортировать по expitationTime. Ничего менять не нужно.
[ismolnik] С, плюс тебе, плюс . [/ismolnik]
Падажжи блджад.
Тебе чо нужно-то? Эффективная структура данных которая позволяет а) доставать хуету по любому из двух ключей, б) удалять хуиту по каждому из ключей, да?
Ну вот как я понимаю std::map в том числе позволяет получить айтем с минимальным ключом. Поэтому делаешь две map, одна по id, вторая по expiry, у первой value это expiry + shared_ptr на запрос, у второй — id + shared_ptr (именно в таком порядке! Ну или у тебя айтем в себе хранит и id, и expiry, тогда у обеих валью это shared_ptr<Item>); всё это обёрнуто в фигню которая получает id, expiry, const shared_ptr<Item>&, добавляет в обе мапы и сразу же шерстит ту мапу, которая по expiry, на предмет ключей которые меньше текушего времени, и выкидывает их из обеих мап.
Три проблемы:
во-первых, тебе нужно уникальное expiry, ну, можешь тупо прибавлять 1 пока шняга с таким временем есть в той мапе. Можешь ещё разрешение по времени увеличить, в смысле, если ты получаешь время в миллисекундах, используй ключ типа time << 5. multimap будет сосать кстати, поскольку тебе придётся перебирать значения экспайри не только для вставления, но и для удаления. Ну или сделай её map<Expiry, map<Id, shared_ptr<Item> >, например — это лучше в теории, но может больше тормозить на практике если у тебя коллизии по времени всё же редкие. Или сделай гибридную, храни айтемы с одинаковым экспайри в одном элементе, потом в векторе, потом в мапе (и всё это — юнион с селектором, чтобы лишней памяти не жрать).
Во-вторых, хотя std::map и имплементирована как rbtree и по идее её front должен выдавать значение с минимальным ключом, это вроде бы не требуется стандартом (я попробовал поискать в нём, хуй проссышь! поэтому может быть лучше использовать что-то что явно даёт эти гарантии, хотя бы попиздить std::map из сурцов своего компилятора, убедиться что она работает как нужно, и переименовать в strictly_ordered_map (имей в виду, что многочисленные долбоёбы почему-то под ordered map понимают map которая preserves the order of insertions).
А потом ты можешь вдобавок к удалению экспайрнутых айтемов каждый раз (или каждый энтый раз, или каждый раз но не чаще чем раз в секунду) когда ты вставляешь ключ, добавить лок и удалять их из отдельного треда раз в секунду, хотя нафига это тебе может быть нужно — не очень понятно. Разве что латенси уменьшить, типа, когда у тебя 10к айтемов, потом приходит запрос и ему вдруг нужно удалить все 10к айтемов разом, перед тем как сможет обработаться следующий запрос.
Тебе чо нужно-то? Эффективная структура данных которая позволяет а) доставать хуету по любому из двух ключей, б) удалять хуиту по каждому из ключей, да?
Ну вот как я понимаю std::map в том числе позволяет получить айтем с минимальным ключом. Поэтому делаешь две map, одна по id, вторая по expiry, у первой value это expiry + shared_ptr на запрос, у второй — id + shared_ptr (именно в таком порядке! Ну или у тебя айтем в себе хранит и id, и expiry, тогда у обеих валью это shared_ptr<Item>); всё это обёрнуто в фигню которая получает id, expiry, const shared_ptr<Item>&, добавляет в обе мапы и сразу же шерстит ту мапу, которая по expiry, на предмет ключей которые меньше текушего времени, и выкидывает их из обеих мап.
Три проблемы:
во-первых, тебе нужно уникальное expiry, ну, можешь тупо прибавлять 1 пока шняга с таким временем есть в той мапе. Можешь ещё разрешение по времени увеличить, в смысле, если ты получаешь время в миллисекундах, используй ключ типа time << 5. multimap будет сосать кстати, поскольку тебе придётся перебирать значения экспайри не только для вставления, но и для удаления. Ну или сделай её map<Expiry, map<Id, shared_ptr<Item> >, например — это лучше в теории, но может больше тормозить на практике если у тебя коллизии по времени всё же редкие. Или сделай гибридную, храни айтемы с одинаковым экспайри в одном элементе, потом в векторе, потом в мапе (и всё это — юнион с селектором, чтобы лишней памяти не жрать).
Во-вторых, хотя std::map и имплементирована как rbtree и по идее её front должен выдавать значение с минимальным ключом, это вроде бы не требуется стандартом (я попробовал поискать в нём, хуй проссышь! поэтому может быть лучше использовать что-то что явно даёт эти гарантии, хотя бы попиздить std::map из сурцов своего компилятора, убедиться что она работает как нужно, и переименовать в strictly_ordered_map (имей в виду, что многочисленные долбоёбы почему-то под ordered map понимают map которая preserves the order of insertions).
А потом ты можешь вдобавок к удалению экспайрнутых айтемов каждый раз (или каждый энтый раз, или каждый раз но не чаще чем раз в секунду) когда ты вставляешь ключ, добавить лок и удалять их из отдельного треда раз в секунду, хотя нафига это тебе может быть нужно — не очень понятно. Разве что латенси уменьшить, типа, когда у тебя 10к айтемов, потом приходит запрос и ему вдруг нужно удалить все 10к айтемов разом, перед тем как сможет обработаться следующий запрос.
это все для опроса snmp, может быть сеть с тысячей устройств, у каждого порядка сотен oid которые нужно запрашивать с разной степенью регулярности - скажем раз в 5 минут. в результате имеем ~3*100к запросов за 5 минут, т.е. 1000 запросов в секунду, (на самом деле меньше потому что в 1 запрос можно запихать несколько oid'ов). соответственно если не ставить таймаут, то запросы на которые я не дождался ответа (udp же будут накапливаться и будут утекать мою память.
Это ты к чему? Я вроде понятно объяснил... Вот такая структура данных которая внутри себя держит map<Id, shared_ptr<Request>>, map<Expiry, shared_ptr<Request>> (assuming that Request contains both Id and Expiry) позволяет с одной стороны быстро выкинуть из себя обработанный реквест, с другой — быстро найти все реквесты с Expiry меньше текущего времени и выкинуть их.
Если у тебя новые реквесты приходят часто, то выполняй шаг "выкинуть все реквесты с expiry < now" каждый раз при добавлении очередного реквеста и не парься.
Если у тебя новые реквесты приходят часто, то выполняй шаг "выкинуть все реквесты с expiry < now" каждый раз при добавлении очередного реквеста и не парься.
а) доставать хуету по любому из двух ключей, б) удалять хуиту по каждому из ключей, да?1. доставать и удалять по ключу
2. массово удалять записи с ключем меньше данного (при условии, что ключ монотонно растет)
ps
кстати можно просто использовать три std:map-а, циклически сдвигая их раз в timeout/2-время, при этом ключ ищется по последним двум, и при переключении самый старый из трех чистится, вставка идет в самый новый
при такой схеме, быстрее может даже будет помечать ключ как удаленный, и вместо map-ов использовать массивы
Ептить, 1000 в секунду - это смехотворное количество, даже если раз в секунду чистить. У нас с такой мега задачей справляются интерпретируемые языки.
здесь весь вопрос был не в высокой нагрузке, а в том, чтобы сделать алгоритм очистки не через жопу и не сжигать 100% одного ядра на этой в общем-то не слишком тяжелой задаче. и еще я надеялся обойтись без поллинга, но видимо без этого тут никуда.
1) что-то много слов, проще так: boost::multi_index
2) стандарт гарантирует сортированность [begin, end) по ключу для std::map
3) у std::map нет метода front
2) стандарт гарантирует сортированность [begin, end) по ключу для std::map
3) у std::map нет метода front
Есть в нашей с Бачаном копилке coda кое-что очень похожее, почти-почти. По крайней мере суть будет ясна и ты алгоритм удаления устаревшего поправишь.
http://github.com/bachan/coda
смотри файлик cache.hpp, там есть шаблонный класс coda_cache. Это фактически std::map<K, V>, в котором есть лимит на число элементов. Там есть два осмысленных метода acquire и release, и фишка acquire в том, что если у тебя в контейнере N элементов, и у тебя лимит равен N, то выдеяя N+1 делается удаление самого древнего элемента.
Таким образом у тебя всегда в контейнере не более N штук в мапке.
Что касается твоей задачи, лимит ты получишь, отдельный тред создавать не надо, блокировок тоже нет и не будет. Круто же! Главное число N подобрать такое, чтобы заведомо всегда хватало. Но если будет перебор, то переливаться через край начнёт.
http://github.com/bachan/coda
смотри файлик cache.hpp, там есть шаблонный класс coda_cache. Это фактически std::map<K, V>, в котором есть лимит на число элементов. Там есть два осмысленных метода acquire и release, и фишка acquire в том, что если у тебя в контейнере N элементов, и у тебя лимит равен N, то выдеяя N+1 делается удаление самого древнего элемента.
Таким образом у тебя всегда в контейнере не более N штук в мапке.
Что касается твоей задачи, лимит ты получишь, отдельный тред создавать не надо, блокировок тоже нет и не будет. Круто же! Главное число N подобрать такое, чтобы заведомо всегда хватало. Но если будет перебор, то переливаться через край начнёт.
Да, лимит задаётся в конструкторе, но это вроде очевидно.
Ты можешь переписать этот класс совсем просто и сделать условием удаления не число элементов, а истечение таймаута.
Ты можешь переписать этот класс совсем просто и сделать условием удаления не число элементов, а истечение таймаута.
без поллинга не обойтись
главное число N подобратьЖуть какая...
Для хранения запросов тебе нужна структура, которая позволяет а) находить запрос по ID б) находить запрос с минимальным expire. Тут уже несколько вариантов насоветовали. На крайний случай для 1000 запросов и массив сойдет.
Еще понадобится таймер.
При добавлении запроса, если таймер еще не взведен, он взводится на expire этого запроса.
При срабатывании таймера удаляются истекшие запросы, если они есть. Если еще остались запросы, на которые не пришел ответ - таймер взводится снова.
Оптимизации работы с таймером:
1. Взводить на expire + Delta, чтобы не дергать таймер слишком часто и чтобы обрабатывать по несколько таймаутов за один раз. Delta берется из соображений, на сколько ты можешь отложить обработку таймаута запроса после того, как таймаут случился.
2. Если после удаления ближайший таймаут оказался больше таймера - переставляем таймер.
И да, подобные штуки уже давно есть запроганные. Тут уже выше советовали.
И да, подобные штуки уже давно есть запроганные. Тут уже выше советовали.Не, я не отрицаю.
Просто как один из вариантов предложил, вдруг задача больше в эту сторону...
смотри файлик cache.hppпредположу, что это lru-cache. у ТС вроде другая задача
Оставить комментарий
elenangel
Я посылаю udp запрос, внутри него есть некий 32-битный идентификатор запроса ID. Мне в ответ должен прийти пакет с тем же идентификатором ID, но может и не прийти вообще. Соответственно я в программе где-то помню ID, допустим в std::map. Как лучше сделать так, чтобы после истечения определенного времени программа забывала про ID?Вариант в лоб - запоминать время отправки рядом с ID и в отдельном треде крутиться и просматривать все времена всех ID'ов и когда найдено истекшее время стирать ID мне не нравится, хочется вместо polling как-то организовать что-то вроде interrupt.
Запросов может быть до нескольких тысяч одновременно, времена ожидания - от единиц миллисекунд до единиц секунд.