At the moment, the transcoderPool state variable represents the pending active set in the current round and when the next round is initialized the members of the pool are locked in as the active set for the round.
transcoderPool is represented by the SortedDoublyLL.Data struct - its internal state represents a doubly linked list. At the moment, the functions defined in the SortedDoublyLL will insert/update/remove elements in the list such that the list remains sorted (descending from the head based on the value of an element's key).
The functions that update transcodePool in the BondingManager are:
increaseTotalStake()
Updates the key of a transcoder in the list
decreaseTotalStake()
Updates the key of a transcoder in the list
tryToJoinActiveSet()
If the pool is full, fetches the last transcoder in the list and if the new transcoder has more stake, remove the last transcoder and insert the new transcoder
If the pool is not full, insert the new transcoder
Let's consider the storage operations associated with using a sorted list.
increaseTotalStake()
O(1) SSTOREs to remove the transcoder at its current position
O(n) SLOADs because we have to find the new position of the transcoder post-update
O(1) SSTOREs to insert the transcoder at the new position
decreaseTotalStake()
O(1) SSTOREs to remove the transcoder at its current position
O(n) SLOADs because we have to find the new position of the transcoder post-update
O(1) SSTOREs to insert the transcoder at the new position
tryToJoinActiveSet()
O(1) SLOADs to find the last transcoder
When we have to evict a transcoder
O(1) SSTOREs to remove the last transcoder
O(n) SLOADs to find the new position of the transcoder
O(1) SSTOREs to insert the transcoder at the new position
An alternative is to keep the list unsorted and only when we want to evict/insert an element into the list do we do a linear search to find the element with the smallest key.
Let's consider the storage operations associated with using an unsorted list.
increaseTotalStake()
O(1) SSTOREs to update the transcoder at its current position
decreaseTotalStake()
O(1) SSTOREs to update the transcoder at its current position
tryToJoinActiveSet()
O(n) SLOADs to find the last transcoder
When we have to evict a transcoder
O(1) SSTOREs to remove the last transcoder
O(1) SSTOREs to insert the transcoder at the new position
When using an unsorted list the only time we might have to do a linear search is in tryToJoinActiveSet(). The one downside is that when using an unsorted list we will not be able to use client generated hints (i.e. the client calculates the new position and it is provided as a hint to the contract - if the hint is the right position we can insert immediately, if it is not then we have to do a linear search starting from the hint position). SortedDoublyLL currently supports client generated hints, but the BondingManager does not expose it to external callers. An alternative to using an unsorted list would be to expose hints to external callers in the BondingManager i.e. staking related functions would need to also allow a hint to be passed in their function signatures.
An add-on to the unsorted list construction would be to keep track of the currentMin in storage. When we insert into the list or update elements in the list we update currentMin. If we have to remove the min element from the list then we can use currentMin. After removing currentMin we will no longer know currentMin so the next time an operation on the list is executed we can do a linear search to find the currentMin again and store it. As a result, most operations will require O(1) SLOADs and only the list operation that immediately follows removal of the min will need to do O(n) SLOADs to calculate thew new currentMin.
yondonfu
commented
5 years ago
At the moment, the
transcoderPoolstate variable represents the pending active set in the current round and when the next round is initialized the members of the pool are locked in as the active set for the round.transcoderPoolis represented by theSortedDoublyLL.Datastruct - its internal state represents a doubly linked list. At the moment, the functions defined in theSortedDoublyLLwill insert/update/remove elements in the list such that the list remains sorted (descending from the head based on the value of an element's key).The functions that update
transcodePoolin theBondingManagerare:increaseTotalStake()decreaseTotalStake()tryToJoinActiveSet()Let's consider the storage operations associated with using a sorted list.
increaseTotalStake()decreaseTotalStake()tryToJoinActiveSet()An alternative is to keep the list unsorted and only when we want to evict/insert an element into the list do we do a linear search to find the element with the smallest key.
Let's consider the storage operations associated with using an unsorted list.
increaseTotalStake()decreaseTotalStake()tryToJoinActiveSet()When using an unsorted list the only time we might have to do a linear search is in
tryToJoinActiveSet(). The one downside is that when using an unsorted list we will not be able to use client generated hints (i.e. the client calculates the new position and it is provided as a hint to the contract - if the hint is the right position we can insert immediately, if it is not then we have to do a linear search starting from the hint position).SortedDoublyLLcurrently supports client generated hints, but theBondingManagerdoes not expose it to external callers. An alternative to using an unsorted list would be to expose hints to external callers in theBondingManageri.e. staking related functions would need to also allow a hint to be passed in their function signatures.An add-on to the unsorted list construction would be to keep track of the
currentMinin storage. When we insert into the list or update elements in the list we updatecurrentMin. If we have to remove the min element from the list then we can usecurrentMin. After removingcurrentMinwe will no longer knowcurrentMinso the next time an operation on the list is executed we can do a linear search to find thecurrentMinagain and store it. As a result, most operations will require O(1) SLOADs and only the list operation that immediately follows removal of the min will need to do O(n) SLOADs to calculate thew newcurrentMin.