解决云服务中的多对多分组问题 - 二分图的社区发现算法

作者：朱国庆

本文介绍一种高效的二分图社区发现算法biLouvain，以云服务中的多对多关系的分组问题为例，分析这类算法的使用方法和效果。

01

背景

在基于XEN的云服务环境中，一个SAAS服务的Pod可能包含十多个VM。这些VM，可能运行于一个Dom0上，也可能运行于多个Dom0上。所以，Pod和Dom0是一个多对多的关系（如下二分图所示）。本文提供一种方式，基于二分图的社区发现算法biLouvain，对Dom0进行最小化自动分组，使得在Dom0中的操作对同一个Pod干扰次数尽量少（最佳是一次）。

02

Dom0的社区发现

我们首先把Dom0分组，每个组叫做一个社区。每个社区内的Dom0和DomU相比社区外的Dom0和DomU有更紧密的联系。所以社区可以被看作是互相独立互不依赖的。

通过工具biLouvain，Dom0社区和Pod社区可以被自动发现识别出来。运行结果类似于：

Community 0[V1]: Dom0_0,Dom0_1,Dom0_6 Community 1[V1]: Dom0_2 Community 2[V1]: Dom0_3,Dom0_7 Community 3[V1]: Dom0_4,Dom0_5 Community 4[V2]: Pod_3 Community 5[V2]: Pod_5,Pod_8 Community 6[V2]: Pod_0,Pod_1,Pod_2,Pod_6 Community 7[V2]: Pod_4,Pod_7

下图显示为相同颜色的Dom0或者Pod被划分到相同的社区：

03

一个生产环境中的例子

某数据中心在一次周末维护升级中所有涉及到的Dom0/DomU/Pod列表文件存在CIS-45691目录下。

（1）拷贝domu_dom0_list和domu_pod_list两个文件。这两个文件分别提供了本次升级中DomU和Dom0的对应关系，以及DomU和Pod的对应关系。通过domu_dom0_list文件的行数，我们可以看到本次升级总共有1304个DomU以及285个Dom0.

[root@bej301365 CIS-45691]$ pwd /root/biLuvain/CIS-45691 [root@bej301365 CIS-45691]$ scp root@bej301545:/fsnadmin/aia/occn-jira/CIS- 45691/domu_dom0_list . [root@bej301365 CIS-45691]$ scp root@bej301545:/fsnadmin/aia/occn-jira/CIS- 45691/domu_pod_list .

[root@bej301365 CIS-45691]$ head domu_dom0_list cfclc1r312dmvr01.X.com,cfclmd0343.X.com cfclc5r204dmvr01.X.com,cfclmd0441.X.com cfclc5r209dmvr01.X.com,cfclmd0518.X.com cfclc5r410dmvr01.X.com,cfclmd0156.X.com cffar12040101.X.com,cfclmd0452.X.com cffar12040102.X.com,cfclmd0452.X.com cffar12040103.X.com,cfclmd0452.X.com cffar12040104.X.com,cfclmd0455.X.com cffar12040105.X.com,cfclmd0455.X.com cffar12040106.X.com,cfclmd0455.X.com

[root@bej301365 CIS-45691]$ head domu_pod_list cffar12040101.X.com,EBQDDEV-TEST cffar12040102.X.com,EBQDDEV-TEST cffar12040103.X.com,EBQDDEV-TEST cffar12040104.X.com,EBQDDEV-TEST cffar12040105.X.com,EBQDDEV-TEST cffar12040106.X.com,EBQDDEV-TEST cffar12040107.X.com,EBQDDEV-TEST cffar12040109.X.com,EBQDDEV-TEST cffar12040111.X.com,EBQDDEV-TEST cffar12040201.X.com,EBPQ

（2）根据上面两个文件产生Dom0和Pod的映射文件dom0_pod_list

## Note: dom02pod.py specifies the pod as "NOT_ANY_POD" on those Dom0s without Pod found

