Block Reference Table | Phase-1
This post is part of a series detailing my GSoC contributions to PostgreSQL, where I worked on implementing a native incremental backup solution for PostgreSQL versions 13 through 16 in pgmoneta. You can read my proposal and follow the discussions and share your thoughts here
0. Context
A key objective of an incremental backup solution is to identify all the content that has changed since the last base backup, particularly pinpointing which specific blocks have been modified.
A naive approach to this problem involves scanning each relation file in the database cluster, comparing it block-by-block with its counterpart from the base backup, and identifying any modified blocks. Sounds simple enough! However, this approach becomes highly inefficient when dealing with files that are several petabytes in size (quite possible in database realm). Breaking down and comparing such massive files introduces considerable overhead and can put significant strain on system resources.
To avoid this overhead, we will rely on our old trustworthy friend WAL (Write-Ahead Logging). By parsing WAL records, we can efficiently extract key details such as which block was modified, whether the relation was truncated (and up to which block), and which file the block belongs to. Since incremental backups are taken periodically after a baseline backup, the volume of WAL data to be processed is relatively small. This keeps the computational cost low and, importantly, independent of the total file size.
1. Definition
A block reference table is used to keep track of which blocks have been modified by WAL records within a certain LSN range.
The exact LSN range of interest is beyond the scope of this post and might be discussed in a future article.
Before moving forward, let’s take a look at some of the important terminologies.
1.1 RelFileLocator
Each and every thing in a database cluster is represented as a database object. All the database objects in PostgreSQL are internally managed by respective object identifiers (OIDs), which are unsigned 4-byte integers. Each database cluster contains multiple tablespaces, with each tablespace represented as a directory within the cluster. Inside each tablespace directory are sub directories for individual databases. Each of these databases, in turn, stores multiple relations (data files — contains tuples), which are represented as separate files.
typedef struct RelFileLocator
{
Oid spcOid; /* tablespace */
Oid dbOid; /* database */
RelFileNumber relNumber; /* relation */
} RelFileLocator;1.2 Fork Number
The forknumber is a small integer identifier used to distinguish between different storage segments (or forks) of a relation, such as a table or index. Each fork represents a different type of data or metadata associated with the relation, like the main data, visibility map, or free space map. These forks are stored as separate files within the storage system but belong to the same relation. Refer to comments for more info regarding the forknumber.
typedef enum ForkNumber
{
InvalidForkNumber = -1,
MAIN_FORKNUM = 0, // primary data storage area for a relation
FSM_FORKNUM, // keep track of available space in the relation
VISIBILITYMAP_FORKNUM, // which pages in the main fork contain no dead tuples, helps in optimization
INIT_FORKNUM,
} ForkNumber;In short, just remember that the forknumber are just different versions of the same relation file, which contains some information regarding a specific table or index and any operation of these files (except free_space_map fork) are recorded in WAL.
1.3 Limit Block
Its the shortest known length of the relation in blocks within the LSN range covered by a particular block reference table. It should be set to 0 if the relation fork is created or dropped. If the relation fork is truncated, it should be set to the number of blocks that remain after truncation. For instance, we have a table t1 (Oid: 16676) which has 4 blocks of data in it (fork_number = 0), after some time we perform a delete operation on the table where we delete block 2 and 3. The memory organization of the table before and after looks something like this:
Here we can see that, the limit block acts as a virtual termination block. It denotes the boundary block after the deletion.
1.4 Block Number
each data file (heap or index) is divided into postgres disk blocks (which may be thought of as the unit of i/o — a postgres buffer contains exactly one disk block). the blocks are 32-bits in size sequentially, 0 to 0xFFFFFFFE.
2. How memory serves this Data Structure
We’ll follow a top-down approach to examine the data structure to a granular level. From the memory point of view, BlockReferenceTable is nothing but a Adaptive Radix Tree {TODO: link to the paper}, that contains a leaf node corresponding to every relation fork in the database cluster.
2.1 Key for the ART
Every relation fork in the system is uniquely identified by a combination of its RelFileLocator and ForkNumber. To efficiently manage and reference these relation forks, we define a dedicated structure called BlockReferenceTableKey. This structure serves as a unique key for tracking each relation fork individually, ensuring accurate identification and management within the block reference table.
typedef struct BlockRefTableKey
{
RelFileLocator rlocator;
ForkNumber forknum;
} BlockRefTableKey;Since our Adaptive Radix Tree (ART) works with string keys, we need a way to convert a BlockReferenceTableKey into a string. One straightforward approach is to recursively traverse the structure, extracting all fields that are of primitive data types, and concatenate their values using a delimiter to form a unique string representation.
Get Ashsharma’s stories in your inbox
Join Medium for free to get updates from this writer.
2.2 File-level structure
Each leaf node denotes a pointer to a BlockReferenceTableEntry for each relation fork. We define BlockReferenceTableEntry something like this -
struct BlockRefTableEntry
{
BlockRefTableKey key;
BlockNumber limit_block;
uint32 nchunks;
uint16 *chunk_size;
uint16 *chunk_usage;
BlockRefTableChunk *chunk_data;
};Next, we look at the file-level structure of the data representation. In PostgreSQL, each file is segmented into fixed-size blocks, each 8KB in size. To further organize these blocks, we introduce the concept of a chunk, which groups together 2¹⁶ (65,536) consecutive blocks. For now, consider the arrangement of blocks inside a chunk as a black-box, just settle with the thought that a chunk can be an array or a bitmap. You can anytime get back here after taking a look at the representation of the chunk.
- limit_block: As defined above, this describes the block number of a relation file such that only the blocks with block number less than limit block are valid.
- nchunks: The total number of chunks in the file.
- chunk_size: array of size nchunks, that contain the information about the size of each chunk in bytes. We adapt a dynamic approach where we don’t allocate a space for 2¹⁶ blocks to a chunk upfront, we start with allocating space for INITIAL_ENTRIES_PER_CHUNK=16 blocks and as the number of blocks grow we scale this space with a factor of 2 until we reach MAX_ENTRIES_PER_CHUNK=2¹² (why 2¹² and not 2¹⁶, we’ll address this in a while).
- chunk_usage: array of size nchunks, storing the number of elements or entries used in each chunk. If that value is less than MAX_ENTRIES_PER_CHUNK, the corresponding chunk is used as an array; else the corresponding chunk is used as a bitmap.
- chunk_data: array of size nchunks, each element is either an array representation or bitmap representation of a chunk, that tracks the block number that have been modified.
2.3 Chunk-level structure
This section we’ll talk about the representation of a chunk in memory. Each Block Number is virtually divided into two parts, msb 16 bits represent the chunk number and lsb 16 bits represent the chunk offset.
Next, each chunk is divided into some number of entries (a maximum of 2¹² entries). Based on the total number of modified blocks, a chunk can be an array of blocks offset if the number of modified are less than MAX_ENTRIES_PER_CHUNK and if happens to be more than this threshold the chunk takes a bitmap representation approach.
For array representation each entry represent a block number while for bitmap representation each entry represent 16 block numbers.
When the number of modified blocks are less than MAX_ENTRIES_PER_CHUNK, chunk follow the array representation where each element of the array contain the 2-byte block number offset (lsb bits). The array can grow up to MAX_ENTRIES_PER_CHUNK i.e array representation can store modified status for 2¹² blocks only after which the chunk transition to bitmap representation.
To check whether a specific block in a relation fork has been modified for the array representation, we first determine its corresponding chunk by using the upper 16 bits (most significant bits) of the block number. Once we have the chunk number, we access chunk_data[chunk_number] and iterate through the associated entries in chunk_used[chunk_number]. We then compare the lower 16 bits (least significant bits) of the block number with each entry to see if it matches, indicating the block has been modified.
When the number of modified blocks in a chunk exceeds the predefined threshold (MAX_ENTRIES_PER_CHUNK), we switch to a bitmap-based representation. In this format, each entry holds a 16-bit bitmap, allowing it to track the modification status of 16 blocks. With a total of 2¹² such entries, this setup enables us to efficiently represent the modification status of all 2¹⁶ blocks within the chunk.
3 Serialization of Block Reference Table
Each summary file begins with a fixed sequence of bytes, known as magic bytes, which serve as a signature indicating the start of the file.
Next, before serializing the actual data (modified blocks), we store some metadata corresponding to each relation fork called the serialized_entry.
typedef struct block_ref_table_serialized_entry
{
struct rel_file_locator rlocator;
enum fork_number forknum;
block_number limit_block;
uint32_t nchunks;
} block_ref_table_serialized_entry;This serialized entry stores information about a specific relation fork and is followed by the chunk data.
Here is how the data is arranged in summary files:
4 Conclusion
This is the initial step towards incremental backup, adopted from postgres. The block reference table is designed with efficiency and speed in mind, offering a significant improvement over traditional methods that rely on comparing each block of two files to identify changes.
Further pgmoneta provides user with two serialization APIs to write the structure to a file or read the structure from file:-
/**
* Write the contents of the block reference table to a file stream
* @param brt The block reference table
* @param file The file stream
* @return 0 if success, otherwise failure
*/
int
pgmoneta_brt_write(block_ref_table* brt, FILE* file);
/**
* Read the contents of the summary file and create a block reference table from it
* @param file The file stfream
* @param [out] brt The block reference table
* @return 0 if success, otherwise failure
*/
int
pgmoneta_brt_read(FILE* file, block_ref_table** brt);To know more about the implementation you can go through the https://github.com/pgmoneta/pgmoneta/blob/main/src/libpgmoneta/brt.c file.
