

New DIST rebalancing code in Infinispan
=======================================
[org.infinispan.distribution package]

The existing code had issues:

* There is a lot of communication involved, e.g. a new joiner broadcasts the new consistent hash (CH), and everybody
  updates it
* Joining, merging and leaving and handled differently, but in principle the same code can be used to handle these
  situations
* Blocking RPCs are used, e.g. when joining the CH is fetched synchronously from the current coordinator
* Certain assumptions about JGroups view ordering are incorrect, especially regarding RELAY:
  * RELAY can first install View V1={A}, and then MergeView V2={A,X} where A and X are in different clusters. The current
    code deterministically picks one of the 2 nodes to be the state provider and the other to be the state requester. This
    won't work when A has state, but X doesn't yet
* Joiners pull the state from the nodes which have it. This is problematic at best in a merge case
* Invalidation also involves communication


New design
----------

The new design moves from a pull-based to a push-based state transfer. Every node makes the decision as to which keys
to push to other nodes, and which ones to invalidate based on view changes. A view change is received at the same
logical time on all nodes, and the order of the views is also guaranteed to be the same across all cluster nodes.

This roughly works as follows:

- On a view change, every node N grabs the existing CH and computes the new CH
- N then iterates through all keys in its data container (and its cache store as well)
- For every key K, N computes the list of existing servers (S-old) and new servers (S-new)
- If S-old == S-new, K is skipped (no rebalancing or invalidation has to be done)
- Then N determines whether it is the current owner of K. This is done by iterating through S-old and returning the
  last server that's also in S-new. For example, if we have S-old={A,B} and S-new={A,B,C}, the current owner is B. If
  we have S-old={A,B} and S-new={B,C,D}, then the owner is B. If we have S-old={A,B} and S-new={C,D}, the owner is null.
  (In this last case, there is no rebalancing as all the data has been lost !)
- If N is the owner of K, it pushes K to all servers in S-new which are *not* in S-old.
- If N is *not* in S-new, K is invalidated on N


Implementation
--------------
- DistributionManagerImpl:
  - On a view change, we submit a new RebalanceTask
  - The RebalanceTask executes the logic above
- State is pushed to store holders via the applyState() method in DistributionManagerImpl
  - applyState() bypasses the check whether a key is local (the pusher already toook that decision)
