Subject: Re: backup manifests
To: Robert Haas <robertmhaas@gmail.com>,
 "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
References: 
 <CA+TgmoZV8dw1H2bzZ9xkKwdrk8+XYa+DC9H=F7heO2zna5T6qg@mail.gmail.com>
From: David Steele <david@pgmasters.net>
Openpgp: preference=signencrypt
Autocrypt: addr=david@pgmasters.net; prefer-encrypt=mutual; keydata=
 mQINBFSheh0BEADGNb3c1kOaX5OGUDhqHTwJ3JW7XAllfWLdknpRg+/fihgLPPRnQHZhjq28
 nmMLqM+C8TjezT2BgVACeu8qqASnuzN/E5+bAl9hVcgCP4eV/lEIWwVxmhcHqSdeWqWZSBRB
 tf07fLBnz22+3LwVsESN+fanWxnoqqvE0+hyGnCEDhOBkihgbYHuq4vw1+xgoGN1uDk4NShV
 El0ZWO90P4e5mOWA2Zsex+8YhGJlfRwMpU69okFCvjpWJKE+ufeJdlrxEpSSKW7SQ0kG1VF7
 CvDKpF70TCWkb4Bagb6c7lwZrMjxuBnlIvOlV3RRY67PAaVIFRRvQJeJABOPHp8HnH8cwici
 7gwwfWBrZZeAdPqs6VNjANqI9uaDasRnD3yHP6CcHIAeCl5hYnzNTkIqBRlnmD5y8s0VRDLr
 6JR3FxscOsvwXPJ+He1RpRlxQDlBboaRFUz8endeQHhGUeHyekQcSYUaz4PX3OJBG0Xi7nr8
 EOP6zOeP61z3dL8NuO3QjgPiygvS0qwMEPvOYo52nEGYn08nvFVajI8yxOXFnIwnmpgr5gdq
 nL9ga72tvSyJQAUx+YB7r1bKjRn/Mlt/fPIS5PXONofiO1K8uX+pzvIX6dnm7ihpFf1XC+uG
 5+DKBnU7yS7jCRL52GxWHbuC3mT4tvzqH2b13TLng1Y7Izi+hwARAQABtCJEYXZpZCBTdGVl
 bGUgPGRhdmlkQHBnbWFzdGVycy5uZXQ+iQI5BBMBCAAjAhsDAh4BAheABQsJCAcDBRUKCQgL
 BBYCAwEFAlShuEECGQEACgkQn830JKJznPPsLhAAtKkIu0mFfxcVqApg4PNjZKYY4TWeN+I+
 go/VKX8QWMadr33t8Sxcgyn48bjBYzgWQXhF4rMcFxDxI3ly5bdE8QKZkhFJJT7N2fBoo9Zm
 ZOsOvPd+5hz07VZpgNSiTXMAphj8+GSTLbYufm/OUnfpS1eovPtPdYPQpNC3RVHA0gtisz26
 NgMLg6QN0iQuITs9N+wiaGtyVIornl4XAY2dM/Hvfr1aDFkukNNr52sc/mGqocG/dKC7dONA
 3860y2MLszQcbAE45iEkmwpGkvxyc3i3tvdD3VNlVI1MKJUBnxFPUEI0lVq5WpApFSIU31+j
 aNunKIcfVxRnM8FTJBsw3RnFRpSsEtiLaZRm5sOZHa9+dy/DWDb+8O1I+momCo88+Jksd6pZ
 2Tz9msOiJiTnFsCZgfbbmayH6w8ZyfHuO0DuxScM1UK+6CLC2VVjQFuH6WHqJpaENg5INswS
 qpUc05iC4i+6dZOe44cviX6LpHuP8vWM0E63CMun0l42yHWy+k6nLvx/fj7t++tF2JIJ92OG
 n/2MkM5lIKknRg27UjYAspD6f3NSZUMIe6tGyWPTtLOu8zOL5CeRyCHMWwUVDKJSBzlK2mV8
 e0EbmtUJFsoNWXWKPKUIxX7JXPN3v523HmOhtyz5SnkGtwEqCZiv/JccYmh+S2IokAuscLNP
 EJq5Ag0EVKF6HQEQALPpUsP67xfcj6NUMyySXSytUzMIVi5XNTyazuNcVfFZzT9QL8wFQkgy
 i/HOD3tmvdGxz6H8V+v+cszp88gCd8TwClss7u+iPsLlAQQWC4q0WiX4OhwFv2H004iuft8i
 odjiWDkYEgIFxlPNxQfHFmchkyODIJXQmnzbgsXwGZtJzAxEVh6AgYJqE/Ev/+kTJhJ7703n
 oIb+PXvafoB5axnU4nf7DuFa9X+q2/ZfzyAXUCKvzDvxb24iUgWFzlWBx0CnI21Kh6aS6hR6
 o00D2OBiU+yCpW9eRTi3SuDuslmtCUaZz5V4SHo37ochEYfZ2LYOPsBO3PUMx8T7MDYrmv/x
 4W5rdjugz4NXWROStNNLpS74LW20rdrEKMDltph7U2zfjjS663K+CUxoXn/ha2WnzBocoY5o
 KwdViLln4s0ivOTa4clHJJUsYiAxLShAe2AP+5kJim24tAabbEOsrRTn9RpT7J8jVT/G0YDE
 glujEt0U04Akkj5NO4G7vJP/AyX5zKZetkp/HFiFBZMkUuXD/KgDc5EM2fpQtaxGGY2fcQqY
 VHUbbxstxyl5d349M9rok7O90hw9BkP0Q8UEpgmlZ6ftwx+ZfZmBEdQ7HcMHnSPSNJkXt/Vi
 ozlcrSnkVXzCXvH9DHrIpgenp8btsJ2XyjSdrEu4jAqYeirW+3qRABEBAAGJAh8EGAEIAAkF
 AlSheh0CGwwACgkQn830JKJznPNmERAApYaQK6i9F6hM2RUD/PqQC45WmzOXK9bDSS9hdk4p
 Nc5jSW2+FkcMFe1XFG2NyGf1v5KBPxuDTQp35PIwRsL59xNmPICu0ae6zmCPUpxbMIEzb/VU
 wXqeuNp3cRVll06goDt5w+2LlAtBrxuDjiWxby9LH+vsIUMLWYu+M50pdtOcXOsO1+zyfs3w
 U6xRZ3PaFDKO1cB68okDFG/cFHnYfY5aETV7LgVBHEOQLwL01U01QC/iqY/aNO4iUH/+PBc0
 R6mYlP7IqDQOQVTJ0dXP365thl0Q7c9e2JQSS9wuSv2EEiR//nnZREtLyrQNLwsXE8UFBDe7
 uA8Lm2ldmQYpHHKAcorGVTHYJaaus2LjH8tZ1i4RGg4hKMJSHil/5C+Ghl+PmcACVeGaxB0c
 mJ8+0jyWDkLCDMAXJJyvXRWIONTAxVt5kKg1/iMAq1IQYNd66agnmgxdSvKLPUo0JJ5fhQJp
 2bqDDTrINTZg+Rub2HeoOMxYJsMypK+6aY4iVlm2Z7A9SgyQDjGAXzD9+XaezNFeXxfPbjo6
 46qA9SycdYhiwaTcTQakiLkZWRIkSjGQwNCK9NktE1fYnXfR0+WaWFduQ4BfM5uta1bt8esB
 /mLEjVYS9RRAWZ/untJrR9JYGTC4Mu6tcLGZD7385yX3TNM1iaIUGxlKkHHCZCnILyq5Ag0E
 VKGipwEQALe8Af9Kgql5rC6NPrOeuOuuqwXMNIwKsTLG8PmmoHKEHKukYuX/YfnGWFU1Ir6t
 y0qXe2XZs8AnLNI753b/7Z7ftMuMWzWqzfU8Pb+8/NrOQqfO05++gtsczY/tflVW2YWJWDZ4
 lhytY4frlOSRuMOI4TjM3NwgkVri4sM4U+OdM8tdkW9IdajLCP0J+wFO+U2dU9b3yCss0GNY
 c0dlbmI6sOmpV70ldAb8i0BqfkGpq3xDcnzf4EQDdF/mBLZwBe0v6dzlxHh2HqL9yztjGXnk
 NtRFYGzKw+ZBuOaSj+OPG7iaBSgeNxDYjww2KTzdSE3DbfGqwrxn/ejD+ZueNcqxsoaT3oNr
 ADeluXmN63C1CcdFmJjAiCCjt3diLgmVL3MyBV+LcSwEz+2B/tlRHV1FWvy8VX1Nj2CwCO9u
 RuJ9HrF05TXjjNC2o6fFME/TkEzsklzvLxP/Bs/wKDvZQKGlzshk8EsmRhnJjzekOg4gOyVM
 LvjbGiBPMh309i0nVgExz0LIvI5Wp8G1YXHiuf6i52pTgeiGfiV6D12b69ABqInOfvROSvfe
 F36OLmoRicJcd8wEwkNPoSHHn/Zxf0fMHe7ZV7EtNSeqB+179SxDqeIEAOhpye6/q57LqvpZ
 qm0ADa5O3J6IMpId+ov0el553e7HxfDmaWJpm+NemLWvABEBAAGJBD4EGAEIAAkFAlShoqcC
 GwICKQkQn830JKJznPPBXSAEGQEIAAYFAlShoqcACgkQgDa4glDlIUCXfQ//aozIciE9Je5m
 kUlKECjXut8vvpO9fbAbxY5VIEWANV2PpIw1LO/8WVstCl38vBZtOxCcZqccLge12Ow72WPF
 5G+v+8OJRwHNjrdI/WvFeMUfqlWB2ok+OOlm9t4U0lTK7YX4K6PvjXiMh1Kpvx/JsxrnGJJx
 X+Ky4icNWdiyaVBs+NDROasZXmy+7S8yeR9ECPxu/DPziC+aPW5lJ3tGqFEPADpmeD8G5K7U
 QyDJ4GRgD+Agez8r60qyhiwFyUXfcn0bOsIx/og4gae8GnadPl1+93+PI0L8Xb+oYcJnvVGE
 zJZJIMsp1Zjhi3PnJEulvDNOxkY7Og2dEwkNSHrru3Z5odl8s629VaYyT1b0Q/GnDAnKtZc3
 tKZVKCvvAf9UmbuBfbuP084dBFeMeFWl3ET9UWpGhKm22KXg8TrMKoM62bUSjW5gIxC8ywLT
 mu7ivcKbxj0rXFB5AdYUff9QsCZFdDZG3fUymOQmYgNhwXAAIwKDKD8CINc2CIVc0qMhh3Hy
 WyyA8JZKw/iK+652WHoKEMmxVunSvvlDIMDf/bYN/HxoUEBcCSWsISKW6xGu1hPKfYK2t6/9
 CVjluTOPeFiBt1ELXsOlpRPe4f0M2Cc/AEFukE1ZoJWlUhtU4zuOpvDtGST9D9imYsgMaMa8
 TtEGFWGDmOfws4yU4tTTUNqFRRAArysPyXEhNNbLncfR5lPGPfZORPqLmIdkNMcDAwmzvC80
 g1WH46wPzIcUUTc7DnP0pZNWGmI2NAnAW/c4Ii3aiXQXZDNVRfdZKL5rEY6dtgxdHl4hc6KN
 KH17wsX4T3dglMqP7VikYT23sNQJVE1oIGjfVR1sOe+DleI5Awa50DgGyLZS9vLfZz/9F28J
 2YM1DExVPxbj75bwfOl65hh8B5BCqqrYp5n/JqV2x5+OSPgCHmd7rJtTbTl89MVKc0uR79ZZ
 hxUBU6m5v2UGHakSlgdbh+qmr6rdFkqRxRFhdepD7u9qvPKHdVIPp23dqkx9r7gIe+RjfkT6
 aq12wQhqgGYaae5bqlg0ls1CpfZxsxJmwmO/DJ2W1hdrPhs/7ml9rv552FBQuQ7i9rddeSju
 lkFsXVWOsbLf45pKAWTwqZihb3nSIoBv53EH0V+1SPzDbgQk2CaQ+DR6k7eujgsI/srPpMtl
 ehqEQ7kzaKFACBgXBOxkheDR/kJzVJxx0a1rIFnvJGL/h5lgo8onxP5scCpotNx/bJjLkBVk
 XQvKDUIu9YPy0yENT58C91WWX/Nac3B5W5ZkmWHh6Lh+5eOiRSLV9MDau6ziULNNpuIA90iY
 1onr0xRNO2DMyn0NzZzL+Y59WlMyATUcQdTgtmlmTcaxWeRiBRlUBLvHvgHLV94=
