基于DAG 的Hive 數據溯源方法

杜 娟 ，蘇秋月

(1.61646 部隊，北京 100192；2.四川大學，四川 成都 610065)

0 引言

Hive 是基于 Hadoop 的開源數據倉庫工具，它提供了豐富的SQL 查詢方式來分析存儲在 Hadoop 分布式文件系統中的數據：可以將結構化的數據文件映射為一張數據庫表，并提供完整的SQL 查詢功能；可以將 SQL 語句轉換為 MapReduce 任務運行，通過自己的 SQL 查詢分析需要的內容。這套 SQL 簡稱Hive SQL，使不熟悉 MapReduce 的用戶可以很方便地利用 SQL 語言查詢、匯總和分析數據[1]。由于Hive 在數據存儲和分析上的靈活性，眾多企業用它存儲重要數據。這些敏感的商業數據被大量企業內部人員訪問和操作，一旦發生人為誤操作或違規操作，很容易導致數據的泄露。現有大數據平臺上的數據安全防護方案缺乏對敏感數據靈活的訪問控制，難以對數據的生命周期及用戶操作行為進行精確的追蹤溯源，無法提供對大數據合規審計管理的支撐。因此，如何提供有效的安全防護機制來保障Hive 中數據的安全，是目前研究的重點。

數據溯源也稱為數據血緣、數據譜系等，數據溯源技術根據追蹤路徑重現數據的歷史、狀態和演變過程，實現數據歷史檔案的追溯[2]。通過數據溯源能追蹤到異常發生的原因，還能幫助人們確定數據倉庫中各項數據的來源。國內外學者在數據溯源技術上進行了深入研究。在數據溯源模型方面，汪洪昕[3]提出了數據染色體溯源模型，更加完善地揭示數據傳播過程中的變化及數據的關系， 并在Hadoop 平臺中得以實現。郝鵬飛[4]通過對大數據模型分析平臺工作流特征分析，討論了基于Oozie 模型工作流的數據溯源問題。

目前針對數據庫的數據溯源追蹤主要有兩種方法：(1)基于標注的方法[5]，此類方法雖然實施起來比較簡單，但需要額外的存儲空間且隨著處理的數據量增加其執行效率會降低，難以直接應用于維護著海量數據的Hive 數據倉庫；(2) 基于逆置函數的方法[6]，此類方法需要的存儲空間較小，但不是所有的數據處理都可以逆置，且其溯源追蹤的性能完全取決于逆置機制。對于Hive 數據倉庫中復雜的數據處理， 要構造一個良好的逆置機制難度較大。Hive 數據的溯源重點在于數據沿襲問題，而給定數據的數據沿襲問題可以概括為建立數據的血緣關系，得到其產生過程以及源數據。

對于數據倉庫中數據溯源問題，柯潔[7]等人基于W3C 的 PROV 模型對 ETL 過程的數據溯源進行了深入分析，并提出了相應的數據溯源算法。文獻[8-9]討論了數據倉庫中的數據譜系跟蹤問題，提供了譜系跟蹤算法以及溯源過程中屬性映射和轉換起源集的求解方法。但這些研究均針對傳統數據倉庫中的數據溯源，難以應用于大數據環境下Hive 的數據溯源。針對大數據環境，文獻[10]提出了一種基于層的數據溯源架構，其中包括大數據來源的捕獲及可視化，并且在溯源數據中引入了一種訪問控制機制。文獻[11-13]總結了數據庫中的數據溯源技術，分析了在Hadoop 環境下數據溯源面臨的研究挑戰，并從數據溯源模型、溯源數據存儲、溯源查詢語言等方面梳理了現有解決方案。Apache Atlas 是Hadoop 社區為解決Hadoop 生態系統的元數據治理問題而產生的開源項目， 它為 Hadoop 集群提供了包括數據分類、集中策略引擎、數據溯源、安全和生命周期管理在內的元數據治理核心能力[14]，因此可以將 Apache Atlas 引入到 Hive 數據溯源中。

針對傳統數據溯源機制難以滿足Hive 中大規模、復雜的數據處理問題，本文提出了基于有向無環圖(Directed Acyclic Graph，DAG)的數據溯源方法。通過對 Apache Atlas 進行擴展，在 Hive 中實現了該數據溯源方法，并通過實驗證明該方法可為Hive 提供準確、高效的數據溯源機制，也為數據安全審計提供了有力支撐。

1 基于 DAG 的數據溯源方法

