Encode the data into DNA and enter it into as much biology as possible. Incorporate it into viruses, bacteria, plants, algae to animals. Make sure the record will be there hopefully as long as any earth life exists. Do not rely on a static single structure which can so easily be destroyed.
That's actually a really interesting question, because we can anticipate the types of mutations that occur: single base errors (mutations/insertions/deletions), displacement, mirror and dislocation (strings cut, reinserted, flipped, etc., within and between chromosomes), and also duplication and deletion of such. This is somewhat different from the usual kinds of errors we have to protect against (e.g. random or burst noise, temporal smearing of signals), but may already exist in practice (does anyone do this for dealing with out-of-order e.g. TCP packets?), and if not, I'm willing to bet suitable codes have been at least studied.
Downside, they're rather opaque to the casual observer, it's not like you can genetically imprint a barcode on the phenotype's skin. Not yet at least.
https://www.abc.net.au/news/science/2021-12-06/climate-change-earth-black-box-recorder/100621778
Recording data onto digital media has a relatively very short life expectancy. The electronics will fail through wear-out within 50 years at best... no more recording. We cannot make the storage impenetrable (who is going to replace batteries?). There will need to be a door but we cannot let vandals break in and destroy the place either.
I don't know about active recording like they're on about in the article; and that's easily excused as a gimmick. They talk big, but they really only have to last long enough to get the thing built and shipped, and then like so many art and humanitarian projects, it can be safely forgotten in the wilderness, until it ceases to function as no reliability engineering went into its design or siting, nor are any locals skilled in, nor tasked with, its maintenance. (Take examples like water wells:
https://www.theguardian.com/society/katineblog/2009/mar/26/water-projects-wasted-moneysome may be poorly constructed (as in the article), some may run dry from overuse (see also: "induced demand"), or bring up toxins (like arsenic), or even just the freaking pump breaks and no one has the tools, equipment or knowledge to fix it.)
But as for persistent digital storage, there are media known. Some of my code is even on it:
https://en.wikipedia.org/wiki/Arctic_World_ArchiveThey just use ordinary optical film, surprisingly enough. The cool and stable environment will be a strong factor in that, I'm guessing. And it could always be copied onto something more robust, like Idunno, etched nickel strip, or etched/engraved glass plate, etc. There's something to be said for the classic Golden Record as well.
Noteworthy that there's a fundamental conflict between density and readability; you can have low density e.g. text that's readable by the unaided eye (if perhaps requiring a sharp pair), or by mild magnification (one lens), strong magnification (several lenses, a microscope), or technological means (scanning with lasers, EBM, holograms..). And if this is something that might be exposed to people, it also needs to be unremarkable enough that they don't try and steal them, or break off a chunk as jewelry, or... Which is particularly a downside of the iridescent pattern of diffraction-limited density (like CDs).
Still another factor for storage is erosion. Burying a vault in continental shield rock, has a reasonable chance of success. Very geologically quiet, it's mostly vulnerable to erosion. And the rate of erosion is predictable over the last some millions of years at least. I mean, basically the worst we can hope for is we've triggered a particularly nasty interglacial, raising temperatures, melting permafrost, increasing rains and erosion; and later, plunging into an even deeper glacial period. Or something like that. Both of which cause significant erosion, and so we would want to place it deep enough, and in a low-lying place to begin with, that it won't be exposed in at least a little while. Say 100kya by the next interglacial or two. (Also relevant to nuclear storage; which, especially if ground-visible landmarks should survive, a highly reliably deserted region would be preferred. Wind erosion would have to be countered by very hard materials (not even granite, but perhaps massive carbide obelisks or something?) as well as windbreak structures, or siting in a natural canyon/cliff. Minding that, a canyon or cliff only exists in the first place because of erosion, so it's not a great starting point.)
Tim