大致算法有5个(邻接表法)
支持大规模调度 (分治法)1e8以上规模
0.通用大规模矢量DAG图模型(容器化设计)
1.有向图 拓扑排序(大规模排序,并发下秒级完成)
2.节点可达性判断(传入两个节点判断是否可达)
3.关键路径
4.剪枝(最小联通图)//叶子(无children节点)到达的最小依赖图
5.最小生成树(大规模支持)、子图合并(节点合并、汇总)
6.两点间最短路径

拓扑架构,矢量拆分、拓扑不可变

通用大规模矢量DAG图模型

  1. RDB阵列法,支持图集群,理论上任务数量无上限,原则上支持全局图拓扑一致
  2. 可以配置RDB集群扩展图规模,原则上单表支持上限(1e8,亿级图节点)
  3. 拓扑可微,支持分布式弹性拆分,即图切分不影响DAG拓扑完整性

矢量图表设计:
矢量图关系表(hydra_${业务线}_vgraph_adjacent):

主键Id 节点GUID 连接类型 父节点GUID
id guid linked_type parent_guid

说明:此连接类型为weak目前做预留处理默认为weak

矢量图节点表(hydra_${业务线}_vgraph_nodes):

主键Id 节点GUID 节点名称 节点描述 其他元信息
id guid node_name node_description ….

矢量图路径缓存表(hydra_${业务线}_vgraph_cache_path):

主键Id 节点GUID 节点路径 节点长路径
id guid path long_path
Author:undefined  Create time:2024-10-11 12:32
Last editor:undefined  Update time:2025-03-27 13:06