Inside The Storage Engine: GAM, SGAM, PFS and other allocation maps

 

Well this one is well overdue and I’m in the middle of writing a class where I want to reference this blog post – so I suppose I’d better write it!! This is an updated post from my old Storage Engine blog that now covers DIFF and ML map pages.

In some previous posts in this series I built up the storage basics in database files:

• Anatomy of a record
• Anatomy of a page
• Anatomy of an extent
• IAM pages, IAM chains, and allocation units

The final pieces in the allocation puzzle are the other allocation-tracking map pages – GAM, SGAM, PFS, ML map, and DIFF map pages. All of the following explanation holds for SQL Server 2000 and all subsequent releases so far. For any of these pages you can do a dump-style 3 DBCC PAGE dump and it will interpret the page and give you a human readable form of the allocation tracking data.

GAM pages

GAM stands for Global Allocation Map. If you remember from before, database data files are split up into GAM intervals (don’t get confused – they’re not split physically, just conceptually). A GAM interval is equivalent to the amount of space that the bitmaps in GAM, SGAM, ML map, DIFF map, and IAM pages track – 64000 extents or almost 4GB. These bitmaps are the same size in each of these five page types and have one bit per extent, but they mean different things in each of the different allocation pages.

The bits in the GAM bitmap have the following semantics:

• bit = 1: the extent is available for allocation (you could think of it as currently allocated to the GAM page)
• bit = 0: the extent is already allocated for use

These semantics are the same for mixed and dedicated/uniform extents.

One thing to note, at the start of every GAM interval is a GAM extent which contains the global allocation pages that track that GAM interval. This GAM extent cannot be used for any regular page allocations. The first GAM extent starts at page 0 in the file and has the following layout:

• Page 0: the file header page (another post!)
• Page 1: the first PFS page
• Page 2: the first GAM page
• Page 3: the first SGAM page
• Page 4: Unused in 2005+
• Page 5: Unused in 2005+
• Page 6: the first DIFF map page
• Page 7: the first ML map page

SGAM pages

I remember last year having an email discussion about what the ‘S’ stands for in SGAM. Various names have been used over the years inside and outside Microsoft but the official name that Books Online uses is Shared Global Allocation Map. To be honest, we always just call them ‘es-gams’ and never spell it out.

As I said above, the SGAM bitmap is exactly the same as the GAM bitmap in structure and the interval it covers, but the semantics of the bits are different:

• bit = 1: the extent is a mixed extent and may have at least one unallocated page available for use (it’s an optimistic update algorithm)
• bit = 0: the extent is either dedicated or is a mixed extent with no unallocated pages (essentially the same situation given that the SGAM is used to find mixed extents with unallocated pages)

Combining GAM, SGAM, and IAM pages

So, taking the GAM, SGAM and IAM pages together (remember that in the IAM bitmap, the bit is set if the extent is allocated to the IAM chain/allocation unit), the various combinations of bits are:

GAM	SGAM	Any IAM	Comments
0	0	0	Mixed extent with all pages allocated
0	0	1	Dedicated extent (must be allocated to only a single IAM page)
0	1	0	Mixed extent with >= 1 unallocated page
0	1	1	Invalid state
1	0	0	Unallocated extent
1	0	1	Invalid state
1	1	0	Invalid state
1	1	1	Invalid state

You can see that only 4 of the 8 possible bit combinations for any particular extent are valid. Anything else constitutes a corruption of some sort and can lead to all kinds of horrible situations.

ML map pages

ML stands for Minimally Logged. These pages track which extents have been modified by minimally-logged operations since the last transaction log backup when using the BULK_LOGGED recovery model. The idea is that the next transaction log backup will backup the log as usual, and then also include all the extents marked as changed in these bitmaps. The combination of these extents, plus the transaction log in the backup gives the differences that have occured in the database since the previous transaction log backup. The ML page bitmaps are cleared once they’ve been read. If you don’t ever use the BULK_LOGGED recovery model, these pages are never used.

The ML page bitmap is exactly the same as the GAM bitmap in structure and the interval it covers, but the semantics of the bits are different:

• bit = 1: the extent has been changed by a minimally logged operation since the last transaction log backup
• bit = 0: the extent was not changed

DIFF map pages

DIFF stands for differential. These pages track which extents have been modified since the last full backup was taken. It is a common misconception that the bitmaps track the changes since the last differential backup. The idea is that a differential backup will contain all the extents that have changed since the last full backup. Restore time can be cut down significantly by using differential backups to avoid having to restore all the log backups in the period between the full and last differential backup – more on this in a later post. The bitmaps are not cleared until the next full backup. Note that I don’t say full database backup in the explanation above. The full and differential backups can be database, filegroup, or file level backups.

The DIFF page bitmap is exactly the same as the GAM bitmap in structure and the interval it covers, but the semantics of the bits are different:

• bit = 1: the extent has been changed since the last full backup
• bit = 0: the extent was not changed

PFS pages

PFS stands for Page Free Space, but the PFS page tracks much more than that. As well as GAM intervals, every database file is also split (conceptually) into PFS intervals. A PFS interval is 8088 pages, or about 64MB. A PFS page doesn’t have a bitmap – it has a byte-map, with one byte for each page in the PFS interval (not including itself).

The bits in each byte are encoded to mean the following:

• bits 0-2: how much free space is on the page
  • 0x00 is empty
  • 0x01 is 1 to 50% full
  • 0x02 is 51 to 80% full
  • 0x03 is 81 to 95% full
  • 0x04 is 96 to 100% full
• bit 3 (0x08): is there one or more ghost records on the page?
• bit 4 (0x10): is the page an IAM page?
• bit 5 (0x20): is the page a mixed-page?
• bit 6 (0x40): is the page allocated?
• Bit 7 is unused

For instance, an IAM page will have a PFS byte value of 0x70 (allocated + IAM page + mixed page).

Free space is only tracked for pages storing LOB values (i.e. text/image in SQL Server 2000, plus (n)varchar(max), varbinary(max), XML, and row-overflow data in SQL Server 2005) and heap data pages. This is because these are the only pages that store unordered data and so insertions can occur anywhere there’s space. For indexes, there’s an explicit ordering so there’s no choice in the insertion point.

The point at which a PFS byte is reset is not intuitive. PFS bytes are not fully reset until the page is reallocated. On deallocation, the only bit in the PFS byte that’s changed is the allocation status bit – this makes it very easy to rollback a deallocation.

Here’s an example. Using a database with a simple table with one row. A DBCC PAGE of the IAM page includes:

PFS (1:1) = 0x70 IAM_PG MIXED_EXT ALLOCATED 0_PCT_FULL

If I drop the table in an explicit transaction and then do the DBCC PAGE again, the output no includes:

PFS (1:1) = 0x30 IAM_PG MIXED_EXT 0_PCT_FULL

And if I rollback then transaction, the DBCC PAGE output reverts to:

PFS (1:1) = 0x70 IAM_PG MIXED_EXT ALLOCATED 0_PCT_FULL

Ok – four blog posts in one day is quite enough! :-)