Очередь приоритетов, которая позволяет эффективно обновлять приоритеты?

Question

ОБНОВЛЕНИЕ : Вот моя реализация Hashed Timing Wheels . Пожалуйста, дайте мне знать, если у вас есть идея улучшить производительность и параллелизм. (20-Jan-2009)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

ОБНОВЛЕНИЕ : я решил эту проблему, используя Иерархические и хэшированные временные колеса . (19-Jan-2009)

Я пытаюсь реализовать таймер специального назначения в Java, оптимизированный для обработки тайм-аута. Например, пользователь может зарегистрировать задачу с мертвой линией, а таймер может уведомить метод обратного вызова пользователя, когда мертвая линия окончена. В большинстве случаев зарегистрированное задание будет выполнено в течение очень короткого промежутка времени, поэтому большинство заданий будет отменено (например, task.cancel ()) или перенесено на будущее (например, task.rescheduleToLater (1, TimeUnit.SECOND)) .

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

Я не могу использовать java.util.Timer или java.util.concurrent.ScheduledThreadPoolExecutor, потому что они предполагают, что для большинства задач истекло время ожидания. Если задача отменяется, отмененная задача сохраняется в ее внутренней куче до тех пор, пока не будет вызван ScheduledThreadPoolExecutor.purge (), и это очень дорогая операция. (O (NlogN) возможно?)

В традиционных кучах или очередях с приоритетами, которые я изучил в моих классах CS, обновление приоритета элемента во многих случаях было дорогостоящей операцией (O (logN)), потому что этого можно добиться только путем удаления элемента и повторной вставки это с новым значением приоритета. В некоторых кучах, таких как куча Фибоначчи, есть O (1) время операции lowerKey () и min (), но по крайней мере мне нужно быстрое увеличение KK () и min () (или KK () ()).

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

Answer 1

Как насчет того, чтобы попытаться отделить обработку обычного случая, когда все быстро завершается, от случаев ошибки?

Используйте как хеш-таблицу, так и очередь с приоритетами. Когда задача запускается, она помещается в хеш-таблицу, а если она быстро завершается, она удаляется за O (1).

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

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

Там параметры намного сложнее, чем просто использование очереди с приоритетами, но их довольно легко реализовать, они должны быть стабильными.

Answer 2

Насколько мне известно (я написал статью о новой очереди приоритетов, в которой также были рассмотрены прошлые результаты), ни одна реализация очереди приоритетов не получает границ кучи Фибоначчи, а также ключ увеличения в постоянном времени.

Есть небольшая проблема с получением этого буквально. Если бы вы могли получить ключ увеличения в O (1), то вы могли бы получить удаление в O (1) - просто увеличьте ключ до + бесконечности (вы можете обработать очередь, заполненную множеством + бесконечностей, используя некоторые стандартные приемы амортизации ). Но если find-min также равен O (1), это означает, что delete-min = find-min + delete становится O (1). Это невозможно в очереди приоритетов на основе сравнения, потому что граница сортировки подразумевает (вставьте все, затем удалите одну за другой), что

n * insert + n * delete-min> n log n.

Смысл в том, что если вы хотите, чтобы очередь приоритетов поддерживала клавишу увеличения в O (1), вы должны принять одно из следующих штрафов:

• Не на основе сравнения. На самом деле, это довольно хороший способ обойти вещи, например, деревья vEB .
• Примите O (log n) для вставок, а также O (n log n) для make-heap (учитывая n начальных значений). Это отстой.
• Примите O (log n) для find-min. Это вполне приемлемо, если вы никогда не наберете do find-min (без сопутствующего удаления).

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

Answer 3

Используйте Хэшированное колесо синхронизации - Google 'Хэшированные иерархические колеса синхронизации' для получения дополнительной информации. Это обобщение ответов, сделанных людьми здесь. Я бы предпочел хешированное колесо ГРМ с большим размером колеса, чем иерархическое колесо ГРМ.

Answer 4

Некоторая комбинация хешей и O (logN) структур должна делать то, что вы просите.

У меня возникает соблазн поспорить с тем, как вы анализируете проблему. В своем комментарии выше вы говорите

Потому что обновление будет происходить очень и очень часто. Допустим, мы отправляем M сообщений на соединение, тогда общее время становится O (MNlogN), что довольно много. - Trustin Lee (6 часов назад)

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

Так что, если в вашем приложении одновременно открыт миллиард сокетов (это действительно вероятно?), Стоимость вставки составляет всего около 60 сравнений на сообщение.