針對Hive 中數據處理的特點，本文提出了基于DAG 的數據溯源方法。該方法包含了兩部分內容：數據血緣圖的定義和基于數據血緣圖的溯源追蹤算法，下面針對這兩部分進行具體的闡述。

1.1 數據血緣圖定義

Hive 數據倉庫中數據的變化主要源于HQL 任務，用戶可以通過 Hive 訪問接口提交 HQL 語句，對Hive 中的數據執行操作。下面對 HQL 語句中所涉及的相關實體及關系進行定義。

定義1數據項(Dataset)，表示數據處理過程中所涉及的數據。例如 Hive 中的數據庫、表、列，以及HDFS 中的文件。

定義 2操作(Process)，表示數據處理過程中用戶執行的具體操作，例如 CRETAE_AS_SELECT、INSERT、SELECT、DTOP，以及 EXPORT、IMPORT 等基本 HQL操作。

定義3關系(Relationship)，表示實體之間的關聯關系，通過關系建立起了數據實體與操作實體之間的聯系。

定義 4數據血緣圖 G=(V，E，R，A)為一個有向無環圖，其中：

{guit，name，typeName，createTime，createBy，version}其中Du 表示使用數據頂點的集合，OP 表示操作頂點的集合，Dr 表示結果數據頂點的集合，Di 和 Do分別表示第 i 和第 o 項數據。E 表示邊的集合，R 是指邊類型的集合，包含了 usedBy 和 generated 兩種類型。其中 usedBy 表示數據操作所使用的數據，建立了使用數據與操作之間的關系。generated 表示一個結果數據產生的過程，建立了操作與結果數據之間的關系。A 表示血緣圖中頂點和邊包含的屬性，具體定義如表1 所示。其中guid 表示實體或關系的唯一標識；name 表示頂點(或邊)所表示的實體(或關系)的名稱；typeName 表示頂點或邊的類型，這里除了邊具有兩種類型外，頂點的類型也包括Dataset 和Process 兩種類型。

在一條HQL 任務中，會存在嵌套子查詢或多表關聯查詢等子操作。所以一條 HQL 語句可能會產生多個使用數據的頂點， 但只產生一個結果數據頂點和一個操作頂點。例如對于某HQL 語句“CREATE TABLE table_c AS SELECT … FROM table_a a JOIN table_b b ON…”， 這里表 table_a和table_b 均為使用數據，表 table_c 為產生的結果數據，CREATE_AS_SELECT 為數據的操作。通過對該數據處理過程進行建模，產生了由四個實體頂點和三條邊關系的血緣圖，如圖1 所示。

表1 屬性定義

圖1 數據血緣圖

1.2 基于 DAG 的溯源追蹤算法

上節利用DAG 構建了Hive 中的數據的血緣關系，在此基礎上，將給定數據的溯源追蹤問題轉變為了圖的連通性問題，利用圖連通算法找到數據頂點能連通的所有頂點，從而得到數據的血緣關系圖，實現對數據的溯源追蹤。因此，本文提出基于DAG的溯源追蹤算法。引入深度優先搜索(Depth First Searching，DFS)算法[15]的思想，根據給定數據頂點進行深度優先查詢，首先得到與該頂點相連的所有邊，然后根據鄰接邊得到相鄰頂點，遞歸執行，最終得到由給定數據頂點能連通的所有頂點構成的數據血緣圖。基于 DAG 的溯源追蹤算法流程如圖 2 所示，具體步驟如下：

(1)初始化用來描述數據血緣關系的圖G；

(2)將表示給定數據的頂點 vertex 添加至圖 G，并標記該頂點已被訪問；

(3)獲取所有與該頂點 vertex 相連的邊，若不存在與之相連的邊，則跳至步驟(5)，否則進行下一步驟；

(4)根據該邊相連的兩個頂點 vertex 和 vertex′，如果 vertex′未被訪問，則設置該頂點為 vertex 的值，然后跳轉至步驟(2)，否則循環該步驟遍歷其他相連的邊；

(5)到此對給定數據的溯源已經完成，返回數據的血緣圖G。

1.3 基于 Hive 的實現框架

圖2 基于DAG 的溯源追蹤算法流程

1.3.1 整體框架

