Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

How to get an ordered linked_map? #2631

Closed
liuchengxu opened this issue May 20, 2019 · 6 comments

Comments

@liuchengxu
Copy link
Contributor

commented May 20, 2019

Currently I don't see an easy way to make a linked_map to be ordered by the value. Do you have a plan to support ordered linked map in substrate? What's the best way to get an ordered linked_map at the moment?

@burdges

This comment has been minimized.

Copy link

commented May 20, 2019

Are you asking about the execute block function specifically? There is no local randomness in the execute block function, so you need the random state to be defined by the chain. We might worry this creates a DoS vector but nobody analyzed this yet. BTreeMap works fine. IndexMap has an interfaces compatible with substrate despite using randomness internally, so maybe eventually.

@liuchengxu

This comment has been minimized.

Copy link
Contributor Author

commented May 20, 2019

No. I'm actually asking about the provided data structure linked_map. Assuming I define a storage item in decl_storage!:

pub Foo get(foo): linked_map T::AccountId => T::Balance;

Foo could be huge eventually and I do need to sort it by the value T::Balance. Currently the linked_map seemingly only supports doing inserts from the beginning. I have no idea how to get it sorted at present.

@tomusdrw

This comment has been minimized.

Copy link
Contributor

commented May 20, 2019

@liuchengxu Currently we don't have that implemented, I also didn't hear about any plans or use cases to implement that.
To implement this efficiently you would need a tree structure, but most likely that would make all the operations logarithmic instead of constant time. You could implement that in the runtime itself and store the tree structure as map.

Note however that enumerating such (unbounded) structure in runtime is not recommended because it's going to be slow and unpredictable, perhaps there is some other way you could achieve what you need?

@liuchengxu

This comment has been minimized.

Copy link
Contributor Author

commented May 20, 2019

My use cause is sort of generating a validator set from the top candidates in the staking module. Our election algorithm is similar to the one before phragmen. We have to sort the candidates based on their total nominations to get the top ones.

It may not be a good choice to store a possibly enormous Vec(candidates or intentions previously called) than Map from our point of view. So we hope to replace the Vec with linked_map, only to finding it may not easy to get sorted :(.

I notice enumerate() is used in L122, substrate/srml/staking/src/phragmen.rs. My concern is whether it will result in a performance issue when Validators becomes utterly huge?

/// The map from (wannabe) validator stash key to the preferences of that validator.
pub Validators get(validators): linked_map T::AccountId => ValidatorPrefs<BalanceOf<T>>;

let mut nominators: Vec<Nominator<T::AccountId>> = Vec::with_capacity(validator_iter.size_hint().0 + nominator_iter.size_hint().0);
let mut candidates = validator_iter.map(|(who, _)| {
let stash_balance = stash_of(&who);
(Candidate { who, ..Default::default() }, stash_balance)
})
.filter_map(|(mut c, s)| {
c.approval_stake += to_votes(s);
if c.approval_stake.is_zero() {
None
} else {
Some((c, s))
}
})
.enumerate()
.map(|(idx, (c, s))| {
nominators.push(Nominator {
who: c.who.clone(),
edges: vec![ Edge { who: c.who.clone(), candidate_index: idx, ..Default::default() }],
budget: to_votes(s),
load: Fraction::zero(),
});
c_idx_cache.insert(c.who.clone(), idx);
c
})
.collect::<Vec<Candidate<T::AccountId>>>();

@kianenigma

This comment has been minimized.

Copy link
Contributor

commented May 21, 2019

@liuchengxu I don't think the enumerate() itself (shown in the code snippet) adds a horrible overhead as in this case it is being called on a Rust Iterator<T> (not the ::enumerate() that you get for free by using linked_map). Though,

  • You point holds. Such codes need to be audited and made sure that economic security is assured (e.g. becoming a validator is sufficiently expensive so that the price needed to exploit this unbounded Vec or Map is large enough). And we are actually using the linked_map::enumerate() here:

<Validators<T>>::enumerate(),
<Nominators<T>>::enumerate(),

Which I think does not more than going through all mappings and concatenating them, not really being related to partial order or being sorted.

  • As for linked_map or map being sorted out of the box, as mentioned (@tomusdrw) I don't see that happening in substrate level (in my opinion since everything is key/value under the hood. Sorting is simply inefficient)
@liuchengxu

This comment has been minimized.

Copy link
Contributor Author

commented May 21, 2019

@kianenigma @tomusdrw Thanks for your info.

@liuchengxu liuchengxu closed this May 21, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.