UNIX程式设计师手册第二版

NFS version 3于1995年公布,更正了NFS v2的大部份的问题. (security
的问题是在RPC上面. RPC本来就有提供security的机制,只是少有实作而
已...) 由于NFS v3出现蛮晚的,有支援的Unix可能算很赶的上流行了:)

本章提到两个dedicated NFS server. 我比较有兴趣的是Auspex NS5000.
另外一个是IBM的, focus在容错. Auspex NS5000有好几个CPU, 每个CPU
都作单一个事,分成两组,一组处理网路上的需求,另一组处理硬碟档案系
统的IO.另外有一个CPU跑修改过的SunOS,admin用,其他的CPU都跑一个叫
做functional multiprocessing kenel (FMK)的系统,彼此间用message
passing交谈. FMK的好处是他只提供作NFS server所必要的function,
而不提供Unix的语意/环境,使得系统省下不少负担.

RFS没什么好提的...

AFS, Andrew File System是CMU发展的系统, 后来成立Transarc
Corporation.继续发展. 后来AFS演变成OSF DCE的Distributed File
System.本书AFS/DFS都有详细的介绍.他们太复杂了,看书比较清楚.
结论是AFS比较不好, DFS作了很多改善, 功能也比较多. DFS比较特
别的是对分散式档案系统cache的改进. DFS server会给他的client
一个(read/write/status/lock..)token, 允许他(read/write/status
/lock..)等等的动作而不需要与server synchronize,也不用
update cache.也就是说该client拥有该资料的使用权(token,权杖之意).
client拥有token直到kernel撤回这样权力为止.kernel随时可撤回
这些token,表示有人要更改data,需要synchronize了.

token的想法非常的高明,因为传统的方法所有的时间都要synchronize.但是
token的想法则是考虑到大部份的时间内皆不会产生race condition,所以
不需要每个动作都synchronize.

不过文中也指出, DFS非常的复杂, 不好实作就是了.


Chapter 11 Advanced File Systems

首先提到interleave的问题.不懂interleave的人可以看这里. 这里提到一个关键
性的bench mark. Unix filesytem的效率在于写入资料的速度. 因为Unix系统的
cache作的已经很好了, 所以read()大部份都发生在cache上, 但是write()则必须
把资料写到硬碟去,变成了bottleneck. 如何改善write()的速度就可以提升
整体效率.

皆下来讨论kernel要如何把资料写到disk上,在crash时有最小的 损失,
fsck才能够做到最大的复原.

File System Clustering (Sun-FFS)

一般的档案存取都是sequential的,虽然会透过好几个read/write system call
达成. 如果kernel也可以像C stdio一样收集这些data block,然后再一起写到
disk去可以增加效率,这就是file system clustering. SunOS首先提出这种办法,
后来SVR4和4.4BSD也都采用了. file system clustering提升了不少FFS的效率,
使得FFS仍然足以与新提出的档案系统匹敌.


The Journaling Approach

这里logging = journaling, 意思是记录. journaling file system or
logging file system (jfs or lfs)基本上就是把对file system的修改
(包括对档案属性,档案内容,档案大小的修改)都以append only的方式附
加(记录)到单一的档案(磁碟空间)去.最主要的目的是crash之后,只有最
后append的部份有可能出问题, fsck的速度极快(只要放弃最后那段log
就可以了). 不过这样说好像太简单了,实际上lfs还要复杂些,有些race
 condition要处理.

一个档案由两个资料组成, 一个是data, 另一个叫meta-data,指的是档案
的permission,access time, modify time,...等等.

我们可以下面的特性来区分lfs:

log 什么东西? data, metadata都log, 或者是只记录meta-data. meta-data
logging更可进一步决定是所有对档案属性的改变都记录起来, 或者只记录影
响档案系统结构的改变就好了. (time-stamps, ownership, permissions等要
是当机时没改到基本上不会影响档案系统的完整)

实作的方式是使用纯LFS(log-structured file system),另一者是用lfs
的概念辅助FFS,改善crash的处理(log-enhanced file system). 纯LFS需
要full data logging, 辅助性lfs通常就是mata-data logging而已.

crash recovery方法也有两种, 一种是redo-only log,另外一种是undo-redo.
redo-only log在 crash后把残余的log继续做完. undo-redo log则可以选择
redo或undo.不同点差在crash 后的处理. redo-only较省disk space,
但是crash recovery有较多synchronization 的问题会出现. undo-redo
的方式有较多的的优点,有synchronization 问题的地方可以把档案还原.
既然要undo,就会记录档案原来的资料, 当然较浪费空间.

