Feature request: Distributed Lock Client

[codyfrisch]

Use case

I believe incorporating a distributed lock client into the powertools would be of value. There are times multiple events being processed need to update the same resource (requires making calls to some API to retrieve updated data, and updating a record). The triggering events may not even be related to each other, other than all triggering an update.

A distributed lock would permit one event to perform the needed work and update a record, while others wait for it to finish (or skip entirely). This saves on calls to APIs (rate limits exist), and possibly save on execution time by skipping the update being handled by another instance.

Example is an application that from time to time needs to get updated data for a customer account from a third party service (the application is a plugin for the service, the data needed is the subscription and account details for the plugin from the third-party marketplace). These updates are needed for execution. One incoming event can gain a lock while updating data for the account, other executions will wait while the update occurs and check for the lock to be released (time required for the update is well understood and <1s).

Another is setting up per-minute distributed rate limit tracking - when an event is received a dynamodb record is created to track the number of requests received in a minute. Different account tiers have different limits. When a tracking record is needed, an API call must be made to get the account tier, current minute API usage (if any) as well as start the API minute timer (so the windows are deterministic). A distributed lock would prevent many incoming events from duplicating this work (and contributing to the API rate limit being tracked!). The rate tracking record allows additional requests to receive a 429 response, causing the external platform to continue to display "in progress" rather than a false "success" if the event were queued. This also minimizes needless executions to find out that the rate limits have been reached.

Solution/User Experience

I would suggest a DynamoDB based lock, built on conditional expressions much like the idempotency tool. There is an existing Java based client in awslabs, https://github.com/awslabs/amazon-dynamodb-lock-client, and at least one defunct typescript based project, https://www.npmjs.com/package/@deliveryhero/dynamodb-lock.

(I am internally developing a DynamoDB based distributed lock, as I need it, and am open to contributing if I can get authorization, and up to speed on this project. Though an ElastiCache based solution would probably be a more efficient solution, it has higher costs at low volume.)

Alternative solutions

Alternative solutions could use ElastiCache, Valkey, Redis, etc. or there could be multiple provider choices within the module.

Acknowledgment

• This feature request meets Powertools for AWS Lambda (TypeScript) Tenets
• Should this be considered in other Powertools for AWS Lambda languages? i.e. Python, Java, and .NET

Future readers

Please react with 👍 and your use case to help us understand customer demand.

[am29d]

Hey @codyfrisch

A distributed lock would permit one event to perform the needed work and update a record, while others wait for it to finish (or skip entirely). This saves on calls to APIs (rate limits exist), and possibly save on execution time by skipping the update being handled by another instance.

How is this different from idempotency? This is exactly what we solve right now with idempotency by having a specific record for a payload execution with expiration and return payload.

Having a lock for rate-limit is something I agree with. I have had customers in the past asking for the same feature, where they have a configuration for each 3rd party API which need its on rate limit, but from the a consumer perspective. I don't think it's an optimal solution to let the client rate limit itself, but the reality is that it is needed in some cases.

However, EventBridge offers solution for exactly this situation, calling API with a rate limiter.

(Optional) For Invocation rate limit per second field, enter the maximum number of invocations per second to send to the API destination endpoint.

You can also do the reverse, let EventBridge invoke your Lambda function with a rate limit, wich of course adds latency and infrastructure configuration, but removes the necessity for a dedicated custom rate-limit solution.

I'd love to add rate-limiter to our set of tools, but we really need understand the use cases and constrains that would make it easier, than current solutions.

[dreamorosi]

Hi @codyfrisch - apologies for the late reply. The issue fell through the cracks of re:Invent and end of year leaves.

I'd like to understand a bit more about the request, primarily since as you also call out there's quite a lot of similarity with the already existing Idempotency utility.

Could you please share an example of where the Idempotency utility falls short for this type of use cases? I think that would help better understand what this distributed lock would add.

At least based on my current understanding, despite the name and framing on the documentation, the Idempotency utility we have today already acts as a lock mechanism in the sense that whenever a request is first seen, an idempotency record for that transaction is created (aka the lock) and any other request attempting to perform the operation on the same payload would get rejected. Possibly the only missing piece is a lock release mechanism, but using a short idempotency ttl would equate to an immediate release.

