Oracle Freelist和HWM原理探讨及相关性能优化
中兴通讯重庆研究所 游波
要害词：Freelist，HWM，存储参数，段，块，dump，优化
文章摘要：
近期来，FreeList的重要作用逐渐为Oracle DBA所熟悉，网上也出现一些相关的讨论。本文以FreeList为线索对Oracle的存储治理的原理进行较深入的探讨，涉及Oracle段区块治理的原理，FreeList算法等。而与FreeList密切相关的一个重用特性HWM，与sql性能密切相关，本文也作了原理分析介绍。在原理探讨的基础上，介绍了常用的存储参数分析方法，并对所涉及的存储优化、HWM的优化和Freelist竞争优化作了说明。
缩略语：
ASSM：auto segement space management
HWM：high water mark
DBA：data block address
OLTP：online transaction PRocess
OPS：oracle parallel server
1.简介
Oracle的空间治理和存储参数治理是Oracle治理及优化的重要部分。FreeList作为Oracle底层存储参数中的核心参数，其行为方式对Oracle的存储治理及性能优化有重大影响，而现有的Oracle文档对此方面的内容比较缺乏。虽然Oracle 9i已出现了ASSM，但是作为深入调优对FreeList熟悉仍是必要的。
近期来，FreeList的重要作用逐渐为Oracle DBA所熟悉，网上也出现一些相关的讨论。本文以FreeList为线索对Oracle的存储治理的原理进行较深入的探讨，涉及Oracle段区块治理的原理，FreeList算法等。而与FreeList密切相关的一个重用特性HWM，与sql性能密切相关，本文也作了原理分析介绍。在原理探讨的基础上，介绍了常用的存储参数分析方法，并对所涉及的存储优化、HWM的优化和Freelist竞争优化作了说明。
这些原理分析和性能优化都建立在探讨的基础上，限于篇幅和本人经验可能存在局限、偏差或谬误。
为了准确文中部分结构和字段的说明直接用英文描述。
限于篇幅本文不对同样很重要的block结构作更深入的讨论，对OPS性能有重要影响的free list group本文也未提及，因此本文在单一free list group下讨论。对于block的深入讨论、free list group的介绍与优化以及PCTUSED和PCTFREE等重要参数的优化请参见参考文献和资料。
2.原理探讨
FreeList作为一个Oracle存储治理的核心参数。其行为方式由Oralce内部控制，我们一般不需要把握和控制。但是我们可能会碰到这些问题，当插入一条记录，会插入到那个块中？是使用新块，还是插入有数据的老块？段是什么时候扩展的，如何扩展的？表中只有一条记录，但是作一次select时代价却是上千个块，为什么？假如我们从原理上清楚了Oracle的存储治理方式，对相关这些问题的解决及性能优化就清楚自然了。
2.1 Oracle的逻辑储存结构
Oralce的逻辑存储结构按表空间，段，区，块进行治理。块是Oracle用来治理存储空间的最基本单元，Oracle数据库在进行输入输出操作时，都是以块为单位进行逻辑读写操作的。区由一系列连续的块组成，Oralce在进行空间分配、回收和治理时是以区为基本单位的。段由多个区组成，这些区可以是连续的也可以是不连续的，一般情况下一个对象拥有一个段。表空间中容纳段和区。
在生成段的时候，会同时分配初始区(initial extents)， 初始区的第一个块就格式化为segment header，并被用来记录free list描述信息、extents信息，HWM信息等。
2.2 free list概念
free list是一种单向链表用于定位可以接收数据的块，在字典治理方式的表空间中，Oracle使用free list来治理未分配的存储块。Oracle记录了有空闲空间的块用于insert或Update。空闲空间来源于两种方式：1.段中所有超过HWM的块，这些块已经分配给段了，但是还未被使用。2.段中所有在HWM下的且链入了free list的块，可以被重用。free list具有下列属性
l flag指示free list 被使用(1)或未使用(0)
l free list 链的首块的地址DBA(data block address)
l free list 链的尾块的地址DBA
free list 的信息通常保留在segment header中,这里给出segment header block dump片段加以说明：
nfl = 3, nfb = 1 typ = 1 nxf = 0
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
SEG LST:: flg: USED lhd: 0x03c00233 ltl: 0x03c00233
SEG LST:: flg: USED lhd: 0x03c00234 ltl: 0x03c00234
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
Segment Header:
==> nfl: number of free lists/block
==> nfb: number of free list blocks + segment header
==> typ: block type
==> nxf: number of transaction free lists
Segment List:
==> flg: flag USED or UNUSED the free list
==> lhd: head of free list
==> ltl: tail of free list
在每一个块中都有一个标记flg用来表明块是否链入了 free list链中。
假如这个标志置上，该块中后向指针指向free list链中下一个块的DBA。假如当前块是链的最末尾的块，该后向指针值为0。
这里给出位于free list上的block dump的片段
Block header dump: 0x03c00235
Object id on Block? Y
seg/obj: 0xe2d8 csc: 0x00.6264c61 itc: 1 flg: O typ: 1 - DATA
fsl: 1 fnx: 0x3c00234 ver: 0x01
==> Seg/obj Object ID in dictionary
==> csc SCN of last block cleanout
==> itc Number of ITL slots
==> flg O = On freelist , - = Not on freelist
==> typ 1 = DATA 2 = INDEX
==> fsl ITL TX freelist slot
==> fnx DBA of NEXT block on freelist
举例来说假如有五个块在free list中，分别为A,B,C,D,E
就会形成segment header->A->B->C->D->E--
同时segment header->E
2.3 free list类别
在段中存在3类free list, 即Master Freelists (MFL), Process Freelists (PrFL), 和 Transaction Freelists.
2.3.1 Master Free List(公用空闲空间池):
每一个段中有一个Master free list，在段创建的时候自动生成。对于每一个段来说都有这样一个空闲空间池,对每个进程都是公用的，空闲空间就是位于master free list 的块上。由于Master free list是公用的，因此当多个进程同时插入行到同一个段上,master free list竞争使用程度就会增加。
2.3.2 Process Free Lists
为了减少Master Free list的竞争问题, 引入了另一种free list叫做Process free lists, 根据sql命令 CREATE/ALTER 中的参数FREELISTS 创建. 这样多个free list 就可以分摊空闲空间的治理，以提高OLTP应用作高度并发插入和更新事务时空间分配治理的性能。通过指定CREATE TABLE / CLUSTER or INDEX的子句STORAGE的参数FREELISTS 来创建，例如: CREATE TABLE flg ( . . . .) . . . STORAGE ( ... FREELISTS 10 ...)。缺省的FREELISTS为1，此时不会创建Process free lists。当FREELISTS>=2时，创建Process free lists。
进程在使用process free list是根据进程的Oracle PID (Process ID)来选择的，公式如下:
select list entry = (PID % NFL) + 1
NFL : FREELISTS定义的Process free list个数
2.3.3 Transaction Free Lists
当Oracle需要时动态创建。一个Transaction Free List 是一种专门给某一个事务使用的free list. 每个段至少有16个transactions free lists, 并且这个值在需要时会增长，直到达到Segment Header块的大小限制。一个事务只有下面情况下会需要分配一个Tx Free Lists entry: 块中释放空间时(DELETE or UPDATE) 并且还不存在Tx Free Lists entry时。
2.4 Free list行为2.4.1 Freelist Link and Unlink 操作
Freelist 按后进先出队列(LIFO) 方式治理。也就是说最后被link到freelist的块拥有最先unlink的机会。
当块中空闲空间增加到大于PCTFREE时，块放入freelist中。free list中的块可用来作update 或insert。 当块中没有足够的空间用于insert操作时并且使用空间大于PCTUSED，块就会从free list中移出。
在块在DELETE or UPDATE 操作之后，假如使用空间落到PCTUSED下，块再次link到free list中。每次块加入free list时，都是link到链表的头部。
例如：考虑段中有120个块编号由1到120。其中有6个块在free list上并假设HWM是 80。（block实际使用DBA编号）
10->24->45->46->65->80-
现在作INSERT 操作,需要400 bytes空间。假设块10上空间不足，但块24上空间可用。现在数据插入到块 24 ，现在块24的剩余空间小于该表的PCTUSED。因此块 24 从free list链表中移出。PCTFREE and PCTUSED参数的目的就是用来控制数据块从free list的链表中移入/移出行为的。现在free lists象这样：
10->45->46->65->80-
然后在同一事务中作DELETE同一个段的数据，使块 54 和 67落到PCTUSED下。现在这些块加入到free list链中。free list链现在象这样:
67->54->10->45->46->65->80-
2.4.2 Transaction Free List 算法
扫描segment Header块中所有的Tx free list,检查是否还没有Tx free list entry分配给transaction， 如何没有，将寻找未使用的entry或已经提交了事务的空的Tx free list。
假如上述搜索过程失败, 新的entry会在segment Header块中Tx free lists区域中开辟。假如没有空间来生成, 事务就必须等待entry的释放。
segment header中的最大free list个数:
Block Size Max # Freelists
----------- -----------------
2K 24
4K 50
8K 101
16k 204
事务T1释放出来的空闲块(DELETE or UPDATE)的使用 :
l 立即被T1所重用
l 当T1 commit后被其它需要空闲块的事务重用，过程举例如下:
2.5 HMW概念
HIGH WATER MARK代表一个表使用的最大的(top limit)块 。2.1中已经提到HIGH WATER MARK 记录在segment header中，并且在Oracle插入数据时一般增长5个blocks（并非总是5个块，具体参见2.4.2中流程图中HMW增长方式）。
segment header block中与HWM相关信息说明如下:
EXTENT CONTROL:
Extent Header:: spare1: 0 space2: 0 #extents: 13 #blocks: 1429
last map 0x00000000 #maps: 0 offset: 4128
Highwater:: 0x020004d0 ext#: 12 blk#: 275 ext size: 475
#blocks in seg. hdr's freelists: 5
#blocks below: 1229
mapblk 0x00000000 offset: 12
Unlocked
==> spare1: this field is no longer used (old inc#, now always 0)
==> space2: this field is no longer used (old ts#, now always 0)
==> #extents: number of extents allocated to segment
==> #blocks: number of blocks allocated to segment
==> last map: address of last extent map block
0 if extent map is entirely in the segment header
==> #maps: number of extent map block
==> offset: offset to end of extent map
==> HWM dba: address of block at highwater mark
==> ext#: HWM extent number relative to segment
==> blk#: HWM block number within extent
==> ext size: HWM extent size (in blocks)
==> #blocks in seg. hdr's freelists: number of blocks in seg. hdr's free list
==> #blocks below: number of blocks below HWM
==> mapblk dba: dba of extent map block containing HWM extent
is 0 if HWM is in the segment header
==> offset: offset within extent map block
is the ext# if HWM is in segment header
==> Locked by: if locked by a transaction, the xid is displayed
HWM可以说是已经使用过的存储空间和未使用过的存储空间之间的分界线。
在表使用过程中，HWM一直向一个方向移动，插入记录时HWM可能会向增加的方向移动，但是删除记录时HWM并不会向相反的方向移动。参见2.4.2。下图显示了某个数据段中HWM的位置情况。
图2.5
HIGH WATER MARK之所以重要是因为它对全表扫描性能的影响。当实施一个全表扫描时，Oracle会读取所有HIGH WATER MARK下的块即使它们是空块。当HIGH WATER MARK 下有很多unused block时实施全表扫描会增加额外的不必要的I/O。它也会在全局共享区中填充很多很多空块。
3.分析方法
存储参数基本上属于oracle internal的东西，因此oralce并没有提供很好的手段来分析。但是对于DBA来说，还是可以通过block dump和DBMS_SPACE等手段来获取部分信息。
3.1 提取block和free list信息
创建dbms_space使用的存储过程show_space
SQL>
create or replace procedure show_space
( p_segname in varchar2,
p_owner in varchar2 default user,
p_type in varchar2 default 'TABLE',
p_partition in varchar2 default NULL )
as
l_free_blks number;
l_total_blocks number;
l_total_bytes number;
l_unused_blocks number;
l_unused_bytes number;
l_LastUsedExtFileId number;
l_LastUsedExtBlockId number;
l_last_used_block number;
procedure p( p_label in varchar2, p_num in number )
is
begin
dbms_output.put_line( rpad(p_label,40,'.') p_num );
end;
begin
dbms_space.free_blocks
( segment_owner => p_owner,
segment_name => p_segname,
segment_type => p_type,
partition_name => p_partition,
freelist_group_id => 0,
free_blks => l_free_blks );
dbms_space.unused_space
( segment_owner => p_owner,
segment_name => p_segname,
segment_type => p_type,
partition_name => p_partition,
total_blocks => l_total_blocks,
total_bytes => l_total_bytes,
unused_blocks => l_unused_blocks,
unused_bytes => l_unused_bytes,
last_used_extent_file_id => l_LastUsedExtFileId,
last_used_extent_block_id => l_LastUsedExtBlockId,
last_used_block => l_last_used_block );
p( 'Free Blocks', l_free_blks );
p( 'Total Blocks', l_total_blocks );
p( 'Total Bytes', l_total_bytes );
p( 'Unused Blocks', l_unused_blocks );
p( 'Unused Bytes', l_unused_bytes );
p( 'Last Used Ext FileId', l_LastUsedExtFileId );
p( 'Last Used Ext BlockId', l_LastUsedExtBlockId );
p( 'Last Used Block', l_last_used_block );
end;
过程已创建。
SQL> create table t1(a char(1000)) storage( freelists 3);
表已创建。
SQL> set serveroutput on;
SQL> exec show_space('T1');
Free Blocks.............................0 <==Number of blocks on freelist
Total Blocks............................5 <==Total data blocks in segment
Total Bytes.............................20480 <==Total bytes in segment
Unused Blocks...........................4 <==Total unused blocks in segment
Unused Bytes............................16384 <==Total unused bytes in segment
Last Used Ext FileId....................15 <==File id of last used extent
Last Used Ext BlockId...................562 <==Block id of last used extent
Last Used Block.........................1 <==Last used block in extent
PL/SQL 过程已成功完成。
有关show_space的进一步使用技巧可参考文献5。以下利用上面得到的数据对segment header block进行dump。
SQL>alter system dump datafile 15 block 562;
在udump/ora10792.trc中
*** 2004-09-08 15:29:57.343
Start dump data blocks tsn: 27 file#: 15 minblk 562 maxblk 562
buffer tsn: 27 rdba: 0x03c00232 (15/562)
scn: 0x0000.064560e4 seq: 0x02 flg: 0x00 tail: 0x60e41002
frmt: 0x02 chkval: 0x0000 type: 0x10=DATA SEGMENT HEADER - UNLIMITED
Extent Control Header
-----------------------------------------------------------------
Extent Header:: spare1: 0 space2: 0 #extents: 1 #blocks: 4
last map 0x00000000 #maps: 0 offset: 2080
Highwater:: 0x03c00233 ext#: 0 blk#: 0 ext size: 4
#blocks in seg. hdr's freelists: 0
#blocks below: 0
mapblk 0x00000000 offset: 0
Unlocked
Map Header:: next 0x00000000 #extents: 1 obj#: 60033 flag: 0x40000000
Extent Map
-----------------------------------------------------------------
0x03c00233 length: 4
nfl = 3, nfb = 1 typ = 1 nxf = 0
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
SEG LST:: flg: UNUSED lhd: 0x00000000 ltl: 0x00000000
End dump data blocks tsn: 27 file#: 15 minblk 562 maxblk 562
对于上述块中字段的说明，以及相关试验。
由于篇幅所限，本文不再列举。可参考文献7。
对非segment header的data block的dump方法和上述类似。data block的结构和segment header block不一样，假如需要了解，可查阅参考文献和资料。
3.2 提取HWM信息3.2.1 HWM位置
HWM位置按下面的公式计算:
HWM = useed byte = Total Bytes - Unused Blocks
Total Bytes和Unused Blocks都可以用show_space提取。
还可以通过ANALYZE tables得到HWM信息. DBA_TABLES视图中包含了可用于各表空间分析的列。其中blocks代表已使用过的块即HWM，empty_blocks代表未使用的空间。
3.2.1 HWM下空间利用信息
要比较有数据行的块的块数和HIGH WATER MARK下总块数，可以用下面的公式来展示HWM下未用空间的比例。
p = 1- r/h
r:有数据行的块的块数
h:HWM下的块数.
r可以通过如下方法获得：
Oracle7:
SELECT count(distinct substr(rowid, 15,4) substr(rowid, 1,8) ) FROM schema.table;
Oracle8 and Oracle9:
SELECT count(distinct substr(rowid, 7,3) substr(rowid, 10,6) ) FROM schema.table;
假如公式计算的结果 p是0，就不需要对表进行重建。假如结果p大于0,应该考虑系统状况和应用需要来决定是否需要总组表。
4.优化4.1手工回收存储空间
在HIGH WATER MARK以上的块对性能没有影响，但是会耗费空间。如何空间大小是一个考虑的问题，就可以决定回收空块。
假设表T1的存储示意图如图2.5所示，使用ALTER TABLE ... DEALLOCATE UNUSED语句可以回收HWM以上的空间。比如：
alter table t1 deallocate unused;
回收后T1的存储示意如图4.1.1
图4.1.1
假如在ALTER TABLE ... DEALLOCATE UNUSED语句中使用了KEEP要害字，则可以在HWM之后保留指定大小的空闲空间，比如：
alter table t1 deallocate unused keep 10K;
回收后T1的存储示意如图4.1.2
图4.1.2
4.2删减表
根据3.2.1可以得到HWM以下块的使用情况。如何p大于时，对全表扫描性能会产生影响，同时也会耗用空间。
假如能够确认应用有良好的索引几乎不会用到全表扫描，那么HIGH WATER MARK以下的空块，尽管耗费了空间，不会对访问产生影响。假如不能确定，那么就需要考虑删减表。
删减表的操作将删除表中所有的记录，并且重置HWM标记。表在删减之后将成为一个空表。
在Oracle中删减表只有如下的两种办法：
1.使用drop语句
先使用drop语句删除整个表，然后再重建这个表。在删除-重建的过程中，与表相关的所有索引、完整性约束以及触发器都会丢失，并且所有依靠于该表的对象都会变为INVALID状态，同时原来争对表的授权也会失效。因此采用这种方式删除表中的记录代价太大。
2．使用TRUNCATE语句
TRUNCATE语句属于DDL语句，不会产生任何回退信息，并且被立即自动提交。在执行TRUNCATE语句时不会影响到与被删减表相关的任何数据库对象与授权，也不会触发表中所定义的触发器。此外，在对标进行删减时，HWM将重置，已经为表分配的存储空间将被回收。
在执行TRUNCATE语句时，可以通过drop storage子句和reuse storage子句来控制被释放的区是否回收到表空间中。如何作在线系统的TRUNCATE，不希望表长时间锁住，那么可以使用reuse storage子句，仅将HWM重置。
4.3 free list优化
free list 竞争出现在多个进程使用同一个free list并试图同时修改free list头部数据块时。可以通过查询视图v$waitsate的class类型为data block 的记录来检查竞争情况。
产生data block类型竞争的主要原因是多个进程试图同时修改free list头部数据块。 然而，它也会出现在当进程预备将块读入buffer cathe时，另一个进程需要访问同一个块。假如能在V$session_WAIT中正好捕捉buffer busy waits，就可以通过查询V$SESSION_WAIT中的P3来判定是那一类。A 0 或 1014代表读类型，其他的值为修改竞争的类型。
下一步需要确定竞争涉及那些段。 假如能够在V$SESSION_WAIT捕捉waits，就可以用P1和P2的值 (对应file 和 block) 在DBA_EXTENTS中找到段名。 如何是一个表，就很可能需要重建表来创建更多的process freelists。 一种计算需要创建多少个freelist的方法是dump一些段中接近HWM的块，检查interested transaction list的个数，具体方法可参见3.1。interested transactions个数的峰值加1 就是需要的最小process freelists的值。
从2.3和2.4可以看出，使用多个free list可能导致更多的空块未被使用， 也可能导致段更快地扩展。
假如性能是当前所关心的重点，那么多free lists 可以用来提高并发访问能力，当然会增加一些额外空间的耗用。然而，假如空间使用大小是首先考虑的因素，那么推荐使用single freelist，使参数FREELISTS=1, 当然就不能提升并发事务的性能了。
V$WAITSTAT 也可显示其他类型class的竞争，包括segment header 和free list。 出现在同一个free list group中多个事务需要同时更新它们的free list header记录时。 有多种方法来解决这个问题如重建表采用更多的free list groups,或者增加 _bump_highwater_mark_count大小，或者调整应用本身。
参考文献和资料：
1.《FREELISTS and FREELIST GROUPS. SCOPE & application 》
2.《INITRANS, MAXTRANS, FREELISTS and FREELIST GROUPS, PCTFREE and PCTUSED》,Mike Ault
3.《Freelist Internals: An OverviewKnowledge》,XPert for Oracle Administration
4．《Blockdump - 8.x Data Segment Header in Oracle》
5．《AskTom dbms_space_free_space》，http://asktom.oracle.com
6．《Data Blocks and Freelists》，http://www.ixora.com.au
7．《偷窥Data block 的物理结构》，http://www.itpub.net
8．《Oracle 9i for windows nt/2000数据系统培训教程》,清华大学出版社
上述部分文章在我的blog网站http://blog.csdn.net/youbo2004上可找到，对于研究free list,free list group和block等有很好的帮助。
