Re: OT: load distribution algorithm

On Mon, 01 Oct 2007 10:45:39 -0000, Alexandre Ferrieux
<alexandre.ferrieux@xxxxxxxxx> wrote:

OK, take your time. In the meantime, I'm just surprised nobody
mentioned (or I missed it again) what happens when the job holding the
sqf gets busy (it happens !), and hence its queue length becomes
larger than the sqf. How do we know how many ex-aequo had already the
same queue length ? Or do you update sqf to -1 again in this case ?

First, I should clarify:

A group of sockets sitting on an event loop may not be a queue in the
usual sense, but I think of it as a "queue" in the sense of trying to
find the shortest one first. So by "queue" I mean a group of sockets
sitting on an event loop.

Now to the question ...

When writing the code, I realized I could eliminate the -1 flag value
special case.

I no longer view the initial state as a special case. I arbitrarily
give the flag to some worker, since they're all equal at the initial
state. I like number 1, so that's who gets it.

I also arbitrarily start the roundrobin with the worker holding the
flag.

If the worker holding the flag gets busy, that won't matter. When a
new socket arrives, the dispatcher always makes a simple choice. He
knows who is next in the roundrobin, he knows who holds the flag, and
he knows their respective socket counts.

Shortest "queue" always wins.

When there is a winner, the winner gets the socket. The dispatcher
does NOT advance the roundrobin, he leaves it where it was, for the
next cycle.

Now if both queues were equal, it's a tie. By rule, the one next up
in the roundrobin wins the tie.

This decision is repeated for every new socket that arrives.

Now imagine opening for business, and a big burst of sockets arrive.
The roundrobin will evenly distribute the sockets among the workers,
and it doesn't matter who holds the flag, UNTIL at least one socket
closes.

When that happens, the worker who closed his socket will try to grab
the flag (if someone else holds it). He follows a rule that says, to
grab the flag, his count must be less than the flag holder's count.

He compares his count to the flag holder's count. It doesn't matter
what the other counts are, he only needs to know the lowest, and that
will always be at the flag holder. So every time a socket closes, the
flag either moves to the shortest queue, or stays at the shortest
queue.

The dispatcher's decision is easy, because the workers keep their own
count of sockets. When the dispatcher sends a new socket to a worker,
the worker increments his count. And when the worker closes a socket,
he decrements his count.

The worker can't do both at the same time, he either does one or the
other. When he decrements his count, and tries to grab the flag, it
doesn't matter what anyone else is doing.

Access to the flag is serialized by a tsv, so the lowest count always
gets it, even if that means changing hands in rapid succession when a
burst of sockets close.


In short, to be O(1) it seems to me that the algorithm must maintain a
somewhat ordered (if incompletely) structure, and not call a O(N)
procedure (like resetting sqf to a reasonable value by scanning
evrybody) from time to time...

Right, that's not necessary.


--
Internet service
http://www.isp2dial.com/

.

Relevant Pages

  • Re: [PATCH 1/3] Kernel interfaces for multiqueue aware socket
    ... Multiqueue and multicore provide packet parallel processing methodology. ... Current kernel and network drivers place one queue on one core. ... Current socket only can receive or send ... Kernel provides several interfaces by which sockets can be bound to rx/tx queues. ...
    (Linux-Kernel)
  • Re: OT: load distribution algorithm
    ... The dispatcher will simply ... round robin jobs, until some queue completes a job. ... There is a global flag, ...
    (comp.lang.tcl)
  • Re: Interrupts handling in ADA
    ... the other three execute a "read" from network function inside ... Queue of entry calls: ... After the "pop" of the first event, can the fist socket continue its ... execution or does it have to wait until the queue is empty? ...
    (comp.lang.ada)
  • Re: Adding new non-blocking sockets during select-call
    ... falling back to the I/O thread only on EWOULDBLOCK. ... before writing to a socket that one has not written to in a long time. ... queue a 'speculative write' job ... it keeps calling 'write' until it either empties the user-space send ...
    (comp.unix.programmer)
  • Re: [PATCH 1/3] Kernel interfaces for multiqueue aware socket
    ... Current kernel and network drivers place one queue on one core. ... Current socket only can receive or send ... Kernel provides several interfaces by which sockets can be bound to rx/tx queues. ...
    (Linux-Kernel)