Christopher Browne wrote:
Christopher Browne wrote
I whiteboarded a couple of attempts at algorithms for this, this
afternoon. It needs a bit more thought, I think, to come up with
something final...
Here's what I have at this point...
The notion that seems to make sense, here, is to construct all of the
possible maximum-length paths from each origin. Note that this is a
loose mix of C-like and pl/pgsql-like code; I'm not yet expecting it to
be exactly right...
<snipped algorithm>
That gives us a list of all the longest possible traversals.
Hm.. I don't really understand that algorithm (But, then, maybe
if've just been up for too long now.. ;-) ). Where is that
quantity-value coming from, and what does it do?
In the meantime I've coded up something myself. My first attempt
was to generate all traversals (not just the ones with maximum length),
and store them in a table (I used an array-valued field instead of a
second table vpath, but thats just a detail). This seems to work, basically,
but performance was horrible (For a fully-meshed graph with 10 nodes,
it would need to generate 10! (10 faktorial = 10*9*...*1) entries... :-(
Therefore, I came up with another idea. Here it is, in pseudocode.
foreach node as x
foreach possible provider of x as y
Temporarily remove x from the graph
zs <- All nodes that are somehow connected to y, via one or more nodes
foreach node in zs as z
If x subscribes a set from z with provider != z
do nothing
else
Add (receiver=x, provider=y, origin=z) to sl_listen.
The idea is that, if I want to figure out if a node x can use
a neighbour y as a provider for events from some node z, I have
to check if y can receive events from z assuming the node x doesn't even
exists. If it can, than y is used as a provider, otherwise it is not.
Attachted is a sql-script that creates a few tables, creates two functions
that implement this algorithm in plpgsql. Below the functions there a few
testcases. It uses it's own tables, with different names than slony for now,
because this made the development and testing easier.
create_listen contains the 3 nested for-loops, while the set-valued function
reachable_from(starting_node, nodes_to_ignore) check with nodes are reachable
from the starting_node when the nodes in nodes_to_ignore are, well, ignored ;-)
I used the columns src, dst and via instead of origin, receiver and provider (
Or src and dst instead of server and client in the case if sl_path).
Does anyone see a case where this would fail? If not, I'll try to
fit this into slony, and see if it workes for my case.
*Maybe* at this point, we remove the traversals that contain cases where
a node is subscribing to a set originating from the origin, but that
goes around the shaping of the subscription sets. Possibly that could
get handled in the loop where the feasible paths were being selected...
We then walk backwards through them to generate listener entries; I'll
not bother looking at that until proper holes have been shot in the above...
greetings, Florian Pflug
--Remove Stuff
drop table subscribe ;
drop table listen ;
drop table path ;
--Create tables
create table path (
dst int4 not null,
src int4 not null,
primary key (dst, src)
) ;
create table listen (
dst int4 not null,
via int4 not null,
src int4 not null,
primary key (dst, via, src),
foreign key (dst, via) references path (dst, src) on delete cascade on
update cascade
) ;
create table subscribe (
dst int4 not null,
via int4 not null,
src int4 not null,
set int4 not null,
primary key (dst, set),
foreign key (dst, via) references path (dst, src) on delete cascade on
update cascade
) ;
--Create functions
-- Find all nodes that v_node can receive events from without (directly or
indirectly)
-- using the nodes in v_blacklist.
create or replace function reachable_from(int4, int4[]) returns setof int4 as '
declare
v_node alias for $1 ;
v_blacklist alias for $2 ;
v_ignore int4[] ;
v_reachable_edge_last int4[] ;
v_reachable_edge_new int4[] default \'{}\' ;
v_src record ;
begin
v_reachable_edge_last := array[v_node] ;
v_ignore := v_blacklist || array[v_node] ;
return next v_node ;
while v_reachable_edge_last != \'{}\' loop
v_reachable_edge_new := \'{}\' ;
for v_src in select src as node
from path
where dst = ANY(v_reachable_edge_last) and src !=
ALL(v_ignore)
loop
if v_src.node != ALL(v_ignore) then
v_ignore := v_ignore || array[v_src.node] ;
v_reachable_edge_new := v_reachable_edge_new ||
array[v_src.node] ;
return next v_src.node ;
end if ;
end loop ;
v_reachable_edge_last := v_reachable_edge_new ;
end loop ;
return ;
end ;
' language 'plpgsql' stable ;
-- Creates listen entries, based on the idea that v_dst should listen on v_via
-- for events from v_src if, and only if, v_via can receive events from v_src
-- without using node v_dst.
create or replace function create_listen() returns void as '
declare
v_dst record ;
v_via record ;
v_src record ;
v_reachable int4[] ;
begin
truncate listen ;
for v_dst in select src as node from path union select dst as node from
path loop
for v_via in select src as node from path where dst =
v_dst.node loop
for v_src in select * from reachable_from(v_via.node,
array[v_dst.node]) as r(node) loop
perform 1 from subscribe where
dst = v_dst.node and via != v_via.node
and src = v_src.node ;
if not found then
insert into listen (dst, via, src)
values (v_dst.node, v_via.node, v_src.node) ;
end if ;
end loop ;
end loop ;
end loop ;
return ;
end ;
' language 'plpgsql' volatile ;
--Some helpers for the test below
create temporary table nodes (id int4 not null primary key) ;
copy nodes (id) from stdin ;
1
2
3
4
5
6
7
8
9
10
\.
--Test1
-- 21 <-> 20 <-> 1 <-> 10 <-> 11
delete from path ;
copy path (dst, src) from stdin ;
1 10
1 20
10 1
10 11
11 10
20 1
20 21
21 20
\.
copy subscribe (set, dst, via, src) from stdin ;
10 11 10 10
20 21 20 20
\.
\timing
select create_listen() ;
\timing
select dst, via, src from listen order by dst, via, src ;
--Test2
-- 2 <-- 1 --> 4
-- | ^ |
-- | / \ |
-- v / \ v
-- 3 5
delete from path ;
copy path (dst, src) from stdin ;
1 3
1 5
2 1
3 2
4 1
5 4
\.
\timing
select create_listen() ;
\timing
select dst, via, src from listen order by dst, via, src ;
--Test3
--Fully meshed setup with 10 nodes
delete from path ;
insert into path (dst, src)
select n1.id, n2.id
from nodes n1, nodes n2
where n1.id != n2.id ;
\timing
select create_listen() ;
\timing
select dst, via, src from listen order by dst, via, src ;
--Test4
--A transitiv graph with 10 nodes
--This should warn about unreachable nodes
delete from path ;
insert into path (dst, src)
select n1.id, n2.id
from nodes n1, nodes n2
where n1.id < n2.id ;
\timing
select create_listen() ;
\timing
select dst, via, src from listen order by dst, via, src ;
--Test5
--A (nearly) transitiv graph with 10 nodes, but with the missing
--connection (1 -> 10) added.
delete from path ;
insert into path (dst, src)
select n1.id, n2.id
from nodes n1, nodes n2
where n1.id < n2.id ;
insert into path (dst, src) values (10, 1) ;
\timing
select create_listen() ;
\timing
select dst, via, src from listen order by dst, via, src ;
_______________________________________________
Slony1-general mailing list
[email protected]
http://gborg.postgresql.org/mailman/listinfo/slony1-general
