📢 In this post, we take a closer look at the Transaction ID (XID) introduced with the MVCC model. First, we cover ① what an XID is and what it is used for, and then ② the approach PostgreSQL chose to overcome the shortage of XIDs.
Transaction ID
What is an XID?
We cannot know what will happen in the future, but we can know what happened in the past. In a DBMS, a series of events is called a transaction, and the XID is the information used to identify when a transaction occurred. In other words, you can think of an XID as a kind of time information.
The XID increases by one each time a transaction occurs, and it is used to implement the MVCC model and to guarantee read consistency.
What XIDs are used for
You may wonder where and how the ever-increasing XID is actually applied. Like time information, the XID is used to record the point in time whenever an object is created or data is changed, as shown below.
relfrozenxid: the XID at object creation is assigned to the object (+ updated when Vacuum runs)
XMIN,XMAX: the XID at which a row (record) was inserted or changed is assigned per row
XIDs assigned per object and per row are compared with the XID at query time to decide whether a row should be visible. Objects with XIDs that are too old also become Vacuum targets.
Structural limits and countermeasures
Running out of XIDs
Using the XID as time information means that the value alone must be enough to pin down a point in time. It is similar to our certainty that the year 2022 we live in will never come again.
Oracle SCN, the counterpart of the PostgreSQL XID, can represent up to 2^63 (as of 19c), a range that would last thousands of years. There is a limit, but it will practically never be reached, so it can be considered sufficient.
Each record (row) carries 4 Byte of version information (XID) so that its point in time can be identified - From PostgreSQL Vacuum - 1. MVCC -
In PostgreSQL, however, an XID must be assigned per row whenever data is inserted or changed, so space usage inevitably becomes an issue.
In other words, the 4 Byte XID, defined with space savings in mind, ended up limiting the range of XIDs that can be represented. 4 Byte can represent only about 4.3 billion XIDs, which a high-TPS system can exhaust in just a few months.
Circular structure
To overcome this structural shortage of XIDs, PostgreSQL uses XIDs in a circular structure.
As shown below, relative to the current point in time, half of all XIDs (2 billion out of 4 billion) form a reserved XID space for future transactions (Newer), and the other half (2 billion) form an XID space that guarantees read consistency for past transactions (Older).
📌 PostgreSQL actually has about 4.3 billion XIDs, and the Newer and Older areas each hold about 2.1 billion. In this post we use 4 billion and 2 billion for simplicity and easier calculation.
Let's look at the figure below to understand the circular structure more easily.
As mentioned above, the XIDs that belong to the Newer/Older areas are not fixed. The Newer/Older areas simply act like fixed windows, each looking at 2 billion XIDs. The XIDs, on the other hand, move counterclockwise like a conveyor belt each time a transaction occurs, and when they reach the end of the rail they circle back and are appended to the end of the Newer area.
So the XIDs in the Newer/Older areas keep changing with the current point in time, and for the same reason, whether an XID value is large or small does not decide whether it is Newer or Older.
Anti-Wraparound and Data Freezing
If you have followed so far, you may have the following question.
In a circular structure that completes one cycle every 4 billion XIDs, won't the same XID eventually make it impossible to identify the point in time?
For example, assume there is data inserted at XID=3 that has not changed since.
As time passes and Current XID reaches 4 billion, the data inserted at XID=3 was clearly inserted in the past, but its XID now sits in the Newer area. So you cannot tell whether data with that XID belongs to the past or the future.
📌 This is why the XIDs in the figure start at 3: 0, 1, and 2 are reserved values with special meanings. Among them, XID=2 is called the Frozen XID. Normal XIDs used by real transactions range from 3 to 4 billion, so the Frozen XID is always guaranteed to be smaller (older) than any normal XID.
To avoid this, PostgreSQL changes the XID of such data to a special value before "Current XID - XID at creation (insert)" exceeds about 2 billion, half a cycle (= the period spent in the Older area). This also tells us that of the 4 billion XIDs, only 2 billion are actually usable.
This series of operations to avoid XID Wraparound is called
Data Freezing. Internally, it marks the XID with a special value called Frozen XID to indicate that the data is permanently in the past.In this case, the data inserted at XID=3 is guaranteed to be converted, before Current XID reaches 2 billion, into
Frozen XID ahead of time, so it can no longer be confused with data inserted at a later XID=3.Related articles
