On 06/17/2015 02:15 PM, Ludwig Krispenz wrote:

## Advertising

On 06/17/2015 02:04 PM, Petr Vobornik wrote:With patch "878 topology: check topology in ipa-replica-manage del" we can use the same logic for POC of ipa topologysuffix-verify command. Checks done: 1. check if the topology is not disconnected. In other words if there are replication paths between all servers. 2. check if servers don't have more than a recommended number of replication agreements (which was set to 4) I'm not sure what else we want to test but these two seemed as low hanging fruit.don't know how hard it is, but I had thought of calculating something like a "degree of connectivity", eg to find single points of failure. In a topology A <--> B <--> C <--> D, if B or C are down (temporariliy) the topology is disconnected. If extending to A <--> B <--> C <--> D <--> A one server con be taken offline, so a brute force would be to check for each server if it could be removed

`The original POC(attached) of the graph traversal did such brute force`

`check(only one server removed at a time). In other words, it's easy.`

Computing indegree and outdegree of each node is easy as well.

Additional checks can be also added later. https://fedorahosted.org/freeipa/ticket/4302

-- Petr Vobornik

#!/usr/bin/python # Python Breath First Search # # Intendted for FreeIPA topology check # structure of segment: # # edges: # # topologysegment # - cn # - iparepltoposegmentrightnode # - iparepltoposegmentdirection # - iparepltoposegmentleftnode # # # vertices: # masters # - cn class Graph(): """ Simple graph structure with vertices, edges and adjectency list """ vertices = set() edges = [] adj = dict() def add_vertex(self, vertex): self.vertices.add(vertex) self.adj[vertex] = [] def add_edge(self, left, right): self.edges.append((left, right)) self.adj[left].append(right) def remove_vertex(self, vertex): self.vertices.remove(vertex) # delete adjacencies del self.adj[vertex] for key, adj in self.adj.iteritems(): adj[:] = [v for v in adj if v != vertex] # delete edges edges = [e for e in self.edges if e[0] != vertex and e[1] != vertex] self.edges[:] = edges def bfs(graph, start=None): if not start: start = list(graph.vertices)[0] visited = set() queue = [start] while queue: vertex = queue.pop(0) if vertex not in visited: visited.add(vertex) queue.extend(set(graph.adj.get(vertex, [])) - visited) return visited def make_graph(servers, segments): graph = Graph() for s in servers: graph.add_vertex(s) for s in segments: direction = s[2] if direction == 'both': graph.add_edge(s[0], s[1]) graph.add_edge(s[1], s[0]) if direction == 'left-right': graph.add_edge(s[0], s[1]) if direction == 'right-left': graph.add_edge(s[1], s[0]) return graph def print_results(errors): if not errors: print "Initial topology is in order. All servers can replicate" else: print "Initial topology has some errors" print_errors(errors) def print_results_removed(removed, errors): if not errors: print removed + " is safe to remove" else: print removed + " is not safe to remove" print_errors(errors) def print_errors(errors): for e in errors: print e[0] + " can't contact: " + ', '.join(e[2]) def iterate_start(graph): servers = list(graph.vertices) servers.sort() e = [] for s in servers: visited = bfs(graph, s) not_visited = set(servers) - visited if not_visited: e.append((s, visited, not_visited)) return e def test(): servers = {'a', 'b', 'c', 'd'} # left, right, direction segments = [ ('a', 'b', 'both'), ('b', 'd', 'both'), ('a', 'd', 'right-left'), ('c', 'd', 'right-left'), ('c', 'd', 'left-right'), ] g = make_graph(servers, segments) visited = bfs(g) not_visited = servers - visited print "" print "===== all servers =======" errors = iterate_start(g) print_results(errors) for s in servers: g = make_graph(servers, segments) g.remove_vertex(s) print "" print "===== removing: " + s + " =======" errors = iterate_start(g) print_results_removed(s, errors) test()

-- Manage your subscription for the Freeipa-devel mailing list: https://www.redhat.com/mailman/listinfo/freeipa-devel Contribute to FreeIPA: http://www.freeipa.org/page/Contribute/Code