Idempotency

I have Idempotency in my own API to prevent consumers creating extra resources by mistake. The Idempotency-Key header is up to the consumer to figure out and set.

Consider a scenario: My API makes it's own calls to a third party API.

I want to create and retain a new Idempotency Key so that I may set it on the third party API so the third party call is idempotent. I have absolutely no idea what to set it to and how to access it the next time a request is made.

All tutorials suggest a "UUID", which makes sense, but how do I retain that UUID and access it the next time a request is made to the third party? My code will retry the API call to the third party due to some error and I need the request to be idempotent, or the user accidentally double sends and the request is not being made Idempotent by the consumer developer.

Before a third party API call I can create a cache record holding the Idem Key. I've thought of a few things that all seem wrong when caching the idem key for re-use:

• I can use the authenticated users ID. However that means the user can only make 1 call to the API (and therefore the third party API) and then has to wait for the Idem Key to expire.
• I can't just expire the cache after use as that defeats the purpose.
• I can't use timestamps because that would make it a unique key every time.
• I can't use the ID of the resource being created in my own database as it's created AFTER the third party API call is made. There are also multiple different API endpoints that make third party calls and not all of them create a resource on my own application.
• I can't use a session key because its an API call, there is no session. (besides, that would limit my app to one third party API call per user per "session".
• I can't assume a user doesn't legitimately want to make a second call a few seconds later.

Its easy enough generating the UUID for it, but retaining that key so the next time a call is made it knows to either generate a new one, or using an old one and where to fetch that old one from, eludes me!

How do you store in-use idempotency keys? What methods do you have for generating them if not a UUID?