倾力大奉献——ASSM内部存储研究大揭密

d.c.b.a · 发表于 2004-4-28 13:11

搞到这个程度，服了。我在流汗了......

Fenng · 发表于 2004-4-28 13:27

原来的图片都没有了,

呵呵

google · 发表于 2004-4-28 14:14

latch和lock的概念从实现上有什么不同？

我现在总算看懂了文章的一部分，
按我的理解，ASSM里面关键的应该是LEVEL2的块10
0x06800009 Free: 1 Inst: 1 --对应9
0x06800019 Free: 1 Inst: 1 --对应25
0x06800029 Free: 1 Inst: 1 --对应41

从这里可以得到多个Level1的类似块9的BitMapBlock列表.
通过这些BITMAP BLOCK，进程可以获取这个Bitmap Block所控制的data block以及修改该BitMap Block的bit.
因此我猜想Oracle可能是把这些BitMap Block按照一定算法独立分配给了多个Insert/Update进程,如果进程发现不够用了就申请下一个BitMapBlock;
如果BitmapBlock不够用了，就分配一个Extend,这个Extend里面也包含一个BitMap Block,然后修改Level2的最后一个指针指向这个BitMapBlock,我这样理解正确吗？
至于Level3...我猜测是Level2的BitMapBlock也不够空间了，就再分配一个Level2的Bitmap Block，然后把Level3 的最后一个指针指向新分配的Level2的BitMap Block

ps:以前看到biti,piner几位的数据块内部分析就头痛，因为经常dump block看到头晕

，不过现在静下心来仔细研究一下确实能学到很多东西

最初由 biti_rainy 发布
[B]

assm 中  freelist  的功能被分散到多个 block中去了，甚至很多block中去了  。
以前freelist的header都是存放在segment header 中的（freelist group > 1 也不过是一组freelist放一个block而已）

另： bitmap 的修改比 freelist header 的修改速度快的多，不存在锁的问题，而是仅仅可能少量block存在着 cache  buffer chain 的竞争  和  buffer pin 的竞争，这些都是 latch 一级而不是 lock 一级。

另：  和你第一个问题相关，若过多的block的剩余空间信息存储在同一个bitmap  block中，则可能导致 cache  buffer  chain  / buffer  pin 等过度的latch的竞争从而导致和 freelist 一样的效果。

我没确认是不是一个 bitmap  任何情况下始终只保存 16个block的空间状态信息，bitmap也是一个树状的分级结构，是不是所有接点都这样没研究过，即使真的如此。 1/16 的空间，也不是什么太大的问题。 [/B]

yangqingdelphi · 发表于 2004-7-7 17:08

TO: Fenng
怎么没有图片了.你再上传一下,好吗?
谢谢

allanliao · 发表于 2004-7-13 12:14

最初由 biti_rainy 发布
[B]不过粗略的感觉，就是unix file system 的结构原理

[/B]

这个感觉就是"触类旁通"吧?

FILE SYSTEM中的inode被借用到ORACLE的datafile中了; 看看UNIX怎么使用inode的:

【LINUX中的EXT2类型的文件系统的inode】
　　对于 ext2 文件系统来说，硬盘分区首先被划分为一个个的 block，一个 ext2 文件系统上的每个 block 都是一样大小的，但是对于不同的 ext2 文件系统，block 的大小可以有区别。典型的 block 大小是 1024 bytes 或者 4096 bytes。这个大小在创建 ext2 文件系统的时候被决定，它可以由系统管理员指定，也可以由文件系统的创建程序根据硬盘分区的大小，自动选择一个较合理的值。这些 blocks 被聚在一起分成几个大的 block group。每个 block group 中有多少个 block 是固定的。

