📚 课程目录第3章血缘关系的数据结构

3、血缘关系的数据结构：有向无环图(DAG)表示、邻接表与邻接矩阵、元数据存储方案

聊完了血缘关系的概念，咱们得落地了。特征血缘在系统里到底长什么样？

说白了，它就是一个有向无环图（DAG）。我刚开始接触特征管理平台时，第一反应就是：这不就是个依赖图吗？对，但又不完全是。它比普通的依赖图多了「数据流」和「变换规则」的语义。

3.1 为什么非得是DAG？

你想想看，特征A从原始日志里提取，特征B依赖A做聚合，特征C又依赖B和另一个原始特征D。这天然就是个有向关系——数据从源头流向终点。那为什么不能有环？

我曾经在一个老项目里见过「循环依赖」的噩梦：特征X依赖Y，Y依赖Z，Z又绕回来依赖X。结果每次上线都要手动排顺序，稍有不慎就全链路报错。DAG强制无环，就是逼你把依赖理清楚，别搞死锁。

  核心要点： DAG保证了特征可以拓扑排序，这是自动化调度和增量更新的基础。

3.2 邻接表 vs 邻接矩阵：我该怎么选？

图存起来就两种主流方式：邻接表和邻接矩阵。我两个都用过，说说真实感受。

对比维度	邻接表	邻接矩阵
存储结构	每个节点维护一个下游列表	N×N 的二维布尔/权重矩阵
空间复杂度	O(V+E)，稀疏图很省	O(V²)，稠密图才划算
查询「A→B是否存在」	需要遍历A的邻接链表，O(度)	直接索引 matrix[A][B]，O(1)
查询「A的所有下游」	直接返回链表，O(度)	遍历整行，O(V)
新增/删除边	链表操作，O(1)~O(度)	改一个值，O(1)
适用场景	特征血缘（稀疏、频繁遍历下游）	稠密图、频繁判断边是否存在

我个人习惯用邻接表。原因很简单：特征血缘图通常很稀疏。一个特征的下游可能只有几个，但整个特征空间可能有几千个节点。用矩阵的话，大部分格子都是0，太浪费了。

我的经验： 在百万级特征规模下，邻接矩阵光存储就要TB级内存，而邻接表只需要GB级。选错了存储方案，后面全得重构。

3.3 代码示例：邻接表实现特征DAG

给你看一段我实际用过的简化版代码。别嫌简单，核心逻辑都在里面了。

class FeatureDAG:
    def __init__(self):
        # 邻接表：key=特征ID，value=下游特征ID列表
        self.adjacency = {}
        # 顺便存一份入度表，方便拓扑排序
        self.in_degree = {}
    
    def add_feature(self, feature_id):
        if feature_id not in self.adjacency:
            self.adjacency[feature_id] = []
            self.in_degree[feature_id] = 0
    
    def add_dependency(self, upstream_id, downstream_id):
        # 添加一条边：upstream → downstream
        self.adjacency[upstream_id].append(downstream_id)
        self.in_degree[downstream_id] += 1
    
    def get_downstream(self, feature_id):
        # 查询某个特征的所有直接下游
        return self.adjacency.get(feature_id, [])
    
    def topological_sort(self):
        # Kahn算法，用于确定特征计算顺序
        from collections import deque
        q = deque([f for f, d in self.in_degree.items() if d == 0])
        result = []
        while q:
            node = q.popleft()
            result.append(node)
            for neighbor in self.adjacency[node]:
                self.in_degree[neighbor] -= 1
                if self.in_degree[neighbor] == 0:
                    q.append(neighbor)
        return result

避坑指南： 我曾经在拓扑排序时忘了处理「入度永远不为0」的情况——那说明图里有环。后来我加了个长度校验：如果 result 长度不等于总节点数，直接报错并打印环信息。

3.4 元数据存储方案：光有图不够

DAG只存了结构，但每个节点和边还有一堆信息要记。比如：

特征的计算逻辑（SQL、Python脚本、配置规则）
特征的产出时间、数据版本
特征的owner、标签、质量分
边的变换类型（直接映射、聚合、过滤、拼接）

这些就是元数据。我见过三种主流存法：

方案	说明	优点	缺点
关系型数据库（MySQL/PostgreSQL）	节点表、边表、属性表分开存	查询灵活，支持事务	深度遍历慢，需要递归CTE
图数据库（Neo4j/Dgraph）	节点和关系原生存储	多跳查询极快，天然支持DAG	运维成本高，小团队不推荐
混合存储（MySQL + Redis/ES）	结构存MySQL，元数据索引存ES	兼顾查询和搜索	架构复杂，需要同步

我个人习惯用关系型数据库 + 内存缓存。为什么？因为特征血缘的元数据查询模式很固定：要么查某个特征的全链路血缘，要么查某个节点的属性。MySQL的递归CTE（WITH RECURSIVE）足够应付大多数场景，再配合Redis缓存热点查询，性价比很高。

一个小技巧： 在MySQL里存边时，我额外存了「depth」字段——从根节点到当前边的跳数。这样查全链路时可以直接按depth排序，不用递归算层级。

3.5 一张图看懂整体结构

下面这张SVG图把上面讲的三个部分串起来了。你可以看到：DAG是骨架，邻接表是存储方式，元数据是血肉。

3.6 实际项目中的选型建议

嗯，这里要注意。不同规模的项目，选型差别很大。

小团队（特征数 < 1000）：直接用MySQL + 邻接表存边表。递归CTE查全链路，够用了。
中型团队（特征数 1万~10万）：MySQL存元数据，Redis缓存热点DAG。邻接表在应用层维护一份内存副本。
大型平台（特征数 > 10万）：上图数据库或者自研内存DAG引擎。我见过用Neo4j做血缘分析的，多跳查询确实快，但运维要专人。

我曾经踩过的坑： 一开始把所有元数据都塞进DAG节点对象里，结果每次序列化都巨大。后来把元数据和图结构分开存储，查询时按需加载，性能提升了10倍。

说白了，数据结构选型没有银弹。你得根据特征规模、查询模式、团队能力来权衡。但不管怎么选，DAG + 邻接表 + 元数据分离这个三层架构，我建议你保留。它经得起时间考验。