bench/hashring/runs/ring.txt

Python 3.11.15 · Linux 6.18.44-fc-v24
exact computation, not a simulation: only the keys are random
100000 keys, 8 nodes, hash is the first 8 bytes of SHA-1

1. MODULO SHARDING: ADDING ONE NODE MOVES ALMOST EVERYTHING
-----------------------------------------------------------
         nodes   -> nodes    keys moved   ideal share
             8          9        88.9%        11.1%
             8         10        80.2%        20.0%

  times more than the minimum, +1 node           8.0

  Ideal share is what has to move at minimum: the keys the new nodes
  take over. Modulo moves many times that, because the divisor
  changes for every key at once - a key's node is not a property of
  the key, it is a property of the current node count.

2. A RING MOVES ONLY WHAT IT HAS TO
-----------------------------------
    vnodes per node   keys moved, +1 node   ideal share
                  1                11.5%        11.1%
                 16                10.9%        11.1%
                128                10.7%        11.1%

  The same change of membership as in block 1, and the same keys.
  What changed is only how the owner is chosen - and the traffic of
  moving data drops from most of the dataset to about a ninth.

3. WITHOUT VIRTUAL NODES THE RING IS BADLY SKEWED
-------------------------------------------------
    vnodes per node   smallest share   largest share   max/min
                  1            0.4%          33.3%     90.5x
                 16            8.7%          16.3%      1.9x
                128           11.0%          15.1%      1.4x
                512           12.1%          13.6%      1.1x

  With one point per node the ring is a random partition of a circle,
  and random partitions are uneven. Virtual nodes are the fix: many
  small arcs average out where few large ones cannot.

4. WHAT VIRTUAL NODES COST
--------------------------
    vnodes per node   points on the ring   max/min
                  1                    8     90.5x
                 16                  128      1.9x
                128                 1024      1.4x
                512                 4096      1.1x

  The points are what a lookup searches and what every node must
  hold. Going from 128 to 512 quadruples the structure to buy the
  last few percent of evenness - which is the shape of the trade,
  not a recommendation.

5. REMOVING A NODE MOVES ITS KEYS AND NOBODY ELSE'S
---------------------------------------------------
  share of keys the removed node owned           11.7%
  share of keys that moved in total              11.7%
  share of OTHER nodes' keys that moved          0.0%

  Everything the removed node held changed owner, and not a single
  key of any other node did. That is the property the whole scheme
  exists for, and it is what modulo sharding does not have.