　　每个 block group 都相对应一个 group descriptor，这些 group descriptor 被聚在一起放在硬盘分区的开头部分，跟在 super block 的后面。所谓 super block，我们下面还要讲到。在这个 descriptor 当中有几个重要的 block 指针。我们这里所说的 block 指针，就是指硬盘分区上的 block 号数，比如，指针的值为 0，我们就说它是指向硬盘分区上的 block 0；指针的值为 1023，我们就说它是指向硬盘分区上的 block 1023。我们注意到，一个硬盘分区上的 block 计数是从 0 开始的，并且这个计数对于这个硬盘分区来说是全局性质的。

　　在 block group 的 group descriptor 中，其中有一个 block 指针指向这个 block group 的 block bitmap，block bitmap 中的每个 bit 表示一个 block，如果该 bit 为 0，表示该 block 中有数据，如果 bit 为 1，则表示该 block 是空闲的。注意，这个 block bitmap 本身也正好只有一个 block 那么大小。假设 block 大小为 S bytes，那么 block bitmap 当中只能记载 8*S 个 block 的情况（因为一个 byte 等于 8 个 bits，而一个 bit 对应一个 block）。这也就是说，一个 block group 最多只能有 8*S*S bytes 这么大。

　　在 block group 的 group descriptor 中另有一个 block 指针指向 inode bitmap，这个 bitmap 同样也是正好有一个 block 那么大，里面的每一个 bit 相对应一个 inode。硬盘上的一个 inode 大体上相对应于文件系统上的一个文件或者目录。关于 inode，我们下面还要进一步讲到。

　　在 block group 的 descriptor 中另一个重要的 block 指针，是指向所谓的 inode table。这个 inode table 就不止一个 block 那么大了。这个 inode table 就是这个 block group 中所聚集到的全部 inode 放在一起形成的。

　　一个 inode 当中记载的最关键的信息，是这个 inode 中的用户数据存放在什么地方。我们在前面提到，一个 inode 大体上相对应于文件系统中的一个文件，那么用户文件的内容存放在什么地方，这就是一个 inode 要回答的问题。一个 inode 通过提供一系列的 block 指针，来回答这个问题。这些 block 指针指向的 block，里面就存放了用户文件的内容。

　　…………

　　现在我们回顾一下。硬盘分区首先被分为好多个 block。这些 block 聚在一起，被分成几组，也就是 block group。每个 block group 都有一个 group descriptor。所有这些 descriptor 被聚在一起，放在硬盘分区的开头部分，跟在 super block 的后面。从 group descriptor 我们可以通过 block 指针，找到这个 block group 的 inode table 和 block bitmap 等等。从 inode table 里面，我们就可以看到一个个的 inode 了。从一个 inode，我们通过它里面的 block 指针，就可以进而找到存放用户数据的那些 block。我们还要提一下，block 指针不是可以到处乱指的。一个 block group 的 block bitmap 和 inode bitmap 以及 inode table，都依次存放在这个 block group 的开头部分，而那些存放用户数据的 block 就紧跟在它们的后面。一个 block group 结束后，另一个 block group 又跟着开始。

　　前面都准备好了以后，我们现在终于可以开始读取文件了。首先要读的，当然是文件系统的根目录。注意，这里所谓的根目录，是相对于这一个文件系统或者说硬盘分区而言的，它并不一定是整个 Linux 操作系统上的根目录。这里的这个 root 目录存放在一个固定的 inode 中，这就是文件系统上的 inode 2。需要提到 inode 计数同 block 计数一样，也是全局性质的。这里需要特别注意的是，inode 计数是从 1 开始的，而前面我们提到过 block 计数是从 0 开始，这个不同在开发程序的时候要特别留心。（这一奇怪的 inode 计数方法，曾经让本文作者大伤脑筋。）

　　那么，我们先来看一下得到一个 inode 号数以后，怎样读取这个 inode 中的用户数据。在 super block 中有一个字段 s_inodes_per_group 记载了每个 block group 中有多少个 inode。用我们得到的 inode 号数除以 s_inodes_per_group，我们就知道了我们要的这个 inode 是在哪一个 block group 里面，这个除法的余数也告诉我们，我们要的这个 inode 是这个 block group 里面的第几个 inode；然后，我们可以先找到这个 block group 的 group descriptor，从这个 descriptor，我们找到这个 group 的 inode table，再从 inode table 找到我们要的第几个 inode，再以后，我们就可以开始读取 inode 中的用户数据了。

