34 major breaking releases
37.0.0 | Sep 26, 2024 |
---|---|
36.0.0 | Jul 18, 2024 |
35.0.0 | Jul 12, 2024 |
34.0.0 | Jun 24, 2024 |
0.0.0 | Nov 21, 2022 |
#7 in #bags
5,075 downloads per month
Used in 18 crates
(5 directly)
2.5MB
49K
SLoC
Release
Polkadot SDK stable2409
lib.rs
:
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.
Dependencies
~17–32MB
~529K SLoC