Message-ID: <4b6244ea-4094-9055-080b-7afb274bf270@pgmasters.net>
Date: Wed, 18 Sep 2019 21:11:36 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:60.0)
 Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: 
 <CA+TgmoZV8dw1H2bzZ9xkKwdrk8+XYa+DC9H=F7heO2zna5T6qg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

Hi Robert,

On 9/18/19 1:48 PM, Robert Haas wrote:
> That whole approach might still be dead on
> arrival if it's possible to add new blocks with old LSNs to existing
> files,[7] but there seems to be room to hope that there are no such
> cases.[8]

I sure hope there are no such cases, but we should be open to the idea
just in case.

> So, let's suppose we invent a backup manifest. What should it contain?
> I imagine that it would consist of a list of files, and the lengths of
> those files, and a checksum for each file. 

These are essential.

Also consider adding the timestamp.  You have justifiable concerns about
using timestamps for deltas and I get that.  However, there are a number
of methods that can be employed to make it *much* safer.  I won't go
into that here since it is an entire thread in itself.  Suffice to say
we can detect many anomalies in the timestamps and require a checksum
backup when we see them.  I'm really interested in scanning the WAL for
changed files but that method is very complex and getting it right might
be harder than ensuring FS checksums are reliable.  Still worth trying,
though, since the benefits are enormous.  We are planning to use
timestamp + size + wal data to do incrementals if we get there.

