基于DAG 的Hive 數(shù)據(jù)溯源方法

杜 娟 ，蘇秋月

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

0 引言

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

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

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

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

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

1 基于 DAG 的數(shù)據(jù)溯源方法

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

1.1 數(shù)據(jù)血緣圖定義

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

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

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

定義3關(guān)系(Relationship)，表示實體之間的關(guān)聯(lián)關(guān)系，通過關(guān)系建立起了數(shù)據(jù)實體與操作實體之間的聯(lián)系。

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

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

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

表1 屬性定義

圖1 數(shù)據(jù)血緣圖

1.2 基于 DAG 的溯源追蹤算法

上節(jié)利用DAG 構(gòu)建了Hive 中的數(shù)據(jù)的血緣關(guān)系，在此基礎(chǔ)上，將給定數(shù)據(jù)的溯源追蹤問題轉(zhuǎn)變?yōu)榱藞D的連通性問題，利用圖連通算法找到數(shù)據(jù)頂點能連通的所有頂點，從而得到數(shù)據(jù)的血緣關(guān)系圖，實現(xiàn)對數(shù)據(jù)的溯源追蹤。因此，本文提出基于DAG的溯源追蹤算法。引入深度優(yōu)先搜索(Depth First Searching，DFS)算法[15]的思想，根據(jù)給定數(shù)據(jù)頂點進(jìn)行深度優(yōu)先查詢，首先得到與該頂點相連的所有邊，然后根據(jù)鄰接邊得到相鄰頂點，遞歸執(zhí)行，最終得到由給定數(shù)據(jù)頂點能連通的所有頂點構(gòu)成的數(shù)據(jù)血緣圖?；?DAG 的溯源追蹤算法流程如圖 2 所示，具體步驟如下：

(1)初始化用來描述數(shù)據(jù)血緣關(guān)系的圖G；

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

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

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

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

1.3 基于 Hive 的實現(xiàn)框架

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

1.3.1 整體框架

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

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

圖3 基于 Hive 的實現(xiàn)框架

1.3.2 溯源收集

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

表2 溯源信息

圖4 Hive 的 Hook 配 置

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

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

1.3.3 溯源信息建模

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

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

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

(2)為使用數(shù)據(jù)和結(jié)果數(shù)據(jù)分別創(chuàng)建Dataset 類型的實體，為其分配唯一標(biāo)識guid 以及設(shè)置基本屬性。根據(jù)實際情況，這里可能會產(chǎn)生多個輸入Dataset類型的實體。

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

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

(5)根據(jù)實體創(chuàng)建頂點，并設(shè)置基本屬性。

(6)根據(jù)關(guān)系創(chuàng)建邊，并設(shè)置邊的兩個鄰接點及基本屬性。

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

圖5 溯源信息建模過程

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

2 實驗與分析

2.1 實驗環(huán)境

通過構(gòu)建Hive 環(huán)境進(jìn)行實驗，在其中一個從節(jié)點上部署 Kafka，創(chuàng)建了一個副本因子為 1、分區(qū)數(shù)為 1 的主題，用于存儲 Hive 中的溯源信息。在另外一個從節(jié)點上部署了JanusGraph 圖數(shù)據(jù)庫，其中使用 Hbase 作為圖數(shù)據(jù)的存儲后端，Solr 作為圖數(shù)據(jù)的搜索引擎。另外由于本文在 Apache Atlas 的基礎(chǔ)上進(jìn)行擴展，實現(xiàn)了基于DAG 的數(shù)據(jù)溯源方法，因此在主節(jié)點上部署了 Atlas。詳細(xì)信息如表 3 所示。

表3 節(jié)點相關(guān)信息

2.2 有效性測試

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

表4 數(shù)據(jù)操作測試用例

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

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

2.3 性能測試

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

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

圖6 表 avgsalary 的數(shù)據(jù)溯源圖

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

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

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

(2)溯源追蹤效率實驗

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

圖8 不同輸入數(shù)據(jù)量下溯源追蹤時間開銷

3 結(jié)論

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