本章讨论的两个lfs, 4.4BSD LFS和 Episode File System (by
Transarc,由AFS衍生出来). Episode是OSF DCE标准采用的local
file system, 是DFS的基础. 4.4BSD LFS是根据Sprite作业系统
的研究而来的. LFS使用redo-only log. Episode使用redo-undo log.

对LFS还是搞不清楚什么是append only log? 没关系, 看了4.4BSD LFS后就瞭解了.
Figure 11-2一目了然. LFS基本上把DISK当成是一条磁带,每个block大小为0.5 MB.
一个block在disk上是一段连续的空间, 不过相邻的(logically..) block则没有在
disk上相邻, 而是用list的方式相邻. 用程式表示如下:

    struct log_segment {    /* block在LFS的术语里面叫log segment */

        int next;    /* 下一个log_segment 所在的位址 */

        char data[0.5MB-sizeof(int)];

    };

    而FFS则是在disk上以渐进的方式动态配置新的log segment以记录log.
    segment间以linked list的方式串在一起.

Kernel记录的log就是这样子记录到disk上的. 在这个segment chain
的tail才是整个档案系统的最新资料.不过旧的资料也没有被盖掉就是了.

LFS还有一个机制, 类似garbagge collection, 更像defragementation.
它使用一个cleaner process来清理旧的log. 这个process会固定的把旧
的log独出来(以segment为单位).然后他会将这个segment的内容与实际
的资料比对,要是这个segment内的资料都是没有用的资料(已被新的资料
所取代了)那么cleaner process就可以把此segment free掉. 如果segment
还有一点东西, 怎么办? 简单! 重写一次,append到最新的log去就好了
嘛(感觉好像nu的speed disk :).

LFS仍然维持directory和inode的架构, 只不过以前的inode是固定
在disk blocks的最前端,而现在inode则是分散各地,存在各log
segment里面. 这样子怎么读这个file system呢? LFS还有一个
inode map, 记录所有inode的位置. inode map被当成是一般的
data一般,也是定期会写到log里面去. kernel就是靠此inode map
作为读取这个档案系统的开端.

大家最感兴趣的, 应该还是效率问题了. 首先LFS需要消耗更为大量
的记忆体才能满足他的运作所需, 有时候是个缺点. 与FFS比较的结
果在大部份的状况下都胜过FFS, 除了在高度多工的时候稍微输了一
点. Sun-FFS (有file system clustering和一些小地方的改进)和
LFS比就不相上下了. BSD LFS在处理meta-data方面较Sun-FFS强(create,
remove, mkdir,rmdir....). 但在read/write等io集中的测试中 Sun
FFS则较快, 特别是LFS cleaner启动的情况下更是如此. 显然
clustering发挥了不少功效.

这边你要谨记在心的是LFS在metadata处理会赢过FFS, 是因为写入
动作较有效率的原因(sequential write), 前面已经提到file system
的瓶颈在write...

Sun FFS和BSD LFS在模拟实际状况的bench mark上的平均分数是
差不多的. LFS比FFS占优势的地方大概是快速的复原能力吧!

本节引用了几份测试报告和bench mark, 有兴趣的可以看参考书目,
看人家如何评量一个档案系统的效能.

本节提到另一个有趣的产品, Write-Anywhere File Layout (WAFL)
system, 是一家名为 Network Appliance Corporation 的 FAServer
系列的NFS产品. WAFL整合了log-structured file system, NVRAM
(non-volatile ram, 像PC cmos的咚咚),和RAID-4磁碟阵列, 提供了
高速的NFS response time. WAFL 有一个特色是许多系统管里者有兴
趣的, 就是snapshot. snapshot就是备份的意思嘛! 也就是系统某一时间
的状态. snapshot在log-structured file system下应该不难制作,
因为所有的资料都用append模式嘛..把cleaner process的功能作个
修改就是了. snapshot 优于传统的备份的原因应该很明显, 传统的
备份过程必须花上一段时间,系统在这段时间内若有修改的话, 这段
时间内的修改则不知道有没有备份到.而snapshot则可以像照相一般
得到系统瞬间的备份.使用者也可以利用snapshot取得旧的档案内容
或达到undelete的功能.