Consider adding a reference to each file that specifies where the file
can be found in if it is not in this backup.  As I understand the
pg_basebackup proposal, it would only be implementing differential
backups, i.e. an incremental that is *only* based on the last full
backup.  So, the reference can be inferred in this case.  However, if
the user selects the wrong full backup on restore, and we have labeled
each backup, then a differential restore with references against the
wrong full backup would result in a hard error rather than corruption.

> I think you should have a
> choice of what kind of checksums to use, because algorithms that used
> to seem like good choices (e.g. MD5) no longer do; this trend can
> probably be expected to continue. Even if we initially support only
> one kind of checksum -- presumably SHA-something since we have code
> for that already for SCRAM -- I think that it would also be a good
> idea to allow for future changes. And maybe it's best to just allow a
> choice of SHA-224, SHA-256, SHA-384, and SHA-512 right out of the
> gate, so that we can avoid bikeshedding over which one is secure
> enough. I guess we'll still have to argue about the default. 

Based on my original calculations (which sadly I don't have anymore),
the combination of SHA1, size, and file name is *extremely* unlikely to
generate a collision.  As in, unlikely to happen before the end of the
universe kind of unlikely.  Though, I guess it depends on your
expectations for the lifetime of the universe.

These checksums don't have to be cryptographically secure, in the sense
that you could infer the plaintext from the checksum.  They just need to
have a suitably low collision rate.  These days I would choose something
with more bits because the computation time is similar, though the
larger size requires more storage.

> I also
> think that it should be possible to build a manifest with no
> checksums, so that one need not pay the overhead of computing
> checksums if one does not wish. 

Our benchmarks have indicated that checksums only account for about 1%
of total cpu time when gzip -6 compression is used.  Without compression
the percentage may be higher of course, but in that case we find network
latency is the primary bottleneck.

For S3 backups we do a SHA1 hash for our manifest, a SHA256 hash for
authv4 and a good-old-fashioned MD5 checksum for each upload part.  This
is barely noticeable when compression is enabled.

> Of course, such a manifest is of much
> less utility for checking backup integrity, but you can still check
> that you've got the right files, which is noticeably better than
> nothing.  

Absolutely -- and yet.  There was a time when we made checksums optional
but eventually gave up on that once we profiled and realized how low the
cost was vs. the benefit.

> The manifest should probably also contain a checksum of its
> own contents so that the integrity of the manifest itself can be
> verified. 

This is a good idea.  Amazingly we've never seen a manifest checksum
error in the field but it's only a matter of time.

And maybe a few other bits of metadata, but I'm not sure
> exactly what.  Ideas?

A backup label for sure.  You can also use this as the directory/tar
name to save the user coming up with one.  We use YYYYMMDDHH24MMSSF for
full backups and YYYYMMDDHH24MMSSF_YYYYMMDDHH24MMSS(D|I) for
incrementals and have logic to prevent two backups from having the same
label.  This is unlikely outside of testing but still a good idea.

Knowing the start/stop time of the backup is useful in all kinds of
ways, especially monitoring and time-targeted PITR.  Start/stop LSN is
also good.  I know this is also in backup_label but having it all in one
place is nice.

We include the version/sysid of the cluster to avoid mixups.  It's a
great extra check on top of references to be sure everything is kosher.

A manifest version is good in case we change the format later.  I'd
recommend JSON for the format since it is so ubiquitous and easily
handles escaping which can be gotchas in a home-grown format.  We
currently have a format that is a combination of Windows INI and JSON
(for human-readability in theory) and we have become painfully aware of
escaping issues.  Really, why would you drop files with '=' in their
name in PGDATA?  And yet it happens.

> Once we invent the concept of a backup manifest, what do we need to do
> with them? I think we'd want three things initially:
> 
> (1) When taking a backup, have the option (perhaps enabled by default)
> to include a backup manifest.

Manifests are cheap to builds so I wouldn't make it an option.

> (2) Given an existing backup that has not got a manifest, construct one.

Might be too late to be trusted and we'd have to write extra code for
it.  I'd leave this for a project down the road, if at all.

> (3) Cross-check a manifest against a backup and complain about extra
> files, missing files, size differences, or checksum mismatches.

Verification is the best part of the manifest.  Plus, you can do
verification pretty cheaply on restore.  We also restore pg_control last
so clusters that have a restore error won't start.

> One thing I'm not quite sure about is where to store the backup
> manifest. If you take a base backup in tar format, you get base.tar,
> pg_wal.tar (unless -Xnone), and an additional tar file per tablespace.
> Does the backup manifest go into base.tar? Get written into a separate
> file outside of any tar archive? Something else? And what about a
> plain-format backup? I suppose then we should just write the manifest
> into the top level of the main data directory, but perhaps someone has
> another idea.

We do:

[backup_label]/
    backup.manifest
    pg_data/
    pg_tblspc/

In general, having the manifest easily accessible is ideal.

Regards,
-- 
-David
david@pgmasters.net