Regarding the distributed rate-limiter, I am not 100% sure this is a concern that belongs within a Lambda function and that perhaps would be better handled at the WAF or API Gateway level. But maybe it's something to explore.

[codyfrisch]

@dreamorosi primary difference from the Idempotency tool is that these are not per-request based but per resource based. It could be something that is happening across many separate requests - including entirely different endpoints. Additionally the use is different, separate executions would wait for release without returning and then either take a lock themselves or act on the results of the operations performed by the execution that had the lock. Idempotency is close, beyond a direct release mechanism, there also needs to be a polling mechanism (for trying to acquire a released lock) and renewal mechanism (to extend the lock) These are short duration (500ms or so) and if there is a failure where it is not released you want an instance polling the lock to be able to acquire it based simply on the conditional expression and the lack of a timely renewal.

The rate limiter was an example of a use case for this, not its own request. The lock is on the operation of getting rate limit data from the third-party API (how many requests have been made, consumed query/mutation complexity (this is graphql)) which in itself consumes API requests - if all request to my service were to make the same API call the API would reach its limits much sooner and reduce throughput (or prevent any real executions all together!). By creating a lock on the API for this call, in a thundering herd situation (very common), one execution makes the call and gets the results while the others wait (~300ms), and once the lock is released they are now able to use the rate limit data the locking process cached in dynamodb (or whatever persistence layer the developer chooses). (I won't get into the details of the actual rate limting, thats irrelevant).

Basically, between lambda executions which themselves are not idempotent - there are routines that are, despite the overall requests not being.

[leandrodamascena]

Thanks for the detailed explanation @codyfrisch! We are a team maintaining Powertools - that's why sometimes some of us may comment on the same issue - and we are very interested in hearing from our customers about their needs.

To avoid wrong assumptions and misunderstandings on my part, I will add my thoughts to make sure I understood the point, ask questions or try to get more information.

Persistent storage

If we agree to implement this, we will need to decide on a backend to store the lock mechanism. I see an opportunity here to use DynamoDB, Redis and probably some SQL database like Aurora DSQL. Do you have any other storage layer in mind? Lambda is stateless by design and we can't store things in memory and assume this will be available in all the requests, so, we need a persistent storage.

Per-request based but per resource based

This is clear to me, you want a mechanism that will be divided between Lambda functions, endpoints and maybe different operations/workloads. The main point of this mechanism is to avoid concurrent calls to an external service from happening, here I have my first questions:

1 - What are these external services? APIs? Database queries? Other? Any kind of block of code?
2 - What is the identifier that will make that operation part of the distributed lock? The name of the lock?

There also needs to be a polling mechanism for acquire and renew:

To acquire the lock, it is clear to me that Powertools should do it, but the renew part I am not sure if it is the responsibility of Powertools or the customer who does the renew polling? Let me try to explain this with code. I'm not the best at TypeScript, so I'll do it using python pseudocode:

Powertools

lock = DynamoDBLock('LockTable', 'rate_limit_data')
lock.renew()

Class DynamoDBLock:
  
  def renew(self,...):
    While True:
       ...

Customer

lock = DynamoDBLock('LockTable', 'rate_limit_data')
    
  while True:
      time.sleep(0.1)  # Renew every 100ms
      lock.renew()

The main difference here is that whoever has control over polling to acquire renew can have better control over Lambda timeout.

Dealing with timeouts

Unlike other execution platforms, Lambda is an environment that has a fixed execution timeout. Acquiring a lock can be a process that takes seconds or minutes, depending on what the customer configures. In Lambda, we also have no way to control the execution SIGTERM and release the lock or stop the polling, for example, which can result in executions being terminated with timeout and affecting part of the customer's logic. Do you see any solution to deal with this?

Costs

Polling to try to acquire a lock in DynamoDB can be a expensive operation due to DynamoDB's billing model. In my mind we would have to do something like the code below, and even if the insert is not successful because ConditionExpression is not satisfactory, the customer will still pay the WCU. This is a point we need to think about.

def acquire(self):
	while True:
	    try:
	        response = self.table.put_item(
	            Item={...},
	            ConditionExpression='attribute_not_exists(lock_name) OR expiry < :current_time',
	            ExpressionAttributeValues={':current_time': int(time.time() * 1000)}
	        )
	        return True
	    except ClientError as e:
	        if e.response['Error']['Code'] != 'ConditionalCheckFailedException':
	            raise
	        time.sleep(0.05)  # Poll every 50ms or configured time

These are my points so far and we need to iterate more times to have more clarity on the solution, but I see excellent potential in this feature.

Please let me know what you think and I can clarify any points that are unclear.

[codyfrisch]

@leandrodamascena

Storage

persistent storage could by dynamodb or redis/valkey (elasticache), or SQL. I used dynamodb in my implementation (I should make that clear, I wrote this since submitting the suggestion and its currently live and working). Redis/Elasticache would be ideal but also adds some complexity since now VPCs are required and other considerations.

Costs & Polling/Renewals

As far as the costs of the polling mechanism and the timeouts - yes, the expectation is these are for short lived situations. 1-5s tops. My implementation is 500ms polls and 333ms renews. The lock duration is 1500ms, and each renewal advances it by 333ms. There is also a hard max duration of 3000ms in my implementation. When the lock is released the dynamodb item is changed to released (a boolean value). My experience is its an average of 1 renewal per request, rarely 2 (less than 15% of the time). Polling tends to match of course.

Something else to remember is in this use case, once the lambda instance that gets the initial lock completes - the rest that were polling use its result rather than acquiring the lock - all stop waiting on next poll interval. Further requests within the 60s window of the rate limit will then use that result and never attempt to lock in the first place. My experience is at most 10 instances will be outstanding waiting for a lock to release (per customer account), before the data exists and they can proceed. Additional requests find the data for the rate limit and proceed without ever acquiring a lock - they just increment values until they are over a limit then return 429. (I know how much capacity each incoming request requires in advance.)

Timeouts

As far as the timeouts, that is the reason for the renewal - the lock is set with a short duration and the timestamp, the renewals advance the timestamp by short intervals. If there is a failure, the timestamp of the last renewal plus the lock duration will soon be in the past, and the lock will be considered stale.

I also pass the getRemainingTimeMs() function from the lambda context in, that is check at various point in process and controls some limits (its also checked during renewal and polling). If it reaches a threshold, a release and cleanup happens. The lock also provides an AbortController() which can signal if renewal goes past limits, or the lock gets snatched in some way, or gets aborted by remaining time. Anything depending on the lock can then abort accordingly.

Theory of Operation

I use a version ID which is set when the lock is first acquired. When trying to acquire the lock, it is first retrieved, checked if its released (or non-existent, or expired/stale). That existing version identifier (UUID) is used when the acquire lock call is made - part of the conditional expression. When it acquires the lock, it sets its own version at the same time blocking any others which had gotten the same older version UUID but not yet acquired it, and additional requests will get the new lock which is unreleased and not stale and go into waiting as well.

When released, new lock attempts get the UUID set last time the lock was acquired and release, and the process repeats itself.

As far as the identifiers, in my use case, the partition key is lock#${accountID} and the sort key is the resource being locked (rate-limit) since the rate limit is per account.

The use cases I've come up with have all be dealing with thundering herds, to prevent me from propagating that effect. But that is an inherent issue caused by the platform I am providing a plugin "App" to - which I guess I will go ahead and reveal is monday.com. I'm sure there are other use cases out there though - part of why I wanted others to chime in, so we can learn what they might be.

[leandrodamascena]

Thanks for explaining these points with too much detail @codyfrisch! Let's give some time for other maintainers to read this and give their opinions. In the meantime, do you have any public branches or repositories where we can see your implementation? I'd be very interested in reading the code to understand how you're addressing some challenges when implementing this.

[codyfrisch]

I airlifted the code out of the repo, but here it is: https://github.com/codyfrisch/distributed-lock. Its ugly. Don't laugh. Its what you get when you're in "just make it work" mode. But if anyone notices anything "wrong" please tell me.

Thanks for explaining these points with too much detail @codyfrisch! Let's give some time for other maintainers to read this and give their opinions. In the meantime, do you have any public branches or repositories where we can see your implementation? I'd be very interested in reading the code to understand how you're addressing some challenges when implementing this.