Hi,

I'm working on a project in which database will support
the execution of several algorithms and applications.

The structure will be as follows: a master which knows what
to do has access to a major database (several TB), and
several children that will process a task (with a small dataset
of at most some tens of MB). The master assigns a few (say 100)
nodes to a task and groups them and delivers data. To reduce
complexity of the algorithm, children are grouped tree like. A
database is considered for delivering data to the processing
nodes, because of the easy to use interface and data storage
options.

Before going to my ideas, a few general questions:
Where would you place the database(s), if you'd use one?
Processing has to be as fast as possible, so what
kind and which database would you use?
How would data be available (distributed) over the nodes?

In the current design/idea, the nodes will all have a
main-memory database. Initial distribution of data
will be initialized by the master and spread to all
the child groups, these groups spread it further until
the last child has reached. Data is then processed
at the child node, and then probably the transactions
log will be given back to the parent. The parent should
wait until all children are ready, and then merge the data
received from all it's children, process it, and send it to
it's parent. The merging should probably have something
of a conflict detection of somekind (ideas?). What (replication)
technique could be use to distribute data to parents. Maybe
locking should also be introduced on all the nodes seperately or
distributed.
As far as I could see there are not many (if one) products
(commercial or open source), that can do replication along
trees, merge replication (of some kind) at each parent node,
be very fast, and generate little overhead.

Any one ideas, suggestions, are whatever in this matter?

Before anyone suggests clustering software (Rocks, Oscar, etc),
it won't do. It's too static for the algorithms used, and
intensive data exchange is needed.

greetings,
Bram

Bram Wiekens wrote:

I'm not sure that a tree is the best structure. I would be inclined to
put all the nodes in a great big queue such that when tasks are executed
they join and when tasks are assigned they leave. I can see a tree
structure being too rigid in terms of the way that the problems are
split down for the children.


Surely this is more like a server than a database. The server reads from
the database and communicates with the processing nodes.

Just one big one.

That depends on your budget. And what type of transactions you are
doing. You can get databases costing millions of $. Don't store anything
in the node, just send them problems and wait for solutions.

If you get rid of this tree structure you wouldn't need distributed
control. One controller could manage task assignment, verification and
combination. If this gets too intensive then you could introduce tiers,
but hopefully combination of solutions is trivial compared to
calculation of solutions.

