在本文中，我们将以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认识仍是必要的。
这些原理分析和性能优化都建立在探讨的基础上，限于篇幅和本人经验可能存在局限、偏差或谬误。
为了准确文中部分结构和字段的说明直接用英文描述。
限于篇幅本文不对同样很重要的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具有下列属性
flag指示free list 被使用(1)或未使用(0)
free list 链的首块的地址DBA(data block address)
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并不会向相反的方向移动。
HIGH WATER MARK之所以重要是因为它对全表扫描性能的影响。当实施一个全表扫描时，Oracle会读取所有HIGH WATER MARK下的块即使它们是空块。当HIGH WATER MARK 下有很多unused block时实施全表扫描会增加额外的不必要的I/O。它也会在全局共享区中填充很多很多空块。
3.分析方法
存储参数基本上属于oracle internal的东西，因此oralce并没有提供很好的手段来分析。但是对于DBA来说，还是可以通过block dump和DBMS_SPACE等手段来获取部分信息。
