百篇博客系列篇.本篇为:
v63.xx 鸿蒙内核源码分析(文件系统篇) | 用图书管理说文件系统 | 51 .c .h .o
文件系统相关篇为:
本篇讲一个大型图书馆的管理方案,来说清楚计算机文件系统是如何管理的.如果读懂了这个方案,就基本了解了文件系统最底层的运行机制.
如何建图书馆
假如给你一个100*100米,高10米的场地用于建图书馆,放置全世界的图书档案,有以下几个运营要求:
- 图书有大有小,差异巨大,比如一本大英百科全书,估计有几百万页,同时也有只有薄薄一页的一封电报.
- 图书不是一次性给齐,后续不断有新增的,修改的,删除的,比如第一次给的24史不全只有12本,后面陆陆续续补上了.
- 书的规模是千万级的.必须要在最短的时间内找到书,新书也要在最短的时间内找到地方搁置.
- 每一次对书的操作都要记录下来,比如何时入库,何时修改,何时被借阅了.
- 权限验证,不同的人对书有不同的权限,比如有的人可以在书上涂鸦,但有的人只能看.
- 图书馆必须安全,不能因为局部失火导致整个图书馆不能正常运营.
- 可以存放目录信息,每个人都可以建自己的书籍目录,要求这些目录信息也能被保存.
- 让借书,还书,拿目录信息变简单,每个人只凭条形码操作.
请问如果是你会如何设计这个图书馆?并让它即安全又高效的运行.
小易的解决方案
有个叫小易的小伙子提出了一种解决方案:
-
全仓库建大小相同的格子,这种格子统一叫单元格.甭管是什么内容最后都是放到格子里,若每个格子按 0.250.250.25 米算, 整个场地可建设成 640万个单元格.单元格有唯一且统一的编号.从
0一直编到640万-1. -
因为单元格太多,管理非常复杂,所以将场地分成大A区,大B区,大C区,…N区,比如分成8大区,每个区分配80万个单元格. 大A区编号[0 - 799999],…依次类推.
-
每个大区又划分成统计区,目录区,图书区.
- 统计区是描述整个图书馆和各分区的信息数据,占用1000个单元格
- 目录区是为管理本分区图书而产生的信息,占19000个单元格,分成三块:
- 索引表块(占18900个单元格):小易规定后续将用一页纸来记录书的索引信息,并把这页纸叫索引页,将索引页装订成一本索引表书,这本书有连续的统一的页编号(也叫条形码). 像大英百科全书这样有几百万页的一本书,不管后续在图书区里占用多少单元格,但其在索引表书中就是一张纸,这张纸有固定格式,记录书的名称,权限,修改时间等等信息.
- 索引页位图块(占10个单元格):记录索引页的使用情况,
0|1代表未使用|已使用. - 图书区单元格位图块(:占90个单元格):记录数据区单元格的使用情况,
0|1代表未使用|已使用.
- 图书区里放的是真正要管理的书籍,按单元格的容量来放,大点的书会分成多个单元格来存放.共占78万个单元格.
将以上信息简化成树形图表示如下:
└─图书馆 => 共 640万个单元格,平均被分成八大战区 ├─大A区 => 80万单元格 │ ├─图书区 => 78万个单元格 │ ├─目录区 => 19000个单元格 │ │ ├─图书区单元格位图块 => 90个单元格 │ │ ├─索引表块 => 18900 个单元格 │ │ │ ├─A文件索引页 => 信息登记表,占一页纸,描述一本书的名称,权限,时间 │ │ │ ├─... │ │ │ └─B目录索引页 │ │ └─索引页位图块 => 10个单元格 │ └─统计区 (1000) └─大B区 ├─图书区 ├─目录区 │ ├─图书区单元格位图块 │ ├─索引表块 │ │ ├─A文件索引页 │ │ ├─... │ │ └─B目录索引页 │ └─索引页位图块 └─统计区 ...
请务必理解这些概念关系,在脑海中形成脑图,这是后续理解整个文件系统如何运作和管理的最关键底层逻辑.以下一一展开说明这些概念.
单元格
因为需求是图书大小没有限制,差别极大,有的书大到上千万页,有的小到只有一页.是个开放问题,需要在空间和时间上进行取舍,不想浪费时间就得浪费空间.没有边界就不可能做特殊处理,这需要标准化的统一管理.如何标准化? 答案是: 建相同的格子
至于是大格子还是小格子可以灵活,但必须是一样尺寸的.这里建 0.25*0.25*0.25米的标准格,可放1000页(1K页)书的,统一按页数放,放满1000页就换个格子放剩下的. 格子是书的关系是(N:1)的关系,即一本书可以分多个格子放,但一个格子中不能放两本不一样的书. 没错,其中就会存在浪费的问题,但浪费就是浪费了. 表现如下:
- 如果一本书只有一页,那也要占一个格子,等于浪费掉999页的空间,注意不再往里面放其他书,否则管理会非常的麻烦.
- 而99999页的大英百科,将被分成100份,最后的999页也占个格子,等于浪费掉一页的空间.
- 当然,如果已知该图书馆将放置的基本都是10K页厚的书就可以按10K页的格子来建设,这样格子就少了,节省了查找的时间. 但如果基本都是10页的书就可以按10页来划格子,节省了空间但换来更多的格子.总之要在时间和空间上取一个平衡.你想如果将10000页的书放在10页单元格的图书馆中意味着要将书本切成1000份存放,后续维护是非常的耗时的.
统计区
统计区用于统计整个图书馆和各大区的全局信息,这种信息非常的重要,被使用频率极高,就像问我们国家有多少人口一样,马上就要答出来,而不是让各省逐级汇报下加起来再回复你.
整个图书馆的全局信息包括:
战区数: 8
战区名称: A区,B区 ...
单元格的总数: 640W
已用单元格: 330W
剩余单元格: 310W
战区单元格范围: A区(0 ~ 799999),B区(800000 ~ ...) ....
索引页编号:A区(0~99999),B区(100000 ~ ...)
图书馆的创建时间:1921年 xx月
图书馆的名称: 世界图书馆
历史大事件: 1949年....
1956年....
列表描述各大分区基本信息
A分区 基本信息...
B分区 基本信息...
C分区 基本信息...
- 整个图书馆全局信息为何不单独于各分区放置,而要在每个分区都保存一份呢? 原因是因为防止数据被损坏,这么重要的数据只有一份如果哪天图书馆着火了放置那部分单元格被火烧掉了,那就歇菜了,整个图书馆都不能正常运作,所以用多份存档的方式是为了数据的安全.烧了东边还有西边撒,虽然会牺牲空间,但图书馆的安全健壮性却上了台阶.各分区的基本信息会有描述,但对分区更详细的信息会在分区的全局信息块中描述.这相当于广东省总人口会在中央登记下,但具体下属市,区,街道办的人口数据广东省自己维护了.
各分区全局信息包括
战区名称: A区
战区范围: (0 ~ 799999)
单元格的总数: 80W
已用单元格: 20W
剩余单元格: 60W
数据块总数:78W
索引块总数:19000
....
目录区
这个区和统计区一样,是因为要高效的管理图书区而衍生出来的区.目录区和图书区所分配单元格数量是在图书馆开业那天就定下来了,填满图书区单元格的真正的图书,而谁也不知道会有些什么图书要进进出出,图书大小决定了单元格的使用情况,每本书会占用一张索引页,所以最后一定会出现两种情况:
- 索引页用完了,但图书区还有格子没被填满.这种情况出现在大量的小而多图书,因为多占用的索引页就会多,因为小占用的图书区单元格就会少.
- 反之,另一种情况是索引页没用完,但图书区没单元格了.这种情况出现在大量的大而少图书,因为大占用图书区单元格就会多,因为少索引页就会少.
- 这就是为什么有时看着明明磁盘还有很大空间,但就是存储进去的原因所在.因为该分区小文件太多了,试着删除那些很小而不用的文件试试.
索引表
完全可以把索引表看成是一本书,书的内容是一页一页的索引页,每一页记录一本书的索引信息,1000页就可以记录1000本书的索引信息,这本书也是要装到格子里的.装这本书的单元格叫索引表块. 如果按1000万本书计算 就会生成1000万张索引页, 每个格子1000页,那么 1000万/1000 = 1万 ,也就是说 索引表这本书,需要1万个单元格来存放. 索引页也有全局唯一且统一的编号,注意这个编号和单元格的编号是两码事,这是很多人搞不明白文件系统的关键所在,二者编号范围在统计区有保存.
大分区中三个分区(统计区,目录区,图书区)的排列格式是固定的.,所以很容易计算出某个分区下索引区块的开始和结束位置.这里假定索引表块在分区相对位置的第3000个单元格开始.
如何借书
此时外部人员可凭条形码来取书.流程如下:
- 技术部的屌丝小王拿着
5300这个数字(条形码)来取书. - 管理员需先锁定这个条形码在哪个大分区,在统计区一查发现在大A区,
索引页编号:A区(0~99999) - 管理员立即计算索引页存放的格子位置(3000+5300/1000)=3006号格子,搬梯子手机拍照第
300页的内容.内容如下:名称: 编程珠玑 大小: 14284页 占用图书区总格子数: 15 单元格大小: 1000页 属于普通文件 条形码: 5300 捆绑数: 2人 权限: (0644/-rw-r-----) 用户ID: ( 10/ 小张) 组ID: (2/ 技术部) 访问时间: 2021-07-24 02:07:21.683190622 -0700 修改书籍时间: 2021-07-21 00:17:34.733766830 -0700 修改索引时间: 2021-07-29 01:20:14.314343117 -0700 图书区存放位置:12,32,45,....980- 管理员先验权限和所属,表上已经说的很清楚,这本书主人是技术部的小张.
- 小张本人
rw-对这本书可以读,可以修改. - 技术部同学
r--对这本书只能读,屌丝小王属于技术部,所以可以借,但不能在上面涂鸦. - 非技术部同学
---说明没有任何权限. - 索引表上清晰的记录了书本的名称,总页数,格子的大小,条形码.
- 数据块号: 15 代表编程珠玑放在大A区图书区的15个格子里,
12,32,45 ....给出了格子的编号,编程珠玑是按编号顺序存放的. - 有了图书区存放位置管理员再依次把书拷贝一份出来,按顺序叠放好,形成完整的编程珠玑交给屌丝小王,同时将借阅数: 2人 改成3人,把访问时间改成当前时间.
两个位图块
如果屌丝小王也想像小张一样,将爱书论程序员的自我修养捐给图书馆,流程又是怎样的呢?
很明显需要增加两部分内容:
- 索引页 ,
论程序员的自我修养将在索引表中有张单独的索引页记录信息,这需要一张干净的索引页. - 图书区单元格, 实际存放
论程序员的自我修养内容的单元格,占用多少单元格取决于书的大小.这需要一批干净的单元格.
注意虽然索引页编号是按顺序编的,一个号接一个号的在索引表这本书里.但是图书馆运营久了有些书是会被销毁的,例如: 条形码为200的delphi程序设计这本书太老太久没人借站着位置就被销毁了,但擦涂的是第200索引页上的记录, 第200页这张纸还是存在的,一直在 199 - 201 页之间. 擦洗干净了谁管你以前是干什么的, 又可用于记录新书的索引信息.那么如何能快速的知道哪些索引页和图书区单元格没有被使用呢? 答案是: 索引页位图块 和 图书区单元格位图块
可以把索引页位图看成是一本书,书的内容是一页一页的位图页,存放这本书的单元格叫 索引页位图块.
将 位图页 画成 100*100的如下格子
010101011010110101010101110101010101101011
101011010101010110101101011010101010101010
110101010101101011010110101010110101101011
010110101101010101011001110101101011010110
101011010101010110101101011010101010101010
110101010101101011010110101010110101101011
011110101101010101010101110101101011010110
010110101101010101011001110101101011010110
101011010101010110101101011010101010101010
....
每一位代表一个索引页的使用情况,上面说了1000万本图书对应就会有1000万张索引页,而一张位图页能标识100100=1万张索引页的使用情况.
总的计算公式就是:
1000万索引页/(100100)=1千张位图页/1000=1个索引页位图块
也就是说只需要一个格子就能装下1000万的索引占用情况.
同样的道理适用于 图书区单元格位图块,它记录的是图书区单元格的使用情况.位图是最简单最高效的记录两种状态是否变更的方法.
如何捐书
有了以上的基础,小王捐书的流程就简单了.
- 从索引页位图中找一个没有被使用
0的索引页,同时在页中标记为1,比如 条形码为9527的可用 - 根据书本的大小来计算需要多少个数据块来存放
论程序员的自我修养,因为程序眼屌丝的书都很厚,例如 9888页,一个单元格放1000页,就需要10个单元格. - 再从数据块位图中找到没有被使用
0的10个单元格,同时在页中标记为1,比如数据块编号3,89,765,...,因不断的变动,很大概率是找不到连续的单元格. - 这时就可以创建属于
论程序员的自我修养这本书的索引页了.如下名称: 论程序员的自我修养 大小: 9888页 数据块号: 10 单元格大小: 1000页 属于普通文件 条形码: 9527 硬链接数: 1人 权限: (0644/-rw-r-----) 用户ID: ( 4/ 屌丝小王) 组ID: (2/ 技术部) 访问时间: 2021-08-04 03:07:21.683190622 -0700 修改书籍时间: 2021-08-04 00:45:34.733766830 -0700 修改索引时间: 2021-08-04 01:20:14.314343117 -0700 数据块位置:3,89,765,...
目录项
能否用小易的方案记录以下这种信息关系?
├── 金庸小说全集 (条形码:322 )
│ ├── 射雕英雄传 (条形码:1245 )
│ ├── 神雕侠侣 (条形码:23456 )
│ ├── 鹿鼎记 (条形码:34567 )
其实也是可以的金庸小说全集虽看似一个目录,但他们在索引区没有太多的区别,金庸小说全集目录同样有一张索引页,内容如下:
名称: 金庸小说全集/
大小: 1页 数据块号: 1 单元格大小: 1000页 目录
条形码: 322 捆绑数: 17
权限: (0755/drwxr-xr-x) 用户ID: ( 10/ 小张) 组ID: (2/ 技术部)
Access: 2021-08-03 22:11:49.021942010 -0700
Modify: 2021-07-23 18:53:38.656550199 -0700
Change: 2021-07-23 18:53:38.656550199 -0700
数据块位置:15
- 唯一的差别是索引页中挑明了它是个目录.这个等于告诉了管理员如何取数据块的数据.目录中的内容如射雕英雄传的索引信息并不在金庸小说全集的索引页中体现.因为索引页的大小是有限的,不能承载太多的内容,不确定的因素都移到了数据块区.
- 数据块位置:
15中存的是射雕英雄传等的条形码,1245,23456,34567,有了条形码就能找到索引页,找到索引页就找到了一切
映射关系
小易的方案基本是文件系统的底层实现.理解了这套方案对后续基于源码理解鸿蒙文件系统的实现会变得简单, 图书馆系统和计算机文件系统概念映射关系如下
小易方案 - > ext 文件系统
大A区 - > 块组(group)
统计区 - > 超级块(super block)
分区描述列表 - > 块组描述符(GDT)
索引表块 - > 索引表(index table)
索引页 - > 索引节点(inode)
条形码 - > 索引编号(inode.id)
图书区位图块 - > 数据块位图(Blocks bitmap)
索引页位图块 - > 索引位图(inode bitmap)
单元格 - > 逻辑块(Blocks)
目录区 - > 索引块(inode Blocks)
图书区 - > 数据块(date Blocks)
百篇博客.往期回顾
在加注过程中，整理出以下文章。内容立足源码，常以生活场景打比方尽可能多的将内核知识点置入某种场景，具有画面感，容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念，那没什么意思。更希望让内核变得栩栩如生，倍感亲切.确实有难度，自不量力，但已经出发，回头已是不可能的了。 😛
与代码有bug需不断debug一样，文章和注解内容会存在不少错漏之处，请多包涵，但会反复修正，持续更新，.xx代表修改的次数，精雕细琢，言简意赅，力求打造精品内容。
关于 51 .c .h .o
看系列篇文章会常看到 51 .c .h .o，希望这对大家阅读不会造成影响.
分别对应以下四个站点的首个字符，感谢这些站点一直以来对系列篇的支持和推荐，尤其是 oschina gitee ，很喜欢它的界面风格，简洁大方，让人感觉到开源的伟大!
而巧合的是.c .h .o是C语言的头/源/目标文件，这就很有意思了，冥冥之中似有天数，将这四个宝贝以这种方式融合在一起. 51 .c .h .o ， 我要CHO ，嗯嗯，hin 顺口 : )
百万汉字注解.百篇博客分析
百万汉字注解 >> 精读鸿蒙源码，中文注解分析， 深挖地基工程，大脑永久记忆，四大码仓每日同步更新< gitee | github | csdn | coding >
百篇博客分析 >> 故事说内核，问答式导读，生活式比喻，表格化说明，图形化展示，主流站点定期更新中< 51cto | csdn | harmony | osc >
关注不迷路.代码即人生
原创不易，欢迎转载，但麻烦请注明出处.