　　这个公式是这样的：block_group = (ino - 1) / s_inodes_per_group。这里 ino 就是我们的 inode 号数。而 offset = (ino - 1) % s_inodes_per_group，这个 offset 就指出了我们要的 inode 是这个 block group 里面的第几个 inode。

　　找到这个 inode 之后，我们来具体的看看 inode 是什么样的。

　　struct ext3_inode {
　　__u16 i_mode；　　　　　　　 /* File mode */
　　__u16 i_uid；　　　　　　　　/* Low 16 bits of Owner Uid */
　　__u32 i_size；　　　　　　　 /* 文件大小，单位是 byte */
　　__u32 i_atime；　　　　　　　/* Access time */
　　__u32 i_ctime；　　　　　　　/* Creation time */
　　__u32 i_mtime；　　　　　　　/* Modification time */
　　__u32 i_dtime；　　　　　　　/* Deletion Time */
　　__u16 i_gid；　　　　　　　　/* Low 16 bits of Group Id */
　　__u16 i_links_count；　　　　/* Links count */
　　__u32 i_blocks；　　　　　　 /* blocks 计数 */
　　__u32 i_flags；　　　　　　　/* File flags */
　　__u32 l_i_reserved1；　　　　/* 可以忽略 */
　　__u32 i_block[EXT3_N_BLOCKS]； /* 一组 block 指针 */
　　__u32 i_generation；　　　　 /* 可以忽略 */
　　__u32 i_file_acl；　　　　　 /* 可以忽略 */
　　__u32 i_dir_acl；　　　　　　/* 可以忽略 */
　　__u32 i_faddr；　　　　　　　/* 可以忽略 */
　　__u8 l_i_frag；　　　　　　 /* 可以忽略 */
　　__u8 l_i_fsize；　　　　　　/* 可以忽略 */
　　__u16 i_pad1；　　　　　　　 /* 可以忽略 */
　　__u16 l_i_uid_high；　　　　 /* 可以忽略 */
　　__u16 l_i_gid_high；　　　　 /* 可以忽略 */
　　__u32 l_i_reserved2；　　　　/* 可以忽略 */
　　}；

　　我们看到在 inode 里面可以存放 EXT3_N_BLOCKS（= 15）这么多个 block 指针。用户数据就从这些 block 里面获得。15 个 blocks 不一定放得下全部的用户数据，在这里 ext3 文件系统采取了一种分层的结构。这组 15 个 block 指针的前 12 个是所谓的 direct blocks，里面直接存放的就是用户数据。第 13 个 block，也就是所谓的 indirect block，里面存放的全部是 block 指针，这些 block 指针指向的 block 才被用来存放用户数据。第 14 个 block 是所谓的 double indirect block，里面存放的全是 block 指针，这些 block 指针指向的 block 也被全部用来存放 block 指针，而这些 block 指针指向的 block，才被用来存放用户数据。第 15 个 block 是所谓的 triple indirect block，比上面说的 double indirect block 有多了一层 block 指针。作为练习，读者可以计算一下，这样的分层结构可以使一个 inode 中最多存放多少字节的用户数据。（计算所需的信息是否已经足够？还缺少哪一个关键数据？）

　　一个 inode 里面实际有多少个 block，这是由 inode 字段 i_size 再通过计算得到的。i_size 记录的是文件或者目录的实际大小，用它的值除以 block 的大小，就可以得出这个 inode 一共占有几个 block。注意上面的 i_blocks 字段，粗心的读者可能会以为是这一字段记录了一个 inode 中实际用到多少个 block，其实不是的。那么这一字段是干什么用的呢，读者朋友们可以借这个机会，体验一下阅读 Linux 内核源代码的乐趣。；-)

