首页 > Linux操作系统 > Linux操作系统 > understanding of FREELISTS and FREELIST GROUPS

understanding of FREELISTS and FREELIST GROUPS

原创 Linux操作系统 作者:tolywang 时间:2005-02-18 00:00:00 0 删除 编辑   



The purpose of this article is to provide an understanding of FREELISTS and




This article is intended to be used by DBAs to help understand how FREELISTS and




The following bulletin is comprised of several parts:

1. Introduction to Oracle data block organization

2. Free List Overview

3. Free List Types

4. Considerations for Optimizing Space Management

5. Algorithms

6. FreeLists in Oracle

1. Introduction:


Before going into the details of freelist management one must know how the

Oracle data blocks are organized.

Every object in an Oracle database which occupies space is associated with a

segment. A segment is a set of extents that contains all the data for a

specific logical storage structure within a tablespace.

There are 4 segment types:

o permanent data segment (table, cluster)

o index segment

o rollback segment

o temporary data segment

Each segment is made up of smaller storage units called extents. An extent is

a storage unit composed of contiguous blocks.

Each segment is initially created in the database with at least one extent

(controlled by parameter MINEXTENTS). Though empty, the space is reserved.

When the initial space is full, a new extent is dynamically allocated. The new

extent size is determined by the parameters NEXT and PCTINCREASE. The dynamic

allocations stop when the number of extents reaches the value of parameter


The first block of the first extent of each segment is reserved by Oracle to

store system information and it is called the segment header.

The Segment Header contains :

o The Extents Table

o The Free Lists descriptors

o The High Water Mark (HWM)

The HWM marks a limit in the segment where each block below is "in use", and

each block above has never been used. The HWM always increases in size; It is

reset to "zero" (position to the start of the segment) when a TRUNCATE is


2. Free List Overview


Starting with V7.3, it is now possible to create a segment either with a

limited number of extents or with an unlimited number of extents. To

accommodate this, five new block types are introduced:

14 : Unlimited Rollback Segment Header

15 : Unlimited Deferred Rollback Segment Header

16 : Unlimited Data Segment Header

17 : Unlimited Data Segment Header with FL groups

18 : Extent Map Block

For each data segment, Oracle keeps track of blocks having available free

space for incoming INSERT or UPDATE.

Free Space comes from 2 ways:

1. All blocks beyond the HWM that are allocated but not used.

2. All blocks below the HWM linked in a free list, and candidates to be


A Free List is constituted of :

o Flag to indicate if the free list is used (1) or unused (0)

o DBA of the block head of the Free List Chain,

o DBA of the block tail of the Free List Chain.

In each Data Block there is a flag to indicate if the block is linked in a

Free List chain. If the flag is set the block will also point to the DBA of

the next block in the free list chain. A zero value means that the current

block is the last block in the chain.

3. Free List Types:


The Master Free List or Common Free space pool:


There is only one for each segment. It is implicitly allocated at segment

creation time. For each data segment there is a pool, common for each process,

of blocks containing free space available for incoming inserts called the

Master free list. Every process has access to this common pool. So, the level

of contention increases when several process simultaneously want to insert

rows in the same segment. The blocks of initial extents allocated at segment

creation time and of the new ones dynamically allocated are linked to the

Master free list.

The Process Free Lists:


To reduce contention problems on the Master Free list, another level of free

lists is available which is called the Process free lists, Explicitly created

when the FREELISTS parameter has been specified in a


Partitioning the Free Space in multiple free lists is used essentially to

improve the performance of OLTP applications with a high degree of concurrent

transactions performing inserts or updates requiring new space allocation.

Parameter FREELISTS has been added in the STORAGE clause of a CREATE TABLE /



CREATE TABLE flg ( . . . .) . . . STORAGE ( ... FREELISTS 10 ...);

The number of process freelists must be close to the maximum number of

concurrent process performing simultaneously inserts in the segment.

It is important to note that this improves the inserts performance, but wastes

disk space usage.

Each process is mapped to a Process free list by its Oracle PID (Process ID):

Process free list entry = (P % NFL) + 1

where P : Oracle PID of the process (index in V$PROCESS),

and NFL : Process free lists number as defined by parameter FREELISTS

The Transaction Free Lists:


Implicitly allocated by Oracle as needed. A Transaction Free List is a free

list dedicated to one transaction and only one. There are a minimum of 16