由LFS和Sun-FFS的比较可以瞭解meta-data logging(log-enhanced
file system)存在的原因了, 取长补短嘛. 本章也讨论了meta-data
logging的系统. meta-data logging在商品化的系统上较受欢迎,
成为市场主流, 因为他可以架构在FFS上,改变不会太大, 还可以和
对FFS的改进(如clustering)互相配合,相得益彰.

本章讨论的另一个lfs是Transarc的Episode File System. Episode
采用redo-undo metadata logging, 并且他的file system可以横越
好几个硬碟. Episode也提供了类似snapshot的功能, 称为cloning.
cloning使用copy-on-write的技术,只复制anode (Episode的inode).
Episode在security方面也提供了POSIX式的access-control list (ACL),
提供较传统Unix更为精细的档案属性控制.

要是你可以拦截使用者对某些目录的存取,然后偷天换日一下, 那一定可以
让系统更有趣. 比如说Mail来的时候通知使用者(不用一直polling), 使用者
读某个档时就把目前时间印出来, 使用者open /tcp//时,
就产生对的连线,让没有网路知觉的shell,awk程式也可以
轻松处理网路上的资料.

本章讨论了两个这样的系统,第一个是watchdogs,这是学生的研究作品,
整合性不足. 4.4 BSD Portal file system才可以算完整解决方案.

一个新的File System写起来很复杂, 而一般人可能只想在file system
上加点小功能,比如说on-line compression等等. 4.4BSD和SunSoft皆
提出了Stackable file system的模组化机制,以达到这个目的.
SunSoft的版本在本书写作的时候还在草稿阶段而已.BSD的则是已经放
入4.4BSD原始码内了.


Chapter 12 Kernel Memory Allocation

本章以后开始讨论到记忆体管理的问题了. Chapter 12讨论kernel
如何管理自己所用的资料结构所使用的记忆体,如 inode的配置等问
题. Chapter 13,13,15则是讨论kernel的virtual memory管理. 被
kernel用来放自己的资料结构的记忆体就不能给paging system用,
所以两者之间如何平衡是很重要的.

本章提了好几个memory allocator. 其中提到C Library的malloc所
使用的方法值得提出来和大家分享. malloc配置记忆体是所谓的power
of two free lists.把记忆体分成不同的2的次方的大小
(32,64,128...1024bytes)来管理. 不过allocator保留这些block
的最前面几个byte当作header, 当这块记忆体不用时(free),
则header指向下一个free block, 彼此间是一个list. 而使用中
时header则指向他所属的list. (比如说大小是32的list), 这样
子free()才会知道怎么归还记忆体.如果你有K&R这本书的话, 可
以翻翻看书上的范例是不是这样子作的.

power-of-two的配置方式有个致命的缺点, 就是可使用的空间只有
sizeof(block)-sizeof(header),也就是略小于(32,64,128,...1024).
如果应用程式要一个比如说64bytes的记忆体, 那么64-block就装不下,
要分配一个128-block才行, 造成浪费.回想一下,你写程式是不是很喜欢
malloc(128), malloc(512), malloc(1024)呢? 是不是感觉上
应该对performance比较好呢? 看完这段描述, 那你可能就不会
这么想了. 我想,这也是许多人评论不同的c compiler记忆体管
理优劣的一个地方吧!如果你常自己抓一些source code来安装,
就可以瞭解为什么很多作者都弃系统的library不用,
自己提供malloc了吧.

书上提到power of two的改进法, 称为McKusic-Karels Allocator.
获得4.4BSD和Digital UNIX采用. McKusic-Karels 配置法把一段连
续的记忆体都切成固定的大小, 比如说32bytes, 那么使用中的header
就不用指回他所属的list了, 因为由他的位置kernel就可以知道他属
于哪一国的.

皆下来提到Buddy System, 这是和power of two不太一样的配置法,
优点是free()之后的临接空间可以聚合起来成为较大的可用空间.
(power-of-two这方面作的并不好). 这个优点称为coalescing.并
且Buddy System可以简易的和paging system交换记忆体空间,
使的kernel占用的记忆体空间可以动态的调整. 不过他的performance
不太好, 因为每次release momory,allocator就很贪心的把所有
临接的记忆体空间并起来, 浪费许多时间.

SVR4使用了修改过的Buddy演算法 - Lazy Buddy 作为配置kernel
objects的方法.

Buddy系统和power of two一样, 都是以2^n作为配置记忆体的单位.

Mach, OSF/1使用了另一种方法, Zone Allocator. 这个配置法不
再以2^n作为配置单位, 而是以物件为导向来配置.也就是说allocator