[發明專利]一種低存儲開銷的運行時遞推數據溯源方法

無效

• 申請號: 201310034449.5
• 申請日: 2013-01-30
• 公開（公告）號: CN103177184A
• 公開（公告）日: 2013-06-26
• 發明（設計）人: 李千目;謝新;戚湧;於東軍;侯君;朱長林
• 申請（專利權）人: 南京理工大學常熟研究院有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種低存儲開銷的運行時遞推數據溯源方法，其特征在于步驟如下：

第一步，在數據處理系統部署時，記錄其粗粒度起源信息；

第二步，在數據處理系統運行過程中，記錄其細粒度起源信息；

第三步，在數據處理系統中最后一個處理單元產生輸出數據元組時，對該輸出數據元組的起源信息進行遞推，遞推得到數據處理系統中第一個處理單元的觸發運行的時間范圍，將第一個處理單元的觸發運行的時間范圍???????????????????????????????????????????????????與輸出數據元組一起進行持久存儲；

第四步，溯源查詢時，根據存儲在輸出數據元組中的第一個處理單元的觸發運行的時間范圍???，推算出數據處理系統輸入數據流中所有對待溯源輸出數據元組的產生有貢獻的輸入數據元組。

2.根據權利要求1所述的低存儲開銷的運行時遞推數據溯源方法，其特征在于：在數據處理系統部署時，記錄的粗粒度起源信息包括：

a)基于元組數量計算的每個處理單元的計算窗口類型；

b)每個處理單元的計算窗口大小，窗口大小為元組數量。

3.根據權利要求1所述的低存儲開銷的運行時遞推數據溯源方法，其特征在于：在數據處理系統部署時，記錄的粗粒度起源信息包括：

a)基于時間長度計算的每個處理單元的計算窗口類型；

b)每個處理單元的計算窗口大小，窗口大小為時間長度。

4.根據權利要求2或3所述的低存儲開銷的運行時遞推數據溯源方法，其特征在于：在數據處理系統運行過程中，需要持久記錄的細粒度起源信息包括：

a)系統輸入數據流中所有輸入數據元組的值及其進入數據處理系統的時間；

b)系統輸出數據流中所有輸出數據元組的值及其產生時間；

需要臨時存儲的細粒度起源信息包括：

a)每個處理單元每次運行的觸發時間；

b)每個處理單元每次運行的處理延遲。

5.根據權利要求3所述的低存儲開銷的運行時遞推數據溯源方法，其特征在于：在數據處理系統中最后一個處理單元產生輸出數據元組時，對該輸出數據元組的起源信息進行遞推，遞推公式如下：

其中

。

6.根據權利要求5所述的低存儲開銷的運行時遞推數據溯源方法，其特征在于：溯源查詢時，根據存儲在輸出數據元組中的PU₁的觸發運行的時間范圍???，推算出數據處理系統輸入數據流中所有對待溯源輸出數據元組的產生有貢獻的輸入數據元組，推算公式如下：

。