If your IDs are completely unique, you could add them to a Bloom filter [0] when cleaning up the resource. Then you could use that to determine if an incoming ID has possibly been used before or definitely not.

[0] https://en.wikipedia.org/wiki/Bloom_filter

Bloom filters are probabilistic, meaning they don't always produce the right result. From the article you posted:

> False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter); the more elements that are added to the set, the larger the probability of false positives.

So I don't think they're the right choice for this problem, if you actually depend on the result "not here" vs "never was here" being right.

Or you could just have your IDs be monotonically increasing and look at the minimum. Any task prior to that number is "410 Gone" by definition.

> Because your storage requirements would grow indefinitely as you would need to store a record for every task ever performed.

The only info that needs to be stored is the ID of the finished task. If, say, the ID is expressed as a GUID then we're talking about 4 ints or 2 longs worth of data.

Even so, these records are supposed to be garbage collected.

You could keep it very tight. IME it’s the index overhead that kills (1000 times as much data makes inserts 10x slower), and ever since partial indexes became a thing that’s a bit less of a problem.

Also deleting is far from free of side effects.

Sure, but what's wrong with that?

So? Storage is cheap. Even supposing you were going to store every single one as a 16 byte UUID, you can store 2^32 such ids in 2^32*2^4=2^36 bytes=~64GB. Is that a large database in your mind?