Skip to content

Latest commit

 

History

History
183 lines (113 loc) · 9.81 KB

queue.md

File metadata and controls

183 lines (113 loc) · 9.81 KB
title
Приоритетная очередь

Приоритетная очередь

TaskFlux работает с приоритетными очередями.

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

TaskFlux работает только с приоритетными очередями (пока не планируется использование обычных)

Создание очереди

При создании очереди нужно задавать параметры - необходимые и дополнительные.

Необходимые

Эти параметры обязательны для заполнения. Значения по умолчанию для них не предполагаются.

Название очереди

Название очереди : Название, которое будет использоваться для идентификации очереди

Этот параметр задает название очереди для работы с ней. Название должно быть уникальным и удовлетворять требованиям.

Реализация

Реализация : Указывает нижележащую структуру, которая используется для хранения записей очереди

На данный

Дополнительные

Дополнительные параметры указываются опционально. Они описывают поведение и некоторые ограничения при работе с очередью.

Максимальный размер очереди

Этот параметр указывает на максимальное количество элементов, которое может храниться в очереди.

Можно задавать любое количество от 0 до 2147483647 (оба включительно).

Если параметр не указан, то ограничение не выставляется — можно хранить любое количество.

Ограничения на диапазон ключей

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

Границы указываемого диапазона:

  • Должны быть допустимыми значениями ключа
  • Максимальное значение не может быть больше минимального
  • Указываются включительно

Таким образом, указываемый диапазон — это поддиапазон всех допустимых значений.

Примеры:

  • [1, 100] - от 1 до 100
  • [0, 3] - разрешены 0, 1, 2 и 3
  • [0, 0] - разрешен только приоритет 0
  • [-100, -1] - от -100 до -1
  • [100, -100] - невалидный диапазон - максимум меньше минимума

Стратегия сортировки

Этот параметр указывает на то, как учитываются ключи при чтении: берется запись с максимальным или минимальным ключом.

Если этот параметр не учитывается, то используется стратегия по умолчанию (по возрастанию, начиная с минимального ключа).

Можно указать 2 параметра:

  • По возрастанию - с минимального ключа
  • По убыванию - с максимального ключа

Максимальный размер сообщения

Этот параметр указывает максимальный размер тела сообщения - количества байт в сообщении.

Указываемое значение не может быть больше глобального ограничения на размер сообщения (указывается в конфигурации приложения, по умолчанию - 16Мб).

Концепции

В этой секции описаны основные структуры данных и понятия, с которыми ведется работа в приложении.

Приоритет

Приоритет : Ключ, который будет использоваться при чтении и записи в очередь

В качестве приоритета используются целые числа.

Допустимые значения от -9223372036854775808 до 9223372036854775807 (включительно).

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

Сообщение

Сообщение : Данные, которые хранятся в очереди, либо пользователь хочет записать

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

На размер сообщения может накладываться ограничение на размер:

  • Глобальный максимальный размер (указывается в конфигурации приложения)
  • Опциональный параметр при создании очереди

Запись

Запись : Ключ и значение вместе

Обозначение сообщения и связанного с ним приоритета.

Название очереди

Название очереди : Строка, идентифицирующая очередь

Название очереди представляется строкой из букв, цифр и специальных знаков:

  • Буквы: любые буквы английского алфавита верхнего и нижнего регистров: A-Z, a-z
  • Цифры: любые арабские цифры: 0-9
  • Специальные знаки:
    • Знаки препинания: ,, ., !, ?, ;, :
    • Скобки: {, }, (, ), [, ]
    • Математические символы: /, *, ^, &, -, <, >, =, +, %, |, ~
    • Кавычки: ``, ', "
    • Прочие специальные символы: \, #, $, @, \ , _

Остальные символы не допускаются.

Длина названия — от 0 до 255 символов.

Примечание: пробел и другие символы пустой строки не допускаются

Замечание: название очереди длины 0 (пустая строка) - название очереди по умолчанию. Поэтому названия пользовательских очередей должны быть длиной больше 0 (от 1 до 255).

Структуры для хранения

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

Основанная на куче

Код: H4

Эта реализация использует 4-арную кучу для хранения записей. Каждая запись состоит из 2 элементов:

  • Ключ, ассоциированный с записью
  • Очередь значений для хранения данных в порядке добавления

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

Дополнительно, используется кэш отображений ключа на соответствующую очередь

Список очередей

Код: QA

Эта реализация использует массив из списков. Индекс в массиве будет равняться соответствующему ключу. Для добавления в очередь новой записи в очередь по соответствующему индексу добавляется сообщение.

При использовании этого типа хранилища необходимо задать политику диапазона ключей