 |
BorlandTalk.com Borland discussion newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Eric Hill Guest
|
Posted: Fri Feb 20, 2004 2:51 pm Post subject: SEDA and PID Random Thoughts |
|
|
I've been reading up on Staged Event Driven Architecture where every step in a process is isolated
into it's own sandbox with an input queue. Breaking an application up like this allows you to
create small thread pools for each stage where parallel processing is desired, and leave the thread
count to 1 for all serial processing. The SEDA paper also talks about dynamically adjusting the
stages to better serve requests. Things like adding another thread to the pool if the input queue
is longer than X items, or removing a thread from the queue if the queue is shorter than X items.
Coming from the PLC world, the ideas would fit well with a PID loop (proportional, integral,
derivitave) algorithm so the developer could simply set some criteria for performance.
Interestingly enough, PID loops are designed to set static numbers that will monitor, control, and
react to a very analog source. The SEDA example of web-site traffic can be thought of as a very
analog source, since you never really know how much traffic you're going to receive at a given time.
The timing constraints of a PID loop would give some degree of control over a widely variable input
stream.
I'm thinking of attempting to build an abstract stage class that has a PID loop integrated with it
to control the internals of the stage such as thread count and input queue length. A developer
would subclass an abstract stage into a concrete implementation (consisting of a single
threads-worth of code) and set the parameters of the stage to best react to the input.
Instead of an abstract stage (similar to TThread), this could also be architected where the
developer just creates a new instance of a stage class and assigns an OnWork property (TNotifyEvent
of sorts) to it, thus decoupling the stage algorithm from the implementation.
Furthermore, the developer could create a single AppStages object that has methods for each stage
and connect it to a stage controller. The app object would define the rules inside of its' methods
for the entire application, and would be called re-entrantly from the stage controller as needed.
Has this been done already? Comments? Etc.?
SEDA: http://www.eecs.harvard.edu/~mdw/proj/seda/
PID loop intro: http://www.isc-ltd.com/resource_centre/tech_pid.html
Eric
|
|
| Back to top |
|
 |
Harley Pebley Guest
|
Posted: Fri Feb 20, 2004 7:19 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
Eric,
| Quote: | I've been reading up on Staged Event Driven Architecture where every step in a process is isolated
into it's own sandbox with an input queue. Breaking an application up like this allows you to
create small thread pools for each stage where parallel processing is desired, and leave the thread
count to 1 for all serial processing.
|
Never heard of the technique but I used something like it 14 years ago in a
Unix environment. Instead of threads and queues I used processes and named
pipes, but architecturally it sounds very similar. Worked really well for
my application.
| Quote: | The SEDA paper also talks about dynamically adjusting the
stages to better serve requests. Things like adding another thread to the pool if the input queue
is longer than X items, or removing a thread from the queue if the queue is shorter than X items.
|
This sounds like basic thread pooling.
| Quote: | I'm thinking of attempting to build an abstract stage class ... where the
developer just creates a new instance of a stage class and assigns an OnWork property ...
|
Or overrides a DoWork method.
| Quote: | Furthermore, the developer could create a single AppStages object that has methods for each stage
and connect it to a stage controller. The app object would define the rules inside of its' methods
for the entire application, and would be called re-entrantly from the stage controller as needed.
Has this been done already? Comments? Etc.?
|
It sounds pretty interesting. I read a couple months ago an article
presenting a thread pooling framework. It was probably either Dr Dobbs,
Delphi Informant or Delphi Magazine. I'm pretty sure it was in Delphi so
most likely one of the latter two. Might give you a foundation to build on.
If you want more information, let me know and I'll try to dig it up.
More things for my reading list. <g>
Cheers,
Harley Pebley
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Fri Feb 20, 2004 9:09 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | Delphi Informant or Delphi Magazine. I'm pretty sure it was in Delphi so
most likely one of the latter two. Might give you a foundation to build on.
If you want more information, let me know and I'll try to dig it up.
|
If you've got time - this is just another one of my learning exercises :)
Thanks!
Eric
|
|
| Back to top |
|
 |