Having read the first part of your post again, if this system is being
designed to perform *one* particular algorithm ("To reduce complexity of
the algorithm") the solution could be improved hugely by designing the
whole cluster around it. You could predict how long each stage would
take and hard-code roles and responsibilities arount that. You could
even include huge amounts of caching and precomputation to allow nodes
to obtain better average case performance.

John

Bram Wiekens wrote:

I generally agree with what John posted in another
followup to this. But have one pointed
question, below

"As fast as possible" is not a number. What
are the specific quantified requirements for
whatever it is that you're doing? Must the
result be available in one hour, one minute,
one second, one millisecond?

If it's one hour, then many designs can work.
If it's one millisecond, than none may work.

You need a specific target to shoot at.

The answer, whenever possible, should be tied
to the business needs.

[SNIP rest]

NPL

--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch

Thanks for your comments, but let me deepen the discussion
a little.

John wrote:

The structure of the tree will be depending on the kind of algorithm
performed. The master node selects and groups a series of nodes,
where groups and numbers are dynamic. Wouldn't this imply a
quite flexible solution?

The nodes themselves should communicate with the data supplier instead of
a server. The server only should do the initial delivery of data, this
is to reduce traffic and overhead. Only in a last phase data (solutions)
should be returned to the server.

The budget is quite thight, a test set up of ten cots systems is used,
in real use about 500 cots machines will be used, requiring a cost-effective
solution for data distribution (local or central organized).

The main reason to use the tree structure, is because
of the different levels of abstraction you could use. Starting
at a high level a the top of the tree, to a very basic level
at the roots. Splitting it up at once would still make it complex.
But maybe the flat model could be considered.

This is the reason why cluster software isn't used. There are several
applications and algorithms that have to be run. All require a different
set up of the cluster. And most algorithms, like self calibration, don't
have very strict time measures. This will makes predicition a little harsh,
a my opion


Bram

You're right about setting a possible target, but that's
a little hard. Let me explain why. The main thing is that
data is distributed,processed, brought back and stored.
The processing with one algorithm takes in the current single
node configuration some days to perform. In the cluster
configuration it's should be reduced a matter of minutes.
So there isn't a strict timeline, in sense of every millisecond
there has to be a result. But the longer it takes to toss the
data around the longer one has to wait. That is what has to
be reduced.

Bram

Nick Landsberg wrote:

Bram Wiekens wrote:

OK, understood.

You currently have something which takes "days."

You mentioned that the data consists of several
Terabytes. (Not unusual nowadays.) Assuming
nothing else was happening on the database at
the same time, how long would it take to read
this data from disk? Even before shipping it
out to the rest of the cluster? Do you
need to read in *all* the data to start your
computations? You should be able to read some
chunk and ship it to some other processor in the
cluster while reading more on the master.

I have strong doubts that >1 TB of data can be read
from disk in under an hour, but have no hard data
to substantiate that. Note that this is not
transfer rate, but read rate from a mechanical
device (or devices in the case of RAID arrays).
Run a benchmark on that first, because
the absolute minimum time would be the
time it takes to read all the data from the disks.

Unless you're doing real heavyweight algorithmic
processing, in my opinion the disk I/O time
will dominate the total time spent.

My best guess at this point in time is that you
will wind up with about 5-15 hours of processing
time. Most of it doing disk I/O. Plus there's
the added time to write it back to the disks,
and that's something you have to consider too.
(Processor "x" may have finished it's computations
on its subset of the data before you finished
reading all the data and now needs to write
it back to the database. This will slow
down the reads for the data destined for
processor "x+17" or whatnot.)

Unsolicited advice: don't give your customer or
boss the impression that it will take "only a few
minutes" until you have verified that I/O to disk
can be done in "only a few minutes".

NPL

P.S. - now that I think about it, I contradicted
myself in the post below. It looks like even
for a 1 hour requirment, no designs may work.
Oh, well.

--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch

Yeah, reading the full set of TB's from disk would take
too much time, you're quite right about that.
But that won't be the case. To clear it up a little
the database that contains several TB is just a storage
device that contains measured data. The master node
takes out a chunk, that just a few MB in size and at
most a few tens of MB in size, that will be processed.
So just a small amount of data (far below 100 MB) will
be tossed around, that's why the idea of an main-memory
database at the nodes arose. Those nodes just do computation
the grand result isn't stored in the cluster but in another
storage device, possibly database.

Bram

Nick Landsberg wrote:

Bram Wiekens wrote:

This is going to be hard to do. The algorithm will have to be specified
in a very specific fashion. I would be inclined to package each
algorithm in some sort of software module that specifies the cluster
configuration. The server could then load this "meta-algorithm",
configure the cluster and commence operation.

The other operation is creating each algorithm's implementation in some
custom way such that the database operations are specified for each
operation. You could then allow some "intelligent" module to configure
the cluster for optimal performance based on the operations used by the
algorithm. Again, without knowing what you are trying to implement
(which algorithm), I'd struggle to recommend the best solution. The tree
structure seems too specific to operate in a near-optimal fashion for
arbitrary algorithm implementations.

I would link the data supplier (conceptually) to the server, since
otherwise you'll end up with awkward control distribution. If you end up
accessing the data direct from the data supplier eventually, that's
fine, as long as the server is specifying how and when this is done.

I don't understand what you mean by "abstraction" in this context. I can
see how a tree can have hierarchical control, but this is going to cause
you issues in balancing load to children of each node. Surely it can't
have "roots". If you have more than one conceptual root, you will end up
with chaotic distributed control I think.


If you can split the algorithm into sub problems of a specified size
then you can reason (in either worst case or average case) about the
*relative* time taken by sub problems to execute in terms of the
sub-problem instance size. If you split the problems up willy-nilly,
then the cluster, /particularly if tree-structured/ will end up with
nodes sitting idle while a particularly hard problem gets calculated by
some unfortunate node.

John

One of the algorithms used is a selfcalibrating algorithm,
which ensures that the systems won't process trash. This is
quite a complex algorithm which I cannot write down here,
but it calibrates on the data is processes.
The first node knows how the algorithm is build and therefore
know how it can split up the workload.

Bram

John wrote:

Ok, I've checked it all again, so I'm a little more
aware of the situation now. Until now I had little
insight in the working of the algorithm. So I'm
slightly less confused now.. ;-)

The timing constraints are indeed important, as suggested.
The algorithm is a heuristic selfcalibrating algorithm for
a processing environment and tries to search the most ideal
situation (eliminating noise etc). What should be done is:
Send data to all nodes in the cluster, and the nodes get
a specific amount of time to compute this data. The only
difference between the nodes is the parameterset they get.
Then some node will decide (compute) which node has the best
result. This will be the calibrating parameters.

This is why I propose the three structure, it avoids
great message distribution in an all to all structure
(stronger knowledge of who is all isn't always available)

In general the systems do their work almost solitair.
And dataset/message exchange should be minimized, because
it gives overhead.

So again do you think think the tree structure would suffice,
or would another structure do a better job?
A Centralized database would probably congest
(alltough it's a pretty fast) network connection between the machines,
and a lot of versioning has to be done, to compare all different results.


Bram