Thu Mar 2 19:25:41 PST 2006
- Previous message: [Slony1-general] Listen path generation and bug 1485
- Next message: [Slony1-general] Listen path generation and bug 1485
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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 -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: dolisten.sql Url: http://gborg.postgresql.org/pipermail/slony1-general/attachments/20060303/812fcccb/dolisten-0001.ksh
- Previous message: [Slony1-general] Listen path generation and bug 1485
- Next message: [Slony1-general] Listen path generation and bug 1485
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the Slony1-general mailing list