Idempotency with Locks Explained with a URL Shortener

Hey there 👋,

Welcome to my first blog post! I thought of starting with a short one. So, in this post, I'll talk about idempotency and how we can implement it with locks with a URL Shortener. You can find the code for the sample URL shortener here. It is built using nodejs and postgres.

Implementing idempotency with locks in a URL Shortener involves two steps:

We'll be focusing on the first step in this article i.e., adding locks to prevent concurrent access to the shortener's database.

With that said, let’s take a look at what idempotency is and why we'd want to make our service idempotent.

What is an idempotent operation?

Our service's POST method is currently not idempotent which means that if we send two requests to shorten the same long URL at the same time, our database would end up with two different entries.

We want to maintain a single entry for each long URL in the database. And, this should be independent of the number of (concurrent) requests we receive. But why do we end up with two different entries in the first place? Let's take a look.

What is the problem?

Let's say our service gets three identical requests (having same long URL) to shorten a URL at the same time and the logic of our service looks something like this:

We will get different entries for the same long URL. This is because our URL shortening implementation is not completely synchronous. Below is the result of firing three parallel requests using fire-parallel-requests.js,

If we take a closer look, the first step in our implementation involves a database lookup. So, our application (nodejs) is receiving the request and handing it over to the database. And, as soon as all the three requests are gone to the database, we are sure of two things:

1. We can no longer guarantee that the order of requests would be maintained.
2. All three requests are going to create three different entries because of the transaction isolation in place, which defaults to read committed in postgres.

Adding idempotency using locks

We want to make sure that only one client is able to shorten a specific URL at a time. All the other concurrent requests by other clients would simply fail with a message to try again. We are going to do this by making our URL shortening implementation (aka critical section) mutually exclusive.

This is where locks (aka mutex) comes into play. Locks make sure that the code inside the critical section is never run for more than one client at a time.

So, with the locking mechanism in place, the updated logic for our service looks like this 👇

What does "locking a resource" means and what exactly are we "locking" here?

We simply want the critical section to be mutually exclusive. Thus, we are "locking" it so that only a single client could access it at a time.

🔏 Locking a resource involves,

• Generating a unique key for a given resource,
• Storing that key somewhere (with a TTL or Time to Live).

Once lock is acquired, no other client can access that resource until the lock is released voluntarily or TTL expires.

🔓 Releasing the acquired lock simply means removing the lock key from the storage.

What happens if a client is not able to acquire the lock?

This can happen if the lock is already acquired & not released yet or there is some unexpected error during the locking process. We can ask the client to try again in that case.

With the locking mechanism in place, there won't be any double entries in our database.

What is the lock key?

Lock key is just a (unique) string that maps to a resource and their relationship is one-to-one.

The reason is, we don't want to have two requests coming to our service to shorten the same long URL at the same time. So it makes sense to choose the long URL as the lock key.

Implementing locking mechanism

I recently came across Redlock package and it is part of the reason I've put together this post. It implements Redlock algorithm for redis locks. You can simply use this package to implement (distributed) locking mechanism in your application.

For locking a resource,

• We need to build a lock key (which in our case is the long URL), and
• Try to acquire the lock with a predefined TTL

1const lock = await redlock.lock(lockKey, ttl);

For releasing the acquired lock,

1await lock.unlock();

You can even extend the lock while its not expired,

1await lock.extend(ttl);

It extends the TTL of the lock from when extend was called.

Conclusion

• We can cut the size of the critical section to further optimize the approach with locks. Instead of using one lock for the whole URL shortening, we can use two locks. One for the operation when we check for existing mapping and the other when we store the created mapping.

• Idempotency plays an important role in creating more reliable APIs. For instance, a user accidentally clicking on a buy button twice can pose a problem if the API is not idempotent. It depends on the use-case but I'll definitely have this in my consideration set moving forward.

What's next?

URL Shortener code can be found here.

To see how race condition can affect the output of URL Shortener,

• Clone the project and make sure you're on main branch.
• Install the packages and run the shortener locally.
• Open another terminal and run the script fire-parallel-requests.js.
• The output would contain different short URLs for the same long URL.

You can then checkout to lock branch and follow the same steps. You'll notice only one short URL in the output and other would error out because of not being able to acquire the lock.

That's it from me. I hope you find it useful. This was my first time encountering locks in their full glory.