Daniil Zakhlystov

usernamedt

My GSoC with PostgreSQL: even faster and safer backup restoration in WAL-G

Daniil ZakhlystovUncategorized

This summer I participated in Google Summer of Code 2020 at PostgreSQL Global Development Group. During these 3 months, I was working on performance and safety features for WAL-G utility. I went through this summer journey together with my mentors Georgy Rylov and Andrey Borodin. In this post, I will mainly focus on the work done during the program.

WAL-G is a tool written in Go for backing up and restoring PostgreSQL clusters (most recently MySQL, MongoDB, and FoundationDB too). It supports Amazon S3 storages (and S3 compatible analogs, like Yandex Object Storage), as well as Google Cloud Storage, Azure Storage, Swift Object Storage, and the file system.

In its core functionality, WAL-G is a successor of WAL-E but written in Go. WAL-G works much faster than WAL-E and also has some new cool features, one of them is delta-backups. Delta-backup, whenever possible, stores only pages, changed since the previous backup. When a full recovery is needed, the restoration process would need the last base backup plus all of the delta backups until the point of restoration.

The goal of the project was to make two enhancements:

The first one was to improve the performance of the backup fetch process by implementing delta-backups unpacking in reverse order to avoid rewriting the same pages along with the following backup structure reorganization to avoid downloading unnecessary files.

The second was to provide users with the features to verify backup consistency, such as WAL’s history consistency check and page checksum verification.

These two enhancements were implemented as four features:

All of the four features by now are merged into WAL-G master branch. You can try them by cloning the WAL-G repo.

Unpacking delta backups in reverse order

When restoring from delta backup, WAL-G at first unpacks the oldest version of the page files from base backup and then applies delta backups to the base version in historical order:

WAL-G default backups unpack order

The problem is that there are page blocks in the older backup which are going to be completely overwritten by their version from the newer backup, thus resulting in unnecessary writes to disk. The main goal of this feature was to improve backup fetch performance by implementing an unpack of delta backups in reverse order:

Reverse backups unpack order

With this approach, pages are written to the disk only once, which noticeably improves backup restore performance. The main idea was to create page files from the latest delta backup at first, then fill the missing information from the following delta backups and the base backup.

The following text describes how WAL-G creates the page file without unnecessary page overwrites. It will focus on the most non-trivial case when the page file was modified multiple times since the first appearance in the base backup. Other more trivial cases are omitted for briefness. The page file is restored using the following scheme:

  1. Create page file from delta
  2. Fill the missing information by applying the previous delta
  3. …
  4. Fill the missing information by applying the first delta
  5. Fill the missing information by applying the base backup

Create page file from delta

WAL-G increment file header

WAL-G uses the information from the header of the delta page file to extract the final size of the page file. Knowing the final size of the page file and the PostgreSQL page size, it is possible to calculate the page count needed to write on the disk. For each page WAL-G performs the following algorithm to write the pagefile:

  1. If this page exists in delta backup, write it to the page file
  2. If this page does not exist in the delta, write an empty page block to the page file
Structure of the created page file

Apply the N-th delta to the page file

For each next delta, WAL-G needs to write only the missing information to the page files. For each page in N-th delta backup WAL-G does the following:

  1. If there is already some version of this page on the disk, then it is the latest and we can ignore the page from delta
  2. If this page doesn’t exist on the disk (empty block in a page file) then WAL-G writes it
Application of N-th delta to file on the disk

Apply the base backup to the page file

After WAL-G reached the base backup, it needs to get the missing pages from the base backup page file version. For each page in the local page file WAL-G does the following:

  1. If there is already some version of this page on the disk, then it is the latest and we can ignore the base backup page
  2. If this page doesn’t exist on the disk (empty block in a page file) then WAL-G writes it
Application of base backup to file on the disk

I’ve implemented the proposed approach and measured performance improvement. WAL-G with reverse delta unpack turned on demonstrated about 2.5x faster backup restore compared to the standard WAL-G. If you are interested in more details, take a look at the complete benchmark report.

Comparison of disk usage between standard delta unpack and reverse delta unpack

Usage