[root@bej301365 CIS-45691]$ cat dom02pod.py #!/usr/bin/env python import csv def get_pod_of_domu(domu): with open('domu_pod_list', 'r') as domu_pod_file: domu_pod_reader = csv.reader(domu_pod_file) for row in domu_pod_reader: if row[0] == domu: return row[1] with open('domu_dom0_list', 'r') as domu_dom0_file: with open('dom0_pod_list', 'a') as dom0_pod_file: domu_dom0_reader = csv.reader(domu_dom0_file) domu_pod_writeer = csv.writer(dom0_pod_file) for row in domu_dom0_reader: dom0 = row[1] pod = get_pod_of_domu(row[0]) if not pod: pod = "NOT_ANY_POD" domu_pod_writeer.writerow([dom0, pod])

[root@bej301365 CIS-45691]$ python dom02pod.py

[root@bej301365 CIS-45691]$ head dom0_pod_list cfclmd0343.X.com,NOT_ANY_POD cfclmd0441.X.com,NOT_ANY_POD cfclmd0518.X.com,NOT_ANY_POD cfclmd0156.X.com,NOT_ANY_POD cfclmd0452.X.com,EBQDDEV-TEST cfclmd0452.X.com,EBQDDEV-TEST cfclmd0452.X.com,EBQDDEV-TEST cfclmd0455.X.com,EBQDDEV-TEST cfclmd0455.X.com,EBQDDEV-TEST cfclmd0455.X.com,EBQDDEV-TEST

（3）去除掉重复的记录并产生新的列表文件dom0_pod_list.uniq

[root@bej301365 CIS-45691]$ cat dom0_pod_list | sort | uniq > dom0_pod_list.uniq

[root@bej301365 CIS-45691]$ head dom0_pod_list.uniq cfclmd0033.X.com,HCKD cfclmd0033.X.com,HCKD-TEST cfclmd0034.X.com,NOT_ANY_POD cfclmd0035.X.com,NOT_ANY_POD cfclmd0036.X.com,CAUU cfclmd0036.X.com,CAYU cfclmd0036.X.com,HCKD cfclmd0037.X.com,CAYU cfclmd0037.X.com,HCKD cfclmd0038.X.com,NOT_ANY_POD

（4）运行biLouvain并产生结果

[root@bej301365 CIS-45691]$ cd /root/biLuvain/biLouvain-master/ [root@bej301365 biLouvain-master]$ mkdir dom0_pod_test [root@bej301365 biLouvain-master]$ cd dom0_pod_test [root@bej301365 dom0_pod_test]$ cp /root/CIS-45691/dom0_pod_list.uniq . [root@bej301365 dom0_pod_test]$ ../src/biLouvain -i dom0_pod_list.uniq -d "," [root@bej301365 CIS-45691]$ ls -l dom0_pod_list_bipartite_ResultsCommunities.txt -rw-r--r-- 1 root root 16079 Aug 13 04:00 dom0_pod_list_bipartite_ResultsCommunities.txt

（5）由于我们升级的批次是按照Dom0来划分，我们只需要关注结果中的Dom0社区。

Community 0[V1]: cfclmd0034.X.com,cfclmd0035.X.com,cfclmd0038.X.com,cfclmd0042.X.com,cfclmd0044.X.com,cfclmd0060.X.com,cfclmd0071.X.com,cfclmd0073.X.com,cfclmd0079.X.com,cfclmd0080.X.com,cfclmd0081.X.com,cfclmd0156.X.com,cfclmd0165.X.com,cfclmd0166.X.com,cfclmd0319.X.com,cfclmd0320.X.com,cfclmd0321.X.com,cfclmd0343.X.com,cfclmd0345.X.com,cfclmd0347.X.com,cfclmd0358.X.com,cfclmd0360.X.com,cfclmd0363.X.com,cfclmd0366.X.com,cfclmd0371.X.com,cfclmd0440.X.com,cfclmd0445.X.com,cfclmd0460.X.com,cfclmd0462.X.com,cfclmd0463.X.com,cfclmd0465.X.com,cfclmd0507.X.com,cfclmd0509.X.com,cfclmd0519.X.com,cfclmd0520.X.com,cfclmd0663.X.com,cfclmd0665.X.com Community 1[V1]: cfclmd0033.X.com,cfclmd0036.X.com,cfclmd0037.X.com Community 2[V1]: cfclmd0041.X.com Community 3[V1]: cfclmd0045.X.com,cfclmd0046.X.com,cfclmd0047.X.com,cfclmd0048.X.com,cfclmd0049.X.com