　　现在我们已经可以读取 inode 的内容了，再往后，我们将要读取文件系统上文件和目录的内容。读取文件的内容，只要把相应的 inode 的内容全部读出来就行了；而目录只是一种固定格式的文件，这个文件按照固定的格式记录了目录中有哪些文件，以及它们的文件名，和 inode 号数等等。

【VXFS/JFS中的inode】

JFS 按需为磁盘 inode 动态地分配空间，同时释放不再需要的空间。这一支持避开了在文件系统创建期间，为磁盘 inode 保留固定数量空间的传统方法，因此用户不再需要估计文件系统包含的文件和目录最大数目。另外，这一支持使磁盘 inode 与固定磁盘位置分离。

【HPUX中的inode】

bdf -i还显示HFS的on-disk inode utilization;(in-core的inode使用情况通过sar -v 1 3查看).

An inode is the data structure on disk and in memory which describes the location and number of blocks required for each file in an HFS file system.

By default,HPUX 10.X中,每6kB磁盘空间会创建一个inode;
在9.x以前,每2kB磁盘空间会创建一个inode;
对于VXFS(JFS),in-core and on-disk inode 都是动态分配的.
缺省的inode个数在使用小的存储和小文件是较合理;在大的存储和大文件场合比较浪费空间.

piner · 发表于 2004-7-14 09:40

三级位图管理与unix的文件系统还是有差别的

应当说，位图管理更类似索引，先有一级块（索引的叶）
然后才有二级块（是指向一级块的指针），然后如果二级块不够，产生新的二级块的时候，会膨胀出新的三级块（是指向二级块的指针）。

文件系统是往下膨胀，而且每个块组中，即存放数据，又存放指针
位图与索引不同的是，往上膨胀的，只有最下层存放真正的数据，上层全部是指针。

再看一个assm的结构图

grassbell · 发表于 2004-7-14 11:50

一口气又把piner的分析的assm和lmt结合起来读了一便，荡气回肠呀！基本消化了

grassbell · 发表于 2004-7-14 13:03

对于segment header的第一个（或多个，如本例）block，记录了后面多少个block的使用情况，
应该取决于第一个extent的大小。后面同理。。。

此例中，表assmtab只有2个extents，每个包括128个blocks
可以看到block 9和10共同来记录后面128个blocks地使用情况，每个分别记录64个。

[php]
SQL> create tablespace assm
  2  datafile 'd:\oracle\oradata\donnydb2\assm01.dbf' size 10m
  3  extent management local
  4  segment space management auto;

Tablespace created.

SQL> create table assmtab(x int) tablespace assm
  2  storage(initial 2000k);

Table created.

SQL> select extent_id,file_id,block_id,bytes from dba_extents where segment_name='ASSMTAB';

EXTENT_ID FILE_ID BLOCK_ID    BYTES
---------- ---------- ---------- ----------
      0       4       9 1048576
      1       4       137 1048576

SQL> exec show_space('ASSMTAB');
Total Blocks............................256
Total Bytes.............................2097152
Unused Blocks...........................252
Unused Bytes............................2064384
Last Used Ext FileId....................4
Last Used Ext BlockId...................8
Last Used Block.........................4

PL/SQL procedure successfully completed.

SQL> alter system dump datafile 4 block 9;

System altered.

SQL> alter system dump datafile 4 block 10;

System altered.

SQL> alter system dump datafile 4 block 11;

System altered.

SQL> alter system dump datafile 4 block 12;

System altered.

SQL>
[/php]

grassbell · 发表于 2004-7-14 13:03

Start dump data blocks tsn: 23 file#: 4 minblk 9 maxblk 9
buffer tsn: 23 rdba: 0x01000009 (4/9)
scn: 0x0000.00603503 seq: 0x02 flg: 0x00 tail: 0x35032002
frmt: 0x02 chkval: 0x0000 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 4 nranges: 1       parent dba:  0x0100000b poffset: 0
unformatted: 60    total: 64       first useful block: 4
owning instance : 1
instance ownership changed at
Last successful Search
Freeness Status:  nf1 0    nf2 0    nf3 0    nf4 0

