Crate pallet_bags_list

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 AccountIds into different bags. Within a bag, these AccountIds 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.

Re-exports

• pub use weights::WeightInfo;
• pub use pallet::*;

Modules

• example
  In this example, assuming each node has an equal id and score (eg. node 21 has a score of 21), the node 22 can be moved from bag 1 to bag 0 with the rebag operation.
• migrations
  The migrations of this pallet.
• mock
  Mock runtime for pallet-bags-lists tests.
• pallet
  The pallet module in each FRAME pallet hosts the most important items needed to construct this pallet.
• weights
  Autogenerated weights for pallet_bags_list

Macros

• log

Structs

• Bag
  A Bag is a doubly-linked list of ids, where each id is mapped to a Node.
• List
  The ONLY entry point of this module. All operations to the bags-list should happen through this interface. It is forbidden to access other module members directly.
• Node
  A Node is the fundamental element comprising the doubly-linked list described by Bag.

Enums

• ListError

Functions

• notional_bag_for
  Given a certain score, to which bag does it belong to?