A Bloom or cuckoo filter would allow for efficient tracking of nonces (depending if the security model prefers false positives with 4xx/resend, or false negatives)
Still not ideal in a distributed environment, a request may have to synchronously go around the world to hit that nonce db.