Page 153 - 《软件学报》2020年第11期

丁丹 等:场景驱动且自底向上的单体系统微服务拆分方法 3469

公式(14)的意义在于,对于连接同一个共享群组中两张表的边,保持一个比较大的权重,增加它们被划分到
同一个微服务的概率;而与共享表相连的其他边的权重削减为原来的 0.2 倍,降低该边相连的两张表被划分到
同一个微服务的可能性.经过调整的矩阵 M 将会作为数据表图的邻接矩阵成为下一步图聚类算法的输入.
2.2.3 数据表图聚类
图的聚类方法有很多种 [31−33] ,本文经过实验对比后,选择了 Girvan-Newman 算法(下文称 G-N 算法) [34−36] 用
于数据表图的聚类,被聚到一起的表最后会被划分到同一个微服务中.作为一种经典的社区发现算法,G-N 算法
认为:社区网络的重要特性是连接两个社区的边会有更高的权重,如果将这些边找出来并删除,剩下的网络就被
很自然地划分为多个社区.为此,算法提出使用边介数(betweenness)作为衡量一条边是否应该从图中删除的标
准.一条边的边介数定义为网络中经过这条边的所有最短路径的数量.G-N 算法不断重复“计算边介数”与“删除
边介数最高的边”这两个步骤,直到图中所有边都被删除.每次删边后算法都会重新计算社区结构,最终会生成
一棵社区结构树(如图 7 所示),树的每一层对应一种对原网络的划分(partition),自顶部向下,社区数量会越来越
多,划分粒度越来越细,最后,每个顶点都是一个独立的社区.这种连续的、粒度逐步细化的树形结构正好适应于
微服务拆分过程,第 2.3 节所描述的“反馈调整”也是基于 G-N 算法的这种特性.

Fig.7 Partition process of database tables
图 7 数据表划分过程

为了从多种不同粒度的拆分方案中选择一个最合适的推荐方案,G-N 算法引入模块度(modularity) [36] 作为
衡量标准,其定义如式(15)所示.
c
Modularity = (e − ∑ ii a i 2 ) (15)
i= 1
公式(15)中,e ii 表示社区 i 内所有边的权重占整个网络所有边权重的比例,a i 表示与社区 i 内顶点相连的所
有边的权重占整个网络所有顶点所连边的权重的比例.模块度的取值范围为[−0.5,1),值越大,说明网络具有越