As nonce is supposed to be random and used only one time, when receiving a nonce, I need to check it with all past nonce records. That means I need a database to store every nonce I had before. Of course I can reduce the database size by limiting the life circle for nonces. But I am curious about how people handle this issue in practice. Is there any efficient way to store and verify a nonce? Thanks.
First of all,
As nonce is supposed to be random is not, strictly speaking, true. Nonce in general is only required to be unique.
It is, however, often convenient to generate nonce as (pseudo-)random bytes. In this case and if the nonce is sufficiently big (say, 12+ bytes) there is no need to check against previous nonces as you will never encounter a repeat in your life.
You can store nonces in any way you want, e.g. in a database; also note that you don't need to store past nonces longer than their validity time. In fact, a nonce should be timestamped, and valid only during a limited time since its creation. For this, all systems (nonce producer, client, and server) need to be time synchronized.