Async Recursion with backoff

It’s been a while since I published anything. More than three years! A lot of things happened since then. The most relevant to mention in the beginning of this post is that I have been super busy building a lot of cool tech with a very talented team here at EPAM Anywhere. We are doing full-stack Typescript with next.js and native AWS serverless services and can’t get enough of it. This experience has been challenging me to learn new things every day and I have a lot to share!

Today I want to show you one particular technique that I found super useful when I need to safely use aws-sdk batch APIs and ensure delivery.

When you work with AWS, you will certainly use aws-sdk and APIs of different services. Need to send a message to an SQS queue? That’s an HTTP API call and you will use sdk. Need to update a document in DynamoDB? The same. Need to push a message to the Firehose? The same. Many of these APIs have their batch equivalents:

These batch APIs will throw if something fundamental is wrong. Say your auth is not good or you don’t have enough permissions or you don’t have the connectivity to the service. If the sdk connected successfully to the service but failed to perform some or all of the operations in your batch, the operation won’t throw. It will return an object that tells you which operations succeeded and which ones failed. The most likely reason to get partial failures is due to throttling. All of these APIs have soft and hard limits and sooner or later you will attempt to do more than AWS feels comfortable letting you get away with.

We learned it the hard way. It’s all documented, obviously, but things like this one are only obvious in hindsight. Let me show you a neat technique to batch safely but first, some background.

Recursion

I always liked recursion. When you need to scroll through something that paginates, you can employ while loops or you can recursively repeat and accumulate results as you go. The recursion always felt much cleaner to me but it comes with a gotcha - no stack is infinite. Consider the following simple example:

1
2
3
4
5
6
7
8
9
10
11
12
13
let iteration = 0;

const op = () => {
++iteration;

return iteration === 100000 ? iteration : op();
};

try {
console.log(op());
} catch (error) {
console.error(iteration);
}

This snippet won’t print 100000. When I run it with node sample.js, I get 15707 printed in the console. Your mileage may vary but you know you can reach the deep end and go no further. The error that I am not reporting is Maximum call stack size exceeded.

Async Recursion

What if op() was performing a network operation? Let’s simulate it and convert op() to an async op():

1
2
3
4
5
6
7
8
9
let iteration = 0;

const op = async () => {
await Promise.resolve(++iteration);

return iteration === 100000 ? iteration : op();
};

op().then(console.log).catch(console.error);

It prints 100000 and we do not exhaust the stack. Let’s understand why and we will be well on our way to leveraging this technique in real world scenarios.

The trick is in how promises (and async functions that return them) use event loop to schedule continuations. I highly recommend this article to get a deeper insight into how it all works. And here’s specifically about promises.

Basically, Promises use micro tasks just like process.nextTick() does and since the callback runs via the event loop, the stack frame is short lived and every recursive invocation has its own.

Let me do the same but this time I will be more explicit:

1
2
3
4
5
6
7
8
9
10
11
let iteration = 0;

const op = () => {
++iteration;

return iteration === 100000
? iteration
: new Promise((resolve) => process.nextTick(() => resolve(op())));
};

op().then(console.log).catch(console.error);

It also prints 100000 but here you can see how I “delay” promise resolution via the callback scheduled on the event loop. It adds one more ingredient that I need to explain.

I am using a trick of promise nesting when I do resolve(op()). When a promise A resolves with a promise B, the result of A is the resolved value of B. Since my op() keeps recursing onto itself, the last promise’s resolved value will be the value returned by the first call to the op().

Async Recursion with backoff

The last thing that I want to illustrate before I show you how I use this technique with aws-sdk APIs is a recursion with a backoff strategy. Take a look:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const { performance } = require("perf_hooks");

let iteration = 0;
const start = performance.now();

const op = () => {
++iteration;;

return iteration === 10
? performance.now() - start
: new Promise((resolve) => setTimeout(() => resolve(op()), iteration));
};

op().then(console.log).catch(console.error);

It prints a value somewhere around 50. The code goes through 10 executions of op() and delays each next run by iteration milliseconds. So +1, then +2, then +3, up to +9 for the last run. We stop when ++iteration is equal to 10 so we only run through 9 via setTimeout(). The sum of the arithmetic progression from 1 to 9 with a step of 1 is 45 but op() doesn’t run exactly at the interval we ask for plus performance.now() isn’t exactly 0ms so let’s call the difference an overhead.

AWS batch APIs with retries

We are now ready to put it all together and employ async recursion with backoff technique with the batch APIs to ensure delivery.

First, the backoff strategies:

1
2
3
4
5
6
7
8
export type BackoffStrategy = (retryCount: number) => number;

export const attemptTimesOneHundredMs: BackoffStrategy = (attempt: number) =>
100 * attempt;

