PostgreSQL 8.0, the 2q memory manager

With the revolutionary PostgreSQL 8.0 were introduced a different memory manager, the two queues.

This algorithm uses three list of buffer page pointers called cache directory blocks (CDB). The lists T1,T2 are actually pointing buffered pages. B1 lists pages been recently in the shared buffer.

The list T1 is used as LRU for the pages loaded from disk. The list T2 is used as LRU list for pages already cached and evicted from the list T1. The list B1 is a LRU list of pages recently evicted from the shared buffer.
When a new page is read from disk is put initially at the beginning of T1. All the CDB in T1 are shifted and the last element in T1 is evicted from the shared buffer, its CDB is put at the B1’s top.

When a backend requests a page present in T1 its CDB is removed from T1 and placed at the T2’s top. The last element in T2 is evicted from the shared buffer and its CDB is put at the B1’s top.

When a backend requests a page in T2 the CDB is moved to the list’s top.

Finally, when a page is read from the disk but its CDB is present in B1, then the page is put at the T2’s top.

The list T1 is the LRU list where the pages requested only one time are evicted quickly from the shared buffer. The list T2 is a MRU list where the pages are moved back on the top when required and where the pages from T1 are stored if required before the eviction. The list B1 is used as extra cache to track pages recently evicted from the shared buffer that need to stay in T2 if requested again.

Despite the interesting approach, this tricky process did not show good performances in production. Things changed when the clock sweep was implemented in PostgreSQL 8.1.

the ARC

The 2q algorithm was an emergency implementation caused by a software patent held on the algorithm initially chosen for the PostgreSQL 8.0’s memory manager. Old books, printed meanwhile the 8.0 was in development, wrongly list the ARC as memory manager. The ARC is an efficient algorithm which keeps in memory two lists of page buffers, one for the LRU and for the MRU. Each list adapts dynamically with the different requests of the cluster’s activity.