Closed sdbondi closed 4 months ago
532 tests ±0 532 :white_check_mark: ±0 1h 45m 36s :stopwatch: - 1m 19s 63 suites ±0 0 :zzz: ±0 2 files ±0 0 :x: ±0
Results for commit e9cb2913. ± Comparison against base commit c2aee348.
:recycle: This comment has been updated with latest results.
Description
fix(consensus)!: implements power of two with "half shard" boundaries
Motivation and Context
This PR implements fixed shard split boundaries for a given number of target shards (based on the number of registered VNs for the current epoch).
For splits to occur at fixed addresses in theU256::MAX
sized shard space, we need to account somehow for the remainders. For example, if a shard space is 4 bits, the max address is 15 (0b1111) and we wish to divide the space into 8 (0b1000) equal pieces, there is a remainder of 7 (0b0111), dividing into 4 (0x0100) there is a remainder of 3 (0b0011) etc. Any remainder would lead to shard splits at different addresses depending on num_shards.To account for the remainder, we divide a shard space ofS' = U256::MAX - u16::MAX
and limitnum_shards
tou16::MAX / 2
. These values are selected because they will give no remainder for any power of twonum_shards
up tou16::MAX / 2
. The final shard always has an extrau16::MAX
addresses for num_shards > 1.The remainder of a power of two division of the shard space will always be
num_shards.next_power_of_two() - 1
e.g.0b11..11 (U256::MAX) % 0b0100 = 0b00..0011
to account for this each shard has an extra 1 added to it."Half shards" are used to break the shard space at the same address as the next power of two for any non-power-of-two num_shards.
For example, let's say that num_shards is 6, we can divide
S'
into 4 equal parts (4 is the previous power of two from 6) but the target number of shards requires 2 extra shards. To achieve this we divide the first 2 shards in half. Or put another way, we divide the first two whole shards at the address at which the next power of two would divide them. In this example, we'd divide them at num_shards = 8.num_shards = 6. Four half shards 0, 1, 2 and 3
PROS:
CONS:
VNs with a lower shard address will on average earn less fees due to the increased likelihood of being in half shardsHow Has This Been Tested?
New unit test cases, manually single shard
What process can a PR reviewer use to test or verify this change?
Multishard network
Breaking Changes
BREAKING CHANGE: shard boundaries have changed, therefore nodes in a multishard network will not agree on the shard state