44 releases (major breaking)
41.0.1 | Oct 29, 2024 |
---|---|
40.0.1 | Nov 7, 2024 |
40.0.0 | Jul 18, 2024 |
39.0.1 | Oct 31, 2024 |
0.0.0 | Dec 8, 2022 |
#897 in Magic Beans
8,678 downloads per month
Used in 87 crates
(42 directly)
3MB
53K
SLoC
Release
Polkadot SDK stable2409
lib.rs
:
Generalized Message Queue Pallet
Provides generalized message queuing and processing capabilities on a per-queue basis for arbitrary use-cases.
Design Goals
- Minimal assumptions about
Message
s andMessageOrigin
s. 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_initialize
which 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.
Design
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 Pages
. The 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::EnqueueMessage
,
frame_support::traits::ServiceQueues
and has frame_support::traits::ProcessMessage
and
OnQueueChanged
hooks to communicate with the outside world.
NOTE: The storage items are not linked since they are not public.
Message Execution
Executing a message is offloaded to the Config::MessageProcessor
which contains the actual
logic of how to handle the message since they are blobs. Storage changes are not rolled back on
error.
A failed 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.
Reentrancy
This pallet has two entry points for executing (possibly recursive) logic;
Pallet::service_queues
and Pallet::execute_overweight
. Both entry points are guarded by
the same mutex to error on reentrancy. The only functions that are explicitly allowed to be
called by a message processor are: Pallet::enqueue_message
and
Pallet::enqueue_messages
. All other functions are forbidden and error with
Error::RecursiveDisallowed
.
Pagination
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
impact.
Weight Metering
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 can_accrue
and 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
termed "bailing".
Scenario: Message enqueuing
A message m
is enqueued for origin o
into queue Q[o]
through
frame_support::traits::EnqueueMessage::enqueue_message
(m, o)
.
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
new Page
just for m
if it does not fit in there. The number of messages in the Book
is
incremented.
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
frame_support::traits::ServiceQueues::service_queues
.
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
frame_support::traits::ServiceQueues::service_queues
.
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
commences.
Terminology
Message
: A blob of data into which the pallet has no introspection, defined as [BoundedSlice<u8, MaxMessageLenOf<T>>
]. The message length is limited byMaxMessageLenOf
which is calculated fromConfig::HeapSize
and [ItemHeader::max_encoded_len()
].MessageOrigin
: A generic origin of a message, defined asMessageOriginOf
. The requirements for it are kept minimal to remain as generic as possible. The type is defined inframe_support::traits::ProcessMessage::Origin
.Page
: An array ofMessage
s, seePage
. Can never be empty.Book
: A list ofPage
s, seeBookState
. Can be empty.Queue
: ABook
together with anMessageOrigin
which can be part of theReadyRing
. Can be empty.ReadyRing
: A double-linked list which contains all readyQueue
s. It chains together the queues via theirready_neighbours
fields. AQueue
is ready if it contains at least oneMessage
which can be processed. Can be empty.ServiceHead
: A pointer into theReadyRing
to the nextQueue
to be serviced.- (
un
)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 asunprocessed
which is the default state for a message after being enqueued. knitting
/unknitting
: The means of adding or removing aQueue
from theReadyRing
.MEL
: The Max Encoded Length of a type, seecodec::MaxEncodedLen
.Reentrance
: To enter an execution context again before it has completed.
Properties
Liveness - Enqueueing
It is always possible to enqueue any message for any MessageOrigin
.
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".
Dependencies
~17–31MB
~519K SLoC