Waiting List Queue using AWS Lambda & ElastiCache

There are a bunch of caveats that I stumbled upon while trying to achieve a simple yet concrete solution for setting up a waiting list queuing system in AWS. Googling ‘how to create a waiting list queue in AWS’ didn’t give back the search results we were looking for, so hopefully, this is indexed in google and is a help to the developers like you who are trying to achieve this as well.

How should the waiting list function

1. User is able to sign-up for a waiting list
2. User is assigned to a certain position depending on the time of signing up to the waiting list
3. The queueing position has to change depending on the removal and addition of any users in the waiting list

Simple right? Let’s break them down…

The problem 🤷🏼

User is able to sign-up for a waiting list

DynamoDB might sound like a great idea, since hey we are using AWS service to develop this feature why not just stick with the shiniest tool we have under our hands. This can store all the information we require regarding the user in one place such as his basic information and also the waiting list position.

The customer is assigned to a position depending on the point in time and the number of signups that already exists on the waiting list

This is where it becomes tricky. At first, you might think, well that’s easy. With a simple count operation, I am able to give the position of the customer in the queue depending on the amount of already signed up customers in the waiting list. Yes, but what about the next two important aspects we are trying to achieve?

The queueing position has to change depending on the removal and addition of any user in the list

Imagine having hundreds or even thousands of sign-ups, counting all of the waiting list entries to calculate a position for the newly added entry to the waiting list will consume a lot of DynamoDB read capacity units, which means $$$. Also, an even more complex operation is re-calculating the new positions for the entries that were shifted back in the queue based on a user action that resulted in the entry being pushed to the front of the queue. This leads to the need to read these entries, calculate their new positions, and update their positions, which of course results in… RCUs ($$$) + WCUs ($$$).

Solution 💡

I am a firm believer in ‘use the right tool for the job’. DynamoDB isn’t the right tool in this situation, at least for figuring out the positions and modifying them on the fly, which is the core of the whole feature. Luckily, there exists another type of datastore that can handle this use case (almost) flawlessly and that is Redis (ElastiCache).

Redis provides us with a type of list called sorted set. A sorted set has a name, a list of items (also called members), and a score. The sorted set will automatically take care of adding, removing, and calculating the position (index) depending on the given score of the item.

In our case the sorted set will have the name “waitingList”, the members will be the customer ids, and scores will be numbers that we assign to the customer as a position. A wonderful resource to learn about sorted sets https://www.youtube.com/watch?v=XqSK-4oEoAc

Architecture 📝

The architecture is straightforward. We have an API Gateway that exposes multiple endpoints so that our users can send a request to either add themselves to the waiting list. Behind the API Gateway, there will be two tiers of lambda functions before our ElastiCache (Redis). The first lambda function will be the public one that will listen to the request of our users from the API Gateway, and will then invoke the second lambda that actually has the connection to the ElastiCache. This way the lambda that is attached to the ElastiCache VPC is not publicly available, and this adds a ‘security layer’.

Implementation Details 📬

Accessing ElastiCache via a Lambda Function

One caveat when working with Lambda and ElastiCache is that ElastiCache is not a serverless service. It is a managed service, but it differs in multiple ways when comparing it with a real serverless service such as Lambda.

Lambda lives in the ‘AWS network’ and we don’t need to create a VPC and deploy it into one, ElastiCache on the other hand does. This results in our ElastiCache Redis server living in its own network and is completely isolated from the Lambdas we use in our application, therefore passing just the connection URL of the Redis server to the Lambda as an environment variable and trying to connect to Redis won’t cut it. Luckily, we can attach a Lambda to a VPC. Again, it’s attached to and not deployed in a VPC. There is a difference between them. You can read more on how to attach a Lambda to a VPC and what does it exactly mean via https://docs.aws.amazon.com/lambda/latest/dg/configuration-vpc.html & https://www.youtube.com/watch?v=beV1AYyhgYA

The gist is that you can attach a Lambda to the VPC that is running an ElastiCache cluster by defining the subnets and security groups of the VPC to the lambda. Also, to resolve the ElastiCache cluster URL in your attached lambda function you also need to enable DNS support for your VPC.

Handling changing positions using Redis sorted set

When you add a member with a score to a sorted set, Redis will sort it by the given score. There are two problems here

1. Adding two members after one another with the same score will position the second added member in front of the first one. This is against what a queue stands for. First come, first serve right?
2. When a user does a certain action that results in a change to his/her score, his position changes depending on the members and their scores in the sorted setlist. That’s fine, that works as it should be. But when another user takes the same action at a later point, and his/her score equals to the user that earlier had their score changed, the recently score changed user will take over the position, and will be placed in a position that is before the other user. This also breaks the first come first serve rule we have.

Since we highly depend on the time when the user signs up to the waiting list, we can take that time as part of our score. By default, every user will be assigned a score of 1 as soon as they sign up to the waiting list, but if all of our users will have a score of 1 Redis will add the latest user to the front of the queue. To overcome this issue, we can use the date and time (epoch) and set them as the fractional part of the decimal.

function generateScore(signedUpDate: Date): number {
  const MAX_VALUE = 9999999999999;
  const dateTimeInEpoch = Math.floor(signedUpDate.getTime() / 1000);
  return Number(`1.${MAX_VALUE - dateTimeInEpoch}`);
  
}

In the above function, is the implementation of what has just been described. Using the date and time as the fractional of the score in order for redis to correctly sort the waiting list sign-ups. We take a single argument which is the ISO date string of the date and time of when the user signed up to the waiting list. We convert the date and time into epoch (number) so we can actually use it as a valid score in the Redis sorted set. The most important part is the deduction of the constant MAX_VALUE with the epoch time. The MAX_VALUE is basically 9 x 13 (maximum digits in epoch). We use this constant to deduct the epoch time of the waiting list creation date because any other user with a later date will sign-up to the waiting list, the generated score will have a higher number of its fractional part. This is the trick that dictates the correct ordering when querying the sorted set.

Getting the users position from Redis

My preferred swiss knife to interact with Redis in Node is ioredis. Below is a small snippet on how to query the user's position from a sorted set. Using zrevrank method, we query a certain user by his/her ID from a sorted set, waitingListKey in this case, where redis will sort the list in descending order and returning the index of the user. Note that here, it’s an index, so to actually get the correct position, we need to increment the returned value from redis by one.

import Redis from 'ioredis';

var client = new Redis({
    host: '127.0.0.1',
    port: 6379,
});


var waitingListKey = 'myWaitingList';


async getMemberIndex(member: string): Promise<number> {
    return client.zrevrank(waitingListKey, member);
}


async getPosition(userId: string): Promise<number> {    
    const index = await getMemberIndex(userId);
    const position = Number(index) + 1;
    return position;
    
}

Hope this has helped you in some way. :)