redis-trib: better slots allocation strategy for resharding

diff --git a/src/redis-trib.rb b/src/redis-trib.rb
index 083f9740ffa2a9bd2fc09eddc59e66b2e1e14fbc..3717f54e7c090064ca83e4aef88e298121ace23e 100755 (executable)
--- a/src/redis-trib.rb
+++ b/src/redis-trib.rb
@@ -287,10 +287,22 @@ class RedisTrib
     # instance.
     def compute_reshard_table(sources,numslots)
         moved = []
     # instance.
     def compute_reshard_table(sources,numslots)
         moved = []

-        sources.each{|s|
+        # Sort from bigger to smaller instance, for two reasons:
+        # 1) If we take less slots than instanes it is better to start getting from
+        #    the biggest instances.
+        # 2) We take one slot more from the first instance in the case of not perfect
+        #    divisibility. Like we have 3 nodes and need to get 10 slots, we take
+        #    4 from the first, and 3 from the rest. So the biggest is always the first.
+        sources = sources.sort{|a,b| b.slots.length <=> a.slots.length}
+        sources.each_with_index{|s,i|

             # Every node will provide a number of slots proportional to the
             # slots it has assigned.
             # Every node will provide a number of slots proportional to the
             # slots it has assigned.

-            n = (numslots.to_f/4096*s.slots.length).ceil
+            n = (numslots.to_f/4096*s.slots.length)
+            if i == 0
+                n = n.ceil
+            else
+                n = n.floor
+            end

             s.slots.keys.sort[(0...n)].each{|slot|
                 if moved.length < numslots
                     moved << {:source => s, :slot => slot}
             s.slots.keys.sort[(0...n)].each{|slot|
                 if moved.length < numslots
                     moved << {:source => s, :slot => slot}