一种支持数据重现的运行时递推数据溯源方法

摘要

本发明属于数据溯源领域，公开了一种支持数据重现的运行时递推数据溯源方法。将起源信息分为粗粒度起源信息和细粒度起源信息，在数据处理系统中最后一个处理单元产生输出数据元组时，对该输出数据元组的起源信息进行递推，递推得到数据处理系统中第一个处理单元的触发运行的时间范围及每个处理单元在首次运行前的状态快照；数据重现时，找到数据库中存储的每个处理单元的初始状态快照，并将查询所得的输入数据元组按原顺序及时间间隔输入数据处理系统，重现输出数据元组的产生过程。由于不需要对每个处理单元的起源信息进行存储，因此拥有更低的存储开销；在递推过程中每个处理单元的初始状态快照，能够在数据处理系统上进行完整数据重现。

主权项

1.一种支持数据重现的运行时递推数据溯源方法，其特征在于步骤如下：第一步，在数据处理系统部署时，记录其粗粒度起源信息；第二步，在数据处理系统运行过程中，记录其细粒度起源信息；第三步，在数据处理系统中最后一个处理单元产生输出数据元组时，对该输出数据元组的起源信息进行递推；递推得到数据处理系统中第一个处理单元的触发运行的时间范围及每个处理单元在首次运行前的状态快照，状态快照中记录处理单元在特定时刻的内部状态，将这些起源信息与输出数据元组一起进行持久存储；第四步，溯源查询时，根据存储在输出数据元组中的第一个处理单元的触发运行的时间范围，推算出数据处理系统输入数据流中所有对待溯源输出数据元组的产生有贡献的输入数据元组；第五步，数据重现时，找到数据库中存储的每个处理单元的初始状态快照，将数据处理系统中每个处理单元恢复至状态快照时，并将第四步溯源查询所得的输入数据元组按原顺序及时间间隔输入数据处理系统，重现输出数据元组的产生过程。2. 根据权利要求1所述的低存储开销的运行时递推数据溯源方法，其特征在于：在数据处理系统部署时，记录的粗粒度起源信息包括：a)基于元组数量计算的每个处理单元的计算窗口类型；b)每个处理单元的计算窗口大小，窗口大小为元组数量。3. 根据权利要求1所述的低存储开销的运行时递推数据溯源方法，其特征在于：在数据处理系统部署时，记录的粗粒度起源信息包括：a)基于时间长度计算的每个处理单元的计算窗口类型；b)每个处理单元的计算窗口大小，窗口大小为时间长度。4. 根据权利要求1所述的支持数据重现的运行时递推数据溯源方法，其特征在于：在数据处理系统运行过程中，需要持久记录的细粒度起源信息包括：a)系统输入数据流中所有输入数据元组的值及其进入数据处理系统的时间；b)系统输出数据流中所有输出数据元组的值及其产生时间；c)系统在产生输出数据元组过程中，每个处理单元首次运行前的状态快照。需要临时存储的细粒度起源信息包括：a)每个处理单元每次运行前的状态快照；b)每个处理单元每次运行的触发时间；c)每个处理单元每次运行的处理延迟。5. 根据权利要求2所述的支持数据重现的运行时递推数据溯源方法，其特征在于：在数据处理系统中最后一个处理单元产生输出数据元组时，对该输出数据元组的起源信息进行递推。递推公式如下：其中。6.根据权利要求1所述的支持数据重现的运行时递推数据溯源方法，其特征在于：溯源查询时，根据存储在输出数据元组中的PU1的触发运行的时间范围，推算出数据处理系统输入数据流中所有对待溯源输出数据元组的产生有贡献的输入数据元组，推算公式如下：。