twitter/gizzmo — pull request #22 by stuhood (2012-02-17 10:46:12+00:00)
Title: DS-46: Improve rebalance scheduling time

> Gizzmo seems to have some algorithmic inefficiencies in scheduling especially rebalance operations which make it impossible to rebalance [clusters with many shards]

This pull tries to cut down on object creation in comparisons, and memoizes hash codes and other expensive-to-compute values. It also makes changes to bucket balancing: moving multiple shards per rebalance iteration, and attempting to minimize set/map lookups.

For a test case with 10k shards, 10 initial hosts, and 16 destination hosts:
117 seconds pre-patch
7 seconds post-patch