transactions free lists per segment, and this number increases as long as it

is necessary, until it reaches the limit of the Segment Header block size.

A transaction needs to allocate a Tx Free Lists entry when:

o It releases space in a block (DELETE or UPDATE)

o And if it has not already allocated one.

4. Considerations for Optimizing Space Management:


The two parameters PCTFREE and PCTUSED of the Storage Clause in a CREATE/ALTER

statement, are used to control and optimize space management within a data

segment block (table, cluster).

PCTFREE specifies the percentage of a data block to be reserved (kept free)

for possible updates to rows that already are contained in that block. After a

block becomes full, as determined by PCTFREE, Oracle does not consider the

block is for the insertion of new rows until the percentage of the block being

used falls below the parameter PCTUSED.

It is advised that the space calculated as (100% - (PCTFREE + PCTUSED)) be

greater than the maximum size of a table row.

5. Algorithms:


A block is put on free list if the free space in the block is greater than the

space reserved by PCTFREE. Blocks linked in a free list are available for

future updates or inserts.

A block is unlinked from a free list if the free space in the block is not

enough to allow a new row insert, and if the percentage of the used space

remains above PCTUSED.

A block is relinked to a free list if after DELETE or UPDATE operations, the

percentage of the used space falls below PCTUSED.

Each time a block is added to a free list, it is linked at the head of the




At time t0 , 2 blocks are on free list : data blocks 1 and 3:

FL: B1 -> B3

At time t1, deletions are done on block B2 such as the block has to be

relinked to Free list:

FL: B2 -> B1 -> B3

A data block is put on Free list only if it is not already linked.

Transaction Free List Algorithms:


The Tx free list allocation process starts by scanning all Tx free lists

allocated in the segment Header block and checking if a Tx free list entry has

not already been allocated to the transaction. Else, it looks for an unused

entry or an empty Tx free list belonging to a "committed" transaction. If the

search fails, a new entry in the Tx free lists area is allocated.

When there is no chance to expand the Tx Free lists area, the unfortunate

transaction has to wait for an entry release. The selected entry is determined

by (PID % Tx free lists total number). PID is the Oracle process Id. The wait

is done by requesting in S mode the TX enqueue held by the transaction T owning

the Tx free list entry. The wait will end when T commits.

The space freed in a block by a transaction T1 (DELETE or UPDATE) :

o is immediately reusable by T1,

o will be reusable for other transactions only after T1 commits and when

looking for space in this block.



5.1 Transaction T1 deletes some rows in table T. These operations release

some space in block 10 in the segment. The percentage of the remaining

used space falls below PCTUSED: block can be reused for incoming inserts,

it is put on free list. To do this, Transaction T1 needs to allocate an

entry in the Transaction free lists area in the Segment Header block,

then links the block 10 in the corresponding free list.

5.2. Transaction T2 wants to insert a new row in table T. The space freed

by T1, in block 10, cannot be reused. Assume that T2 does not have a

Tx free list allocated in the segment (because T2 has not released

space in the segment)

5.2.1 T2 starts walking on its Process Free List (PrFL) looking for a free