Extent Map Block Offset: 4294967295
First free datablock : 4
Bitmap block lock opcode 0
Locker xid:    :  0x0000.000.00000000
   Highwater::  0x0100000d  ext#: 0    blk#: 4    ext size: 128
  #blocks in seg. hdr's freelists: 0
  #blocks below: 0
  mapblk  0x00000000  offset: 0
  HWM Flag: HWM Set
  --------------------------------------------------------
  DBA Ranges :
  --------------------------------------------------------
0x01000009  Length: 64    Offset: 0

0:Metadata 1:Metadata 2:Metadata 3:Metadata
4:unformatted 5:unformatted 6:unformatted 7:unformatted
8:unformatted 9:unformatted 10:unformatted 11:unformatted
12:unformatted 13:unformatted 14:unformatted 15:unformatted
16:unformatted 17:unformatted 18:unformatted 19:unformatted
20:unformatted 21:unformatted 22:unformatted 23:unformatted
24:unformatted 25:unformatted 26:unformatted 27:unformatted
28:unformatted 29:unformatted 30:unformatted 31:unformatted
32:unformatted 33:unformatted 34:unformatted 35:unformatted
36:unformatted 37:unformatted 38:unformatted 39:unformatted
40:unformatted 41:unformatted 42:unformatted 43:unformatted
44:unformatted 45:unformatted 46:unformatted 47:unformatted
48:unformatted 49:unformatted 50:unformatted 51:unformatted
52:unformatted 53:unformatted 54:unformatted 55:unformatted
56:unformatted 57:unformatted 58:unformatted 59:unformatted
60:unformatted 61:unformatted 62:unformatted 63:unformatted
  --------------------------------------------------------
End dump data blocks tsn: 23 file#: 4 minblk 9 maxblk 9

*** 2004-07-14 11:56:22.000
Start dump data blocks tsn: 23 file#: 4 minblk 10 maxblk 10
buffer tsn: 23 rdba: 0x0100000a (4/10)
scn: 0x0000.00603503 seq: 0x02 flg: 0x00 tail: 0x35032002
frmt: 0x02 chkval: 0x0000 type: 0x20=FIRST LEVEL BITMAP BLOCK
Dump of First Level Bitmap Block
--------------------------------
nbits : 4 nranges: 1       parent dba:  0x0100000b poffset: 1
unformatted: 64    total: 64       first useful block: 0
owning instance : 1
instance ownership changed at
Last successful Search
Freeness Status:  nf1 0    nf2 0    nf3 0    nf4 0

Extent Map Block Offset: 4294967295
First free datablock : 0
Bitmap block lock opcode 0
Locker xid:    :  0x0000.000.00000000
   Highwater::  0x00000000  ext#: 0    blk#: 0    ext size: 0
  #blocks in seg. hdr's freelists: 0
  #blocks below: 0
  mapblk  0x00000000  offset: 0
  HWM Flag: Not Set
  --------------------------------------------------------
  DBA Ranges :
  --------------------------------------------------------
0x01000049  Length: 64    Offset: 0

0:unformatted 1:unformatted 2:unformatted 3:unformatted
4:unformatted 5:unformatted 6:unformatted 7:unformatted
8:unformatted 9:unformatted 10:unformatted 11:unformatted
12:unformatted 13:unformatted 14:unformatted 15:unformatted
16:unformatted 17:unformatted 18:unformatted 19:unformatted
20:unformatted 21:unformatted 22:unformatted 23:unformatted
24:unformatted 25:unformatted 26:unformatted 27:unformatted
28:unformatted 29:unformatted 30:unformatted 31:unformatted
32:unformatted 33:unformatted 34:unformatted 35:unformatted
36:unformatted 37:unformatted 38:unformatted 39:unformatted
40:unformatted 41:unformatted 42:unformatted 43:unformatted
44:unformatted 45:unformatted 46:unformatted 47:unformatted
48:unformatted 49:unformatted 50:unformatted 51:unformatted
52:unformatted 53:unformatted 54:unformatted 55:unformatted
56:unformatted 57:unformatted 58:unformatted 59:unformatted
60:unformatted 61:unformatted 62:unformatted 63:unformatted
  --------------------------------------------------------