To use the reverse delta unpack, do one of the following:

  • set the WALG_USE_REVERSE_UNPACK environment variable
  • add the --reverse-unpack flag:
wal-g backup-fetch /path LATEST --reverse-unpack

Corresponding pull requests

Reorganization of backup structure

After the implementation of the reverse delta unpack feature disk load and overall performance during backup-fetch has been greatly reduced. Nevertheless, WAL-G still needed to download absolutely all backup files from the cloud. However, with the reverse delta unpack feature implemented it wasn’t longer necessary – for example, there may have been a situation when WAL-G already had a consistent local version (no missing page blocks) of each file in the archive that was going to be downloaded. In this case, the archive contained only outdated files that aren’t useful anyway, so WAL-G can skip the download of the entire archive and proceed to the next one. The goal was to avoid downloading these unnecessary archives from the cloud and improve the WAL-G backup fetch performance even more 🙂

WAL-G stores each backup in the cloud split into several compressed archives. The problem is that to check which files exist in the archive you need to download and decompress it from the storage. The main idea is quite simple – store the contents of each archive in a backup JSON sentinel file so WAL-G can skip the archives without interesting files without downloading them.

{ // this is a sample backup sentinel JSON file 
  "PgVersion": 120002,
  "UncompressedSize": 500781396,
  "CompressedSize": 100243768,
  "LSN": 17448304680,
  "DeltaCount": 8,
  "DeltaFromLSN": 16743661608,
  "SystemIdentifier": 6847498813832237599,
  "DeltaFullName": "base_00000003000000030000002F",
  "TarFileSets": { // new field to store information of contents of each tar archive here
    "part_001.tar.lz4": [
      "/",
      "/base",
      "/base/1",
      "/base/13689",
      "/base/13690",
      "/base/16384",
      "/base/16384/1259",
      "/base/16384/16397",
...
    ],
    "part_003.tar.lz4": [
      "tablespace_map",
      "backup_label"
    ]
  },
  "Files": {...},
  "DeltaFrom": "base_0000000300000003000000E6_D_0000000300000003000000D6",
  "FinishLSN": 17448304952,
  "Spec": null
}

We’ve successfully implemented this approach and now WAL-G stores the contents of each backup archive in backup sentinel JSON by default. However, with this approach, the case when all of the files in the archive can be skipped may be quite rare. For a file that is being updated frequently, there is a high chance that some delta backup will contain only outdated information about it that WAL-G won’t need. And vice versa, if some file is being updated rarely, there is a high chance that delta backup will still hold some required data so we can’t skip the archive containing this file and we need to download the entire archive.

That’s why we developed an additional backup creation mode (rating composer) based on file update ratings. The idea was to place the files with a similar update frequency in the same archives so we can get the higher chance of the entire archive to be skipped. WAL-G needed to somehow determine the update frequency for each file in the database cluster folder. Luckily, for paged files, there is information from Postgres statistics collector – particularly n_tup_ins, n_tup_del, n_tup_upd columns from pg_stat_all_tables view.

In the rating composer mode, during backup creation, for each file WAL-G calculates the updates count using the data from pg_stat_all_tables and stores it in the current backup sentinel JSON. If available, WAL-G also reads the previousUpdatesCount – previous updates count value from the previous backup sentinel JSON. Using these values WAL-G then calculates the updateRating for each file: (currentUpdatesCount * 100) / previousUpdatesCount. Finally, all that left to do is:

  1. Sort all the files in the current backup by their updateRating
  2. Start packing files into archive from the file with the highest update rating
  3. When the size of the files packed in the current archive exceeds the WALG_TAR_SIZE_THRESHOLD limit, create the new archive, and go to step 2.

Ok, seems like we’re done… But actually no. To speed up things a little bit, WAL-G can do concurrent packing of multiple tar archives during backup creation (WALG_UPLOAD_DISK_CONCURRENCY setting). If you look closely, the above algorithm can’t be parallelized in straightforward way. In order to parallelize it, we need to split the files into archives before starting to pack them so we can pack each tarball in separate goroutine.

