[zeromq-dev] Load Balancing/Distributing/Queuing Algos: A Discussion

[Stefan Sandberg]

  Loadbalancing is fun, it's one of those types of algorithms that can 
continue to surprise you, the more you think about it,
but still being simple enough to quickly test different types.

I guess the first thing to do would be to separate the current 
roundrobin scheme into something more atomic,
like a simple api with an array of socket and a next() function..

For me, roundrobin makes sense given the operational timespan is infinite,
but the entire point of the project I'm working on is to decrease that 
time spent, and I dont have access or any type of control
over the hardware(nor quality of if), I need to favor certain clients 
over others..
The simplest method there is obviously latency/throughput but also cpu & 
ram, depending on the type of work done.

Likewise I also need some sort of way to identify bad workers that keep 
behaving bad, and prune them.
I worked on the generic client for Electricsheep for almost a year, and 
Scott once told me the only
viable way to make sure the data returned from clients is sane, 
(assuming that is still true since I'm no longer involved)
was to hand out N duplicates of the workload and doing additional work 
on the results on the server.
(sometimes rendered frames came back as garbled data, even though the 
transport of it worked fine)

Both round-robin & LRU wont work for my scenario..  (Or rather, they do 
work, statistically, over time, but not in practice..)

For example, I have a fast Core2-Duo and a slow Atom based netbook here 
that I use for testing.
If I for instance send out jobs to calculate PI, the c2d might chew up 
10 jobs while the netbook does one,
and neither LRU nor RR will do the right thing there, but if I could 
assign weights to each of them,
using their reported HW as a rough guide, and continually modify those 
weights based on how they perform over time,
I can prioritize them and get a vastly different outcome.

My goal is to make the system race-to-idle as quickly as possible, and 
zmq currently wont allow that.




On 2010-08-29 21:44, Brian Granger wrote:
> Stefan,
>
> I have played around with other load balancing algorithms and I do
> agree, it would be nice to have an interface that allows users to pick
> which algorithm is used.  The two other approaches I have looked at
> are:
>
> * Randomized choice of peer,
> * Randomly pick two peers and write to the least used one.
>
> Other than time, the main reason I have not pushed hard on these
> approaches, is that there is currently no API for supporting multiple
> load-balancing algorithms that are configurable.  That would be quite
> nice.
>
> Cheers,
>
> Brian
>
> On Mon, Aug 23, 2010 at 2:50 AM, Stefan Sandberg
> <keffo.sandberg at gmail.com>  wrote:
>> I'd like to suggest something inbetween...
>>
>> Currently zmq does loadbalancing with the assumption that everything
>> connected is of equal quality,
>> currently just round-robin'izes over that set equally, which only ever
>> really makes if you have a rack of identical hardware.
>>
>> What I'd like is a generic 'choice' device, which will continually rate
>> all sockets based on stuff that zmq can
>> already figure out behind the scenes, like latency/throughput/idletime
>> etc etc..
>>
>> Ie, keep a list of connections, continually try to rate them based on
>> their lowlevel behaviour, and then let the
>> choice-device iterate over a sorted set..
>> It would involve sorting obviously, but a very well tuned lockless
>> priority-queue implementation,
>> and a customizable update-rate would bring the sorting overhead to a
>> minimum, imo.
>>
>> The default behaviour could simply be the current round-robin, or a more
>> fancy randomized set etc,
>> since they just set weights on each client connection.
>>
>> Now the nifty bit would be a simple api function to offset the low-level
>> socket heuristics already provided by zmq,
>> with your own custom stuff, like offset a connection by worker cpu/ram etc.
>>
>> So to summarize, zmq tries to prioritize based on how it's own,
>> low-level, sockets are behaving,
>> but each connection's internal 'worth' can be offset with an api
>> function at will.
>>
>> Just thoughts!
>> ---------------
>>
>>
>>
>> On 2010-08-17 13:35, Pieter Hintjens wrote:
>>> On Tue, Aug 17, 2010 at 12:57 PM, Peter Alexander<vel.accel at gmail.com>    wrote:
>>>
>>>
>>>> Hi Pieter and thanks for your reply to this question in the other thread. I
>>>> moved it here to see if we could all discuss this some more and come to some
>>>> possible conclusion and/or road-map.
>>>>
>>>> I feel it's important to, in some way, make a selection of
>>>> balancing/distributing algorithms an optional flag which could maybe part of
>>>> the flag set in zmq_setsockopts().
>>>>
>>> Discussion is always good.  I see two possible types of distribution algorithm:
>>>
>>> * Stateless distribution, which works with no knowledge of the state
>>> of the workers.  We currently have round-robin but random scatter
>>> could be an alternative.  This could be trivially added as a socket
>>> option on REQ/XREQ and PUSH.
>>>
>>> * Stateful distribution, which requires data back from workers to make
>>> an informed choice.  This cannot work with PUSH without significant
>>> changes.  It can work with REQ/REP if we use the REQ to return state.
>>> The service (REP side) can then distribute work to the client workers
>>> (REQ side) based on any algorithm it likes.  I'd assume (but need to
>>> try) that with XREQ/XREP and identities, it's 100% customizable.
>>>
>>>
>>>> Using other mechanisms to overcome the built in round-robin, for example,
>>>> defeats the efficiency of 0mq and therefore it needs to be built-in, imo.
>>>>
>>> Not really... so long as you're not trying to distribute over multiple
>>> sockets, it's fine.
>>>
>>> The other idea is to wait for policy/transport separation
>>> (http://www.zeromq.org/docs:3_0) and then define your own socket types
>>> with specific distribution algorithms.
>>>
>>> -
>>> Pieter Hintjens
>>> iMatix - www.imatix.com
>>> _______________________________________________
>>> zeromq-dev mailing list
>>> zeromq-dev at lists.zeromq.org
>>> http://lists.zeromq.org/mailman/listinfo/zeromq-dev
>>>
>> _______________________________________________
>> zeromq-dev mailing list
>> zeromq-dev at lists.zeromq.org
>> http://lists.zeromq.org/mailman/listinfo/zeromq-dev
>>
>
>