......

Community 68[V1]: cfclmd0659.X.com,cfclmd0660.X.com Community 69[V1]: cfclmd0664.X.com Community 70[V1]: cfclmd0666.X.com,cfclmd0667.X.com,cfclmd0668.X.com,cfclmd0669.X.com Community 71[V1]: cfclmd0661.X.com,cfclmd0671.X.com,cfclmd0672.X.com,cfclmd0673.X.com,cfclmd0674.X.com,cfclmd0675.X.com

我们可以看到根据biLouvain算法，285个Dom0被划分成了72个社区。

（6）基于Python的networkx和matplotlib库我们可以画出社区划分的结果图。

import networkx as nx import matplotlib.pyplot as plt from random import random def get_dom0_partition(file): partition = {} with open(file, 'r') as fd: for line in fd: line = line.strip() if line and "[V1]" in line: com = int(line.split()[1].split("[")[0]) dom0s = line.split()[2].split(",") for dom0 in dom0s: partition[dom0] = com return partition def get_edgelist(file): edge_list = [] with open(file, 'r') as dom0_pod_file: dom0_pod_reader = csv.reader(dom0_pod_file) for row in dom0_pod_reader: edge_list.append((row[0],row[1])) return edge_list def set_size(w,h, ax=None): """ w, h: width, height in inches """ if not ax: ax=plt.gca() l = ax.figure.subplotpars.left r = ax.figure.subplotpars.right t = ax.figure.subplotpars.top b = ax.figure.subplotpars.bottom figw = float(w)/(r-l) figh = float(h)/(t-b) ax.figure.set_size_inches(figw, figh) edge_list = get_edgelist("/root/biLuvain/CIS-45691/dom0_pod_list") left,right = set(),set() for s,t in edge_list: left.add(s) right.add(t) G = nx.Graph() G.add_nodes_from(list(right), bipartite=0) G.add_nodes_from(list(left), bipartite=1) G.add_edges_from(edge_list) partition = get_dom0_partition("/root/biLuvain/CIS-45691/dom0_pod_list_bipartite_ResultsCommunities.txt") size = float(len(set(partition.values()))) pos = nx.spring_layout(G,k=0.07) #pos = nx.random_layout(G) #l,r = nx.bipartite.sets(G) #pos = {} #pos.update((node, (1, index)) for index, node in enumerate(r)) #pos.update((node, (2, index)) for index, node in enumerate(l)) count = 0. labels={} for com in set(partition.values()): count = count + 1. list_nodes = [nodes for nodes in partition.keys() if partition[nodes] == com] #print str(com) + ":" + ",".join(list_nodes) for node in list_nodes: labels[node] = node.split(".")[0] #color = (str(count / size),str(count / size),str(count / size)) color = (random(),random(),random()) if len(list_nodes) == 3: c1 = random() color = (c1, c1, c1) #print color nx.draw_networkx_nodes(G, pos, list_nodes, node_size = 600, vmin=0, vmax=0.9, node_color = color, dpi = 2000) nx.draw_networkx_edges(G,pos, alpha=0.5, dpi = 2000) nx.draw_networkx_labels(G,pos,labels, alpha=0.5, font_size=18) set_size(40,40) plt.axis('off') plt.savefig("/root/biLuvain/CIS-45691/dom0_pod.png") plt.show()

04

基于Dom0社区划分升级批次

因为每个Dom0社区是独立的，意味着每个社区内的Dom0/DomU是独立的没有外部依赖的，现在我们划分批次的时候选择以社区为单位，而非Dom0。通过这种方法，每个批次内选择的Dom0对别的批次内选择的Dom0/DomU没有或者只有最少的依赖。我们划分批次的规则就变成了尽量确保每个批次所选择的多个社区所包含的Dom0数量的总和等于或接近期望的每批次Dom0数目，例如50.

如下图所示：

05

参考文档及工具

https://pdfs.semanticscholar.org/41ee/f8a3cad2c9906fd4293fb2ca4a19aa878d7e.pdf https://github.com/paolapesantez/biLouvain

关于作者

之前从事过多年Solaris/Linux下存储和网络相关领域的底层驱动开发和维护，后加入Oracle系统架构和性能服务团队/SRE团队从事Cloud运维开发。