Держу пари, что это преждевременная оптимизация: вы фактически не измерили узкие места в вашей системе с помощью инструмента анализа производительности, такого как CodeAnalyst или VTune.

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

Одна из возможностей - разделить домен сокетов N на некоторое количество сегментов размера B, а затем хэшировать каждый сокет в одно из этих (N / B) сегментов. В этом сегменте находится куча (или что-то еще) со временем обновления O (log B). Если верхняя граница N не установлена ​​заранее, но может варьироваться, то вы можете динамически создавать больше сегментов, что добавляет небольшие сложности, но, безусловно, выполнимо.

В худшем случае сторожевой таймер должен искать (N / B) очереди на предмет истечения, но я предполагаю, что сторожевой таймер не требуется для уничтожения незанятых сокетов в любом конкретном порядке! То есть, если в последнем интервале времени 10 сокетов простаивали, ему не нужно искать в этом домене тот, который истек первый тайм-аут, иметь дело с ним, затем находить тот, который истек второй тайм-аут и т. Д. должен просканировать (N / B) набор сегментов и перечислить все тайм-ауты.

Если вас не устраивает линейный массив сегментов, вы можете использовать приоритетную очередь очередей, но вы хотите избежать обновления этой очереди в каждом сообщении, иначе вы вернетесь туда, откуда начали. Вместо этого определите время, которое меньше фактического времени ожидания. (Скажем, 3/4 или 7/8 от этого), и вы помещаете очередь низкого уровня в очередь высокого уровня только в том случае, если ее наибольшее время превышает это значение.

И, рискуя указать очевидное, вы не хотите, чтобы ваши очереди включались в истекшее время. Ключи должны быть время начала . Для каждой записи в очереди истекшее время должно постоянно обновляться, но время начала каждой записи не меняется.

Answer 5

Существует ОЧЕНЬ простой способ сделать все вставки и удаления в O (1), используя тот факт, что 1) приоритет основан на времени и 2) у вас, вероятно, есть небольшое фиксированное количество длительностей тайм-аута.

1. Создайте обычную очередь FIFO для удержания всех задач с таймаутом в течение 10 секунд. Поскольку все задачи имеют одинаковую продолжительность тайм-аута, вы можете просто вставить в конец и удалить из начала, чтобы сохранить сортировку очереди.
2. Создайте еще одну очередь FIFO для задач с продолжительностью тайм-аута 30 секунд. Создайте больше очередей для других периодов ожидания.
3. Для отмены удалите элемент из очереди. Это O (1), если очередь реализована в виде связанного списка.
4. Перепланирование может быть выполнено как отмена-вставка, так как обе операции O (1). Обратите внимание, что задачи могут быть перенесены в разные очереди.
5. Наконец, чтобы объединить все очереди FIFO в одну очередь с общим приоритетом, пусть заголовок каждой очереди FIFO участвует в обычной куче. Главой этой кучи будет задача с самым быстрым истечением времени ожидания из ВСЕХ задач.

Если у вас есть m различных длительностей тайм-аута, сложность для каждой операции всей структуры составляет O (log m). Вставка - O (log m) из-за необходимости искать, в какую очередь вставлять. Remove-min - это O (log m) для восстановления кучи. Отмена - это O (1), но в худшем случае O (log m), если вы отменяете заголовок очереди. Поскольку m - это небольшое фиксированное число, O (log m) по существу равно O (1). Не масштабируется с количеством задач.

Answer 6

Ваш конкретный сценарий предлагает мне круговой буфер. Если макс. Тайм-аут составляет 30 секунд, и мы хотим собирать сокеты, по крайней мере, каждую десятую секунды, а затем использовать буфер из 300 двусвязных списков, по одному на каждую десятую секунды в этом периоде. Чтобы «увеличить» время для записи, удалите ее из списка, в котором она находится, и добавьте его к списку для нового десятого секунды (обе операции в постоянном времени). Когда период заканчивается, пожните все, что осталось в текущем списке (возможно, передав его в поток жнеца) и продвиньте указатель текущего списка.

Answer 7

Я думаю, что было бы лучше сохранить все задачи в списке и выполнить их итерацию.

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

Answer 8

Есть ли веская причина не использовать java.lang.PriorityQueue? Не обрабатывает ли remove () ваши операции отмены за время log (N)? Затем реализуйте собственное ожидание, основываясь на времени, пока элемент находится в начале очереди.

Answer 9

У вас есть жесткое ограничение на количество элементов в очереди - есть ограничение для сокетов TCP.

Поэтому проблема ограничена. Я подозреваю, что любая умная структура данных будет медленнее, чем использование встроенных типов.