浅谈数据血缘的实现原理

面对成百上千张的数据表，不知道该如何关联，也不知道这些表具有什么业务价值

执行过长，慢的无法忍受的SQL脚本，却不敢轻易进行整改

数据表是否包含机密数据需要被清理，以及这些机密数据是否被转存导致权限放大

其实，以上的这些问题都可以统一归类为数据发现问题。大部分企业会针对离线数仓任务进行SQL分析，构建表和字段的血缘关系，数据发现包括但不限于: 数据 表/列的业务分类分级和机密字段识别等。

2、数据血缘的基本概念

数据血缘(Data Lineage)，指的是数据从产生、ETL处理、加工、融合、流转到最终消亡，数据之间自然形成一种关系。这些关系就是描述数据的数据（元数据）。掌握了这个元数据，就能最大程度的做好数据的应用和管理。

tips：有童鞋对元数据感兴趣的，可以看这篇文章https://zhuanlan.zhihu.com/p/336504407

3、数据血缘的常见用途

业务域的划分针对任务的表和字段，通过血缘关系可以确定表的上下游，以及对应这个表所涵盖的业务范围包括哪些

提升调度性能

通过收集调度任务的开始结束时间，了解任务ETL链路的时间瓶颈，在根据JOB的执行情况定位性能瓶颈，通过调整任务的基线、保证任务的资源提供，提升整条ETL链路的执行效率。

数据异常定位

若在某天的调度中，发现数据异常，想确认是什么造成，可根据DQC和血缘关系了解底层数据波动情况，快速定位原因。

数仓链路优化通过对表和字段的下游使用频次，找到使用较多的，分析其是否有重复计算、浪费资源的情况。再判断是否可以因此建设事实或维度表、或者把计算的指标或维度沉淀。

调度依赖的准确性判断

在平时的开发过程中，很可能修改过SQL，但是忘记在调度平台上配置相对应的依赖，这样很可能会出现问题，其实通过调度平台的调度关系的元数据，和收集到的血缘关系进行对比，可定时性的判断调度任务依赖是否准确。

4、数据血缘的实现原理（表级别）

本文只阐述最基本的表级别的血缘关系的实现思路，真实的血缘实现，远比文章中的场景复杂。

原理一  SQL解析之正则表达式

在最开始时，刚毕业的小白，如果让你做好数仓的血缘元数据时，你会怎么做？

在初期的小白根本就不懂编译器、语法分析、词法分析以及AST这些概念时，想到的唯一办法就是通过正则这个朴素的手段去解析SQL了，想法也非常直接，FROM或者JOIN后面就是源表，INSERT INTO/INSERT OVERWRITE TABLE后面就是目标表。

source_table_regex = re.compile(r"(?:from|join)\s+(\S*)(?:\s+|;)", re.IGNORECASE)
target_table_regex = re.compile(r"insert\s+(?:into|overwrite)\s+table\s+(\S*)\s+", re.IGNORECASE)

不过，若是我们的SQL是这样的呢？

select * 
--from tableA
from tableB;

或者是这样的：

select * from tableA
where description = "from Excel";

你会发现，这个思路有很多漏洞。事实上如果加上一些if-else的判断，这个方案其实也满足了大部分场景。但是！！！！身为开发人员一定要明白一个理念，当你在生产环境中只要有一个场景没有满足，那就是bug。

原理二 AST语法树的解析

首先针对思路二，大家可以提前了解AST的概念，参考https://blog.csdn.net/u013212754/article/details/106981084

其次在了解思路二前提下，需要知道Hive SQL的执行过程（毕竟还是看的HQL的语法树）以及一些名词解释。

• 名词解释

词法分析器：词法分析器的工作是分析量化那些本来毫无意义的字符流，将他们翻译成离散的字符组（也就是一个一个的Token），供语法分析器使用。简单说就是分析sql里每个单词该怎么组成。

语法分析：语法分析器将把收到的Tokens组织起来，并转换成语法规则定义的所允许的结构。简单说就是研究这些单词该以怎样的结构组成一个SQL的。

Antlr：ANTLR (ANother Tool for Language Recognition ) 是一种语言识别工具，它提供了一个框架，可以通过包含 Java, C++, 或 C# 动作（action）的语法描述来构造语言识别器，编译器和解释器。

• Hive SQL的解析流程：

Hive根据Antlr定义的词法、语法规则完成词法、语法分析将HQL解析为AST Tree；

遍历AST Tree，抽象出查询的基本组成单元Query Block；

遍历Query Block解析为操作树Operator Tree(即，逻辑执行计划)；

逻辑优化器进行操作树变换，合并多余的ReduceSinkOperator，减少shuffle；

遍历Operator Tree，将操作树翻译为对应的MapReduce任务；

物理优化器进行MapReduce任务变换，生成最终的执行计划。

具体步骤：

• 对Hive SQL进行词法分析和语法分析，获取对应的AST 原始的抽象语法树
• AST语法树剪枝优化，减少遍历次数，提高语义解析的效率，具体主要做两方面的优化：

针对token中涉及到的无效解析节点进行删除,如order by，distributedby,cluster by,sort by以及limit；

针对token中where/having的子查询，在保证SQL语法正确性以及语义完整性的前提下，采用1=1 等价策略进行等价替换，降低了血缘关系解析的复杂性；通过以上两种剪枝操作，既可以减少SQL语句的复杂性，又可以降低AST语法树的层级，进一步减少了遍历AST树递归次数，降低血缘分析的复杂性，提高了语句解析效率。

遍历AST获取上游表名和下游表名，在SQL语句中存在大部分SQL语句片段即CTE。由于其在血缘关系解析中不起关键作用，且对SQL解析带来很大困扰，因此血缘关系解析需对CTE类型进行识别，并进行替换与删除。

5、总结

市面上其实针对数据血缘的产品有很多，像阿里DataWorks的数据地图、字节的DataLeap以及非常火的开源产品Apache Atlas都是非常好用工具产品。但是本质上是想通过这篇文章，让小伙伴们在使用这些产品的时候多去思考这些产品背后的实现原理。