Yeah but what about something that won't make my wallet cry?

Pretty much any queue and a compute will do. SQS paired with lambda an event bridge (I forget if that's the service to trigger the lambda or not) would be solid. I lean towards compute that's a bit easier to run in different settings so just any old code checking the queue and executing as expected also works. SQS is cheap and it's pretty damn solid. I believe it was the first AWS service.

But in reality, any managed queue or even a well structured DB table can be fine, depending on your scale.

Is using Lambda with an external data store (like MongoDB) a solved problem?

I remember this being an issue a long time ago, where Lambda pretty much was a non starter for use cases where you're running 1000 independent tasks that each, on their own, is a small unit of work (just 1 or 2 database queries).

Long way of asking: is there a way to share a database connection between lambda functions or does each run need to re-establish / re-authenticate a new connection with the database?

Declare your connection outside of your handler function - this post is from 2017 but it shows it clearly:

https://www.jeremydaly.com/reuse-database-connections-aws-la...

It will get re-used across lambda invocations as long as the instance of it isn't killed which typically happens after a few minutes

For MongoDB specifically see the best practices docs for Lambda (https://www.mongodb.com/docs/atlas/manage-connections-aws-la...).

This outlines creating the handler outside the function context to allow the client to be reused between invocations.

Spot and any queue