Adaptive branching factor for gossiping
My draft, quick-shot proposal (change however you want):
Every gossip wire level message contains branching factor BF
There is a variable in every node, current branching factor CBF
There is a configurable initial branching factor IBF
There is a configurable dampening factor 0.0 < DF < 1.0
There is a configurable minimum branching factor MBF >= 1
On events that change my current version:
- If I bump my version (fork) -> CBF := IBF
- If I merge an external gossip G -> CBF := G.BF (or should CBF := max(CBF, G.BF) ?)
- if no change -> CBF = MBF
On a gossip timer tick
- Send CBF number of gossip messages, each having G.BF = max(CBF * DF, MBF)
- Set CBF := MBF
There are some cases to be considered when multiple changes are disseminated at the same time, but I think it should work.
Every gossip wire level message contains branching factor BF
There is a variable in every node, current branching factor CBF
There is a configurable initial branching factor IBF
There is a configurable dampening factor 0.0 < DF < 1.0
There is a configurable minimum branching factor MBF >= 1
On events that change my current version:
- If I bump my version (fork) -> CBF := IBF
- If I merge an external gossip G -> CBF := G.BF (or should CBF := max(CBF, G.BF) ?)
- if no change -> CBF = MBF
On a gossip timer tick
- Send CBF number of gossip messages, each having G.BF = max(CBF * DF, MBF)
- Set CBF := MBF
There are some cases to be considered when multiple changes are disseminated at the same time, but I think it should work.
Leave a comment
on 2013-03-14 12:39 *
By Patrik Nordwall
Purpose: Speed up dissemination when there is a change, but keep the traffic low when there are no changes.
Implementation note: CBF would be a field in akka.cluster.Gossip (not a separate field)
Implementation note: CBF would be a field in akka.cluster.Gossip (not a separate field)
on 2013-09-19 12:00 *
By Patrik Nordwall
If we don't have time for the full thing we should at least do the small change in attached patch. It has been tried with good results (also attached) in the 200 nodes test.
file:aY7MwGismr44BcacwqjQYw
Speedup patch
Speedup patch
Speedup results, blue=master, green=path, join one