背景:Data Provenance

在CS学术领域有个术语叫做Data Provenance,有人翻译为“数据世系”。实际上,就是一个文件的meta data,属性信息。只不过这里的属性记录得更加详细,颇有些log的意味。简单来说,就是“谁创建了它”、“谁对它做了什么修改”、“数据流传输到了哪里”等等一系列记录。在我们的数据出现异常的时候,数据世系能帮助我们追溯根源,在程序debug、核实取证以及数据恢复上也都有着巨大用途。

例如,在电信网络流量管理中,一些异常检测工具能够及时的发现网络流量中的异常,但是这些工具并不能检测出是什么原因导致的异常,异常发生在哪里?如果系统能够追踪流数据的世系,那么用户可以确定数据演化过程以及产生异常的原始流,定位并确定异常产生的原因。

问题来了,数据和对应的数据世系实际上是分离的,是两份不同的文件。要满足我们的需求,数据世系必须具有以下特点:

  • 数据世系与数据的映射耦合。即数据世系要能够精确无误地描述数据,我们使用原子性和一致性来保障这个机制。原子性的意思是,在存储期间,数据和数据世系必须同时存在,或同时不存在。一致性则表示在查询时,数据必须与数据世系中的记录保持一致。
  • Causal Ordering。即事件发生的先后次序描述。如果B是改变A的某些数据后得到的结果,那么A就存在(发生)在B之前,或者说A是B的前一个版本,因而A的数据世系是B的数据世系的子集。
  • 独立数据的持久性。假设A发生在B之前,如果A被删除了,B的数据世系仍旧应该包含A的数据世系。
  • 有效查询。用户想要验证他们数据的属性,数据世系应该能够随时提供高效的查询结果。

这些在分布式系统中都是经典问题,特别是一致性和Ordering,有各种各样的实现方式。我将在另一篇文章中详细介绍相关理论。本篇所要描述的,是如果通过现有云计算平台提供的服务来实现数据和数据世系存储系统PASS(Provenance-Aware Storage System),更广义地来看,其实是实现数据和元数据(data and its metadata)的存储一致性。

使用Amazon云服务实现数据世系

这里会使用到三项Amazon Cloud服务:S3, SimpleDB, SQS。S3是已经介绍过的云端存储,SimpleDB是一套基于key-value型的数据库服务,SQS是一种分布式排队服务。

1. 仅使用S3来实现

仅使用S3的系统结构

仅使用S3的系统结构

仅使用S3的协议

仅使用S3的协议

S3可以支持最大5GB的数据存储,并提供SOAP和REST接口。使用S3可以保证最终一致性Eventual consistency和causal ordering。但如果客户端程序在上传了数据世系后崩溃,S3中就仅有数据世系而没有对应的数据,系统就失去了原子性。另外,数据查询是低效的,因为我们无法通过单独的数据世系来获取对应数据。

2. 使用S3 + SimpleDB实现

SimpleDB的数据存储为name-value对的形式,并最多支持256个attributes。在SimpleDB中,数据世系被表示为数据库条目,例如

ItemName=uuid1_2
attribute-name=name,attribute-value=foo
attribute-name=input,attribute-value=bar_2
attribute-name=type,attribute-value=file

使用S3 + SimpleDB的系统结构

使用S3 + SimpleDB的系统结构

S3 + SimpleDB的协议

S3 + SimpleDB的协议

这种方式支持了causality ordering,并且查询效率高。不过原子性仍然没有保证。

3. 使用S3 + SimpleDB + SQS实现

SQS是一个分布式消息队列系统,队列以URL作标识,它支持SendMessage, ReceiveMessage, DeleteMessage操作。不过SQS仅支持8KB的消息队列大小。

S3 + SimpleDB + SQS的系统结构

S3 + SimpleDB + SQS的系统结构

S3 + SimpleDB + SQS的协议

S3 + SimpleDB + SQS的协议

SQS和本地Log日志不同,如果本地log损坏了,所有的记录都会丢失。而SQS将记录保存在云端,具有健壮性。如果commit进程崩溃,我们仍然可以启动另一个commit进程并执行剩下的事务操作。

上图中S3 + SimpleDB + SQS这个协议执行过程分为两大步,这里详细解释一下:

步骤一Log: 将数据记录在队列中
1. 上传数据到S3中,作为一个临时存储副本。
2. 分配一个事务ID (uuid)
3. 将数据世系分割为8KB的数据块,并加入到SQS队列中。为每个队列消息加上uuid标签,然后增加一条指向S3中临时数据的记录。

步骤二Commit: 将数据从队列传到S3和SimpleDB中
1. ReceiveMessage: 从队列中获取消息并组装数据包
2.调用PutAttributes操作,将数据世系存储到 SimpleDB中
3. 执行S3 COPY操作,将数据从临时存储复制出来,永久存储。
4. 从SQS队列中删除消息
5. 从S3中删除临时数据

三种方式的比较

图表说明一切

属性 P1 P2 P3
原子性 ×
Causality ordering
高效查询 ×

P1 = S3
P2 = S3 + SimpleDB
P3 = S3 + SimpleDB + SQS

注:本文部分内容编译自哈佛大学Muniswamy-Reddy的论文Provenance for the Cloud