在Apache Atlas 的基礎上進行了擴展，實現了基于 DAG 的數據溯源方法，整體框架如圖 3 所示。該框架主要包括溯源收集、溯源信息建模和溯源追蹤三個模塊。該框架的簡要工作流程如下：在用戶執行HQL 操作之后，內嵌于Hive 中的溯源收集模塊收集數據操作過程中的溯源信息，并發送給溯源信息建模模塊；溯源信息建模模塊在收到溯源信息后，對溯源信息進行建模，將收集的溯源信息轉換成數據血緣圖，并持久化存儲在圖數據庫中；當對給定數據進行溯源追蹤時，溯源追蹤模塊利用基于DAG的溯源追蹤算法對給定數據進行追蹤溯源，最終返回數據的血緣關系圖。

實現框架采用的圖數據庫為 JanusGraph[16]，并利用AtlasGraphManagement 接口實現對圖數據的操作。由于溯源追蹤模塊主要通過基于 DAG 的溯源追蹤算法實現給定數據的溯源追蹤，后面就不再介紹該模塊的實現。

圖3 基于 Hive 的實現框架

1.3.2 溯源收集

溯源收集是Hive 數據溯源實現的基礎，本文主要關注溯源收集的方式和內容兩方面。為了在保證數據準確性的前提下不對Hive 本身帶來過高的負載，本文采用在Hive 中實現Hook 鉤子函數的形式，在HQL 執行完成后，實時地收集數據的變化過程。這里基于Apache Atlas 實現對Hive 溯源信息的收集，具體是在Hive 配置文件中添加如圖4 所示信息。

表2 溯源信息

圖4 Hive 的 Hook 配 置

在確定收集的方式和時機之后，需要考慮應該收集數據處理過程中的哪些內容，這些內容必須與溯源相關。在對 Hive 進行數據溯源時，不能完全使用Atlas 收集的元數據來構建數據的溯源關系。因此，本文參考了W7 模型中以數據為中心的思想[17]，追溯在何時、何地以及何種原因，由何人通過何種方式對數據進行了何種操作，重新定義了收集的溯源信息，如表2 所示。這些內容可以為后續利用數據血緣圖模型建立數據的血緣關系提供重要的基礎。

由表2 可以看出，定義的Hive 溯源信息表示一次HQL 任務中所涉及的相關信息，主要分為三類：數據相關信息、操作相關信息和上下文信息。

1.3.3 溯源信息建模

利用數據血緣圖模型對收集的溯源信息進行建模，首先提取出溯源信息中的數據和操作等基本對象，根據對象類型創建對應的實體；然后根據實體創建圖頂點，以及根據實體屬性中包含的與相關實體的關系創建邊，并保存于圖數據庫中。每種類型的實體均由唯一標識和一組基本屬性集合組成。唯一標識是在創建實體或關系時產生的，而屬性集合來自于溯源收集的內容。數據實體的屬性包含了溯源信息中數據相關的信息，操作實體的屬性包含了操作和上下文相關的信息。

對一條溯源信息建模，以數據和操作為頂點，它們之間的關系作為有向邊，以此形成數據血緣圖的實現流程如圖5 所示，具體的步驟如下：

(1)提取溯源信息中的基本對象，包括使用數據、操作以及結果數據。

(2)為使用數據和結果數據分別創建Dataset 類型的實體，為其分配唯一標識guid 以及設置基本屬性。根據實際情況，這里可能會產生多個輸入Dataset類型的實體。

(3)為溯源信息中的操作對象創建 Process 類型的實體，并根據操作以及上下文信息設置基本屬性。其中在 inputs 集合和outputs 集合中分別添加使用數據實體和結果數據實體。

(4)根據Process 實體屬性中的inputs 集合和outputs集合包含的數據實體，創建Relationship 依賴關系，分別為 usedBy 類型和 generated 類型。

(5)根據實體創建頂點，并設置基本屬性。

(6)根據關系創建邊，并設置邊的兩個鄰接點及基本屬性。

(7)將頂點和邊添加至圖中，并以鄰接表的方式持久化存儲在圖數據庫中。

圖5 溯源信息建模過程

通過上述流程，將Hive 中數據處理過程收集的溯源信息構建成了具有關聯關系的數據血緣圖，并且利用圖數據庫將血緣關系進行了持久化的存儲，為后續基于DAG 的溯源追蹤算法對給定數據進行溯源， 還原出數據的血緣關系圖提供了可能。

2 實驗與分析

2.1 實驗環境

