Made with Substrate, for Polkadot.
Bags-List Pallet
An onchain implementation of a semi-sorted linked list, with permissionless sorting and update operations.
Pallet API
See the [pallet
] module for more information about the interfaces this pallet exposes,
including its configuration trait, dispatchables, storage items, events and errors.
This pallet provides an implementation of
[frame_election_provider_support::SortedListProvider
] and it can typically be used by another
pallet via this API.
Overview
This pallet splits AccountId
s into different bags. Within a bag, these AccountId
s are stored
as nodes in a linked-list manner. This pallet then provides iteration over all bags, which
basically allows an infinitely large list of items to be kept in a sorted manner.
Each bags has a upper and lower range of scores, denoted by [Config::BagThresholds
]. All nodes
within a bag must be within the range of the bag. If not, the permissionless [Pallet::rebag
]
can be used to move any node to the right bag.
Once a rebag
happens, the order within a node is still not enforced. To move a node to the
optimal position in a bag, the [Pallet::put_in_front_of
] or [Pallet::put_in_front_of_other
]
can be used.
Additional reading, about how this pallet is used in the context of Polkadot's staking system: https://polkadot.network/blog/staking-update-september-2021/#bags-list-in-depth
Examples
See [example
] for a diagram of rebag
and put_in_front_of
operations.
Low Level / Implementation Details
The data structure exposed by this pallet aims to be optimized for:
- insertions and removals.
- iteration over the top* N items by score, where the precise ordering of items doesn't particularly matter.
Further Details
- items are kept in bags, which are delineated by their range of score (See
[
Config::BagThresholds
]). - for iteration, bags are chained together from highest to lowest and elements within the bag are iterated from head to tail.
- items within a bag are iterated in order of insertion. Thus removing an item and re-inserting it will worsen its position in list iteration; this reduces incentives for some types of spam that involve consistently removing and inserting for better position. Further, ordering granularity is thus dictated by range between each bag threshold.
- if an item's score changes to a value no longer within the range of its current bag the item's position will need to be updated by an external actor with rebag (update), or removal and insertion.