专栏首页云服务与SRE架构师社区解决云服务中的多对多分组问题 - 二分图的社区发现算法

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

作者:朱国庆

本文介绍一种高效的二分图社区发现算法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运维开发。

本文分享自微信公众号 - 云服务与SRE架构师社区(ai-cloud-ops),作者:朱国庆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 云上构建高可用实例——应用负载均衡

      作为云行业的新人,把在云上构建系统的一点一滴记录下来,有坑填坑,没坑挖坑再填平,同时也希望能给看到此文章的人提供一定的实操及经验指南。  下文中所有云中操作...

    王录华
  • 操作系统基础-内存虚拟化

    原文发布于微信公众号 - 云服务与SRE架构师社区(ai-cloud-ops),作者李勇。

    王录华
  • 如何使用ELK Stack分析Oracle DB日志

    随着业务的发展,服务越来越多,相应地,日志的种类和数量也越来越多。一般地,我们会用grep、awk,或者编写脚本进行日志分析。对于多个服务构成的系统,需要人为把...

    王录华
  • 【一文看尽200篇干货】2018最新机器学习、NLP、Python教程汇总!

    【新智元导读】本文收集并详细筛选出了一系列机器学习、自然语言处理、Python及数学基础知识的相关资源和教程,数目多达200种!来源既包括斯坦福、MIT等名校,...

    新智元
  • 11.22 访问日志不记录静态文件

    访问日志不记录指定类型的文件目录概要 网站大多元素为静态文件,如图片、css、js等,这些元素可以不用记录 把虚拟主机配置文件改成如下: <VirtualHo...

    运维小白
  • 3杂再破市场行情 6位数结拍

    近段时间,域名圈可谓热度不减,交易的好消息接连不断,这不,听说又有3个域名结拍。

    躲在树上的域小名
  • 提高GitHub访问速度及其他DNS优化

    試毅-思伟
  • 5声母域名备受欢迎 btczj.com 2万被秒

    域名被秒、域名易主的消息并不常见,最近就有HY.com成功易主;ljj.com以七位数的价格卖终端等等等,近日,一5声母域名:btczj.com以一口...

    躲在树上的域小名
  • Padavan 配置v2ray

    参考:https://ntgeralt.blogspot.com/2019/06/padavan-v2ray.html

    超级大猪
  • 如何判断安卓模拟器的型号(品牌)

    看到这个标题,可能很多人会疑惑,为啥?判断安卓模拟器本身就不一定准确,更何况还要知道它是什么品牌?

    meteoric

扫码关注云+社区

领取腾讯云代金券