大致算法有5个(邻接表法)
支持大规模调度 (分治法)1e8以上规模
0.通用大规模矢量DAG图模型(容器化设计)
1.有向图 拓扑排序(大规模排序,并发下秒级完成)
2.节点可达性判断(传入两个节点判断是否可达)
3.关键路径
4.剪枝(最小联通图)//叶子(无children节点)到达的最小依赖图
5.最小生成树(大规模支持)、子图合并(节点合并、汇总)
6.两点间最短路径
拓扑架构,矢量拆分、拓扑不可变
通用大规模矢量DAG图模型
- RDB阵列法,支持图集群,理论上任务数量无上限,原则上支持全局图拓扑一致
- 可以配置RDB集群扩展图规模,原则上单表支持上限(1e8,亿级图节点)
- 拓扑可微,支持分布式弹性拆分,即图切分不影响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
Last editor:undefined Update time:2025-03-27 13:06