Ritchie Guest
|
Posted: Sat Feb 21, 2004 3:04 am Post subject: Re: SEDA and PID Random Thoughts |
|
|
In article <40361f00 (AT) newsgroups (DOT) borland.com>, [email]eric (AT) ijack (DOT) net[/email] says...
| Quote: | I've been reading up on Staged Event Driven Architecture where every
step in a process is isolated into it's own sandbox with an input queue.
Breaking an application up like this allows you to create small thread
pools for each stage where parallel processing is desired, and leave
the thread count to 1 for all serial processing. The SEDA paper also
talks about dynamically adjusting the stages to better serve requests.
Things like adding another thread to the pool if the input queue is
longer than X items, or removing a thread from the queue if the queue
is shorter than X items.
Coming from the PLC world, the ideas would fit well with a PID loop
(proportional, integral, derivitave) algorithm so the developer could
simply set some criteria for performance.
|
I saw a research paper once on an experimental web server that used that
very technique. Looked pretty interesting :)
The thread pool I use that I created a while back could have its
Capacity set on the fly, although it did not do so automatically (I ran
test programs with a spinner to play with the capacity to see how it
fared). It had a queue of ICOREExecutable (an interface with only
'procedure Execute' on it) that fed the threads. Pretty easy to take a
look at QueueList.Count and vary the capacity on the fly.
I'll bet you could do SEDA pretty nicely with a list for a queue and a
protected list of TThreads that you feed.
| Quote: | Interestingly enough, PID loops are designed to set static numbers that
will monitor, control, and react to a very analog source. The SEDA
example of web-site traffic can be thought of as a very analog source,
since you never really know how much traffic you're going to receive at
a given time.
The timing constraints of a PID loop would give some degree of control
over a widely variable input stream.
|
*laugh* The idea of taking an integral of web traffic over time makes me
chuckle Interesting, though.
| Quote: | I'm thinking of attempting to build an abstract stage class that has a
PID loop integrated with it to control the internals of the stage such
as thread count and input queue length. A developer would subclass an
abstract stage into a concrete implementation (consisting of a single
threads-worth of code) and set the parameters of the stage to best react
to the input.
|
I guess you'd need some extra parameters so that you know how much your
input queue has been added to over some previous amount of time (I'm
gathering there's a limit to how far back you need such stats, or
whether one can just keep using a rolling integral... I would think a
completely rolling integral wouldn't properly compensate for time of day
- maybe I should go read those papers again).
Sounds pretty good, though :)
| Quote: | Instead of an abstract stage (similar to TThread), this could also
be architected where the developer just creates a new instance of a
stage class and assigns an OnWork property (TNotifyEvent of sorts)
to it, thus decoupling the stage algorithm from the implementation.
|
Or provide a base class or interface you can feed to the abstract stage
so that when it's time for processing, it can say FStage.DoWork
(FStageWork), or provide a StageFactory that creates the appropriate
Stage when needed.
Or I'm missing the design, which is also possible :)
Lots of possibilities :)
| Quote: | Furthermore, the developer could create a single AppStages object
that has methods for each stage and connect it to a stage controller.
The app object would define the rules inside of its' methods for the
entire application, and would be called re-entrantly from the stage
controller as needed.
|
I *know* I'm misunderstanding this piece :)
I thought the each kind of stage could be called multiple times from the
thread pool? Wouldn't there be concurrency issues? Are the stages
themselves separate objects? If so, how would the method know which to
use?
Like I said, I know I'm misunderstanding :)
| Quote: | Has this been done already? Comments? Etc.?
|
I've made a Tasking system that does a single flow of control that can
sit atop a thread pool and be serviced by various threads, but nothing
quite like you're talking about :)
Interesting reading :)
-- Ritchie Annand
Senior Software Architect
http://www.malibugroup.com
http://nimble.nimblebrain.net
http://wiki.nimblebrain.net
|
|
| Back to top |
|
 |