export const attemptSquaredTimesOneHundredMs: BackoffStrategy = (
attempt: number
) => Math.pow(attempt, 2) * 100;

SQS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
interface SQSBatchDeliveryOptions {
readonly sqs: SQS;
readonly queueUrl: string;
readonly retries?: number;
readonly backoff?: BackoffStrategy;
}
/**
* Perform batch write to the SQS. All records that failed will be retried with a backoff.
*
* The method will throw if we failed to deliver the batch after we exhausted the allowed retries.
*
* This factory method returns a reusable function that you can use over and over again if you are sending batches to the same `queue`.
*
* **NOTE** We are not checking any limits imposed by AWS/SQS. As of the time of this writing:
* - no more than 10 messages per batch
* - a message (and a batch as a whole) cannot be larger than 256Kb. We have helpers that do S3 bypass.
* - a message in each batch can only be ASCII with a few exceptions. Base64 encoding is recommended and we have helpers that you can use
*
* @param sqs instantiated sqs client
* @param queueUrl the queue URL to work with
* @param retries how many times to retry. default is 5
* @param backoff backoff strategy that can be calculated based on the attempt number. the default is 100ms * attempt
* @returns the reusable function that you call with your batch details

*/
export const deliverBatchToSqs =
({ sqs, queueUrl, retries = 5, backoff = attemptTimesOneHundredMs }: SQSBatchDeliveryOptions) =>
(batch: SQS.SendMessageBatchRequestEntryList): Promise<void> => {
const run = async (batch: SQS.SendMessageBatchRequestEntryList, attempt: number): Promise<void> => {
if (attempt > retries) {
throw new Error(`Failed to deliver batch after ${attempt} attempts`);
}

const { Failed } = await sqs.sendMessageBatch({ QueueUrl: queueUrl, Entries: batch }).promise();

if (Failed.length > 0) {
const retry = batch.filter((entry) => Failed.find((failed) => failed.Id === entry.Id));
if (retry.length > 0) {
return new Promise((resolve) => setTimeout(() => resolve(run(retry, attempt + 1)), backoff(attempt)));
}
}
};

return run(batch, 1);
};

And then somewhere else in the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
async dispatch(events: Message[]): Promise<void> {
const batches = batchBy10AndNoMoreThan256KbEach(events);

const deliver = deliverBatchToSqs({ sqs: this.sqs, queueUrl: this.queue, logger });

await Promise.all(
batches.map((batch) =>
deliver(
batch.map((message) => ({
Id: nanoid(),
MessageGroupId: message.groupId,
MessageDeduplicationId: message.key,
MessageBody: message.payload,
}))
)
)
);
}

DynamoDB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
interface DynamoBatchDeliveryOptions {
readonly db: DocumentClient;
readonly table: string;
readonly retries?: number;
readonly backoff?: BackoffStrategy;
}

/**
* Perform batch write/delete to the DynamoDB. All records that failed will be retried up to five times with a backoff.
* The method will throw if we failed to deliver the batch after the specified number of retries. Default is 5
*
* This factory method returns a reusable function that you can use over and over again if you are sending batches to the same `table`.
*
* **NOTE** We are not checking any limits imposed by AWS/Dynamo. As of the time of this writing:
* - 25 requests per batch
* - max document size is 400Kb including attribute name lengths
* - the total size of items written cannot exceed 16Mb (400x25 is less btw)
*
* @param db instantiated document client
* @param table the name of the DynamoDB table to work with
* @param retries how many times to retry. default is 5
* @param backoff backoff strategy that can be calculated based on the attempt number. the default is 100ms * attempt
* @returns the reusable function that you call with your batch details
*/
export const deliverBatchToDynamo =
({ db, table, retries = 5, backoff = attemptTimesOneHundredMs }: DynamoBatchDeliveryOptions) =>
(batch: DocumentClient.WriteRequests): Promise<void> => {
const run = async (batch: DocumentClient.WriteRequests, attempt: number): Promise<void> => {
if (attempt > retries) {
throw new Error(`Failed to deliver batch after ${attempt} attempts`);
}

const { UnprocessedItems } = await db.batchWrite({ RequestItems: { [table]: batch } }).promise();

if (UnprocessedItems) {
const retry = UnprocessedItems[table];
if (retry?.length) {
return new Promise((resolve) => setTimeout(() => resolve(run(retry, attempt + 1)), backoff(attempt)));
}
}
};

return run(batch, 1);
};

I have to say that we are not using this technique in our request/response APIs. We are pretty serious about building fast and pleasant experiences and so we target sub-half-second for user facing APIs. We use this technique anywhere else though - async step functions, batch operations, code that is responding to external events.

That’s it for today. I hope you found it useful. More to come soon!

Author

Pavel Veller

Posted on

July 14, 2022

Updated on

May 29, 2025

Licensed under

Comments