16 major breaking releases
|new 23.0.0||Mar 26, 2023|
|22.0.0||Mar 5, 2023|
|21.0.0||Feb 26, 2023|
|20.0.0||Feb 19, 2023|
#342 in Magic Beans
54 downloads per month
Auto-generated README.md for publishing to crates.io
Generalized Message Queue Pallet
Provides generalized message queuing and processing capabilities on a per-queue basis for arbitrary use-cases.
- Minimal assumptions about
MessageOrigins. Both should be MEL bounded blobs. This ensures the generality and reusability of the pallet.
- Well known and tightly limited pre-dispatch PoV weights, especially for message execution.
This is paramount for the success of the pallet since message execution is done in
on_initializewhich must never under-estimate its PoV weight. It also needs a frugal PoV footprint since PoV is scarce and this is (possibly) done in every block. This must also hold in the presence of unpredictable message size distributions.
- Usable as XCMP, DMP and UMP message/dispatch queue - possibly through adapter types.
The pallet has means to enqueue, store and process messages. This is implemented by having
queues which store enqueued messages and can be served to process said messages. A queue is
identified by its origin in the
BookStateFor. Each message has an origin which defines into
which queue it will be stored. Messages are stored by being appended to the last [
Page] of a
book. Each book keeps track of its pages by indexing
ReadyRing contains all
queues which hold at least one unprocessed message and are thereby ready to be serviced. The
ServiceHead indicates which ready queue is the next to be serviced.
The pallet implements [
frame_support::traits::ServiceQueues] and has [
OnQueueChanged] hooks to communicate with the outside world.
NOTE: The storage items are not linked since they are not public.
Executing a message is offloaded to the [
Config::MessageProcessor] which contains the actual
logic of how to handle the message since they are blobs. A message can be temporarily or
permanently overweight. The pallet will perpetually try to execute a temporarily overweight
message. A permanently overweight message is skipped and must be executed manually.
Queues are stored in a paged manner by splitting their messages into [
Page]s. This results
in a lot of complexity when implementing the pallet but is completely necessary to achieve the
second #Design Goal. The problem comes from the fact a message can possibly be
quite large, lets say 64KiB. This then results in a MEL of at least 64KiB which results in a
PoV of at least 64KiB. Now we have the assumption that most messages are much shorter than their
maximum allowed length. This would result in most messages having a pre-dispatch PoV size which
is much larger than their post-dispatch PoV size, possibly by a factor of thousand. Disregarding
this observation would cripple the processing power of the pallet since it cannot straighten out
this discrepancy at runtime. Conceptually, the implementation is packing as many messages into a
single bounded vec, as actually fit into the bounds. This reduces the wasted PoV.
Page Data Layout
A Page contains a heap which holds all its messages. The heap is built by concatenating
(ItemHeader, Message) pairs. The [
ItemHeader] contains the length of the message which is
needed for retrieving it. This layout allows for constant access time of the next message and
linear access time for any message in the page. The header must remain minimal to reduce its PoV
The pallet utilizes the [
sp_weights::WeightMeter] to manually track its consumption to always
stay within the required limit. This implies that the message processor hook can calculate the
weight of a message without executing it. This restricts the possible use-cases but is necessary
since the pallet runs in
on_initialize which has a hard weight limit. The weight meter is used
in a way that
check_accrue are always used to check the remaining weight of
an operation before committing to it. The process of exiting due to insufficient weight is
Scenario: Message enqueuing
m is enqueued for origin
o into queue
First the queue is either loaded if it exists or otherwise created with empty default values.
The message is then inserted to the queue by appended it into its last
Page or by creating a
Page just for
m if it does not fit in there. The number of messages in the
Q[o] is now ready which will eventually result in
m being processed.
Scenario: Message processing
The pallet runs each block in
on_initialize or when being manually called through
First it tries to "rotate" the
ReadyRing by one through advancing the
ServiceHead to the
next ready queue. It then starts to service this queue by servicing as many pages of it as
possible. Servicing a page means to execute as many message of it as possible. Each executed
message is marked as processed if the [
Config::MessageProcessor] return Ok. An event
Event::Processed] is emitted afterwards. It is possible that the weight limit of the pallet
will never allow a specific message to be executed. In this case it remains as unprocessed and
is skipped. This process stops if either there are no more messages in the queue or the
remaining weight became insufficient to service this queue. If there is enough weight it tries
to advance to the next ready queue and service it. This continues until there are no more
queues on which it can make progress or not enough weight to check that.
Scenario: Overweight execution
A permanently over-weight message which was skipped by the message processing will never be
executed automatically through
on_initialize nor by calling
Manual intervention in the form of
frame_support::traits::ServiceQueues::execute_overweight] is necessary. Overweight messages
emit an [
Event::OverweightEnqueued] event which can be used to extract the arguments for
manual execution. This only works on permanently overweight messages. There is no guarantee that
this will work since the message could be part of a stale page and be reaped before execution
Message: A blob of data into which the pallet has no introspection, defined as [
BoundedSlice<u8, MaxMessageLenOf<T>>]. The message length is limited by [
MaxMessageLenOf] which is calculated from [
Config::HeapSize] and [
MessageOrigin: A generic origin of a message, defined as [
MessageOriginOf]. The requirements for it are kept minimal to remain as generic as possible. The type is defined in [
Page: An array of
Messages, see [
Page]. Can never be empty.
Book: A list of
Pages, see [
BookState]. Can be empty.
Booktogether with an
MessageOriginwhich can be part of the
ReadyRing. Can be empty.
ReadyRing: A double-linked list which contains all ready
Queues. It chains together the queues via their
Queueis ready if it contains at least one
Messagewhich can be processed. Can be empty.
ServiceHead: A pointer into the
ReadyRingto the next
Queueto be serviced.
processed: A message is marked as processed after it was executed by the pallet. A message which was either: not yet executed or could not be executed remains as
unprocessedwhich is the default state for a message after being enqueued.
unknitting: The means of adding or removing a
MEL: The Max Encoded Length of a type, see [
Liveness - Enqueueing
It is always possible to enqueue any message for any
Liveness - Processing
on_initialize always respects its finite weight-limit.
Progress - Enqueueing
An enqueued message immediately becomes unprocessed and thereby eligible for execution.
Progress - Processing
The pallet will execute at least one unprocessed message per block, if there is any. Ensuring
this property needs careful consideration of the concrete weights, since it is possible that the
weight limit of
on_initialize never allows for the execution of even one message; trivially if
the limit is set to zero.
integrity_test can be used to ensure that this property holds.
Fairness - Enqueuing
Enqueueing a message for a specific
MessageOrigin does not influence the ability to enqueue a
message for the same of any other
MessageOrigin; guaranteed by Liveness - Enqueueing.
Fairness - Processing
The average amount of weight available for message processing is the same for each queue if the
number of queues is constant. Creating a new queue must therefore be, possibly economically,
expensive. Currently this is archived by having one queue per para-chain/thread, which keeps the
number of queues within
O(n) and should be "good enough".