Trash and restore for a note-taking app

Your note-taking app has 300,000 users and about 40 million notes, kept in notebooks. When someone deletes a note or a whole notebook, it goes to a trash instead of vanishing. From the trash they can restore it for 30 days. After 30 days it must be erased from the database, as the privacy policy promises.

A notebook can hold up to 5,000 notes, and restoring a notebook brings its notes back with it. The note list, search and note counts never show trashed items. Users delete about 60,000 notes a day, plus a few hundred whole notebooks.

How do you mark a deleted item, and how do restore and the final purge work?