Indexing S3 files in DynamoDB, Serverlessly

This article will explore different architectures for uploading files, like images, to a serverless backend. The files are stored in S3 and indexed by DynamoDB, where they are associated with an arbitrary domain entity. When a client queries an entity, they obtain the IDs of the files from which URLs to S3 can be derived.

In the absence of a distributed transaction between these systems, the problem we're interested in solving is how to maintain consistency between the file, in S3, and the index, in DynamoDB.

Our file management system contemplates both uploads and deletions.

A file uploading API

Let's consider the following GraphQL API for uploading files. The upload mutation will be used to obtain an S3 signed URL where we can PUT the file.

input UploadFileInput {
    entity: ID!
    md5: String!
}

type Header {
    key: String!
    value: String!
}

type UploadFilePayload {
    uploadURL: AWSURL!
    uploadHeaders: [Header!]!
}

type Mutation {
    upload(input: UploadFileInput!): UploadFilePayload!
}

The mutation accepts the file's MD5 (so the signed URL can only be used to upload files with a matching digest) and the entity ID where we'll index it. In the reply we get the upload URL and the headers to include in the PUT request. The entity ID needs to be carried as metadata throughout the system, and is contained in those headers.

Obtaining the signed URL and issuing a PUT request containing the file is the synchronous part of the architecture depicted in Figure 1.

In the background, when the file is uploaded, an S3 notification¹ triggers a Lambda function which will index the file. We know what entity to associate the file with because its ID is stored in the file metadata in S3 (it got there through the headers used in the PUT request).

Deletions and race conditions

So far so good! Let's now consider the mutation to delete a file.

input DeleteImageInput {
    url: AWSURL!
}

type DeleteImagePayload {
    _: Boolean
}

type Mutation {
    deleteImage(input: DeleteImageInput!): DeleteImagePayload!
}

A pretty simple API, but what about the backend implementation?

Ideally, uploading the file and indexing it would be an atomic, distributed transaction. But since it is done in two discrete steps, there are race conditions galore when trying to delete the file, especially if the deletion happens right after the upload.

One approach could be to delete the file in S3 and use the subsequent notification to delete the index entry in DynamoDB. The issue here is that S3 doesn't guarantee the order of notifications. There is, however, a sequencer contained in the notification payload that can be used to order the notifications for a given object. In our case, we can simply synchronize the notifications using the index, as we'll shortly describe.

S3 guarantees at-least-once delivery of notifications, so we also have to account for retries: processing the notifications must be idempotent. We will guarantee idempotence by storing a tombstone when the file is deleted. The tombstone will live for a grace period (a couple of days should be sufficient) and must be cleaned up asynchronously (either through another process or through a TTL on the file item). This will handle the following scenario:

1. The upload notification is processed and the file is indexed, but the Lambda fails for some reason;
2. A deletion happens right after and the deletion notification is processed, replacing the key by a tombstone;
3. The upload notification is retried; it now encounters a tombstone and does nothing².

Note that if we clean up the tombstone in the upload notification, we open ourselves up to the possibility of the upload being retried (either from S3 or from the user) and the file being incorrectly indexed.

If we ensure each file has a unique key in S3, an upload never wins over a deletion. Were we to allow uploads to the same key after a deletion, we would need to store the sequencer in the index (which would act as the timestamp in last-write-wins systems like Cassandra and ScyllaDB).

Alternatively, we can handle the deletion by writing the tombstone directly to DynamoDB without going through the S3 notification, since it is the index that is being used for synchronization. With this approach the deletion effect is immediately visible to an observer, instead of eventually. Asynchronously, we must clean up the tombstone and delete the file from S3 (we can periodically run a compaction process or set a TTL on the item and use DynamoDB streams to later delete the file). This is the architecture depicted in Figure 2.

Pretty complex, huh? This complexity is mostly arising from us wanting to handle a deletion in close succession to the upload, such that the notifications can overlap. Maybe if we gate the deletion on the presence of the index we can simplify our architecture. That would entail returning an error to the user if they attempt to delete the file after uploading it, while it has not been indexed yet. This isn't great UX though. We can instead store the deletion intent in a queue and keep trying to process it until the file is indexed. Here we're replacing the tombstone cleanup process with a queue, but it is perhaps simpler. There's also a period where the image can appear to resurrect, after it is indexed but before the deletion completes. This is the architecture in Figure 3.

Would a REST API be simpler?

Since there is no built-in mechanism in GraphQL to upload files, common wisdom suggests that a REST endpoint should be used for uploading instead. Will that really make a difference though? Consider the architecture in Figure 4, where an API Gateway handler receives the file to upload, writes it to S3, and indexes it in DynamoDB.

Seems pretty straightforward, right? But there's a wrinkle: the handler may fail between uploading the file to S3 and indexing it in DynamoDB. This means two things:

1. The handler must be idempotent to handle retries; and
2. A retry may not happen, so the handler should clean up after itself.

We can't simply put the request in a queue due to message size limitations, so we need a more elaborate solution. We're right back at the approaches of the previous section.

Conclusion

Indexing S3 files in DynamoDB seems straightforward, but bringing deletions into the picture sure complicates things due to potential race conditions. We looked at multiple strategies to deal with those races, balancing UX and complexity. As with most problems in distributed systems, there isn't a perfect solution.

1. It can take over a minute for the file to be indexed and available for queries. ↩

2. We must use DynamoDB conditional statements to ensure consistency. ↩