Harley Pebley Guest
|
Posted: Sat Feb 21, 2004 4:02 am Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | Delphi Informant or Delphi Magazine. I'm pretty sure it was in Delphi so
most likely one of the latter two. Might give you a foundation to build on.
If you want more information, let me know and I'll try to dig it up.
If you've got time - this is just another one of my learning exercises
|
I think it was "High Performance Client/Server Applications" by Marcel van
Brakel in the December 2003 issue of Delphi Magazine. I don't have the hard
copy in front of me to verify, but the source code in the CServer directory
at http://www.thedelphimagazine.com/disks/dmag100.zip looks about what I
remembered from the article.
HTH,
Harley Pebley
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Sat Feb 21, 2004 9:25 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | *laugh* The idea of taking an integral of web traffic over time makes me
chuckle Interesting, though.
|
<g> I thought the same thing, but the more I thought about it, the more it
fit the design needs.
| Quote: | I guess you'd need some extra parameters so that you know how much your
input queue has been added to over some previous amount of time (I'm
gathering there's a limit to how far back you need such stats, or
whether one can just keep using a rolling integral... I would think a
completely rolling integral wouldn't properly compensate for time of day
- maybe I should go read those papers again).
|
I think that since spikes in traffic happen throughout the day, the system
should really only be looking at the last few minutes (5 to 10) compared to
the current traffic level. You could make the system react quicker to
surges in traffic, and react slower to less traffic, so it would ramp up
quicker than it slows down. Could be fun to play with anyway... :)
| Quote: | Furthermore, the developer could create a single AppStages object
that has methods for each stage and connect it to a stage controller.
The app object would define the rules inside of its' methods for the
entire application, and would be called re-entrantly from the stage
controller as needed.
I *know* I'm misunderstanding this piece
|
The AppStages object would be derived from an abstract class and have
methods that handled each stage. Sort of like a big state machine. One
method would register all the different stages with the stage controller, so
as a developer, you would just need to build one class that had your
business logic in it.
| Quote: | I thought the each kind of stage could be called multiple times from the
thread pool? Wouldn't there be concurrency issues? Are the stages
themselves separate objects? If so, how would the method know which to
use?
|
You would definitely need to make sure your code was thread-safe, but having
the same method called at the same time by two threads shouldn't pose a
problem.
Eric
|
|
| Back to top |
|
 |
Ritchie Guest
|
Posted: Tue Feb 24, 2004 1:53 am Post subject: Re: SEDA and PID Random Thoughts |
|
|
In article <4037cce0$1 (AT) newsgroups (DOT) borland.com>, [email]eric (AT) ijack (DOT) net[/email] says...
| Quote: | I think that since spikes in traffic happen throughout the day, the system
should really only be looking at the last few minutes (5 to 10) compared to
the current traffic level. You could make the system react quicker to
surges in traffic, and react slower to less traffic, so it would ramp up
quicker than it slows down. Could be fun to play with anyway...
|
Ramping up fast and ramping down slowly sounds ideal. One potential
downfall of PID might be that it doesn't distinguish enough between the
impact of various kinds of requests: queries, order processing,
navigation, although that could possibly go into the mix of determining
"traffic" to the site (instead of a straight byte count or somesuch, go
for a sum [ requests(i) * request_impact(i) ])
Sounds like a simulator could get quite a workout :)
| Quote: | The AppStages object would be derived from an abstract class and have
methods that handled each stage. Sort of like a big state machine. One
method would register all the different stages with the stage controller, so
as a developer, you would just need to build one class that had your
business logic in it.
|
So something would go and feed each method something from the
appropriate input queue for that state?
Something like:
NextItem := StageInputQueues[i].Dequeue;
if Assigned(NextItem) then
begin
NextStageMethod := AppStages.Methods[i];
NextStageMethod(NextItem);
end;
?
| Quote: | You would definitely need to make sure your code was thread-safe, but having
the same method called at the same time by two threads shouldn't pose a
problem.
|
As long as they had some sort of context passed into them that couldn't
be called by multiple things at the same time.
Perhaps...
procedure TMyAppStages.ProcessStuff(AContext: IStageContext);
var
ProcessContext : IProcessContext;
X : IStageContext;
begin
if Supports(AContext,IProcessContext,ProcessContext) then
begin
X := DoSomeLookup(ProcessContext.SessionID,ProcessContext.UserName);
ProcessContext.NextQueue.Add(X); // Next stage
end;
end;
-- Ritchie Annand
Senior Software Architect
http://www.malibugroup.com
http://nimble.nimblebrain.net
http://wiki.nimblebrain.net
|
|
| Back to top |
|
 |