To split the files into archives properly we need to know the size of each file that is going to be written to the archive. For regular files, WAL-G reads the file size from the file system. For increment files, WAL-G calculates the expected size of increment.

WAL-G with the described backup creation and fetch logic downloaded 16,5% less data from the S3 storage compared to the standard WAL-G with almost no loss in backup push performance. This number may actually vary a lot because it depends on the multiple factors: how often the database is updated, how frequently delta and base backups are being created, etc. For anyone interested, here is the complete benchmark log.

Usage

Since this feature involves both backup creation and restore process, in order to fully enable it you need to do two things:

(Optional, but recommended. Be aware that although rating composer allows saving more data, it may result in slower backup creation compared to the default tarball composer) Enable rating tarball composer during backup creation so the files with a similar update rating will be placed in the same archives. Do one of the following:

  • set the WALG_USE_RATING_COMPOSER environment variable
  • add the --rating-composer flag:
wal-g backup-push /path --rating-composer

Enable redundant backup archives skipping during backup-fetch. Do one of the following:

  • set the WALG_SKIP_REDUNDANT_TARS and WALG_USE_REVERSE_UNPACK environment variables
  • add the --skip-redundant-tars and --reverse-unpack flags:
wal-g backup-fetch /path LATEST --reverse-unpack --skip-redundant-tars

Corresponding pull requests

WAL’s history consistency check

PostgreSQL manages PITR by maintaining a write-ahead log (WAL), which can be “replayed” from a redo point to a stopping point in the event of a database crash. The goal was to implement a feature which can ensure that WAL-G can provide PITR (point in time recovery) for the backup.

We’ve decided to split this feature into two commands: wal-verify and wal-show. Both of them are being used to inspect the WAL storage folder, but have different use cases.

wal-show

wal-show outputs information about the WAL storage folder. It shows all WAL segment timelines available in storage, displays the available backups for them, and checks them for missing segments. The main idea is simple – command scans the entire WAL storage folder and detects available WAL segments timelines. Then, for each timeline, WAL-G detects the maximal (END_SEGMENT) and minimal (START_SEGMENT) segments in storage. Then WAL-G verifies the segment range [START_SEGMENT, END_SEGMENT] for integrity:

  • If there are no gaps (missing segments) in the range, final status is OK
  • If there are some missing segments found, final status is LOST_SEGMENTS

This command is inspired by the show command of pg_probackup utility 🙂

Usage

The usage is simple, make sure that you have storage environment variables configured and run:

wal-g wal-show

By default, it also shows available backups for each timeline (can be turned off with --without-backups flag).

Default output of wal-show

User also can request a detailed JSON with --detailed-json flag:

[
   {
      "id":1,
      "parent_id":0,
      "switch_point_lsn":0,
      "start_segment":"000000010000000000000078",
      "end_segment":"00000001000000010000000B",
      "segments_count":80,
      "missing_segments":[
         "000000010000000100000007",
         "000000010000000100000006",
         ...
         "0000000100000000000000B3"
      ],
      "backups":[
         {
            "backup_name":"base_000000010000000100000009",
            "time":"2020-07-26T18:36:36.757Z",
            "wal_file_name":"000000010000000100000009",
            "start_time":"2020-07-26T18:30:59.892342Z",
            "finish_time":"2020-07-26T18:36:31.852791Z",
            "date_fmt":"%Y-%m-%dT%H:%M:%S.%fZ",
            "hostname":"MacBook-Pro-danius.local",
            "data_dir":"/Users/danius/walg_experiments/postgresdb",
            "pg_version":120002,
            "start_lsn":4445962336,
            "finish_lsn":4462739536,
            "is_permanent":false,
            "system_identifier":6847498813832237599,
            "uncompressed_size":834620740,
            "compressed_size":160905595
         }
      ],
      "segment_range_size":148,
      "status":"LOST_SEGMENTS"
   },
   ...,
]

wal-verify

Although wal-show can show us information about segments in the WAL storage folder, we still can’t say for sure if there is a consistent WAL segment history for the cluster. We want to ensure that WAL-G can perform a PITR for the backup. The improvement we can make is to verify that WAL-G has all the necessary WAL segments in storage up to the current cluster LSN.