通過構建Hive 環境進行實驗，在其中一個從節點上部署 Kafka，創建了一個副本因子為 1、分區數為 1 的主題，用于存儲 Hive 中的溯源信息。在另外一個從節點上部署了JanusGraph 圖數據庫，其中使用 Hbase 作為圖數據的存儲后端，Solr 作為圖數據的搜索引擎。另外由于本文在 Apache Atlas 的基礎上進行擴展，實現了基于DAG 的數據溯源方法，因此在主節點上部署了 Atlas。詳細信息如表 3 所示。

表3 節點相關信息

2.2 有效性測試

為了驗證Hive 中數據處理過程中的數據是否被正確的溯源，本節對Hive 中的數據執行了部分常見的 HQL 操作作為測試用例，如表 4 所示。從表 4 可以看出，Hive 中數據處理過程中的數據被正確溯源。

表4 數據操作測試用例

利用Apache Atlas 的可視化管理頁面查詢Hive中數據的血緣信息，這里查詢了表avgsalary 的數據溯源關系，如圖6 所示。

由圖6 可以看出，表avgsalary 的血緣關系分為兩種類型：一種關系是與表avgsalary 中數據的來源有關； 另一種關系是與表avgsalary 中數據的去處有關。首先查找表avgsalary 的來源，以該表為起點往前追溯，可知它是由用戶對表empinfo 執行了CREATE AS SELECT 操作得到的。而表 empinfo 數據的產生總共有三部分的來源，第一部分是HDFS 中的empinfo.csv文件；另外兩個部分是來自Hive 中原有的表department 和表 employee。到此，發現沒有可以往前追溯的節點了，然后返回到表avgsalary，往后查找其產生了哪些數據。發現該表的數據有兩個去處，一是經過EXPORT 操作產生了 HDFS 文件‘avgsalary.csv’；二是經過SELECT 操作產生了臨時文件。

2.3 性能測試

為了測試本文所提出的數據溯源方法對性能的影響，本節從溯源信息采集對HQL 執行的額外時間開銷以及溯源追蹤效率兩方面進行了測試。

(1)溯源信息采集時間開銷實驗

圖6 表 avgsalary 的數據溯源圖

本文對 Hive 進行了擴展，在 Driver 驅動中增加了溯源收集模塊，因此本實驗旨在對擴展前后的Hive 進行對比測試，檢驗溯源收集過程對整體性能的影響。本實驗執行相同的HQL 任務處理不同規模的數據，測試對不同輸入數據規模下，加入溯源信息采集模塊前后HQL 執行時間的對比， 以及在HQL 過程中溯源采集的時間開銷。該測試實驗設置為 8 組，其中數據量從 64 MB 到 512 MB，分別測試其執行時間，每次的執行時間取同一實驗執行3 次的平均值。實驗結果如圖 7 所示。

圖7 溯源收集對HQL 執行時間性能影響

由圖7 可以看出，加入溯源收集模塊與無溯源收集模塊的HQL 執行時間均隨著輸入數據量的增加而呈線性增長,但有溯源收集模塊與無溯源收集模塊的時間開銷差距較小。另外，在整個執行過程中，溯源收集的時間開銷趨近于零。由此可知，溯源采集對HQL 的額外時間開銷可以忽略不記。

(2)溯源追蹤效率實驗

為了實現根據給定數據項的溯源追蹤，本文提出了基于DAG 的溯源追蹤方法，利用圖論查詢算法完成對數據的來源以及產生過程的追蹤溯源。在不同輸入數據規模的情況下，對溯源追蹤的時間開銷進行了測試，每次的執行時間取同一實驗執行3 次的平均值。實驗結果如圖8 所示。可以看出，隨著數據規模的增加，數據溯源追蹤的時間基本上保持在300 ms 左右，且波動范圍很小。由此可知，本文提出的溯源追蹤方法整體性能較好。

圖8 不同輸入數據量下溯源追蹤時間開銷

3 結論

本文對Hive 數據倉庫的數據溯源進行了研究，首先介紹了數據溯源的相關理論與機制，并針對傳統數據溯源難以應用于Hive 中大規模、復雜的數據處理的問題，提出了基于DAG 的數據溯源方法；然后對該方法中數據血緣圖的構建以及基于DAG 的溯源追蹤算法進行了闡述；接著基于Apache Atlas 實現了該方法對Hive 中數據溯源及可視化的展示；最后通過實驗驗證了本文所提的數據溯源方法的有效性，并從溯源收集和溯源追蹤兩方面的性能測試，驗證了該方法的整體性能較好。實驗表明，基于DAG 的數據溯源方法不僅實現了對 Hive 中數據準確、高效的溯源，也為數據操作審計提供了有力支撐。