Bryan Crotaz Guest
|
Posted: Tue Feb 24, 2004 10:33 am Post subject: Re: SEDA and PID Random Thoughts |
|
|
I'm going to try this with one of my work queues. I've got two queues, one
high priority and one low priority. I'll try putting higher priority
threads on one, then try putting more threads on instead. I'll report back
later...
Bryan
|
|
| Back to top |
|
 |
Anders Isaksson Guest
|
Posted: Tue Feb 24, 2004 1:21 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
On Sat, 21 Feb 2004 15:25:47 -0600, "Eric Hill" <eric (AT) ijack (DOT) net> wrote:
| Quote: | You could make the system react quicker to surges in traffic, and
react slower to less traffic, so it would ramp up quicker than
it slows down.
|
I'd be rather careful with that! If traffic always come in bursts,
evenly spaced in time, you will ramp up more than down all the time,
quickly saturating the system.
--
Anders Isaksson, Sweden
BlockCAD: http://user.tninet.se/~hbh828t/proglego.htm
Gallery: http://user.tninet.se/~hbh828t/gallery/index.htm
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Tue Feb 24, 2004 10:17 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | I'd be rather careful with that! If traffic always come in bursts,
evenly spaced in time, you will ramp up more than down all the time,
quickly saturating the system.
|
Obviously there would have to be a minimum and maximum "worker" count. I'm thinking more of the
reactive portion of the PID loop. You would react more for positive errors, and less for negative
errors, so you would ramp to your maximum faster than you offramp to your minumum.
I'm really enjoying this idea as you can tell... <G>
Eric
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Tue Feb 24, 2004 10:29 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | Ramping up fast and ramping down slowly sounds ideal. One potential
downfall of PID might be that it doesn't distinguish enough between the
impact of various kinds of requests: queries, order processing,
navigation, although that could possibly go into the mix of determining
"traffic" to the site (instead of a straight byte count or somesuch, go
for a sum [ requests(i) * request_impact(i) ])
Sounds like a simulator could get quite a workout
|
Agreed. I do think that (as in the traditional sense) the PID loop would really need to be tuned by
the developer.
Something like:
with Stage.Parameters do begin
ScalingPercent := 20; // 20%
ResetTime := 30000; // 30 seconds
ReactionTime := 120000; // 120 seconds
end;
| Quote: | So something would go and feed each method something from the
appropriate input queue for that state?
|
Exactly.
The worker threads would pick up a task in the input queue and feed it into the stage handler. The
stage would be responsible for setting the next stage, which could be "finished" or "terminate
caller".
| Quote: | As long as they had some sort of context passed into them that couldn't
be called by multiple things at the same time.
|
The context would really be the work item. The work item will either be waiting in a queue, or
being handled by a stage. It should never be in two places at once.
You definitely get what I'm saying, so I'm at least not smoking too much wacky weed :)
Eric
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Tue Feb 24, 2004 10:30 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | I'm going to try this with one of my work queues. I've got two queues, one
high priority and one low priority. I'll try putting higher priority
threads on one, then try putting more threads on instead. I'll report back
later...
|
Please let us know.
Even on a single-cpu machine, a small number of threads (2 to 4) should exhibit faster performance
than a single thread for /anything/ not CPU bound.
Eric
|
|
| Back to top |
|
 |