wal-verify designed to help us to do this verification. After launching wal-verify, WAL-G does the following:

  1. Connect to the Postgres cluster and fetch the current cluster segment number and timeline.
  2. Walk the WAL segments history starting from the current cluster segment number in reversed chronological order and find missing segments.

Reverse chronological order was chosen for a smooth timeline follow – by using records in timeline .history files WAL-G can follow timeline changes correctly and easily. On each walked segment, WAL-G checks if there is a record with the current segment number in the timeline history file. If the record exists, WAL-G switches timeline to the parent timeline specified in this record.

WAL segments can be missing from WAL storage folder because of multiple reasons, so let’s do some classification. On the picture below missing segments are marked red, found are marked green. You can see that there are different causes of why the segment may not exist in WAL storage.

Different types of missing segments

I’ve made four statuses for WAL segments:

  • FOUND segments, obviously, are present in WAL storage
  • MISSING_DELAYED segments are not present in WAL storage, but probably Postgres did not try to archive them via archive_command yet
  • MISSING_UPLOADING segments are the segments which are not present in WAL storage, but looks like that they are in the process of uploading to storage
  • MISSING_LOST segments are the segments which are not present in WAL storage and not MISSING_UPLOADING nor MISSING_DELAYED

Output of wal-verify is the report which consists of two parts:

  1. WAL storage status, calculated with the following logic:
    -If there are no missing segments, then OK
    -If there are some missing segments, but they are not MISSING_LOST, then WARNING
    -If there are some MISSING_LOST segments, then it is a FAILURE
  2. A list that shows WAL segments in chronological order grouped by Timeline and Status (FOUND/MISSING_DELAYED/MISSING_UPLOADING/MISSING_LOST).

Usage

The usage is simple, make sure that you have storage and Postgres cluster environment variables configured and run:

wal-g wal-verify

I’ve included sample outputs of wal-verify command below. You can also enable JSON output via --json flag.

Sample wal-verify outputs

Corresponding pull requests

Page checksum verification

The goal of this feature was to make WAL-G support backup verification via page checksum verification. Starting from PostgreSQL v9.3, each page contains a pd_checksum in its header to verify any data corruption so it can be used to verify WAL-G backups.

PostgreSQL uses the modified version of the FNV-1a hash (FNV is shorthand for Fowler/Noll/Vo) as the checksum algorithm. I’ve adapted this algorithm in Go from PostgreSQL source code (written in C). Also, I’ve also partially borrowed the logic of is_page_corrupted() function from Google’s pg_page_verification tool.

The page verification feature operates on the backup creation stage. If found any, corrupted block numbers (by default, no more than 10 of them) will be recorded to the backup sentinel JSON file.

Usage

Users can enable the page verification using --verify flag or by setting WALG_VERIFY_PAGE_CHECKSUMS environment variable:

wal-g backup-push /path --verify

WAL-G show the warning if found any corrupt blocks during backup-push:

Example of corrupt block warning

Also, WAL-G saves the corrupt block numbers in the backup sentinel JSON file.

 "/base/16384/16397": {
      "CorruptBlocks": {
        "SomeCorruptBlocks": [
          1
        ],
        "CorruptBlocksCount": 1
      },
      "IsIncremented": false,
      "IsSkipped": false,
      "MTime": "2020-08-27T14:31:06.483880188+05:00"
    },

By default, no more than 10 corrupt block numbers are written per page file. To write all corrupt block numbers, add the --store-all-corrupt flag or set the WALG_STORE_ALL_CORRUPT_BLOCKS environment variable.

Corresponding pull requests

Final note

I want to thank my mentors Andrey and Georgy. I’ve not only become more fluent in Golang but also learned a lot about PostgreSQL internal structure. I’ve enjoyed these couple of months of GSoC, I hope that you did too! I think that we’ve made WAL-G a little bit cooler 🙂 . I hope that the features that we’ve done will be useful and will benefit the end users. Thank you, guys!

© 2020 Daniil Zakhlystov

Sliding Sidebar