(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210201442.7 (22)申请日 2022.03.02 (65)同一申请的已公布的文献号 申请公布号 CN 114564293 A (43)申请公布日 2022.05.31 (73)专利权人 北京大学 地址 100871 北京市海淀区颐和园路5号 (72)发明人 张齐勋　赵毓瑾　杨勇　陶冶　 李影　 (74)专利代理 机构 北京万象新悦知识产权代理 有限公司 1 1360 专利代理师 贾晓玲 (51)Int.Cl. G06F 9/48(2006.01) G06F 16/23(2019.01)审查员 王铮 (54)发明名称 基于约束检测与冲突消解的大规模在线服 务系统变更调度方法及系统 (57)摘要 本发明提供了一种基于约束检测与冲突消 解的大规模在线服务系统变更调度方法及系统， 属于软件变更管理领域。 本发明基于服务依赖图 和历史变更运行数据， 自动构建和更新变更约束 模型； 基于服务依赖图和变更约束模型， 检测待 调度变更之间的约束， 并基于变更之间的约束进 行变更间的冲突消解， 生 成满足约束的变更调度 方案， 保证变更调度的正确性。 本发明中的变更 约束模型构建与更新、 约束检测、 冲突消解都是 自动进行， 无需人工参与， 节省了人力成本； 变更 约束模型能够随着系统中服务依赖关系的变化 以及历史变更运行数据的积累进行更新， 具有对 系统迭代的较强的自适应性； 变更约束检测与冲 突消解过程保证 了变更调度的正确性。 权利要求书3页 说明书7页 附图1页 CN 114564293 B 2022.11.25 CN 114564293 B 1.一种大规模在线服务系统变更调度方法， 其特征在于， 包括变更约束模型的构建与 更新、 变更约束检测、 变更冲突消解； 具体步骤 包括： 1)变更约束模型的构建与更新， 具体执 行如下步骤： 11)提取变更记录： 从历史成功变更的运行数据中， 提取各个变更的变更对象、 变更类 型、 变更开始 运行时间、 变更完成运行时间， 其中， 变更对象是子服务， 变更类型包括修改配 置、 修改代码、 更新软件库版本、 更新数据库条目； 每一条数据记为reci＝(ci， ti1， ti2)， ci＝ (obji， acti)， 其中， ci表示变更， obji表示变更对象， acti表示变更类型， ti1表示变更开始运 行时间， ti2表示变更完成运行时间； 记数据集为Rec＝{rec1， rec2， ...， recq}， q为数据集 中 包含的变更 数量； 12)提取顺序变更对： 顺序变更对是满足以下条件的有序变更对(ci， cj)： (a)ti2＜tj1； (b)tj1‑ti2＜w， 其中w为预先设定的超参数， 用于控制顺序变更对的最大时间间隔， 记顺序 变更对集 合为P＝{(c11， c12)， (c21， c22)， ...， (cp1， cp2)}.； 13)提取变更类型和服务依赖类型： 记变更类型为C1， C2， ...， Cn， 其中n为全部变更类型 的数量， 对于每一条历史变更运行数据reci， 该条数据的变更类型Class(acti)∈{C1， C2， ...， Cn}.， 记服务依赖类型为D1， D2， ...， Dm， 其中m为全 部服务依赖类型的数量， 服务依赖 类型与服 务依赖图的边的类型相对应； 14)构建变更约束模型： 变更约束模型表示为维度是m ×n×n的矩阵M， 其中Mi， j， k表示当 两个变更的变更对象存在依赖关系Di， 被依赖的变更对象对 应的变更类型是Cj， 依赖变更对 象对应的变更类型是Ck时， 变更之间存在的约束； Mi， j， k的值为正表示被依赖的变更对象对 应的变更应该 先运行， 反 之亦然， 绝对值表示以上约束的置信度； 15)定期更新变更约束模型： 在经过一段时间后， 会产生新的成功运行的变更运行数 据， 将这些 数据作为历史运行 数据， 使用其进行变更约束模型的更新； 2)变更约束检测， 具体执 行如下步骤： 21)收集变更请求： 收集不断到达的变更请求， 每隔一段时间或每到达一定数量的变 更， 完成本 批变更请求的收集； 22)基于服务依赖图和变更约束模型， 检测待调度变更之间的约束， 以有序变更对的形 式表示， 记待调度变更为 各个待调度变更的变更对象分别为 变更类型分别为 3)变更冲突消解,具体执 行如下步骤： 31)初始化变更调度方案， 以有向无环图Pl的形式表示， 将 作为节点 加入Pl， 节点之间的有向边表示目标节点代表的变更的运行开始时间必须晚于源节点代表 的变更的运行 结束时间； 32)初始化j＝1， k ＝2； 33)在变更约束检测的结果Cons中查找(cj， ck)和(ck， cj)， 若存在(cj， ck)， 说明若ck开始 运行的时间在cj结束运行的时间之前， 会产生冲突， 冲突消解的方 法是cj结束运行之后cx才 可以开始运行， 向Pl中加入边cj→ck； 同理， 若存在(ck， cj)， 向G中加入边ck→cj； 34)遍历下一对j， k， 满足 1≤j≤k≤NCR， 若存在这样的j， k， 执 行33)、 34)； 35)完成变更调度方案的生成， 基于变更调度方案进行变更的调度。权　利　要　求　书 1/3 页 2 CN 114564293 B 22.如权利要求1所述的大规模在线服务系统变更调度方法， 其特征在于， 步骤14)中变 更约束模型的构建过程分为以下步骤： 141)创建两个维度都为m ×n×n的矩阵M1， M2， 两个矩阵都被初始化 为全0矩阵； 142)使用M1， M2记录变更顺序对的数据； 143)基于M1、 M2， 得到变更约束模型， 具体方式是依 次计算M的每个元素 的值， 计算公式 是 Mi， j， k表示了对于两个变更， 记为变更1， 记为变更2， 当 变更1的变更对象依赖于变更2的变更对象， 依赖关系为Di， 且变更1和变更2的变更类型分 别为Cj与Ck时， 变更运行先后顺序的约 束； 当Mi， j， k＞0， 说明历史运行数据支持变更1的完成 应该先于变更2的开始， 反 之亦然。 3.如权利要求2所述的大规模在线服务系统变更调度 方法， 其特征在于， 步骤142)中具 体做法是， 对 于P中的所有变更顺序对(ci1， ci2)， 记ci1的变更对象和变更类型分别为obji1和 Ci1， ci2的变更对象和变更类型分别为obji2和Ci2， 在服务依赖图中查询obji1与obji2之间的 依赖关系， 查询结果为 对于所有j＝1,2,...,NDi， 在依赖关系 下， 若 obji1依赖于obji2， 将 的值加1； 若obji2依赖于obji1， 将 的值加1。 4.如权利要求1所述的大规模在线服务系统变更调度方法， 其特征在于， 步骤15)分为 以下步骤： 151)执行11)、 12)， 提取变更记录和顺序变更对； 152)执行14)， 得到使用新的成功运行的变更运行 数据构建的变更约束模型M ’； 153)使用M ’更新M， 对M ’和M进行加权求和， 计算公式是M＝α M+(1 ‑α )M’， 其中α 是预定义 的M的权重系数。 5.如权利要求1所述的大规模在线服务系统变更调度方法， 其特征在于， 步骤21)中每 个变更请求包含了变更的基本属性， 包括变更对象、 变更类型、 请求变更的团队信息、 变更 描述。 6.如权利要求1所述的大规模在线服务系统变更调度方法， 其特征在于， 步骤22)中待 调度变更之间的约束检测分为以下步骤： 221)初始化j＝1， k ＝2， 初始化约束检测的结果Co ns＝{}； 222)初始化cj,ck之间的约束系数csj， k为0； 223)基于服务依赖图和变更约束模型M， 计算csj， k， 查询服务依赖图中objj,objk的所有 依赖关系， 记所有依赖关系的类型为 对于所有1≤i≤TDj， k， 在依赖类型 下 ， 若 o b jj依 赖 于 o b jk， 则 若 o b jk依 赖 于 o b jj， 则 224)基于csj， k， 向Cons中加入新的有序变更对， 若csj， k的绝对值大于Thcs， cj,ck间存在 约束， 则向Cons中加入有序变更对， 在 此条件下， 若csj， k为正， 加入(cj， ck)； 若csj， k为负， 加 入(ck， cj)； 225)遍历下一对j， k， 满足 1≤j≤k≤NCR， 若存在这样的j， k， 执 行222)至225)。 7.一种实现权利要求1所述大规模在线服务系统变更调度方法的系统， 其特征在于， 包权　利　要　求　书 2/3 页 3 CN 114564293 B 3