Ritchie Annand Guest
|
Posted: Wed Feb 25, 2004 9:59 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
In article <403bd013$1 (AT) newsgroups (DOT) borland.com>, [email]eric (AT) ijack (DOT) net[/email] says...
| Quote: | Agreed. I do think that (as in the traditional sense) the PID loop
would really need to be tuned by the developer.
Something like:
with Stage.Parameters do begin
ScalingPercent := 20; // 20%
ResetTime := 30000; // 30 seconds
ReactionTime := 120000; // 120 seconds
end;
|
One thing I was going to do at some point for my own purposes was to put
a lot more instrumentation into a derivative of my thread pool to do
some similar balancing there; they're structured in such a way that it
would be relatively easy to determine how "busy" they are, both in the
threads themselves (how long in calls for each versus total time) and in
the incoming queue (is it growing or shrinking?) and step up and down
the thread count accordingly.
Can't think of what a proper PID loop would look like, though. Perhaps
it *is* an art to putting together the feedback... I'd have to make some
combination of queue size (positive pressure on thread count... but only
to a point; too many threads could gum up the works), thread busy-ness
(positive pressure on thread count... until the point where adding the
thread takes up enough system resources to make each thread *busier*),
and thread count itself (slight negative pressure to reduce it to a
proper norm).
Hmmmm, I could see the feedback loops getting out of hand. A hard limit
would help, but I could see thread count wanting to increase from the
pressure of the queue size and thread business, even though that makes
things even busier. Would PID ameliorate that? Kick it towards a local
minimum?
| Quote: | So something would go and feed each method something from the
appropriate input queue for that state?
Exactly.
|
Excellent, I understood at last ;)
| Quote: | The worker threads would pick up a task in the input queue and feed it
into the stage handler. The stage would be responsible for setting the
next stage, which could be "finished" or "terminate caller".
|
Yep, I can visualize that fairly easily My early Task experiments did
something *very* similar to that. They were designed to be single-
thread-at-a-time, but that was mostly just a matter of where to put
state (I passed in an interface to the shared data to work on, but that
data was hosted by my stage handler 'ICORETask'). They'd set what the
next stage (I even had them called ICORETaskStage) was and then drop
out.
I didn't have the stages as methods on the same object, though, I had
them as separate classes that got passed in state and accessors to the
other stages, but either approach would work :)
| Quote: | As long as they had some sort of context passed into them that couldn't
be called by multiple things at the same time.
The context would really be the work item. The work item will either
be waiting in a queue, or being handled by a stage. It should never
be in two places at once.
|
*nod* That should work fairly well. I'm trying to think if there might
be circumstances where enough transformation has happened that the stage
might want to consume the work item and emit a *different* one (with the
same ID as the consumed one so that the work gets back to the right
spot). *shrug* Maybe, maybe not.
| Quote: | You definitely get what I'm saying, so I'm at least not smoking too
much wacky weed
|
*laugh* Either that or we both are :)
I got inspired initially from reading about the academic Sandstone Web
Server project (which sounds in many ways like the architecture you were
thinking of) - what most appealed to me was having a way around the two
major architectures: the single-thread-delegates-every-call model (even
if duplicated), and the new-thread-for-every-request model. Something
in-between that could be tweaked and balanced and scaled.
What was your original inspiration? :)
| Quote: | Eric
- the half a bee |
-- Ritchie Annand
Senior Software Architect
http://www.malibugroup.com
http://nimble.nimblebrain.net
http://wiki.nimblebrain.net
|
|
| Back to top |
|
 |