block. (Let's assume that there are 3 blocks on the PrFL and they

don't have enough free space T2 needs.)

5.2.2 The first block fails the check. The block must be exchanged (move to

the next block on the list) with another one. This block has to be

unlinked from the free list if the used space in the block goes

beyond the space defined by PCTUSED or, if the "UNLINK counter" is

below a particular threshold. (The default value is 5). The idea

behind this is not to keep blocks that fail during free space search

at the head of free lists.

The UNLINK action is done only if the current block is head of the

free list chain.

5.2.3 After all the blocks on the PrFL are checked and no block is found,

the block selection in the process free list is stopped

5.2.4 Oracle tries to move blocks from Master free list to Process free

list. This operation is called Free Lists Merge. The number of blocks

to move is defined by a constant and it is 5. Search will continue

from step 5.2.1

Note that at this point Oracle WILL NOT look at the other PrFL even

though there might be empty blocks on those lists. This will cause

some space to be wasted temporarily.

5.2.5 (Assume that there are no more blocks on the Master Free List)

Oracle tries now to get blocks from the other Tx free lists

(committed). The Tx free lists entries in the header block are

scanned, looking for not empty and "committed" entries. For those

entries, ALL the blocks are moved to the Master Free list. Then,

only a part (5) of the blocks in Master free list are moved again

to process free list.

If there are blocks moved from the TxFl to the MsFL, go to step 2.1

5.2.6 (If 2.5 fails) Oracle tries to bump up the HWM. To reduce contention

on segment header block, Oracle bumps up the HWM by m blocks at a

time. The number m is:

1: if the block does not have to go on free list,

1: if we are on the initial extent (0) and the HWM is <= 4 (small


min (5, unused blocks in the extent): before 7.2

min (5*(NFL+1), unused blocks in the extent): since 7.2.

In the example, we assume HWM is at the end of the extent.

5.2.7 New extent allocation. The new blocks are moved to Master free list.

Free block search continues from step 2.4

5.3 Transaction T1 wants now to insert a new row in table T. First, it

looks for available space in blocks linked to its transaction free

list. The block 10 has available space, and the free space in it is

enough to the space required by the new row, block 10 is selected.

The percentage of the used space in the block goes up above PCTUSED,

the block has to be unlinked from the transaction free list.

6. Freelists Groups:


In multi-instances (Oracle Parallel Server), to reduce contention on the

segment header block, which contains the free lists descriptors of the

segment, it is possible to allocate other special blocks to store free lists

descriptors. These groups are called the Free Lists Groups.

FREELIST GROUPS is introduced in STORAGE clause of a CREATE TABLE / CLUSTER or




CREATE TABLE flg ( . . . .) . . . STORAGE ( ... FREELIST GROUPS 2

FREELISTS 10 ...);

Each free list group is associated with a special block called the Free List

Block. These blocks will be allocated right after the segment header. So, if

and object is created with 2 freelist groups, the first block of the first

extent will be the segment header block and the second and third blocks will

be the freelist blocks.

These blocks store a Master free list (of the group), and as much process free

lists as specified by parameter FREELISTS. The rest of the block dedicated to

Transactions free lists.

In the segment header block of an object with free list groups there is only

one free list called The Super Master Free list or the Segment Master free


The free list groups reduce contention on the segment header block, and reduce

inter-instance "pinging", at the cost of excessive disk space consumption.

The algorithm to map a Freelist Group, defined on a segment S, to a process P

of an instance I, is the following:


NFB : number of Freelist Groups defined on segment S,

P : Oracle PID of the process (from V$PROCESS),

I : INSTANCE_NUMBER parameter (if set in INIT.ORA) or parameter

THREAD value

MAXINST : maximum of instances sharing the same database (MAXINSTANCES

parameter of CREATE DATABASE).

In a non OPS environment or OPS and Single-Instance environment:

Free list group is: (P % NFB) + 1

In a multi-instance environment (OPS):


Free list group is : ((I-1) % NFB) + 1




if (I-1) < REST

Free list group is : INITIAL + (P % (RANGE+1))

if (I-1) >= REST

Free list group is : INITIAL + REST + (P % RANGE)



For the given table and all index associated to it, the TRUNCATE operation

does the following tasks:

1. Get exclusive access to the segment header. If the segment header

is locked process has to wait its release by requesting a TX lock

in Shared mode.

2. Lock the segment header.

3. Flush all blocks belonging to this segment in the buffer cache to


4. Clear all the free lists in the segment header block and in all

free list groups blocks (if freelist groups are defined). The

before image of all the changes are recorded in the Rollback


5. Truncate the segment: the HWM returns to its initial position

(extent 0 and block 0 if table or 1 if index). The before image

of the change is recorded in the rollback segment.

6. Trim all the extents beyond MINEXTENTS.

7. If OPS, flush on disk the segment header block and free list groups


NOTE: Performance vs. Space


As can be seen from the algorithms above, using multiple free lists may cause

some empty blocks to go unused, causing the segment to extend. If performance

is critical, multiple free lists can be used to improve concurrent access,

possibly at the expense of additional space used. However, if space is the

primary consideration, then a single freelist should be used, leaving

FREELISTS=1, without the performance benefits for concurrent transactions.



[NOTE:157250.1] Freelist Management with Oracle 8i

来自 “ ITPUB博客 ” ,链接:,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
Oracle , MySQL, SAP IQ, SAP HANA, PostgreSQL, Tableau 技术讨论,希望在这里一起分享知识,讨论技术,畅谈人生 。


  • 博文量
  • 访问量