End dump data blocks tsn: 23 file#: 4 minblk 10 maxblk 10

*** 2004-07-14 11:57:24.000
Start dump data blocks tsn: 23 file#: 4 minblk 11 maxblk 11
buffer tsn: 23 rdba: 0x0100000b (4/11)
scn: 0x0000.00603507 seq: 0x02 flg: 0x00 tail: 0x35072102
frmt: 0x02 chkval: 0x0000 type: 0x21=SECOND LEVEL BITMAP BLOCK
Dump of Second Level Bitmap Block
number: 4    nfree: 4    ffree: 0    pdba:    0x0100000c
  opcode:1
xid:
  L1 Ranges :
  --------------------------------------------------------
0x01000009  Free: 5 Inst: 1
0x0100000a  Free: 5 Inst: 1
0x01000089  Free: 5 Inst: 1
0x0100008a  Free: 5 Inst: 1

  --------------------------------------------------------
End dump data blocks tsn: 23 file#: 4 minblk 11 maxblk 11

*** 2004-07-14 11:58:20.000
Start dump data blocks tsn: 23 file#: 4 minblk 12 maxblk 12
buffer tsn: 23 rdba: 0x0100000c (4/12)
scn: 0x0000.00603508 seq: 0x01 flg: 0x00 tail: 0x35082301
frmt: 0x02 chkval: 0x0000 type: 0x23=PAGETABLE SEGMENT HEADER
  Extent Control Header
  -----------------------------------------------------------------
  Extent Header:: spare1: 0    spare2: 0    #extents: 2    #blocks: 256
               last map  0x00000000  #maps: 0    offset: 2716
   Highwater::  0x0100000d  ext#: 0    blk#: 4    ext size: 128
  #blocks in seg. hdr's freelists: 0
  #blocks below: 0
  mapblk  0x00000000  offset: 0
               Unlocked
  --------------------------------------------------------
  Low HighWater Mark :
   Highwater::  0x0100000d  ext#: 0    blk#: 4    ext size: 128
  #blocks in seg. hdr's freelists: 0
  #blocks below: 0
  mapblk  0x00000000  offset: 0
  Level 1 BMB for High HWM block: 0x01000009
  Level 1 BMB for Low HWM block: 0x01000009
  --------------------------------------------------------
  Segment Type: 1 nl2: 1    blksz: 8192 fbsz: 0
  L2 Array start offset:  0x00001434
  First Level 3 BMB:  0x00000000
  L2 Hint for inserts:  0x0100000b
  Last Level 1 BMB:  0x0100008a
  Last Level II BMB:  0x0100000b
  Last Level III BMB:  0x00000000
   Map Header:: next  0x00000000  #extents: 2 obj#: 32839  flag: 0x20000000
  Extent Map
  -----------------------------------------------------------------
0x01000009  length: 128
0x01000089  length: 128

  Auxillary Map
  --------------------------------------------------------
Extent 0    :  L1 dba:  0x01000009 Data dba:  0x0100000d
Extent 1    :  L1 dba:  0x01000089 Data dba:  0x0100008b
  --------------------------------------------------------

Second Level Bitmap block DBAs
--------------------------------------------------------
DBA 1: 0x0100000b

End dump data blocks tsn: 23 file#: 4 minblk 12 maxblk 12

piner · 发表于 2004-7-14 15:20

是的

你的这个结果是很有代表性的，因为开始extent中block太多
一个1级块管理不过来，所以出现了2个1级块。

然后才是1个2级块，最后是段头
所以可以看到4个Metadata的块

[精华] 倾力大奉献——ASSM内部存储研究大揭密

ASSM 和文件系统的类比

[精华] 倾力大奉献——ASSM内部存储研究大揭密

ASSM 和 文件系统的类比

ASSM 和文件系统的类比