Eric Hill Guest
|
Posted: Thu Feb 26, 2004 6:47 am Post subject: Re: SEDA and PID Random Thoughts |
|
|
| Quote: | One thing I was going to do at some point for my own purposes was to put
a lot more instrumentation into a derivative of my thread pool to do
some similar balancing there; they're structured in such a way that it
would be relatively easy to determine how "busy" they are, both in the
threads themselves (how long in calls for each versus total time) and in
the incoming queue (is it growing or shrinking?) and step up and down
the thread count accordingly.
|
The PID loop should really be set to tune one specific parameter (i.e.
thread count or queue maximum size) based on one specific criteria (i.e.
queue flow rate, average time in stage, etc.). Increase the thread count to
process work faster. Reduce the thread count to speed up the stage
execution time. Increase the maximum queue size when a burst of traffic
comes in, and reduce it when done to conserve memory.
| Quote: | Can't think of what a proper PID loop would look like, though. Perhaps
it *is* an art to putting together the feedback... I'd have to make some
combination of queue size (positive pressure on thread count... but only
to a point; too many threads could gum up the works), thread busy-ness
(positive pressure on thread count... until the point where adding the
thread takes up enough system resources to make each thread *busier*),
and thread count itself (slight negative pressure to reduce it to a
proper norm).
|
You really want (as a developer) to define one specific input and one
specific output. Too many variables make tuning nearly impossible.
Side note: You should try tuning pressure PID loops with eight 50,000GPM
pumps in parallel, head flow valves on each, tail flow valves on each, and a
tail aggregate valve. You want to ramp up pumps one at a time, not cause
cavitation by reverse water flow, maintain a constant output pressure (so
you don't rupture crappy pipes all over the city), and not run the supply
reservoir out of water. Now THAT project was a PITA! Trust me, you REALLY
don't want to introduce a slew of variables.
| Quote: | Hmmmm, I could see the feedback loops getting out of hand. A hard limit
would help, but I could see thread count wanting to increase from the
pressure of the queue size and thread business, even though that makes
things even busier. Would PID ameliorate that? Kick it towards a local
minimum?
|
I would start by adjusting the derivitave so the system reacted slower to
the bursts. Burst traffic can queue up without issue - that's the point of
the queue. You're really wanting to equalize the sustained traffic rate,
not the burst traffic rate. I'd set the error condition to be the
percentage of running threads to maximum number of threads combined with the
input queue size. As the input queue size grows and STAYS large (sustained
traffic), the PID loop would increase the thread-count by one and wait
another 30 seconds to see what happens.
| Quote: | I didn't have the stages as methods on the same object, though, I had
them as separate classes that got passed in state and accessors to the
other stages, but either approach would work
|
It really depends on the size of your state machine. Anything more than a
few pages of code should be separated for readability. [Insert standard
2/100ths of a Dollar here]
| Quote: | *nod* That should work fairly well. I'm trying to think if there might
be circumstances where enough transformation has happened that the stage
might want to consume the work item and emit a *different* one (with the
same ID as the consumed one so that the work gets back to the right
spot). *shrug* Maybe, maybe not.
|
I guess it's possible to have a single stage emit two work items - I hadn't
thought of that. Good idea.
| Quote: | You definitely get what I'm saying, so I'm at least not smoking too
much wacky weed :)
*laugh* Either that or we both are
|
<g>
| Quote: | What was your original inspiration?
|
Several days after reading the SEDA white paper, I was sitting at work
staring at a different problem (one that involved work queues however) and
was trying to explain the garden-hose analogy to a coworker. As I was
making very silly motions with my hands about hooking up another hose (a new
thread to the bundle of existing hoses) to increase data flow, the idea of
using a PID control loop to control flow (as I had done quite literally in a
previous job) just "popped in there". It was definitely a "eureka" moment.
I politely dropped what I was doing and went back to my desk where I keep a
nice pad of Post-It notes and a box of el-cheapo Bic pens. I think
better in yellow... <G>
| Quote: | Eric
- the half a bee
|
?
|
|
| Back to top |
|
 |
Bryan Crotaz Guest
|
Posted: Thu Feb 26, 2004 6:35 pm Post subject: Re: SEDA and PID Random Thoughts |
|
|
"Eric Hill" <eric (AT) ijack (DOT) net> wrote
| Quote: | I'd be rather careful with that! If traffic always come in bursts,
evenly spaced in time, you will ramp up more than down all the time,
quickly saturating the system.
Obviously there would have to be a minimum and maximum "worker" count.
I'm thinking more of the
reactive portion of the PID loop. You would react more for positive
errors, and less for negative
errors, so you would ramp to your maximum faster than you offramp to your
minumum.
I'm really enjoying this idea as you can tell...
|
Sounds to me like
numberOfThreads = fn(queue length)
where fn may be linear but more likely inverse exponential.
Bryan
|
|
| Back to top |
|
 |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
|